Fundamentals

Fundamental mathemetical structures

Sets #

Set: an unordered collection of distinct elements.

• Notation using '$\{$' and '$\}$':
• Member of: $A \in B$
• Empty set: $\emptyset = \{ \}$
• Equality: $A = B$
  • A and B contain the same elements
  • $A = B$
  • Note: duplicate items don't matter: $\{ 1, 2, 2 \} = \{ 1, 2 \}$
• Subsets: $A \subseteq B$, each element of $A$ is also an element of $B$
  • For every set S, we have $S \subseteq S$ and $\emptyset \subseteq S$
  • Proper subset: $C \subset D$ and not $C \neq D$
• Cardinaliy (size): $|S|$ count of elements in a set
  • Can be finite or infinite

Set Operations #

• Union: $A \cap B$, set of elements that are both in $A$ and $B$
  • Disjoint: sets that have no elements in common
• Intersection: $A \cup B$, set of elements that are either in $A$ or $B$
• Difference: $A \setminus B = A - B$, set of all elements in $A$ but not in $B$
• Complement: $\overline{A} = U \setminus A$, all elements that are not in $A$
• Symmetric difference: $A \oplus B$, set of elements in A or B, but not to both in A and B (exclusive-or)
• Powerset: $P(S)$, the set of all subsets of $S$
  • Example:
    • $A$ = $\{ 1, 2, 3 \}$
    • $P(A)$ = $\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$
• Partition: a set consisting of non-empty subsebsets (blocks) of a set
  • The intersection of all blocks covers the set
  • All blocks are disjoint

Sets of numbers #

• $\mathbb{N} = \{ 0, 1, 2, 3, ... \}$, natural numbers
• $\mathbb{Z} = \{ ..., -3, -2, -1, 0, 1, 2, 3, ... \}$, integers
• $\mathbb{Q} = \{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \neq 0 \}$ rational numbers
• $\mathbb{R}$, real numbers: rational numbers and irrational numbers like $\sqrt{2}$, $\pi$ or $e$
• $\mathbb{C}= \{ a + bi \mid a, b \in \mathbb{R}\}$, complex numbers, $i^2 = -1$

Sequences #

Sequence: a list of objects in definite order

• Indexed list: $1, 2$ $s_0 = 1$, $s1 = 2$
• Notation
  • Suggestive: $s = a, b, c, ...$
  • Recursive defenition
    • Starting value: $s_0 = 3$
    • Resursive value: $s_n = s * s_{n-1} + 7$
  • Explicit defenition:
    • $S_n$ as a function of $n$
    • $s_n= n^2$
• Characteristic function: computer representation
• Countable or uncountable
  • A set is countable if all elements can be written as a sequence.
  • Each finite set is countable

Strings #

• Alphabet non-empty finite set $\Sigma$ of letters
• Word/string over $\Sigma$: finite sequence of letters form alphabet $\Sigma$
  • Writting without commas
  • $\Sigma^*$ the set of all words over $\Sigma$
• Empty word/string: $\epsilon$
• (Formal) Language $L \subseteq \Sigma^*$: set of words
• Concatenation $w_1 \cdot w_2$: strings/words added to each other
  • Language concatenation: $L \cdot M = \{ s \cdot t \mid s \in L \land t \in M \}$
• Regular expression: expression to match a subset of $\Sigma^*$

Intervals #

• Inclusive $[a, b]$: $a$ and $b$ are included in the interval
• Exclusive $(a, b)$: $a$ and $b$ are NOT included in the interval

Can be combined like this: $[a, b)$ or $(a, b]$

Matrices #

Boolean Matrices #

• Join $\lor$: binary OR
• Meet: $\land$: binary AND
• Boolean matrix product: like normal matrix multiplication but instead $\max$ the values