Lectures Sets

Sets Hoorcollege 1
Set Theory for Computer Science 8 februari 2018

● Definition and notation
○ Learn with Sets how to structure data.
○ Definition and notation of a set
■ Set: unordered collection of elements
■ To denote a set we use: {}
■ Try to use a name that describes the set
■ Use dots to indicate you want to continue with all the integer numbers
that lie between.
■ Examples:
● DaysOfWeek := {Mon, Tue, Wed, Thu, Fri, Sat, Sun}
● A := {1, 2, 3}
● Digits := 0, 1, … , 9}

● N := {1, 2, 3, … } natural numbers
● Z := { ... , -2, -1, 0, 1, 2, … } integer numbers
■ Second notation: Prototypes en discription notation:
● MulitplesOf2 := {2k : k a natural number} = {0, 2, 4, … }
● Months := {x: x is a month}
● “Elements of the form x where x is a month”
○ Element and subset
■ Element
● a∈A means a is an element of set A
● a∉A means a is not an element of set A
■ Subset
● A⊆B means all elements of A are
elements of B
● Meaning: A is a subset of B
● A ⊈B means at least one element of A is
not in B
● Meaning: A is not a subset of B
■ Examples
● 4 ∈ {1, 2, 3, 4} {2, 3} ⊆ {1, 2, 3, 4}
● 5 ∉ {1, 2, 3, 4} {2, 5} ⊈ {1, 2, 3, 4}
○ Equality, empty set and number of elements
■ Equality
● Equal if: Set A is a subset of B and B is a subset of A.
● The order in which you write the elements of the set doesn’t
matter.
● A=B ⇔ A ⊆ B and B ⊆ A
⇔ A and B have exactly the
same elements
■ Examples
● {1, 2, 3, 4} = {4, 3, 2, 1} = {4, 3, 3, 2 1 2}
● {1, 2, 3, 4} ≠ {2, 3, 4, 5}
■ The empty set

, ● Ø or {} set with no elements
■ Number of elements
■ Use # to denote the number of elements of the set
■ {} is also a subset
● #{4, 3, 3, 2, 1, 2} = 4 #Ø = 0
○ Review exercises
■ Exercise 1
● Write down all subsets of {1} and of {1,2}
○ Subsets of {1}
■ {1}{}
○ Subsets of {1, 2}
■ {1}, {2}, {} and {1,2}
■ The set itself is also a subset.
■ Exercise 2
● Are the following set inclusions true or false?
○ a) {1, 3, 5, 7} ⊆ {7, 6, 5, 4, 3, 2, 6, 8}
■ False
○ b) {1, 3, 5, 7} ⊆ {7, 4, 1, 6, 5, 4, 4, 3}
■ True
● Fundamental set operations
○ Universe
■ Sets are subsets of a universe U:




■
■ Example:
● U: all 4-letter words
● A: words with ‘a’
■ The elements that are outside ‘a’ but in the U are all the 4-letter words
without ‘a’.
■ A’: words with no ‘a’
● A’ := {x ∈ U : x ∉ A}
■ U defines the context we work in
○ Complement
■ Complement of A

, ■
■ Example:
● U: all 4-letter words
● A: words with ‘a’
● A’: words with no ‘a’
■ A’ := {x ∈ U: x ∉ A}
○ Union and intersection
■ Union of A and B




■
■ Example
● U: all 4-letter words
● A: words with ‘a’
● B: words with ‘b’
● A U B: words with ‘a’ or ‘b’ (inclusive or)
■ Prototype description notation: A U B := {x ∈ U: x ∈ A or x ∈ B}
○ Union and intersection
■ Intersection of A and B




■
■ Example
● U: all 4-letter words
● A: words with ‘a’
● B: words with ‘b’
● A ∩ B: words with ‘a’ and ‘b’
■ A ∩ B := { {x ∈ U: x ∈ A and x ∈ B}

, ○ Set-theoretic and symmetric difference
■ A minus B




■
■
Example
● U: all 4-letter words
● A: words with ‘a’
● B: words with ‘b’
● A \ B: words with ‘a’ but no ‘b’
■ A \ B := { x ∈ A: x ∉ B} = A ∩ B’
■ B minus A is not the same as A minus B
○ Set-theoretic and symmetric difference
■ Symmetric difference of A and B
■ Example
● U: all 4-letter words
● A: words with ‘a’
● B: words with ‘b’
● A △ B: words with ‘a’ or ‘b’ but not both (exclusive or) B: words with ‘a’ or ‘b’ but not both (exclusive or)
■ A △ B: words with ‘a’ or ‘b’ but not both (exclusive or) B := (A \ B) U (B \ A)
= (A U B) ∩ (A ∩ B)’

○
Review exercises
■ Exercise
● We are given the data:
○ A := {0, 1, 2, 3}
○ B := {2, 3, 4, 5}
○ The universe is N
● Determine the following sets:
○ A U B = {0, 1, 2, 3, 4, 5} A \ B = {0, 1}
○ A ∩ B = {2, 3} B \ A = {4, 5}
○ A’ = {4, 5, 6, … } A △ B: words with ‘a’ or ‘b’ but not both (exclusive or) B = {0, 1, 4, 5}
○ B’ = {0, 1} U {6, 7, 8, …}
● Venn diagrams and partitions
○ Venn diagram: abstract visualisation of relations between sets
■ 2 sets ⇒ 4 regions 3 sets ⇒ 8 regions




○
■ Any region in a Venn diagram might be empty