Mathematical Foundations¶

This section reviews the mathematical vocabulary used throughout the course. These are not new ideas — you have seen most of them in Discrete Mathematics — but the ToC framing is worth making explicit.

Sets¶

A set is an unordered collection of distinct objects. The two defining properties are:

• Order does not matter: \(\{1, 2, 3\} = \{3, 2, 1\}\)
• Duplicates do not matter: \(\{1, 2, 2, 3\} = \{1, 2, 3\}\)

Sets can be described by listing elements, or by a defining property:

The empty set is written \(\emptyset\) or \(\{\}\).

Power Set¶

The power set of \(A\), written \(\mathcal{P}(A)\) or \(2^A\), is the set of all subsets of \(A\).

Example: If \(A = \{1, 2, 3\}\), then:

Sequences and Tuples¶

A sequence is an ordered list of objects where both order and duplicates matter:

• \((1, 2, 3) \neq (3, 2, 1)\) — order matters
• \((1, 2, 3) \neq (1, 2, 3, 3)\) — duplicates matter

A tuple is a finite sequence. Tuples of specific sizes have conventional names:

Cartesian Product¶

The Cartesian product (or cross product) of sets \(A_1, A_2, \ldots, A_k\) is the set of all \(k\)-tuples \((a_1, a_2, \ldots, a_k)\) where \(a_i \in A_i\):

Example: Let \(A = \{\text{Tea, Coffee}\}\), \(B = \{\text{Toast, Eggs}\}\), \(C = \{\text{Apple, Banana}\}\). Then \(A \times B \times C\) contains all 8 triples such as \((\text{Tea, Toast, Apple})\), \((\text{Coffee, Eggs, Banana})\), and so on.

The size of a Cartesian product is:

Functions¶

A function is a rule that assigns to each element of the domain exactly one element of the range:

meaning \(f\) maps domain \(D\) to range \(R\), with \(f(\text{input}) = \text{output}\) where \(\text{input} \in D\) and \(\text{output} \in R\).

The domain can be a Cartesian product, giving functions of multiple arguments:

The arity of such a function is \(n\) (the number of arguments).

Graphs¶

A graph is an ordered pair \(G = (V, E)\) where \(V\) is a finite set of vertices (nodes) and \(E\) is a set of edges.

• Undirected graph (no self-loops): \(E \subseteq \big\{\, \{u, v\} \mid u, v \in V,\ u \neq v \,\big\}\)
• Directed graph (digraph): \(E \subseteq \big\{\, (u, v) \mid u, v \in V \,\big\}\) — here order matters, so \((u, v) \neq (v, u)\)

We use directed graphs extensively when drawing state transition diagrams for automata.

Closure¶

Closed Under an Operation¶

A set \(A\) is closed under an operation \(\circ\) if applying \(\circ\) to any two members of \(A\) always produces another member of \(A\):

Example: The natural numbers \(\mathbb{N}\) are closed under addition (\(3 + 5 = 8 \in \mathbb{N}\)) but not under subtraction (\(3 - 5 = -2 \notin \mathbb{N}\)).

Closure of a Set¶

The closure of a set \(S\) under a rule or operation is the smallest superset of \(S\) that is closed under that rule — obtained by repeatedly applying the rule until no new elements can be generated.

Examples:

• The closure of \(\{0, 1\}\) under addition is \(\mathbb{W}\) (the whole numbers).
• The closure of \(\{-1, 1\}\) under addition is \(\mathbb{Z}\) (all integers).