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

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!

• Welcome to MSE! See this post for a guide on how to format math in your posts: meta.math.stackexchange.com/questions/5020/…
– mrp
Commented Mar 5, 2015 at 16:12
• Note that every integer of the form $4c$ can be written either as $8n$ (if $c$ is even), or as $8n+4$ (if $c$ is odd). There are no other options - so $8n+2$ is out of the question. Commented Mar 5, 2015 at 16:25

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.

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?

• I see that 8n+2 cannot be equal to 4m because of the "+2", but how can I formally prove that?
– Mike
Commented Mar 5, 2015 at 16:22
• If you set $8n+2=4m$, and divide by 4, you get $m=2n+\frac{1}{2}$, that is, $m$, an integer, is $2n$, an integer, plus $\frac{1}{2}$, a non-integer, but adding an integer to a non-integer always results in a non-integer. Commented Mar 5, 2015 at 16:24

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.

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$?

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