# How to determine the complement when the predicate is not a simple inclusion

I'm given sets defined using set-builder notation and I'm not entirely sure how to take the complement of the set. I ask a general question in Part I, then a related question in a more complicated case that is relevant to the proof I'm trying to construct in Part II.

Part I

I know for set defined in set-builder notation where the predicate is simply an inclusion of the set elements in another set, like $$X = \{ x \in U : x \in B \cup C \}$$ then the complement is \begin{align} X^c &= \{ x \in U : x \in B \cup C \}^c \\ &= \{ x \in U : x \notin B \cup C \} & \text{(this is the definition I've seen)} \\ &= \{ x \in U : \neg(x \in B \cup C) \}. \end{align}

But can I use the negation of the predicate in general to derive the set-builder form of the complement?

For example, let $$A = \{ x \in U : f(x) \in B \hspace{2pt} \wedge \hspace{2pt} g(x) \in C \},$$

then would the complement simply be

\begin{align} A^c &= \{ x \in U : \neg(f(x) \in B \hspace{2pt} \wedge \hspace{2pt} g(x) \in C) \} \\ &= \{ x \in U : f(x) \in B^c \hspace{2pt} \vee \hspace{2pt} g(x) \in C^c \}? \end{align}

Part II

In a more complicated case, if I'm given the following definitions for the inverse of the mapping $f : U \rightarrow V$

$$f^{-1}(X) = \{ f^{-1}(F_v) : F_v \in X \}, \hspace{10pt} X \subseteq 2^{V}$$

where

$$f^{-1}(F_v) = \{ x \in U : f(x) \in F_v \}, \hspace{10pt} F_v \in 2^V.$$

Then given some specific $A \in f^{-1}(X)$ where $X \subseteq 2^V$, what would the set builder form of $A^c$ look like?

I was thinking that I could say, from the definition of $f^{-1}(X)$, that $A$ could be expressed in set-builder notation as follows.

Because $A \in f^{-1}(X)$ there must be some $F_v \in X$ such that

\begin{align} A &= f^{-1}(F_v) \\ &= \{ x \in U : f(x) \in F_v \}. \end{align}

Using the same $F_v$, if my assumption about how to take the complement of a set in set-builder notation is correct, then I could then write $A^c$ as

\begin{align} A^c &= (f^{-1}(F_v))^c \\ &= \{ x \in U : f(x) \in F_v \}^c \\ &= \{ x \in U : \neg(f(x) \in F_v) \} \\ &= \{ x \in U : f(x) \in F_v^c \} \\ &= f^{-1}(F_v^c). \end{align}

Is this correct?

For the first part, you are correct. If I define some subset $A$ of a fixed "universal" set $U$ by $$A:=\{x\in U:\phi(x)\}$$ where $\phi$ is some set theory formula, then $$A^{\mathsf{c}}:=U\setminus A=\{x\in U:\neg\phi(x)\}.$$
Proposition Let $X$ and $Y$ be sets. Let $f:X\to Y$. For each $B\in\mathscr{P}\left(Y\right)$, $f^{-1}\left(Y\setminus B\right)=X\setminus f^{-1}\left(B\right)$.
Proof. Let $B\in\mathscr{P}\left(Y\right)$ be arbitrary. \begin{align*} f^{-1}\left(Y\setminus B\right)&=\left\{z\in X:f\left(z\right)\in\left(Y\setminus B\right)\right\}\\ &=\left\{z\in X:f\left(z\right)\in \left\{y\in Y:y\notin B\right\}\right\}\\ &=\left\{z\in X:f\left(z\right)\notin B\right\}\\ &=\left\{z\in X:z\notin f^{-1}\left(B\right)\right\}\\ &=X\setminus f^{-1}\left(B\right). \end{align*}
• Very interesting thank you Alberto. Just a quick question In your proof going from line 3 to line 4. This is based on the observation that if $f(z) \notin B$ then, from the definition of $f^{-1}(B)$ we know that $z \notin f^{-1}(B)$ right? – jodag Sep 12 '16 at 23:13