Topic 1: Set Theory

Question 1

What is a set (3)

Answer 1

-A set is a collection of objects
-We often use uppercase letters to denote sets, and lowercase letters to denote elements of sets (x in A -> x ∈ A)
-For ;large sets, you specify the elements: {x:x² = 1} -> 1, -1 (x such that x² = 1, elements are +-1)

Question 2

What is the order/cordinality of a set (1)

Answer 2

-The order/cordinality of a set is the number of elements in A, denoted |A|

Question 3

What is a subset of a set (3)

Answer 3

-If A and B are two sets, A is a subset of B if every element of A is contained in B (A ⊆ B)
-If B contains at least one element which isn’t in A, A is a proper subset of B (A ⊂ B)
-A = B if A ⊆ B and B ⊆ A

Question 4

What is the intersection, union and empty set, and how can they be illustrated on a venn diagram (3,3,3)

Answer 4

-The intersection A n B is the set of all elements which belong to both A and B
-{x: x ∈ A and x ∈ B}
-On a venn diagram, this is the area in both A and B

-The union A u B is the set of all elements which belong to either A or/and B
-{x: x ∈ A and/or x ∈ B}
-On a venn diagram, this is the area in A or B or both

-The empty set Ø is the set consisting of no elements
-Ø = {}
-On a venn diagram, this is the area not in a circle

Question 5

What does it mean for 2 sets A and B to be disjoint (1)

Answer 5

-If 2 sets A and B have an empty intersection, A n B = Ø, and they are disjoint

Question 6

What does it mean to be commutative (1)

Answer 6

-All sets are commutative, as A n B = B n A

Question 7

What is the universal set (2,1)

Answer 7

-The universal set Ω is the set consisting of everything
-We consider every set to be a subset of Ω

-On a venn diagram, this is drawn outside the box consisting of the diagram

Question 8

What is the difference and complement of a set (4, 2)

Answer 8

-The difference A\B of two sets is the set considering every element of A which isn’t in B
-A\B = {x:x ∈ A and x ∉ B}
-In general, the difference is not commutative
-On a venn diagram, this is the area of A which isn’t in B

-The complement A’ of A is the difference Ω\A
-Everything which isn’t in A

Question 9

What is the cartesian product + example (2,2)

Answer 9

-The cartesian product of A and B, AxB is the set of ordered pairs of elements
-AxB = {(a,b): a ∈ A and b ∈ B}

-A {1, 2, 3}, B = {a, b}
-AxB = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

Question 10

How can we use the cartesian product to represent the plane (2)

Answer 10

-ℝ^2 = ℝxℝ = {(x,y): x, y ∈ ℝ}
-(could replace 2 with n and x,y with x, x1, …, xn)

Question 11

What is the distributive law, and how do you prove it (1, 1, 7, 7, 1)

Answer 11

-A u (Bnc) = (AuB) n (AuC)

-To prove formally, you have to use the fact that A=B if A ⊆ B and B ⊆ A

-First show A u (B n C) ⊆ (AuB) n (AuC)
-Suppose x ∈ A u (BnC)
-If x ∈ A, x ∈ (AuB) but also x ∈ (AuC)
-so x ∈ (AuB) n (AuC)
-If x ∈ BnC, x ∈ B and x ∈ C
-So, x ∈ (AuB) n (AuC)
-So, Au(BnC) ⊆ (AuB) n (AuC)

-Now show (AuB) n (AuC) ⊆ A u (BnC)
-Suppose x ∈ (AuB) n (AuC). So x ∈ AuB and x ∈ AuC
-Then x ∈ A or B and x ∈ A or C
-If x ∈ A, x ∈ A u (BnC)
-If x ∉ A, x ∈ B and x ∈ C, so x ∈ (BnC)
-Thenx ∈ A u (BnC)
-Thus, x ∈ Au(BnC) and thus (AuB) n (AuC) ⊆ Au(BnC)

-Therefore, A u (BnC) = (AuB) n (AuC)