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 \({ x }\) 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.
There is something a bit unsatisfying about the arguments which showed that the powers of two and the Fibonacci numbers are arithmetic. For one thing, we seem to be putting more arithmetic into our language than we are getting out of it. Both sequences are very easy to define but in order to show that their elements are an arithmetic set we needed to borrow some facts from number theory which are considerably deeper than we’d need for the definitions. The other problem is that it’s not clear how to generalise those arguments to other simple sequences, even very closely related ones. We could, for example, use the argument above with only very minor changes to show that the powers of 3 or of 5 are arithmetic sets. For powers of 4 we can use the fact that a number is a power of 4 if and only if it is the square of a power of 2. What about powers of 6, though?
It would be nice to have a general principle saying that, if we can define a sequence within our language, for example by specifying the initial element and a rule for getting from each element to the next, like “start from 1 and keep multiplying by 6”, then the set of values should be arithmetic. It’s possible to do this, but it requires a great deal of preliminary work.