Take the 2-minute tour ×

if we take a {1, 2, 3} set as a countable set.
it has subsets with 2 elements right, Those sets are : {1, 2}, {1, 3}, {2, 3}.
But what about uncountable sets?
if we take a (0, 9) set as subset of real numbers or rational numbers which has many elements, how can i get subsets with two elements of this uncountable set?

share|improve this question
Firstly, as a subset of the rationals, $(0,9)$ is countable. But to pull out only two elements, I might choose, say, $\{ 1, 2 \}$, as they're certainly in that set. –  mixedmath Oct 28 '12 at 15:58
I don't understand why you retagged this like that. It has nothing to do with functional analysis, and it's much more [elementary-set-theory] than [set-theory]. –  Asaf Karagila May 10 '13 at 9:35

1 Answer 1

up vote 3 down vote accepted

Suppose $A$ is an uncountable set. In particular it is infinite. Fix $k-1$ elements from $A$, say $a_1,\ldots,a_{k-1}$.

Now for every $a\in A\setminus\{a_1,\ldots,a_{k-1}\}$ the function $a\mapsto\{a,a_1,\ldots,a_{k-1}\}$ is injective. Again, since $A$ is uncountable we have that $A\setminus\{a_1,\ldots,a_{k-1}\}$ is equipotent with $A$.

Therefore there are at least $|A|$ many subsets of size $k$; on the other hand we have that $|\{B\subseteq A\mid B\text{ is finite}\}|=|A|$ as well. While not a completely trivial theorem, it is still a true theorem for any infinite set. Therefore there cannot be more than $|A|$ sets of size $k$.

Therefore the cardinality of $\{B\subseteq A\mid |B|=k\}$ is exactly $|A|$.

(Note that I am assuming the axiom of choice holds, or at least that $A$ can be well-ordered. This is not an uncommon assumption in modern mathematics. The question, when asked in the broader context where the axiom of choice fails and $A$ cannot be well-ordered is vastly more complicated to answer due to all sort of pathological sets which may arise.)

share|improve this answer
Not an uncommon assumption is definitely a litotes! –  Brian M. Scott Oct 28 '12 at 17:52
@Brian: It is not not not not a litotes, you meant to say! :-) (I'm assuming the real life has double negation elimination, by the way...) –  Asaf Karagila May 10 '13 at 10:16

Your Answer


