Suppose we have a set $A = \{x : \psi(x)\}$ where $\psi$ is a set theoretic formula where the only (free) variable is $x$.

Is it correct to describe the complement of $A$ in the following way?

$A^c = \{x : \sim \psi(x)\}$

My intuition is that this is the case, but I am not sure if there are some degenerate cases where this breaks.

I think this is a basic exercise in logic, and follows somehow from the following:

$A^c = \{x: x \not \in A\} = \{x: \sim (x \in A)\} = \dots$

  • 1
    $\begingroup$ No. Unrestricted comprehensions are banned. If you define the complement in respect to another set, this could be valid. Both your definitions of $A$ and $A^c$, as written, are not well-defined in ZFC. $\endgroup$ – Don Thousand Feb 5 '19 at 18:06
  • $\begingroup$ The degenerate case is $\psi(x)$ defined as $x \notin x$. Then you get Russell's paradox. en.wikipedia.org/wiki/Russell%27s_paradox $\endgroup$ – user4894 Feb 5 '19 at 18:32
  • $\begingroup$ Yes, this is the correct description, assuming that all sets are contained in some given "universe". $\endgroup$ – Andrés E. Caicedo Feb 5 '19 at 21:50

In this answer I assume you're interested in ZF; it probably won't wholly apply to theories where comprehension works differently or where "class" means something different. Specifically, I'll follow Takeuti and Zaring (Introduction to Axiomatic Set Theory, second edition, Springer 1982, Chapter 4 -- q. v. for a more careful treatment of set builder notation in ZF than is usually given) and say that $A$ is a set iff $\exists x \; x = A$, and that $A$ is a proper class otherwise. (As noted in the comments, the usual example of a proper class is $\{x:x\not\in x\} = \{x:x = x\} =: V$.)

The answer to the question "Is this definition of X correct?" depends on what you want to follow from the definition -- what you want $X$ to mean. What do we want "complement" to mean? We probably want each set to have exactly one complement which is also a set. If we define "complement" in the way you suggest, that's not going to happen. For let $A^C := \{x:x \not\in A\}$. Then whenever $A$ is a set, $A^C$ is a proper class. (Otherwise, by Pairing and Union, $A \cup A^C = V$ would be a set.) Or, in other words, whenever $A$ is a set, there is no set which is the complement of $A$. We didn't get anything we wanted.

As already noted in the comments, we can do better by saying that whenever we say "complement" we mean "complement relative to $s$", where $s$ is some set: $A^C = \{x : x \not\in A \land x \in s\}.$ This is a function on the powerset of $s$, in the sense that $$\forall x \in \mathcal{P}(s)\exists! y \; y = x^C$$ is provable in ZF; we got all we wanted. But it's worth noting that we didn't do better by giving a better definition of "complement"; rather we did better by stipulating that "complement" is really an abbreviation, and that what it abbreviates changes with context.


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.