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.

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

 

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

 

[HallsofIvy]

What is the definition of "cardinality"? Or, perhaps just the definition of "same cardinality".