# Small set theory question from Munkres

I'm suppose to translate the following sets into $A$, $B$, and $C$ using $\cap$, $\cup$, and $-$.

$$F=\{ x : x \in A \text{ and } (x \in B \implies x \in C)\}$$

My first attempt was: $$F= A \cap (B \cap C)$$.

But my worry is about everything within the parentheses. I'm aware that $$B \cap C=\{x : x \in B\} \text{ and } \{x : x \in C\}.$$ This is not an implication.

-
Can you just write $B\Rightarrow C$? E.g. using the logic formulas for $b\to c$ via $\wedge$ and $\vee$? – Ilya Jan 16 '13 at 9:50
I'm not sure I follow. Would $B \rightarrow C$ require an and or or? – emka Jan 16 '13 at 9:58
Well, what is the definition of $B\rightarrow C$ that you have? – Ilya Jan 16 '13 at 9:58

## 2 Answers

Edit: I've rewritten my answer because I think I aimed it at a different level when I didn't really need to.

Consider the definition of $F$: $$F = \left\{ x : x \in A \text{ and if } x \in B \text{ then } x \in C \right\}$$ If we're to have $x \in F$ then we must certainly have $x \in A$, since otherwise the condition isn't satisfied. So we know that $F \subseteq A$.

This means that we obtain $F$ by throwing out some elements of $A$ $-$ namely, those elements which don't satisfy the condition.

Which elements do we throw out? Precisely those which are in $B$ but not in $C$. Since if an element is in $B$ but not $C$ then $x \in B \to x \in C$ isn't satisfied (and these are the only elements for which this condition isn't satisfied).

So we need to throw out $B - C$. That is, $F = A - (B - C)$.

-
Should it be $A \cap (B-C)$? I ask this because in order for $x \in F$ it has to be in both $A$ and $B-C$. At least that is how I read it. – emka Jan 16 '13 at 10:42
@emka: No. If $x \in B-C$ then $x \in B$ but $x \not \in C$; but we need $x \in B \to x \in C$, so if $x \in F$ and $x \in B$, then $x$ has to lie in $C$! And indeed, we don't even need $x \in B$ for the condition to hold: we could have $x \in C$ and $x \not \in B$, for example (as long as $x \in A$). – Clive Newstead Jan 16 '13 at 11:41
More concretely, let $A$ be the set of integers, $B$ be the set of even integers and $C$ be the set of multiples of $3$. Then a 'thing' is in $F$ if it is an integer and whenever it is even it is also a multiple of $3$... so $F$ is the set consisting of all the odd integers and those even integers which are multiples of $3$ (i.e. multiples of $6$). This is the same as taking the set of all integers and throwing out the even integers which are not multiples of $3$. – Clive Newstead Jan 16 '13 at 11:44

$p\implies q$ is equivalent to $\neg p\vee q$, so $$x\in A\wedge(x\in B \implies x\in C)$$ is equivalent to $$x\in A\wedge(x\notin B \vee x\in C)$$ Also we have that $\neg\neg p\equiv p$, so we can write it as $$x\in A\wedge \neg(\neg(x\notin B\vee x\in C))$$ and by De Morgan's laws $$x\in A\wedge\neg(x\in B \wedge x\notin C)$$ Finally $(x\in A\wedge x\notin B)\equiv x\in(A\cap B)$, and applying it twice we get $$x\in A\smallsetminus(B\smallsetminus C)$$hence $F=A\smallsetminus(B\smallsetminus C)$

-