Тема 0

Основни понятия


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


  • $A, B, C$ - множества
  • $\cup, \cap, \setminus$ - операции сечение, обединение, разлика
  • $\alpha, \beta, \cdots$ - мощност
  • $\bar{\bar A}$ - мощност на множество
  • $f : A \to B$ - изображение (функция)
  • $A \sim B \rightleftharpoons f : A \to B \quad g : B \to A$ - 2 множества са еквивалентни, ако има инективни изображения от първото във 2рото и обратно. Това е равносилно да им биективно изображение от едното върху другото.
  • $\mathrm{Im} f$ - образ на $f$ - т.е. функционално множество (евентуално $\subseteq B$
  • $\mathrm D f$ - дефиниционна област на $f$
  • $A \times B$ - декартово произведение
  • $\mathbb N = \{ 1, 2, 3, \cdots \}$ - естествените числа (без както виждате)
  • $\mathbb Z, \mathbb Q,\ \mathbb R$ - цели, рационални, реални числа
  • Всяко подмножество на естествените числа, ограничено от горе/долу има максимален/минимален елемент.
  • Всяко множество еквивалентно на $\mathbb N$ има мощност $\omega$ (т.е изброимо е)
  • Всяко множество еквивалентно на $\mathbb R$ има мощност $c = 2^\omega$ (ака. континуум)
  • За всяко множество може да се построи друго множество с по-голяма мощност (доказва се по теория на множествата).
  • $A, B : \bar{\bar A} < \bar{\bar B} \iff f : A \to B \And \lnot f : B \to A$ - т.е мощността на едно множество е по-малка от мощността на друго, ако съществува инективно изображение от първото във второто, но не съществува инективно изображение от второто в първото.
  • Ще докажем, че $A \nsim 2^A$. Т.е че едно множество и неговия булеан1 имат различни мощности (не са еквивалентни).

Доказателство:
Съществува изображение от $A$ към $2^A$:

(1)
\begin{eqnarray} & & f : A \to 2^A\\ & & \forall a \in A : f(a) = \{ a \} \subset A \Rightarrow \{ a \} \in 2^A \end{eqnarray}

Сега ще докажем че не съществува инективно изображение от $2^A$ във $A$. Допускаме противното!
Т.е допускаме че има инективно изображение, тогава има биекция. Нека тази биекция я наречем $f : A \to 2^A$.
Ще разгледаме следните 2 множества:

(2)
\begin{eqnarray} \Gamma_1 & = & \{ a | a \in A \And a \in f(a) \}\\ \Gamma_2 & = & \{ a | a \in A \And a \notin f(a) \}\\ \end{eqnarray}

2те множества са непразни - $f^{-1}(A) \in \Gamma_1,\ f^{-1}(A) \in f(f^{-1}(A)) = A$
$f^{-1}(\varnothing) \in \Gamma_2,\ f^{-1}(\varnothing) \notin f(f^{-1}(\varnothing)) = \varnothing$.
Освен това 2те множества са непресичащи се (в противен случай ще излезе че един елемент хем принадлежи на образа си, хем не принадлежи).

Тъй като $\Gamma_1, \Gamma_2$ са подмножества на $A$, ще проверим към кое от 2те множества принадлежи $g_2 = f^{-1}(\Gamma_2)$:

  1. $g_2 \in \Gamma_1 \Rightarrow g_2 \in f(g_2) \iff g_2 \in \Gamma_2$
  2. $g_2 \in \Gamma_2 \Rightarrow g_2 \notin f(g_2) \iff g_2 \notin \Gamma_2$

И в двата случая стигнахме до противоречие. Допуснатото е невярно! $A \nsim 2^A$

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