Тема 15

Фундирани и добре наредени множества и индуктивни принципи за тях. Морфизъм в добри наредби. Сравнимост.

---

страницата се нуждае от дописване/преглеждане

---

Добра наредба

Дефиниция: $\langle A, \le \rangle$ е добра наредба ако:
a) $A$ е частично наредено множество и $\forall B(B \ne \varnothing \And B \subseteq A \Rightarrow B$ има най-малък елемент $)$.
b) $A$ е линейно наредено множество и $\forall B(B \ne \varnothing \And B \subseteq A \Rightarrow B$ има минимален елемент $)$.

Индукция по Пеано:
Нека $A \subseteq \mathbb N$.
Ако

1. $0 \in A$ и
2. $\forall x(x \in A \Rightarrow S(x) \in A)$

тогава $A = \mathbb N$.

Индукция (обобщена):
Нека $A \subseteq N$
Ако $\forall x(\forall y(y < x \Rightarrow y \in A) \Rightarrow x \in A)$, тогава $A = N$

Твърдение: Нека $A$ е добре наредено множество. Нека $B \subseteq A$ удовлетворява свойството

(1)

\begin{align} \mathrm{(ind)} \quad \forall x(\forall y(y < x \Rightarrow y \in B) \Rightarrow x \in B) \end{align}

Тогава $B = A$. (т.е доказваме че това свойство е в сила за всички добре наредени множества - в тях може да се прави индукция).

Доказателство: Нека $B$ изпълнява свойството $\mathrm{(ind)}$. Допускаме, че $B \ne A$. Тогава $A \setminus B \ne \varnothing$. Понеже $A$ е добре наредено, следователно съществува най-малък елемент $x_0$ в множеството $A \setminus B$.
Допускаме, че съществува елемент $x'$, такъв че $x' < x_0 \And x' \notin B$. Но тогава $x' \in A \setminus B \And x' < x_0$ - противоречие - $x_0$ е най-малкия елемент на $A \setminus B$. Но тогава според $\mathrm{(ind)}$, понеже всички елементи по-малки от $x_0$ са във $B$, следва че и $x_0 \in B$. Противоречие - $x_0 \in A \setminus B$. Така доказахме, че $B = A$.