1
$\begingroup$

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 \begin{equation} X = \{ x \in U : x \in B \cup C \} \end{equation} 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 \begin{equation} A = \{ x \in U : f(x) \in B \hspace{2pt} \wedge \hspace{2pt} g(x) \in C \}, \end{equation}

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$

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

where

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

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?

$\endgroup$
1
$\begingroup$

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)\}.$$

For the second part, it seems your question boils down to whether the complement of pre-image equals the pre-image of the complement, which it does!

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*}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – jodag Sep 12 '16 at 23:13
  • $\begingroup$ That's right. Line (3) is a subset of Line (4) because of what you mentioned. But also mentally justify Line (4) is a subset of Line (3) in order to justify the equality. $\endgroup$ – Alberto Takase Sep 13 '16 at 0:09

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.