\[ \newcommand{\tr}{\Rightarrow} \newcommand{\trs}{\tr^{\!\ast}} \newcommand{\rlnm}[1]{\mathsf{(#1)}} \newcommand{\rred}[1]{\xrightarrow{#1}} \newcommand{\rreds}[1]{\mathrel{\xrightarrow{#1}\!\!^*}} \newcommand{\cl}{\mathsf{Cl}} \newcommand{\pow}{\mathcal{P}} \newcommand{\matches}{\mathrel{\mathsf{matches}}} \newcommand{\kw}[1]{\mathsf{#1}} \newcommand{\andop}{\mathrel{\&\!\&}} \newcommand{\orop}{\mathrel{\|}} \newcommand{\ff}{\mathsf{false}} \newcommand{\tt}{\mathsf{true}} \newcommand{\abra}[1]{\langle #1 \rangle} \newcommand{\bnfnt}[1]{\abra{\small \textsf{#1}}} \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \newcommand{\first}{\mathsf{First}} \newcommand{\nullable}{\mathsf{Nullable}} \newcommand{\follow}{\mathsf{Follow}} \newcommand{\tm}[1]{\mathsf{#1}} \]

Basic Set Theory

You should ensure you properly understand the meaning of the following notation:

• The empty set $\emptyset$
• Set extension $\{x,y,z,\ldots\}$
• Set comprehension $\{ x \in S \mid P(x) \}$
• Binary union $X \cup Y$
• Binary intersection $X \cap Y$
• Difference $X - Y$
• Complement $X^c$
• Subset inclusion $X \subseteq Y$
• Set cardinality (number of elements) \(\lvert X \rvert\)
• Power set $\mathcal{P}(X)$

Predicates

A predicate on a set $A$ is a subset $U \subseteq A$.

We may think of a predicate $U$ as consisting of a set of (interesting, desirable, pertinent) elements of a bigger set $A$.

Example

We define the predicate $E \subseteq \mathbb{N}$ to be the set

\[E = \{ n \in \mathbb{N} \mid \text{ $n$ is even } \}\]

consisting of all even numbers.

Relations

Let $A$ and $B$ be sets.

The cartesian product of $A$ and $B$ is the set consisting of pairs $(a, b)$ of one element from $A$ and one element from $B$: \(A \times B = \{ (a, b) \mid a \in A \land b \in B \}\)

A relation from $A$ to $B$ is a subset $R \subseteq A \times B$ of the cartesian product.