# Thread: Cardinality defined by surjections (or injections)?

1. ## Cardinality defined by surjections (or injections)?

Does anyone know if these following two statements can be proved somehow or are they simply true by definition?

"If there exists a surjective function $f: X \to Y$, then $card(X) \geq card(Y)$"

"If there exists an injective function $f: X \to Y$, then $card(X) \leq card(Y)$"

Both statements are invoked in more advanced proofs without hesitation, so I usually take them for granted. But I realized that's a bad mentality, so I tried to prove those two statements using the definition of injection and surjection but I am not sure if my approach was correct.

For a surjection, it specifies that for all $y \in Y$, there exists an $x \in X$ such that $f(x) = y$. The definition never specified that such an $x$ was unique, so we could construct a mapping of two elements or more elements in $X$ towards one element in $Y$, which would get us a comparison of the cardinality of the two sets. Is that correct (and if it is, rigorous enough)?

For an injection, it only says that if two elements $f(x_1) = f(x_2) \in Y$, then $x_1 = x_2$. It never talked about such an element $y \in Y$ which has no corresponding $x$ element to map from, which would suggest that $card(X)$ could be less than $card(Y)$. Would that work?

I could not find anything online that delved further into the matter. Could someone please shed some light on this matter?

Thanks!

2. Originally Posted by Last_Singularity

"If there exists a surjective function $f: X \to Y$, then $card(X) \geq card(Y)$"
for any $y \in Y$ choose $x_y \in X$ such that $f(x_y)=y.$ now let $X_0=\{x_y : \ y \in Y \}.$ define the map $g: X_0 \longrightarrow Y$ by $f(x_y)=y.$ obviously $g$ is a bijection. thus $\text{card}(X_0)=\text{card}(Y).$

but $X_0 \subseteq X.$ thus $\text{card}(X) \geq \text{card}(X_0)=\text{card}(Y).$

"If there exists an injective function $f: X \to Y$, then $card(X) \leq card(Y)$"
well, this one is trivial: $f:X \longrightarrow f(X)$ is a bijection and $f(X) \subseteq Y.$ thus $\text{card}(X)=\text{card}(f(X)) \leq \text{card}(Y).$

3. Originally Posted by Last_Singularity
"If there exists a surjective function $f: X \to Y$, then $card(X) \geq card(Y)$"

"If there exists an injective function $f: X \to Y$, then $card(X) \leq card(Y)$"
Are you sure these aren't meant to be the other way around?

4. Thanks, NonCommAlg!

Then the next logical question would be: since you proved those statements using the fact that: if $X \subseteq Y$, then $card(X) \leq card(Y)$, would this fact then be the bottom line or could that be proved as well using an even more fundamental principle?

5. Originally Posted by Last_Singularity
Thanks, NonCommAlg!

Then the next logical question would be: since you proved those statements using the fact that: if $X \subseteq Y$, then $card(X) \leq card(Y)$, would this fact then be the bottom line or could that be proved as well using an even more fundamental principle?
your second question is actually a definition. what i did was just to somehow justify the definition. also if we take your second question as a definition, then $X \subseteq Y$ implies $\text{card}(X) \leq \text{card}(Y),$

because the inclusion map $X \longrightarrow Y$ is injective. you cannot find any more fundamental principle.