Given a set $X$ and a cardinal $\kappa$ such that $\kappa<|X|$, can I always find a subset of $X$ which has cardinality $\kappa$?

If that's the case, then there must be a subset of the reals which has cardinality $\aleph_1$ ( even though we cannot prove there's a bijection between it and the reals themselves ) is there an explicit example of such a subset?

  • $\begingroup$ The answer may depend on your set theory. For example, without the Axiom of Choice (or at least some weaker version, such as Countable Choice), you cannot show that every infinite set contains an infinite countable subset (that is, a set of cardinality $\aleph_0$). $\endgroup$ – Arturo Magidin Jul 28 '19 at 4:35
  • $\begingroup$ Do you mean $\aleph_0 $? Because I normally think of $\aleph_1$ as the cardinality of $\Bbb R$. Though some expert will probably say this assumes CH. There is a different symbol, but I've forgotten what it is. Surely I can find it by googling. Anyway there's $\Bbb Z\subset \Bbb R$ at $\aleph_0 $, and any interval at $\aleph_1$. I see the responders below are both at a higher level than myself, in this. The symbol I was looking for was $\beth$. Sorry experts, for being like a bull in a China shop. $\endgroup$ – Chris Custer Jul 28 '19 at 4:39
  • $\begingroup$ @ArturoMagidin Thank you, that's nice how even simple constructions turn out to be independent of ZF. I was actually expecting it to be provable in it. $\endgroup$ – victormd Jul 28 '19 at 4:48
  • $\begingroup$ You are assuming that $\aleph_1 \ne 2^{\aleph_0}$? The continuum hypothesis states it is. If we don't accept the continuum hypotheses and assume it isn't then yes, there can be a subset of cardinality $\aleph_1$ but, like $\aleph_1$ itself, t is hypothetical. $\endgroup$ – fleablood Jul 28 '19 at 4:49
  • 4
    $\begingroup$ @ChrisCuster: It's not just experts that will tell you that assuming $|\mathbb{R}|=\aleph_1$ means assuming the Continuum Hypothesis; it's anyone who actually knows what $\aleph_1$ means and what CH states. Though it is not uncommon to find a lot of people who think that what CH states is that "there isn't any cardinal strictly between $\aleph_0$ and $\aleph_1$", in fact $\aleph_1$ is by definition, the smallest cardinal strictly larger than $\aleph_0$. $\endgroup$ – Arturo Magidin Jul 28 '19 at 5:33

By definition, the cardinality of set $Y$ is smaller than the cardinality of set $X$ exactly if there exists an injection from $Y$ into $X$. Obviously the image of $Y$ in $X$ then has the same cardinality as $Y$. Thus yes, if $k<|X|$, then $X$ has a subset of cardinality $k$.

And this indeed means that $\mathbb R$ has a subset of cardinality $\aleph_1$. But we cannot explicitly give one. Or more exactly, we cannot give an explicit set of which we can prove that its cardinality is $\aleph_1$. Of course since it is consistent that $\mathbb R$ has cardinality $\aleph_1$, just $\mathbb R$ itself might be such an example. But we cannot prove or disprove it.

Note that my first paragraph is independent of the axiom of choice. However, the second paragraph isn't, as without the axiom of choice it is consistent that $|\mathbb R|\ngeq\aleph_1$.

  • $\begingroup$ Can't we well order the cardinals without AC? Cause the rationals have a clear injection on the reals. $\endgroup$ – victormd Jul 28 '19 at 4:53
  • $\begingroup$ @victormd: No, without AC we can't well-order all cardinals. It is true that $|\mathbb R|\gt \aleph_0$, as shown by the inclusion of the rationals (or, more directly, the natural numbers, which are the very definition of $\aleph_0$). But without AC, $|X|>\aleph_0$ does not imply $|X|\ge\aleph_1$. $\endgroup$ – celtschk Jul 28 '19 at 4:59
  • 1
    $\begingroup$ @celtschk: I think that without AC you have to be careful about what “cardinals” means. One can certainly define the cardinals by letting them be the alephs without AC (the alephs being the ordinals that cannot be bijected with any strictly smaller ordinal), but of course then the problem is that not every set is necessarily bijectable with a cardinal. But with that definition, the cardinals are trivially well-ordered, since they form a subclass of the ordinals. $\endgroup$ – Arturo Magidin Jul 28 '19 at 6:24
  • 1
    $\begingroup$ @celtschk: I think we are talking at cross purposes, or at least inexactly as to what exactly is being meant here. For one thing, the statement that given any two sets there is either an injection from one to the other or an injection from the other to the one is equivalent to the Axiom of Choice, and that is a statement that I would interpret as “the cardinality of two sets can be compared”. So I think this is really confusion because “cardinality” is unclear in the absence of Choice. $\endgroup$ – Arturo Magidin Jul 28 '19 at 7:16
  • 1
    $\begingroup$ @celtschk: as I suspected, this arises out of the problem of figuring out what “cardinality” means when you don’t have AC. To me, when you say “can be compared”, it implies that the order is total, not merely partial (as the defining characteristic of a total order vs a partial order is that you can compare any two elements). In any case, we are both aware that these notions become difficult and problematical in the absence of AC, and that careful definitions are needed in that case, and we can leave it at that. $\endgroup$ – Arturo Magidin Jul 28 '19 at 18:39

Under $ZFC$ every set is equinumerous with some cardinal and can be well ordered, so you can just well order it and take the first $\kappa$ items for a subset of size $\kappa$.

It is consistent with $ZFC$ that the reals are of size $\aleph_1$, in which case any subset larger than $\aleph_0$ has size $\aleph_1$. If the reals are larger than $\aleph_1$ they have a (many) subset(s) of size $\aleph_1$ but we cannot display one. If we could and we could show it was smaller than the reals we would know the reals were at least $\aleph_2$.


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.