Cardinality of sets is a basic concept of set theory, but Georg Cantor extended the range of the idea when he applied it to infinite sets. Cardinality, simply explained, is just the count of elements in a set. The cardinality is expressed as a natural number, such as two, or five. It can also be zero for the empty set, even though zero is not usually considered a natural number. The integers make a wider set, consisting of all the natural numbers, and all the negative numbers. Natural numbers and integers are all “whole” numbers (numbers having no fractional part).
There is a cute little proof I worked up (thought of it myself, I did) to show that the cardinality of the natural numbers is exactly the same as the cardinality of the integers, and it goes like this:
Make a two-column list. In the left column, list the row number, starting at 1. In the right column, if n is odd, write (n+1)/2. If n is even, write -(n/2). That is, let the right column list the natural numbers and their corresponding negative integers, in alternating succession. In the left column, keep a tally of the entries.
| n | Value |
|---|---|
| 1 | 1 |
| 2 | -1 |
| 3 | 2 |
| 4 | -2 |
| 5 | 3 |
| 6 | -3 |
| … | … |
Clearly the list can be extended ad infinitum, and it establishes that the natural numbers are sufficient to count all the positive and negative whole numbers.
It’s also clear from the list above that we can set the natural numbers into a one-to-one correspondence with the odd numbers. But the odd numbers are a subset of the natural numbers. Therefore the set of naturals contains itself.
There is another interesting result which comes from Cantor himself: The cardinality of the set of natural numbers I, called Aleph-null, is a natural number, and it is the smallest infinite natural number. In other words, the set of integers has a cardinality, which is the number of integers in the set, and that number is Aleph-null. But that set has an infinite number of members. Therefore Aleph-null is a natural number of infinite magnitude.
We had a discussion about this in #philosophical several days ago, and it upset some people inordinately, to claim that some integers have an infinite magnitude. I don’t know why, unless it was some confusion of the set of natural numbers with things that physically exist.
May 21, 2008 at 9:52 am
Ah, this must be the post which is intended specifically to provoke me. And I must admit, your insinuation that I’m some kind of filthy empiricist did cause a little heat under the collar, but it’s all OK, I’ve calmed down now, without too much damage to the surrounding furniture.
The issue (for me, at least) is not the existence of infinite numbers in general, or Aleph-null in particular, but whether or not Aleph null is a natural number. I’m not sure why you think it is a natural number, or why you think Cantor ever claimed it was. It’s never been treated as a natural number in anything I’ve ever read, and I very much doubt Cantor ever made this claim.
The natural numbers are defined by the Peano axioms[1]. Apart from setting up some properties of the natural numbers, they basically state that the natural numbers are 0 or the successor of some natural number, i.e. 0 is a natural number, the successor of zero is a natural number, the successor of the successor of the successor of zero is a natural number, etc. Aleph-null can’t be a natural number as it isn’t the successor of a natural number. I suppose you could say it’s the successor of itself, but I think it’s difficult to maintain that this is the same successor relationship as exists amongst the naturals. In any case, there’s no way to get from 0 to Aleph-null by the successor relationship.
Another, perhaps clearer, way of showing that it is not amongst the naturals, is to use mathematical induction to show that all natural numbers are finite. Mathematical induction is a standard way of generalising about all natural numbers, and is defined by Peano axiom number 9:
For some property p, whenever the following two conditions hold:
1) if a natural number k has p, then its successor S(k) also has p
2) 0 has p
Then all natural numbers have p.
Considering then the finitude of natural numbers:
1) if some natural number k is finite, then it’s successor is also finite.
2) 0 is finite.
Therefore, all natural numbers are finite. As Aleph-null is infinite, it is not a natural number.
One’s options for disagreeing with this proof are not great. One could deny (1) – which would raise the question as to which finite number has an infinite number directly after it in the number sequence. One could deny (2), but it seems counter to the notion of infinity to suppose that 0 is infinite. Or the principle of mathematical induction could be denied, in which case as it is definitional of the natural numbers for modern mathematics, I can only suppose this move to be setting up a different meaning of ‘natural number’ to the customary one.
What Cantor did develop was a way of coping with infinite magnitudes, such as cardinalities of infinite sets, in a way analogous to how we deal with numbers. A ‘greater than’ ordering is defined, as are operations analogous to addition and subtraction, multiplication and exponentiation. On the basis of this Cantor claimed that Alpeh-null is *a number*. Introduction of new classes of numbers is a fairly familiar occurrence, and whether or not the cardinalities of infinite sets that Cantor demonstrated count as numbers depends on how far you’re willing to extent your notion of number.
[1]http://en.wikipedia.org/wiki/Peano_axioms)
May 21, 2008 at 12:27 pm
If some natural number k is less than 1000, then all natural numbers are less than 1000.
Nice proof!
But seriously, Cantor, if you want to go by him, called them transfinites to reflect that the numbers had qualities of both integers and infinities. And in any case, the reason Aleph-null is a natural number is because it’s a count of the elements in a set, and all counting numbers are naturals. That’s just what we mean by a natural number… you said it yourself. The naturals are defined by the successor function, and just as some naturals can be larger than 1000, so too, some naturals can be larger than any specified limit. This is important, because we have to be able to say the size of the set of integers.
Oh.. and the remarks about the empiricist in the group were not about you, they were about someone else. I wouldn’t accuse you of being an empiricist … unless you say something about not being able to “reach” an infinity by counting
May 22, 2008 at 3:56 am
Sure, if I was making a claim like that it would be dumb. But that’s not what I was doing. Don’t get confused by the name: mathematical induction is not the same thing at all as empirical induction. Trying to put your argument in the framework of mathematical induction doesn’t work (as it shouldn’t). Let’s look at the two conditions necessary for mathematical induction:
1) if some natural number k is less than 1000, then its successor S(k) is less than 1000
2) 0 is less than 1000
(2) is clearly true. However, (1) is clearly false – specifically, it’s not true of 999. 999 is less than a thousand, and its successor (1000) is not.
If you want to attack my (mathematical) inductive proof, I’ve already indicated the possible lines of criticism. Let me summarize them again:
(a) deny that 0 is finite.
(b) deny the inductive step, i.e: deny that
if k is finite, then S(k) is also finite.
(c) repudiate mathematical induction.
Hopefully you agree (a) is absurd, and you don’t seem to be taking that line anyway.
If you want to go with (b), then please either tell me which finite number on the natural number sequence is followed directly by an infinite number, or at least give an existence proof that there is one. This line seems pretty absurd to me, but perhaps you think it’s not absurd.
If you want to go with (c), then unfortunately as mathematical induction is definitive of the natural numbers, whatever you are doing, it isn’t showing anything about the natural numbers.
Confusing it with a fallacious argument which is at best only superficially similar does not suffice, I’m afraid.
BTW, as I said before, mathematical induction is a standard method of proof (perhaps it could be said to be *the* standard method of proof) for deriving properties of the natural numbers. If there’s something wrong with it, somehow generations of number theorists have failed to notice it and nearly two centuries of number theory would have to be scrapped.
It occurs to me from time to time that maybe you’re using ‘natural number’ to mean something different to the rest of the mathematical community? Your last comment seems to be using it as synonymous with ‘cardinal number’, in which case I agree with everything you say but strongly suggest using more standard terminology to avoid confusion.
May 22, 2008 at 9:23 am
A couple of other points:
*) I am saying that you can’t count to infinity. I have to, as I’m saying aleph-null is not a natural number. If you could count to it, it would be a natural number. I’m sorry if this means I’m an empiricist, but so be it.
*) It’s true that for any specified natural number, there are natural numbers greater than it. But that’s not the same thing as there being a natural number that’s greater than any specified natural number. In fact, these two statements are contradictory, which makes me wonder whether you’re not contradicting yourself when you say that aleph-null is a natural number. Are you saying that aleph-null is a natural number greater than any other natural number? Or are you claiming that there are natural numbers greater than aleph-null?
October 2, 2008 at 11:34 pm
[...] public links >> cardinality Cardinality of the Natural Numbers Saved by skarol on Wed 01-10-2008 Speculations on the Ontological and Spiritual Nature of any … [...]