2
$\begingroup$

Cantor had shown that for any two subsets containing all numbers in $\mathbb{R}$ on any two intervals, they must have equal cardinalities because one can find a bijective function.

The famous example is that the cardinality on the set of Reals in $[0, 1]$ is equal to the cardinality on the set of Reals on $[0, 2]$.

The bijection for the two sets is to simply multiply any $x$ in the first set by 2, and you have found a bijection. Define $\mathbb{A} = \{x\in\mathbb{R}: 0 \leq x \leq 1\}$ and define $\mathbb{B} = \{x \in \mathbb{R}: 0 \leq x \leq 2\}$, then our function is simply $f: x \mapsto 2x$.

What bugs me about this is that you can also find a mapping such that it is injective, but not surjective.

We simply define our function as $f: x \mapsto x$. This function maps every element $\mathbb{A}$ to an element in $\mathbb{B}$, but there are still elements left over in $\mathbb{B}$ that don't have an element in $\mathbb{A}$ mapping to it.

For finite sets, this would usually imply that $|\mathbb{B}| > |\mathbb{A}|$, ($\mathbb{B}$ is strictly larger than $\mathbb{A}$) but this doesn't seem to be the case for infinite sets.

The argument for finite sets can be easily explained as a way to count without numbers. For example, if you and I have a bunch of rocks, and you want to see who has more, you can line them up, and see who has left over at the end. In the analogy, if I all of my rocks have a unique rock from your set next to it, the mapping is injective. If all of your rocks have a unique rock from my set of rocks next to it, the function is surjective. If both are true, the function is bijective. If all of mine have a unique rock from your set next to it, but I have some left over, I have more. If all of your rocks have a unique rock from my set next to it, but you have left over, you have more. If there are none left over on either side, they are equal. But this no longer seems to work for infinite sets. Why?

$\endgroup$
  • $\begingroup$ This is why you can always get a room at the Hilbert Hotel. It's the hallmark of infinite sets. Given that the reals are infinite, the answer to the question of your headline, "What does a one-to-one mapping say about the cardinality of the reals if it isn't onto?" is simply, "It says that the cardinality of the reals is at least as large as itself". $\endgroup$ – BrianO Dec 24 '15 at 6:15
1
$\begingroup$

Definition

  1. We say $|A|=|B|$ if there exists a bijective function from $A$ to $B$.

  2. We say $|A|\leq|B|$ if there exists an injective function from $A$ to $B$.

  3. We say $|A|\geq |B|$ if there exists a surjective function from $A$ to $B$.

Added:

  1. We say $|A|<|B|$ if an injective function $f:A\to B$ exists a surjective function $g:A\to B$ doesn't exist.

It is pretty clear from here that if we have $|A|=|B|$ we also have $|A|\leq |B|$ just like with real numbers, so there are no contradictions.

Remark

If we define $f:\Bbb B\to \Bbb A: x\mapsto \frac x 2$ we have an injective mapping, this tells us that $|B|\leq |A|$.

Remark 2

With real numbers we have the 'law' which states

$$a\leq b \wedge b\leq a\rightarrow a=b$$

When taking about cardinality, we have the a theorem which says that that relation still holds when taking about cardinals: The cantor-bernstein theorem.

Notice that this is not trivial: it says that if we have injections from both sides, there exists a bijection between the two sets.

$\endgroup$
  • $\begingroup$ Actually, the maping $\mathbb{B} \rightarrow \mathbb{A} : x \rightarrow \frac{x}{2}$ would be bijective, since everything in $\mathbb{A}$ is also in $\mathbb{B}$. But the mapping $\mathbb{A} \rightarrow \mathbb{B} : x \rightarrow x$ is strictly injective. An injective function may imply that $A \leq B$, but the lack of surjectivity would seem to negate the $=$ part - implying $A < B$ $\endgroup$ – Ephraim Dec 24 '15 at 2:13
  • $\begingroup$ Yes. My mapping is bijective, but in particular, as I've said, it's injective. I'm afraid to say that "the lack of surjectivity would seem to negate the = part$ is incorrect. That works only for finite sets (and the definitions I wrote happen to keep it that way). $\endgroup$ – YoTengoUnLCD Dec 24 '15 at 2:15
  • $\begingroup$ You seem to be confusing what it means for two infinite sets to have the same cardinality. This just means that there exists a way to pair up all the elements from the two sets in a one to one manner. It doesn't matter if you can find a 'worse' arrangement (aka, an injective but not surjective function). $\endgroup$ – YoTengoUnLCD Dec 24 '15 at 2:17
  • $\begingroup$ I guess the reason I am confused is because the intuition is no longer there. The argument for finite sets can be easily explained as a way to count without numbers. For example, if you and I have a bunch of rocks, and you want to see who has more, you can line them up, and see who has left over at the end. If all of mine have one of your rocks next to it, but I have some left over, I have more. If all of your rocks has one of mine next to it, but you have left over, you have more. If there are none left over on either side, they are equal. But this no longer seems to work for infinite sets. $\endgroup$ – Ephraim Dec 24 '15 at 2:21
  • 2
    $\begingroup$ Yes. You are right: For finite sets, having a bijection between two sets is equivalent to having the same number of elements (which is what your analogy is saying: I have the same number of fingers in each hand because I can pair all of them in a one to one manner). However, for infinite sets, saying "number of elements" makes no sense, so we looked for some equivalent condition that holds for finite sets and used to expand the notion of cardinality. $\endgroup$ – YoTengoUnLCD Dec 24 '15 at 2:47
0
$\begingroup$

The injective function $f$ given in OP implies that $|\mathbb{B}| \ge |\mathbb{A}|$. Now consider the injective function $g:\mathbb{B}\to \mathbb{A}$ via $g:x\mapsto \frac{1}{3}x$, which proves that $|\mathbb{A}|\ge |\mathbb{B}|$.

We may combine these with the Shroder-Bernstein theorem to conclude that $|\mathbb{A}|=|\mathbb{B}|$.

$\endgroup$
0
$\begingroup$

I think you may be confused in regard to the following ;

The existence of a bijective map between two sets does not tell us anything about other potential bad maps.

Ie as you said you still can find functions that are not both surjective and injective , but as pointed out , Cantor-Bernstien will hopefully work it all out in the end

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