Logic (PHIL 2080, COMP 2620, COMP 6262) Bonus Material: Recap on Set Notation
Logic (PHIL 2080, COMP 2620, COMP 6262)
Bonus Material: Recap on Set Notation
Pascal Bercher
Planning & Optimization
Yoshihiro Maruyama
Logic
Intelligent Agents
College of Engineering and Computer Science
the Australian National University (ANU)
25 February 2021
Set Notation
Set Notation
Pascal Bercher and Yoshihiro Maruyama 1.5
Set Notation
Sets versus Lists
We will heavily base upon sets.
Sets are invariant against repetition.
• E.g., {a, a, b, b, b, c} = {a, b, c}.
Sets are invariant against re-ordering.
• E.g., {a, b, a, b, c, b} = {a, a, b, b, b, c}.
• Thus, we also get {a, b, a, b, c, b} = {a, a, b, b, b, c}
= {a, b, c} = {a, c, b}
= {b, a, c} = {b, c, a}
= {c, a, b} = {c, b, a}
Therefore, sets are fundamentally different from lists!
• Lists are also called sequences or tuples.
• E.g., the list (a, b, c) is different from both (a, c, b) and (a, a, b, c)
Pascal Bercher and Yoshihiro Maruyama 2.5
Set Notation
Set Notation
The empty set {} is usually always denoted by the symbol ∅.
In contrast, the empty list (i.e., empty sequence) is denoted by ε.
Let X be a finite set. Then, 2X denotes its “power set” that
contains all subsets.
• E.g., if X = {a, b, c}, then
2X = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, ∅}
The “cardinality” of a set X is the number of its elements and
denoted by |X |. Cardinality is not recursive!
• E.g., if X = {a, b, c}, then |X | = 3.
• Regarding non-recursiveness: if, e.g., X = {{a, b}, c}, then
|X | = 2, because it has two elements, not three.
Note that for all possible X it holds that |2X | = 2|X |.
• E.g., if X = {a, b, c}, then |2X | = 2|X | = 23 = 8
Pascal Bercher and Yoshihiro Maruyama 3.5
Set Notation
Set Notation, cont’d
We write a ∈ X if a is contained in X , i.e., an element of X . We
say a /∈ X if a is not contained in X . Again, this is not recursive!
• E.g., if X = {{a, b}, c}, then only {a, b} ∈ X and c ∈ X , but
a /∈ X and b /∈ X . Also {c} /∈ X .
We write Y ⊆ X if Y is a (not necessarily strict) subset of X . We
write Y * X if this does not hold.
• E.g., {a, b, c} ⊆ {a, b, c} (in fact, X ⊆ X for all sets X ).
• E.g., {a, c} ⊆ {a, b, c}.
• E.g., if X = {{a, b}, c}, then {c} ⊆ X and {{a, b}} ⊆ X ,
but {{a, c}} * X and {a, b} * X .
Let X ,Y , Z be sets. Then X × Y × Z is the cartesian product of
these sets. It’s the set of tuples with one element from each set.
• Formally, X × Y × Z = {(x , y , z) | x ∈ X , y ∈ Y , z ∈ Z}
• One normally uses standard math notation, e.g., X 2 = X × X . We
use X n for exactly n times X , and X∗ for all numbers in N ∪ {0}.
Pascal Bercher and Yoshihiro Maruyama 4.5
Set Notation
Set Operations
X ∪ Y denotes the set union of X and Y , i.e., X ∪ Y contains all
elements that occur in any of those sets.
• Formally: X ∪ Y = {z | z ∈ X or z ∈ Y}
X ∩ Y denotes the set intersection, i.e., X ∩ Y contains all
elements that are contained in both sets.
• Formally: X ∩ Y = {z | z ∈ X and z ∈ Y}
X \ Y denotes the set subtraction, i.e., X \ Y contains all
elements that are contained in X , but not (“minus the ones”) in Y .
• Formally: X \ Y = {z ∈ X | z /∈ Y}
Pascal Bercher and Yoshihiro Maruyama 5.5
Set Notation