###### tags: `離散數學`

:::info
[回共筆首頁](https://hackmd.io/zrsmsRtEQ-OrnGslDxT0NQ)
[回科目首頁](https://hackmd.io/OwMjUy0fRq2kEuCRiMwtkQ)
:::

# 2. Basic Structures: Sets, Functions, Sequences, Sums and Matrices

## Section 2.1: Sets
### Sets
- set => unordered collection of object
- elements/members => the objects in a set
- $a \in A$ => denotes that a is an element of the A

### Roster Method
- 順序不重要
- 數量不重要
- 當set的elements有規律時，可以用刪節號(Elipses)表達部分elements

### Some Important Sets

### Interval Notation
- closed interval $[a,b]$
- open interval $(a,b)$

### Universal Set and Empty Set
- Universal Set U => containing everything currently under consideration
- Empty set => set with no elements. Symbolized $\emptyset$ or $\{\}$

:::danger
$\emptyset$ => $\{\}$ 裡沒有東西
$\{\emptyset\}$ => $\{\}$ 裡有一個空集合
:::

### Set Equality
- Definition: Two sets are equal if and only if they have the same elements.
- $A = B$
- Example
- $\{1,3,5\}$ = $\{3,5,1\}$
- $\{1,5,5,5,3,3,1\}$ = $\{1,3,5\}$

### Subsets
- Definition: The set A is a **subset** of B, if and only if every element of A is also an element of B.
- Notation: $a \subseteq B$ => A is subset of the set B
- $a \subseteq B$ hold if and only if $\forall x(x \in A \implies x \in B)$ is true.
- 若A集合是空集合，則$x \in A$ 永遠為False，$(x \in A \implies x \in B)$永遠為True
- A是B的子集合，有可能A集合裡面的所有元素就剛好等於B集合

:::info
若要證明$A = B$，則要同時證明$A \subseteq B$ 和 $B \subseteq A$為True，互相為對方的子及合，代表$A = B$
:::

### Proper Subsets
- Definition: If $A \subseteq B$, but $A \neq B$, then we say A is a **proper subset** of B, denoted by $A \subset B$.
- $\forall x(x \in A \implies x \in B) \wedge \exists x(x \in B \wedge x \notin A)$
- A裡面的所有的元素都屬於B集合，且有些B集合的元素，不在A集合裡面

### Set Cardinality => 成員數量的值
- Definition: If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is **finite**. Otherwise it is **infinite**.
- Definition: The **cardinality** of a finite set A, denoted by $\mid A \mid$, is the number of (distinct) elements of A.
- Examples:
1. $\mid$ $\emptyset$ $\mid$ $=0$ 空集合裡面就是沒有東西，所以Cardinality就是0
2. $\mid$ $\{$ $\emptyset$ $\}$ $\mid$ $=1$ 有一個集合裡面有一個空集合，所以Cardinality就是1

### Power Sets
- Definition: The set of all subsets of a set A, denoted $P(A)$, is called the **power set** of A.
- Example: If $A = \{ a,b \}$ then $p(A) = \{$ $\emptyset$ $,\{ a \}, \{b\}, \{a,b\}\}$
- n個element的集合，power set的Cardinality會是2的n次方

### Tuples
- Ordered

### Cartesian Product
- Definition: The **Cartesian Product** of sets Aand B, denoted by $A \times B$ is the set of ordered pairs (a,b) where $a \in A$ and $b \in B$.
- $A \times B = \{(a,b)\mid a \in A \wedge b \in B \}$
- Example:
- $A = \{ a,b \} , B = \{1,2,3\}$
- $A \times B = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}$

## Section 2.2: Set Operations
### Set Operations
- Union
- 聯集
- $A \cup B = \{ x | x \in A \lor x \in B \}$
- Intersection
- 交集
- $A \cap B = \{ x | x \in A \land x \in B \}$
- Complementation
- 補數
- $\overline A = \{ x \in U | x \notin A \}$
- Difference
- $A - B = \{ x | x \in A \land x \notin B \} = A \cap \overline B$

### Symmetric Difference

### Set Identities (只列出重要的)
- Absorption laws

### Generalized Unions and Intersections

## Section 2.3: Functions
### Functions
- Sometimes called **mappings** or **transformations**
- function $f$ from A to B, denoted $f:A \implies B$
- $f:A \implies B$ can also be defined as a subsets of $A \times B$
- $f$ from A to B contains one
- only one ordered pair $(a,b)$ for every element $a \in A$
---
- We say $f$ **maps** A to B or $f$ is a **mapping** from A to B.
- A is called the **domain** of $f$.
- B is called the **codomain** of $f$.
- If $f(a) = b$
- then b is called the **image** of a under $f$.
- a is called the **preimage** of b.
- The **range** of $f$ is the set of all images of points in A under $f$. We denote it by $f(A)$

### Injections
- one-to-one
- injective
- $f(a) = f(b)$ inplies that $a = b$ for all a and b in the domain of $f$.

### Surjections
- onto
- surjective
- for every element $b \in B$ there is an element $a \in A$ with $f(a) = b$.

### Bijections
- one-to-one correspondence
- bijective
- both one-to-one and onto

### Different Types of Correspondences

### Showing that $f$ is one-to-one or onto

### Inverse Functions
- Definition: Let $f$ be a bijection from A to B. Then the **inverse** of $f$, denoted $f^{-1}$, is the function from B to A defines as $f^{-1}(y) = x$ iff $f(x) = y$

### Composition
- $f \circ g(x) = f(g(x))$

### Some Important Functions
- floor
- $f(x) = \lfloor x \rfloor$
- is the **largest integer less than or equal to x**.
- ceiling
- $f(x) = \lceil x \rceil$
- is the **smallest integer greater than or equal to x**

## Section 2.4: Sequences and Summations
### Geometric Progression
- sequence of the form: $a, ar, ar^2,...,ar^n,...$
- **initial term a**
- **common ratio r**

### Arithmetric Progression
- sequence of the form: $a, a+d, a+2d,...,a+nd,...$
- **initial term a**
- **common difference d**

### Strings
- A string is a finite sequence of characters from a finite set (an alphabet).
- Empty string => $\lambda$
- Ex. the string $abcde$ has length 5.

### Recurrence Relations