Does equal sizes of two sets imply they have the same cardinality in general?
This may seem like a silly question (and it certainly seems that way asking it) but I want to make sure my thought process is correct.
If two sets have the same cardinality then we can define a function $f: A \to B$ that is one-to-one and onto. Cardinality refers to the size of the sets.
Suppose instead I have two sets I know are the same size. Fixing an example:
$A: \{1, 2, 3\}$
$B: \{4, 5, 6\}$
Each has 3 elements. Since they have the same size, does this imply I can find a one-to-one and onto function $f: A \to B$? I would guess so. If I had to pin point my confusion - I think it comes from defining the function. In this case, I think I can define a a function $f = a + 3$, that maps exactly one element of $a \in A$ to every $b \in B$, and every $b \in B$ has some $a \in A$ such that $f(a) = b$.
Is this true in general?
$\endgroup$ 123 Answers
$\begingroup$Notation. "$X\lesssim Y$" is notation for "there exists a 1-to-1 function from $X$ to $Y$."
Notation. "$X\sim Y$" is notation for "there exists a 1-to-1 onto function from $X$ to $Y$."
Terminology. Say $X$ is finite if there exists a natural number $n$ such that $X\lesssim\{1,\ldots,n\}$.
Definition. Let $X$ be a nonempty finite set. The cardinality of $X$, denoted $\#X$, is $$\min\{n\in\mathbb{N}:X\lesssim\{1,\ldots,n\}\}.$$
Theorem. Let $X$ be a nonempty finite set. Then $$\{n\in\mathbb{N}:X\sim \{1,\ldots,n\}\}=\{\#X\}.$$
Corollary. Let $X$ and $Y$ be nonempty sets of the same size. That is to say, $\#X=\#Y$. Then there exists a bijection from $X$ to $Y$. That is to say, $X\sim Y$.
Proof. Assume $\#X=\#Y$. Fix a bijection $\phi:X\to\{1,\ldots,\#X\}$. Fix a bijection $\psi:Y\to\{1,\ldots,\#Y\}$. Then $\psi^{-1}\circ\phi$ is a bijection from $X$ to $Y$ as desired. $\square$
$\endgroup$ $\begingroup$You can number the elements of a finite set, i.e. associate to every element a natural in $[1,n]$ where $n$ is the cardinality. This numbering is a bijection.
Then you can match any two sets of the same cardinality by relating the elements with the same index. This defines the bijection you are looking for.
Note that this also holds for infinite countable sets.
$\endgroup$ 1 $\begingroup$Choose arbitrarily an element from $A$ and an element from $B$ and remove them, as long as the sets are non-empty.
If the sets are finite, the process will stop. If they have the same size, they will both be empty, and all their elements have been associated in pairs, defining a bijection.
$\endgroup$
