2.1 Basics

This section serves as a quick introduction, where we establish the notation and fundamental mathematical concepts such as sets, functions, and various propositions. We will not dedicate time to proving these propositions, as they are already well-established and proven in the realm of school-level and university entry-level mathematics.

Theorems, propositions and definitions

Theorems, propositions, and definitions will be presented in a uniform style for clarity. Each presentation will begin with the formulation of the assumptions relevant to the theorem. Then, following a delineating line, we will state the theorem or definition itself:

$$\begin{align*} &\sphericalangle \\ &\text{Conditions and prerequisited} \\ \hline \\ &\text{Theorem results / definition} \end{align*}$$

Additionally, it is important to pay attention to any notes provided below each theorem or definition. These notes are designed to enhance clarity and contribute to a deeper understanding of the content.

Definitions

We will use the symbol $:=$ to indicate the definition of a term or concept. Specifically, this symbol signifies that we are establishing a definition rather than stating an incidental equality.

For instance, when we write $X_k :=\{nk: n \in \N\}$, it means that we are intentionally defining the set $X_k$ in this particular manner. In this context, $X_k$ is not merely "coincidentally" equal to the set $\{nk: n \in \N\}$; rather, it is being specifically defined as such.

Logics

In our discussions, we will consistently use a set of traditional mathematical symbols:

1. $\forall x$ - This symbol represents the phrase "for all $x$," indicating that the statement that follows is true for every instance of $x$.

2. $\exists x$ - This notation denotes "there exists some $x$," which implies the existence of at least one instance of $x$ that satisfies the given conditions. It is important to note that the existence is not necessarily unique

3. $\exists! x$ - This is used to express "there exists a unique $x$." It specifies that there is exactly one instance of $x$ that fulfills the stated criteria

4. $a \vee b$ - This is interpreted as "$a$ or $b$." For instance, the expression $(r \ge m) \vee (r = 0)$ should be understood as meaning either "$r$ is greater than or equal to $m$" or "$r$ equals 0," possibly including both conditions

5. $a \wedge b$ - This stands for "$a$ and $b$." As an example, the expression $(r \le m) \wedge (r \ge 0)$ conveys the idea that "$r$ is less than or equal to $m$ and greater than or equal to 0," which can be succinctly expressed as $0 \le r \le m$

6. $\neg a$ - This notation represents the negation of the statement $a$. In logical terms, if $a$ is false, then $\neg a$ is true, and conversely, if $a$ is true, then $\neg a$ is false

Sets

For sets, our notation will use to the following conventions:

1. We typically use lowercase letters (such as $a$) to represent elements of a set

2. Uppercase letters (like $A$) denote sets themselves

3. Calligraphic letters (for instance, $\mathcal{A}$) to denote classes. Class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. It could have been thought as "set of sets" but the latter have some problems in axiomatics (like Russel paradox) which class doesn't have

4. Fraktur letters will be used for denoting a special subclasses of a class, like maximal ideals $\mathfrak M$ in the class of all ideals

note

We will use the notation $X \in \mathcal S$ to denote that $X$ is a set

1. The expression $a \in A$ means that the element $a$ belongs to the set $A$.

2. The notation $B \subseteq A$ indicates that $B$ is a subset of or equal to $A$. In more formal terms: $\forall b \in B: b \in A$.

3. $B \subset A$ denotes that $B$ is a proper subset of $A$. This is defined as: $(B \subseteq A) \wedge (B \ne A)$, meaning every element of $B$ is in $A$, but $B$ is not equal to $A$.

4. $A \cup B$ is a set union, $A \cup B := \{x: (x \in A) \vee (x \in B)\}$

5. $A \cap B$ is a set intersection, $A \cap B := \{x: (x \in A) \wedge (x \in B)\}$

6. $A \setminus B$ is a set difference, $A \setminus B := \{x: (x \in A) \wedge (x \notin B)\}$

7. $|A|$ denotes the number of elements in the set $A$, and this number is also referred to as the cardinality of the set.

8. $X \times Y:=\{(x, y): x\in X, y \in Y\}$ - a cartesian (external) product of two sets

9. $XY:=\{xy: x\in X, y \in Y\}$ - inner product of two sets.

10. $xY := \{x\}Y$

11. Paritition $X = \sum_iX_i$ means that $X = \bigcup_iX_i, X_i \cap X_j = \empty$.

Binary relations

def: Binary relation

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S \\ &U \subseteq X \times X \\ \hline \\ &U - \text{binary relation} \\ \end{align*}$$

def: Equivalence relation

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S \\ & U \subseteq X \times X \\ & \forall x, y, z \in X: \\ \text{Reflexifity:} \,\, &(x, x) \in U \\ \text{Symmetry:} \,\,&(x, y) \in U \implies (y, x) \in U \\ \text{Transitivity:} \,\, &(x, y) \in U, (y, z) \in U \implies (x, z) \in U \\ \hline \\ &X \in \mathcal S_{\sim}, X - \text{a set with equivalence relation} \\ &x \sim y := (x, y) \in U \end{align*}$$

Proposition 2.1.1: Equivalence relation induces set parition

$$\begin{align*} &\sphericalangle \\ &X \in \mathcal S_{\sim} \\ \hline \\ &\exists X_1, X_2, \ldots : X = \sum_iX_i \\ &\forall x, y: \\ &x \sim y \implies x, y \in X_i\\ &\neg(x \sim y) \implies x \in X_i, y \in X_j, i \ne j\\ &[x]_{\sim} := X_i - \text{equivalence class} \end{align*}$$

note

We can pick any representative of equivalence class to indicate this class. We use the notation $[x]_{\sim}$ for that.

def: Parital order

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S \\ & U \subseteq X \times X \\ & \forall x, y, z \in X: \\ \text{Reflexifity:} \,\, &(x, x) \in U \\ \text{Antisymmetry:} \,\,&x \ne y, (x, y) \in U \implies (y, x) \notin U \\ \text{Transitivity:} \,\, &(x, y) \in U, (y, z) \in U \implies (x, z) \in U \\ \hline \\ &X \in \mathcal S_{\leq_P}, X - \text{partially ordered set} \\ &x \leq_P y := (x, y) \in U \end{align*}$$

def: Total order

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S_{\leq_P} \\ & \forall x, y \in X: \\ \text{Strongly connected:} \,\, &(x\leq_P y)\vee(y \leq_P x) \\ \hline \\ &X \in \mathcal S_{\leq_T}, X - \text{totally ordered set} \\ \end{align*}$$

Proposition 2.1.2: Every partial order induces partial order on a subset

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S_{\leq_P} \\ & Y \subseteq X \\ \hline \\ &Y \in \mathcal S_{\leq_P} \end{align*}$$

def: Chain

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S_{\leq_P} \\ & Y \subseteq X \\ &Y \in \mathcal S_{\leq_T} \\ \hline \\ &Y \in \mathfrak C(X), Y - \text{chain} \end{align*}$$

Proposition 2.1.3: Zorn's lemma

$$\begin{align*} &\sphericalangle \\ & X \in \mathcal S_{\leq_P} \\ & \forall Y \in \mathfrak C(X): \exists x \in X: \forall y \in Y: y \leq x \\ \hline \\ & \exists m \in X: \forall x \in X: x \leq m \end{align*}$$

Mappings

1. The notation $f: A \to B$ describes a mapping (or function) from set $A$ to set $B$. A mapping establishes a correspondence between elements of set $A$ and elements of set $B$. By definition, a mapping is well-defined, meaning that each element in $A$ corresponds to exactly one element in $B$. However, the reverse is not necessarily true; it is possible for two elements in $A$ to correspond to the same element in $B$.

2. $f: a \mapsto a^2$ specifies the precise mechanism of element correspondence in a mapping (note the different arrow used here compared to the one above). In this example, each element $a \in A$ is mapped to the element $a^2 \in A$. Alternatively, this can be expressed using function notation as $f(a) = a^2$.

3. Consider $A' \subseteq A$, we define image $f(A') := \{f(x), x \in A'\}$

4. Consider $f: A \to B$ and $B' \subseteq B$. Then we define pre-image $\phi^{-1}(B'):=\{a \in A: \phi(a) \in B'\}$.

5. If $b \in B$ then $\phi^{-1}(b) := \phi^{-1}(\{b\})$

def: Injective function

$$\begin{align*} &\sphericalangle \\ &f: A \to B \\ &\forall a_1, a_2 \in A:f(a_1)=f(a_2) \implies a_1 = a_2 \\ \hline \\ &f: A \overset{1-1}{\to} B, f - \text{injective} \\ \end{align*}$$

def: Surjective function

$$\begin{align*} &\sphericalangle \\ &f: A \to B \\ &\forall b \in B: \exists a \in A: f(a)=b \\ \hline \\ &f(A) = B, f - \text{surjective} \\ \end{align*}$$

def: Bijective function

$$\begin{align*} &\sphericalangle \\ &f: A \overset{1-1}{\to} B, f(A) = B \\ \hline \\ &f: A \leftrightarrow B, f - \text{bijective} \\ \end{align*}$$

Examples: Mappings

Numbers

Proposition 2.1.4: Principle of Well Ordering

$$\begin{align*} &\sphericalangle \\ &X \subseteq \mathbb{N} \\ &X \neq \empty \\ \hline \\ &\exist k \in X: \forall n \in X: k \leq n \end{align*}$$

In other words, every non-empty subset of natural numbers has a minimum element.

Propsition 2.1.5: Division algorithm

$$\begin{align*} &\sphericalangle \\ &a, b \in \Z, b \ne 0 \\ \hline \\ &\exists! m, r \in \mathbb{Z}, 0\leq r \lt b: a=bm+r \end{align*}$$

Proposition 2.1.6: Linear diophantine equation

$$\begin{align*} &\sphericalangle \\ &a, b \in \Z, a, b \ne 0 \\ \hline \\ &\exists m, n \in \Z: \text{gcd}(a,b)=am+bn \end{align*}$$

def: Prime number

$$\begin{align*} &\sphericalangle \\ &p \in \N, p > 1 \\ & a \in \N, a \mid p \implies (a = p) \vee (a = 1) \\ \hline \\ &\forall p \in \mathfrak P, p - \text{prime} \end{align*}$$

Proposition 2.1.7

$$\begin{align*} &\sphericalangle \\ &a, b \in \Z \\ &p \in \mathfrak P \\ \hline \\ &p \mid ab \implies (p \mid a)\vee(p \mid b) \end{align*}$$