We consider the signature Σ of arithmetic with two constants 0 and 1 , two two-digit function symbols + and - one two-di
Posted: Tue Jul 12, 2022 12:07 pm
We consider the signature Σ of arithmetic with two constants 0and 1 , two two-digit function symbols + and - one two-digitpredicate symbol < . Many statements about natural numbers (i.e.the Σ - structure with carrier set N and the usual interpretationof the symbols in Σ ) can be expressed as predicate logicalformulas over Σ.
Example: The statement "' x is an even number"' corresponds tothe formula ∃y : (x = y + y) with a free variable x . Transform thefollowing statements into predicate logical formulas over Σ :
(a) "' x divides y + 1 ."'
(b) "' x is a prime number."'
(c) "'There are infinitely many prime numbers'"
(d) ''Every even number ≥ 4 can be represented as the sumof two primes.''
(e) "'All numbers with odd squares are odd.'"
Example: The statement "' x is an even number"' corresponds tothe formula ∃y : (x = y + y) with a free variable x . Transform thefollowing statements into predicate logical formulas over Σ :
(a) "' x divides y + 1 ."'
(b) "' x is a prime number."'
(c) "'There are infinitely many prime numbers'"
(d) ''Every even number ≥ 4 can be represented as the sumof two primes.''
(e) "'All numbers with odd squares are odd.'"