# 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.

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

2.$\displaystyle \exists x. (x \in H \implies x \in B) \wedge (x \notin E)$
Answer: $\displaystyle (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: $\displaystyle 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 $\displaystyle 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, $\displaystyle A=\{x\mid P(x)\}$ and $\displaystyle B=\{x\mid Q(x)\}$. The set A is called the extension of property P and similarly for B and Q. Then $\displaystyle A\cap B=\{x\mid P(x)\land Q(x)\}$, $\displaystyle A\cup B=\{x\mid P(x)\lor Q(x)\}$ and $\displaystyle A'=\{x\mid\neg P(x)\}$ where $\displaystyle \land$, $\displaystyle \lor$ and $\displaystyle \neg$ mean "and," "or," and "not," respectively. So, the laws like De Morgan's carry over from logic to set theory and back: $\displaystyle (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.$\displaystyle \exists x. (x \in H \implies x \in B) \wedge (x \notin E)$
Answer: $\displaystyle (H' \bigcup B) \bigcap E' \neq \emptyset$
It should be clear that H is the extension of the property $\displaystyle x\in H$, i.e., $\displaystyle H=\{x\mid x\in H\}$. Using the fact that $\displaystyle R\implies S=\neg R\lor S$ and the correspondence described above, $\displaystyle \{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 $\displaystyle A\cap B$ (\cap in LaTeX) denotes the intersection of A and B, i.e., the set of common elements. In contrast, $\displaystyle \bigcap A$ denotes the intersection of the elements of A when A is a family of sets. I.e., if $\displaystyle A=\{a_1,\dots,a_n\}$, then $\displaystyle \bigcap A=a_1\cap\dots a_n$. A similar thing holds for $\displaystyle \cup$ (\cup in LaTeX) and $\displaystyle \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 $\displaystyle \exists x: x\in B \wedge x\notin H$

Now think about taking the intersection of B and H compliment, or $\displaystyle 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 $\displaystyle 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 $\displaystyle p \implies q$) is false, or (inclusive!) the consequent (the q) is true. So we want $\displaystyle x \in H$ to be false, which is equivalent to $\displaystyle x \in H'$ being true. The consequent is that $\displaystyle x \in B$. So we can really think about the conditional as being the same as $\displaystyle 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 $\displaystyle (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?