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

Artusartos

## 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.

## 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.

kostas230
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.

Artusartos
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##, ... , $a_m \in A \implies a_m \in X$. 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: