# Thread: Translating to set notation with existence.

1. ## Translating to set notation with existence.

Hey all,
I understand basic set notation, but I'm having trouble understanding these 2 examples which deal with existence and translating them to set notation. If someone could explain them thoroughly , I'd appreciate it.
Thanks in advance.

1.There are some B that are not H.
Answer: $B \bigcap H' \neq \emptyset$

2. $\exists x. (x \in H \implies x \in B) \wedge (x \notin E)$
Answer: $(H' \bigcup B) \bigcap E' \neq \emptyset$

2. ## Re: Translating to set notation with existence.

What exactly do you need to do: translate these statements to set notation or explain why the first line and the second line say the same thing?

Originally Posted by cynlix
1.There are some B that are not H.
Answer: $B \bigcap H' \neq \emptyset$
Let B be the set of male cats and H be the set of white cats. Then the complement of H, i.e., H', is the set of non-white cats, so $B\cap H'$ is the set of male non-white cats. Saying that this set is nonempty is the same as saying that there exists a male cat that is non-white.

In general, there is a direct correspondence between set operations on (the extensions of) properties and logical connectives. Let A be the set of objects having a property P and B be the set of objects having a property Q. In set notation, $A=\{x\mid P(x)\}$ and $B=\{x\mid Q(x)\}$. The set A is called the extension of property P and similarly for B and Q. Then $A\cap B=\{x\mid P(x)\land Q(x)\}$, $A\cup B=\{x\mid P(x)\lor Q(x)\}$ and $A'=\{x\mid\neg P(x)\}$ where $\land$, $\lor$ and $\neg$ mean "and," "or," and "not," respectively. So, the laws like De Morgan's carry over from logic to set theory and back: $(A\cap B)'=A'\cup B'=\{x\mid\neg(P(x)\land Q(x))\}=\{x\mid\neg P(x)\lor \neg Q(x)\}$.

Originally Posted by cynlix
2. $\exists x. (x \in H \implies x \in B) \wedge (x \notin E)$
Answer: $(H' \bigcup B) \bigcap E' \neq \emptyset$
It should be clear that H is the extension of the property $x\in H$, i.e., $H=\{x\mid x\in H\}$. Using the fact that $R\implies S=\neg R\lor S$ and the correspondence described above, $\{x\mid (x\in H\implies x\in B)\land x\notin E\}=\{x\mid (x\notin H\lor x\in B)\land x\notin E\}=(H'\cup B)\cap E'$.

Note that $A\cap B$ (\cap in LaTeX) denotes the intersection of A and B, i.e., the set of common elements. In contrast, $\bigcap A$ denotes the intersection of the elements of A when A is a family of sets. I.e., if $A=\{a_1,\dots,a_n\}$, then $\bigcap A=a_1\cap\dots a_n$. A similar thing holds for $\cup$ (\cup in LaTeX) and $\bigcup$.

3. ## Re: Translating to set notation with existence.

Alrighty, let me see if I can help you make some sense out of these.

For the first one, you can think of as $\exists x: x\in B \wedge x\notin H$

Now think about taking the intersection of B and H compliment, or $B \bigcap H'$. Will it be empty? The answer is no. We defined the problem by saying that there was something in both! So we can write $A \bigcap H' \neq \emptyset$

If you understand that, then the second one can be done in a similar manner.

Lets ask ourselves what x would satisfy that conditional. We know that a conditional is satisfied when either the antecedent ( p in $p \implies q$) is false, or (inclusive!) the consequent (the q) is true. So we want $x \in H$ to be false, which is equivalent to $x \in H'$ being true. The consequent is that $x \in B$. So we can really think about the conditional as being the same as $H' \bigcup B$ Now consider the second part of the intial statement. It tells us that there is an x which satisifies the first conditon AND is also a member of E'. so if we take the original statement and intersect it with E, we get $(H' \bigcup B ) \bigcap E' \neq \emptyset$. Why? Because we said that there is an x that satisfies those conditions, so that set cannot be empty.

Does that make sense, or am I just rambling?