• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter Artusartos
  • Start date
  • #1
247
0

Homework Statement



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.

Homework Equations





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
 

Answers and Replies

  • #2
96
3
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.
 
  • #3
247
0
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.

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:
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
955
What is the definition of "cardinality"? Or, perhaps just the definition of "same cardinality".
 

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

Replies
1
Views
948
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
5
Views
835
Replies
1
Views
3K
Replies
2
Views
1K
Replies
4
Views
2K
Top