3

Cantor defined an infinite set as a set whose subset can be placed in a one-to-one correspondence with its subset. That is, take the set of all natural numbers: {0, 1, 2, 3, 4,...}. From that set, you can form a subset of all even numbers: {0, 2, 4, 6,...}. There is a one-to-one correspondence between both these sets. After all, you can multiply each member in the set of all natural numbers by 2, and you’ll get the set of all even numbers. Because of this one-to-one correspondence, the two sets have the same cardinality, despite the set of even numbers being a subset of the set of natural numbers. This is counter-intuitive to me. How can a subset of a set be as big as the set itself? To make the intuition more concrete, consider the set of multiples of 1,000,000: {0, 1,000,000, 2,000,000,...}. There is a one-to-one correspondence between this set and the set of all natural numbers. So they have the same cardinality. This is really counter-intuitive.

From as far as I can tell, there are basically two axioms at play here:

A1: If all members of set A can be placed in a one-to-one correspondence with all the members of set B, then both sets have the same cardinality.

A2: If set A is a proper subset of set B, then A has a smaller cardinality than set B.

How Cantor defined infinite sets is that he accepted A1 and rejected A2. That is counter-intuitive to me. But mathematicians might say that my intuition is just wrong. So my question is whether we can define infinite sets in another way, i.e. accept A2 but reject A1. That is, the set of even numbers is smaller than the set of all natural numbers, even though both sets have a one-to-one correspondence. If you think this is counter-intuitive because sets with one-to-one correspondence with each other should have the same cardinality, and thus think this is wrong, why can’t I say the same when Cantor accepted A1 and rejected A2? Either way, there is something counter-intuitive and paradoxical.

So, my questions are:

  1. Can we accept A2 and reject A1 for the definition of an infinite set?
  2. What arguments, if any, are given for accepting A1 and rejecting A2?
  • "Cantor defined an infinite set as a set whose subset can be placed in a one-to-one correspondence with its subset." You're gonna want to rework this definition. What I think you mean to say is "Cantor defined an infinite set as a set which is able to be put into one-to-one correspondence with one of its own proper subsets." What you said makes it sound like each set only has one subset ("its subset") and that that set is bijectable to itself, the first being false and the second being trivial. That's not what Cantor argued. – Not_Here Jan 16 at 4:12
  • Whatever does not give information about real world is counter-intuitive. Infinite sets do not give that information. Anything we see in the world is finite. – rus9384 Jan 16 at 9:28
  • "Cantor defined an infinite set as a set whose subset can be placed in a one-to-one correspondence with its subset." -- Actually Dedekind did that. Credit where due. en.wikipedia.org/wiki/Dedekind-infinite_set Assuming that's what you meant to write. – user4894 Jan 17 at 22:31
  • "How can a subset of a set be as big as the set itself?" It's not. It has the same cardinality. The phrase "as big as" is a figure of speech. As is "smaller than" or "larger than" when applied to infinite sets. I think this is a common point of confusion, to try to apply the everyday idea of size to infinite sets. If two sets are equinumerous, we SAY they are the "same size" but that is only a figure of speech. – user4894 Jan 17 at 22:34
  • It might help to first define what a finite set is without reference to the infinite set of natural numbers. Then an infinite set is just one that is not finite. Then you will see why the standard definition of an infinite set (from Dedekind) makes sense. See my blog posting, "Infinity: The Story So Far" at dcproof.com/Infinity.html where I develop this idea using intuitive and formal methods. – Dan Christensen Jan 18 at 19:07
10

The answer is affirmative. The only hard fact is that the Hume's principle (bijective sets have equal sizes) and the part-whole axiom of Euclid (the whole is greater than its part) are incompatible for infinite sets. It is not that your intuition is "wrong", but rather that any extension of "size" to infinite sets will be paradoxical, it has to discard one or the other. One can select one group of intuitions to keep, or one can select another. Cantor made one choice, and it was adopted in modern mathematics (for its technical benefits, among other things), but an alternative group of intuitions can be coherently taken instead. We just can not keep it all. If there is anything wrong here it is expecting that our intuitive concept of size, developed from experience with finite sets, would carry over in full beyond the context in which it was developed.

This psychological obstacle is reflected in the long historical struggles with the concept of size for infinite sets, described e.g. in Mancosu's Measuring the Size of Infinite Collections of Natural Numbers numbers: Was Cantor's Theory of Infinite Number Inevitable? It is interesting that Bolzano, Cantor's precursor on set theory, rejected the Hume's principle, exactly because it conflicted with the part-whole axiom. Gödel , on the other hand, gave an influential argument that Cantor's choice in favor of the Hume's principle was "inevitable". Nonetheless, a coherent alternative, called numerosity, that adopts the part-whole axiom instead, was introduced by Benci in 1995, and developed by him, Di Nasso and Forti in 2000-s, see their Aristotelian Notion of Size. However, since the Hume's principle is now rejected we can not apply it to sets proper, they need to have additional counting structure, in this case they have to be labeled sets.

The idea is to split a set into boxes, each one containing only finitely many elements (with the same label), and count them by counting the content of the boxes, in sequence. The numerosity is built from the sequence whose n-th term counts the number of elements with labels up to n, i.e. in the first n boxes. This only works for countable sets, but there is an extension to arbitrary sets using ordinals. All integers (labeled by themselves) produce 1,2,3,4,5,6..., even integers (also labeled by themselves) produce 1,1,2,2,3,3..., which is strictly smaller starting from the second term, so their numerosity is strictly smaller.

The general construction is technical and is similar to the ultrapower construction of the hyperreal numbers - one takes numerosities to be equivalence classes of nondecreasing integer sequences that are equivalent modulo a Ramsey ultrafilter (whatever this means). But the numerosities do satisfy the part-whole axiom, and have nice algebraic properties. One can define arithmetic on them, and they add when disjoint labeled sets are put together. The trade-off is that there are plenty of bijective sets with different numerosities.

Here is Mancosu's commentary on Gödel's argument and how it fails for numerosities:

"Gödel’s reflection aims at showing that in generalizing the notion of number from the finite to the infinite one inevitable ends up with the Cantorian notion of cardinal number. The key step in the argument is the premise and the theory of numerosities can help us see that the premise already contains in itself the Cantorian solution. In fact, the premise takes as evident the request that “the number of objects belonging to some class does not change if, leaving the objects the same, one changes in any way whatsoever their properties or mutual relations (e.g., their colors or their distribution in space).” While the premise constitutes no problem when dealing with finite sets, one might question its acceptability in the realm of the infinite. Indeed, in the theory of numerosities we cannot grant the premise when it comes to infinite sets.

For, while it is possible to abstract from the nature of the objects themselves there is one type of relation that affects the counting, namely the way in which the elements are grouped. Such grouping makes no difference in the realm of finite sets of integers. But when we move to infinite sets a rearrangement of the grouping will in general affect the approximating functions and thus the numerosity of the set. Someone committed to the counting embodied in the theory of numerosities might thus reasonably resist accepting the premise on which Godel bases his argument and thus also resist the claim that the generalization of number from the finite to the infinite must perforce end up with the notion of cardinal number. In short, having a different way of counting infinite sets shows that while Gödel gives voice to one plausible intuition about how to generalize “number” to infinite sets there are coherent alternatives."

  • Wow thanks a lot! Been looking around for papers and books on this topic. – jshthng Jan 16 at 14:11
2

Axiom

A2: If set A is a proper subset of set B, then A has a smaller cardinality than set B

is intuitive.

Correct; since ancient time [see Euclid's Elements] it was assumed :

Common notion 5.

The whole is greater than the part.

But is also quite ancient the discovery that this principle may lead to problems in some cases; see the so-called Galileo's paradox.

Thus, Cantor's intuition to define a new way of "counting" the elements of a collection : the notion of one-to-one correspondence is prior to (and independent of) the concept of counting number.

The benefit of this approach was its applicability to every type of collections: finite and infinite.

In the case of finite collection*, the new approach was cocnsistent with the usual one, based on counting numbers.


Having said that, tehre are some alternative approaches to mathematical infinity; see e.g.

and

See also Finitism.

  • Why would Galileo's paradox be a paradox though? Inifinity is inapproachable and set of squares will be much smaller than set of natural numbers if their largest element is the same (and greater than 1). – rus9384 Jan 16 at 9:31
  • @rus9384 Your comment doesn't make sense. It's like saying that an infinite series doesn't converge because if you take an initial finite segment and sum it you don't get the value the entire infinite series converges to. If you're a finitist then okay, but if you agree that infinity makes sense then what you're saying doesn't make any sense. If you're a finitist but you don't announce that when you argue with someone who does accept infinity, you come off as if you're arguing in bad faith and not being up front about what is actually going on. – Not_Here Jan 16 at 10:57
  • @Not_Here Well, I don't know why would two infinities be equal in set theory if they are not in analysis. Seems inconsistent. – rus9384 Jan 16 at 14:23
  • @rus9384 Nobody said that they're "equal", is that really your best attempt? Just because two objects share one property (in this case having the same cardinality) that makes them equal simpliciter? Nobody with even a cursory understanding of mathematics thinks that. – Not_Here Jan 16 at 14:54
  • @Not_Here So, you will argue that according to modern math they are not both aleph_0? That aleph_0 = aleph_0 is trivial. But my question is where does the one-to-one correspondence implies the same number of elements. In your intuition? Maybe. But not in mine. – rus9384 Jan 16 at 21:21
1

This is just a question of disambiguating “bigger” (or “smaller” or “size”).

There are two kinds of objects involved here:

  • Sets of Xs (where X is some kind of objects). Such a set is a selection of Xs. You can picture it as a bag of points where each point has a different label (telling us which X it represents).

  • Cardinal numbers. They are “shapes” of sets. You can picture a cardinal number as a bag of points without labels.

There is a mapping from sets of Xs to cardinal numbers, associating to each such set its cardinality. In the bag metaphor, it amounts to removing the labels, i.e. forgetting which Xs are members of the set. You’re left with the set’s “shape” (or cardinal number). This removing the labels is the abstraction of the nature of the elements in Cantor’s famous quote:

We will call by the name “power” or “cardinal number” of M the general concept which, by means of our active faculty of thought, arises from the aggregate M when we make abstraction of the nature of its various elements m and of the order in which they are given. Cantor starts with sets enumerated in some order, unlike us, which is why we don’t need to forget also the order in which they are given.

Now, there is a standard order relation on sets of Xs, namely inclusion: a set of Xs is smaller than or equal to another one if all Xs in the first are also in the second. They are the same if they have exactly the same elements.

There is also a standard order relation on cardinal numbers. Here, since the points don’t have any labels, you can’t ask for two cardinal numbers to have the same elements, they don’t have any. You can just see if you can map points of the first injectively into points of the second, in which case the first is smaller than or equal to the second. They are the same if you can map them bijectively. In practice, cardinal numbers are usually presented to us via some concrete presentation as some set of Xs, so that we define these injections or bijections in terms of Xs. (N.B. any spatial arrangement that may come to your mind is just extra baggage due to the bag metaphor, the points of a cardinal number have no spatial arrangement, they are not spatial at all.)

This gives rise to two different notions of “bigger” for sets of Xs:

  1. A is bigger₁ than B if it’s bigger for the inclusion order of sets. For instance, the set of all natural numbers is bigger₁ than the set of even numbers. The only set of natural numbers which is the same size₁ as that of even numbers is itself. N.B. If you want to reify size₁, you can just take the size₁ of A to be A itself (that would be the alternative to cardinality of the question in your title).

  2. A is bigger₂ than B if A’s cardinality is bigger than B’s, for the standard order on cardinal numbers. For instance, the set of all natural numbers is not bigger₂ than the set of even numbers, they are the same size₂, as witnessed by the “divide by 2” bijection between them, which makes the corresponding cardinal numbers equal.

There is nothing paradoxical if we don’t forget the indices (or use different words). Both notions of size coexist peacefully in mathematics. We just need to specify what we mean by “bigger” (mathematicians would usually be explicit, using, if the context isn’t enough, “is included in” or “has a greater cardinality than”).

The answers to your questions 1 and 2 would be, as written, “no” and “none”, but that’s just nitpicking: if you reformulate your A1 by substituting “size” for “cardinality” and your question 1 by substituting “for the definition of size of a set” for “for the definition of an infinite set”, then the answers are “yes” (just use size₁ instead of size₂) and “it depends on what notion of size you use”.

0

This is counter-intuitive to me. How can a subset be as large as the set itself?

This is because we are using two different notions of measure here and they are not complete commensurate.

Here's a physical example: take a rubber band and then pull it. It's now larger than it was before. Do you see this as being counter-intuitive? Of course not, it's something that's both readily visible and understandable from your own experience.

The language of sets is useful. And whilst Cantorian cardinality is a marvel, the main problem I have with it is that it has little use outside of its own domain. Compare this with the calculus which is still breaking new ground and proving its usefulness.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.