Теория на Множествата - Тема 5

Функции. Теорема на Тарски за неподвижната точка

Функции

Дефиниция(функция):
Нека $\mathrm{Rel}(A)$. Казваме, че $A$ е функция, ако $\forall x\forall y\forall y'(\langle x, y \rangle \in A \And \langle x, y' \rangle \in A \Rightarrow y = y' )$

Дефиниция:(тотална функция): Ако $\mathrm{Dom}(A) = B \And \mathrm{Rng}(A) \subseteq C$ казваме, че $A$ е (тотална) функция от $B$ към $C$. Записваме $A : B \to C$

Дефиниция(частична функция): Ако $\mathrm{Dom}(A) \subseteq B \And \mathrm{Rng}(A) \subseteq C$ казваме, че $A$ е частична функция от $B$ към $C$. Записваме $A : B \multimap\to C$

Дефиниция(сюрекция): Ако $A : B \to C$ и $\mathrm{Rng}(A) \equiv C$ то казваме, че $A$ е сюрективна (или 'върху')

Дефиниция(инекция): Aко $(x \ne x' \And \langle x ,y \rangle \in A) \Rightarrow \langle x', y \rangle \notin A$, то казваме че $A$ е инективна (още '1-1'/едноеднозначна)

Дефиниция: Ако $A : B \to C$ и $B_1 \subseteq B$. Дефинираме образ на $B_1$ под действието на функцията $A$:
$A[B_1] \rightleftharpoons \{ y | (\exists x \in B_1)(A(x) = y)\}$

Дефиниция(рестрикция): $A \upharpoonright B_1 \rightleftharpoons A \cap (B_1 \times C)$. Това се нарича рестрикция от $B_1$.

Дефиниция(монотонност): Нека $f : \mathcal{P}(A) \to \mathcal{P}(A)$. Казваме, че $f$ е монотонна, ако:

(1)
\begin{align} \forall x_1\foral x_2(x_1 \subseteq x_2 \subseteq A \Longrightarrow f(x_1) \subseteq f(x_2)) \end{align}

Дефиниция(неподвижна точка): Нека $f : X \to Y$. Казваме, че $x_0$ е неподвижна точка за $f$, ако $f(x_0) = x_0$.

Лема на Тарски

Лема на Тарски за неподвижната точка:
Нека $f: \mathcal P(A) \to \mathcal P(A)$ е монотонна функция. Тогава:

  • $f$ има неподвижна точка
  • Същестуват 2 неподвижни точки $x_1, x_2$, такива че $x_1$ е най-малката неподвижна точка, а $x_2$ е най-голямата неподвижна точка:
    • $\exists x_1(\forall x \in \mathcal P(A))(f(x) = x \Rightarrow x_1 \subseteq x)$
    • $\exists x_2(\forall x \in \mathcal P(A))(f(x) = x \Rightarrow x \subseteq x_2)$

Доказателство:
$f : \mathcal P(A) \to \mathcal P(A)$ e монотонна.
$f(X) \subseteq X$ - това са 'кандидати' за неподвижни точки - всяка неподвижна точка изпълнява това условие. Има обаче точки, които го изпълняват и не са неподвижни точки.
Нека $\mathcal X = \{ X | f(X) \subseteq X \And X \in \mathcal P(A) \}$. Това е множеството от всички кандидати. Обърнете внимание, че е непразно, защото $A \in \mathcal X$.
Нека разгледаме $X_0 = \cap \mathcal X$. Ще докажем, че $X_0 \in \mathcal X$.
Нека $X \in \mathcal X$ е произволно.
Тогава $X_0 \overset{1}\subseteq X \Rightarrow f(X_0) \overset{2}\subseteq f(X) \overset{3}\subseteq X$.
1 - от конструкцията на $X_0$. 2 - от монотонността на $f$. 3 - от конструкцията на $\mathcal X$.
Получихме $f(X_0) \subseteq X$. Обаче това е изпълнено за всяко $X \in \mathcal X$. Така получихме, че $f(X_0) \subseteq \cap \mathcal X = X_0$, т.е. $f(X_0) \subseteq X_0$, т.е $X_0 \in \mathcal X$.
От друга страна от монотонността на функцията имаме $f(X_0) \subseteq X_0 \Rightarrow f(f(X_0)) \subseteq f(X_0)$. От тук заключваме, че $f(X_0) \in \mathcal X$. От конструкцията на $X_0$ получаваме : $X_0 \subseteq f(X_0)$.
Окончателно $f(X_0) \subseteq X_0 \And X_0 \subseteq f(X_0) \Rightarrow X_0 = f(X_0)$. Тъй като $X_0$ е сечение на всички кандидати, тази точка е най-малката неподвижна (защото всяка друга би била кандидат, и следователно надмножество на $X_0$).

За максимум се доказва абсолютно аналогично, като се използва другото свойство за кандидат $X \subseteq f(X)$ и разгледаме множеството $\mathcal Y = \{ Y | Y \subseteq f(Y) \And Y \in \mathcal P(A) \}$, както и неговото обединение: $Y_0 = \cup \mathcal Y$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License