CS计算机代考程序代写 flex Haskell AI COMP30026 Models of Computation – Sets

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