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?

  • $\begingroup$ I suppose you mean the statement "for every set, there does not exist the complementary set"? $\endgroup$ – Wojowu Jun 22 '17 at 21:47
  • 1
    $\begingroup$ Yes, that is an equivalent statement. $\endgroup$ – 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.

  • $\begingroup$ 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 ). $\endgroup$ – DanielWainfleet Jun 23 '17 at 0:03
  • 2
    $\begingroup$ 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). $\endgroup$ – 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\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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