# 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\}\}$

- Example:
**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