7
$\begingroup$

I know that the cardinality of the sets of real numbers $(0, 1)$ and $(1, \infty)$ are equal.

So what is the fallacy in this argument?

For every real on $(0, 1)$, we can add any integer $n$ to it and get a number on $(1, \infty)$, with the number from the first set as the fractional part of our new number. However, this can be applied to every real on $(0, 1)$, with every integer greater than one... seeming to suggest a larger cardinality of the second set than the first.

$\endgroup$
  • 9
    $\begingroup$ What do you conceive to be “more” reals? Typically, being uncertain there causes most confusion. $\endgroup$ – Luke Jun 19 '15 at 16:25
  • 2
    $\begingroup$ To me your question seems similar to Galileo's paradox. $\endgroup$ – Martin Sleziak Jun 19 '15 at 17:19
  • 5
    $\begingroup$ Don't we have like one of those every couple of weeks? $\endgroup$ – Asaf Karagila Jun 19 '15 at 17:45
  • 14
    $\begingroup$ @AtulGangwar try taking the reciprocal of every number in the first set. What do you get? Every number in the second set. $\endgroup$ – baum Jun 19 '15 at 17:53
  • 2
    $\begingroup$ @AtulGangwar Let for example $$f: (-0.5, 0.5) \to \mathbb{R} \\ f(x) = \begin{cases} 1/2x - 1 &\mbox{if } x \in (0, 0.5) \\ 1/2x + 1 &\mbox{if } x \in (-0.5, 0) \\ 0 &\mbox{if } x = 0\\\end{cases}\\$$ Then let $g: (0,1) \to (-0.5, 0.5), g(x) = x - 0.5$, and apply $f \circ g$. $\endgroup$ – G. Bach Jun 19 '15 at 22:00
35
$\begingroup$

Your argument shows that the cardinality of $(1,\infty)$ equals the cardinality of $(0,1)$ times the cardinality of the positive integers. In other words,

$$\mathfrak c=\mathfrak c\cdot\aleph_0$$

That is also known in other ways. The equation comes from the definition of the product of cardinal numbers.

The source of the "paradox" is that an infinite set can have the same cardinality as a proper subset. This cannot hold for finite sets but often does for infinite sets. The usual way to introduce that "paradox" is to show that the sets $\{1,2,3,\ldots\}$ and $\{0,1,2,3,\ldots\}$ have the same number of elements, though the second set has "one more" element than the first. For a dramatization of this, see Hilbert's Hotel.

$\endgroup$
  • 5
    $\begingroup$ You should not write the cardinality of the continuum as $\aleph$, even with any subscript. (Whether it even is an aleph depends on choice, and which aleph it is under choice depends on CH.) You should write $\mathfrak{c}$, $\beth_1$, $|\mathbb{R}|$, $|(0,1)|$, or something like this. $\endgroup$ – Ian Jun 19 '15 at 16:38
  • 2
    $\begingroup$ @Ian: Why not? The book Theory of Sets by E. Kamke, for example, uses $\aleph$ (as well as $\mathfrak c$) for the cardinal number of the real numbers. It would be wrong to place a subscript on it, due to the undecidability of the continuum hypothesis, but I have often seen the aleph without any subscript used in this way. $\endgroup$ – Rory Daulton Jun 19 '15 at 16:58
  • $\begingroup$ That's very strange to me, because in the usage I am familiar with, the alephs are well-ordered by definition. But then, if you assume choice from the start, I guess that's fair. (Again, in the usage I am familiar with, people like to isolate where choice is used in their arguments, rather than taking it as given from the start.) $\endgroup$ – Ian Jun 19 '15 at 17:00
  • $\begingroup$ @Ian: Kamke does assume the Axiom of Choice, so you are probably right. I'll edit my answer. Thanks for the tip. $\endgroup$ – Rory Daulton Jun 19 '15 at 17:02
  • $\begingroup$ @Ian, Rory: Let me clear up some confusion. $\aleph$ is used to denote the cardinality of the continuum, and this use dates over a century ago; however $\aleph_\alpha$ also denotes the well-ordered infinite cardinals (like $\aleph_0,\aleph_1$ and so on). And in addition it is used in several places for Hartogs and Lindenbaum numbers ($\aleph(X)$ and $\aleph^*(X)$ denote certain cardinals derived from $X$). Of course, these notations are different and have different contexts, but it's hard to mix them all. So nowadays we write $\frak c$ or $2^{\aleph_0}$ instead. [...] $\endgroup$ – Asaf Karagila Jun 20 '15 at 12:12
12
$\begingroup$

The problem is you do not have one mapping, you have a family of maps indexed by $\mathbb{N}$. In order to deduce something formally about cardinality, one must talk about a single map, not a bunch of maps.

Also, each of your maps embeds $(0,1)$ into $(1,\infty)$, which only shows that the cardinality of $(0,1)$ is less than or equal to the cardinality of $(1,\infty)$. It does not conclude anything about strict inequality of their cardinalities, for this would require a proof stating the non-existence of a bijection between your sets.

$\endgroup$
  • 1
    $\begingroup$ "for this would require a proof stating the non-existence of a bijection between your sets." Aha, that's the key part. $\endgroup$ – baum Jun 19 '15 at 16:24
  • 1
    $\begingroup$ Indeed, for you know that there is such a bijection! $\endgroup$ – Andrew Jun 19 '15 at 16:26
5
$\begingroup$

Your argument does not show a larger cardinality for $(1,\infty)$. You have shown that $\mathfrak {c=c}\cdot \aleph_0$, which is true

$\endgroup$
3
$\begingroup$

The essential mistake here is the assumption that if you can establish a One-To-Many mapping from A to B, then you have proven that Cardinality(A) < Cardinality(B), or just in general, that they are not equal. While this happens to be true for finite sets, this most definitely is not true for sets of transfinite cardinality.

Rather, you must rely on the definition of Equality for set-cardinality, which is that if you can establish any 1-to-1 mapping from A onto B then Cardinality(A) = Cardinality(B). Therefore, to establish non-equal cardinality, you must show that there is no 1-to-1 onto mapping possible between them (which is what the Diagonal Proof does for Natural numbers Vs. Real numbers).

$\endgroup$
  • 1
    $\begingroup$ Shouldn't it be one to one and onto for the cardinality to be same? $\endgroup$ – PleaseHelp Jun 19 '15 at 17:34
  • $\begingroup$ @AtulGangwar Yes, you are correct. It's been awhile for me, and Ive fallen into the habit of using CS terms. I will fix it, thanks. $\endgroup$ – RBarryYoung Jun 19 '15 at 17:36
1
$\begingroup$

This doesn't explicitly answer your question, but may contribute to your understanding.

What you have observed (essentially) is that there is a proper subset of the real numbers with the same cardinality of the whole set. Here "cardinality" means "matches using a one to one and onto function". The next step is to realize that's not a contradiction - it's the definition of what it means for a set to be infinite.

The usual first instance of this "contradiction" (or paradox) is that there are the same number of even integers as integers.

The other answers here are correct, but perhaps more technical than what you need.

$\endgroup$

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.