Sets Lecture 8 Robb T. Koether Mon, Feb 15, 2016

Sets
Lecture 8
Robb T. Koether
Hampden-Sydney College
Mon, Feb 15, 2016
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
1 / 21
Outline
1
Sets
2
Some LATEX
3
Proofs Involving Sets
4
Assignment
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
2 / 21
Outline
1
Sets
2
Some LATEX
3
Proofs Involving Sets
4
Assignment
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
3 / 21
Set Builder Notation
Set builder notation defines a set by using the following form.
S = {x ∈ A | x satisfies a specific condition}.
Examples
The set of all positive real numbers.
The set of all even integers.
The set of all real solutions to the equation x 5 + x − 1 = 0.
The set of all integer solutions to the equation x 5 + x − 1 = 0.
The set of all primes.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
4 / 21
Subsets
Definition (Subset)
A set A is a subset of a set B, denoted A ⊆ B, if every element of A is
also an element of B.
Definition (Proper Subset)
A set A is a proper subset of a set B, denoted A ⊂ B, if every element
of A is also an element of B, but A 6= B.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
5 / 21
Subsets
The statement A ⊆ B can be expressed as a conditional:
x ∈ A =⇒ x ∈ B.
The difference between “subset” and “proper subset” is analogous
to the difference between ≤ and <.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
6 / 21
The Empty Set
Definition (The Empty Set)
The empty set, or null set, denoted ∅ or {}, is the set that contains no
elements.
The empty set is a subset of every set.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
7 / 21
Set Operations
Let U be the universe of discourse.
Definition (Intersection)
The intersection of sets A and B is the set
A ∩ B = {x ∈ U | x ∈ A and x ∈ B}.
Definition (Union)
The union of sets A and B is the set
A ∪ B = {x ∈ U | x ∈ A or x ∈ B}.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
8 / 21
Set Operations
Let U be the universe of discourse.
Definition (Complement)
The complement of a set A is the set
Ac = {x ∈ U | x ∈
/ A}.
Definition (Set Difference)
The difference of sets A and B is the set
A \ B = {x ∈ U | x ∈ A and x ∈
/ B}.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
9 / 21
Outline
1
Sets
2
Some LATEX
3
Proofs Involving Sets
4
Assignment
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
10 / 21
Some LATEX
Math
Set builder
Set builder
Set builder
Subset
Proper subset
Empty set (ugly)
Empty set (pretty)
Union
Intersection
Complement
Set difference
Robb T. Koether (Hampden-Sydney College)
LATEX
\{
\}
\mid
\subseteq
\subset
\emptyset
\varnothing
\cup
\cap
ˆc
\setminus
Sets
Symbol
{
}
|
⊆
⊂
∅
∅
∪
∩
c
\
Mon, Feb 15, 2016
11 / 21
Some LATEX
The code
A\setminus B\subseteq(A\cap B)ˆc
will produce
A \ B ⊆ (A ∩ B)c .
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
12 / 21
Outline
1
Sets
2
Some LATEX
3
Proofs Involving Sets
4
Assignment
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
13 / 21
Proofs Involving Sets
Theorem
For any sets A, B, and C, if A ⊆ B, then A ∩ C ⊆ B ∩ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
14 / 21
Proof.
Let A, B, and C be sets.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Let x ∈ A ∩ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Let x ∈ A ∩ C.
Then x ∈ A and x ∈ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Let x ∈ A ∩ C.
Then x ∈ A and x ∈ C.
Because A ⊆ B, it follows that x ∈ B.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Let x ∈ A ∩ C.
Then x ∈ A and x ∈ C.
Because A ⊆ B, it follows that x ∈ B.
Therefore, x ∈ B ∩ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proof.
Let A, B, and C be sets.
Suppose that A ⊆ B.
Let x ∈ A ∩ C.
Then x ∈ A and x ∈ C.
Because A ⊆ B, it follows that x ∈ B.
Therefore, x ∈ B ∩ C.
Thus, A ∩ C ⊆ B ∩ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
15 / 21
Proofs Involving Sets
Theorem
For any sets A, B, and C,
(A \ C) ∪ (B \ C) ⊆ (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
16 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Then x ∈ A \ C or x ∈ B \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Then x ∈ A \ C or x ∈ B \ C.
Case 1: Suppose x ∈ A \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Then x ∈ A \ C or x ∈ B \ C.
Case 1: Suppose x ∈ A \ C.
Then x ∈ A and x ∈
/ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Then x ∈ A \ C or x ∈ B \ C.
Case 1: Suppose x ∈ A \ C.
Then x ∈ A and x ∈
/ C.
Because x ∈ A, then x ∈ A ∪ B.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Let A, B, and C be sets.
Let x ∈ (A \ C) ∪ (B \ C).
Then x ∈ A \ C or x ∈ B \ C.
Case 1: Suppose x ∈ A \ C.
Then x ∈ A and x ∈
/ C.
Because x ∈ A, then x ∈ A ∪ B.
Therefore, x ∈ (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
17 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Then x ∈ B and x ∈
/ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Then x ∈ B and x ∈
/ C.
Because x ∈ B, then x ∈ A ∪ B.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Then x ∈ B and x ∈
/ C.
Because x ∈ B, then x ∈ A ∪ B.
Therefore, x ∈ (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Then x ∈ B and x ∈
/ C.
Because x ∈ B, then x ∈ A ∪ B.
Therefore, x ∈ (A ∪ B) \ C.
Therefore, x ∈ (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Proof.
Case 2: Suppose x ∈ B \ C.
Then x ∈ B and x ∈
/ C.
Because x ∈ B, then x ∈ A ∪ B.
Therefore, x ∈ (A ∪ B) \ C.
Therefore, x ∈ (A ∪ B) \ C.
If follows that (A \ C) ∪ (B \ C) ⊆ (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
18 / 21
Proofs Involving Sets
Now prove the converse.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
19 / 21
Proofs Involving Sets
Now prove the converse.
That is, prove that
(A ∪ B) \ C ⊆ (A \ C) ∪ (B \ C).
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
19 / 21
Proofs Involving Sets
Now prove the converse.
That is, prove that
(A ∪ B) \ C ⊆ (A \ C) ∪ (B \ C).
Why is that the “converse?”
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
19 / 21
Proofs Involving Sets
Now prove the converse.
That is, prove that
(A ∪ B) \ C ⊆ (A \ C) ∪ (B \ C).
Why is that the “converse?”
After proving the converse, it follows that
(A \ C) ∪ (B \ C) = (A ∪ B) \ C.
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
19 / 21
Outline
1
Sets
2
Some LATEX
3
Proofs Involving Sets
4
Assignment
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
20 / 21
Assignment
Homework
Presentations this week:
2.12, 2.13, 2.25, 2.26, 2.30, 2.31, 2.33.
For the following two statements, (1) write the negation of the
statement, (2) determine which statement (original or negation) is
true, and (3) prove the one that is true. Then turn in your proofs on
Wednesday, February 17.
(∀a ∈ Z) (∀b ∈ Z) ((ab is even ) =⇒ ((a is even ) ∨ (b is even )))
(∀a ∈ Z) (∃b ∈ Z) (∃b ∈ Z) (a = 2b + 3c)
Robb T. Koether (Hampden-Sydney College)
Sets
Mon, Feb 15, 2016
21 / 21