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
- 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 \vert 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 \vert 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 \in Dom (F)\) such that \(s_2 \neq s'_2\), \(F (s_2) \neq F (s'_2)\), because if \(F (s_2) = F (s'_2)\), \(s_2 = f (F (s_2)) = f (F (s'_2)) = s'_2\), a contradiction.
So, \(Card (f (S_1)) = Card (Dom (R)) = Card (Dom (F)) \le Card (S_1)\).
