How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Question

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem.

Here in the current problem I'm asking to disprove me(most probably I'm wrong).

As you can see in this problem as answered by Nicolas that if a map is from $A \to B$ and is bijective then the cardinality of $A$ and $B$ is same.

Logarithmic map is from $\mathbb{R^+} \to \mathbb{R}$ and it is a bijective map and therefore it implies that the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ is same.

My logic

We can rewrite $\mathbb{R}=\mathbb{R^-} \cup \{0\} \cup \mathbb{R^+}$

Now we can see that $\mathbb{R}$ has all the elements of $\mathbb{R^+}$ and over that it has {0} and elements of $\mathbb{R^-}$. Now using pigeonhole principle, if we pair each element of $\mathbb{R^+}$ to itself from $\mathbb{R^+} \to \mathbb{R}$ (eg. 5.124 is paired to 5.124 and so on) now when the pairing gets over then you have elements of $\mathbb{R^-}$ which have not been paired.

Now one can say that since they are infinite sets therefore we cannot talk about pairing as I did above. When we are dealing with the pigeonhole principle then at that time it is not necessary to know the exact numbers involved.

Now whatever method you use for pairing you will always end with some elements of $\mathbb{R}$ which have not been paired (acc to pigeonhole principle).

Most probably I'm wrong but how?.

Kindly make me understand that I'm wrong and the above used logic by me is inappropriate.

Answer 1

The definition of equicardinal is that there exists a bijection between the sets.

You are trying to define "not equicardinal" as "there exists a bijection between one set and a strict subset of another". This definition is not a good one, as all Dedekind infinite sets (such as $\mathbb{Z}, \mathbb{R}$) have the property that they are bijective with strict subsets of themselves; hence all Dedekind-infinite sets are "not equicardinal" with themselves by your definition.

In answer to OP's comment, the specific problem with the pigeonhole principle argument in the OP is that this proves that some attempts at a bijection fail. But as discussed above, and in the other solution, and in the comments, is that if ANY bijection exists, then the two sets are equicardinal.

Answer 2

As mentioned by others as well, the statement is that $A\sim B \Leftrightarrow \exists \phi:A\leftrightarrow B$ (i.e., $A$ and $B$ are of the same cardinality if there exists a bijection between $A$ and $B$)

That is not to say that all maps between them must be bijective, just that there must be at least one such map.

Consider $A=\mathbb{N}$ and $B=\mathbb{N}$. As they in fact represent the same set, they clearly have the same cardinality. Consider the map $\phi:~A\to B$ defined by $\phi(n) = n+1$. You have then that $Range(\phi)\subsetneq B$, but that does not contradict that $A$ and $B$ have the same cardinality. It just means that that choice of $\phi$ wasn't able to prove anything one way or the other.

Answer 3

The fault in the logic in your argument is that the Pigeonhole Principle only applies to finite numbers. From Wikipedia, the statement of the Pigeonhole Principle is:

"if $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item"

Your argument attempts to use the Pigeonhole Principle on an infinite amount of pigeons, even though it can only be used on finite amounts of pigeons. Note that here there is an infinite version of the Pigeonhole Principle but it's not very useful and doesn't apply to this situation.

Answer 4

This answer is specifically about the Pigeonhole Principle, unlike some other answers which have been about infinity.

A correct use of the Pigeonhole Principle requires the following:

1. I define what my pigeonholes and pigeons are. The cardinality of the pigeons must be strictly larger than the cardinality of the pigeonholes.
2. My nemesis assigns pigeons to pigeonholes in any way he likes.
   
3. Regardless of how he assigns pigeons, there must be at least two pigeons in some pigeonhole.
   
4. I use the fact that there are two (or more) pigeons in a pigeonhole to conclude something interesting about all assignments that my nemesis can make.

Note that it is necessary at the very beginning that there be more pigeons than pigeonholes. If I don't know how many pigeons and pigeonholes there are, then I cannot apply this principle.

Note also that I don't get to decide which pigeons go to which pigeonholes, I am trying to conclude something regardless of pigeonhole assignment.

For the specific example in the OP, there is an assignment that the nemesis can make ($x\to e^x$) that maps every $\mathbb{R}$ pigeon into an $\mathbb{R}^+$ pigeonhole without any two pigeons sharing a spot. I can't prevent him from doing this, because the whole idea of the PP is that I'm trying to prove something about all of his possible assignments.

Answer 5

I think the fundamental error here is a mistaken notion of what the Pigeonhole Principle is. Nowhere in the Wikipedia page cited in the question does it say there is any rule over which hole each pigeon may go into.

As is evident from some comments on other answers the argument in the question is based on the misconception that the Pigeonhole Principle does entail such a rule, namely, that the pigeon named $x$ must go in the hole named $x.$ Without such a rule, there is no reason to say that the Pigeonhole Principle necessarily sends the number $17$ (from $\mathbb R^+$) to the number $17$ (in $\mathbb R$).

In fact, the correctly understood Pigeonhole Principle contradicts the notion that the pigeons must be uniquely identified with the holes they occupy. When applied to a set of "pigeons" that is larger than some finite set of "holes," the principle explicitly says that you will put more than one pigeon in at least one of the holes. (The generalization explained later on the same page and here even talks about how many pigeons must go in some of the holes.) One of the pigeons must therefore go into a hole that is not uniquely identified with that pigeon.

As stated in other answers, it is sufficient to find one bijection from $A$ to $B$ that is "onto" (pairs every element of $B$ with some element of $A$) in order to show that $|A| = |B|.$ For finite sets $A$ and $B$ of equal cardinality, every bijection from $A$ to $B$ will be onto, but that is not the case for infinite sets.

For finite sets, the existence of a bijection from $A$ to a proper subset of $B$ shows that $|A| < |B|.$ If $A$ and $B$ are infinite sets, however, such a bijection shows only that $|A| \leq |B|.$

The bijection $x \to x$ from $\mathbb R^+$ to a proper subset of $\mathbb R$ therefore shows that $|\mathbb R^+|\leq|\mathbb R|.$ The bijection $x \to \pi + \arctan x,$ on the other hand, is a bijection from $\mathbb R$ to the interval $(0,2\pi),$ which is a proper subset of $\mathbb R^+.$ Hence we see that $|\mathbb R|\leq|\mathbb R^+|.$

Since $|\mathbb R^+|\leq|\mathbb R|$ and $|\mathbb R|\leq|\mathbb R^+|,$ it follows that $|\mathbb R^+|=|\mathbb R|.$

In other words, the bijection $x \to x$ from $\mathbb R^+$ to a proper subset of $\mathbb R$ does not imply in any way that $|\mathbb R^+|<|\mathbb R|$; instead, properly understood, that bijection can be used as part of a proof that $|\mathbb R^+|=|\mathbb R|.$

Answer 6

Two sets $A$ and $B$ are said to be equicardinal if there exist at least one bijective function from $A$ to $B$.

What you have shown is that a certain $f$ between $\mathbb{R}$ and $\mathbb{R}^+$ is not bijective. But that doesn't prove that each function between $\mathbb{R}$ and $\mathbb{R}^+$ isn't bijective.

Answer 7

The Cantor-Schroder-Bernstein theorem tells you that if there exists an injection from set A to set B and an injection from set B to set A, there exists a bijection between $A$ and $B$ and they have the same cardinality.

An injection $f:\mathbb{R}^+ \to \mathbb{R}$ is easy - just use the inclusion map ($f(x)=x$).

An injection $g:\mathbb{R} \to \mathbb{R}+$ is also easy - just use the exponential function ($g(x)=e^x$).

Thus, by Cantor-Schroder-Bernstein, $\mathbb{R}$ and $\mathbb{R}^+$ have the same cardinality.