Axioms & Choice


Peano arithmetic is founded upon rules called axioms, which dictate how numbers (or groups of numbers represented as one entity, like those in the set of Complex numbers ℂ) can behave. For the set of natural numbers  including 0, there are 9 such axioms.

0. 0 is a member of the set of numbers ( 0 )
1. For all numbers ( ∀x ), x equals x=x )
2. For all numbers x and y ( ∀xy ), if x=y, then y=x
3. ∀xyz if x=y and y=z, then x=z
4. ∀x∀y if x∈ and x=y, then y∈
5. ∀x there exists a successor number x+1 ( ∃S(x)  )
6. ∀xy S(x)=S(y) if and only if ( iff ) x=y S(x)=S(y)x=y )
7. It is not true that there exists an x where S(x)=0 ( ∄x S(x)=0 )
8. If 0 is a member in X0X ) and if being a member in X implies the successor is a member of XxXS(x)X ), then X contains the set of all numbers ( X )

Pretty foundational mathematics, no? Set theory needs a lot of shorthand to keep track of what injections (preserving unique mappings from on set to another) are actually being made.

The last axiom is really infinitely many, patterning a recursive definition for the set of all natural numbers. These axioms define 2 as S(S(0)) and infinity as S(S(S(…S(0)…))). I should draw the distinction that  is used for elements constituting a set, while  or  is used for sets within sets. The former is used to distinguish proper subsets, like {1, 3, 5} being strictly only part of {0, 1, 2, 3, 4, 5}, while the latter includes redundant subsets, like {8} being a subset of {8}. Notably enough though, there is an empty set or null set {} (sometimes written ∅), which is a subset of everything because it includes nothing.

So why all this material on Piano Peano arithmetic (PA)? It relates in part to Object-Oriented Programming with the “is-a” parental relationship in class hierarchies, but the second-order logic of the Peano axioms is, in fact, not as strong as the Zermelo-Frankel (ZF) system of axioms that we use for most of mathematics. David Hilbert posed the question of PA’s consistency as the second of his 23 Problems.

ZF does not include the Axiom of Choice (AC), which states that given an infinite set of sets of elements, you can make a new set consisting of one element from each set. In other words, if I have infinite sock drawers each with at least one sock, I can take a sock out of each one and put that into a new sock drawer. That makes sense, right? We define the set ZFC to include the axioms of both ZF and AC. But this leads to

Russel’s Paradox

Banach-Tarski Paradox