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?

  • $\begingroup$ 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. $\endgroup$ – davidlowryduda Oct 28 '12 at 15:58
  • $\begingroup$ 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]. $\endgroup$ – Asaf Karagila May 10 '13 at 9:35

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

  • 2
    $\begingroup$ Not an uncommon assumption is definitely a litotes! $\endgroup$ – Brian M. Scott Oct 28 '12 at 17:52
  • $\begingroup$ @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...) $\endgroup$ – Asaf Karagila May 10 '13 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.