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$?

Question

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?

Answer 1

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

Answer 2

This is unorthodox, but I'm going to answer the interesting follow-up question raised by the OP in the comments. I had fun figuring out the answer, and it's too long for a comment, so why not write it down here?

Suppose $Y\subseteq X$ and $A$ is a set with $|Y|\leq |A|\leq |X|$. Can we prove without choice that there exists a subset $A'$ with $Y\subseteq A'\subseteq X$ and $|A'| = |A|$?

Yes. Let $g\colon Y\to A$ and $h\colon A\to X$ be injective functions witnessing $|Y|\leq |A|$ and $|A|\leq |X|$. We will define an injective function $f\colon A\to X$ with $Y\subseteq f(A)$, so taking $A' = f(A)$ works.

The idea is to adjust the existing injective function $h\colon A\to X$ to make its image contain $Y$. Well, $A$ already contains a copy $g(Y)$ of $Y$, so a basic idea is to define $$f(a) = \begin{cases} h(a) & \text{if }a\notin g(Y)\\ g^{-1}(a) & \text{if }a\in g(Y).\end{cases}$$ Then $Y\subseteq f(A)$, but $f$ may not be injective. A failure of injectivity comes from an element $g^{-1}(a)\in Y$ which is already in the image of $h$ on $A\setminus g(Y)$. We can fix this by mapping any such $a$ to $h(a)$ instead of $g^{-1}(a)$. This may introduce further failures of injectivity, but they can be fixed iteratively. Altogether, we get the following argument.

Define $Z_0 = A\setminus g(Y)$. By induction, define $Z_{n+1} = Z_n \cup \{a\in g(Y)\mid g^{-1}(a)\in h(Z_n)\}$. Let $Z = \bigcup_{n\in \omega} Z_n$.

Now define, for all $a\in A$, $$f(a) = \begin{cases} h(a) & \text{if }a\in Z\\ g^{-1}(a) & \text{if }a\notin Z.\end{cases}$$

• $f$ is injective. Since $h$ and $g^{-1}$ are injective, any failure of injectivity comes from $h(a) = g^{-1}(b)$ for some $a\in Z$ and $b\notin Z$. But then $a\in Z_n$ for some $n\in \omega$, so $g^{-1}(b) = h(a) \in h(Z_n)$, and $b\in Z_{n+1}\subseteq Z$, contradiction.

• $Y\subseteq f(A)$. Let $y\in Y$. If $g(y)\notin Z$, then $f(g(y)) = g^{-1}(g(y)) = y\in f(A)$. So assume $g(y)\in Z$. Then $g(y)\in Z_n$ for some $n\in \omega$. Let $n$ be least such that $g(y)\in Z_n$, and note $n>0$ since $g(y)\in g(Y)$. Then $y = g^{-1}(g(y))\in h(Z_{n-1})\subseteq f(Z)$, as desired.