Do $X$ and $Y$ have the same cardinality if their families of finite subsets do?

Question

Let $X$ and $Y$ be sets. It is undecidable in ZFC whether $2^{|X|} = 2^{|Y|}$ implies $|X| = |Y|$ (in Cohen's original model for ZFC + $\neg$CH, one has $2^{\aleph_0} = 2^{\aleph_1}$). What if we restrict our attention to the finite parts of $X$ and $Y$?

Question. Do $X$ and $Y$ have the same cardinality if the families of finite subsets of both sets do?

As noted by Nik Weaver in a comment, the answer is yes when we assume in the background to be working with the axioms of ZFC. But, what about ZF?

I feel this must be either basic or very well known (to those who know it very well).

Answer 1

It can be proved in $\mathsf{ZF}$ that ``for all cardianls $\mathfrak{a},\mathfrak{b}$, if $\mathrm{fin}(\mathfrak{a})=\mathrm{fin}(\mathfrak{b})$, then $\mathfrak{a}=\mathfrak{b}$'' implies $\mathsf{AC}$. Here $\mathrm{fin}(\mathfrak{a})$ denotes the cardinality of the set of all finite subsets of a set which is of cardinality $\mathfrak{a}$.

Assume that, for all cardianls $\mathfrak{a},\mathfrak{b}$, if $\mathrm{fin}(\mathfrak{a})=\mathrm{fin}(\mathfrak{b})$, then $\mathfrak{a}=\mathfrak{b}$. We prove $\mathsf{AC}$ by showing that, for an arbitrary limit ordinal $\lambda$, $\mathrm{V}_\lambda$ is well-orderable. Let $\mathfrak{a}$ be the cardinality of $\mathrm{V}_\lambda$ and let $\kappa$ be the Hartogs number of $\mathrm{V}_\lambda$, i.e., the first ordinal that cannot be mapped injectively into $\mathrm{V}_\lambda$. Note that every finite subset of $\mathrm{V}_\lambda$ is an element of $\mathrm{V}_\lambda$, so $\mathrm{fin}(\mathfrak{a})=\mathfrak{a}$.

It suffices to prove that $\mathrm{fin}(\mathfrak{a}+\kappa)=\mathrm{fin}(\mathfrak{a}\cdot\kappa)$, since then by our assumption we would have $\mathfrak{a}+\kappa=\mathfrak{a}\cdot\kappa$, and thus $\mathfrak{a}$ is well-ordered by a lemma of Tarski. Clearly, $\mathrm{fin}(\mathfrak{a}+\kappa)=\mathrm{fin}(\mathfrak{a})\cdot\mathrm{fin}(\kappa)=\mathfrak{a}\cdot\kappa$. It remains to show that $\mathrm{fin}(\mathfrak{a}\cdot\kappa)=\mathfrak{a}\cdot\kappa$. It is proved as follows.

Let $u$ be an arbitrary finite subset of $\mathrm{V}_\lambda\times\kappa$. Then $\mathrm{ran}(u)=\{\alpha\mid\exists x(\langle x,\alpha\rangle\in u)\}$ is a finite subset of $\kappa$, and thus there is a unique isomorphism $h_u$ of $\mathrm{ran}(u)$ onto some natural number. Note that $u$ is uniquely determined by $\langle\mathrm{ran}(u),\{\langle x,h_u(\alpha)\rangle\mid\langle x,\alpha\rangle\in u\}\rangle$, so $$ \mathrm{fin}(\mathfrak{a}\cdot\kappa)\leqslant\mathrm{fin}(\kappa)\cdot\mathfrak{a}=\mathfrak{a}\cdot\kappa, $$ which completes the proof.$\quad\square$

Answer 2

If $\mathrm{ZF}$ is consistent, then it does not prove the statement.

Let $\left<x_n\right>_{n<\omega}$ be generic for the finite support product of an $\omega$-sequence of Cohen forcings. Let $C=\{x_n\}_{n<\omega}$ and let $M=L(C\cup\{C\})$. So $M\models \mathrm{ZF}$. Let $\Theta$ be the least ordinal which is not the surjective image of $C$ in $M$. Then the claim is that $M\models \text{$``|\mathcal{P}_{<\omega}(X)|=|\mathcal{P}_{<\omega}(Y)|$ but $|X|\neq|Y|$"}$ where $X=C\cup\Theta$ and $Y=\mathbb{R}^M\cup\Theta$, giving counterexamples to the question in $M$.

A standard observation: given $x\in\mathbb{R}^M$, note that there is a finite set $S\subseteq C$ such that $x$ is $\mathrm{OD}_{S\cup\{C\}}^{M}$, and hence by homogeneity, in fact $x\in L[S]$. Let the support $S_x$ of $x$ be the least such set. (Note that if $S$, $S'$ are two such sets, then $x$ is also $\mathrm{OD}_{(S\cap S')\cup\{C\}}^{M}$, by mutual genericity: letting $T=S\cap S'$, then $x\in L[S]\cap L[S']=L[T][S\setminus T]\cap L[T][S'\setminus T]$, so $x\in L[T]$.)

Given a finite set $A\subseteq \mathbb{R}^M$, let the support $S_A$ of $A$ be $S_A=S_{x_0}\cup S_{x_1}\cup\dotsb\cup S_{x_{n-1}}$ where $A=\{x_0,\dotsc,x_{n-1}\}$. Note that the map $A\mapsto S_A$ is in $L(C\cup\{C\})$.

Note also that since $S_A$ is a finite set of reals, it is canonically wellordered, just by using the restriction of the standard linear order of the reals. Let $<_A$ be this wellorder.

Now to see that $M\models\text{$``|\mathcal{P}_{<\omega}(C\cup\Theta)|=|\mathcal{P}_{<\omega}(\mathbb{R}^M\cup\Theta)|$"}$, we just need to see that $M$ has an injection $$ \pi:\mathcal{P}_{<\omega}(\mathbb{R}^M\cup\Theta)\to\mathcal{P}_{<\omega}(C\cup\Theta),$$ since in fact $C\cup\Theta\subseteq \mathbb{R}^M\cup\Theta$. Let $B\subseteq\mathbb{R}^M\cup\Theta$ be finite; we will define $\pi(B)$. Let $A=B\cap\mathbb{R}^M$ and set $\pi(B)\cap C=S_A$. Let $A'=B\cap\Theta$ and set $\pi(B)\cap\Theta=\{\gamma\}$ where $\gamma$ is the G"odel code of the pair $(\alpha,\beta)$, where $\alpha$ naturally codes $A'$ and $\beta$ is the position of $A$ in the $L[S_A]$-wellorder, where we use $<_A$ to order $S_A$ in a specific manner, so that $\beta$ is then uniquely determined. So overall, we define $$ \pi(B)= S_A\cup\{\gamma\}.$$ Note that $\pi$ is an injection.

It remains to see that $M\models \text{$``|C\cup\Theta|\neq|\mathbb{R}^M\cup\Theta|$"}$, for which it suffices to see that $M\models``\text{There is no injection $\sigma:\mathbb{R}^M\to C\cup\Theta$"}$. So suppose we have such an injective $\sigma\in M$. Then there is a finite set $A\subseteq C$ such that $\sigma\in\mathrm{OD}^{M}_{A\cup\{C\}}$. But then if $x\in\mathbb{R}^M$ and $\sigma(x)\in\Theta$, then by homogeneity, $x\in L[A]$. In particular, if $x\in C$ and $\sigma(x)\in\Theta$, then $x\in A$, so there are only finitely many such $x$. So if $x\in C\setminus A$ then $\sigma(x)\in C$, but $\sigma(x)\notin A$, since $x\notin L[A]$. So in fact if $x\in C\setminus A$ then $\sigma(x)=x$. But now letting $x_0,x_1\in C\setminus A$ with $x_0\neq x_1$, we have $x_0\oplus x_1\notin L[A]$, so $\sigma(x_0\oplus x_1)\notin A\cup\Theta$, but also $\sigma(x_0\oplus x_1)\notin C\setminus A$, since $\sigma``(C\setminus A)=C\setminus A$. This is a contradiction.