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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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 ♦
    Commented 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
    Commented Feb 9, 2018 at 10:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .