Sets and Formal Languages

A set is an unordered collection of distinct elements. Sets are fundamental to the mathematics of formal languages and computation.

Defining a set:

A = {1, 2, 3, 4, 5}          // List notation (roster notation)
B = {x | x is an even integer, 0 ≤ x ≤ 10}  // Set-builder notation
  = {0, 2, 4, 6, 8, 10}

Key set notation:

| Symbol | Meaning | Example | | --------------------- | ---------------------------------------------- | ------------------------------ | -------------------------------------------- | --- | ----------- | ---- | | $x\in S$ | $x$ is a member of set $S$ | $3\in \{1,2,3\}$ is True | | $x\notin S$ | $x$ is not a member of $S$ | $5\notin \{1,2,3\}$ is True | | $\varnothing$ or $\{\}$ | Empty set — contains no elements | $\varnothing =\{\}$ | | $\mathbb{N}$ | Natural numbers $\{0,1,2,3,\dots \}$ | $5\in \mathbb{N}$ | | $\mathbb{Z}$ | Integers $\{\dots ,-2,-1,0,1,2,\dots \}$ | $-3\in \mathbb{Z}$ | | $|S|$ | Cardinality (size/number of elements) of $S$ | $|\{a,b,c\}|=3$ |

Sets do not have duplicate elements: $\{1,2,2,3\}=\{1,2,3\}$.

Three fundamental operations on sets:

Union ($A\cup B$) — elements in $A$, $B$, or both:

$A\cup B=\{x|x\in A\text{ or }x\in B\}$

$\{1,2,3\}\cup \{3,4,5\}=\{1,2,3,4,5\}$

Intersection ($A\cap B$) — elements in both $A$ and $B$:

$A\cap B=\{x|x\in A\text{ and }x\in B\}$

$\{1,2,3\}\cap \{3,4,5\}=\{3\}$

Complement ($\overline{A}$ or $A^{\prime }$) — all elements NOT in $A$ (relative to the universal set $U$):

$\overline{A}=\{x|x\in U\text{ and }x\notin A\}$

If $U=\{1,2,3,4,5\}$ and $A=\{1,2,3\}$, then $\overline{A}=\{4,5\}$.

Universal set ($U$) — the set of all elements under consideration in a given context. Every other set in that context is a subset of $U$.

The Cartesian product $A\times B$ of two sets $A$ and $B$ is the set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$:

$A\times B=\{(a,b)|a\in A,b\in B\}$

Example:

$A=\{1,2\},B=\{x,y\}$ $A\times B=\{(1,x),(1,y),(2,x),(2,y)\}$

$|A\times B|=|A|\times |B|=2\times 2=4$.

Why it matters in computing: the Cartesian product defines transition tables for finite state machines. A transition function $\delta :Q\times \Sigma \to Q$ maps (state, input symbol) pairs to new states — $Q\times \Sigma$ is a Cartesian product.

A formal language is a set of strings defined over an alphabet.

Alphabet ($\Sigma$) — a finite, non-empty set of symbols. Examples:

• Binary alphabet: $\Sigma =\{0,1\}$
• Lowercase letters: $\Sigma =\{a,b,c,\dots ,z\}$
• DNA bases: $\Sigma =\{A,C,G,T\}$

String — a finite sequence of symbols from $\Sigma$. Examples over $\Sigma =\{a,b\}$:

• a, b, aa, ab, ba, bb, aab, …

Empty string ($\epsilon$) — the string with zero symbols. $|\epsilon |=0$.

${\Sigma }^{\ast }$ — the set of all possible strings over $\Sigma$, including $\epsilon$. This is an infinite set even when $\Sigma$ is finite.

Language ($L$) — any subset of ${\Sigma }^{\ast }$. Examples:

• $L_1=\{a,aa,aaa\}$ — a finite language
• $L_2=\{a^n{b}^n|n\ge 1\}$ — strings of $n$ a's followed by $n$ b's (infinite language)
• The set of all valid Python programs over the ASCII alphabet

AQA requires awareness of the following distinction:

Countable set — a set whose elements can be listed in a sequence (put into one-to-one correspondence with $\mathbb{N}$).

• Examples: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ (rationals), the set of all strings over any finite alphabet (${\Sigma }^{\ast }$)

Uncountable set — a set too large to be listed in any sequence; cannot be put into one-to-one correspondence with $\mathbb{N}$.

• Examples: $\mathbb{R}$ (real numbers), the set of all possible languages over an alphabet

Significance for computing:

• ${\Sigma }^{\ast }$ is countable — there are countably many possible programs
• The set of all languages over $\Sigma$ is uncountable — there are uncountably many possible problems
• Therefore, most problems cannot be solved by any program — there are more problems than programs

(Extra context — not required beyond AQA 7517 awareness level) This is formalized by Cantor's diagonal argument — the same technique that proves the set of real numbers is uncountable and underpins the proof that the halting problem is unsolvable.

1. Including duplicates in a set

Sets cannot contain duplicate elements. $\{1,2,2,3\}$ is the same as $\{1,2,3\}$. Listing duplicates in a set answer shows a misunderstanding of what a set is.

2. Confusing $\varnothing$ and $\{\varnothing \}$

$\varnothing$ is the empty set — it contains no elements; $|\varnothing |=0$. $\{\varnothing \}$ is a set containing one element (the empty set); $|\{\varnothing \}|=1$. These are different.

3. Confusing union and intersection symbols

$\cup$ (union) looks like a "U" — Union. $\cap$ (intersection) looks like an inverted U — the elements in common. Getting these backwards is a common notation error.

4. Treating ε as a character in the alphabet

$\epsilon$ is not a symbol in $\Sigma$ — it represents the absence of any symbol. The string $\epsilon$ has length 0. Adding it to a string leaves the string unchanged: $w\cdot \epsilon =w$.

5. Forgetting ε in ${\Sigma }^{\ast }$

${\Sigma }^{\ast }$ includes the empty string $\epsilon$. If the question asks for all strings of length 0 or more over $\{a,b\}$, the empty string must be included.