# 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 $\displaystyle f: X \to Y$, then $\displaystyle card(X) \geq card(Y)$"

"If there exists an injective function $\displaystyle f: X \to Y$, then $\displaystyle 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 $\displaystyle y \in Y$, there exists an $\displaystyle x \in X$ such that $\displaystyle f(x) = y$. The definition never specified that such an $\displaystyle x$ was unique, so we could construct a mapping of two elements or more elements in $\displaystyle X$ towards one element in $\displaystyle 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 $\displaystyle f(x_1) = f(x_2) \in Y$, then $\displaystyle x_1 = x_2$. It never talked about such an element $\displaystyle y \in Y$ which has no corresponding $\displaystyle x$ element to map from, which would suggest that $\displaystyle card(X)$ could be less than $\displaystyle 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 $\displaystyle f: X \to Y$, then $\displaystyle card(X) \geq card(Y)$"
for any $\displaystyle y \in Y$ choose $\displaystyle x_y \in X$ such that $\displaystyle f(x_y)=y.$ now let $\displaystyle X_0=\{x_y : \ y \in Y \}.$ define the map $\displaystyle g: X_0 \longrightarrow Y$ by $\displaystyle f(x_y)=y.$ obviously $\displaystyle g$ is a bijection. thus $\displaystyle \text{card}(X_0)=\text{card}(Y).$

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

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

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

"If there exists an injective function $\displaystyle f: X \to Y$, then $\displaystyle 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 $\displaystyle X \subseteq Y$, then $\displaystyle 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 $\displaystyle X \subseteq Y$, then $\displaystyle 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 $\displaystyle X \subseteq Y$ implies $\displaystyle \text{card}(X) \leq \text{card}(Y),$

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