# What fragments of ZF are consistent with a set being equal in size to its power set?

What examples of fragments of ZF are consistent with: $$\exists x \exists f\, (f\colon x \to P(x) \wedge f \text{ is bijective})$$ and are not too weak, ideally with at least the consistency strength of PA?

• The fragment that I know of is the theory axiomatized by Extensionality, Singletons, Boolean union, Power, Predicative stratified instances of Separation, and Infinity (in the form $\exists x\, (x \text{ is infinite})$)

• Another theory has the same axioms above plus set union, but with separation restricted to stratified formulas with three types.

• Another theory has all the above axioms and allows all stratified instances of separation, but asserts Extensionality only for non-empty objects. This theory is not known to prove a set that is equal to its power in size, but is consistent with all types of inequality of size between a set and its power. The references for this are known to people working with NF(U).

What other known fragments of ZF are not too weak, and yet are consistent with a set being equal to its power set in size?

• It will have to be weak to keep from forming the set of members y of x which do not belong to f(y), while still having the power to express your notion. Gerhard "Not Sure Of The Utility" Paseman, 2018.08.23. – Gerhard Paseman Aug 23 '18 at 19:52
• @GerhardPaseman if for example Con(NF) is proved then we can have a fragment that can interpret $\omega$_order arithmetic and yet be consistent with this notion. To me any fragment near the strength of $PA$ is not to be considered weak. – Zuhair Al-Johar Aug 23 '18 at 21:26
• You really should use the lo.logic tag, this is the second time I've added it to a question you asked in this area. Also, use \text as a wrapper for when you want text inside a math environment – David Roberts Aug 23 '18 at 22:29
• @DavidRoberts thanks – Zuhair Al-Johar Aug 23 '18 at 23:25
• @MattF. your comment is not correct. An injection form P(N) to N is not consistent with IZF. The statement that there can be no injection from P(A) to A for any A follows from Cantor's argument, which is purely constructive. Perhaps, you have confused P(N) with $N^N$, or $2^N$... – Michal R. Przybylek Aug 24 '18 at 22:29

Your question is related to Lawvere's fixed point theorem, about which I wrote a blog post a while ago. It takes next to nothing to prove the following theorem:

Theorem (Lawvere): If $e : A \to B^A$ be a surjection. Then every map $f : B \to B$ has a fixed point.

Proof. Consider the map $g : A \to B$ defined by $g(x) = f(e(x)(x))$. Because $e$ is a surjection, there is $a \in A$ such that $e(a) = g$. Now we have $e(a)(a) = g(a) = f(e(a)(a))$, therefore $e(a)(a)$ is a fixed point of $f$. QED.

It will be difficult to find a set theory which admits sets of functions but does not allow you to prove the above theorem. The point is that the theorem immediately implies Cantor's theorem.

Corollary: There is no surjection $A \to 2^A$.

Proof. The map $f : 2 \to 2$ defined by $f(0) = 1$ and $f(1) = 0$ has no fixed points, therefore we cannot have a surjection $A \to 2^A$. QED.

Observe that all of what we have said so far is intuitionistically valid, so it applies to classical as well as intuitionistic set theory. (Caveat: intuitionistically the powerset of $A$ is not $2^A$ but $\Omega^A$ where $\Omega = \mathcal{P}(1)$, the powerset of the singleton; nevertheless, the corollary still works because the complement/negation map $\Omega \to \Omega$ has no fixed points.)

The above arguments can be made as soon as we have the ability to form sets of functions. So I wonder how you manage to prove that there is a bijection between a set and its power-set in your fragments. Are you quite sure you can speak about functions in a normal way? Or to put it another way, which part of the proof of Lawvere's theorem doesn't work in your fragments of set theory?

As far as I am concerned, Lawvere's and Cantor's theorems are completely independent of set theory. They are basic facts about functions.

• Note that this is true even in NF as long as you look at it categorically. The reason you can have $V=\mathcal{P}(V)$ is because $\mathcal{P}(V)$ is not a categorical power object of $V$; it's a power object of $\{\{x\}:x\in V\}$. NF's stratification requirement prevents us from forming the necessary universal maps to make it the power object of $V$. Something similar will probably be going on in any such fragment: your "power sets" will lack a certain universal property. – Malice Vidrine Aug 25 '18 at 22:30
• The definition of map $g$ is not stratified, you have $e(x)(x)$ so $x$ will receive the same type as $e(x)$ since $e(x)$ is the image of $x$ under $e$ and also $x$ appears one type lower than $e(x)$ since it is the argument of $e(x)$, so that won't work in the stratified fragments that I've mentioned. – Zuhair Al-Johar Aug 26 '18 at 2:55
• as about the ability of the fragments that I've mentioned, the last one which is the one having non-extensionals is as strong as $\omega$-order arithmetic. I think (I'm not sure) that we can have much stronger fragments and yet compatible with existence of a set that is equipotent with its power. – Zuhair Al-Johar Aug 26 '18 at 3:00
• I am not familiar with NF, so thanks for explaining where things fail to work. From a category-theoretic point of view I find it odd that we'd still call something "function space" or "powerset" if it does not behave like one. – Andrej Bauer Aug 26 '18 at 8:53