The axiom of infinity is a bundle of tricks. As I said originally, it does two things. First, it gives us our first infinite set; and second, it sets the stage for representing arithmetic in terms of sets. With the axiom of infinity, we get the natural numbers; with the natural numbers, we can get the integers; with the integers, we can get the rationals. Once we have the rationals, things get a bit harder – but we can get the reals via Dedekind cuts; and by transfinite induction, we can get the transfinite numbers. But before we can get to any of that, we need a sound representation of the naturals in terms of sets.
Let’s look at the statement of the axiom again:
∃N : ∅∈N ∧ (∀x:x∈N ⇒ (x∪{x})∈N).
That’s a classic recursive definition, consisting of a base case and an inductive case. The base tells us the initial value of N – the empty set. And the inductive case shows us how we can construct the further members of N.
Walk through a few steps of that:
- By the base case ∅ ∈ N.
- Since ∅∈N, then ∅∪{∅}={∅}∈N.
- Since {∅}∈N, then {∅}∪{{∅}}={∅,{∅}}∈N.
- Since {∅,{∅}}∈N, then {∅,{∅}}∪{{∅,{∅}}}={∅,{∅},{∅,{∅}}}∈N
So we’re looking at an infinite sequence of values, which have a peculiar property. The N+1th value in the series consists of the set of the first N values – the set of all values that preceeded it.
If you look at this series through the lens of the Peano
axioms, you can see that it works for the integers. ∅ is the initial value, 0. For any number i, there’s a unique successor {i}∪{{i}}. Every member of the set is the successor to exactly one number – the larger number which is a subset of it. There’s only one possible successor to any number. And while it’s less obvious than the others, you can, with the help of some of the other axioms, work through the induction rule, showing that it works. So the axiom of infinity is giving us a set-based view of
the natural numbers.
But we know that the natural numbers aren’t enough to do all of math, right? We’ve seen in other places that the set of natural numbers isn’t large enough – a construction that gives us natural numbers can’t be used to represent all of the reals, because no matter how we do it, the set of naturals is just too small.
That’s where the powerset axiom is going to come in. The powerset – the set of all subsets of this infinite set – is larger than this. And the powerset of that set is still larger. We’ll see more about that later. But first, we’re going to have to start being a lot more precise. So far, we’ve been able to mostly just gloss over the distinction between sets and classes, because everything we’ve talked about so far is a set. But when we start getting into some of the really big sets – sets bigger than the reals – then things start getting a bit crazy, and the set/proper class distinction starts to become very important.
Don’t forget — we can also get the reals by imposing an extra restriction on the surreals. 🙂
Unrelated to the topic.. but how do you get math characters to print out as characters. Is there a latex to unicode converter? Most of the time i see latex on websites it creates images.
“With the axiom of infinity, we get the natural numbers”.
Is that true? We need extensionality to prove that the set that exists here contains an infinite number of items (without it, {∅} and {∅,{∅}}} might be the same set).
Even then, this axiom does not state that the set it talks about contains no other items than ∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}, etc. That set might as well contain {∅,{∅,{∅}}}
First, we don’t actually need extensionality to prove that {∅} and {∅,{∅}}} are unequal. That follows immediately from the definition of equality, which is hard coded into the proof calculus. Extensionality is only needed for going the other direction: {∅} = {∅}
First, we’re assuming that we have the previous axioms as well. They build upon themselves. That’s why they’re given in a particular order.
So we have specification, which lets us cut out any excess elements. So we can assume that the set does contain nothing but the natural numbers.
In a post about ordinals, I screw up my ordinals . . .
Yes, as long as there is one set N fulfilling the properties in the axiom, there will be several.
The trick is to use as the set of natural numbers the intersection of all of them. This intersection then belongs to the same class (it is the smallest member), contains nothing extra, and fulfils induction.
Ryan Dickie: he says like ∅ to get ∅. HTML entities and Unicode contain a very large pile of mathematical and scientific characters.
Vorn
…waugh. Previewing unescapes things, and that’s… not what I wanted. He uses &∅ to get ∅.
Vorn
….oh, for standing in the rain. One more time. If it works, yay! If it doesn’t, well, go bug somebody else. ∅.
Vorn
One doesn’t need the axiom of infinity to represent arithmetic in terms of sets, I think. You only need it in order to have a *set* of all the integers. Without the axiom of infinity, the class of integers may be proper (not a set), but you can still prove plenty of theorems about the class of integers.
The integers can be represented in set theory by the finite Von Neumann ordinals. If the axiom of infinity is false, there are no other ordinals — no set of all the finite ordinals, in particular — but the finite ordinals can still represent the integers just fine, and will satisfy the Peano Axioms.
Antendren, your comment about them being in a particular order for a reason would be better supported if, in this post outlining the axioms, the axiom of specification came before the axiom of infinity 🙂
It doesn’t matter, because when you have the entire ZFC system, you can show the existence of a minimal such set using specification; but I think Mark was leaping forward a bit.
As for Ørjan’s view of just using intersection, I don’t see why that’s justified, per the axioms. Given one such N, you can construct other sets using the axioms of pairing and union, but I don’t see how you are guaranteed to be able to construct a set smaller than N which still fulfills the axiom’s defining property.
Well hmph. When I learned them, specification came first. Of course, we didn’t assume the existence of the empty set, and instead simply assumed the existence of a set, and then used specification to get the empty set. (Actually, our proof calculus had non-empty universes built into it, so we didn’t even need that.) So specification was necessary to even state the axiom of infinity.
First, you can use specification within N to take the intersection of the class of sets having the property, and that intersection is a set (the smallest one) with the property. There is of course no guarantee that it is different from the original N, since N is essentially arbitrary.
This smallest set (call it M) is the only one in the class satisfying the Peano axiom of induction. Because to satisfy induction means exactly that every subset of M with the property of the axiom of infinity is the whole of M.
Orjan’s set can come up, if we use an alternative Axiom, let’s call it the Other Axiom of Infinity:
∃M : ∅∈M ∧ (∀x:x∈M ⇒ (∅,{x})∈M).
That’s a different recursive definition, again consisting of a base case and an inductive case. The base tells us the initial value of M – the empty set. And the inductive case shows us how we can construct the further members of M.
Walk through a few steps of that:
1. By the base case ∅ ∈ M.
2. Since ∅∈M, then {∅,{∅}}∈M. It is also an element of the previously defined N, but that doesn’t definitionally matter.
3. Since {∅,{∅}}∈M, then {∅,{∅,{∅}}}∈M.
4. Since {∅,{∅,{∅}}}∈M. then
{∅,{∅,{∅,{∅}}}}∈M.
So we’re looking at another infinite sequence of values, which have a peculiar property. The N+1th value in the series consists of the set which has all previous values as elements, but differently nested with an extra null set element. That is, we define a countable infinity of ninary trees who always have the null set as a left-most leaf, and whose rightmost branches and subbranches include all trees that preceeded it.
If you look at this alternate series through the lens of the Peano axioms, you can see that it works for the integers. ∅ is the initial value, 0. For any number i, there’s a unique successor {∅,{i}}.
That is, the Other Axiom of Infinity gives us an infinite set M, different from N, and a different but equivalent construction of the integers.
0 is represented in M and N both by ∅.
1 is represented in M and N both by {∅,{∅}}.
2 is represented in M by {∅,{∅,{∅}}} and in N by {∅,{∅},{∅,{∅}}}.
In our new M, if an integer n is one of the trees of emptiness, the unique successor n+1 is represented by
{∅,{representation of n}}.
One can define both M and N, and then prove that they have the same cardinality, by putting the two different representations of the integers in correspondance, and showing that both satisfy the Peano axioms.
I think. This was off the top of my head. Am I right, wrong, close?
“God created the integers, all else is the work of Man,” to be sure, but God can create the same thing in different ways, even as his Angel named Conway showed.
Over at the (very advanced!) blog of Terrence Tao, there is a thread entitled
“Soft analysis, hard analysis, and the finite convergence principle” which mentions:
“In the field of analysis, it is common to make a distinction between ‘hard’, ‘quantitative’, or ‘finitary’ analysis on one hand, and ‘soft’, ‘qualitative’, or ‘infinitary’ analysis on the other….”
“At first glance, the two types of analysis look very different; they deal with different types of objects, ask different types of questions, and seem to use different techniques in their proofs. They even use different axioms of mathematics; the AXIOM OF INFINITY, the axiom of choice, and the Dedekind completeness axiom for the real numbers are often invoked in soft analysis, but rarely in hard analysis….”
There are people who are philosophically dismissive of many of Cantor’s arguments, including (incorrectly) the Diagonalization argument.
In particular, “in the philosophy of mathematics, constructivism asserts that it is necessary to find (or ‘construct’) a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its existence, according to constructivists.”
See the nice simple discussion of cardinality and Cantor’s diagonal argument in the context of constructivism at:
http://en.wikipedia.org/wiki/Constructive_mathematics