Suppose we have a set $x$ of cardinality $\kappa$. If $\lambda$ is a cardinal lower then $k$, normally we can say that there exists a subset $y$ of $x$ of size $\lambda$. To prove this – I believe – we have to use an instance of choice as strong as the size of $\lambda$. The only way that $ZFC$ have to prove this fact (again, maybe) is the recursion one: we can start with $\emptyset$ and, for each successor ordinal $\alpha<\lambda$, we can construct the set $Y_{\alpha}=Y_{\alpha-1}\cup\{z_{\alpha}\}$ with $z_{\alpha}\in x\setminus Y_{\alpha-1}$, operating continuously at limit steps. To reasoning this way $ZFC$ should make $\lambda$ choices. So the question is: if what I written so far is correct (and if not, then please show me another way to find such a subset for every $\lambda$ and $\kappa$), have I to conclude that is consistent with $ZF$ that there exists a set of cardinality $\kappa$ and a $\lambda<\kappa$ (both necessarily infinite) without any subset of that size?
If $x$ is a set of cardinality $\kappa$ and $\lambda<\kappa$, do we need the axiom of choice to prove that there is a subset of $x$ of size $\lambda$
axiom-of-choicecardinalslogicset-theory
Best Answer
No. You have to use exactly no choice at all.
To say that $|A|\leq|B|$ is to say that there is a function $f\colon A\to B$ which is injective. Therefore the range of this function is a subset of $B$ of cardinality $|A|$, as witnessed by $f$ being the bijection between the two sets.
In fact, you don't even need Replacement. Barely even Separation is required (just bounded one, that is).
(Note that we didn't even limit ourselves to ordinals. In that case things are even simpler, since $\lambda\leq\kappa$ implies $\lambda\subseteq\kappa$, so $\lambda$ is already the subset witnessing that.)