4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What statement of the Pigeonhole Principle do you have in mind? $\endgroup$ – Travis Dec 16 '14 at 22:34
  • 2
    $\begingroup$ Just because two sets have the same cardinality does not mean every map between them will be a bijection. $\endgroup$ – Unit Dec 16 '14 at 22:38
  • $\begingroup$ You've correctly proven that there is a map from ${\mathbb R}^+$ to ${\mathbb R}$ that is not a bijection. Your mistake is thinking that this implies anything about the cardinalities of ${\mathbb R}^+$ and {\mathbb R}$. $\endgroup$ – WillO Dec 20 '14 at 15:03
  • $\begingroup$ @WillO no. Again, by finding a map which is not a bijection is not the same as finding out there there are no maps which are bijections. If you can prove there are no maps that are bijections then you know they are different cardinalities. If you find at least one map which is a bijection then you prove they are the same cardinality. $\endgroup$ – JMoravitz Dec 20 '14 at 16:35
  • $\begingroup$ @JMoravitz: My question was aimed at the OP, not at people who already understand this stuff. $\endgroup$ – WillO Dec 20 '14 at 19:18
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sir kindly see the comment which I added for JMoravitz in the above answer. $\endgroup$ – Singh Dec 17 '14 at 4:28
  • $\begingroup$ Sir I'm not saying that the if ANY bijection exists, then the two sets are equicardinal approach is wrong. I'm asking where I'm with my logics. $\endgroup$ – Singh Dec 17 '14 at 5:39
  • $\begingroup$ Your post, despite containing the words "Pigeonhole Principle", is not a correct application of this principle. What are the pigeonholes, and what are the pigeons? All the responders are addressing the question hiding behind the incorrect use of PP. $\endgroup$ – vadim123 Dec 17 '14 at 15:01
  • $\begingroup$ Sir as I said before I am wrong(but I don't know where I'm wrong). Example, let you and me be the pigeons and when we are entering the holes we have to be careful that I enter the hole with name Singh and you will only enter the hole with name vadim123. Now let $\mathbb{R}$ be the pigeons and $\mathbb{R^+}$ be the holes. Now according to the condition every pigeon has to enter a hole with its own name on it. Then every +ve member of R+ will have a hole but -ve numbers and zero do not have their holes and so we can say that the number of pigeons(R) is more then the number of holes(R+). $\endgroup$ – Singh Dec 18 '14 at 7:03
  • $\begingroup$ @Singh, I have never seen pigeons required to go in holes with their own names. There's no need for that restriction. Do you not agree that $x \to x+1$ is a bijection from $\mathbb Z$ to itself? Are you familiar with the Hilbert Hotel? $\endgroup$ – David K Dec 18 '14 at 9:06
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sir I understand this way as I have already given the example of logarithmic map. Whatever you said I understand that and that is all right. But my question is that, that where I'm making the mistake when thinking of pigeonhole principle and using it as I did in my problem. Remember I also stated the $\mathbb{R}=\mathbb{R^-} \cup {0} \cup \mathbb{R^+}$ $\endgroup$ – Singh Dec 17 '14 at 4:03
  • 3
    $\begingroup$ Short answer is that pigeon hole principle doesn't apply in infinite settings. Look up "hilbert's hotel". Longer answer is that pigeonhole principle works if cardinality of the sets in question are actually different and therefore can't be used to prove if cardinality is different as it would be a circular argument. $\endgroup$ – JMoravitz Dec 17 '14 at 5:42
  • $\begingroup$ Sir are you asking me to look this? I will see this in a while and what you have said I already have mentioned(something similar) in my question. $\endgroup$ – Singh Dec 17 '14 at 5:48
  • $\begingroup$ Yes. Take note that pigeonhole principle states that if we have more pigeons than holes that there must be a hole with at least two pigeons in it. For finite quantities there is little confusion in that statement, but for infinite quantities "more" refers to being of a larger cardinality. $\endgroup$ – JMoravitz Dec 17 '14 at 5:53
  • 1
    $\begingroup$ try reading math.stackexchange.com/questions/551123/… In this case of having "more money" we are referring to metric amounts, size of how much money. It is an example of why $a<b \Rightarrow a+c \leqq b+c$ if we are not sure that $c$ is a finite number. Only if we know $c$ is finite can we say $a+c\lneq b+c$ $\endgroup$ – JMoravitz Dec 17 '14 at 15:39
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It was conclusively proved that pigeons whose cardinality is larger than $\aleph_0$ cannot fly! :-) $\endgroup$ – Asaf Karagila Dec 20 '14 at 14:48
  • $\begingroup$ @AsafKaragila, I've got $\aleph_0$ problems but the pigeonhole principle ain't one. $\endgroup$ – vadim123 Dec 20 '14 at 17:18
  • $\begingroup$ I'm sure we can force that on you! ;-) $\endgroup$ – Asaf Karagila Dec 20 '14 at 17:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sir please go through the last two comments on this page. $\endgroup$ – Singh Dec 18 '14 at 9:41
  • $\begingroup$ Are you referring to your "$c=c$" argument? If so, regular addition is only defined for finite numbers. We can't add infinite amounts of things. So your inequalities seem to hold, but it doesn't make sense to speak of infinity plus a finite number. Regardless of this, the Pigeonhole Principle, by its own definition, only applies to finite numbers of objects, therefore it can't be applied to $\mathbb{R}$ $\endgroup$ – Michael Blakeman Dec 18 '14 at 9:55
  • $\begingroup$ Yes sir I was talking about that argument. In that argument is that the first statement not true? It is a situation in which something is greater then another and then too they are equal! I'm working in order to understand why pigeonhole principle can't work here. $\endgroup$ – Singh Dec 18 '14 at 12:42
  • 2
    $\begingroup$ If you insist on doing addition with infinite cardinals, then the way it works is that if A is an infinite cardinal, and b is a finite cardinal, then A + b = A. Yes, that means A = A+1 = A+2 =... but there is no contradiction since you can not "subtract A and obtain 0 = 1 = 2" as there are not additive inverses (i.e. negative infinite cardinals) in this setting. $\endgroup$ – Ned Dec 18 '14 at 14:42
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.