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
what is a family of sets F?
a collection of sets (where every element in F is a set)
what is the union of the family of sets F?
{ x : x ∈ A for some A ∈ F }
what is the intersection of a family of sets?
{ x : x ∈ A for all A ∈ F }
both the union and intersection of a family of sets are..
sets of elements (arbritrary x’s)
Alternative way to write U F if F = {A, B, C }
U{A, B, C}
if F = {A,B,C}, what is U F shorthand for?
A U B U C
U{A, B} in written english
the union of all sets within the family {A,B}
what is an ordered pair?
a pair of objects with a first coordinate and a second coordinate
(a,b) ∈ A ✕ B iff
a ∈ A and b ∈ B
two ways to denote the cartesian product across all real numbers
R ✕ R or R^2
R ✕ R denotes the set of..
points in the xy plane
key value pairs are always ordered pairs from..
the Cartesian product Keys ✕
Values
A^n corresponds to
the cartesian product of n copies of the set A (e.g an R vector over 4)
the number is elements in a product is
the product of each individual set’s cardinality
|A ✕ {}|
A ✕ {} |
0
A ✕ {}
{}
X ⊆ Y
Hence X\Y =
{}
X ⊆ Y
Hence X’ U Y =
The universal set
from the identity (P ⇒ Q) ⇔ (¬P ∨ Q), we get the identity P ⊆ Q = …
P’ U Q = universe set
property of sets that corresponds to the contrapositive law
A ⊆ B iff A’ ⊆ B’
