{%hackmd @RintarouTW/About %}

# Proofs and Concepts
the fundamentals of abstract mathematics

http://people.uleth.ca/~dave.morris/books/proofs+concepts.pdf

## Propositional Logic

**DEFINITION:**

An **assertion** is a sentence that is either true or false.
(Some textbooks use the term **proposition** or **statement** or **sentence**, instead of assertion.)

A **deduction** is a series of hypotheses that is followed by a conclusion. (The conclusion and each of the hypotheses must be an assertion.)

<img src="https://i.imgur.com/GEE2Jwb.png" style="filter:invert(.9)"></img>

**tautology** : always true.
ex: $A \lor \lnot A$

**contradiction** : always false
ex: $A \& \lnot A$

$A\equiv B$

$A$ is **logically equivalent** to $B$.

### Rule of Negation

$$
\lnot \lnot A \equiv A\\
\lnot (A\lor B) \equiv \lnot A \& \lnot B\\
\lnot (A\& B) \equiv \lnot A \lor \lnot B\\
\lnot (A \implies B) \equiv A \& \lnot B\\
\lnot (A \iff B) \equiv A \iff \lnot B
$$

### converse, inverse & contrapositive

The converse of $A\implies B$ is $B\implies A$.

The inverse of $A\implies B$ is $\lnot A \implies \lnot B$

The contrapositive of $A\implies B$ is the converse of it's inverse = $\lnot B\implies \lnot A$

### Rules of Propositional Logic

<img src="https://i.imgur.com/0A17Npk.png" style="filter:invert(.9)"></img>

## Functions

<img src="https://i.imgur.com/wba9hWE.png" style="filter:invert(.9)"></img>

$$f: A\to B$$

No one-to-many is allowed in a function.
many-to-one is allowed, ex: $f(x) = x^2$, where both $f(\pm 1)=1^2$

### Ono-to-one

$$
\forall a_1,a_2 \in A, (a_1\neq a_2\implies f(a_1)\neq f(a_2))\\
\#(A) = \#(B)
$$

many-to-one is not allowed.

### Onto

$$
\forall b\in B, \exists a\in A,( f(a)=b)\\
\#(A) \geq \#(B)
$$

many-to-one is allowed.

### Bijection

one-to-one and onto

$$
\forall a_1, a_2 \in A, (a_1\neq a_2\implies f(a_1)\neq f(a_2)\\
\#(A)=\#(B)
$$

or

$$
\forall b\in B,\exists! a\in A, (f(a)=b)
$$

## Inverse Function

$f$ must be one-to-one and onto to get $f^{-1}$

if $f$ is many-to-one, $f^{-1}$ is one-to-many which is not allowed in a function.

if $f$ is one-to-one but not onto, $\exists b\in B, f^{-1}(b) \notin A\implies f^{-1} \text{ is not } B\to A$

**DEF:**
$$
\begin{cases}
f:A\to B\\
f^{-1}:B\to A
\end{cases}\\
f^{-1}(f(a)) = a\text{ for all }a\in A\\
f(f^{-1}(b)) = b\text{ for all }b\in B
$$

### Composition of functions

<img src="https://i.imgur.com/Sa4F23T.png" style="filter:invert(.9)"></img>

$$
\begin{cases}
f:A\to B\\
g:B\to C
\end{cases}\\
(g\circ f)(a) := g(f(a))\text{ for all } a\in A
$$

ex:
$$
\begin{cases}
f(x) = 3x\\
g(x) = x^2
\end{cases}\\
(g\circ f)(x) = g(3x) = (3x)^2 = 9x^2\\
(f\circ g)(x) = f(x^2) = 3x^2
$$

so $g\circ f \neq f\circ g$, composition is not comuntative.

## Equivalence Relation

An **equivalence relation** is a binary relation that's **reflexive**,**symmetric** and **transitive**.
for ex: "="

### Binary Relation

$\text{R}$ is a **binary relation** on set A.

$\text{R}$ is **reflexive** iff $\forall a \in A, (a \text{ R } a)$
for ex: $\forall a\in A, a=a$

$\text{R}$ is **symmetric** iff $\forall a,b \in A, (a\text{ R } b \implies b\text{ R } a)$
for ex: $\forall a,b\in A, a=b\implies b=a$

$\text{R}$ is **transitive** iff $\forall a,b,c \in A, (a \text{ R } b
\text{ } \& \text{ } b \text{ R } c \implies a \text{ R } c)$
for ex: $\forall a,b,c\in A, (a > b) \& (b > c)\implies a>c$

## Equivalence Class

$\sim$ is an equivalence relation on a set A, the equivalence class of "a" is the subset of A,

$$[a] = \{x\in A|x\sim a\}$$

for ex:

$$
\begin{cases}A = \{1,2,3,4,5\}\\
\sim = \text{\{(1,1),(1,3),(1,4),(2,2),(2,5),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4),(5,2),(5,5)\}}
\end{cases}
$$

$\sim$ is a equivalence relation on $A$.


$\forall a_1, a_2 \in A, (a_1 \sim a_2\implies [a_1] = [a_2])$

[1] = [3] = [4] = {1,3,4}

[2] = [5] = {2,5}

$\forall a_1, a_2 \in A, (a_1\nsim a_2\implies [a_1] \cap [a_2] = \varnothing)$

1 $\nsim$ 2 $\implies$ [1] $\cap$ [2] = $\varnothing$

Given $[a_1], [a_2]$ two equivalence classes are not disjoint, such that $[a_1] = [a_2]$.

**Proof:**

$$
\exists a\in [a_1], a\in [a_2]\implies a\sim a_1, a\sim a_2\\
\therefore [a_1] = [a]=[a_2]
$$

## Modulo Arithmetic

$a\sim b\iff [a]=[b]$

### Integer Modulo

Notation : $\bar a = [a]_n$ for convenience.

Thus,

$$
\mathbb{Z_3} = \{\bar 0, \bar 1, \bar 2\}
$$


$$
\bar a +_n \bar b=\overline{a+b}\\
\bar a -_n \bar b=\overline{a-b}\\
\bar a \times_n \bar b=\overline{ab}
$$

## Number Theory

$\forall a,b,c \in \mathbb{Z}, (a\mid b)\land(b\mid c) \implies a\mid c$

$\forall a,b,n \in \mathbb{Z},
a\equiv b \pmod n\iff n\mid (a-b)$
a is congruent to b modulo n $\iff a \mod n = b \mod n$, both with the same remainer.

$$\cases{
a = q_a\times n + r\\
b = q_b\times n + r
}
\implies a\equiv b\equiv r\pmod n
$$

## Induction

$a_1$ is true, assume $a_{n-1}$ is true $\implies a_n$ is true when $n\ge 2$

### Well Ordered

$\mathbb{N}$ is well ordered.

$\implies$ Every nonempty set of $\mathbb{N}$ has a smallest element.

$\forall p\in \mathbb{N^+},$ p is prime $\iff p > 1,$ and p is not divisible by any element of $\mathbb{N^+}$ other than 1 and p itself.

$n\in \mathbb{N}$ and $n>1$ $implies$ $n$ is divisible by a prime number.

### ma+nb = 1

$a\not=b$ and $a, b$ are relatively prime $\iff a, b$ have the only common divisor 1.

$$
a, b\text{ are relatively prime}
\iff \exists m,n\in\mathbb{Z}, ma+nb = 1
$$

**Proof**

$\impliedby )$

Assume $ma+nb=1$ but $a$ and $b$ are not relatively prime.
Then $a, b$ have a common divisor $d(> 1 \in \mathbb{Z})$.

$\cases{a = q_ad\\b = q_bd} (q_a, q_b \in \mathbb{Z})$

$ma+nb = mq_ad+nq_bd = d(mq_a+nq_b) = 1$

$mq_a + nq_b = \frac{1}{d}$

$\because m,n,q_a, q_b \in \mathbb{Z}\implies mq_a + nq_b \in \mathbb{Z}\implies d=1$ (contradiction to $d > 1$)
$\therefore a,b$ must be relatively prime.

$$
\forall a,b\in \mathbb{N^+},m,n\in \mathbb{Z}, ma+nb=1\implies a,b \text{ are relatively prime}
$$

The contrapositive is also true,

$$
\forall a,b\in \mathbb{N^+},m,n\in \mathbb{Z}, a, b\text{ are not relatively prime} \implies ma+nb\not=1
$$

$\implies )$

$a, b \in N^+, m,n \in Z$

$d$ is the gcd of $a,b$

$ma + nb = mq_ad+nq_bd = 1 \implies mq_a+nq_b = \frac{1}{d}$

$d = 1$ is the only way to make $mq_a+nq_b = 1$

$d = 1$ implies $a,b$ must be relatively prime.

when $d = 1$, exists $m,n \in \mathbb{Z}$ let $ma+nb =1$

$\implies )$
$$S = \{ma+nb\mid m,n\in\mathbb{Z}\}\cap \mathbb{N^+}$$

Let $d$ be the smallest element in $S$ since $\mathbb{N^+}$ is well-ordered. $\implies d \geq 1$

$d = m_0a+n_0b$ where $m_0, n_0 \in \mathbb{Z}\implies d\in \mathbb{N^+}$

$a, d\in N^+\implies a = qd+r$ $(0\leq r < d, r\in \mathbb{N}, q\in \mathbb{Z})$

$r=a-qd=a-q(m_0a+n_0b)=(1-qm_0)a-n_0b$

$\because d$ is the smallest element in $S$, and $r < d \therefore r\notin S$

## Function and Relation

$$\cases{
A = \{1, 2, 3\}\\
B = \{a, b\}
}\\
\Downarrow\\
A\times B = \{(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)\}
$$

There are $|A|\times|B|$ elements in $A\times B$.

These elements $(x,y)$ are used to be a representation of mapping relations between $A$ and $B$.

### Relation

$$
R = \{(x,y)\mid x,y\in A\}
$$

Duplicated $(x, y_1), (x, y_2) \in R$ (same $x$, different $y$) are allowed. It's used to describe or define the relations between elements of $A$.

### Function

$$
f : A\to B = \{(x,y)\mid x\in A, y\in B\}\\
\forall x \in A, \exists y \in B, f(x) = y
$$
There is no duplicated $(x, y_1), (x, y_2)$ since many-to-one is not allowed in function. Also, all $x\in A$(domain) must be mapped to B(codomain).

Since each $x \in A$ must be mapped to $B$, and there're $|B|$ possible choices for each $x$. So there're $|B|^{|A|}$ possible mappings which indicate different functions.

#### Bijection

Bijection on $A\to A$ leads to the possible mappings as Permutaion of $A$($|A|!$). Because bijections is one-to-one and onto, so the many to one cases are not allowed.

It means for each $x\in A$(domain), the picked one on the codmain can't be picked again. So it becomes permutaion.

ex:
$$
A = \{1,2,3\}\\
\pmatrix{1&2&3\\1&2&3}=\{(1,1),(2,2),(3,3)\}\\
\pmatrix{1&2&3\\1&3&2}=\{(1,1),(2,3),(3,2)\}\\
\pmatrix{1&2&3\\2&1&3}=\{(1,2),(2,1),(3,3)\}\\
\pmatrix{1&2&3\\2&3&1}=\{(1,2),(2,3),(3,2)\}\\
\pmatrix{1&2&3\\3&1&2}=\{(1,3),(2,1),(3,2)\}\\
\pmatrix{1&2&3\\3&2&1}=\{(1,3),(2,2),(3,1)\}
$$

## Terms and Notations

$a \mid b$
: a is a divisor of b

$a \not\mid b$
: a is not a divisor of b

(x, y)
: ordered pair where (x,y) $\not=$ (y, x)

Cartesian product of A and B
: $A\times B = \{(a, b)\mid a\in A, b\in B \}$

#(A$\times$B)
: cardinality of $\#(A\times B) = \#A\cdot \#B$

{x, y}
: set representation without order, {x, y} = {y, x}

function
: A set $f$ is a function from A to B $\iff$
: a. $\forall (a,b)\in f, (a\in A)\land(b\in B)$ and
: b. $\forall a\in A, \exists! b\in B, (a,b)\in f$, ex: $(a,b)$ and $(a,c)$ can't exist at the same time (one-to-many is not allowed)

domain and codomain
: if $f$ is a function from A to B($f :A\to B$), $A$ is the domain of $f$, $B$ is a codomain of $f$.

range = {$f(a)\mid a\in A$}
: The range of $f$ is the set that collects all the these elements f(a).

binary operation
: if $A$ is a set, then any function from $A\times A \to A$ is called binary operation.

one-to-one (injective)
: $\forall a_1,a_2 \in A, f(a_1) = f(a_2) \implies a_1 = a_2$
: or the contrapositive
: $\forall a_1,a_2 \in A, a_1\not=a_2\implies f(a_1)\not=f(a_2)$

onto (surjective)
: $\forall b\in B, \exists a\in A, f(a) = b$

bijection
: a function that's **one-to-one** and **onto**.
: $\forall b\in B,\exists! a\in A, f(a) = b$

identity map
: For any set A, define the identity map $I_A: A\to A$ by $\forall a\in A, I_A(a) = a$

inverse function $f^{-1}$
: $\cases{f: A\to B\\g: B\to A}$, $g$ is $f$'s inverse function $\iff \cases{\forall a\in A,g(f(a))=a\\\forall b\in B,f(g(b))=b}$

if $f:A\to B$ has an inverse function $f^{-1}:B\to A$, $f$ is a bijection.

composition function
: $\cases{f:A\to B\\ g: B\to C}\implies g\circ f: A\to C$
: $(g\circ f)(a) = g(f(a))$, for all $a\in A$

kernel
: $f: A\to B, K\subseteq A\times A=\{(x,y)\mid x,y\in A, f(x)=f(y)\}$. The relation $K$ is called the **kernel** of $f$.

image
: $f:A\to B$ and $A_1 \subset A$, the image of $A_1$ on $f$ is
: $f(A_1)=\{f(a)\mid a\in A_1\}$

pre-image or inverse-image
: $f:A\to B$ and $B_1\subset B$, the pre-image of $B_1$ under $f$ is
: $f^{-1}(B_1)=\{a\in A\mid f(a)\in B_1\}$

cardinality
: Sets A and B have the same cardinality $\iff$ there is a bijection from A to B.

partition
: A partition of a set A is a collection of nonempty subsets of A
<img src="https://i.imgur.com/Av6bT3X.png" style="filter:invert(.9)"></img>
: $\cases{\bigcup\limits_{i=1}^n Ai = A\\\forall A_i, A_j\in A, (i\not=j)\implies A_i\cup A_j = \varnothing}$

: Suppose $\sim$ is an equivalence relation on A $$\{[a]\mid a\in A\}$$ is a partition of A, also called **A modulo $\sim$**, denoted $A/\sim$

$\bigcup$
: $\bigcup\limits_{i=1}^{n}A_i=A_1\cup A_2\cup\cdots A_n$

$\prod$
: $\prod\limits_{i=1}^{n} x_i= x_1\cdot x_2\cdots x_n$

###### tags: `abstract` `math`