# 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}
• TS
• ⊄ not proper (strict) subset of
• Set: S = {a, b, c}
• Set: Q = {a, b, c}
• Set: W = {b, c, d}
• QS
• WS
• ⊆ 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}
• WS
• ⊃ 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)
• 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 an 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