1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Let A be a subset of X, and suppose we have an injection from X to A

  1. Sep 20, 2013 #1
    1. The problem statement, all variables and given/known data

    Let X be a set and let A be a subset of X. Suppose there is an injection $f: X \rightarrow A$. Show that the cardinalities of A and X are equal.

    2. Relevant equations



    3. The attempt at a solution


    I tried proving this for hours but couldn't really get anywhere. So I was wondering if anybody could give me a hint so that I could start from there. By the way, I'm not supposed to use the Cantor-Bernstein Theorem.

    Thanks in advance
     
  2. jcsd
  3. Sep 20, 2013 #2
    Suppose that X is finite. It's easy to prove by contradiction that they have the same cardinalities. A similar of proving the statement goes for the other cardinalities.
     
  4. Sep 20, 2013 #3

    For finite sets, let's suppose that ##|X|=n## and ##|A|=m## where ##m > n##.

    Since ##A \subseteq X##, if ##a \in A## then ##a \in X##. So ##a_1 \in A \implies a_1 \in X##, ##a_2 \in A \implies a_2 \in X##, ... , [itex]a_m \in A \implies a_m \in X[/itex]. So we have a bijection h from X to the set {1, ... m}. But since ##|X|=n##, we also have a bijection k from X to {1, 2, ... ,n}. However, there exists no bijection between {1, 2, ... ,n} and {1, 2, ... , m} since m >n. A contradiction.

    For countably infinite sets, we can use the injection ##f: X \rightarrow A##. Since X is countable, we can list the elements of ##X## as ##x_1, x_2, ... ##. We can also list the elements of A as ##a_1, a_2, ...##. Let us reorder the elements of A so that ##x_1## is sent to ##a_1##, ##x_2## is sent to ##a_2##, and so on. This function must be surjective. Suppose not. Then there exists ##a_k## for some k, such that ##f^{-1}(a_k) = \emptyset##. But this just means that we do not have ##x_k## in ##X##, which is a contradiction, since we assumed that X was countably infinite.

    But I can't really see how I can extend this to uncountable sets....
     
    Last edited: Sep 20, 2013
  5. Sep 20, 2013 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What is the definition of "cardinality"? Or, perhaps just the definition of "same cardinality".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted