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