natural numbers as sets

Analytic philosophers and logicist mathematicians have discovered that natural numbers are not necessarily a logical primitive. Perhaps the most successful part of the reduction of mathematics to logic is the reduction of natural numbers to sets. Various philosophers/mathematicians have formulated numbers in different ways:

Gottlob Frege

• 0 = {x: ~(x = x)}
• S(n) = {x: [|x| = S(|y|)] & [y ∈ n]}
• (a = n) ↔ (a ∈ n)

Zero is the set of all things that are not identical with themselves; the empty set (∅). The successor of a number is the set of all sets that have a cardinality one higher than every set in that number. A number is the set of all sets that have a cardinality of that number (eg: 2 is the set of all sets that have two members). See also: Zirtix's write-up in logicism.

John von Neumann

• 0 = ∅
• S(n) = {n, {n}}
• 1 = {∅}
• 2 = {∅, {∅}}
• 3 = {∅, (∅}, {∅, {&empty}}}
• (a = n) ↔ (|a| = |n|)

Zero is the empty set. The successor of a number is the set containing that number and all the members of that number. See also: Gorgonzola's write-up in ordinals.

Ernst Zermelo

• 0 = ∅
• S(n) = {n}
• 1 = {∅}
• 2 = {{∅}}
• (a = n) ↔ (n = {^a∅}^a)

Zero is the empty set. The successor of a number is the set containing that number.

---

If you are choosing a reduction of natural numbers you should keep in mind that equality and cardinality are important relations. Therefore, unless you are both a logicist and a mathematical formalist, Zermelo's formulation is difficult to work with. Contrasting the value between Frege and von Neumann's formulations is beyond the scope of this write-up.

---

Source: Philosophy of Logic taught by Micheal Newman at Trent University.

The advantage of von Neumann numerals (defined above in vagary's writeup) may not be obvious. Why did John von Neumann bother to invent a new way of counting with sets, when Zermelo had something which appeared simpler?

Von Neumann numerals extend easily to give a new class of "infinite numbers", called ordinals (or ordinal numbers, depending on which philosophers you believe in). They're not necessary in order to define ordinals, but they are nice. NOTE: I dispense with mathematical rigor in this writeup; consult a good set theory text if you want to die of boredom, but do it right.

To define the finite von Neumann numerals, we used two principles:

"Zero"

0 = {}

"Plus one"

x+1 = {x}∪x

Applying these inductively, we have 1={0}={{}}, 2={{{}},{}}, ... So each finite number gets defined. Now let's try to define the first infinite ordinal, "ω". ω certainly isn't the successor of any ordinal, so we can't use our 2 principles to generate it. We need something new. But what?

Well, note that every von Neumann numeral x satisfies x={y:y<x}. We know we want ω to be the least ordinal greater than every finite ordinal, so let's define ω={{}, {{}}, {{},{{}}}, ...} = ∪_k=0^∞k (here we take exactly the union of all finite k's, expressed as von Neumann numerals). Having defined ω, we can go on: ω+1={ω}∪ω, which is nice. We go on, defining ω+2={ω+1}∪{ω}∪omega;, ..., after which we can define 2ω=∪_k=0^∞(ω+k).

So we know what our third principle should be: it should give us the limit of a set of ordinals as their union. From where should we get the set? Any set of ordinals will do!

"Limit"

If X is a set of ordinals, then ∪X (the union of all the von Neumann numerals for these ordinals) is the ordinal called "the limit of X".

It turns out that ∪X is the smallest von Neumann numeral greater than all elements of X, and that all important properties for ordinals are satisfied.

With the limit principle, we can go on the understand the ordinals kω, ..., ω², ..., ω²+ω, ..., ω^k, ..., ω^ω, ...

But if we can do it for countable ordinals, we could take X to be the set of all countable ordinals (yes, it is a set, not just a class, so everything works out nicely), and get the von Neumann numeral for the first uncountable ordinal. And the process goes on...

Still other "numerals" exist. Among the most interesting are Church numerals, which define natural numbers as functions in the lambda calculus. However, these are not sets in any natural sense.