At his blog, Joe G. has worked himself into a lather over the cardinality (or roughly speaking, the size) of infinite sets (h/t Neil Rickert):
Of Sets, Supersets and Subsets
Oleg the Asshole, Still Choking on Sets
Of Sets and EvoTARDS
Subsets and Supersets, Revisted [sic]
In particular, Joe is convinced that the sets {0,1,2,3,…} and {1,2,3,4,…} have different cardinalities:
…the first set has at least one element that the second set does not, ie they are not equal.
So if two sets are not equal, then they cannot have the same cardinality.
As a public service, let me see if I can explain Joe’s errors to him, step by step.
First of all, Joe, sets do not have to be equal in order to have the same cardinality, as Neil showed succinctly:
I give you two sets. The first is a knife and fork. The second is a cup and saucer. Those two sets are not equal. Yet both have cardinality two.
Two sets have the same cardinality if their elements can be placed into a one-to-one correspondence. That’s the only requirement. Here is a one-to-one correspondence (or “bijection”) for Neil’s sets:
knife <–> cup
fork <–> saucer
Note that there is nothing special about that one-to-one correspondence. This one works just as well:
fork <–> cup
knife <–> saucer
It makes no difference if the elements are numbers. The same rule applies: two sets have the same cardinality if their elements can be placed into a one-to-one correspondence. Consider the sets {0,1,2} and {4,5,6}. They can be placed into the following correspondence:
0 <–> 4
1 <–> 5
2 <–> 6
As before, there is nothing special about that correspondence. This one also works:
1 <–> 4
0 <–> 5
2 <–> 6
There are six distinct one-to-one correspondences for these sets, and any one of them, by itself, is enough to demonstrate that the sets have the same cardinality.
Now take the sets {1,2,3} and {2,4,6}. They can be placed into this one-to-one correspondence:
2 <–> 2
1 <–> 4
3 <–> 6
However, note that it’s not required that the 2 in the first set be mapped to the 2 in the second set. This one-to-one correspondence also works:
1 <–> 2
2 <–> 4
3 <–> 6
As in the previous example, there are six distinct one-to-one correspondences, and any one of them is sufficient to demonstrate that the cardinalities are the same.
Now consider the sets that are befuddling you: the infinite sets {0,1,2,3,…} and {1,2,3,4,…}. They can be placed into a one-to-one correspondence:
0 <–> 1
1 <–> 2
2 <–> 3
3 <–> 4
…and so on.
A one-to-one correspondence exists. Therefore the cardinalities are the same.
Here’s what I think is confusing you, Joe: there is a different mapping from the first set to the second that looks like this:
0 doesn’t map to anything
1 <–> 1
2 <–> 2
3 <–> 3
… and so on.
You observe that all of the elements of the second set are “used up”, while the first set still has an “unused” element — 0. You comment:
They both go to infinity but the first one starts one number before the second. That means that the first one will always have one element more than the second which means they are NOT the same size, by set standards.
But that’s silly, because you could just as easily choose a different mapping, such as:
0 doesn’t map to anything
1 doesn’t map to anything
2 doesn’t map to anything
3 <–> 1
4 <–> 2
5 <–> 3
… and so on.
Now there are three unused elements in the first set. We can also arrange for the “unused” elements to be in the second set:
nothing maps to 1
nothing maps to 2
nothing maps to 3
0 <–> 4
1 <–> 5
2 <–> 6
… and so on.
There are now three unused elements in the second set. By your logic, that would mean that the second set has a greater cardinality. It clearly doesn’t, so your logic is wrong.
You can even arrange for an infinite number of unused elements:
0 <–> 2
1 <–> 4
2 <–> 6
3 <–> 8
… and so on.
Now the odd integers are unused in the second set. Since there are now infinitely many “unused” elements in the second set, then by your logic the second set is infinitely larger than the first. Your logic is wrong, and the mathematicians are right.
Two sets have the same cardinality if they can be placed into a one-to-one correspondence. The sets {0,1,2,3,…} and {1,2,3,4,…} can be placed into such a correspondence, so they have the same cardinality.
END (Hi, KF!)
Is Joe more like a scorpion stinging itself, or a snake biting its own tail?
keiths,
Joe’s method obviously fails for non-integer x. Take x=0.01. He can’t compare {0,1,2,3,…} and {0.01,1.01,2.01,3.01,…} (or {−0.01,0.99,1.99,2.99,…}). The two sets have no common members.
Hey, Joe, which set is bigger? {0,1,2,3,…} or {0.01,1.01,2.01,3.01,…}? By how much?
How about {0,1,2,3,…} and {0+0.01i,1+0.01i,2+0.01i,3+0.01i,…}?
The answer is
– I don’ know
You see there’s nothing wrong with Joe’s method. It’s logical and doesn’t contradict anything.
Nothing wrong in the same sense as there is nothing wrong with declaring the number 1 to be red, the number 2 green, and the number 3 blue. There is nothing wrong with it, but there is nothing right, either.
I agree. It’s confusing and useless. However keiths is arguing that somehow Joe’s method gives a wrong answer. It’s like saying:
+(1,1) = 2
*(1,1) = 1
Therefore function * gives the wrong answer. 😯
olegt,
Joe concedes that his method of comparing sets does not apply to the two sets mentioned above.
Very well, Mr. Gallien. Since you have multiple tools at your disposal, why don’t you describe the tool with which you would compare the sizes of the sets {0,1,2,3,…} and {0+x,1+x,2+x,3+x,…}? Here x is a number greater than 0 but smaller than 1.
olegt,
Joe catalogs his tool chest:
So much for multiple tools. 🙂
Well, I am afraid this method (ask Joe and if that fails go back to Cantor) leads to some rather illogical situations. Let’s apply it and see that it leads to contradictions.
1. According to Joe, set {0,1,2,3,…} is bigger than set {1,2,3,…}.
2. Take the first of these and replace the number 1 with 1.01. The sets {0,1,2,3,…} and {0,1.01,2,3,…} cannot be compared by Joe’s method, we go back to Georg Cantor. Georg tells us that the two sets have the same cardinality. (Joe might agree with that since we merely replaced 1 with 1.01.)
3. Georg also tells us that sets {0,1.01,2,3,…} and {1,2,3,…} have the same cardinality.
4. We have thus demonstrated that {0,1,2,3,…} has the same size as {0,1.01,2,3,…}, which in turn has the same size as {1,2,3,…}. So the sizes of {0,1,2,3,…} and {1,2,3,…} are the same.
5. Points 1 and 4 are in contradiction.
Oh well, Joe is dithering.
Here is how the sets are defined precisely, Mr. Gallien. The first is a set of all non-negative integers {0,1,2,3,…}, in which 1 is replaced with 1.01. The second is a set of all positive integers {1,2,3,4,…}.
If that seems unclear let us know. 😉
Joe, quit playing dumb. You understand perfectly well what the two sets are.
But in case that you are really that dumb, here is an intro on describing sets. Once you have read that, here is a formal description of the two sets:
The second set is S2 = {n: n ∈ Z; and n>0}.
The first set is a union of two sets: S1 = {0,1.01} ∪ {n: n ∈ Z; and n>1}.
LOL
Or, more to the point, the first set can be written as {0,1,2,3,…} \ {1} ∪ {1.01}.
Joe decides that his methodology now applies to two sets none of which is a proper superset of the other.
Very well. Set {0,1+x,2,3,…} has greater Gallien cardinality than {1,2,3,4,…}.
How about comparing {x,1+x,2,3,4,…} and {1,2,3,4…}, Joe?
In other words, the first set is the set of non-negative integers {0,1,2,3,…} with the first two members increased by a small amount x. Formally, {0,1,2,3,…} \ {0,1} ∪ {x,1+x}.
Once you are done with that, you should be able to compare {x,1+x,2+x,3+x,…} with {1,2,3,4,…}.
You see where I am going, Joe? 😕
he must be a genius to enhance mathematics in an afternoon..
I’m not going to send any traffic to UD or Joe’s blog, but based on your summary what he seems to be saying is that 1 + \inf > \inf.
If he can’t understand that the mathematical concept of infinity has well-defined properties and cannot be treated as a finite number, he’s probably not going to understand where you’re going.
Patrick,
Joe certainly doesn’t “grok” infinity as a mathematical concept. Mind you, he’s by no means alone in that. It’s just that he can’t let himself know he doesn’t understand, let alone admit it to anyone else.
Joe’s main problem is that he bites more than he can chew.
When I used to read UD, I was often reminded of the Cliff Clavin character in Cheers. A number of the IDCists there have an opinion on everything and a much greater willingness to pontificate than to educate themselves.
A distinguishing feature, though, is that I might enjoy having a beer with Cliff.
Given he has no teeth, that makes any bite too much..
My first encounter with Cantor’s diagonal proof was in high school. This was a light-bulb moment. High school math tends to be either dull or gimmicky. But the diagonal proof stunned me by being both non-obvious and elegant. And I got me a free A out of the experience 🙂 (The teacher went over the proof once, and after a short break he asked for a volunteer to reproduce the proof.)
olegt wrote:
Yes. That’s why I said:
damitall,
More like a sponge boring itself to death.
Saya,
It does give wrong answers. Let me explain.
You are supposing that cardinality is a completely arbitrary concept, and that Joe’s definition isn’t right or wrong, it just happens to clash with the more useful one that mathematicians use. That’s not correct.
Cardinality isn’t arbitrary at all. It’s an extension of the concept of “number of elements”. By comparing the number of elements in two finite sets we can find out which set is larger. We’d like to be able to do this for infinite sets as well, but we can’t do this by comparing the “number” of elements in one (infinite) to the “number” of elements in the other (infinite).
Enter cardinality. By extending the concept of “number of elements”, cardinality gives us a way to establish the relative sizes of infinite sets. It also retains the property that given two sets A and B, A is either smaller, equal in size, or larger than set B.
Joe’s definition sacrifices this essential property, and so “Joe’s cardinality” is not an extension of “number of elements”. It gives us contradictory answers regarding the relative sizes of infinite sets. In other words, it gives wrong answers.
Awww. Joe tries to dress like a grown-up mathematician:
The Number Line Hypothesis with Respect to Set Theory
Unfortunately, the hat is hanging down over his eyes, the too-large glasses are askew and the overcoat is trailing behind him like a cape.
Is there a prize for the longest sustained fail in the the history of mathematics?
Without reading his post, I hypothesize that it gets at least five out of seven on Martin Gardner’s signs of a crank.
Dang. Now I’m feeling sorry for Joe again. He’s trying so hard, but failing so badly:
Not merely said, but proven.
Your method fails because the “count the leftovers” approach doesn’t work with infinite sets, as Oleg and I have already demonstrated.
No, because with infinite sets the answer will be “these sets occupy an infinite number of points along the number line”. To compare the cardinalities of two infinite sets you would then be comparing infinity to infinity. Which is larger?
No, Joe, and this is your biggest stumbling block. You are assuming that the infinite is just a really, really big version of the finite, and that “what happens in the finite can be extended into the infinite”. Not so. The infinite is qualitatively different from the finite.
For example, on any finite segment of the number line with length > 1 there is a largest integer. On an infinite “segment” of the number line that goes off to positive infinity, there is no largest integer.
And yet again, for two infinite “segments” the number of points are infinity and infinity, respectively. How are you going to determine which is larger?
So now you’re suggesting that sets expand or shrink if you shift them along the number line, even though you haven’t added or removed a single element?
Which of these sets has the greatest cardinality?
{-0.5, 0.5, 1.5}
{0, 1, 2}
{0.5, 1.5, 2.5}
{1, 2, 3}
Did shifting them along the number line make any difference? Did the shifting process add or remove any elements?
Christ, Joe.
Yes. It’s called the Failds Medal.
I know it’s fun to inhale at UD and exhale over here, but if you keep channeling the stupid like that, you’re going to fry your brain. Do we need to stage an intervention?
I wonder how long it will take Joe to discover and misuse bijections.
Now he’s gone and posted his “hypothesis” at UD, with this addendum:
He did qualify it as greater than or equal to…
Perhaps we need a comparison operator like >=<
That would give Joe some wiggle room.
(I can’t figure out how to post lt followed by gt.)
If JoeG would now throw in the Cantor-Schroeder-Bernstein theorem he might make some progress.
Joe:
No, a subset. If it had to be a proper subset then your method, as poor as it already is, couldn’t even establish that two identical sets have the same cardinality!
It seems I understand your “method” better than you do, Joe. It happens to work when the sets are identical.
Here’s why. Let’s compare the cardinalities of {1,2,3,4…} and {1,2,3,4,…} using “Joe’s cardinality”.
1 lines up with 1
2 lines up with 2
3 lines up with 3
…and so on.
There are no “leftovers”, so the cardinalities are the same.
Multiply each element of the second set by 2, however, and “Joe’s cardinality” fails miserably:
1 doesn’t line up with anything
2 lines up with 2
3 doesn’t line up with anything
4 lines up with 4
…and so on.
There are an infinite number of leftovers, so according to Joe’s method the cardinalities are different. Yet we did absolutely nothing to change the number of elements. We didn’t add any elements and we didn’t remove any elements. All we did was change the size of the existing elements.
“Joe’s method” gives the wrong answer.
Joe,
Cardinality between Open and Closed Sets, explained by “Dr. Math” from The Math Forum @ Drexel.
See also: Cardinal Number, Wolfram MathWorld; Set theory, Mathematical Atlas
Unlike Joe, Chance Ratcliff is trying to understand. Good for him.
Chance,
F(a) = a is not a bijection. Each element of A maps onto one element of B, but not vice-versa. The cardinality test only works with true bijections (aka one-to-one correspondences).
Yes, you can “count the leftovers” with finite sets and get the correct answer.
By the way, you don’t really want the complement of the intersection of sets A and B, since that would include elements that are outside of both A and B, such as -1. What you’re looking for is (A ∪ B) – (A ∩ B), which will give you {0}.
It’s true for both cases. F(a) = a is not a bijection, as explained above.
Here’s the weird thing about infinite sets, Chance. If you allow non-bijective mappings between your two sets A and B, you can end up with any number of “leftover” elements:
F(a) = a -1 leaves no “unused” elements
F(a) = a leaves {0}
F(a) = a + 1 leaves {0, 1}
F(a) = a + 2 leaves {0, 1, 2}
The problem is that none of those (except the first) is a bijection. If you stick to bijections, however, you’re safe. If you can find a bijection, then the sets have equal cardinality, whether they are finite or infinite.
Chance,
It’s not mere craftiness. Bijections are essential for the cardinality test. If you don’t have a bijection, you can’t do the test, as I explained in my previous comment.
That’s another weird thing about infinite sets. It is possible for an infinite set to have the same cardinality as its proper subset.
In fact, that’s what started this whole discussion. {0,1,2,3,…} has the same cardinality as {1,2,3,4,…}, despite the fact that the latter is a proper subset of the former.
Joe’s argument that {0,1,2,…} has greater cardinality than {1,2,…} ignores the fact that it is possible to create a simple bijection that maps them one-to-one:
f: Z -> Z, f(x) = x + 1
thereby showing that the set of all positive integers and the set of all non-negative integers have the same cardinality.
Your (very clear) exposition is equivalent to the bijection f: Z -> Z, f(x) = 2x, showing that the set of all positive, even integers has the same cardinality as the set of all positive integers.
Without understanding the basic properties of the mathematical concept of infinity, Joe is not going to understand either example.
(I know most people reading this understand these concepts quite well. I am not trying to teach grandpa to suck eggs.)
Patrick,
That’s a new one on me. 🙂
Where did you grow up?
In the backwoods of Maine. I’m mostly house trained now, though.
Craftiness? That’s an objection to an elegant mathematical technique?
Denyse O’Leary misrepresents E.O. Wilson as saying that “biology doesn’t need math”, and Robert Byers applauds:
The good news is that Joe finally has someone he can feel superior to.
That is pure gold.
More amusement from Byers:
“Mathematics is the language with which God wrote the universe.” — Galileo
I guess Robert has no interest in what God has to say.
I think we can guess that maths is something else Byers is no good at. You know, like science, logic or writing.
Forget the fact that they are integers, Joe, and that the sets overlap. Just look at them as ‘things’. Infinite sets of ‘things’. When you count the things, you are doing so in integers, which can go on to infinity (a number you can’t ‘look back from’, because you can never get there).
If your set also includes integers, this can throw you a curve ball. {1,2,3,4, …} looks like the optimal mapping – each set member also gives its ordinal position in the set. Sticking in zero, or anything else displacing the members from their ordinal positions, is adding members – but paradoxically it’s not making the set any bigger; it’s already infinitely big, and can’t get any bigger. Galileo spotted this – the set of integers is the same size as the set of squares, even though the latter is a proper subset of the former.
An infinite set of fleebs – {groof, klem, weef, argle …} is the same size as the overlapping set {klem, weef, argle …} and the nonoverlapping set {urgh, kijls, aroog, jurf …}. The reason is the ellipsis, not the things you’ve chosen to name up front. If ‘groof’ happened to be Venusian for 0, ‘klem’ 1 etc, the sets would be the same size as if they represented an infinity of different kinds of vegetable.
Joe:
It’s because your methodology remains a bit of a mystery, Joe. It continues to evolve in time.
You initially claimed that your methodology only applies when one set is a proper subset of another.
Then you decided that you can allow some non-overlapping elements.
And now you are talking about entirely non-overlapping sets like {0,1,2,3,…} and {0+x,1+x,2+x,3+x,…}.
Maybe you should pause for a moment and formulate your comparison method carefully. 😉
Am I missing some subtlety in Joe’s argument or is he really claiming that \inf + 1 > \inf?
Don’t worry, Joe will be along shortly with a different and better infinity. He has to, else his revolution in Set Theory will never leave the starting gate.
Or that the cardinality of a set varies according to its intersects with other sets in the vicinity?
Redefining well-established mathematical concepts? Now that’s just crazy talk. Next you’ll be trying to convince me that someone would be silly enough to try to redefine what an objective nested hierarchy is, or that religiously-based speculations without evidence or testable predictions should be considered scientific.