Просмотр

{| width="100%"  
 | width="40%"|[[Проблемы остановки и тождественности]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Существуют ли несчетные множества?]]
|}
----
<math>\textstyle \bullet</math> Размышления о совокупностях объектов создало математику. Множество, как и любое базовое понятие, без порочного круга синонимов (собрание объектов, совокупность, класс) определить непросто. В любом случае, мы считаем, что существуют две сущности &mdash; множества и их элементы. Элементы мы обозначаем маленькими буквами <math>\textstyle a</math>, <math>\textstyle b</math>, а множества &mdash; большими <math>\textstyle \mathcal A</math>, <math>\textstyle \mathcal B</math>.

По Кантору, элементы множества являются объектами "хорошо различимыми нашей интуицией или нашей мыслью". Пока речь идёт о конечных множествах, можно предъявить кучу камней или саблезубых тигров. В этом случае множество задаётся перечислением всех своих элементов: <math>\textstyle \mathcal A = \{a,b,c\}</math>. При помощи ''предиката'', т.е. логической функции от двух аргументов <math>\textstyle \in(a, \mathcal A)</math>, мы выражаем факт ''принадлежности'' элемента <math>\textstyle a</math> множеству <math>\textstyle \mathcal A</math> (принадлежит, не принадлежит, и третьего не дано!). Принадлежность удобно записывать в операторном виде, ставя символ <math>\textstyle \in</math> между аргументами предиката: <math>\textstyle a\in \mathcal A</math>.

Помимо принадлежности для множеств состоящих их одних и тех же элементов вводится предикат равенства <math>\textstyle \mathcal A= \mathcal B</math>. Если же множество <math>\textstyle \mathcal A</math> состоит из тех же элементов, что и <math>\textstyle \mathcal B</math>, но они не равны, говорят, что <math>\textstyle \mathcal A</math> является ''подмножеством'' <math>\textstyle \mathcal B</math>. Для выражения этого утверждения вводится третий предикат: <math>\textstyle \mathcal A\subset \mathcal B</math>.

Кроме предикатов, для образования новых множеств вводится три предметные функции:

:<center><math>\begin{array}{llll} объединение: & \mathcal A\cup \mathcal B \;\;= &\{ x | \;\; (x\in \mathcal A) \vee (x\in \mathcal B)\}\\ пересечение: & \mathcal A\cap \mathcal B \;\;= &\{ x | \;\; (x\in \mathcal A) \,\And\, (x\in \mathcal B)\}\\ дополнение: & \mathcal A - \mathcal B \;\;= &\{ x | \;\; (x\in \mathcal A)\,\And\, (x\not\in \mathcal B)\}\\ \end{array}</math></center>

Задание множества при помощи логического условия: <math>\textstyle \mathcal A =\{x|\;условие\}</math> иногда очень удобно. Например, натуральные числа от 1 до 5 можно задать так: <math>\textstyle \mathcal A=\{1,2,3,4,5\}</math>, а можно и так <math>\textstyle \mathcal A=\{x|\;(x>0) \,\And\, (x<6)\}</math>. То, что элемент не принадлежит множеству обозначается как <math>\textstyle x\not\in \mathcal B</math>. Это сокращение записи отрицания при помощи логической связки: <math>\textstyle \neg (x\in \mathcal B)</math>.

Таким образом, в объединённое множество попадают все элементы из обоих множеств. В пересечение только общие для множеств элементы, а в дополнение <math>\textstyle \mathcal A - \mathcal B</math> только те элементы <math>\textstyle \mathcal A</math>, которые не принадлежат <math>\textstyle \mathcal B</math>. Предполагается, что в множестве одинаковые элементы всегда встречаются только один раз. Для неупорядоченных множеств порядок расположения элементов не играет роли.

Удобно рассматривать понятие основного или фундаментального множества <math>\textstyle \mathcal R</math>, содержащего ''все'' элементы какого-нибудь заданного типа. Например, фундаментальным будет множество всех натуральных чисел. Задав его, можно говорить о различных подмножествах натуральных чисел (чётные, простые, и т.п.). При помощи функций <math>\textstyle \mathcal A\cup \mathcal B</math>, <math>\textstyle \mathcal A\cap \mathcal B</math> и <math>\textstyle \mathcal A-\mathcal B</math> можно строить новые множества.

Эти базовые функции можно визуализовать при помощи диаграмм Эйлера-Венна, в которых замкнутая область обозначает некоторое множество. Область геометрического пересечения двух множеств будет множественным пересечением <math>\textstyle \mathcal A\cap \mathcal B</math>, и т.д.: 

<center>[[File:sets.png]]</center>

В такой форме теория множеств возвращается к своим наглядным истокам &mdash; куче камней на полу в пещере. Для того чтобы множественные функции были замкнутыми необходимо ввести объект &mdash; пустое множество <math>\textstyle \varnothing</math>. Например, <math>\textstyle (\mathcal A- \mathcal B)\cap \mathcal B = \varnothing</math>.

Чтобы определить ''конкретное'' множество необходимо каким-то образом выразить факт принадлежности ему некоторого элемента. Другими словами, для всех <math>\textstyle a</math> задать логические значения функции <math>\textstyle a\in A</math>. Множество может быть ''бесконечным'', и нам необходим ''конечный'' способ его задания. Поэтому мы должны предложить ''алгоритм'', который "''разрешает''" помещать число <math>\textstyle a</math> в множество <math>\textstyle A</math>. Например, если число <math>\textstyle p</math> не имеет делителей кроме 1 и себя, то оно является элементом множества простых чисел <math>\textstyle \mathcal P</math>, т.е. <math>\textstyle p\in \mathcal P</math>. В данном случае существует функция которая на вход получает число <math>\textstyle p</math>, раскладывает его на множители и возвращает 1 для простых чисел или 0 для составных.

Другой способ состоит в том, чтобы при помощи некоторого алгоритма "''перечислять''" элементы множества. Так множество чётных чисел можно задать в перечислительном варианте как <math>\textstyle e_k=2*k</math>, где <math>\textstyle k</math> все натуральные числа (т.е. выразить одно множество <math>\textstyle \mathcal X</math> через элементы другого <math>\textstyle \mathcal Y</math> в виде функции <math>\textstyle y=f(x)</math>). Ещё более "перечислительно" будет выглядеть определение при помощи рекурсии: <math>\textstyle e_1=0</math>, <math>\textstyle e_k=e_{k-1}+2</math>.

В результате мы приходим к некоторой классификации ''конструктивных'' множеств по способу их построения. В частности говорим, что могут быть разрешимые и перечислимые множества.

<math>\textstyle \bullet</math> ''Разрешимым'' называется множество целых чисел для которого существует алгоритм определения принадлежности ему некоторого элемента. Для разрешимого множества <math>\textstyle {\mathcal A}</math> задаётся ''вычислимая'' и всюду ''определённая'' функция <math>\textstyle \mathbf{is}(a)</math>:

:<center><math>\mathbf{is}(a) = \left\{ \begin{array}{ll} 1,\;\;\;\;& если\;a\in \mathcal A\\ 0,\;\;\;\;& если\;a\not \in \mathcal A.\\ \end{array} \right.</math></center>

Естественно, наличие внутри <math>\textstyle \mathbf{is}(a)</math> символа принадлежности не означает, что мы пользуемся кем то заданным предикатом <math>\textstyle a\in A</math> (получился бы порочный круг). Вместо "<math>\textstyle a\in A</math>" стоит конечная последовательность символов некоторой программы, которая должна выдать не нулевое значение, тогда <math>\textstyle \mathbf{is}(a)=1</math>. Если же эта программа, или другая "<math>\textstyle a\not \in \mathcal A</math>" выдаёт ноль, то <math>\textstyle \mathbf{is}(a)=0</math>. Функция <math>\textstyle \mathbf{is}(a)</math> называется ''характеристической''.

Так как существует "Проблема Остановки", будем считать, что разрешимым будет только множество, для алгоритма которого ''доказано'' (!), что он останавливается при любых входах.

Можно ввести также понятие "''частично разрешимое множество''" для которого функция <math>\textstyle \mathbf{is}(a)</math> является частичной, т.е. определённой не для всех <math>\textstyle a</math>. Тогда для некоторых <math>\textstyle a</math> будет неизвестно принадлежат они множеству или нет. Это уже не очень "хорошее" множество.

<math>\textstyle \bullet</math> ''Перечислимым'' называется подмножество натуральных чисел, ''все'' элементы которого можно получать (перечислять) при помощи алгоритма. Это означает что существует некоторая функция, которая в своей памяти последовательно размещает числа. Например, <math>\textstyle \mathcal M: \{3, 14, 15,92, ....\}</math>, т.е. после нескольких шагов алгоритма добавляется новое число <math>\textstyle e_1</math>, затем после, вообще говоря, другого числа шагов добавляется <math>\textstyle e_2</math>, и т.д. Приведенный в предыдущем разделе алгоритм поиска в ширину создавал подобные перечислимые множества зависимостей.

Если алгоритм перечисления существует, то его можно переписать в виде выдачи <math>\textstyle i</math>-того элемента последовательности. Таким образом, для перечислимого множества существует ''вычислимая'' функция <math>\textstyle \mathbf{get}(i)</math>:

:<center><math>\mathcal E : \{e_1, e_2, e_3, ....\}\;\;\;\;\;=>\;\;\;\;\;\;\mathbf{get}(i)\{\;...\;\mathbf{return }\;e_i\;\},</math></center>

т.е. её значение равно <math>\textstyle i</math>-тому элементу множества.

Однако, в отличии от <math>\textstyle \mathbf{is}(x)</math>, Функция <math>\textstyle \mathbf{get}(i)</math> может быть ''частичной функций''. Точнее, начиная с некоторого номера <math>\textstyle i</math> она не определена. Это означает, что породив несколько элементов множества, алгоритм перечисления может зациклиться и перестать выдавать элементы. Неприятность состоит в том, что мы не всегда можем распознать попадание алгоритма в подобный режим.

<math>\textstyle \bullet</math> Важно понимать, что хотя алгоритм перечисления последовательно даёт элементы множества, это не означает, что мы способны узнать принадлежность некого, ''ещё не полученного'' числа к множеству. Т.е. ''перечислимое множество не обязательно разрешимо'' Если бы можно было доказать эквивалентность разрешимых и перечислимых множеств, смысл бы в подобном делении отпал.

Понятно, что любое разрешимое множество перечислимо. Для построения алгоритма его перечисления можно в цикле вызывать функцию <math>\textstyle \mathbf{is}(x)</math> для <math>\textstyle x=0,1,2,...</math>, выдавая в память (перечисляя) только числа для которых <math>\textstyle \mathbf{is}(x)=1</math>. Этот пример ещё раз показывает, что перечислимое множество определяется, вообще говоря, частичным алгоритмом. Например, пусть разрешимое множество задано алгоритмом: "<math>\textstyle x\in \mathcal A</math> если <math>\textstyle x<4</math>. Тогда понятно, что после <math>\textstyle x=3</math> алгоритм перечисления начинает крутится неограничено долго.

Область определения любой вычислимой функции <math>\textstyle f(x)</math> является перечислимым. Действительно, всегда можно реализовать алгоритм пошагового выполнения функции. Сделаем один шаг алгоритма для <math>\textstyle f(0)</math>, затем по два шага алгоритма для <math>\textstyle f(0)</math> и <math>\textstyle f(1)</math>, затем по три шага для <math>\textstyle f(0)</math>, <math>\textstyle f(1)</math>, <math>\textstyle f(2)</math>, и т.д. Если на некоторой итерации этого процесса одно из вычислений <math>\textstyle f(x)</math> останавливается по '''return''', то алгоритм перечисления выдаёт значение <math>\textstyle x</math> в множество определения функции. Таким образом, если при некоторых <math>\textstyle x</math> функция <math>\textstyle f(x)</math> не определена, то они будут в списке пошагово выполняющихся функций "висеть" бесконечно долго, но процесс перечисления не заблокируют.

Далее. Пусть у нас есть подмножество натуральных чисел <math>\textstyle \mathcal A</math> и его дополнение <math>\textstyle \bar{\mathcal A}</math> (т.е. все остальные натуральные числа не попавшие в <math>\textstyle \mathcal A</math>). Если и <math>\textstyle \mathcal A</math>, и <math>\textstyle \bar{\mathcal A}</math> перечислимы, то множество <math>\textstyle {\mathcal A}</math> разрешимо. Это утверждение носит название ''теорема Поста'':

:<center><math>\begin{array}{clccl} \mathcal A &разрешимо &=>& \mathcal A,\bar{\mathcal A} & перечислимы\\ \mathcal A,\bar{\mathcal A} & перечислимы&=>& \mathcal A &разрешимо \end{array}</math></center>

Алгоритм разрешения <math>\textstyle \mathbf{is}(x)</math> следующий. Для данного <math>\textstyle x</math> запускаем ''одновременно'' пошагово выполняться алгоритмы порождения множеств <math>\textstyle \mathcal A</math>, и <math>\textstyle \bar{\mathcal A}</math>. ''По определению'' <math>\textstyle x</math> находится в одном из этих множеств, поэтому рано или поздно будет порождён.

Ещё раз подчеркнём: 1) алгоритм перечисления может никогда не остановиться, хотя и перестанет выдавать новые числа; 2) порядок перечисления не регламентируется, и числа могут быть не упорядочены, например по возрастанию; 3) алгоритм перечисляет ''все'' элементы, но зацикливается если множество конечно.

<math>\textstyle \bullet</math> Таким образом, алгоритмы и вычислимые функции позволяют формализовать идею конструктивного множества, дав ей некоторые любопытные оттенки. В частности, и разрешимое и перечислимое множества задаются алгоритмом, но разрешимые множества более эффективны и являются более "правильными" множествами чем перечислимые.

Естественно, тут же возникает вопрос &mdash; "а ограничены ли мы только конструктивными множествами?" Ответ на него очень непрост и существенно зависит от философской позиции математика, точнее тех правил Игры, которые он для себя считает приемлемыми. Неконструктивные множества существуют, если допустимо работать с "неясными" понятиями, по крайней мере до момента возникновения парадоксов.

Рассмотрим пример. Пусть фундаментальным множеством <math>\textstyle \mathcal R</math> является множество всех алгоритмов. Это множество достаточно хорошо определено. Мы можем не только упорядочивать алгоритмы, перечисляя их, но и разрешать. В частности, всегда можно однозначным образом проверить что данная цепочка символов является синтаксически верным алгоритмом.

"Определим" теперь три подмножества <math>\textstyle \mathcal R</math>: 

<blockquote> 
<math>\textstyle \mathcal A</math>: "множество всех алгоритмов не использующих оператор '''goto'''" 
</blockquote> 
<blockquote> 
<math>\textstyle \mathcal B</math>: "множество всех определённых при данном <math>\textstyle x</math> функций <math>\textstyle f(x)</math>"
</blockquote> 
<blockquote> 
<math>\textstyle \mathcal C</math>: "множество всех алгоритмов решающих проблему остановки" 
</blockquote>

Множество <math>\textstyle \mathcal A</math>, являющееся разрешимым (если функция не порождает бесконечной цепочки вызовов других функций). Существуют конкретные элементы подобного множества, мы можем их разрешать или порождать.

Множество <math>\textstyle \mathcal B</math> является уже неразрешимым, но перечислимым. Точнее для некоторых элементов предикат <math>\textstyle b\in B</math> определён, тогда как для других не определён, и мы не можем сказать принадлежит ли <math>\textstyle b</math> к <math>\textstyle B</math> или нет. Это уже не так хорошо. У нас нет способа применять к такому объекту множественные операции. Например, мы не можем однозначно определить дополнение до всех алгоритмов <math>\textstyle \mathcal R - \mathcal B</math>.

Третье множество <math>\textstyle \mathcal C</math> выглядит совсем плохим. Более того, в силу теоремы Тьюринга такого множества просто не существует. Но мы же его задали, причём такой однозначной фразой! Очень часто в математике рассматриваются множества определённые не алгоритмом, а некоторым общим описанием, например "возьмём множество всех множеств". Пока противоречия не возникают рассуждать о таких объектах конечно можно. Но где проходит грань неясности между "множеством всех множеств" и "множеством тех множеств которые не являются множествами" <math>\textstyle \ddot\smile</math>?.

<math>\textstyle \bullet</math> Многие математические задачи имеют алгоритмическое решение. Например, при помощи алгоритма мы всегда можем сложить два числа, или разложить любое число на простые множители. Однако, есть алгоритмически неразрешимые задачи. Примером такой задачи является "Проблема Остановки".

Ещё один хорошо известный пример связан с ''диафантовыми уравнениями''. Они являются полиномами с целыми коэффициентами и несколькими неизвестными. Примеры таких уравнений:

:<center><math>x^2+2x+1=0;\;\;\;\;\;\;\;\;\;x\cdot y=z;\;\;\;\;\;\;\;\;\;\;\;x^3+y^3=z^3;...</math></center>

В 10-проблеме Гильберта, сформулированной в 1901г. требуется найти алгоритм определяющий для любого диафантового уравнения, имеет ли оно целочисленные решения или нет. Более того, сами решения строить не обязательно, достаточно узнать что они есть в принципе. Таким образом, требуется построить ''разрешающий алгоритм'' на вход которого подаётся уравнение (или его номер), а на выходе получается 1, если уравнение имеет решения, и 0 &mdash; если нет.

Для некоторых классов уравнений подобные алгоритмы существуют. Например, решения уравнения <math>\textstyle a_n x^n+a_{n-1} x^{n-1}+...+ a_1 x+ a_0 = 0</math> находятся среди делителей свободного члена <math>\textstyle a_0</math>. Всегда имеет решение уравнение <math>\textstyle x\cdot y=z</math>. Можно доказать, что уравнение <math>\textstyle x^3+y^3=z^3</math> не имеет решений, и т.д. Однако, как и в "Проблеме Остановки", стоит задача построения универсального алгоритма для ''любого'' диафантового уравнения. В 1970г. Юрий Владимирович Матиясевич доказал неразрешимость этой задачи.

Подобная "деструктивная" деятельность очень увлекательна и обычно использует метод доказательств от обратного: "предположим, что такой алгоритм существует ....., мы пришли к противоречию, значит его нет". Понятно, что с такими противоречиями необходимо обходиться придельно осторожно. Особый интерес вызывает также и обратная задача &mdash; максимальное расширения класса разрешимых уравнений для которых можно выяснить наличие или отсутствие у них решений. Аналогично можно искать класс неразрешимых уравнений, и т.д.

Если считать проблему Гильберта решённую в таком отрицательном варианте, то понятно, что говорить о множестве <math>\textstyle \mathcal S</math>: "всех диафантовых уравнений имеющих решения" можно, но "хорошим" его назвать трудно, хотя оно и является перечислимым. Заметим, что до 1970 г. подобные категории уточнения определения <math>\textstyle \mathcal S</math> были просто не доступны. Еще хуже, когда не известно, является ли множество хотя бы перечислимым. Работа с такими объектами требует незаурядного мужества.
----
{| width="100%"  
 | width="40%"|[[Проблемы остановки и тождественности]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Существуют ли несчетные множества?]]
|}
----
[[Истинность и доказуемость]] - о конструктивной математике, Канторе и Гёделе