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

Choose-an-Element Proofs: Multiples of 6 Are a Subset of the Evens

IKey Formulas

Statement	Meaning	How to prove it
$S \subseteq T$	$(\forall x)[(x \in S) \to (x \in T)]$	Let $x \in S$ be arbitrary; using only that property, show $x \in T$
$S \ne T$	some element lies in one set but not the other	Exhibit one such element; for the sets $S$ and $T$ below, $2 \in T$ but $2 \notin S$
$S \subsetneq T$	$(S \subseteq T) \wedge (S \ne T)$	Prove the two conjuncts separately

Key Insight: with $S = \{x \in \mathbb{Z} \mid (\exists m \in \mathbb{Z})(x = 6m)\}$ and $T = \{y \in \mathbb{Z} \mid (\exists n \in \mathbb{Z})(y = 2n)\}$ , a subset claim is a "for each" statement, so it needs an arbitrary element; $S \ne T$ is a "there exists" statement, so one element settles it.

IILists Suggest, Proofs Decide

A finite window of two infinite sets can suggest a subset relation, but one counterexample disproves one.

Question Inspect x 12

IIIBuilding the Know-Show Table

The forward process starts from an arbitrary $x \in S$ ; the backward process asks what $x \in T$ requires.

Step 1

Step	Know	Reason
P	$S$ = multiples of $6$ , $T$ = even integers	Hypothesis
P1	Let $x \in S$ .	Choose an arbitrary element of $S$
P2	$(\exists m \in \mathbb{Z})(x = 6m)$	Definition of multiple
P3	$x = 2(3m)$	Algebra, $6 = 2 \cdot 3$
P4	$3m \in \mathbb{Z}$	Closure properties of $\mathbb{Z}$

Q3	$(\exists n \in \mathbb{Z})(x = 2n)$	Steps P3 and P4, $n = 3m$
Q2	$x \in T$	Definition of even
Q1	$(\forall x \in \mathbb{Z})[(x \in S) \to (x \in T)]$	Steps P1 and Q2
Q	$S \subseteq T$	Definition of subset
Step	Show	Reason

IVVenn Conjectures on a Small Universe

Two conjectures from the video, tested on sets you build inside $U = \{1, 2, \dots, 8\}$ .

Conjecture

💡 Each conjecture is proved later in this unit with the choose-an-element method; a finite check, however many cases it covers, cannot replace that proof.

VQuiz Questions

Problem 1 · The First Forward Line

Goal: prove $S \subseteq T$ , where $S$ is the set of multiples of $6$ and $T$ is the set of even integers. Which line should open the forward process?

✅ Correct! The goal

(\forall x)[(x \in S) \to (x \in T)]

calls for an arbitrary element with the given property, here membership in

S

❌ Not quite.

12

is one particular multiple of

6

; what is proved about it says nothing about

18

-6

or any other element of

S

❌ Wrong direction. Starting from an element of

T

is how one would attack

T \subseteq S

, which is false:

2 \in T

but

2 \notin S

❌ Not quite.

S \subseteq T

is the conclusion; assuming it makes the proof circular.

Show solution

By definition, $S \subseteq T$ means $(\forall x \in \mathbb{Z})[(x \in S) \to (x \in T)]$ . A universally quantified conditional is proved by choosing an arbitrary element that satisfies the hypothesis, so the forward process begins with Let $x \in S$ . The only thing we may then use is that $x = 6m$ for some integer $m$ .

Problem 2 · One Example Is Not a Proof

A student writes: " $12 \in S$ because $12 = 6 \cdot 2$ , and $12 \in T$ because $12 = 2 \cdot 6$ . Hence $S \subseteq T$ ." Here $S$ is the set of multiples of $6$ and $T$ the set of even integers. What is wrong with this argument?

✅ Correct!

S \subseteq T

is a statement about every element of

S

, and

S

is infinite; a single example can only suggest it.

❌ Not quite. One element in both sets shows only that

S \cap T

is nonempty; the subset relation needs every element of

S

❌ Wrong direction. That would address

T \subseteq S

, which is false since

2 \in T

and

2 \notin S

❌ Not quite.

12 = 2 \cdot 6

with

6 \in \mathbb{Z}

, so

12

is even and

12 \in T

; each step the student wrote is true.

Show solution

Each sentence the student wrote is true, but the conclusion does not follow. The claim is $(\forall x \in \mathbb{Z})[(x \in S) \to (x \in T)]$ ; verifying it for $x = 12$ covers one case out of infinitely many.

The repair: let $x \in S$ , so $x = 6m$ for some $m \in \mathbb{Z}$ . Then $x = 2(3m)$ and $3m \in \mathbb{Z}$ by closure, so $x$ is even and $x \in T$ . Since $x$ was arbitrary, $S \subseteq T$ .

Problem 3 · Multiples of 9 and Multiples of 3

Given: $A = \{x \in \mathbb{Z} \mid x \text{ is a multiple of } 9\}$ and $B = \{x \in \mathbb{Z} \mid x \text{ is a multiple of } 3\}$ . A proof of $A \subseteq B$ begins: "Let $x \in A$ . Then $x = 9m$ for some $m \in \mathbb{Z}$ ."

Which integer n finishes the proof by giving x = 3n?

Which fact proves that A ≠ B?

✅ Correct!

x = 9m = 3(3m)

with

3m \in \mathbb{Z}

gives

A \subseteq B

, and the single element

3

shows

B \not\subseteq A

, so

A \subsetneq B

❌ Check the product.

3(9m) = 27m

, not

9m

❌ Not quite.

3 \cdot 3 = 9

, which equals

x = 9m

only when

m = 1

;

n

must work for the arbitrary

m

❌ Check the product.

3(6m) = 18m

, not

9m

❌ Not quite. Factor

9 = 3 \cdot 3

and regroup

9m

❌ Not quite. An element in both sets is consistent with

A = B

; you need an element in one set but not the other.

❌ Not quite.

18 = 3 \cdot 6

, so

18 \in B

; the statement

18 \notin B

is false.

❌ Not quite.

A \subseteq B

is true, but it is also true when

A = B

; it cannot show the sets differ.

❌ Not quite. To show two sets are not equal, find one element in one set and not the other.

Show solution

$A \subseteq B$ . Let $x \in A$ , so $x = 9m$ for some $m \in \mathbb{Z}$ . Since $9 = 3 \cdot 3$ ,

x = 9m = 3(3m),

and $3m \in \mathbb{Z}$ by closure. Taking $n = 3m$ gives $x = 3n$ , so $x$ is a multiple of $3$ and $x \in B$ . As $x$ was arbitrary, $A \subseteq B$ .

$A \ne B$ . $3 = 3 \cdot 1$ , so $3 \in B$ ; but $3$ is not a multiple of $9$ , so $3 \notin A$ . Hence $B \not\subseteq A$ , and $A \ne B$ .

Problem 4 · Transfer: Congruence and Odd Integers

Given: $R = \{x \in \mathbb{Z} \mid x \equiv 1 \pmod 4\}$ and $O = \{x \in \mathbb{Z} \mid x \text{ is odd}\}$ . Recall $x \equiv 1 \pmod 4$ means $4 \mid (x - 1)$ , that is, $x = 4k + 1$ for some $k \in \mathbb{Z}$ ; and $x$ is odd means $x = 2n + 1$ for some $n \in \mathbb{Z}$ . Which statement is true?

✅ Correct!

x = 4k + 1 = 2(2k) + 1

with

2k \in \mathbb{Z}

proves

R \subseteq O

, and

3 \in O - R

proves

R \ne O

❌ Not quite.

3

is odd, but

3 - 1 = 2

is not divisible by

4

, so

3 \in O

and

3 \notin R

❌ Reversed.

3 \in O

but

3 \notin R

, so

O \not\subseteq R

; and every

x = 4k + 1

is odd, so

R \subseteq O

❌ Not quite. Choose an arbitrary

x \in R

x = 4k + 1 = 2(2k) + 1

, which is odd, so

R \subseteq O

Show solution

$R \subseteq O$ . Let $x \in R$ . Then $4 \mid (x - 1)$ , so $x - 1 = 4k$ for some $k \in \mathbb{Z}$ , and

x = 4k + 1 = 2(2k) + 1.

By closure $2k \in \mathbb{Z}$ , so with $n = 2k$ we have $x = 2n + 1$ : $x$ is odd and $x \in O$ . Since $x$ was arbitrary, $R \subseteq O$ .

$R \ne O$ . $3 = 2 \cdot 1 + 1$ is odd, so $3 \in O$ ; but $3 - 1 = 2$ and $4 \nmid 2$ , so $3 \notin R$ .

Together, $R \subsetneq O$ . (Negative elements behave the same way: $-3 \in R$ since $-3 - 1 = -4$ , while $-1 \in O - R$ .)

Solved: 0 / 4