Formal Methods 101: Set Theory
Introduction:
Set Theory involves sets which are unordered lists.
Ex. Set: S = (a, b, c)
Note: S is the set and a, b, c are the elements of the set.
All members of a set must be of the same type. (Note: because set can have complex types (sets themselves); this can be circumvented by the properties of the complex types.)
Set Membership:
∅ element of
∅ = {}
∅ denotes the empty set
∈ element of
Set: S = {a, b, c}
a ∈ S
∉ not element of
Set: S = {a, b, c}
d ∉ S
⊂ proper (strict) subset of
Set: S = {a, b, c}
Set: T = {a, b}
T ⊂ S
⊄ not proper (strict) subset of
Set: S = {a, b, c}
Set: Q = {a, b, c}
Set: W = {b, c, d}
Q ⊄ S
W ⊄ S
⊆ subset of
Set: S = {a, b, c}
Set: Q = {a, b, c}
Set: T = {a, b}
Q ⊆ S
T ⊆ S
⊈ not subset of
Set: S = {a, b, c}
Set: W = {b, c, d}
W ⊄ S
⊃ superset of (strict)
Set: S = {a, b, c}
Set: T = {a, b}
S ⊃ T
⊅ not superset of (strict)
Set: S = {a, b, c}
Set: Q = {a, b, c}
Set: W = {b, c, d}
Q ⊅ S
W ⊅ S
⊇ superset of (not strict)
Set: S = {a, b, c}
Set: Q = {a, b, c}
Set: T = {a, b}
Q⊇S
T⊇S
⊉ not superset of (not strict)
Set: S = {a, b, c}
Set: W = {b, c, d}
W⊉S
Set Operators:
∩ disjoint
Set: S = (a, b, c, d)
Set: T = (a, b, e, f)
S ∩ T = (c, d, e, f)
∪ union
Set: S = (a, b, c, d)
Set: T = (a, b, e, f)
S ∪ T = (a, b)
\ difference (relative complement)
S = (a, b, c, d)
Set: T = (a, b, e, f)
S \ T = (c, d)
Note: (c, d) is the relative complement
T \ S = (e, f)
Note: (c, d) is the relative complement
absolute complement
Set: S = (a, b, c, d, e, f)
Set: T = (a, b)
Set: W = (c, d)
T ⊂ S
T ⊂ W
The absolute complement is S \ (? ∪ W) = (e, f)
∆ symmetric difference
Set: S = (a, b, c, d)
Set: T = (a, b, e, f) “(S \ ” ?)∪ (T \ S) = (c, d, e, f
X Cartesian product
Set: S = (a, b, c)
Set: T = (d, e, f)
S X T = ((a, d), (a, e), (a, f), (b, d), (b, e), (b, f), (c, d), (c, e), (c, f))
T X S = ((d, a), (e, a), (f, a), (d, b), (b, e), (b, f), (c, d), (c, e), (c, f))
Note: The Cartesian product operator produces a set of all possible ordered pairs between two sets.
P(S) Power set
Set: S = (a, b)
P(S) = ((a, b), (a), (b), ∅)
Note: The Power set of S produces the set of all subsets sets including the empty subset.
between two sets.
Cardinality
Set: S = (a, b)
The cardinality of set S is 2
Note: The carnality of a set is the number of members in the set.
Insert
Set S = (a, b, c)
Insert(S, d) returns S = (a, b, c, d)
The Insert operator (i.e. Insert(Set, element)) adds a member to a set.
Delete
Set S = (a, b, c)
Delete(S, a) returns S = (b, c)
The Delete operator (i.e. Delete(Set, element)) removes a member from a set.
Lookup
Set S = (a, b, c)
Lookup(S, c) returns TRUE
Lookup(S, d) returns FALSE
The Lookup operator (i.e. Lookup(Set, element)) determines if a set contains a specific member.
Common Sets:
ℕ
The set of all natural numbers (0, 1, 2, 3, 4, 5….)
ℤ
The set of all integers (….-3, -2, -1, 0, 1, 2, 3…)
ℚ
The set of all rational numbers
ℝ
The set of all real numbers
