1122: For Map, Cardinality of Range Is Equal to or Smaller Than Cardinality of Domain

<The previous article in this series | The table of contents of this series | The next article in this series>

description/proof of that for map, cardinality of range is equal to or smaller than cardinality of domain

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Proof

---

Starting Context

• The reader knows a definition of map.
• The reader knows a definition of cardinality of set.
• The reader knows a definition of relation.

---

Target Context

• The reader will have a description and a proof of the proposition that for any map, the cardinality of the range is equal to or smaller than the cardinality of the domain.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Structured Description

Here is the rules of Structured Description.

Entities:
$S_1$: $\in \{\text{ the sets }\}$
$S_2$: $\in \{\text{ the sets }\}$
$f$: $:S_1\to S_2$
//

Statements:
$Card(f(S_1))\le Card(S_1)$
//

---

2: Proof

Whole Strategy: Step 1: think of the relation, $R:=\{(s_2,s_1)\in S_2\times S_1|s_2=f(s_1)\}$; Step 2: apply the axiom of choice to have a function, $F\subseteq R$, such that $Dom(F)=Dom(R)$.

Step 1:

Let us think of the relation, $R:=\{(s_2,s_1)\in S_2\times S_1|s_2=f(s_1)\}$.

The domain of $R$ is $Dom(R)=f(S_1)$.

$R$ is not necessarily any function, because for an $s_2$, there may be some multiple $s_1$ s.

Step 2:

But by the axiom of choice, there is a function, $F\subseteq R$, such that $Dom(F)=Dom(R)$.

$F$ is a map from $Dom(F)$ into $S_1$.

$F$ is injective, because for any $s_2,s_2^{\prime }\in Dom(F)$ such that $s_2\ne s_2^{\prime }$, $F(s_2)\ne F(s_2^{\prime })$, because if $F(s_2)=F(s_2^{\prime })$, $s_2=f(F(s_2))=f(F(s_2^{\prime }))=s_2^{\prime }$, a contradiction.

So, $Card(f(S_1))=Card(Dom(R))=Card(Dom(F))\le Card(S_1)$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>