lection-13.tex

\documentclass[aspectratio=169]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{cancel}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{cmll}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{multicol}
\usetikzlibrary{patterns,calc}
\usepackage{chronosys}
\usepackage{proof}
\usepackage{multirow}
\usepackage{marvosym}
\usepackage{hyperref}
%\usepackage{tabularx}
\usepackage{comment}
\setbeamertemplate{navigation symbols}{}
%\usetheme{Warsaw}

\newtheorem{thm}{Теорема}[section]
\newtheorem{dfn}{Определение}[section]
\newtheorem{lmm}{Лемма}[section]
\newtheorem{exm}{Пример}[section]
\newtheorem{axm}{Аксиома}[section]
\newtheorem{snote}{Пояснение}[section]

\newcommand{\divisible}%
{\mathrel{\lower.2ex%
\vbox{\baselineskip=0.7ex\lineskiplimit=0pt%
\kern6pt \hbox{.}\hbox{.}\hbox{.}}%
}}

\begin{document}

\newcommand\doubleplus{+\kern-1.3ex+\kern0.8ex}
\newcommand\mdoubleplus{\ensuremath{\mathbin{+\mkern-10mu+}}}

\begin{frame}
\begin{center}\LARGE Аксиома выбора\end{center}
\end{frame}

\begin{frame}{Аксиома выбора}
\begin{axm}[выбора]
Из любого семейства дизъюнктных непустых множеств $\mathcal{A}$ можно выбрать непустую трансверсаль --- 
множество $S$, что $|S \cap A| = 1$ для каждого $A\in\mathcal{A}$. Иначе, $S \in \times \mathcal{A}$.
\end{axm}

\begin{thm}[функциональный вариант аксиомы выбора]
Пусть $\mathcal{A}$ --- семейство непустых множеств. Тогда существует
$f : \mathcal{A} \rightarrow \cup \mathcal{A}$, причём $\forall a.a \in \mathcal{A} \rightarrow f(a) \in a$
\end{thm}

\begin{proof}
Пусть $X(A) = \{ \langle A, a \rangle \ |\ a \in A \}$, 
по семейству $\mathcal{A}$ рассмотрим $\{X(A)\ |\ A\in\mathcal{A}\}$
\begin{itemize}
\item непустых: если $A\in\mathcal{A}$, $A \ne \varnothing$, то $X(A) \ne \varnothing$;
\item дизъюнктное: если $A_0,A_1\in\mathcal{A}$, $A_0 \ne A_1$, то $X(A_0) \cap X(A_1) = \varnothing$
\end{itemize}
тогда по аксиоме выбора $\exists f.f \in \times \mathcal{A}$.
\end{proof}
Обратное утверждение также легко показать.
\end{frame}

\begin{frame}{Аксиома выбора: альтернативные формулировки}
\begin{thm}[Лемма Цорна]
Если задано $\langle M, (\preceq) \rangle$ и для всякого линейно упорядоченного $S \subseteq M$ выполнено
$\text{upb}_M S \ne \varnothing$, то в $M$ существует максимальный элемент.
\end{thm}
\begin{thm}[Теорема Цермело]
На любом множестве можно задать полный порядок.
\end{thm}
\begin{thm}
У любой сюръективной функции существует частичная обратная.
\end{thm}

\begin{thm}
Аксиома выбора $\Rightarrow$ лемма Цорна: без доказательства.
\end{thm}
\end{frame}

\begin{frame}{Начальный отрезок}

\begin{dfn}
Назовём (для данного раздела) упорядоченным множеством пару $\langle S, (\prec_S)\rangle$.
Отношение порядка $(\prec_S)$ может быть как строгим, так и нестрогим.
Будем говорить, что $\langle S, (\prec_S)\rangle$ --- начальный отрезок $\langle T, (\prec_T) \rangle$,
если:\begin{itemize}
\item $S \subseteq T$;
\item если $a,b \in S$, то $a \prec_S b$ тогда и только тогда, когда $a \prec_T b$;
\item если $a \in S$, $b \in T\setminus S$, то $a \prec_T b$.
\end{itemize}
Будем обозначать это как $\langle S, (\prec_S)\rangle\sqsubseteq\langle T, (\prec_T)\rangle$ или как $S \sqsubseteq T$, если порядок на множествах понятен из контекста.
\end{dfn}

\begin{thm}
Отношение <<быть начальным отрезком>> является отношением нестрогого порядка.
\end{thm}
\end{frame}

\begin{frame}{Верхняя грань семейства упорядоченных множеств}
\begin{thm}[о верхней грани]
Если семейство упорядоченных множеств $X$ линейно упорядочено отношением <<быть начальным отрезком>>, то у него есть верхняя грань.
\end{thm}

\begin{proof}
Пусть $M = \cup \{ T | \langle T, (\prec) \rangle \in X \}$ и
$(\prec)_M = \cup \{ (\prec) | \langle T, (\prec) \rangle \in X \}$.

%\item Раз все элементы $X$ сравнимы, значит, любые два отношения порядка не противоречат друг другу
%(одно -- продолжение другого).
Покажем, что если $\langle A, (\prec_A)\rangle \in X$, то $A \sqsubseteq M$. Рассмотрим определение:
\begin{itemize}
\item $A \subseteq M$ --- выполнено по построению $M$;
\item если $a,b \in A$, то $a \prec_A b$ влечёт $a \prec_M b$ (по построению $M$). Если же $a \prec_M b$, но $a \not\prec_A b$,
то существует $A'$, что $a,b \in A'$ и $a \prec_{A'} b$. Тогда $A\not\sqsubseteq A'$ и $A'\not\sqsubseteq A$, что невозможно
по линейности порядка;
\item если $a \in A$, $b \in M\setminus A$, то найдётся $B$, что $b\in B$, отчего $a \prec_B b$ (так как $A \sqsubseteq B$) 
и $a \prec_M b$ (по построению $M$).
\end{itemize}
%Аналогично покажем, что $(\prec)_M$ --- отношение порядка.
Тогда $\langle M, (\prec_M)\rangle$ --- требуемая верхняя грань.
\end{proof}

\end{frame}

\begin{frame}{Лемма Цорна $\Rightarrow$ теорема Цермело}
Пусть выполнена лемма Цорна и дано некоторое $X$. Покажем, что на нём можно ввести полный порядок.
\begin{itemize}
\item Пусть $S = \{ \langle P, (\prec)\rangle \ |\ P \subseteq X, (\prec)\text{ --- полный порядок} \}$.
{\color{gray}Например, для $X = \{0,1\}$ множество
$S = \{
\langle\varnothing,\varnothing\rangle,
\langle \{0\},\varnothing\rangle,
\langle\{1\},\varnothing\rangle,
\langle X, 0 \prec 1\rangle,
\langle X, 1 \prec 0\rangle
\}$.}

\item Введём порядок на $S$ как $(\sqsubseteq)$. Заметим, что это --- частичный, но не линейный порядок. 
{\color{gray}Например, $\langle X, 0 \prec 1\rangle$ несравним с $\langle X, 1 \prec 0\rangle$.}

\item По теореме о верхней грани любое линейно упорядоченное подмножество 
$\langle T, (\sqsubseteq) \rangle$ (где $T \subseteq S$) имеет
верхнюю грань.

{\color{gray}Например, 
для $\{\langle\varnothing,\varnothing\rangle,
\langle \{0\},\varnothing\rangle,
\langle X, 0 \prec 1\rangle\}$ это $\langle X, 0 \prec 1\rangle$.}

\item По лемме Цорна тогда есть $\langle R, (\sqsubseteq_R)\rangle = \max S$. Заметим, что $R = X$, потому что иначе пусть
$a \in X\setminus R$. Тогда положив $M = \langle R\cup\{a\}, (\sqsubseteq_R)\cup\{x\prec a\ |\ x \in R\} \rangle$
получим, что $M$ тоже вполне упорядоченное (и потому $M \in S$), значит, $R$ не максимальное.
\end{itemize}
%\end{proof}
\end{frame}

\begin{frame}{Теорема Цермело $\Rightarrow$ существование обратной $\Rightarrow$ аксиома выбора}
\begin{thm}Теорема Цермело $\Rightarrow$ у сюръективных функций существует частичная обратная.\end{thm}
\begin{proof}
Рассмотрим сюръективную $f: A \rightarrow B$. Рассмотрим семейство $R_b = \{ a \in A\ |\ f(a) = b \}$.
Построим полный порядок на каждом из $R_b$. Тогда $f^{-1}(b) = \min R_b$.
\end{proof}
\begin{thm}Существует частичная обратная у сюръективных функций $\Rightarrow$ существует трансверсаль у семейства непустых дизъюнктных множеств.\end{thm}
\begin{proof}
Пусть дано семейство непустых дизъюнктных множеств $\mathcal{A}$. 
Рассмотрим $f: \cup \mathcal{A} \rightarrow \mathcal{A}$, что
$f(a) = \cup\{ A \in \mathcal{A}\ |\ a \in A \}$. Поскольку элементы $\mathcal{A}$ дизъюнктны,
$f(a) \in \mathcal{A}$ при всех $a$. Тогда существует $f^{-1}: \mathcal{A} \rightarrow \cup\mathcal{A}$. Тогда 
$\{ f^{-1}(A)\ |\ A\in\mathcal{A} \} \in \times \mathcal{A}$.
\end{proof}
\end{frame}

\begin{frame}{Зачем нужна аксиома выбора?}
\begin{dfn}Пределом функции $f$ в точке $x_0$ по \emph{Коши} называется такой $y$, что
$$\forall \varepsilon\in\mathbb{R}^+.\exists \delta\in\mathbb{R}^+.\forall x.|x-x_0| < \delta \rightarrow |f(x) - y| < \varepsilon$$
\end{dfn}

\vspace{-0.5cm}
\begin{dfn}Пределом функции $f$ в точке $x_0$ по \emph{Гейне} называется такой $y$, что
для любой $x_n \rightarrow x_0$ выполнено $f(x_n) \rightarrow y$.
\end{dfn}
\end{frame}

\begin{frame}{Предел по Гейне влечёт предел по Коши}
\begin{thm}
Если $\lim\limits_{x \rightarrow x_0}f(x) = y$ по Гейне, то
$\forall \varepsilon>0.\exists \delta>0.\forall x.|x-x_0|<\delta \rightarrow |f(x)-y| < \varepsilon$.
\end{thm}

\begin{proof}
Пусть не так:
$\exists \varepsilon>0.\forall \delta>0.\exists x_\delta.|x_\delta-x_0|<\delta \with |f(x_\delta)-y| \ge \varepsilon$.
Фиксируем $\varepsilon$ и возьмём $\delta_n = \frac{1}{n}$ и $p_n = x_{\delta_n}$. 
$p_n \rightarrow x_0$, так как $|x_\frac{1}{n} - x_0| < \frac{1}{n}$, 
по определению предела по Гейне $f(p_n) \rightarrow y$, 
но по предположению $\forall n\in\mathbb{N}.|f(p_n) - y| \ge \varepsilon$.
\end{proof}\pause

\begin{snote}
Для применения предела по Гейне нужна $p_n$: то есть $p: \mathbb{N}\rightarrow\mathbb{R}$.
%где $\Gamma(p) \subseteq \mathbb{N}\times\mathbb{R}$
\pause
%$\langle x_\frac{1}{1}: |x_\frac{1}{1}-x_0|<1 \with |f(x_\frac{1}{1})-y| \ge \varepsilon$; $x_\frac{1}{2}: |x_\frac{1}{2}-x_0|<\frac{1}{2} \with |f(x_\frac{1}{2})-y| \ge \varepsilon; ...\rangle$ 
%\pause

%\vspace{0.3cm}
... %$\exists \varepsilon.\forall \delta.\exists x_\delta.|x_\delta-x_0|<\delta \with |f(x_\delta)-y| \ge \varepsilon$.\\
Фиксируем $\varepsilon$ и рассмотрим $X_\delta = \{ x \ |\ |x-x_0| <\delta \with |f(x)-y| \ge \varepsilon\}$.
Отрицание предела по Коши означает, что $X_\delta \ne \varnothing$ при любом $\delta > 0$.
%Возьмём $\delta_n = \frac{1}{n}$ и $x_{\frac{1}{n}} \in X_\frac{1}{n}$.
\pause

... То есть по семейству $Q:=\{ X_1, X_\frac{1}{2}, X_\frac{1}{4}, \dots \}$ 
по аксиоме выбора построим $q: Q \rightarrow \cup Q$, что $q(X_\frac{1}{n}) \in X_\frac{1}{n}$.
Далее, взяв композицию $p_n := q(X_{\delta_n})$, получаем $p_n \rightarrow x_0$, что $\forall n\in\mathbb{N}.|f(p_n) - y| \ge \varepsilon$.
\end{snote}
\end{frame}

\begin{frame}{Предел по Коши влечёт предел по Гейне}
\begin{thm}Пусть $\lim\limits_{x \rightarrow x_0} f(x) = y$ и дана $x_n \rightarrow x_0$.
Тогда $f(x_n) \rightarrow y$.\end{thm}

\begin{proof}
%Пусть $\lim_{x \rightarrow x_0} f(x) = y$ и дана $x_n \rightarrow x_0$. 
%То есть, $\forall \varepsilon>0.\exists \delta>0.\forall x.|x-x_0| < \delta \rightarrow |f(x) - y| < \varepsilon$
Фиксируем $\varepsilon > 0$.
\begin{itemize}
%\item Заметим, что $\forall $ и $|x_n - x_0| < \delta\rightarrow|f(x_n) - y| < \varepsilon$.
\item $\exists \delta > 0.\exists N\in\mathbb{N}.(\forall x.|x - x_0| < \delta \rightarrow |f(x) - y| < \varepsilon) \with
(\forall n\in\mathbb{N}.n > N \rightarrow |x_n - x_0|<\delta).$
\item $(\forall x.|x - x_0| < \delta \rightarrow |f(x) - y| < \varepsilon) \rightarrow (|x_n - x_0| < \delta \rightarrow |f(x_n) - y| < \varepsilon)$ \ (сх. 11).
\item $\exists \delta > 0.\exists N\in\mathbb{N}.\forall n\in\mathbb{N}.n > N\rightarrow |f(x_n) - y| < \varepsilon$.
\item Поскольку $\delta$ не используется в формуле, $\exists \delta > 0$ можно устранить.
\item Отсюда $\exists N\in\mathbb{N}.\forall n\in\mathbb{N}.n > N\rightarrow |f(x_n) - y| < \varepsilon.$
\end{itemize}
\end{proof}\pause

Почему здесь не потребовалась аксиома выбора? Потому что нам нужен единственный $\delta$, а для него --- 
единственный $N$

\end{frame}

\begin{frame}{Равенство и функции}
\begin{exm}
Пусть $A_0 = \{0,1,3,5\}$ и $A_1 = \{3,5,1,0,0,5,3\}$.
Верно ли, что $A_0 = A_1$?\pause

Да, так как $\forall x.x \in \{0,1,3,5\} \leftrightarrow x \in \{3,5,1,0,0,5,3\}$.\end{exm}\pause

\begin{thm}[конгруэнтность]
Если $f: A \rightarrow B$, также $a,b\in A$ и $a=b$, то $f(a) = f(b)$.
\end{thm}

\begin{proof}
Пусть $F \subseteq A\times B$ --- график функции $f$.

%Легко показать, что если $a=b$ и $y_1 = y_2$, то $\langle a, y_1\rangle = \langle b,y_2\rangle$.\\
%Значит (по аксиоме равенства), $\langle a,x\rangle \in F$ тогда и только тогда,
%когда $\langle b,x\rangle \in F$. 
По определению функции, $\forall x.\forall y_1.\forall y_2.\langle x,y_1\rangle \in F \with \langle x,y_2 \rangle \in F \rightarrow y_1 = y_2$.\\
Также, если $f(a) = y_1$, $f(b) = y_2$, то $\langle a,y_1 \rangle \in F$ и $\langle b,y_2 \rangle \in F$.\\
Тогда: $\langle a,y_1\rangle = \langle b,y_1\rangle = \langle b,y_2 \rangle = \langle a,y_2\rangle$,
то есть $f(a) = y_2 = f(b)$.

%Пусть $\langle a,x \rangle \in F$ (поскольку $f$ --- функция, такое $x$ должно существовать).
%Тогда из $a=b$ следует $\langle b,x \rangle = \langle a,x \rangle$ (по свойствам упорядоченной пары), значит, $f(b) = x$.
\end{proof}
% следует $f(A_0) = f(A_1)$ 
%по определению функционального бинарного отношения:
%$$\forall x.\exists y.F(x, y) \with \forall y_0.\forall y_1.F(x,y_0) \with F(x,y_1) \rightarrow y_0=y_1$$.
%\end{exm}
\end{frame}

\begin{frame}{Теорема Диаконеску}
\begin{thm}Если рассмотреть ИИП с ZFC, то для любого $P$ выполнено $\vdash P \vee \neg P$.\end{thm}
\begin{proof}Фиксируем $P$. Рассмотрим $\mathcal{B} = \{0,1\}$, $A_0 = \{ x \in \mathcal{B} | x = 0 \vee P \}$ и 
$A_1 = \{ x \in \mathcal{B} | x = 1 \vee P\}$.
$\{A_0,A_1\}$ --- семейство непустых множеств, и по акс. выбора существует
$f: \{A_0,A_1\} \rightarrow \cup A_i$, что $f(A_i) \in A_i$. (Если $P$, то $A_0 = A_1$ и $\{A_0,A_1\} = \{\mathcal{B}\}$).

\vspace{0.3cm}
\begin{tabular}{ll}
$\vdash f(A_0) \in A_0 \with f(A_1) \in A_1$ & а.выбора: $f(A_i) \in A_i$\\
$\vdash {\color{olive}f(A_0) \in \mathcal{B}} \with (f(A_0) = 0 \vee P) \with {\color{olive}f(A_1) \in \mathcal{B}} \with (f(A_1) = 1 \vee P)$ & а.выделения\\
%$\vdash(f(A_0) = 0 \vee P) \with (f(A_1) = 1 \vee P)$ & Удал. $(\with)$\\
$\vdash (f(A_0) = 0 \with f(A_1) = 1) \vee P$ & Удал. $(\with)$ + дистр.\\
$\vdash P\vee{\color{blue}f(A_0) \ne f(A_1)}$ & $0 \ne 1$ и транз.\\\pause
$\vdash P \rightarrow A_0 = A_1$ & Определение $A_i$\\
$\vdash A_0 = A_1 \rightarrow f(A_0) = f(A_1)$ & Конгруэнтность\\
$\vdash \color{blue} f(A_0) \ne f(A_1) \rightarrow \neg P$ & Контрапозиция\\
$\vdash P \vee \neg P$ & Подставили
\end{tabular}
\end{proof}
\end{frame}

\begin{frame}{Слабые варианты аксиомы выбора}

\begin{thm}[конечного выбора]
Если $X_1\ne\varnothing, \dots, X_n\ne\varnothing$, $X_i\cap X_j = \varnothing$ при $i \ne j$, то $\times \{X_1, \dots, X_n\} \ne \varnothing$.
\end{thm}

\begin{proof}
\begin{itemize}\item База: $n=1$. Тогда $\exists x_1.x_1 \in X_1$, поэтому $\exists x_1.\{x_1\} \in \times \{X_1\}$.

\item Переход: %если $\exists v.v \in \times \{X_{1,n}\}$ и $\exists x_{n+1}.x_{n+1} \in X_{n+1}$, то
$\exists v.v \in \times \{X_{1,n}\}\rightarrow\exists x_{n+1}.x_{n+1} \in X_{n+1}\rightarrow
v \cup \{x_{n+1}\} \in \times (X_{1,n}\cup\{X_{n+1}\})$.
\end{itemize}\vspace{-0.3cm}\end{proof}

%Построим явно: $(\exists x_1.x_1 \in X_1) \rightarrow \exists f.\exists x_1.f = \{\langle X_1, x_1 \rangle\}\with x_1 \in X_1$

%Построим явно: $$\exists x_1.\dots\exists x_n.x_1 \in X_1 \with \dots \with x_n \in X_1 \rightarrow \varphi(\langle X_1, x_1\rangle, \dots, \langle X_n, x_n\rangle)$$
%И потом:
%$$X_1 \ne \varnothing \with \dots \with X_n \ne \varnothing \rightarrow \exists f.\varphi(f)$$

%Докажем явным выписыванием: 
%$x_1 \in X_1 \with \dots \with x_n \in X_n \rightarrow \varphi(\{\langle X_1, x_1\rangle, \dots, \langle X_n, x_n\rangle\})$\\
%$\exists x_1 \in X_1 \with \dots \with (\exists x_n \in X_n)\rightarrow \exists f.\varphi(f)$
%$$(x_1 \in X_1) \with \dots \with (x_n \in X_n) \rightarrow (f = \{\langle X_1, x_1 \rangle, \dots, \langle X_n, x_n \rangle\} \rightarrow f(X_1) = x_1 \with \dots \with f(X_n) = x_n)$$
%$$(f = \{\langle X_1, x_1 \rangle, \dots, \langle X_n, x_n \rangle\} \rightarrow f(X_1) = x_1 \with \dots \with f(X_n) = x_n)$$
%$$(\exists x_1. x_1 \in X_1)\with\dots\with(\exists x_n.x_n \in X_n)\rightarrow\exists f.f(X_1) \in X_1 \with \dots \with f(X_n) \in X_n$$

\begin{axm}[счётного выбора]
Для счётного семейства непустых множеств существует функция, каждому из которых сопоставляющая один из своих элементов.
\end{axm}

\begin{axm}[зависимого выбора]
Если $\forall x \in E.\exists y \in E. x R y$, то существует последовательность $x_n: \forall n.x_n R x_{n+1}$.
\end{axm}
\end{frame}

\begin{frame}{Теорема Диаконеску и конечный выбор}
Заметим, что семейство $\{A_0, A_1\}$ из теоремы Диаконеску в ИИП не является конечным (равно как и бесконечным).
\begin{dfn}Конечное множество --- равномощное некоторому конечному кардинальному числу.\end{dfn}

\begin{itemize}
\item Какова мощность семейства? 
\item 1, если $P$, и 2, если $\neg P$. 
\item Но поскольку $P \vee \neg P$ не выполнено в ИИП, мы не можем
доказать, что мощность семейства 1 или 2.
\item Поэтому мы не можем воспользоваться теоремой конечного выбора.
\end{itemize}
\end{frame}

\begin{frame}{Наследственные фундированные множества}
\begin{dfn}Наследственным свойством множества назовём такое свойство, которым обладает как само
множество, так и все его подмножества.
\end{dfn}

\begin{dfn}Фундированным множеством назовём такое, которое не пересекается хотя бы с одним своим элементом.\end{dfn}

\begin{dfn}Аксиома фундирования. 
В каждом непустом множестве найдется элемент, не пересекающийся с исходным множеством.
$$\forall x .x = \varnothing \vee \exists y .y \in x \with \forall z.z \in x \rightarrow z \notin y$$
\end{dfn}

Иными словами, в каждом множестве есть элемент, минимальный по отношению $(\in)$.
\end{frame}

\begin{frame}{Каковы возможные модели для теории множеств?}
\begin{dfn}\emph{Универсум фон Неймана} $V$ --- все наследственные фундированные множества.\end{dfn}

При наличии аксиомы фундирования можно показать, что $V = \cup_a V_a$, где:
$$V_a = \left\{\begin{array}{ll}
    \varnothing, & a=0\\
    \mathcal{P}(V_b), & a = b'\\
    \bigcup_{b < a}(V_b), & a \text{ --- предельный}
\end{array}\right.$$

\begin{dfn}
\emph{Конструктивный универсум} $L = \cup_a L_a$, где:
$$L_a = \left\{\begin{array}{ll}
    \varnothing, & a=0\\
    \{ \{ x\in L_b\ |\ \varphi(x,t_1,\dots,t_k) \}\ |\ \varphi\text{ --- формула}, t_i \in L_b\}, & a = b'\\
    \bigcup_{b < a}(L_b), & a \text{ --- пред.}
\end{array}\right.$$
\end{dfn}
\end{frame}

\begin{frame}{Усиление аксиомы выбора}
\begin{dfn}
Аксиома конструктивности: $V=L$, то есть допустимы только те фундированные множества, которые задаются формулами.
\end{dfn}

\begin{thm}Аксиома выбора и континуум-гипотеза следуют из аксиомы конструктивности\end{thm}

Для некоторых теорий аксиома слишком сильна.
\end{frame}

\begin{frame}{Заключительный обзор}
Конструктивность теории --- насколько легко строить сложные объекты в ней:
\begin{enumerate}
\item Неконструктивные теории допускают доказательства чистого существования произвольных по сложности объектов.
\item Конструктивные теории: требуют процесс построения (желательно конечный или хотя бы счётный), 
состоящий из интуитивно понятных шагов.
\end{enumerate}

Аксиома выбора и её рассмотренные варианты влияют на её конструктивность:
\begin{enumerate}
\item КИП + ЦФ + Акс. выбора: менее конструктивна.
Например, возможно показать существование разбиения шара на 5 частей, из которых можно составить два шара,
равных исходному (теорема Банаха-Тарского).
Интуитивно нарушается аддитивность объёма (формального парадокса нет).

\item КИП + ЦФ
\item ИИП + ЦФ: более конструктивна. Она проще формализуется с помощью компьютера, но мат. анализ в ней сложнее и довольно сильно отличается от классического.
\end{enumerate}
\end{frame}

\end{document}