COMP30026 Models of Computation – Sets
COMP30026 Models of Computation
Sets
Bach Le / Anna Kalenkova
Lecture Week 6 Part 1
Semester 2, 2021
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 1 / 22
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 2 / 22
Assignment 1
Assignment 1 was released on 26 August; it is due on 16 September.
Solutions are submitted through Grok and Gradescope (Challenges 5
and 6).
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 3 / 22
Set Theory
“Definition”: (Georg Cantor) A set is a collection into a whole of
definite, distinct objects of our intuition or of our thought. The
objects are called the elements (members) of the set.
Notation: We write a ∈ A to express that a is a member of set A.
Examples: 42 ∈ N and π 6∈ Q.
Principle of Extensionality: For all sets A and B we have
A = B ⇔∀x (x ∈ A⇔ x ∈ B)
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 4 / 22
Set Notation
Small sets can be specified completely: {−2,−1, 0, 1, 2},
{Huey,Dewey, Louie}, {}. We often write the last one as ∅.
Note that, by the Principle of Extensionality, order and repetition are
irrelevant, for example,
{{1, 2, 2}, {1}, {2, 1}} = {{1}, {1, 2}}
For large sets, including infinite sets, we have set abstraction:
If P is a property of objects x then the abstraction
{x | P(x)}
denotes the set of things x that have the property P. Hence
a ∈ {x | P(x)} is equivalent to P(a).
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 5 / 22
Set Notation and Haskell’s List Notation
Haskell’s list notation is clearly inspired by set notation:
Haskell Set notation
[] {}
[1,2,3] {1, 2, 3}
[n | n <- nats, even n] {n ∈ N | even(n)}
[f n | n <- nats] {f (n) | n ∈ N}
[1,3..] {1, 3, . . .}
The dot-dot notation here assumes some systematic way of
generating all elements (an enumeration).
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 6 / 22
Well-Foundedness
Call a set S well-founded if there is no infinite sequence
S = S0 ∋ S1 ∋ S2 ∋ · · · , and consider the set W of all well-founded
sets.
If W ∈ W then W ∋ W ∋ W · · · , and therefore W 6∈ W .
If W 6∈ W then there is some infinite sequence
W = W0 ∋ W1 ∋ W2 · · · . Since W1 ∋ W2 ∋ W3 · · · , W1 is not
well-founded, that is, W1 6∈ W . This contradicts W = W0 ∋ W1.
Bertrand Russell’s famous paradox similarly considers a set property
R = {x | x 6∈ x} which leads to an inconsistent set theory:
R ∈ R ⇔ R 6∈ R
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 7 / 22
Sets and Types
One way (a crude way) to curb set theory so as to obtain consistency
is to impose a system of types. In fact this was Russell’s solution.
The purpose of the type discipline is to rule “S ∈ S” inadmissible, by
insisting that S cannot inhabit type “t” and also “set of t”.
Russell’s type concept is the root of type disciplines used in many
programming languages.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 8 / 22
The Subset Relation
A is a subset of B iff ∀x (x ∈ A⇒ x ∈ B).
We write this as A ⊆ B .
If A ⊆ B and A 6= B , we say that A is a proper subset of B , and
write this A ⊂ B .
Do not confuse ⊆ with ∈. We have {1} ⊆ {1, 2}, but {1} 6∈ {1, 2}.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 9 / 22
The Subset Relation Is a Partial Ordering
For all sets A, B , and C , we have
A ⊆ A (reflexivity)
A ⊆ B ∧ B ⊆ A⇒ A = B (antisymmetry)
A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C (transitivity)
These laws are easy to prove from the definition of ⊆.
The three laws together state that ⊆ is a partial ordering.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 10 / 22
Special Sets
The empty set satisfies ∅ ⊆ A for every set A.
A set with just a single element is a singleton.
For example, {{1, 2}} is a singleton (its only element is a set).
The set {a} should not be confused with its element a.
A set with two elements is a pair.
Ordinarily, and in programming languages, we refer to (1,2) as a
pair, but in set theory we would call that an ordered pair.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 11 / 22
Algebra of Sets
Let A and B be sets. Then
A ∩ B = {x | x ∈ A ∧ x ∈ B} is the intersection of A and B ;
A ∪ B = {x | x ∈ A ∨ x ∈ B} is their union;
A \ B = {x | x ∈ A ∧ x 6∈ B} is their difference; and
A⊕ B = (A \ B) ∪ (B \ A) is their symmetric difference.
In the presence of a set X of which all sets are considered subsets, we
also define
Ac = X \ A is the complement of A.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 12 / 22
Venn Diagrams
X
A
B
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 13 / 22
Some Laws
Absorption: A ∩ A = A
A ∪ A = A
Commutativity: A ∩ B = B ∩ A
A ∪ B = B ∪ A
Associativity: A ∩ (B ∩ C ) = (A ∩ B) ∩ C
A ∪ (B ∪ C ) = (A ∪ B) ∪ C
Distributivity: A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 14 / 22
More Laws
Double complement: A = (Ac)c
De Morgan: (A ∩ B)c = Ac ∪ Bc
(A ∪ B)c = Ac ∩ Bc
Duality: X c = ∅ and ∅c = X
Identity: A ∪ ∅ = A and A ∩ X = A
Dominance: A ∩ ∅ = ∅ and A ∪ X = X
Complementation: A ∩ Ac = ∅ and A ∪ Ac = X
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 15 / 22
Subset Equivalences
Subset characterisation: A ⊆ B ≡ A = A ∩ B ≡ B = A ∪ B
Contraposition: Ac ⊆ Bc ≡ B ⊆ A
A ⊆ Bc ≡ B ⊆ Ac
Ac ⊆ B ≡ Bc ⊆ A
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 16 / 22
Subset Equivalences
Subset characterisation: A ⊆ B ≡ A = A ∩ B ≡ B = A ∪ B
Contraposition: Ac ⊆ Bc ≡ B ⊆ A
A ⊆ Bc ≡ B ⊆ Ac
Ac ⊆ B ≡ Bc ⊆ A
All very similar to the equivalences we saw for propositional
logic—just substitute ¬ for complement, ∧ for ∩, ∨ for ∪, ⇒ for ⊆,
⊥ for ∅, and ⊤ for X .
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 16 / 22
Powersets
The powerset P(X ) of the set X is the set {A | A ⊆ X} of all
subsets of X .
In particular ∅ and X are elements of P(X ).
If X is finite, of cardinality n, then P(X ) is of cardinality 2n.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 17 / 22
Generalised Union and Intersection
Suppose we have a collection of sets Ai , one for each i in some
(index) set I . For example, I may be {1..99}, or I may be infinite.
The union of the collection is
⋃
i∈I
Ai = {x | ∃i (i ∈ I ∧ x ∈ Ai)}
The intersection of the sets is
⋂
i∈I
Ai = {x | ∀i (i ∈ I ⇒ x ∈ Ai)}
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 18 / 22
Ordered Pairs
Can we capture the notion of ordered pairs (a, b) with set-theoretic
notions? We want this to hold:
(a, b) = (c, d)⇔ a = c ∧ b = d
We can achieve this by defining
(a, b) = {{a}, {a, b}}
Hence we can freely use the notation (a, b) with the intuitive
meaning.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 19 / 22
Cartesian Product and Tuples
The Cartesian product of A and B is defined
A× B = {(a, b) | a ∈ A ∧ b ∈ B}
We define the set An of n-tuples over A as follows:
A0 = {∅}
An+1 = A× An
Of course we shall write (a, b, c) rather than (a, (b, (c, ∅))).
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 20 / 22
Some Laws Involving Cartesian Product
(A× B) ∩ (C × D) = (A× D) ∩ (C × B)
(A ∩ B)× C = (A× C ) ∩ (B × C )
(A ∪ B)× C = (A× C ) ∪ (B × C )
(A ∩ B)× (C ∩ D) = (A× C ) ∩ (B × D)
(A ∪ B)× (C ∪ D) = (A× C ) ∪ (A× D) ∪ (B × C ) ∪ (B × D)
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 21 / 22
Relations
An n-ary relation is a set of n-tuples.
(MY255 , Lagos, Lusaka, 1755),
(ZA942 , Lima, London, 1015),
(BB114 , Lyon, Lodz, 2220)
That is, the relation is a subset of some Cartesian product
A1 × A2 × · · · × An.
Or equivalently, we can think of a relation as a function from
A1 × A2 × · · · × An to {0, 1}.
Models of Computation (Sem 2, 2021) Sets © University of Melbourne 22 / 22