Set Theory Flashcards
Covers the basics of set theory
what is the set B (stylised)?
binary numbers - {0,1}
why can sets with elements listed in a different order/with duplicates be considered equal?
a set is defined solely in terms of its members
A = B iff…
A ⊆ B and B ⊆ A
¬(A⊆B)
A ⊈ B
the universe of discourse consists of
all elements under consideration
what are the 3 properties of the subset relation?
reflexive, antisymmetric and transitive
describe how the subset relation is reflexive
A ⊆ A for all sets A
describe how the set relation is anti-symmetric
if a and b are related in both directions, they must be equal. e.g iff A ⊆ B and B ⊆ A, A = B
describe how the subset relation is transitive
if A ⊆ B and B ⊆ C, A ⊆ C
what is the least set with respect to inclusion?
the empty set since it is contained in any other set
how to use set builder notation to define B, the subset of A
B = { x ∈ A : x has property P }
write { Dan”, Felix } using set builder notation
{ x : x = Dan or x = Felix }
what is Russell’s paradox
the set of sets that do not contain themselves CANNOT exist in naive set theory
the importance of Russell’s paradox in set theory
it should not be possible to construct sets of all sets
two sets are disjoint if…
they have no elements in common
the intersection of two disjoint sets
the empty set
|A|
the cardinality of A
what is the inclusion-exclusion principle
|A U B| = |A| + |B| - |A ∩ B|
A \ B in set builder notation
{ x ∈ A : x ∉ B }
x ∈ { A \ B } iff
x ∈ A and x ∉ B
construct the set A’ using only the universe discourse and the set A
U \ A
P(A)
the set containing all subsets of A (including the empty set and itself)
a set of 4 elements has how many subsets
16
what trick can you use to figure out the number of elements in a powerset?
Pascal’s Triangle
