# Can the non-existence of absolute complements be proved without using the axiom of unions?

In Zermelo-Fraenkel set theory, there is no universal set, and to prove that, you need hardly any of the theory, just the axiom of specification.

Also in ZF, no set has an absolute complement, and that follows easily from the non-existence of the universal set, and the axiom of unions.

Question: Can we prove the non-existence of absolute complements in a subset of ZF, without the axiom of unions?

• I suppose you mean the statement "for every set, there does not exist the complementary set"? – Wojowu Jun 22 '17 at 21:47
• Yes, that is an equivalent statement. – A. Burrell Jun 22 '17 at 22:14

The axioms of Pairing and Separation are enough to reproduce Russell's Paradox indirectly:

Suppose for a contradiction that there are $A \cup B = \mathbf V$ and $A\cap B=\varnothing$.

Let $x\in\!\!\in y$ be an abbreviation for $\exists z(x\in z\land z\in y)$ and consider $$A' = \{x\in A\mid \neg(x\in\!\!\in x)\} \qquad B' = \{x\in B\mid \neg(x\in\!\!\in x)\}$$ and let $P=\{A',B'\}$.

Assume without loss of generality that $P \in A$, $P\notin B$ (otherwise just swap $A$ and $B$).

Now if $P\in A'$ then $P\in A'\in P$, so $P$ should not have been in $A'$.

Therefore $P\notin A'$, but this requires that $P\in\!\!\in P$, or in other words $P$ is an element of one of its two elements. But we just concluded $P\notin A'$, and $P\notin B'$ because $P\notin B$.

Either way we have a contradiction.

• I had a feeling this could be done, i.e. avoiding Regularity (Foundation) and I spent a little time trying to find a way to do it ( without success ). – DanielWainfleet Jun 23 '17 at 0:03
• Very nice. This generalizes to show that there cannot exist a set $X$ whose union is the universe (assuming Replacement to get that the analogue of your $P'$ is a set). – Eric Wofsey Jun 23 '17 at 0:52

Yes; you can prove this from just Pairing and Regularity. Suppose $X$ is a set and the complement $Y$ of $X$ is also a set. By Pairing, $\{X\}$, $\{Y\}$, and $\{X,Y\}$ are sets. Regularity for $\{X\}$ says that $X\not\in X$ and Regularity for $\{Y\}$ says that $Y\not\in Y$. Since $X$ and $Y$ are complements, $X\in Y$ and $Y\in X$. But this now violates Regularity for $\{X,Y\}$.