# discrete mathematics & mathematical reasoning basic ... discrete mathematics & mathematical...

Post on 01-Aug-2020

9 views

Embed Size (px)

TRANSCRIPT

Discrete Mathematics & Mathematical Reasoning Basic Structures: Sets, Functions, Relations,

Sequences and Sums

Colin Stirling

Informatics

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 1 / 38

Sets

A set is an unordered collection of elements

A = {3,2,1,0} = {1,2,0,3} Membership 3 ∈ A Non-membership 5 6∈ A Emptyset ∅ = { }

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 2 / 38

Sets

A set is an unordered collection of elements A = {3,2,1,0} = {1,2,0,3}

Membership 3 ∈ A Non-membership 5 6∈ A Emptyset ∅ = { }

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 2 / 38

Sets

A set is an unordered collection of elements A = {3,2,1,0} = {1,2,0,3} Membership 3 ∈ A Non-membership 5 6∈ A

Emptyset ∅ = { }

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 2 / 38

Sets

A set is an unordered collection of elements A = {3,2,1,0} = {1,2,0,3} Membership 3 ∈ A Non-membership 5 6∈ A Emptyset ∅ = { }

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 2 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values

N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers

Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers

Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers

R Real numbers R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers

R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers

Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers Q Rational numbers

C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Some important sets (boldface in the textbook)

B = {true, false} Boolean values N = {0,1,2,3, . . . } Natural numbers Z = {. . . ,−3,−2,−1,0,1,2,3, . . . } Integers Z+ = {1,2,3, . . . } Positive integers R Real numbers R+ Positive real numbers Q Rational numbers C Complex numbers

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 3 / 38

Sets defined using comprehension

S = {x | P(x) } where P(x) is a predicate

{x | x ∈ N ∧ 2 divides x} = {2m | m ≥ 0} Subsets of sets upon which an order is defined

[a,b] = {x | a ≤ x ≤ b} closed interval [a,b) = {x | a ≤ x < b} (a,b] = {x | a < x ≤ b} (a,b) = {x | a < x < b} open interval

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 4 / 38

Sets defined using comprehension

S = {x | P(x) } where P(x) is a predicate {x | x ∈ N ∧ 2 divides x} = {2m | m ≥ 0}

Subsets of sets upon which an order is defined

[a,b] = {x | a ≤ x ≤ b} closed interval [a,b) = {x | a ≤ x < b} (a,b] = {x | a < x ≤ b} (a,b) = {x | a < x < b} open interval

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 4 / 38

Sets defined using comprehension

S = {x | P(x) } where P(x) is a predicate {x | x ∈ N ∧ 2 divides x} = {2m | m ≥ 0} Subsets of sets upon which an order is defined

[a,b] = {x | a ≤ x ≤ b} closed interval [a,b) = {x | a ≤ x < b} (a,b] = {x | a < x ≤ b} (a,b) = {x | a < x < b} open interval

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 4 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference

If Ai are sets for all i ∈ I then ⋃

i∈I Ai and ⋂

i∈I Ai are sets A ⊆ B subset; A ⊇ B superset A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset

A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset A = B set equality

P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality

A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

Notation

A ∪ B union; A ∩ B intersection; A− B difference If Ai are sets for all i ∈ I then

⋃ i∈I Ai and

⋂ i∈I Ai are sets

A ⊆ B subset; A ⊇ B superset A = B set equality P(A) powerset (set of all subsets of A); also 2A

|A| cardinality A× B cartesian product (tuple sets)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 5 / 38

A proper mathematical definition of set is complicated (Russell’s paradox)

The set of cats is not a cat (is not a member of itself) The set of non-cats (all things that are not cats) is a member of itself Let S be the set of all sets which are not members of themselves S = {x | x 6∈ x} (using naive comprehension) Question: is S a member of itself (S ∈ S) ? S ∈ S provided that S 6∈ S; S 6∈ S provided that S ∈ S Modern formulations (such as Zermelo-Fraenkel set theory) restrict comprehension. (However, it is impossible to prove in ZF that ZF is consistent unless ZF is inconsistent.)

Colin Stirling (Informatics) Discrete Mathematics (Chaps 2 & 9) Today 6 / 38

A proper mathematical definition of set is complicated (Russell