1
$\begingroup$

Somewhat of a basic question that I've been pondering about, suppose we have 2 finite sets $A,B$, arbitrary sets with arbitrary elements that we know nothing about, except that they are both finite.

We can intuitively say that $card(A) < card(B)$ if there is a function $f:A \to B$ that is injective but not surjective (or "on to"). a simple example would be $A=\{1\}$, $B=\{1,0,-1\}$, $f(x)=x$.

the case that $A$ is finite but $B$ is infinite is also an easy case, it is not hard to show using that above definition that $card(A) < card(B)$, a very intuitive result.

But if $A,B$ are both infinite sets, the above definition fails.

a simple example as to why this fails can be $A=\{2,4,6,...\}$ and $B=\{1,2,3,...\}$ and $f: A\to B$, $f(x)=x$.

$f$ in this case is injective, but not surjective, it is not a bijection. So does that mean $card(A) < card(B)$? it shouldn't, because $f(x)=0.5x$ is a bijection. they should be of same cardinality.

To sum up, is there a better criteria to determine which set is bigger, apart from "$B$ is bigger than $A$ if there is an injective function from $A$ to $B$ that is not surjective and also it is impossible to find a bijection between them" ? To prove that a bijection does not exist between $2$ sets is not always trivial. So what is the criteria that one set is strictly larger than another?

$\endgroup$
1
$\begingroup$

It means that there is an injection from $A$ into $B$, but there is no bijection between $A$ and $B$.

Assuming the axiom of choice, this is the same as saying that there is no surjection from $A$ onto $B$ (but without the axiom of choice, it is possible that $A$ maps injective (with one function) and surjectively (with another) onto $B$, but not bijectively (with any function)).

As often is the case with infinite sets, it might not be possible to actually prove that one cardinal is strictly larger than the other. For example, $2^{\aleph_0}$, the cardinality of $\Bbb R$, is not necessarily strictly larger than $\aleph_1$, the cardinality of $\omega_1$ the first uncountable ordinal, and it is consistent that the two cardinals are equal, and it is consistent that they are not equal (in which case $\aleph_1$ is strictly smaller).

$\endgroup$
  • 1
    $\begingroup$ and what if I can't successfully show that there is no bijection between them? just because I haven't found one doesn't mean that it doesn't exist. $\endgroup$ – Oria Gruber Sep 28 '14 at 20:37
  • $\begingroup$ Yes, it's a pickle. Sometimes it's hard, sometimes it is outright impossible to prove or disprove the existence or non-existence of bijections. $\endgroup$ – Asaf Karagila Sep 28 '14 at 20:39
  • $\begingroup$ I think I understand, thank you Asaf. edit: It is valid to say that $2^{\aleph_0} > \aleph_1$? I'd love to see a proof. $\endgroup$ – Oria Gruber Sep 28 '14 at 20:44
  • $\begingroup$ No, it's not valid. It's only valid to say that $\aleph_1\leq2^{\aleph_0}$, and even that requires the axiom of choice, in which case you can either do something a bit more direct that looks like a proof, or deduce that since every two cardinals are comparable and $2^{\aleph_0}$ is uncountable it has to be that $\aleph_1\leq2^{\aleph_0}$. $\endgroup$ – Asaf Karagila Sep 28 '14 at 20:47
0
$\begingroup$

I think given infinite sets $A,B$, an equivalent definition in terms of surjections and not bijections is:

The cardinality of $B$ is bigger than $A$ iff for all functions $g:A \to B, \space g$ is not a surjection. So just finding one example of a function that is not a surjection is not sufficient to show that the two sets do not have the same cardinality. In your example of $A = \{2,4,6, \dots \}, B= \{1,2,3 ,\dots\}$ it is true that you found a non-surjective function $f$. But since there is a surjection $h:A \to B$ where $h(x) = \frac{x}{2}$ we can not conclude that the cardinality of $A$ is less than $B$. It can be challenging to show that no surjection exists. Are you familiar with the Cantor-Schroeder-Bernstein Theorem? You may be able to prove two sets have the same cardinality without having to consider surjections. Otherwise, a proof by contradiction might work to show no surjective function exists.

https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem

$\endgroup$
  • 1
    $\begingroup$ This should not be the definition. It is equivalent to the definition, but it is not a good substitute (for instance, it is not constructive. What do we do if there are no surjections from $A$ to $B$ or from $B$ to $A$? How do we rule this possibility out?) $\endgroup$ – Andrés E. Caicedo Sep 28 '14 at 21:04
  • $\begingroup$ @AndresCaicedo thank you for the critique; I will rephrase my statement $\endgroup$ – graydad Sep 28 '14 at 22:15
  • $\begingroup$ Note that when you switch to surjections you have to involve the axiom of choice. It should be possible to arrange a model where choice fails and there are two infinite sets that has no injections between them, but there are surjections in both ways. $\endgroup$ – Asaf Karagila Sep 28 '14 at 22:25
  • $\begingroup$ @AsafKaragila Thank you for pointing that out as well; I would have missed that. Where would I include that in my post? Or is what I have said beyond salvaging? $\endgroup$ – graydad Sep 28 '14 at 22:30
  • $\begingroup$ It's not that your post is beyond salvaging, the axiom of choice is not that big of a deal for most people. It's just something that builds on @Andres Caicedo's remark from before. You can end up with pathological situations, and to fix this you use the axiom of choice which easily reduces the whole things back to injections. So the difficulty in proving the existence or non-existence of functions is not any different from what I have remarked in my answer. $\endgroup$ – Asaf Karagila Sep 28 '14 at 22:40

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.