R. Muller
- Sets, Relations & Maps
- Orders
The Idea
-
Computer software is often required to keep track of "collections" of things.
-
Mathematicians have thought carefully about these collections, and know them as sets.
-
Software is also often required to keep track of the association between items from one set (the "keys") and another (the "values").
Basic Sets
-
A set is a collection of items with no duplicates.
Examples: A = {1, 2, 3} B = {Bob, Alice, Joe} N = {0, 1, 2, ...} natural numbers
-
NB: Only restriction on elements is identity.
Notation
- alpha
$\alpha$ , beta$\beta$ , gamma$\gamma$ , Gamma$\Gamma$ , delta$\delta$ , epsilon$\epsilon$ , tau$\tau$ , sigma$\sigma$ . - A, B, C, …, X, Y, Z for sets;
-
$\emptyset$ or {} for the empty set; - a, b, c, ... for elements of sets;
-
$a \in A$ means that$a$ is an element of set$A$ ; -
$(a_1, \ldots, a_n)$ is an n-tuple.
Variables and Quantifiers
-
x, y, z for variables (which vary over sets!)
-
$\forall x \in A$ . statementasserts that statement holds for every element of A. For example,
$\forall x\in{1, 2, 3}.x < 4$ means$1 < 4$ and$2 < 4$ and$3 < 4$ . The occurrence of$x$ adjacent to the quanitifer is called a binding occurrence of$x$ ; the occurrence of$x$ to the right of the dot is called an applied occurrence or use of$x$ . Note that we obtained$1 < 4$ by plugging in (or substituting)$1$ for$x$ in the statement$x < 4$ . -
$\exists x \in A$ . statementasserts that statement holds for some element of A.
Set Comprehensions
-
{ x | statement } means set of all x such that statement holds;
Example
Evens =
${ x \in \mathbb N \mid \exists y \in \mathbb N \mathrm{\ such\ that\ } x = 2y }$ or equivalently
Evens =
${ x \mid x \in \mathbb N \mathrm{\ and\ } \exists y \in \mathbb N \mathrm{\ such\ that\ } x = 2y }$
Basic Sets
- Notation:
- Subset :
$A \subseteq B$ means$\forall x \in A . x \in B$ ; - Set Equality :
$A = B$ means$A \subseteq B$ and$B \subseteq A$ .
- Subset :
Operations on Sets
-
Union :
$A_1 \cup \ldots \cup A_n = { a \mid a \in A_i\ \mathrm{for\ some}\ i \in {1, \ldots, n}}$ ; -
Intersection :
$A_1 \cap\ldots\cap A_n = { a \mid a \in A_i \mathrm{\ for\ every\ } i\in{1, \ldots, n}}$ ; -
Disjoint Union :
$A_1 + \ldots + A_n = { (i, a) \mid a \in A_i\mathrm{\ for\ some\ } i\in{1,\ldots, n} }$ ; -
Product :
$A_1 \times \ldots\times A_n = { (a_1,\ldots, a_n) \mid a_i \in A_i}$ ; -
Sequences : Let
$A$ be a set and let$\epsilon$ denote the empty sequence.$A^* = { w \mid w = \epsilon \mathrm{\ or\ } w = aw' \mathrm{\ with\ } a \in A \mathrm{\ and\ } w' \in A^*}$ Example:
${a, b}^* = {\epsilon, a\epsilon, b\epsilon, aa\epsilon, ab\epsilon, \ldots }$ Notes:
- This is an example of an inductive definition,
- Trailing $\epsilon$s are usually omitted so the set in the example above is written
${\epsilon, a, b, aa, ab, \ldots }$ .
-
Powerset : Let
$A$ be a set. Then the powerset of$A$ is$P(A) = { A' \mid A' \subseteq A}$ Example : P({1,2}) = {{}, {1}, {2}, {1, 2}};
Diversion: Russell's Paradox
-
Let
$\mathbf R = { A \mid A \not\in A}$ . The set of all non-self-containing sets. E.g.,${a} \in \mathbf R$ . Is$\mathbf R\in \mathbf R$ ? -
Assume that
$\mathbf R \not\in \mathbf R$ . Then$\mathbf R \in \mathbf R$ .-
Assume that
$\mathbf R \in \mathbf R$ . Then$\mathbf R \not\in \mathbf R$ . -
So
$\mathbf R \in \mathbf R \mathrm{\ iff\ } \mathbf R \not\in \mathbf R$ . Naive set theory is inconsistent.
-
Relations
-
$R$ is a(n n-ary) relation on sets$A_1, \ldots, A_n$ if$R \subseteq A_1 \times \ldots \times A_n$ . -
When
$R$ is an n-ary relation on sets$A_1, \ldots, A_n$ and$A_1 = \ldots = A_n$ we say that$R$ is an n-ary relation on$A_1$ ; -
When R is a finite set we say it is a finite relation.
Binary Relations
Let
Domain of Definition: DomDef(R) =
Example Relations
A = {1, 2, 3}, B = {Bob, Alice}
-
R1 = A x B = {(1, Bob), (1, Alice), (2, Bob), (2, Alice), (3, Bob), (3, Alice)}
-
R2 = {}
-
R3 = {(1, Bob), (3, Alice)} // e.g., DomDef(R3) = {1, 3}
-
R4 = {(1, Alice), (2, Alice), (3, Alice)}
Partial Maps (aka Partial Functions)
Let
R1 is not a partial map but all of R2, R3 and R4 are partial maps.
Notation:
- We usually use f, g, h, ... for partial maps;
- We use the notation
$f(a)$ to denote the unique$b$ such that$(a, b)\in f$ . Note that this notation isn't defined if there is no$b$ such that$(a, b)\in f$ .
Total Map
Let
Function Set Constructors
-
The set of all partial maps from A to B: A -o-> B = { f | f is a partial map from A to B }
-
The set of all total maps from A to B: A --> B = { f | f is a total map from A to B }
Examples
{1, 2} --> {Bob, Alice} = { {(1, Bob), (2, Bob)},
{(1, Alice), (2, Alice)},
{(1, Bob), (2, Alice)},
{(1, Alice), (2, Bob)}
}
{1, 2} -o-> {Bob, Alice} = {1, 2} --> {Bob , Alice}
U
{ {},
{(1, Bob)},
{(1, Alice)},
{(2, Bob)},
{(2, Alice)}
}
Predicates
-
Let Bool = {true, false};
= {void} + {void} = {(void, 0), (void, 1)}
-
P is a predicate on A if P is a map from A to Bool.
-
Example: >2 is a unary predicate on N:
2 = {(0, false), (1, false), (2, false), (3, true), ...}
Implementing Maps
Finite maps (from A --> B, or A -o-> B) implemented with a data structure such as hash table, e.g., Java's HashMap.
-
The set of "keys" in A must be identifiable (see equivalence below)
-
Other efficient data structures can be used if A is totally ordered
Preorder
-
Let
$R$ be a relation on$A$ .$R$ is reflexive iff$\forall x \in A . (x, x) \in R$ ; -
Let
$R$ be a relation on$A$ .$R$ is transitive iff$\forall x, y, z \in A. \mathrm{\ If\ } (x,y) \in R \mathrm{\ and\ } (y,z) \in R \mathrm{\ then\ } (x,z) \in R$ . -
A relation that is both reflexive and transitive is called a preorder.
Partial Orders
-
Let
$R$ be a binary relation on$A$ .$R$ is symmetric iff$\forall x, y \in A . \mathrm{\ if\ } (x, y) \in R \mathrm{\ then\ } (y, x) \in R$ ; -
Let
$R$ be as above.$R$ is antisymmetric iff$\forall x, y \in A. \mathrm{\ if\ } (x, y) \in R \mathrm{\ and\ } (y, x) \in R \mathrm{\ then\ } x = y$ . -
A symmetric preorder is called an equivalence relation.
-
An antisymmetric preorder is called a partial order.
Partially Ordered Sets
If R is a reflexive, antisymmetric and transitive binary relation on A, we say that
- R is a partial order on set A
- The set A is partially ordered by R
- A is a partially ordered set (not mentioning R)
- A is a poset
Notation
-
If set
$A$ is partially ordered by$R$ , we write$(A, R)$ or more often$(A, \le_R)$ or$(A, \le)$ if R is implied by context; -
For
$a, a' \in A$ , instead of writing$(a, a') \in R$ we usually write$a\le_R a'$ or$a\le a'$ if R is implied. -
If
$a \le a'$ and$a != a'$ we write$a < a'$ .
Examples
A = {Bob, Alice}, R1 = {(Bob, Bob), (Alice, Alice), (Bob, Alice)}
Hasse Diagram of a Relation
Alice
|
Bob
Examples
A = P({Bob, Alice, Joe}) = { {},
{Bob}, {Alice}, {Joe},
{Bob, Alice}, {Bob, Joe}, {Alice, Joe},
{Bob, Alice, Joe}
}
R2 =
{Bob, Alice, Joe}
/ | \
{Bob, Alice} {Bob, Joe} {Alice, Joe}
| /\ /\ |
{Bob} {Alice} {Joe}
\ | /
{}
Total Order
-
Let R be a partial order on A. R is a total order on A iff
$\forall x, y \in A . \mathrm{\ either\ } (x, y) \in R \mathrm{\ or\ } (y, x) \in R$ . -
Example :
$(\bf N, \le)$ .
Lexicographic Ordering
Let
$w \le_{A^} w'$ iff either $w = \epsilon$ or $w = av$, $w' = a'v'$ and either $a \lt_A a'$ or $a =A a'$ and $v \le{A^} v'$.
Example:
Let A = {p, q}. Then A* = {e, p, q, pq, ppq, … } and $pq \le_{A^} ppq$ because $a = p$, $v = q$, $a' = p$, $v' = pq$, $a = a'$ and $v \le_{A^} v'$ because
Note: If
Summary
In summary: we have type constructors: union, intersection, sum, product, sequence, -o-> and —>. Of these, sum, product, sequence, -o-> have direct computational interpretations.