Some subsets of the natural numbers can be described by statements in one or the other of our two languages. As we just saw, the set of prime numbers can be expressed by such a statement. Some cannot be described by any statement in our language though. A simple proof of this fact will be presented in the set theory chapter. A set which can be described by a statement is called arithmetic. The accent is on the third syllable, in contrast to its use in phrases like “elementary arithmetic”, where the accent is on the second syllable.
Note that sets of numbers are not part of our language. The closest we have is Boolean expressions with one free variable. We can think of the set of values of the variable which make that expression true but we can’t assign a name to that set within our language.
An example of an arithmetic set is the set of powers of 2. Our language doesn’t have any notation for exponentiation so we can’t just say \({ z }\) is a power of 2 if there is some \({ y }\) such that \({ z = 2 ^ y }\). Instead we can observe that if \({ z }\) is a power of 2 then every divisor of \({ z }\) is either 1 or is a multiple of 2, and conversely that every \({ z }\) with this property is a power of 2. This is something we can translate into our language. “\({ x }\) is a divisor of \({ z }\)” translates as \[ \{ ∃ y . [ ( x · y ) = z ] \} . \] “\({ x }\) is 1” is just \[ ( x = 0 ') . \] “\({ x }\) is a multiple of \({ 2 }\)” is \[ \{ ∃ y . [ x = ( 0'' · y ) ] \} . \] So “every divisor of \({ z }\) is either 1 or a multiple of 2” translates as \[ [ ∀ x . ( \{ ∃ y . [ ( x · y ) = z ] \} ⊃ [ ( x = 0 ') ∨ \{ ∃ y . [ x = ( 0'' · y ) ] \} ] ) ] . \]
Another example of an arithmetic set is the set of Fibonacci numbers, although proving this will require more work. Let \({ f _ n }\) be the \({ n }\)’th Fibonacci number, defined recursively by \[ f _ 0 = 0 , \quad f _ 1 = 1 , \quad f _ { n + 2 } = f _ n + f _ { n + 1 } . \] For \({ n = 1 }\) we have \[ f _ { n + 1 } ^ 2 = f _ n f _ { n + 2 } + ( - 1 ) ^ n . \] Suppose that the equation above holds for \({ n = m }\), i.e. that \[ f _ { m + 1 } ^ 2 = f _ m f _ { m + 2 } + ( - 1 ) ^ m . \] Then \[ \begin{split} f _ { m + 3 } f _ { m + 1 } & = ( f _ { m + 2 } + f _ { m + 1 } ) f _ { m + 1 } \cr & = f _ { m + 2 } f _ { m + 1 } + f _ { m + 1 } ^ 2 \cr & = f _ { m + 2 } f _ { m + 1 } + f _ m f _ { m + 2 } + ( - 1 ) ^ m \cr & = f _ { m + 2 } ( f _ { m + 1 } + f _ m ) + ( - 1 ) ^ m \cr & = f _ { m + 2 } f _ { m + 2 } + ( - 1 ) ^ m \cr & = f _ { m + 2 } ^ 2 - ( - 1 ) ^ { m + 1 } \end{split} \] and therefore \[ f _ { m + 2 } ^ 2 = f _ { m + 3 } f _ { m + 1 } + ( - 1 ) ^ { m + 1 } . \] So \[ f _ { n + 1 } ^ 2 = f _ n f _ { n + 2 } + ( - 1 ) ^ n \] is true also when \({ n = m + 1 }\). Since it holds for \({ n = 0 }\) and holds for \({ n = m + 1 }\) whenever it holds for \({ n = m }\) it must hold for all \({ n }\), by induction. Now \[ f _ { n + 2 } = f _ n + f _ { n + 1 } \] so we can rewrite our relation above as \[ f _ { n + 1 } ^ 2 = f _ n ( f _ n + f _ { n + 1 } ) + ( - 1 ) ^ n . \] Consider the case where \({ n }\) is even, i.e. \({ n = 2 k }\), and let \[ x _ k = f _ { 2 k } , \quad y _ k = f _ { 2 k + 1 } . \] Then the equation above becomes \[ y _ k = x _ k ( x _ k + y _ k ) + 1 . \] Suppose \({ z }\) is a Fibonacci number. Then \({ z = x _ k }\) or \({ z = y _ k }\) for some value of \({ k }\). So, in our language for elementary arithmetic, \[ [ ∃ x . ( ∃ y . \{ ( y · y = \{ [ x · ( x + y ) ] + 1 \} ) ∧ [ ( z = x ) ∨ ( z = y ) ] \} ) ] . \] We’ve just seen that if \({ z }\) is a Fibonacci number then it makes this statement, with our usual interpretation, true. The converse is true as well, although that’s even harder to prove, and I’ll skip this part. So the Fibonacci numbers are described by a statement in our language and so are an arithmetic set.
In addition to arithmetic sets we can also talk about arithmetic relations. These correspond to Boolean expressions with multiple free variables. In fact we’ve seen a few examples already. “… is divisible by …” is an arithmetic relation.