8
$\begingroup$

Is there a model of ${\sf ZF}$ such that there is an infinite set $X$ and a injective map $f:{\cal P}(X)\to {\cal P}(X)$ so that for $a\neq b \in {\cal P}(X)$ we have $|f(a)\cap f(b)| \leq 1$?

Note. As user Gro-Tsen in the comments below points out, if we weaken the condition $|f(a)\cap f(b)| \leq 1$ to "$f(a)\cap f(b)$ is finite", then the resulting statement is a theorem of ${\sf ZFC}$.

Improve this question
$\endgroup$
8
  • 5
    $\begingroup$ It might be worth pointing out that (it is an easy theorem of ZF that) there exists $f\colon\mathcal{P}(\mathbb{N})\to\mathcal{P}(\mathbb{N})$ such that $f(a)\cap f(b)$ is finite for every $a\neq b$ in $\mathcal{P}(\mathbb{N})$ (see, e.g., Jech, Set Theory, third millennium ed., lemma 9.21). $\endgroup$
    – Gro-Tsen
    Oct 30, 2017 at 15:34
  • 5
    $\begingroup$ (In fact, the proof of the statement in my previous comment is so easy I might as well write it here: map an infinite binary sequence to the sequence of its finite prefixes, and use obvious bijections to get a map $f\colon\mathcal{P}(\mathbb{N})\to\mathcal{P}(\mathbb{N})$ with the same properties.) $\endgroup$
    – Gro-Tsen
    Oct 30, 2017 at 15:37
  • $\begingroup$ Thanks @Gro-Tsen - I am aware of this result; if you strengthen the finiteness condition you mention to "$f(a)\cap f(b)$ is empty or at most a singleton" (or contains at most $n$ elements for some fixed $n\in\mathbb{N})$ then the resulting statement is false in ZFC, but maybe not in ZF. But coming back to your statement, I will include it in the problem statement -- thank you again! $\endgroup$
    – Dominic van der Zypen
    Oct 30, 2017 at 15:55
  • 2
    $\begingroup$ Where can I find a proof of the fact that the statement with $|f(a)\cap f(b)|\leq 1$ is refutable in ZFC? How about with $|f(a)\cap f(b)|\leq k$ (with $k$ constant)? (Maybe these questions are stupid.) $\endgroup$
    – Gro-Tsen
    Oct 30, 2017 at 21:43
  • 3
    $\begingroup$ Alex: Choose for each $a$ with $|f(a)|>k$, a $k+1$-element subset of $f(a)$. Under the axiom of choice, $|X|^{k+1}=|X|$, so there are at most $|X|$ such elements of $P(X)$. Similarly, the number of those elements of $P(X)$ for which $|f(a)|\leq k$ is also $\leq|X|$, so we get that $|P(X)|\leq|X|$, contradicting Cantor's theorem. $\endgroup$
    – Péter Komjáth
    Nov 21, 2017 at 6:39

1 Answer 1

Reset to default
-1
$\begingroup$

What if we make an attempt like this as follows: There is no such ZF model. We can prove in ZF that there is no infinite set X and injective function $f:\mathcal{P}(X)\rightarrow\mathcal{P}(X)$ such that $\vert f(a)\cap f(b)\vert\leq 1$ for all $a\neq b\in \mathcal{P}(X)$. There are atmost $\vert X \vert^{2}$ many elements $a$ of $\mathcal{P}(X)$ such that $\vert f(a)\vert > 1$. Similarly, there are atmost $\vert X \vert^{2}$ many elements $a$ of $\mathcal{P}(X)$ such that $\vert f(a)\vert \leq 1$. Hence, we obtain $\vert\mathcal{P}(X)\vert\leq\vert X \vert ^{2}$. Now it's possible to prove in ZF that $\vert\mathcal{P}(X)\vert\ \not\leq \vert X \vert ^{2}$ for any infinite set X and thus we obtain a contradiction.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ "There are atmost $\vert X \vert^{2}$ many elements $a$ of $\mathcal{P}(X)$ such that $\vert f(a)\vert > 1$." How do you prove this in ZF? $\endgroup$
    – Nate Eldredge
    Feb 8, 2018 at 23:56
  • 6
    $\begingroup$ You cannot prove in $\mathsf{ZF}$ that $|\mathcal P (X)|>|X|^2 $ for $X$ infinite. $\endgroup$
    – Andrés E. Caicedo
    Feb 9, 2018 at 1:05
  • $\begingroup$ @AndrésE.Caicedo What if we use the Theorem 4.2 from the Combinatorial Set Theory book by Lorenz J. Halbeisen ? I think then we can claim in ZF that $\vert\mathcal{P}(X)\vert \not\leq \vert X \vert^{2}$ for any infinite set X. I edited. $\endgroup$
    – Amitayu Banerjee
    Feb 9, 2018 at 8:46
  • 4
    $\begingroup$ But you seem to assume that $|\mathcal P(X)|$ and $|X|^2$ are comparable. Why are they comparable? $\endgroup$
    – Asaf Karagila ♦
    Feb 9, 2018 at 8:59
  • $\begingroup$ @AsafKaragila Yes, we can't say they are comparable in ZF. I didn't assume $\vert \mathcal{P}(X)\vert$ and $\vert X \vert^{2}$ are comparable. I was trying to obtain $\vert \mathcal{P}(X)\vert \leq \vert X \vert^{2}$, which is not possible since there is no injection from $\mathcal{P}(X)$ to $X^{2}$. $\endgroup$
    – Amitayu Banerjee
    Feb 9, 2018 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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