6
$\begingroup$

Definition. Two sets have the same cardinality iff they can be put into one-to-one correspondence; or, $$A \simeq B \iff |A| = |B| $$

This definition applies to infinite as well as to finite sets. It follows from the last three definitions that set $A$ has a larger cardinality than set $B$ iff both

  1. a proper subset of $A$ and the whole of $B$ can be put into one-to-one correspondence
  2. the whole of $A$ cannot be put into one-to-one correspondence with any proper subset of $B$.

From: A Crash Course in the Mathematics Of Infinite Sets Peter Suber, Philosophy Department, Earlham College

The last part specifically refers to proper subsets of $B$. That excludes at least one subset of $B$, namely $B$. So, is it possible that the whole of A cannot be put into one-to-one correspondence with any proper subset of $B$ but may with $B$ itself? Why did he not say "any subset of $B$"?

$\endgroup$
  • $\begingroup$ Use Mathjax for more flexible math typesetting. You can typeset $x\cong y$, $x \simeq y$ or $x\sim y$ by typing $x\cong y$, $x\simeq y$ or $x\sim y$. $\endgroup$ – Jam Mar 5 '20 at 16:56
  • 2
    $\begingroup$ The set of all even natural numbers is a proper subset of $\Bbb N$ with the same cardinality. Any set has a bijection to itself, that's why it is excluded from the definition of finite set. $\endgroup$ – Berci Mar 5 '20 at 16:59
  • 1
    $\begingroup$ What do you mean by "larger than" in this context? Yes, it is possible for a proper subset of an infinite set to have the same cardinality. E.g. the even integers vs the integers. $\endgroup$ – JMoravitz Mar 5 '20 at 16:59
  • 1
    $\begingroup$ @JMoravitz: I think OP's title is misleading. The real question seems to be, is it possible for there to be a bijection between (infinite) sets $A$ and $B$ without there being a bijection between $A$ and any proper subset of $B$? (Because if $A$ and $B$ are finite sets, then shouldn't condition $1$ be sufficient for $|A| > |B|$?) $\endgroup$ – Brian Tung Mar 5 '20 at 17:06
  • $\begingroup$ In that case, no... as any infinite set has a countable subset, consider such a countable subset $A^*=\{a_1,a_2,a_3,\dots\}$ of $A$, and the image under the bijection $f$ between $A$ and $B$ of that countable subset in $B$. Now construct a new bijection between $A$ and $B\setminus\{f(a_1)\}$ given by $g(x) = \begin{cases} f(x)&\text{if }x\notin A^*\\ f(a_{n+1})&\text{if }\exists n,x=a_n\end{cases}$. Note that $B\setminus\{f(a_1)\}$ is a proper subset of $B$. $\endgroup$ – JMoravitz Mar 5 '20 at 17:12
0
$\begingroup$

I believe the specification in $(2)$ of proper subsets instead of the full set, $B$, is a historical remnant from Cantor's original formulation of the definition. As the other answer and comment by egreg and JMoravitz have demonstrated, the specification is redundant. It is also absent from some later definitions of "larger cardinality than".


The effect of the two components of the definition is that (2) establishes that the two sets have unequal cardinalities and then (1) distinguishes the order of the inequality to discern which set is larger. $(2)$ alone would be true for $\{1,2,3\}$ and $\{1,2\}$, since any attempted pairing of their elements leaves an unpaired remainder, but fails to specify the order of the sets sizes. $(1)$ alone would be true for $\mathbb{N}$ and $\mathbb{N}_{\text{even}}$, despite them being the same size; all natural numbers can be paired with an even number in the subset by doubling them.

The definition of "larger cardinality than" that you cite is due to (Cantor, 1895 pp. 483-484). The following is an abridged excerpt from (Cantor, 1915 pp. 89-90), the translation of the 1895 publication. This is further discussed in (Bezhanishvili and Landreth, p. 17). I've rewritten the excerpt with modern notation and terminology. *

"Greater" and "Less" with Powers

If for two sets $A$ and $B$ with the cardinalities $b = |B|$ and $a=|A|$, both the conditions:

  1. There is a subset $A_1$ of $A$, such that $|A_1|=|B|$,

  2. There is no subset of $\mathbf{B}$ which is bijective with $A$,

are fulfilled ... they express a definite relation of the cardinalities $a$ and $b$ to one another. Further, the equivalence of $A$ and $B$, and thus the equality of $a$ and $b$, is excluded... Thirdly, the relation of $a$ to $b$ is such that it makes impossible the same relation of $b$ to $a$...

We express the relation of $a$ to $b$ characterized by $(1)$ and $(2)$ by saying: $b$ is “less” than $a$ or $a$ is “greater” than $b$; in signs $b<a$ or $a > b$.

Cantor's statements $(1)$ and $(2)$ respectively represent your two statements but we see that Cantor's formulation of $(2)$ references the subsets of the smaller set, $B$. To quote the original text, "Es giebt keinen Theil von $M$ der mit $N$ äquivalent ist". That is to say "There is no part from the smaller set that is equivalent with the larger set".


You are vindicated in your questioning since some more modern formulations of the definition, e.g., (Meyries, p. 8) eschew the redundant stipulation of subsets in $(2)$: *

The set $A$ is called of larger cardinality than the set $B$, if

  1. $B$ is of equal cardinality as a subset of $A$

  2. and if $\mathbf{B}$ and $A$ are not of equal cardinality.

In this case one symbolically writes $|A| > |B|$.

Others express the definition using injectivity of functions, again using $B$ itself instead of its subsets, e.g., (Neely, 2020 p. 12): *

We say $|B| < |A|$ if:

  1. there is an injection $f : B → A$

  2. there is no injection $f : A → \mathbf{B}$


References


* NB: In the excerpts, I have changed their notation of the sets to $A$ and $B$ and swapped the order of the definition's two components to match your $(1)$ and $(2)$.

$\endgroup$
3
$\begingroup$

Any infinite set $B$ has at least a proper subset $C$ such that $|C|=|B|$ (assuming choice, of course, or some weaker axiom thereof).

Since $B$ is infinite, it is not empty. Let $b_0\in B$ and consider $C=B\setminus\{b_0\}$.

Then $|B|=|C|$. Indeed, take a countable subset $Z$ of $B$ (it exists by choice). Then $Z\cup\{b_0\}$ is countable as well, so we can assume $b_0\in Z$. There exists a bijection $f\colon\mathbb{N}\to Z$ such that $f(0)=b_0$. Now consider $F\colon B\to C$ defined by $$ F(x)=\begin{cases} f(n+1) & \text{if $x\in Z$ and $x=f(n)$} \\[4px] x & \text{if $x\notin Z$} \end{cases} $$ It's easy to prove that $F$ is a bijection.

If $|A|=|B|$, then we can use $F$ to provide also a bijection $A\to C$ and $C$ is a proper subset of $B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy