2
$\begingroup$

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$
12
  • 1
    $\begingroup$ What does "size" even mean? Usually, the size of a finite set is $n$ iff you can find a bijective function from the first $n$ natural numbers to a given set. With that definition, your question becomes clear, as one can compose bijections to make another bijection. It should be noted that just because it's hard for you to find a bijection, or write it out, doesn't mean it isn't there. $\endgroup$ Commented Feb 5, 2019 at 4:59
  • $\begingroup$ @DonThousand That is a good question, I get size is only "defined" for finite sets. Are you implying that if a set has a defined cardinality it is also countable? $\endgroup$
    – CL40
    Commented Feb 5, 2019 at 5:02
  • $\begingroup$ I don't know what you mean by defined cardinality $\endgroup$ Commented Feb 5, 2019 at 5:04
  • $\begingroup$ huh good question, I dont really know either. I guess in my head I was thinking of a set that is finite. The "size" is defined (not infinite). $\endgroup$
    – CL40
    Commented Feb 5, 2019 at 5:05
  • $\begingroup$ Size is usually defined by a bijection, even for finite sets. You can see clearly how this answers your question? $\endgroup$ Commented Feb 5, 2019 at 5:05

3 Answers 3

1
$\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$
0
$\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$ Note that this reasoning is close to circular, as $[1,n]$ is itself a set. We can rephrase the numbering process by stating that "it is possible to remove an element from a non-empty finite set" and combine with the principle of induction. $\endgroup$
    – user65203
    Commented Feb 5, 2019 at 10:14
0
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .