Перечислимые и разрешимые множества — различия между версиями
WikiSysop (обсуждение | вклад) |
WikiSysop (обсуждение | вклад) |
||
| Строка 77: | Строка 77: | ||
<blockquote> | <blockquote> | ||
<math>\textstyle \mathcal A</math>: "множество всех алгоритмов не использующих оператор '''goto'''" | <math>\textstyle \mathcal A</math>: "множество всех алгоритмов не использующих оператор '''goto'''" | ||
| − | + | </blockquote> | |
| + | <blockquote> | ||
<math>\textstyle \mathcal B</math>: "множество всех определённых при данном <math>\textstyle x</math> функций <math>\textstyle f(x)</math>" | <math>\textstyle \mathcal B</math>: "множество всех определённых при данном <math>\textstyle x</math> функций <math>\textstyle f(x)</math>" | ||
| − | + | </blockquote> | |
| + | <blockquote> | ||
<math>\textstyle \mathcal C</math>: "множество всех алгоритмов решающих проблему остановки" | <math>\textstyle \mathcal C</math>: "множество всех алгоритмов решающих проблему остановки" | ||
</blockquote> | </blockquote> | ||
Текущая версия на 15:06, 4 марта 2010
| Проблемы остановки и тождественности << | Оглавление | >> Существуют ли несчетные множества? |
|---|
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Размышления о совокупностях объектов создало математику. Множество, как и любое базовое понятие, без порочного круга синонимов (собрание объектов, совокупность, класс) определить непросто. В любом случае, мы считаем, что существуют две сущности — множества и их элементы. Элементы мы обозначаем маленькими буквами Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle b} , а множества — большими Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} .
По Кантору, элементы множества являются объектами "хорошо различимыми нашей интуицией или нашей мыслью". Пока речь идёт о конечных множествах, можно предъявить кучу камней или саблезубых тигров. В этом случае множество задаётся перечислением всех своих элементов: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A = \{a,b,c\}} . При помощи предиката, т.е. логической функции от двух аргументов Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \in(a, \mathcal A)} , мы выражаем факт принадлежности элемента Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} множеству Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} (принадлежит, не принадлежит, и третьего не дано!). Принадлежность удобно записывать в операторном виде, ставя символ Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \in} между аргументами предиката: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\in \mathcal A} .
Помимо принадлежности для множеств состоящих их одних и тех же элементов вводится предикат равенства Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A= \mathcal B} . Если же множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} состоит из тех же элементов, что и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} , но они не равны, говорят, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} является подмножеством Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} . Для выражения этого утверждения вводится третий предикат: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A\subset \mathcal B} .
Кроме предикатов, для образования новых множеств вводится три предметные функции:
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}}
Задание множества при помощи логического условия: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A =\{x|\;условие\}} иногда очень удобно. Например, натуральные числа от 1 до 5 можно задать так: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A=\{1,2,3,4,5\}} , а можно и так Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A=\{x|\;(x>0) \,\And\, (x<6)\}} . То, что элемент не принадлежит множеству обозначается как Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x\not\in \mathcal B} . Это сокращение записи отрицания при помощи логической связки: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \neg (x\in \mathcal B)} .
Таким образом, в объединённое множество попадают все элементы из обоих множеств. В пересечение только общие для множеств элементы, а в дополнение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A - \mathcal B} только те элементы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} , которые не принадлежат Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} . Предполагается, что в множестве одинаковые элементы всегда встречаются только один раз. Для неупорядоченных множеств порядок расположения элементов не играет роли.
Удобно рассматривать понятие основного или фундаментального множества Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal R} , содержащего все элементы какого-нибудь заданного типа. Например, фундаментальным будет множество всех натуральных чисел. Задав его, можно говорить о различных подмножествах натуральных чисел (чётные, простые, и т.п.). При помощи функций Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A\cup \mathcal B} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A\cap \mathcal B} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A-\mathcal B} можно строить новые множества.
Эти базовые функции можно визуализовать при помощи диаграмм Эйлера-Венна, в которых замкнутая область обозначает некоторое множество. Область геометрического пересечения двух множеств будет множественным пересечением Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A\cap \mathcal B} , и т.д.:

В такой форме теория множеств возвращается к своим наглядным истокам — куче камней на полу в пещере. Для того чтобы множественные функции были замкнутыми необходимо ввести объект — пустое множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \varnothing} . Например, Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle (\mathcal A- \mathcal B)\cap \mathcal B = \varnothing} .
Чтобы определить конкретное множество необходимо каким-то образом выразить факт принадлежности ему некоторого элемента. Другими словами, для всех Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} задать логические значения функции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\in A} . Множество может быть бесконечным, и нам необходим конечный способ его задания. Поэтому мы должны предложить алгоритм, который "разрешает" помещать число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} в множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle A} . Например, если число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p} не имеет делителей кроме 1 и себя, то оно является элементом множества простых чисел Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal P} , т.е. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p\in \mathcal P} . В данном случае существует функция которая на вход получает число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p} , раскладывает его на множители и возвращает 1 для простых чисел или 0 для составных.
Другой способ состоит в том, чтобы при помощи некоторого алгоритма "перечислять" элементы множества. Так множество чётных чисел можно задать в перечислительном варианте как Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e_k=2*k} , где Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle k} все натуральные числа (т.е. выразить одно множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal X} через элементы другого Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal Y} в виде функции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y=f(x)} ). Ещё более "перечислительно" будет выглядеть определение при помощи рекурсии: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e_1=0} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e_k=e_{k-1}+2} .
В результате мы приходим к некоторой классификации конструктивных множеств по способу их построения. В частности говорим, что могут быть разрешимые и перечислимые множества.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Разрешимым называется множество целых чисел для которого существует алгоритм определения принадлежности ему некоторого элемента. Для разрешимого множества Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle {\mathcal A}} задаётся вычислимая и всюду определённая функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)} :
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{is}(a) = \left\{ \begin{array}{ll} 1,\;\;\;\;& если\;a\in \mathcal A\\ 0,\;\;\;\;& если\;a\not \in \mathcal A.\\ \end{array} \right.}
Естественно, наличие внутри Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)} символа принадлежности не означает, что мы пользуемся кем то заданным предикатом Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\in A} (получился бы порочный круг). Вместо "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\in A} " стоит конечная последовательность символов некоторой программы, которая должна выдать не нулевое значение, тогда Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)=1} . Если же эта программа, или другая "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\not \in \mathcal A} " выдаёт ноль, то Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)=0} . Функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)} называется характеристической.
Так как существует "Проблема Остановки", будем считать, что разрешимым будет только множество, для алгоритма которого доказано (!), что он останавливается при любых входах.
Можно ввести также понятие "частично разрешимое множество" для которого функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(a)} является частичной, т.е. определённой не для всех Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} . Тогда для некоторых Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} будет неизвестно принадлежат они множеству или нет. Это уже не очень "хорошее" множество.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Перечислимым называется подмножество натуральных чисел, все элементы которого можно получать (перечислять) при помощи алгоритма. Это означает что существует некоторая функция, которая в своей памяти последовательно размещает числа. Например, Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal M: \{3, 14, 15,92, ....\}} , т.е. после нескольких шагов алгоритма добавляется новое число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e_1} , затем после, вообще говоря, другого числа шагов добавляется Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e_2} , и т.д. Приведенный в предыдущем разделе алгоритм поиска в ширину создавал подобные перечислимые множества зависимостей.
Если алгоритм перечисления существует, то его можно переписать в виде выдачи Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i} -того элемента последовательности. Таким образом, для перечислимого множества существует вычислимая функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{get}(i)} :
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathcal E : \{e_1, e_2, e_3, ....\}\;\;\;\;\;=>\;\;\;\;\;\;\mathbf{get}(i)\{\;...\;\mathbf{return }\;e_i\;\},}
т.е. её значение равно Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i} -тому элементу множества.
Однако, в отличии от Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(x)} , Функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{get}(i)} может быть частичной функций. Точнее, начиная с некоторого номера Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i} она не определена. Это означает, что породив несколько элементов множества, алгоритм перечисления может зациклиться и перестать выдавать элементы. Неприятность состоит в том, что мы не всегда можем распознать попадание алгоритма в подобный режим.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Важно понимать, что хотя алгоритм перечисления последовательно даёт элементы множества, это не означает, что мы способны узнать принадлежность некого, ещё не полученного числа к множеству. Т.е. перечислимое множество не обязательно разрешимо Если бы можно было доказать эквивалентность разрешимых и перечислимых множеств, смысл бы в подобном делении отпал.
Понятно, что любое разрешимое множество перечислимо. Для построения алгоритма его перечисления можно в цикле вызывать функцию Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(x)} для Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=0,1,2,...} , выдавая в память (перечисляя) только числа для которых Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(x)=1} . Этот пример ещё раз показывает, что перечислимое множество определяется, вообще говоря, частичным алгоритмом. Например, пусть разрешимое множество задано алгоритмом: "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x\in \mathcal A} если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x<4} . Тогда понятно, что после Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=3} алгоритм перечисления начинает крутится неограничено долго.
Область определения любой вычислимой функции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(x)} является перечислимым. Действительно, всегда можно реализовать алгоритм пошагового выполнения функции. Сделаем один шаг алгоритма для Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(0)} , затем по два шага алгоритма для Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(0)} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(1)} , затем по три шага для Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(0)} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(1)} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(2)} , и т.д. Если на некоторой итерации этого процесса одно из вычислений Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(x)} останавливается по return, то алгоритм перечисления выдаёт значение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} в множество определения функции. Таким образом, если при некоторых Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(x)} не определена, то они будут в списке пошагово выполняющихся функций "висеть" бесконечно долго, но процесс перечисления не заблокируют.
Далее. Пусть у нас есть подмножество натуральных чисел Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} и его дополнение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bar{\mathcal A}} (т.е. все остальные натуральные числа не попавшие в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} ). Если и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} , и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bar{\mathcal A}} перечислимы, то множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle {\mathcal A}} разрешимо. Это утверждение носит название теорема Поста:
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{clccl} \mathcal A &разрешимо &=>& \mathcal A,\bar{\mathcal A} & перечислимы\\ \mathcal A,\bar{\mathcal A} & перечислимы&=>& \mathcal A &разрешимо \end{array}}
Алгоритм разрешения Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{is}(x)} следующий. Для данного Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} запускаем одновременно пошагово выполняться алгоритмы порождения множеств Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} , и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bar{\mathcal A}} . По определению Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} находится в одном из этих множеств, поэтому рано или поздно будет порождён.
Ещё раз подчеркнём: 1) алгоритм перечисления может никогда не остановиться, хотя и перестанет выдавать новые числа; 2) порядок перечисления не регламентируется, и числа могут быть не упорядочены, например по возрастанию; 3) алгоритм перечисляет все элементы, но зацикливается если множество конечно.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Таким образом, алгоритмы и вычислимые функции позволяют формализовать идею конструктивного множества, дав ей некоторые любопытные оттенки. В частности, и разрешимое и перечислимое множества задаются алгоритмом, но разрешимые множества более эффективны и являются более "правильными" множествами чем перечислимые.
Естественно, тут же возникает вопрос — "а ограничены ли мы только конструктивными множествами?" Ответ на него очень непрост и существенно зависит от философской позиции математика, точнее тех правил Игры, которые он для себя считает приемлемыми. Неконструктивные множества существуют, если допустимо работать с "неясными" понятиями, по крайней мере до момента возникновения парадоксов.
Рассмотрим пример. Пусть фундаментальным множеством Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal R} является множество всех алгоритмов. Это множество достаточно хорошо определено. Мы можем не только упорядочивать алгоритмы, перечисляя их, но и разрешать. В частности, всегда можно однозначным образом проверить что данная цепочка символов является синтаксически верным алгоритмом.
"Определим" теперь три подмножества Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal R} :
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} : "множество всех алгоритмов не использующих оператор goto"
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} : "множество всех определённых при данном Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} функций Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f(x)} "
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal C} : "множество всех алгоритмов решающих проблему остановки"
Множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A} , являющееся разрешимым (если функция не порождает бесконечной цепочки вызовов других функций). Существуют конкретные элементы подобного множества, мы можем их разрешать или порождать.
Множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal B} является уже неразрешимым, но перечислимым. Точнее для некоторых элементов предикат Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle b\in B} определён, тогда как для других не определён, и мы не можем сказать принадлежит ли Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle b} к Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle B} или нет. Это уже не так хорошо. У нас нет способа применять к такому объекту множественные операции. Например, мы не можем однозначно определить дополнение до всех алгоритмов Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal R - \mathcal B} .
Третье множество Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal C} выглядит совсем плохим. Более того, в силу теоремы Тьюринга такого множества просто не существует. Но мы же его задали, причём такой однозначной фразой! Очень часто в математике рассматриваются множества определённые не алгоритмом, а некоторым общим описанием, например "возьмём множество всех множеств". Пока противоречия не возникают рассуждать о таких объектах конечно можно. Но где проходит грань неясности между "множеством всех множеств" и "множеством тех множеств которые не являются множествами" Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \ddot\smile} ?.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Многие математические задачи имеют алгоритмическое решение. Например, при помощи алгоритма мы всегда можем сложить два числа, или разложить любое число на простые множители. Однако, есть алгоритмически неразрешимые задачи. Примером такой задачи является "Проблема Остановки".
Ещё один хорошо известный пример связан с диафантовыми уравнениями. Они являются полиномами с целыми коэффициентами и несколькими неизвестными. Примеры таких уравнений:
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x^2+2x+1=0;\;\;\;\;\;\;\;\;\;x\cdot y=z;\;\;\;\;\;\;\;\;\;\;\;x^3+y^3=z^3;...}
В 10-проблеме Гильберта, сформулированной в 1901г. требуется найти алгоритм определяющий для любого диафантового уравнения, имеет ли оно целочисленные решения или нет. Более того, сами решения строить не обязательно, достаточно узнать что они есть в принципе. Таким образом, требуется построить разрешающий алгоритм на вход которого подаётся уравнение (или его номер), а на выходе получается 1, если уравнение имеет решения, и 0 — если нет.
Для некоторых классов уравнений подобные алгоритмы существуют. Например, решения уравнения Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a_n x^n+a_{n-1} x^{n-1}+...+ a_1 x+ a_0 = 0} находятся среди делителей свободного члена Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a_0} . Всегда имеет решение уравнение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x\cdot y=z} . Можно доказать, что уравнение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x^3+y^3=z^3} не имеет решений, и т.д. Однако, как и в "Проблеме Остановки", стоит задача построения универсального алгоритма для любого диафантового уравнения. В 1970г. Юрий Владимирович Матиясевич доказал неразрешимость этой задачи.
Подобная "деструктивная" деятельность очень увлекательна и обычно использует метод доказательств от обратного: "предположим, что такой алгоритм существует ....., мы пришли к противоречию, значит его нет". Понятно, что с такими противоречиями необходимо обходиться придельно осторожно. Особый интерес вызывает также и обратная задача — максимальное расширения класса разрешимых уравнений для которых можно выяснить наличие или отсутствие у них решений. Аналогично можно искать класс неразрешимых уравнений, и т.д.
Если считать проблему Гильберта решённую в таком отрицательном варианте, то понятно, что говорить о множестве Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal S} : "всех диафантовых уравнений имеющих решения" можно, но "хорошим" его назвать трудно, хотя оно и является перечислимым. Заметим, что до 1970 г. подобные категории уточнения определения Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal S} были просто не доступны. Еще хуже, когда не известно, является ли множество хотя бы перечислимым. Работа с такими объектами требует незаурядного мужества.
| Проблемы остановки и тождественности << | Оглавление | >> Существуют ли несчетные множества? |
|---|
Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе