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
  • ⊃ ?????? (??????)  ???????? ??
    • Set: S = {a, b, c}
    • Set: T = {a, b}
    • S ⊃ T
  • ⊅ ??? ?????? (??????)  ???????? ??
    • Set: S = {a, b, c}
    • Set: Q = {a, b, c}
    • Set: W = {b, c, d}
    • Q ⊅ S
    • W ⊅ S
  • ⊇ ???????? ??
    • Set: S = {a, b, c}
    • Set: Q = {a, b, c}
    • Set: T = {a, b}
    • Q⊇S
    • T⊇S
  • ⊉ ??? ???????? ??
    • Set: S = {a, b, c}
    • Set: W = {b, c, d}
    • W⊉S

Set Operators:

  • ∩ ?????????????
    • Set: S = (a, b, c, d)
    • Set: T = (a, b, e, f)
    • S ∩ T = (c, d, e, f)
  • ∪ ?????
    • 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
  • a??????? ??????????
    • 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)
  • ∆ ????????? ????????ce
    • 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.
  • ?(?) 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.
  • ??????
    • 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.
  • ??????
    • 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.
  • ??????
    • 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

Leave a Reply

Your email address will not be published. Required fields are marked *