Mathematical-Reasoning · Unit 16 · Video 4 · Interactive Practice

Proving a Set Is Empty: Disjoint Sets and Element Chasing

IKey Formulas

Idea	Statement
Disjoint sets	$A$ and $B$ are disjoint $\iff A \cap B = \emptyset$
Proving "If $P$ , then $T = \emptyset$ "	Contrapositive: assume $T \neq \emptyset$ , prove $\neg P$ . Contradiction: assume $P$ and $T \neq \emptyset$ , derive a contradiction.
What the assumption supplies	$T \neq \emptyset \implies$ there exists $x \in T$
Subset test	$A \subseteq B \iff A \cap B^c = \emptyset$ , and since $A - B = A \cap B^c$ , also $A \subseteq B \iff A - B = \emptyset$

Key Insight: An empty set gives you no element to choose, so assume the set is not empty: that assumption hands you an element $x$ , and you chase $x$ to $\neg P$ or to a contradiction. To show $A \not\subseteq B$ , one element with $x \in A$ and $x \notin B$ is enough.

IIA Witness in $A \cap B^c$

An element of $A \cap B^c$ is exactly an element of $A$ outside $B$ , so it decides whether $A \subseteq B$ .

IIICongruence Classes That Never Meet

Are $\{x \in \mathbb{Z} \mid x \equiv a \pmod{12}\}$ and $\{y \in \mathbb{Z} \mid y \equiv b \pmod{8}\}$ disjoint?

a (mod 12) 3 b (mod 8) 2

IVBoth Directions of $A \subseteq B \iff A \cap B^c = \emptyset$

One direction assumes $A \cap B^c \neq \emptyset$ ; the other chooses $x \in A$ and rules out $x \notin B$ .

Direction Step 1

1. Prove the contrapositive: if $A \cap B^c \neq \emptyset$ , then $A \not\subseteq B$ .

2. Assume $A \cap B^c \neq \emptyset$ , and let $x \in A \cap B^c$ .

3. Then $x \in A$ and $x \in B^c$ .

4. Since $x \in B^c$ , we have $x \notin B$ .

5. So $x \in A$ and $x \notin B$ , hence $A \not\subseteq B$ .

1. Assume $A \cap B^c = \emptyset$ .

2. Let $x \in A$ . Either $x \in B$ or $x \notin B$ .

3. Suppose $x \notin B$ . Then $x \in B^c$ , so $x \in A \cap B^c$ .

4. This contradicts $A \cap B^c = \emptyset$ .

5. Therefore $x \in B$ ; since $x$ was any element of $A$ , $A \subseteq B$ .

VQuiz Questions

Problem 1 · The Contrapositive of an Emptiness Claim

Given: a statement of the form "If $P$ , then $T = \emptyset$ ." Which statement is its contrapositive?

✅ Correct! The contrapositive negates both parts and swaps them. Its hypothesis

T \neq \emptyset

is what supplies an element

x \in T

to work with.

❌ That is the converse. It swaps the parts without negating them, and the converse is not logically equivalent to the original statement.

❌ That is the inverse. It negates the parts without swapping them; the inverse is equivalent to the converse, not to the original statement.

❌ Not quite. This keeps

P

as the hypothesis and contradicts the original conclusion; it is false whenever the original statement is true and

P

holds.

Show solution

The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ . Here $Q$ is " $T = \emptyset$ ", so $\neg Q$ is " $T \neq \emptyset$ ", and the contrapositive is

\text{If } T \neq \emptyset, \text{ then } \neg P.

A proof by contrapositive therefore starts by assuming $T \neq \emptyset$ , which gives an element $x \in T$ , and uses $x$ to prove $\neg P$ .

Problem 2 · Different Moduli, Shared Element?

Given: $A = \{x \in \mathbb{Z} \mid x \equiv 5 \pmod{12}\}$ and $B = \{y \in \mathbb{Z} \mid y \equiv 1 \pmod{8}\}$ , where $a \equiv b \pmod{n}$ means $n \mid (a - b)$ . Which statement is true?

✅ Correct!

17 - 5 = 12

and

17 - 1 = 16 = 8 \cdot 2

, so

17

lies in both sets, and one shared element proves

A \cap B \neq \emptyset

❌ Check membership in $B$ .

5 - 1 = 4

, and

8 \nmid 4

, so

5 \notin B

❌ Not quite. That only shows

5 \notin B

. Disjointness is a claim about every element of

A

, and some other element of

A

might still lie in

B

❌ A finite list cannot prove disjointness. Both sets are infinite, and checking

0

15

says nothing about larger integers; continue the lists and

17

appears in both.

Show solution

List elements: $A$ contains $5, 17, 29, \dots$ and $B$ contains $1, 9, 17, 25, \dots$ Check $17$ directly:

17 - 5 = 12 = 12 \cdot 1, \qquad 17 - 1 = 16 = 8 \cdot 2.

So $17 \equiv 5 \pmod{12}$ and $17 \equiv 1 \pmod{8}$ , hence $17 \in A \cap B$ and $A \cap B \neq \emptyset$ : the sets are not disjoint. Different moduli and different residues alone never decide the question; you need either a shared element or a proof that none exists.

Problem 3 · Prove Two Congruence Classes Are Disjoint

Given: $A = \{x \in \mathbb{Z} \mid x \equiv 1 \pmod{6}\}$ and $B = \{y \in \mathbb{Z} \mid y \equiv 4 \pmod{10}\}$ . Prove $A \cap B = \emptyset$ by contradiction.

How does the proof begin?

From $x = 1 + 6m$ and $x = 4 + 10n$ with $m, n \in \mathbb{Z}$ , which line gives the contradiction?

✅ Correct! Assuming the intersection is not empty supplies

x

; the two expressions for

x

force an odd number to equal an even one.

❌ Wrong goal. That is the opening of a proof that

A \subseteq B

. To prove a set is empty there is no element to choose, so assume

A \cap B \neq \emptyset

to get one.

❌ That assumes the conclusion. A proof by contradiction assumes the negation of what you want, and the negation of

A \cap B = \emptyset

A \cap B \neq \emptyset

❌ Checking examples is not a proof.

A

is infinite, and four elements outside

B

say nothing about the rest of

A

❌ $m$ and $n$ are independent. The two integers come from two different divisibility statements, so nothing forces

m = n

; ruling out that one case leaves all the others.

❌ Different moduli prove nothing. For example,

1 \equiv 1 \pmod{6}

and

1 \equiv 1 \pmod{10}

, so the classes of

1

mod

6

and

1

mod

10

1

❌ One element is not enough. This shows only

7 \notin B

; the contradiction must hold for the arbitrary

x \in A \cap B

, not for one chosen element of

A

❌ Not quite. A proof by contradiction of

A \cap B = \emptyset

starts from

A \cap B \neq \emptyset

❌ Not quite. Set the two expressions for

x

equal and compare parities.

Show solution

Assume, to the contrary, that $A \cap B \neq \emptyset$ , and let $x \in A \cap B$ . Then $x \equiv 1 \pmod{6}$ and $x \equiv 4 \pmod{10}$ , so $6 \mid (x - 1)$ and $10 \mid (x - 4)$ . Hence there are integers $m$ and $n$ with

x = 1 + 6m \quad\text{and}\quad x = 4 + 10n.

Setting these equal gives $1 + 6m = 4 + 10n$ , so

3 = 6m - 10n = 2(3m - 5n).

Since $3m - 5n$ is an integer, the right side is even, but $3$ is odd. This contradiction shows $A \cap B = \emptyset$ , so $A$ and $B$ are disjoint.

Problem 4 · Chasing an Element Through Three Sets

Given: $A$ , $B$ , $C$ are subsets of a universal set $U$ . To prove "If $A \subseteq B$ and $B \cap C = \emptyset$ , then $A \cap C = \emptyset$ ," assume $A \subseteq B$ , $B \cap C = \emptyset$ and $A \cap C \neq \emptyset$ , and let $x \in A \cap C$ . Which line finishes the proof?

✅ Correct! The hypothesis

A \subseteq B

carries

x

from

A

into

B

, and

x

is already in

C

, so

x

lands in the set assumed empty.

❌ That step does not follow. From

x \in A

and

A \subseteq B

we get

x \in B

, the opposite of

x \notin B

❌ No contradiction there.

x \in A \cap B

is true here, and it is consistent with

A \subseteq B

; when

A \subseteq B

, every element of

A

is in

A \cap B

❌ That step does not follow.

x \in C - B

would need

x \notin B

, but

x \in A \subseteq B

gives

x \in B

Show solution

Assume $A \subseteq B$ and $B \cap C = \emptyset$ , and suppose, to the contrary, that $A \cap C \neq \emptyset$ . Then there is an element $x \in A \cap C$ , so $x \in A$ and $x \in C$ .

Since $x \in A$ and $A \subseteq B$ , we have $x \in B$ . Together with $x \in C$ , this gives $x \in B \cap C$ , which contradicts $B \cap C = \emptyset$ .

Therefore $A \cap C = \emptyset$ : the sets $A$ and $C$ are disjoint.

Solved: 0 / 4

Proving a Set Is Empty: Disjoint Sets and Element Chasing

IKey Formulas

IIA Witness in A∩BcA \cap B^cA∩Bc

IIICongruence Classes That Never Meet

IVBoth Directions of A⊆B ⟺ A∩Bc=∅A \subseteq B \iff A \cap B^c = \emptysetA⊆B⟺A∩Bc=∅

VQuiz Questions

IIA Witness in $A \cap B^c$

IVBoth Directions of $A \subseteq B \iff A \cap B^c = \emptyset$