Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-13 Teacher: Prof. Musacchio

Proofs Involving Sets

Introduction

Recall (Definition 1.3) that if $A$ and $B$ are sets, then $A \subseteq B$ means that every element of $A$ is also an element of $B$ . In other words, it means if $a \in A$ , then $a \in B$ .
Therefore to prove that $A \subseteq B$ , we just need to prove that the conditional statement “If a ∈ A, then a ∈ B” is true.

Prove that ${x \in Z : 2∣ x} \cap {x \in Z : 9∣ x} \subseteq {x \in Z : 6∣ x}$
- Proof. Suppose $a \in {x \in Z : 2∣ x} \cap {x \in Z : 9∣ x}$ .
- By definition of intersection, this means $a \in {x \in Z : 2∣ x}$ and $a \in {x \in Z : 9∣ x}$ .
- Since $a \in {x \in Z : 2∣ x}$ we know $2∣ a$ , so $a = 2 c$ for some $c \in Z$ .
- Thus a is even. Since $a \in {x \in Z : 9∣ x}$ we know $9∣ a$ , so $a = 9 d$ for some $d \in Z$ .
- As a is even, $a = 9 d$ implies $d$ is even. (Otherwise $a = 9 d$ would be odd.)
- Then $d = 2 e$ for some integer $e$ , and we have $a = 9 d = 9 (2 e) = 6 (3 e)$ .
- From $a = 6 (3 e)$ , we conclude $6∣ a$ , and this means $a \in {x \in Z : 6∣ x}$ .
We have shown that $a \in {x \in Z : 2∣ x} \cap {x \in Z : 9∣ x}$ implies $a \in {x \in Z : 6∣ x}$ , so it follows that ${x \in Z : 2∣ x} \cap {x \in Z : 9∣ x} \subseteq {x \in Z : 6∣ x}$ .