Expressing more complex ideas

All of elementary arithmetic can be expressed in this language, but sometimes a bit of ingenuity is required. Sometimes this is relatively straightforward. We don’t have a \({ < }\) sign, for example, but we can still express the idea that \({ x < z }\). In fact we can do so in many different ways, including

We can also compensate for the lack of subtraction and division signs. \({ x = z - y }\) can be expressed as \({ [ ( x + y ) = z ] }\). The second statement implies \({ ( y ≤ z ) }\), without which the first wouldn’t make sense. Similarly, \({ x = z / y }\) can be expressed as \({ [ ( x · y ) = z ] }\).

Knowing that statements about division can be expressed via statements about multiplication we can see how to express divisibility. The condition that \({ z }\) is divisible by \({ x }\), i.e. that \({ x }\) is a divisor of \({ z }\), for example, can be expressed as \({ \{ ∃ y . [ ( x · y ) = z ] \} }\).

We can also express primality. The following sentence is one way of saying that \({ z }\) is prime: \[ \{ [ ∀ x . ( ∀ y . \{ [ ( x · y ) = z ] ⊃ [ ( x = z ) ∨ ( y = z ) ] \} ) ] ∧ ( 0 '' ≤ z ) \} . \] As with all statements, this one is best understood by breaking it into smaller phrases. Starting with \[ [ ∀ x . ( ∀ y . \{ [ ( x · y ) = z ] ⊃ [ ( x = z ) ∨ ( y = z ) ] \} ) ] \] we can peel off the universal quantifiers and and ask when \[ \{ [ ( x · y ) = z ] ⊃ [ ( x = z ) ∨ ( y = z ) ] \} \] is true. This means if \({ [ ( x · y ) = z ] }\), i.e. if \({ z }\) is the product of \({ x }\) and \({ y }\), then \({ [ ( x = z ) ∨ ( y = z ) ] }\), i.e. at least one of \({ x }\) or \({ y }\) is equal to \({ z }\). Since the only way to write a prime as a product of natural numbers is 1 times itself, in either order, the statement \[ [ ∀ x . ( ∀ y . \{ [ ( x · y ) = z ] ⊃ [ ( x = z ) ∨ ( y = z ) ] \} ) ] \] is true whenever \({ z }\) is prime. There are two non-prime values of \({ z }\) for which the statement above is true though, \({ 0 }\) and \({ 1 }\). To exclude these we add the additional condition \[ ( 0 '' ≤ z ) , \] which ensures that \({ z }\) is greater than or equal to 2.

We can express even more complicated thoughts. We can say, for example, that there are infinitely many primes. It’s not immediately obvious how to do this. We’ve just seen how to express the fact that any particular number is prime but how can we make a statement about infinitely many numbers in language which doesn’t have a notation for sets or infinity? There is a standard trick for this. To say that there are infinitely many primes we say that for every number \({ w }\) there is a prime number \({ z }\) greater than or equal to \({ w }\). In our language this is \[ \{ ∀ w . [ ∃ z . ( \{ w ≤ z \} ∨ \{ [ ∀ x . ( ∀ y . \{ [ ( x · y ) = z ] ⊃ [ ( x = z ) ∨ ( y = z ) ] \} ) ] ∧ ( 0 '' ≤ z ) \} ) ] \} . \]