Mathematical logic (1) Set, Relation and function 集合，关系与函数

1. Set 集合

1.1 Primary 初步知识

A collection of elements is called set

• Element of set: the object

1.2 Intension & Extension 内涵与外延

• Intension(内涵): The intension of a set is its description or defining properties, i.e.,
  what is true about members of a set. (对概念的定义)
• Extension(外延): The extension of a set is its members or contents. (概念所代表的
  对象)

$Extension$ $Axiom$ : The two sets $A$ and $B$ are equal ($A = B$) if and only if $A$ and $B$ have the same members.

1.3 Definition 定义

Denote $φ(x)$ as a propertry of $x$, then $\{x| φ(x)\}$ represents a set that all x have this propertry.

For more:

• $\{x | x \neq x\} = \emptyset$
• $\{X | X \notin X\} = \emptyset$

(can be proof by contradiction)

Set remains the same whatever you change the order of elements or repeat them.

$$\{a, b\} = \{a, a, b\} = \{a, b, a\}$$

1.4 Subset 子集

If for any $x$ in $A$ satisfying $x \in B$, then $A \subseteq B$.

1.4.1 Proper Subset 真子集

there exists at least one element of B which is not an element of $A$ ，then $A$ is a proper (or strict) subset of $B$, denoted by $A \subseteq B$.

We say $\emptyset$ is a proper subset of any except itself.

1.5 Power Set 幂集

If $A$ is a set, $\{X | X \subseteq A\}$ is the power set of $A$, denoted as $\mathcal{P}(A)$.

• $\mathcal{P}(\emptyset) = \{\emptyset\}$
• $\mathcal{P}(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\}$

1.6 Set Operations 集合操作

• Union(并集): $A \cup B = \{x |x \in A \ or \ x \in B \}$
• Intersection(交集): $A \cap B = \{x | x \in A \ and \ x \in B\}$
• Difference(差集): $A - B = \{x | x \in A \ and \ x \notin B\}$

2. Relations 关系

2.1 Tuples 有序元组

An ordered element sequece $<x_1,x_2,\dots,x_n> (x_i \in \mathbb{N})$ is denoted as n-tuple.

2.1.1 Properties 有序n元组的性质

• We say $<x_1,x_2,\dots,x_m> \ = \ <y_1,y_2,\dots,y_n>$ when $m=n \ and \ x_1=y_1, \dots, x_n=y_n$
• A tuple can contain mutiple instances of the same element
• A tuple has a finite number while a set may not.

2.1.2 Cartesian Product 笛卡尔积

$A \times B$ denotes the Cartesian product: $\{<x,y>|x \in A \ and \ y \in B\}$.

2.2 Binary Relations 二元关系

A binary relation $R$ over sets $X$ and $Y$ is a subset of $A \times B$ denoted as $R \subseteq A \times B$

$<x,y> \ \in R$ means $x$ is $R$-related to $y$, denoted as $R(x,y)$ or $xRy$.

Specially when $X = Y$, we call relation $R$ is over $X$ (denoted as $xRx$).

e.g $<$ is a binary relation over $\mathbb{N},\mathbb{Z}$.

2.3 n-ary Relation 多元关系

n-ary Cartesian product: $A_1 \times A_2 \times A_3 \times \dots A_n = \{<x_1,x_2,x_3,\dots,x_n>|x_1 \in A_1, x_2 \in A_2,\dots,x_n \in A_n\}$

Iff $R \subseteq A^n$, $R$ is denoted as n-ary relation over A.

2.4 Equivalence Relation 等价关系

When $R$ is a binary relation on set $A$ and $R$ is a equivalence relation, $R$ has following properties:

• R is Reflexive(自反) meaning for all $x \in A$, $xRx$.
• R is Symmetric(对称) meaning for all $x, y \in A$, if $xRy$ then $yRx$.
• R is Transitive(可传递) meaning for all $x, y, z \in A$, if $xRy$ and $yRz$, then $xRz$.

e.g. “=” is an equivalence relation on $\mathbb{N}$.

2.5 Equivalence Class 等价类

Given an equivalence relation $R$ over a set $A$, for any $x \in A$, the equivalence class of x in the set

$$[x]_R = \{y \in A \ | \ xRy\}$$

Theorem $1$ :
If $R$ is an equivalence relation over $A$, then for all $a \in A$ belongs to a equivalence class.

Theorem $2$ :
Given an equivalence relation on set $A$, the collection of equivalence classes forms a partition of set $A$.

eg. Define a equivalence relation $R$ over $\mathbb{Z}$ by:

$$aRb \Leftrightarrow a \text{ mod } 3 = b \text{ mod } 3$$

All the equivalence classes of $R$ are:

$$\begin{aligned} [0]_R &= \{n \in Z | n \text{ mod } 3 = 0\} = 3\mathbb{Z} \\ [1]_R &= \{n \in Z | n \text{ mod } 3 = 1\} = 3\mathbb{Z} + 1 \\ [2]_R &= \{n \in Z | n \text{ mod } 3 = 2\} = 3\mathbb{Z} + 2 \end{aligned}$$

2.6 Partial Order Relation 偏序关系

A binary relation $R$ is a partial order when satisfying $R$ is:

• Reflective
• Antisymmetric
• Transitive

Minimal element: for $x \in A$ there doesn’t exist another $y \in A$ such that $yRx$, then $x$ is the minimal element.

Maximal element: for $x \in A$ there doesn’t exist another $y \in A$ such that $xRy$, then $x$ is the maximal element.

2.7 Total Order Relation 全序关系

If $R$ is a partial order relation and for any $x, y \in A$ there exists $xRy$ or $yRx$, then $R$ is a total order relation over $A$

e.g. $\subseteq$ is a total order on $\mathcal{P}(\mathbb{N})$, $\emptyset$ is the minimal element and $\mathbb{N}$ is the maximal element.

3. Function 函数

A function from $X$ to $Y$ is a binary relation $R$ that satisfies:

• For all $x \in X$, there exists $y \in Y$ such that $xRy$.
• If $y,z$ \in Y such that $xRy$ and $xRz$, then $y=z$.

3.1 Notation 记法

We typically use $f,g,h$ to represent functions

$$f: A \to B$$

expresses that $f$ is a function from set $A$ to $B$.

• Domain(定义域): the set of input values ($A$ for $f$).
• Codomain(陪域): the set of possible output values($B$ for $f$).
• Range(值域): the set of actual output values (subset of $B$ for $f$).

3.2 n-ary Function 多元函数

$f: A_1 \times A_2 \times \dots \times A_n \to B$ is called an n-ary function

An n-ary function maps ordered n-tuples from its domain to elements in its codomain.

3.3 Injective, Surjective and Bijective Functions 单射，满射与双射函数

Given a function $f: X \to Y$:

• Injective: $\forall a,b \in X, f(a)=f(b)\Rightarrow a=b$
  

• Surjective: $\forall y \in Y,\exist x \in X, f(x) = y$
  

• Bijective: $\forall x \in X ,\exist g: Y \to X, g(f(x)) = x$, or, $f$ is both injective and surjective.
  

3.4 Composition Function 复合函数

Given $f: X \to Y$, $g: Y \to Z$, function $g \circ f: X \to Z$ denotes as a composition function on $X,Y,Z$