Proof by contradiction that $B \cap C$ is an empty set

Question

Let $B$ and $C$ be sets such that $$B = \{b \in\mathbb{Z} \mid b = 8n+2 \text{ for some } n\in\mathbb{Z}\}$$

$$C = \{c \in\mathbb{Z} \mid c = 4m \text{ for some } m\in\mathbb{Z}\}$$

Prove by contradiction that $B ∩ C = \emptyset$.

I know that I have to first negate $B ∩ C$, however I never learned how to do this. Can somebody please walk me through the negation and then proof?

Thank you!

Answer 1

Negation of the fact $B \cap C = \emptyset$ is that there exists $a$ such that $a \in B \cap C $. Assume that such $a$ exists, then from definitions of $B$ and $C$ there exist integers $m,n$ such that $a=8n+2=4m$, but this implies that $m=2n+0.5$ and this is contradiction with $m$ being integer.

Answer 2

You actually don't need to negate $B\cap C$, but rather the statement that $B\cap C=\emptyset$, which would just be $B\cap C\ne\emptyset$. This would mean that intersection contains some element. Then let $x\in B\cap C$. Then $x\in B$ and $x\in C$. This means that $x=8n+2$ and $x=4m$, for some $m,n\in\mathbb{Z}$. Can you find the contradiction from there?

Answer 3

Suppose that $B \cap C$ is nonempty.

Then there exists an $x \in B \cap C$.

Then, $x \in B$ and $x \in C$.

Thus, $x = 8n + 2$ and $x = 4m$ for some integers $m, n$.

Note that this means that: $8n + 2 = 4m$ $\Rightarrow 4n + 1 = 4m$ $\Rightarrow 2(2n) + 1 = 2(2m)$

We have a contradiction, as the left side is odd by definition, while the right side is even by definition. An odd number cannot be equal to an even number.

Thus, $B \cap C$ is empty.

Answer 4

Be careful here because "negate" has a slightly different meaning than what you are trying to do.

To set up a proof by contradiction, you should do the following:

1. Assume your hypothesis is true
2. Assume your conclusion is false
3. Derive a contradiction by finding logical progression which contradicts your hypothesis

Specifically for this problem, you should:

1. Assume $B = \{b \in\mathbb{Z} \mid b = 8n+2 \text{ for some } n\in\mathbb{Z}\}$ and $ C = \{c \in\mathbb{Z} \mid c = 4m \text{ for some } m\in\mathbb{Z}\}$

2. Suppose to the contrary that $B ∩ C \not = \emptyset$

3. Derive a contradiction. $B ∩ C \not = \emptyset$ means that there is some element in both $B$ and $C$. So, $\exists x \ s.t. \ x = 8n + 2 = 4m$. Now proceed with regular algebra as you would with any usual equation. Dividing both sides by $8$ gives you $m = 2n + \frac 12$, which contradicts the conditions of set $C$ that $m$ must be an integer.

If you are ever stuck on how to proceed, try simplifying the equation further. Think about all the conditions of your hypothesis and try different ways to contradict one of them. For example, your thought process might be: okay, we know $m \in \Bbb Z$, how can I manipulate the equation to show $m \not \in \Bbb Z$?

Answer 5

Suppose that $B \cap C \neq \emptyset$ . That means we have an element in $B \cap C$. For example, $$\exists x \in B\cap C \Rightarrow x \in B \land x \in C$$ $$\Rightarrow \exists n,m\in \mathbb{Z} \;\; (x = 8n+2 \land x = 4m)$$ $$\Rightarrow 8n + 2 = 4m \Rightarrow 4n + 1 = 2m$$ $4n$ is even, $1$ is odd. And we know that sum of two odd and even numbers is odd. But here we have $2m$ and this is even. So we have a contradiction. Thus $B \cap C = \emptyset$.