Discrete Mathematics

Predicates and Sets

H. Turgut Uyar Ayşegül Gençata Yayımlı Emre Harmancı

2001-2013
License

2001-2013
c T. Uyar, A. Yayımlı, E. Harmancı

You are free:

to Share – to copy, distribute and transmit the work
to Remix – to adapt the work
Under the following conditions:
Attribution – You must attribute the work in the manner specified by the author or licensor (but not in any
way that suggests that they endorse you or your use of the work).
Noncommercial – You may not use this work for commercial purposes.
Share Alike – If you alter, transform, or build upon this work, you may distribute the resulting work only
under the same or similar license to this one.

Legal code (the full license):

http://creativecommons.org/licenses/by-nc-sa/3.0/
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Predicate

Definition
predicate (or open statement): a declarative sentence which
contains one or more variables, and
is not a proposition, but
becomes a proposition when the variables in it
are replaced by certain allowable choices
Universe of Discourse

Definition
universe of discourse: U
set of allowable choices

examples:
Z: integers
N: natural numbers
Z+ : positive integers
Q: rational numbers
R: real numbers
C: complex numbers
Universe of Discourse

Definition
universe of discourse: U
set of allowable choices

examples:
Z: integers
N: natural numbers
Z+ : positive integers
Q: rational numbers
R: real numbers
C: complex numbers
Predicate Examples

Example
U =N
p(x): x + 2 is an even integer

p(5): F
p(8): T

¬p(x): x + 2 is not an even integer

Example
U =N
q(x, y ): x + y and x − 2y are even integers

q(11, 3): F , q(14, 4): T

Predicate Examples

Example
U =N
p(x): x + 2 is an even integer

p(5): F
p(8): T

¬p(x): x + 2 is not an even integer

Example
U =N
q(x, y ): x + y and x − 2y are even integers

q(11, 3): F , q(14, 4): T

Predicate Examples

Example
U =N
p(x): x + 2 is an even integer

p(5): F
p(8): T

¬p(x): x + 2 is not an even integer

Example
U =N
q(x, y ): x + y and x − 2y are even integers

q(11, 3): F , q(14, 4): T

Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Quantifiers

Definition Definition
existential quantifier: universal quantifier:
predicate is true for some values predicate is true for all values
symbol: ∃ symbol: ∀
read: there exists read: for all

symbol: ∃!
read: there exists only one
Quantifiers

Definition Definition
existential quantifier: universal quantifier:
predicate is true for some values predicate is true for all values
symbol: ∃ symbol: ∀
read: there exists read: for all

symbol: ∃!
read: there exists only one
Quantifiers

Definition Definition
existential quantifier: universal quantifier:
predicate is true for some values predicate is true for all values
symbol: ∃ symbol: ∀
read: there exists read: for all

symbol: ∃!
read: there exists only one
Quantifiers

existential quantifier
U = {x1 , x2 , . . . , xn }
∃x p(x) ≡ p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )
p(x) is true for some x

universal quantifier
U = {x1 , x2 , . . . , xn }
∀x p(x) ≡ p(x1 ) ∧ p(x2 ) ∧ · · · ∧ p(xn )
p(x) is true for all x
Quantifiers

existential quantifier
U = {x1 , x2 , . . . , xn }
∃x p(x) ≡ p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )
p(x) is true for some x

universal quantifier
U = {x1 , x2 , . . . , xn }
∀x p(x) ≡ p(x1 ) ∧ p(x2 ) ∧ · · · ∧ p(xn )
p(x) is true for all x
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Quantifier Examples

Example
U =R
p(x) : x ≥ 0 ∃x [p(x) ∧ r (x)]
q(x) : x 2 ≥ 0 ∀x [p(x) → q(x)]
r (x) : (x − 4)(x + 1) = 0 ∀x [q(x) → s(x)]
s(x) : x 2 − 3 > 0 ∀x [r (x) ∨ s(x)]
∀x [r (x) → p(x)]
are the following expressions true?
Negating Quantifiers

replace ∀ with ∃, and ∃ with ∀

negate the predicate

¬∃x p(x) ⇔ ∀x ¬p(x)

¬∃x ¬p(x) ⇔ ∀x p(x)
¬∀x p(x) ⇔ ∃x ¬p(x)
¬∀x ¬p(x) ⇔ ∃x p(x)
Negating Quantifiers

replace ∀ with ∃, and ∃ with ∀

negate the predicate

¬∃x p(x) ⇔ ∀x ¬p(x)

¬∃x ¬p(x) ⇔ ∀x p(x)
¬∀x p(x) ⇔ ∃x ¬p(x)
¬∀x ¬p(x) ⇔ ∃x p(x)
Negating Quantifiers

Theorem
¬∃x p(x) ⇔ ∀x ¬p(x)

Proof.

¬∃x p(x) ≡ ¬[p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )]

⇔ ¬p(x1 ) ∧ ¬p(x2 ) ∧ · · · ∧ ¬p(xn )
≡ ∀x ¬p(x)
Negating Quantifiers

Theorem
¬∃x p(x) ⇔ ∀x ¬p(x)

Proof.

¬∃x p(x) ≡ ¬[p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )]

⇔ ¬p(x1 ) ∧ ¬p(x2 ) ∧ · · · ∧ ¬p(xn )
≡ ∀x ¬p(x)
Negating Quantifiers

Theorem
¬∃x p(x) ⇔ ∀x ¬p(x)

Proof.

¬∃x p(x) ≡ ¬[p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )]

⇔ ¬p(x1 ) ∧ ¬p(x2 ) ∧ · · · ∧ ¬p(xn )
≡ ∀x ¬p(x)
Negating Quantifiers

Theorem
¬∃x p(x) ⇔ ∀x ¬p(x)

Proof.

¬∃x p(x) ≡ ¬[p(x1 ) ∨ p(x2 ) ∨ · · · ∨ p(xn )]

⇔ ¬p(x1 ) ∧ ¬p(x2 ) ∧ · · · ∧ ¬p(xn )
≡ ∀x ¬p(x)
Predicate Equivalences

Theorem
∃x [p(x) ∨ q(x)] ⇔ ∃x p(x) ∨ ∃x q(x)

Theorem
∀x [p(x) ∧ q(x)] ⇔ ∀x p(x) ∧ ∀x q(x)
Predicate Equivalences

Theorem
∃x [p(x) ∨ q(x)] ⇔ ∃x p(x) ∨ ∃x q(x)

Theorem
∀x [p(x) ∧ q(x)] ⇔ ∀x p(x) ∧ ∀x q(x)
Predicate Implications

Theorem
∀x p(x) ⇒ ∃x p(x)

Theorem
∃x [p(x) ∧ q(x)] ⇒ ∃x p(x) ∧ ∃x q(x)

Theorem
∀x p(x) ∨ ∀x q(x) ⇒ ∀x [p(x) ∨ q(x)]
Predicate Implications

Theorem
∀x p(x) ⇒ ∃x p(x)

Theorem
∃x [p(x) ∧ q(x)] ⇒ ∃x p(x) ∧ ∃x q(x)

Theorem
∀x p(x) ∨ ∀x q(x) ⇒ ∀x [p(x) ∨ q(x)]
Predicate Implications

Theorem
∀x p(x) ⇒ ∃x p(x)

Theorem
∃x [p(x) ∧ q(x)] ⇒ ∃x p(x) ∧ ∃x q(x)

Theorem
∀x p(x) ∨ ∀x q(x) ⇒ ∀x [p(x) ∨ q(x)]
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Multiple Quantifiers

∃x∃y p(x, y )
∀x∃y p(x, y )
∃x∀y p(x, y )
∀x∀y p(x, y )
Multiple Quantifier Examples

Example
U =Z
p(x, y ) : x + y = 17
∀x∃y p(x, y ):
for every x there exists a y such that x + y = 17
∃y ∀x p(x, y ):
there exists a y so that for all x, x + y = 17

what if U = N?
Multiple Quantifier Examples

Example
U =Z
p(x, y ) : x + y = 17
∀x∃y p(x, y ):
for every x there exists a y such that x + y = 17
∃y ∀x p(x, y ):
there exists a y so that for all x, x + y = 17

what if U = N?
Multiple Quantifier Examples

Example
U =Z
p(x, y ) : x + y = 17
∀x∃y p(x, y ):
for every x there exists a y such that x + y = 17
∃y ∀x p(x, y ):
there exists a y so that for all x, x + y = 17

what if U = N?
Multiple Quantifier Examples

Example
U =Z
p(x, y ) : x + y = 17
∀x∃y p(x, y ):
for every x there exists a y such that x + y = 17
∃y ∀x p(x, y ):
there exists a y so that for all x, x + y = 17

what if U = N?
Multiple Quantifiers

Example
Ux = {1, 2} ∧ Uy = {A, B}

∃x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∨ [p(2, A) ∨ p(2, B)]

∃x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∨ [p(2, A) ∧ p(2, B)]
∀x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∧ [p(2, A) ∨ p(2, B)]
∀x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∧ [p(2, A) ∧ p(2, B)]
Multiple Quantifiers

Example
Ux = {1, 2} ∧ Uy = {A, B}

∃x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∨ [p(2, A) ∨ p(2, B)]

∃x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∨ [p(2, A) ∧ p(2, B)]
∀x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∧ [p(2, A) ∨ p(2, B)]
∀x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∧ [p(2, A) ∧ p(2, B)]
Multiple Quantifiers

Example
Ux = {1, 2} ∧ Uy = {A, B}

∃x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∨ [p(2, A) ∨ p(2, B)]

∃x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∨ [p(2, A) ∧ p(2, B)]
∀x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∧ [p(2, A) ∨ p(2, B)]
∀x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∧ [p(2, A) ∧ p(2, B)]
Multiple Quantifiers

Example
Ux = {1, 2} ∧ Uy = {A, B}

∃x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∨ [p(2, A) ∨ p(2, B)]

∃x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∨ [p(2, A) ∧ p(2, B)]
∀x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∧ [p(2, A) ∨ p(2, B)]
∀x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∧ [p(2, A) ∧ p(2, B)]
Multiple Quantifiers

Example
Ux = {1, 2} ∧ Uy = {A, B}

∃x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∨ [p(2, A) ∨ p(2, B)]

∃x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∨ [p(2, A) ∧ p(2, B)]
∀x∃y p(x, y ) ≡ [p(1, A) ∨ p(1, B)] ∧ [p(2, A) ∨ p(2, B)]
∀x∀y p(x, y ) ≡ [p(1, A) ∧ p(1, B)] ∧ [p(2, A) ∧ p(2, B)]
References

Required Reading: Grimaldi

Chapter 2: Fundamentals of Logic

2.4. The Use of Quantifiers

Supplementary Reading: O’Donnell, Hall, Page

Chapter 7: Predicate Logic

Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Set

Definition
set: a collection of elements that are
distinct
unordered
non-repeating
Set Representation

explicit representation
elements are listed within braces: {a1 , a2 , . . . , an }

implicit representation
elements that validate a predicate: {x|x ∈ G , p(x)}

∅: empty set
let S be a set, and a be an element
a ∈ S: a is an element of set S
a∈/ S: a is not an element of set S

|S|: number of elements (cardinality)

Set Representation

explicit representation
elements are listed within braces: {a1 , a2 , . . . , an }

implicit representation
elements that validate a predicate: {x|x ∈ G , p(x)}

∅: empty set
let S be a set, and a be an element
a ∈ S: a is an element of set S
a∈/ S: a is not an element of set S

|S|: number of elements (cardinality)

Set Representation

explicit representation
elements are listed within braces: {a1 , a2 , . . . , an }

implicit representation
elements that validate a predicate: {x|x ∈ G , p(x)}

∅: empty set
let S be a set, and a be an element
a ∈ S: a is an element of set S
a∈/ S: a is not an element of set S

|S|: number of elements (cardinality)

Set Representation

explicit representation
elements are listed within braces: {a1 , a2 , . . . , an }

implicit representation
elements that validate a predicate: {x|x ∈ G , p(x)}

∅: empty set
let S be a set, and a be an element
a ∈ S: a is an element of set S
a∈/ S: a is not an element of set S

|S|: number of elements (cardinality)

Set Representation

explicit representation
elements are listed within braces: {a1 , a2 , . . . , an }

implicit representation
elements that validate a predicate: {x|x ∈ G , p(x)}

∅: empty set
let S be a set, and a be an element
a ∈ S: a is an element of set S
a∈/ S: a is not an element of set S

|S|: number of elements (cardinality)

Explicit Representation Example

Example
{3, 8, 2, 11, 5}
11 ∈ {3, 8, 2, 11, 5}
|{3, 8, 2, 11, 5}| = 5
Implicit Representation Examples

Example
{x|x ∈ Z+ , 20 < x 3 < 100} ≡ {3, 4}
{2x − 1|x ∈ Z+ , 20 < x 3 < 100} ≡ {5, 7}

Example
A = {x|x ∈ R, 1 ≤ x ≤ 5}

Example
E = {n|n ∈ N, ∃k ∈ N [n = 2k]}
A = {x|x ∈ E , 1 ≤ x ≤ 5}
Implicit Representation Examples

Example
{x|x ∈ Z+ , 20 < x 3 < 100} ≡ {3, 4}
{2x − 1|x ∈ Z+ , 20 < x 3 < 100} ≡ {5, 7}

Example
A = {x|x ∈ R, 1 ≤ x ≤ 5}

Example
E = {n|n ∈ N, ∃k ∈ N [n = 2k]}
A = {x|x ∈ E , 1 ≤ x ≤ 5}
Implicit Representation Examples

Example
{x|x ∈ Z+ , 20 < x 3 < 100} ≡ {3, 4}
{2x − 1|x ∈ Z+ , 20 < x 3 < 100} ≡ {5, 7}

Example
A = {x|x ∈ R, 1 ≤ x ≤ 5}

Example
E = {n|n ∈ N, ∃k ∈ N [n = 2k]}
A = {x|x ∈ E , 1 ≤ x ≤ 5}
Set Dilemma

There is a barber who lives in a small town.

He shaves all those men who don’t shave themselves.
He doesn’t shave those men who shave themselves.
Does the barber shave himself?
yes → but he doesn’t shave men who shave themselves
→ no
no → but he shaves all men who don’t shave themselves
→ yes
Set Dilemma

There is a barber who lives in a small town.

He shaves all those men who don’t shave themselves.
He doesn’t shave those men who shave themselves.
Does the barber shave himself?
yes → but he doesn’t shave men who shave themselves
→ no
no → but he shaves all men who don’t shave themselves
→ yes
Set Dilemma

There is a barber who lives in a small town.

He shaves all those men who don’t shave themselves.
He doesn’t shave those men who shave themselves.
Does the barber shave himself?
yes → but he doesn’t shave men who shave themselves
→ no
no → but he shaves all men who don’t shave themselves
→ yes
Set Dilemma

let S be the set of sets that are not an element of themselves

S = {A|A ∈ / A}
Is S an element of itself?
yes → but the predicate is not valid → no
no → but the predicate is valid → yes
Set Dilemma

let S be the set of sets that are not an element of themselves

S = {A|A ∈ / A}
Is S an element of itself?
yes → but the predicate is not valid → no
no → but the predicate is valid → yes
Set Dilemma

let S be the set of sets that are not an element of themselves

S = {A|A ∈ / A}
Is S an element of itself?
yes → but the predicate is not valid → no
no → but the predicate is valid → yes
Set Dilemma

let S be the set of sets that are not an element of themselves

S = {A|A ∈ / A}
Is S an element of itself?
yes → but the predicate is not valid → no
no → but the predicate is valid → yes
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Subset

Definition
A ⊆ B ⇔ ∀x [x ∈ A → x ∈ B]

set equality:
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
proper subset:
A ⊂ B ⇔ (A ⊆ B) ∧ (A 6= B)
∀S [∅ ⊆ S]
Subset

Definition
A ⊆ B ⇔ ∀x [x ∈ A → x ∈ B]

set equality:
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
proper subset:
A ⊂ B ⇔ (A ⊆ B) ∧ (A 6= B)
∀S [∅ ⊆ S]
Subset

Definition
A ⊆ B ⇔ ∀x [x ∈ A → x ∈ B]

set equality:
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
proper subset:
A ⊂ B ⇔ (A ⊆ B) ∧ (A 6= B)
∀S [∅ ⊆ S]
Subset

Definition
A ⊆ B ⇔ ∀x [x ∈ A → x ∈ B]

set equality:
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
proper subset:
A ⊂ B ⇔ (A ⊆ B) ∧ (A 6= B)
∀S [∅ ⊆ S]
Subset

not a subset

A * B ⇔ ¬∀x [x ∈ A → x ∈ B]
⇔ ∃x ¬[x ∈ A → x ∈ B]
⇔ ∃x ¬[¬(x ∈ A) ∨ (x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ ¬(x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ (x ∈
/ B)]
Subset

not a subset

A * B ⇔ ¬∀x [x ∈ A → x ∈ B]
⇔ ∃x ¬[x ∈ A → x ∈ B]
⇔ ∃x ¬[¬(x ∈ A) ∨ (x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ ¬(x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ (x ∈
/ B)]
Subset

not a subset

A * B ⇔ ¬∀x [x ∈ A → x ∈ B]
⇔ ∃x ¬[x ∈ A → x ∈ B]
⇔ ∃x ¬[¬(x ∈ A) ∨ (x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ ¬(x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ (x ∈
/ B)]
Subset

not a subset

A * B ⇔ ¬∀x [x ∈ A → x ∈ B]
⇔ ∃x ¬[x ∈ A → x ∈ B]
⇔ ∃x ¬[¬(x ∈ A) ∨ (x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ ¬(x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ (x ∈
/ B)]
Subset

not a subset

A * B ⇔ ¬∀x [x ∈ A → x ∈ B]
⇔ ∃x ¬[x ∈ A → x ∈ B]
⇔ ∃x ¬[¬(x ∈ A) ∨ (x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ ¬(x ∈ B)]
⇔ ∃x [(x ∈ A) ∧ (x ∈
/ B)]
Power Set

Definition
power set: P(S)
the set of all subsets of a set, including the empty set
and the set itself

if a set has n elements, its power set has 2n elements

Power Set

Definition
power set: P(S)
the set of all subsets of a set, including the empty set
and the set itself

if a set has n elements, its power set has 2n elements

Example of Power Set

Example

P({1, 2, 3}) = {
∅,
{1}, {2}, {3},
{1, 2}, {1, 3}, {2, 3},
{1, 2, 3}
}
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Set Operations

complement
A = {x|x ∈
/ A}

intersection
A ∩ B = {x|(x ∈ A) ∧ (x ∈ B)}
if A ∩ B = ∅ then A and B are disjoint

union
A ∪ B = {x|(x ∈ A) ∨ (x ∈ B)}
Set Operations

complement
A = {x|x ∈
/ A}

intersection
A ∩ B = {x|(x ∈ A) ∧ (x ∈ B)}
if A ∩ B = ∅ then A and B are disjoint

union
A ∪ B = {x|(x ∈ A) ∨ (x ∈ B)}
Set Operations

complement
A = {x|x ∈
/ A}

intersection
A ∩ B = {x|(x ∈ A) ∧ (x ∈ B)}
if A ∩ B = ∅ then A and B are disjoint

union
A ∪ B = {x|(x ∈ A) ∨ (x ∈ B)}
Set Operations

difference
A − B = {x|(x ∈ A) ∧ (x ∈
/ B)}
A−B =A∩B
symmetric difference:
A 4 B = {x|(x ∈ A ∪ B) ∧ (x ∈
/ A ∩ B)}
Set Operations

difference
A − B = {x|(x ∈ A) ∧ (x ∈
/ B)}
A−B =A∩B
symmetric difference:
A 4 B = {x|(x ∈ A ∪ B) ∧ (x ∈
/ A ∩ B)}
Set Operations

difference
A − B = {x|(x ∈ A) ∧ (x ∈
/ B)}
A−B =A∩B
symmetric difference:
A 4 B = {x|(x ∈ A ∪ B) ∧ (x ∈
/ A ∩ B)}
Cartesian Product

Definition
Cartesian product:
A × B = {(a, b)|a ∈ A, b ∈ B}
A × B × C × · · · × N = {(a, b, . . . , n)|a ∈ A, b ∈ B, . . . , n ∈ N}

|A × B × C × · · · × N| = |A| · |B| · |C | · · · |N|

Cartesian Product

Definition
Cartesian product:
A × B = {(a, b)|a ∈ A, b ∈ B}
A × B × C × · · · × N = {(a, b, . . . , n)|a ∈ A, b ∈ B, . . . , n ∈ N}

|A × B × C × · · · × N| = |A| · |B| · |C | · · · |N|

Cartesian Product Example

Example
A = {a1 .a2 , a3 , a4 }
B = {b1 , b2 , b3 }

A×B = {
(a1 , b1 ), (a1 , b2 ), (a1 , b3 ),
(a2 , b1 ), (a2 , b2 ), (a2 , b3 ),
(a3 , b1 ), (a3 , b2 ), (a3 , b3 ),
(a4 , b1 ), (a4 , b2 ), (a4 , b3 )
}
Equivalences

Double Complement
A=A

Commutativity
A∩B =B ∩A A∪B =B ∪A

Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C ) (A ∪ B) ∪ C = A ∪ (B ∪ C )

Idempotence
A∩A=A A∪A=A

Inverse
A∩A=∅ A∪A=U
Equivalences

Double Complement
A=A

Commutativity
A∩B =B ∩A A∪B =B ∪A

Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C ) (A ∪ B) ∪ C = A ∪ (B ∪ C )

Idempotence
A∩A=A A∪A=A

Inverse
A∩A=∅ A∪A=U
Equivalences

Double Complement
A=A

Commutativity
A∩B =B ∩A A∪B =B ∪A

Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C ) (A ∪ B) ∪ C = A ∪ (B ∪ C )

Idempotence
A∩A=A A∪A=A

Inverse
A∩A=∅ A∪A=U
Equivalences

Double Complement
A=A

Commutativity
A∩B =B ∩A A∪B =B ∪A

Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C ) (A ∪ B) ∪ C = A ∪ (B ∪ C )

Idempotence
A∩A=A A∪A=A

Inverse
A∩A=∅ A∪A=U
Equivalences

Double Complement
A=A

Commutativity
A∩B =B ∩A A∪B =B ∪A

Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C ) (A ∪ B) ∪ C = A ∪ (B ∪ C )

Idempotence
A∩A=A A∪A=A

Inverse
A∩A=∅ A∪A=U
Equivalences

Identity
A∩U =A A∪∅=A

Domination
A∩∅=∅ A∪U =U

Distributivity
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

Absorption
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

DeMorgan’s Laws
A∩B =A∪B A∪B =A∩B
Equivalences

Identity
A∩U =A A∪∅=A

Domination
A∩∅=∅ A∪U =U

Distributivity
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

Absorption
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

DeMorgan’s Laws
A∩B =A∪B A∪B =A∩B
Equivalences

Identity
A∩U =A A∪∅=A

Domination
A∩∅=∅ A∪U =U

Distributivity
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

Absorption
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

DeMorgan’s Laws
A∩B =A∪B A∪B =A∩B
Equivalences

Identity
A∩U =A A∪∅=A

Domination
A∩∅=∅ A∪U =U

Distributivity
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

Absorption
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

DeMorgan’s Laws
A∩B =A∪B A∪B =A∩B
Equivalences

Identity
A∩U =A A∪∅=A

Domination
A∩∅=∅ A∪U =U

Distributivity
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )

Absorption
A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

DeMorgan’s Laws
A∩B =A∪B A∪B =A∩B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
DeMorgan’s Laws

Proof.

A ∩ B = {x|x ∈
/ (A ∩ B)}
= {x|¬(x ∈ (A ∩ B))}
= {x|¬((x ∈ A) ∧ (x ∈ B))}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|(x ∈
/ A) ∨ (x ∈
/ B)}
= {x|(x ∈ A) ∨ (x ∈ B)}
= {x|x ∈ A ∪ B}
= A∪B
Example of Equivalence

Theorem
A ∩ (B − C ) = (A ∩ B) − (A ∩ C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Equivalence Example

Proof.

(A ∩ B) − (A ∩ C ) = (A ∩ B) ∩ (A ∩ C )
= (A ∩ B) ∩ (A ∪ C )
= ((A ∩ B) ∩ A) ∪ ((A ∩ B) ∩ C ))
= ∅ ∪ ((A ∩ B) ∩ C ))
= (A ∩ B) ∩ C
= A ∩ (B ∩ C )
= A ∩ (B − C )
Topics

1 Predicates
Introduction
Quantifiers
Multiple Quantifiers

2 Sets
Introduction
Subset
Set Operations
Inclusion-Exclusion
Principle of Inclusion-Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C | =
|A| + |B| + |C | − (|A ∩ B| + |A ∩ C | + |B ∩ C |) + |A ∩ B ∩ C |

Theorem

X X
|A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj |
i i,j
X
+ |Ai ∩ Aj ∩ Ak |
i,j,k

· · · + −1n−1 |Ai ∩ Aj ∩ · · · ∩ An |
Principle of Inclusion-Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C | =
|A| + |B| + |C | − (|A ∩ B| + |A ∩ C | + |B ∩ C |) + |A ∩ B ∩ C |

Theorem

X X
|A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj |
i i,j
X
+ |Ai ∩ Aj ∩ Ak |
i,j,k

· · · + −1n−1 |Ai ∩ Aj ∩ · · · ∩ An |
Principle of Inclusion-Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C | =
|A| + |B| + |C | − (|A ∩ B| + |A ∩ C | + |B ∩ C |) + |A ∩ B ∩ C |

Theorem

X X
|A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj |
i i,j
X
+ |Ai ∩ Aj ∩ Ak |
i,j,k

· · · + −1n−1 |Ai ∩ Aj ∩ · · · ∩ An |
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

a method to identify prime numbers

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 5 7 9 11 13 15 17
19 21 23 25 27 29

2 3 5 7 11 13 17
19 23 25 29

2 3 5 7 11 13 17
19 23 29
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

a method to identify prime numbers

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 5 7 9 11 13 15 17
19 21 23 25 27 29

2 3 5 7 11 13 17
19 23 25 29

2 3 5 7 11 13 17
19 23 29
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

a method to identify prime numbers

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 5 7 9 11 13 15 17
19 21 23 25 27 29

2 3 5 7 11 13 17
19 23 25 29

2 3 5 7 11 13 17
19 23 29
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

a method to identify prime numbers

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 5 7 9 11 13 15 17
19 21 23 25 27 29

2 3 5 7 11 13 17
19 23 25 29

2 3 5 7 11 13 17
19 23 29
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

a method to identify prime numbers

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27 28 29 30

2 3 5 7 9 11 13 15 17
19 21 23 25 27 29

2 3 5 7 11 13 17
19 23 25 29

2 3 5 7 11 13 17
19 23 29
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

number of primes between 1 and 100

numbers that are not divisible by 2, 3, 5 and 7
A2 : set of numbers divisible by 2
A3 : set of numbers divisible by 3
A5 : set of numbers divisible by 5
A7 : set of numbers divisible by 7
|A2 ∪ A3 ∪ A5 ∪ A7 |
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

number of primes between 1 and 100

numbers that are not divisible by 2, 3, 5 and 7
A2 : set of numbers divisible by 2
A3 : set of numbers divisible by 3
A5 : set of numbers divisible by 5
A7 : set of numbers divisible by 7
|A2 ∪ A3 ∪ A5 ∪ A7 |
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

number of primes between 1 and 100

numbers that are not divisible by 2, 3, 5 and 7
A2 : set of numbers divisible by 2
A3 : set of numbers divisible by 3
A5 : set of numbers divisible by 5
A7 : set of numbers divisible by 7
|A2 ∪ A3 ∪ A5 ∪ A7 |
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 | = b100/2c = 50 |A2 ∩ A3 | = b100/6c = 16

|A3 | = b100/3c = 33 |A2 ∩ A5 | = b100/10c = 10
|A5 | = b100/5c = 20 |A2 ∩ A7 | = b100/14c = 7
|A7 | = b100/7c = 14 |A3 ∩ A5 | = b100/15c = 6
|A3 ∩ A7 | = b100/21c = 4
|A5 ∩ A7 | = b100/35c = 2
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 | = b100/2c = 50 |A2 ∩ A3 | = b100/6c = 16

|A3 | = b100/3c = 33 |A2 ∩ A5 | = b100/10c = 10
|A5 | = b100/5c = 20 |A2 ∩ A7 | = b100/14c = 7
|A7 | = b100/7c = 14 |A3 ∩ A5 | = b100/15c = 6
|A3 ∩ A7 | = b100/21c = 4
|A5 ∩ A7 | = b100/35c = 2
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 ∩ A3 ∩ A5 | = b100/30c = 3
|A2 ∩ A3 ∩ A7 | = b100/42c = 2
|A2 ∩ A5 ∩ A7 | = b100/70c = 1
|A3 ∩ A5 ∩ A7 | = b100/105c = 0

|A2 ∩ A3 ∩ A5 ∩ A7 | = b100/210c = 0
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 ∩ A3 ∩ A5 | = b100/30c = 3
|A2 ∩ A3 ∩ A7 | = b100/42c = 2
|A2 ∩ A5 ∩ A7 | = b100/70c = 1
|A3 ∩ A5 ∩ A7 | = b100/105c = 0

|A2 ∩ A3 ∩ A5 ∩ A7 | = b100/210c = 0
Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 ∪ A3 ∪ A5 ∪ A7 | = (50 + 33 + 20 + 14)

− (16 + 10 + 7 + 6 + 4 + 2)
+ (3 + 2 + 1 + 0)
− (0)
= 78

number of primes: (100 − 78) + 4 − 1 = 25

Inclusion-Exclusion Example

Example (sieve of Eratosthenes)

|A2 ∪ A3 ∪ A5 ∪ A7 | = (50 + 33 + 20 + 14)

− (16 + 10 + 7 + 6 + 4 + 2)
+ (3 + 2 + 1 + 0)
− (0)
= 78

number of primes: (100 − 78) + 4 − 1 = 25

References

Required Reading: Grimaldi

Chapter 3: Set Theory

3.1. Sets and Subsets
3.2. Set Operations and the Laws of Set Theory
Chapter 8: The Principle of Inclusion and Exclusion
8.1. The Principle of Inclusion and Exclusion

Supplementary Reading: O’Donnell, Hall, Page

Chapter 8: Set Theory