Results 1 to 5 of 5

Math Help - Cardinality defined by surjections (or injections)?

  1. #1
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157

    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!
    Last edited by Last_Singularity; December 26th 2008 at 07:13 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Last_Singularity View Post

    "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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by Last_Singularity View Post
    "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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Last_Singularity View Post
    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.
    Last edited by NonCommAlg; December 26th 2008 at 08:18 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Continuous surjections
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 4th 2011, 01:55 PM
  2. Proof regarding injections and bijections
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 19th 2010, 03:41 PM
  3. Replies: 2
    Last Post: August 5th 2009, 10:20 AM
  4. Cardinality of a Set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 03:33 PM
  5. Surjections and a true/false statement.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 17th 2008, 04:43 AM

Search Tags


/mathhelpforum @mathhelpforum