# 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