Set Theory Lecture 2 Flashcards
What is a list in set theory?
An ordered sequence of elements.
Give an example of a list.
DigitList := ⟨0,1,2,…,9⟩.
How does a list differ from a set?
A list is ordered and can contain duplicates, while a set is unordered and contains unique elements.
What is a Cartesian product of two sets?
A × B := {⟨a,b⟩ | a ∈ A and b ∈ B}, the set of all ordered pairs from A and B.
Give an example of a Cartesian product.
{1,2} × {a,b} = {⟨1,a⟩, ⟨1,b⟩, ⟨2,a⟩, ⟨2,b⟩}.
What is the Cartesian product of three sets?
A × B × C := {⟨a,b,c⟩ | a ∈ A, b ∈ B, c ∈ C}.
What is the formula for the size of a Cartesian product?
(A × B) = #A · #B.
What is the number of elements in Dates := DayNums × MonthNums if #DayNums=31 and #MonthNums=12?
Dates = 31 × 12 = 372.
What is a relation in set theory?
A relation R is a subset of a Cartesian product of sets.
What is a binary relation?
A relation of type A × B or A² within a set A.
Give an example of a binary relation.
IsBrotherOf := {⟨x, y⟩ | x is the brother of y} ⊆ People².
What is an alternative notation for binary relations?
Instead of ⟨x,y⟩ ∈ R, we can write x R y.
How are relations represented visually?
Using directed graphs or matrices.
What does the matrix representation of a relation show?
It represents connections between elements as 1 (true) or 0 (false).
What is the inverse of a relation R?
R⁻¹ := {⟨x, y⟩ | ⟨y, x⟩ ∈ R}.
Give an example of an inverse relation.
If LivesIn = {⟨Jan, Amsterdam⟩}, then (LivesIn)⁻¹ = {⟨Amsterdam, Jan⟩}.
What does inverting a relation do in its graph representation?
It reverses the direction of all arrows.
What is the composition of two relations R and S?
R ∘ S := {⟨x, z⟩ | there exists y such that x S y and y R z}.
Give an example of relation composition.
IsFriendOf ∘ IsUncleOf = {⟨x, z⟩ | x is an uncle of a friend of z}.
Why does order matter in relation composition?
Different orders of composition produce different results, e.g., IsMarriedTo ∘ IsParentOf ≠ IsParentOf ∘ IsMarriedTo.
What is the associativity property of relation composition?
(R ∘ S) ∘ T = R ∘ (S ∘ T).
What is the inverse of a composite relation?
(R ∘ S)⁻¹ = S⁻¹ ∘ R⁻¹.
What is reflexivity in a relation?
A relation R is reflexive if for all x, x R x holds.
What is symmetry in a relation?
A relation R is symmetric if for all x, y: x R y → y R x.
What is transitivity in a relation?
A relation R is transitive if for all x, y, z: x R y and y R z → x R z.
What is anti-symmetry in a relation?
A relation R is anti-symmetric if for all x, y: x R y → ¬(y R x).
Is ‘IsFriendOf’ reflexive, transitive, symmetric, or anti-symmetric?
Symmetric but not necessarily reflexive, transitive, or anti-symmetric.
Is ‘IsParentOf’ reflexive, transitive, symmetric, or anti-symmetric?
Transitive and anti-symmetric, but not reflexive or symmetric.
Is ‘IsDescendantOf’ reflexive, transitive, symmetric, or anti-symmetric?
Transitive but not reflexive, symmetric, or anti-symmetric.
What is the key takeaway from the lecture?
Understanding lists, Cartesian products, relations, relation composition, and properties like reflexivity, symmetry, transitivity, and anti-symmetry.
