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!)
Joe does not have an ability to digest math. He requires a quote from the mathematical literature to be refuted.
This should help:
Also this:
Thanks for posting.
You have explained it well. However, I doubt that you will succeed in explaining it to JoeG.
As Joe is banned here, and therefore cannot respond, specific comments about Joe’s math should probably go to the sandbox.
But by all means let’s discuss sets 🙂
I myself would like to know how understanding sets relates to understanding nested hierarchies. It seems to me graph theory is a more intuitive place to start. The cool thing about living organisms is that they fall so beautifully into a tree, albeit one that is bushy near the root, and has the odd spindly lateral connection.
There is simply no point arguing with a moron like Gallieni. He’s not just stupid, he’s aggressively stupid. Not only does he not know, he doesn’t know that he doesn’t know.
They’re intimately related, because each node in an evolutionary tree can be expressed as the set of its subtrees.
For example, this tree can be compactly expressed as the following set:
{A,{G,{{B,C,D},{E,F}}}}
Well, he’s not exactly a threat to science. I do sometimes wonder whether he’s some kind of undercover COINTEL agent from the NCSE.
Ah thanks. I think my problem with sets is that I hate curly brackets. I spend my life squinting at brackets in MatLab trying to figure out whether they should be curly or round, and not being able to see which one I’ve typed. Gimme an adjacency matrix any day.
Brackets (round) are in fact used for computer-readable representations of trees. You may prefer an adjacency matrix but we in the phylogeny field would find it too big and cumbersome.
The standard computer-readable representation of this phylogeny would be:
(A,(G,((B,C,D),(E,F))));
The standard was based on one invented by Christopher Meacham, which in turn was based on the relationship Cayley noted in 1857 between trees and nested-parenthesis expressions.
The standard is described here.
Of course, the sets {1,2,3,4…} and {1.0…, 2.0…., 3.0…, 4.0…} have different cardinalities. The infinite set of integers has a different cardinality from the infinite set of real numbers.
Don’t even mention the reals. Joe is confused enough as it is.
JoeG has responded to my post.
As everyone predicted, he is still hopelessly confused.
This quote gives an idea where Joe is heading:
Translation: Math is hard and y’all are meanies!
But it does have practical applications. Remember that business of nested hierarchies?
olegt,
“Fringe math,” Joe? Here is what Stanford Encyclopedia of Philosophy makes of it:
Joe G,
It’s not an arbitrary mapping. It’s a one-to-one mapping. And the reason I chose a one-to-one mapping is that it shows exactly why your “count the leftovers” approach doesn’t work.
If you find a one-to-one mapping between two sets, you can be sure that they have the same cardinality whether they are finite or infinite.
To put it more precisely, the first set includes every integer greater than or equal to 0, while the second set includes every integer greater than or equal to 1. Your mistake is in trying to treat infinity like a normal number. In effect, you are arguing that (a countable) infinity plus one is greater than (a countable) infinity. It’s not, as any mathematician (and a whole lot of non-mathematicians) can tell you.
No, it’s quite objective, because two sets are defined as having the same cardinality if their elements can be placed in a one-to-one correspondence. The nice thing about this definition is that if works for both finite and infinite sets.
Your “count the leftovers” approach, by contrast, only works for finite sets, so mathematicians have rejected it. Mathematicians have thought about this much more carefully than you have or are able to, Joe.
Statements like that make you look like an ass, Joe.
Those two sentences contradict each other. Cantor proved, with his brilliant diagonal argument, that you can measure the cardinality of the integers (a “countable” infinity) against the cardinality of the reals (an “uncountable” infinity) and show that the latter is greater than the former.
That contradicts what you wrote earlier:
I see that you’ve gone back and edited your post to try to paper over your mistake:
Anyone who knows set theory knows that sets are defined as equal if their elements are the same. Equal sets always have the same cardinality, but sets with the same cardinality are not necessarily equal. Learn some set theory, Joe.
You are the one who is taking an approach that only works with finite sets (“counting the leftovers”) and trying to apply it to infinite sets.
Read the OP again. The one-to-one correspondence approach works with both finite and infinite sets. That’s why mathematicians use it instead of your flawed approach.
Yes, because every point in time is a finite point. At every finite point in time, the first runner has gone one mile farther than the second. Infinity is not a finite point, Joe, so the same reasoning does not apply to it.
No. By my logic, the first runner has run one more mile than the second at any finite point. Don’t confuse finite quantities with infinity.
Joe might also have difficulty with Robert Marks’s Powerpoint presentation on Implications of Cantorian Transfinite Set Theory on Creation. Marks seems to think that there are theological implications there (to be fair, so did Cantor). It is actually on Marks’s website in the Apologetics pages!
Since Joe and Marks are supposed to be on the same team, they might have to thrash this out.
Or some better spectacles
Many of us “out here” have very limited understanding of mathematics (and are somewhat envious of those with better)
The concepts of “zero” and “infinity” can be quite troublesome, particularly the latter
Then again, most of us don’t descend into potty-mouthed belligerence and insistence that ignorance beats knowledge when our lack of grasp is revealed.
Then again (again), we can always settle down with books and the internet to try to learn a bit. Or just keep quiet.
I think the sticking point seems to be the fact that the integers can be both set members and ‘placeholders’ as you go along counting the members. In {0,1,2,3 …}, every member is one adrift from its ordinal position; in {1,2,3,4 …} they are the same. But you could completely randomise the sets; there is nothing that says a set must be ordered.
Further, the behaviour of sets where the numbers are actually integers (codes for an actual number of things) is no different from one in which they are codes for something else. The numbers could equally be codes for an array of fruit held in a separate table.
0=banana,
1=apple,
2=guava,
3=grape,
4=cherry.
Set 1 is then {banana,apple,guava,grape…}
Set 2 is then {apple,guava,grape,cherry…}
Every one of those set members has a corresponding member at the same ordinal position – and so do the sets of integers, one with and one without zero (‘banana’). And this relationship doesn’t stop when you run out of ‘real’ fruit and run into the imaginary ones!
One could even remove the ‘infinite’ part by pictorially representing the fruit on a continuous reel, and placing the reels side by side. There is a finite set of different fruit, and a finite set of results – one for each time you put your dollar in and pull the handle – but an infinite set of possible results. You can spin for infinity and will always get a member of each set, the nth member since you started playing. There will be much repetition, but each member of the result set is different – the second banana is not the first banana.
I still find it non-intuitive but awesome that the set of the natural numbers has the same cardinality as the set of the rational numbers.
And even more mind-boggling that there is no set of intermediate cardinality between those sets and the set of the reals.
At least once I was sure I’d found one.
Then I got distracted by perpetual motion machines.
Certainly that. But I’m not sure they exist. I already have two pairs of varilux with different combinations of focal lengths.
Age sucks.
As I understand it, Cantor’s Continuum Hypothesis is the thesis that there is no set of intermediate cardinality, but the CH has not been proven or disproven. The other night I was talking about this with a professor whose done some work in set theory. He suggested that the problem with the CH is that we don’t really know how far up in the order of cardinalities the power-set operation takes us, so we can’t know that the set of reals (which has the cardinality of the power-set of the naturals) is the next higher cardinality after the naturals.
Use Emacs for your code and color each pair of matching braces differently!
Good thought. Although, to be honest, my real trouble with curly braces in MatLab is that I haven’t properly figured out when you need to use them. And if I’m cannibalising some code, I sometimes don’t notice which they are.
In fact, I tend to regard them as a kind of seasoning. If my code won’t run, I sprinkle on a few curly braces, and adjust to taste.
It’s my secret spice weasel. Works more often than you might think.
“If my code won’t run, I sprinkle on a few curly braces, and adjust to taste.”
You are making my inner OCD programmer weep.
It’s something to do with converting cell2char or char2cell (the second one I think).
Try it! It’s better than Jalapeno!
Kantian Naturalist,
That’s right. In fact, it has been proven that the continuum hypothesis can be neither proven nor disproven in the context of standard set theory!
From a Joe G comment underneath his latest bit of math denialism:
Too funny.
Imagine being Joe. He doesn’t know set theory, he doesn’t even know the terminology, he doesn’t know what Cantor meant, he has no idea what the diagonal argument is, but he’s thought about all of this for five minutes, so he must be right and every competent mathematician in the world must be wrong.
Joe, the integers {…,-2, -1, 0, 1, 2,…} can be placed into a one-to-one correspondence with “the set for only positive”, as you so elegantly describe it:
0 <–> 1
-1 <–> 2
1 <–> 3
-2 <–> 4
2 <–> 5
…and so on.
That means they have the same cardinality, “obvioulsy”.
Being a compassionate, giving kinda guy, I looked for a simple description of the properties of infinity and infinite sets to help him understand. This might be too advanced, but perhaps he’ll find that Math Is Fun!
Joe,
Invoking subsets doesn’t help, Joe. {1,2,3} is not a subset of {4,5,6}, and vice-versa. Yet they have the same cardinality, because they can be placed into a one-to-one correspondence. Mathematicians, being competent, do not use your bizarre “subset method” to assess cardinality. They also do not use your flawed “count the leftovers” method, because that doesn’t work with infinite sets. They look for one-to-one correspondences because that method actually works, for both finite and infinite sets.
Finite lengths are not infinities. Infinities are not finite. Your decidedly finite mind is failing to grasp this important distinction. Follow Patrick’s link.
Joe just seems to want to use a non-standard definition of cardinality.
I wonder if anyone else uses it?
He seems to concede that under the definition we are using, our conclusion is correct, but useless (“fringe”).
I’m not sure that his is any more useful, and seems redundant.
But does anyone have an actual use for Cantor? Is there a toaster out there that wouldn’t work without it?
An open message to JoeG:
We are all having a bit of fun, laughing at what you are posting. But let me try to get serious.
You want to look at cardinality in what seems to you to be a simple intuitive way. If that’s how you want to think about cardinality, fair enough. However, it is a central aspect of mathematics that we cannot allow ourselves to be influenced by simple intuition. For that often leads us astray. Instead, we must be sticklers for following definitions and rules of inference, even if they seem to contradict simple intuition.
There’s some background to this. People have obviously tried looking at cardinality in accordance with simple intuition. That works with finite sets. But, when tried with infinite sets, it quickly leads to logical contradiction. The way we actually handle cardinality might look unintuitive to you, but it avoids those logic contradictions.
It all boils down to infinity = infinity. Not infinity + 1, or infinity – 1.
Ah, Sal Cordova has managed to teach Joe, I think.
Joe’s methods don’t work, so nobody but Joe uses them. Joe’s subset method can’t even show that {knife, fork} and {cup, saucer} have the same cardinality. His “count the leftovers” method gives nonsensical answers when dealing with infinite sets, as the OP explains.
I don’t know of any technological applications for Cantor, but he is indispensable to mathematicians, since set theory is considered to be the foundation of all mathematics.
Joe’s take on infinities:
I would LOVE to see one bijection that maps rational numbers onto irrational ones. Go ahead, Joe, describe the mapping. Provide a recipe for us to figure out what 1 maps onto, what is the pre-image of the square root of three, and so on.
No, Joe is still as confused as ever:
Link
Maybe a deathbed re-Cantor.
olegt,
Hello oleg. I can name a mapping.
f : N –> R
f[n] = decode[n] (“9” is decoded as “,”)
f’ : R –> N
f'[r] = encode[r] (“,” is encoded as “9”)
Example:
12345945699 maps to 12345,4569
12345,4569 maps to 12345945699
Happy?
One can have MOAR fun with Joe’s “cardinality by lineup.”
Consider the set {0+x, 1+x, 2+x, 3+x,…}, where x is a real number. When x=0, we have {0,1,2,3,…}. When x=1, we have {1,2,3,4,…}. The great thing about parameter x is that it allows us to continuously interpolate between the two previously considered sets.
The size of a set is “obviously” an integer number and as such it cannot change continuously. Thus, as we increase x continuously from 0 to 1, the size of the set should remain unchanged. So as we arrive at x=1, the set size is still the same as it was when we departed from 0.
So not only do we have a bijective mapping between sets {0,1,2,3,…} and {1,2,3,4,…}, we have a continuous bijective mapping that provides a continuous interpolation between the two sets. Their sizes should certainly be the same.
olegt,
Interesting thought from Joe:
So I take it that when x is a small positive number, the size of the set X={x,1+x,2+x,3+x,…} is slightly smaller than the size of {0,1,2,3,…}. And when x is a small negative number, it is slightly larger. Is that so?
And what about the size of {0+ix, 1+ix, 2+ix, 3+ix,…} (where i is the imaginary unit). Is the size of that set larger or smaller than that of {0,1,2,3,…}? Or is it complex? 😮
Joe,
Why don’t you use your method (whatever it is) to compare the sizes of sets {0,1,2,3,…} and {0+x,1+x,2+x,3+x,…}, where x is a small number.
From what I have seen so far, I would guess that the answer is “I don’t know.”
COUNT THE LETTERS IN THE RECIEPE.
Joe writes:
No, Joe. We were telling you that {0,1,2,3,…} has the same cardinality as {1,2,3,4,…}, and we were telling you that a countable infinity plus one has the same cardinality as a “mere” countable infinity.
Read my OP. In it, I showed how your “count the leftovers” method leads to the following absurd and contradictory results:
1. Set 0 has a cardinality that is one greater than the cardinality of set 1.
2. Set 0 has a cardinality that is three greater than the cardinality of set 1.
3. Set 0 has a cardinality that is three less than the cardinality of set 1.
4. Set 0 has a cardinality that is infinitely less than the cardinality of set 1.
And if that isn’t obvious enough for you, consider this:
1. Take the set {0,1,2,3,…}.
2. Double each element. You still have the same “number” of elements, but each is twice as large as it was before, right?
3. The new set is {0,2,4,6,…}.
4. Now use your method to compare the original set to the new one:
0 lines up with 0
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 unmatched elements, so your method tells us that the original set is infinitely larger than the new set. But we already know that the sets have the same “number” of elements, because all we did was double each element of the original set. We didn’t add any elements. Your method contradicts itself.
Your method doesn’t work. The method of one-to-one correspondences does work. That is why no one but you uses your method, while mathematicians everywhere use the one-to-one correspondence method.
Is it finally sinking in, Joe? (Hope springs eternal.)
Better yet, Joe, why don’t you plot a graph of
as a function of x?
This ought to be good.
P.S. Joe, the vertical bars denote the cardinality of the enclosed set, as I’m sure you don’t know.
keiths,
Well, Joe can’t. For a small x (say, between 0 and 1), the sets {0,1,2,3,…} and {0+x,1+x,2+x,3+x,…} have no common members. None is a proper subset of the other. So his comparison method fails.
Thus Joe should properly answer “I don’t know.”
The standard set theory’s answer of course is the cardinalities are the same. Because there is an obvious bijection, f(n) = n+x.
Poor Joe. Sure he’s slow and obnoxious, but you can’t help feeling sorry for the guy.
Imagining waking up every morning and realizing that you are Joe G and that you’re going to be Joe G, every day, for the rest of your life. No wonder he’s angry all the time.
The meltdown continues:
keiths is full of shit and proud of it
Joe,
You mean, more than it already was?
I thought you might say that. That’s why I included this example at the end of my comment. Note that identical elements are lined up, just as your method requires, but it still gives the wrong answer:
Why would anyone want to use your broken “method”, Joe?
Joe,
Your method fails on olegt’s example for the very same reason, plus one more:
The correct method (the one that mathematicians use) can handle Oleg’s example regardless of the value of x. It even works if x is imaginary or complex.
Your method can’t handle Oleg’s example unless you coddle it by forcing x to be an integer.
Even worse, your method leads to another contradiction, just as it did on my example:
{0+x, 1+x, 2+x, 3+x,…} has the same “number” of elements regardless of the value of x. After all, you don’t add or remove elements by changing the value of x — you just change the size of each element.
If x=0, the set becomes {0,1,2,3,…}. If x=1, then it becomes {1,2,3,4,…}. But according to your “method”, the first set is larger than the second.
The first set can’t simultaneously be the same size as the second and also larger than the second. Your method fails yet again by leading to a contradiction.
No, your method works only if a) one set is a subset of the other, and either b) at least one of the sets is finite, or c) the user doesn’t mind getting the wrong answer again and again.
Meanwhile, the mathematicians’ method works on both finite and infinite sets, it gives the right answer, and it doesn’t require one set to be a subset of the other.
Who in their right mind would choose your method?