9

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?
Improve this question
5
  • 1
    "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
    Commented Jan 16, 2019 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
    Commented Jan 16, 2019 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
    Commented Jan 17, 2019 at 22:31
  • 1
    "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
    Commented Jan 17, 2019 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
    Commented Jan 18, 2019 at 19:07

5 Answers 5

Reset to default
22

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."

Improve this answer
1
  • 2
    Wow thanks a lot! Been looking around for papers and books on this topic.
    – phst
    Commented Jan 16, 2019 at 14:11
4

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 consistent with the usual one, based on counting numbers.

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

and

See also Finitism.

Improve this answer
7
  • 1
    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
    Commented Jan 16, 2019 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
    Commented Jan 16, 2019 at 10:57
  • 1
    @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
    Commented Jan 16, 2019 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
    Commented Jan 16, 2019 at 14:54
  • 1
    @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
    Commented Jan 16, 2019 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”.

Improve this answer
1

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.

Improve this answer
0

I would like to supplement the currently accepted answer with a discussion on whether the concept of numerocity can be generalized further, beyond the subsets of integers, and even to the numerocity of continuum.

1. First of all, let us introduce a concept of numerocity of a set, starting from the subsets of integers. We introduce it as a sum of the indicator function of a subset over the whole set.

$N(S)=\sum_{k=-\infty}^\infty p_s(k)=p_s(0)+\sum_{k=1}^\infty p_s(k)+\sum_{k=1}^\infty p_s(-k)$

here, p_s is the indicator function of S. As we can see, in general, numerocity is a divergent series, characterized by the rate of growth and regularized value.

The concept of numerocity is, unlike cardinality, additive. Numerocity of union of two non-intersecting sets is the sum of the numerocities of each one (Euclid's principle as opposed to Cantor-Hume principle implemented in cardinality).

2. Being divergent series, the numerocities of subsets of integers using certain equivalence rules based on Laplace transform, can also be equated with a subset of germs at infinity in the Hardy field, and consequently, with divergent integrals. Under this equivalence, the order relations and regularized values are preserved.

For instance, the numerocity of positive integers {1,2,3,4,...} is equivalent to the germ at infinity of the function f(x)=x-1/2, and to a divergent integral enter image description here. We will denote the germ of the function f(x)=x at infinity as ω, it is equivalent to the half of the numerocity of integers, equal to the numerocity of the even or odd numbers, divergent integral enter image description here. Powers of ω (via germs) are given as enter image description here. We will use it more below.

3. Now, what if we want to generalize a numerocity to other countable sets, which are not necessarily subsets of integers? For instance, we need to count the numerocity of the roots of a given function. It turns out, that the following functional $\int_{(a,b)}\delta(f(x))|f'(x)|dx$ gives the number of roots of the function f(x) on the interval (a,b), so we take this integral (which also can be divergent if the numerocity of the roots is infinite) as the numerocity of the roots.

4. We will denote $\overline{\delta}(x)=\delta(f(x))|f'(x)|$ as the "squarable delta function" (which is a function that gives values from the space of germs or divergent integrals), and generalize it to other cases via the definition that $\int_{S}\overline{\delta}(f(x))dx$ gives the numerocity of roots of f(x) on S.

5. Unlike the conventional Delta distribution, squarable delta function satisfies the property $\overline{\delta}(a x)=\overline{\delta}(x)$, so it allows a piece-wise definition.

Via Fourier and Laplace transforms we can see that $\frac 1\pi\int_0^\infty dx=\overline{\delta}(0)$, it is also equal to ω/π, so we can define it piecewise

$\overline{\delta}(x)={\begin{cases}\frac 1\pi\int_0^\infty dx,&{\text{if }}x=0\ 0,&{\text{if }}x\ne 0.\end{cases}}$

6. Uing ω, we can express numerocities in integral form: $N(S)=\frac1\pi\int_\mathbb{R} p_s(x)\omega dx$.

7. James Propp proposed a good way to calculate the finite part of a numerocity of a countable subset of positive reals: $\operatorname{reg}N(S)=\lim_{q\to1^-}\sum_{k=1}^\infty q^{s_k}$ where s_k are the elements of S.

8. Below, we will understand $\int_a^b=\frac12 \int_{(a,b)}+\frac12\int_{[a,b]}$, in other words, the boundaries of an integral are half-included in the set over which we integrate.

9. Now, what is numerocity of an uncountable set, say an interval [0,1)?

We can express this numerocity using an integral:

$N([0,1))=\int_0^1 \overline{\delta}(0) dx=\frac1\pi\int_0^1 \omega dx$

But this quantity cannot be represented as analytic function or power series or germ of a real function at infinity because otherwise it could be equal to a numerocity of a countable set.

10. Thus, we introduce a new notation $\alpha=N([0,\pi))=\pi N([0,1))=\int_0^\pi \overline{\delta}(0)dx=\int_0^1 \omega dx$. For some reason, chosing the interval [0,π) instead of [0,1) simplifies further expressions.

11. We can now express the numerocity of reals: $N(\mathbb{R})=N(\mathbb Z)\cdot N([0,1))=\frac{2\omega\alpha}\pi=\frac1\pi\int_{-\infty}^\infty \omega dx$.

12. We have from Laplace transform:

$\int_{-1 }^{1 } \left( \begin{cases} f(\omega/\pi) & x=0 \ 0 & x\neq 0 \ \end{cases} \right) , dx=f'(0)+\frac1\pi\int_0^{\infty } f''(x) , dx=f'( \omega/\pi).$

13. This gives a more general rule of integration: $\int_a^b f(\omega ) g(x) , dx=\left(\alpha f'(\omega )+\operatorname{reg}f(\omega)\right) \int_a^b g(x) , dx \tag2$, particularly, $\int_0^{\infty } \ln \omega , dx= \alpha$.

14. One can generalize the numerocity of uncountable sets to other dimensions, but in all cases the Euler's characteristic of a set represents the regularized value (finite part) of the numerocity.

Thus, it seems it is absolutely possible to define and express the numerocities of uncountable sets, but it brings us beyond the realm of germs or divergent integrals of real functions.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .