Random terminology moment

  • iff is an abreviation for if and only if

Strings

When all the sets in a Cartesian product are the same

  • We write $A^n = A \times A \times A \times … \times A$ (n times)
  • We call the element of strings of length $n$ over set $A$
  • For arbitrary length string over $A$ we write $A^+$:
    • $A^+ = A^1 \cup A^2 \cup A^3 \cup …$
  • A string of length $0$ is an empty sequence which we usually denote by $\epsilon$.
  • We define $A^0 = {\epsilon}$
  • $A^*$ is the set of all strings over $A$ including the empty string.
  • $A^* = A^0 \cup A^+$

Examples

  • $(1, 4, 6, 25), (1, 2, 3), (18)$ are strings over $\mathbb{N}$
  • ‘cat’, ‘dog’, ‘bat’, ‘hat’, ‘jam’ are strings of length $3$ over the English alphabet
    • Note that we don’t write it as $(‘c’, ‘a’, ’t’)$ for convenience
  • ‘001011101’ is a string of length $9$ over ${0, 1}$

Bit Strings

  • We call the set $\mathbb{B} = {0, 1}$ - set of “bits”
  • Elements of $\mathbb{B}^*$ are called bit strings
  • Bit strings are useful to store information

Storage

  • Let $S$ be a finite set of cardinality $n$
  • Let $s_1, s_2, …, s_n$ be the elements of set $S$ in a particular order
  • Let $A \subseteq S$.
  • We can define the bit string $b_A = (b_1, b_2, …, b_n)$ by putting, for every $i = 1, …, n$: $b_i = 1 \textrm{ iff } s_i \in A$

Examples

\[ S = \{1, 2, 3\}\\ A = \{1, 3\}\\ \\ b_A = (1, 0, 1) \]
\[ S = \{1, 3, 5, 7, 9, 11\}\\ b_\left\{3, 7\right\} = (0, 1, 0, 1, 0, 0)\\ \\ b_\left\{1, 7, 9\right\} = (1, 0, 0, 1, 1, 0) \]

Subsets

Every bit string $b$ defines a subset of $S$ with elements in order $s_1, … s_n$
$b_A = (b_1, b_2, … b_n)$ defines the subset:

\[ A = \{s_i | b_i = 1\} \]

Bit String Maths

  • Bit strings are useful because binary operations can be used to calculate things such as unions and intersections

Intersection

Intersection is the equivalent of performing a binary AND on two or more bit strings

\[ \begin{aligned} b_A &= &(0, 1, 1, 0, 1, 0)\\ b_B &= &(1, 0, 1, 1, 1, 0)\\ b_\left\{A \cap B\right\} &= &(0, 0, 1, 0, 1, 0) \end{aligned} \]

Need to prove: $b_C[i] = 1 \textrm{ iff } s_i \in A \cap B$

\[ \begin{aligned} b_{A \cup B}[i] = 1 & \textrm{ iff } b_A[i] * b_B[i] = 1\\ & \textrm{ iff } b_A[i] = 1 \textrm{ and } b_B[i] = 1\\ & \textrm{ iff } s_i \in A \textrm{ and } s_i \in B\\ & \textrm{ iff } s_i \in A \cap B\\ \end{aligned} \]

Union

Union is the equivalent of performing a binary OR on two or more bit strings

\[ \begin{aligned} b_A &= &(0, 1, 1, 0, 1, 0)\\ b_B &= &(1, 0, 1, 1, 1, 0)\\ b_\left\{A \cap B\right\} &= &(1, 1, 1, 1, 1, 0) \end{aligned} \]

Need to prove: $b_C[i] = 1 \textrm{ iff } s_i \in A \cup B$

\[ \begin{aligned} b_{A \cup B}[i] = 1 & \textrm{ iff } b_A[i] = 1 \textrm{ or } \left(b_A[i] = 0 \textrm{ and } b_B[i] = 1\right)\\ & \textrm{ iff } b_A[i] = 1 \textrm{ or } b_B[i] = 1\\ & \textrm{ iff } s_i \in A \textrm{ or } s_i \in B\\ & \textrm{ iff } s_i \in A \cup B\\ \end{aligned} \]

Infinite Sets

  • What if the set $S$ is infinite?
  • We cannot work with $B \times B \times …$
  • When $S$ is finite, a bit string $(b_1, b_2, …, b_n)$ maps every $s_i \in S$ to an element of $B$
  • This can be generalised to the case where $S$ is infinite by defining a mapping from $S$ to $B$.

Mappings

Each mapping $f$ defines the subset:

\[ \{s \in S | f(s) = 1\} \]

And vice versa, each subset $A$ of $S$ defines the mapping:

\[ f_A(s) = 1 \textrm{ iff } s \in A \]

Example

  • The bit mapping $\mathbb{N}$ is defined by is_even$(n) = 1 \textrm{ iff } n \textrm{ is even}$ defines the subset of even numbers
  • As a subset of $\mathbb{Z}$, the set $\mathbb{N}$ is defined by is_nat$(z) = 1 \textrm{ iff } z \geq 0$
  • There are as many subsets on a set $S$ as there are mappings from $S$ to $B$