О счётности простых деревьев и следствиях из неё

Размещено на http://www.allbest.ru/

О счётности простых деревьев и следствиях из неё

В.Л. Чечулин

Аннотация

Ввиду доказанной ранее некорректности диагонального метода (Зенкин) переобоснованы, посредством семантики самопринадлежности, теоремы Гёделя, а также утверждения о несчетности количества точек прямой; указано на возможность лишь счетного количества обозначений, построен пересчет обозначений n-ичных разложений чисел на отрезке [0, 1).

Ключевые слова: семантика самопринадлежности; теоремы Гёделя; предикативные и непредикативные формальные системы; несчетность числа точек на прямой; счетность обозначений.

1. Предисловие

В 1997 г. Зенкиным А.А. были опубликованы результаты [1], показывающие некорректность диагонального метода Кантора Этот диагональный метод был представлен как правдоподобное, но парадоксальное (нефинитное) рассуждение, см. подробнее в [1].© В.Л. Чечулин, 2010. В связи с этим возникает потребность в анализе и переобосновании базирующихся на этом диагональном методе утверждений, что и представлено ниже, с использованием семантики самопринадлежности, введенной русским математиком Миримановым еще в 1918 г. [2].

С одной стороны, приведено описание краткого варианта доказательств теорем Гёделя, с другой - в теории множеств с самопринадлежностью разрешен аналог континуум-гипотезы.

2. Краткое доказательство теорем Гёделя

Подробно основания структур с самопринадлежностью и сами эти структуры описаны в работах [3], [4], для понимания этого параграфа достаточно интуитивного представления о несамопринадлежащих, XX, и самопринадлежащих, YY, объектах.

Теоремы Гёделя доказываются достаточно кратко. Пусть имеется предикативная теория Т такая, в которой есть набор аксиом (схем аксиом) Аi, и выводимые утверждения Вj,

(Ai1, …, Ain, Вj1,..., Вjm) |= Вj0, (1)

причем это выводимое утверждение не содержится в цепи вывода от аксиом до себя самого, т. е. в левой части формулы (1), которую, безотносительно ее содержания, обозначим через L, {Ai1, …, Ain, Вj1,..., Вjm} = L, Вj0 L.

Теорема 1. В предикативной системе не доказуема ее непротиворечивость.

Теорема 2 (о неполноте). Предикативная теория не полна.

Схемы доказательств этих теорем одинаковы: непредикативные утверждения о непротиворечивости, или полноте, предикативной теории Т не являются в ней выводимыми ввиду того, что эти утверждения в их выводе ссылаются на себя самих

Размещено на http://www.allbest.ru/

Пусть С - высказывание о непротиворечивости теории, т. е. в С утверждается, что все утверждения теории Т таковы, что в этой теории не выводимы и их отрицания. И пусть Т непротиворечива, т. е. высказывание С выполнимо на всех высказываниях этой теории (важным для использования семантики самоссылочных высказываний является допущение того, что это высказывание уже истинно), т. е. семантически C выводимо из множества всех высказываний теории, в том числе и из себя самого (раз отрицает собственное отрицание при наличии непротиворечивости),

{Ai, …, Вj, …, С} |= С, (2)

C L, что противоречит условиям предикативности системы Т (C L). Следовательно, теорема 1 о том, что в предикативной теории не доказуема ее непротиворечивость, доказана. ?

Пусть F - высказывание о полноте системы; F утверждает, что в системе Т выводимы все утверждения, в том числе и само F, но тогда F, если оно верно, семантически (самоссылочно) тем самым высказывается о себе самом:

{Ai, …, Вj, …, F} |= F, (3)

F L, что противоречит условиям допущения чисто предикативности теории Т (F L). Доказана теорема 2. ?

Однако предположение о непредикативности теории Т являлось лишь начальным условием рассуждений, и в связи с доказанными теоремами 1, 2 допускается и иная интепретация результата - непротиворечивость теории не доказуема в предикативных системах, т. е. доказательства непротиворечивости возможны только с допущением непредикативности (самоссылочности) в семантике рассуждений, как, например в теории множеств с самопринадлежностью [3]. Тем самым доказана теорема.

Теорема 3 (о предикативных системах). Непротиворечивость и полнота предикативной теории не доказуемы средствами самой этой теории.

Таким образом, без применения диагонального метода передоказаны теоремы Гёделя. Поскольку в этих теоремах (1-3) не упоминался совершенно тип логики, посредством которого осуществляется вывод в теории Т, то эти теоремы действенны на множестве предикативных теорий с произвольными правилами вывода (в т. ч. на использующих многозначную, модальную и т. п. логики).

Следующие утверждения, рассматриваемые без использования диагонального метода, связаны с отношением счетности и несчетности множеств.

3. Несчетность точек на прямой

При описании упорядоченных структур в теории множеств с самопринадлежностью в работе [4] было показано, что объекты, определяющие структуру прямой, самоподобны, т.е. обладают свойством структурной изоморфности объекта его собственному подобъекту.

Определение 1. Два объекта структурно изоморфны, если они изоморфны и совпадают по структуре, т. е. А В, если А В (изоморфизм : AB) и если для любых а 1, a2 A, (а 1)=b1, (a2)=b2, b1, b2 B, имеет место (а 1 a2) (b1 b2).

Определение 2. Внутренность объекта А содержит объекты, принадлежащие объекту А, за исключением самого объекта А;

V(А)={[х]М |([х] или ([x]А и АV(А))}.

Определение 3. Объект А собственно внутренний по отношению к объекту В, если он принадлежит В, но не принадлежит ряду внутренностей объекта В.

Определение 4. Объект самоподобен, если он структурно изоморфен подобъекту, собственно внутреннему по отношению к этому же объекту.

Для самоподобных объектов C и D одной прямой, D С, или С D, или D = С, причем в любом случает имеет место структурный изоморфизм D C. Для объектов натурального ряда (натуральных чисел) свойство структурной изоморфности, очевидно, не выполняется, одни натуральные числа другим неизоморфны. Следовательно, самоподобные объекты несчетны.

Теорема 4. Количество точек на прямой несчетно.

Точкам на прямой соответствует максимальный упорядочиваемый отношением принадлежности объект - нить недостижимых последователей, являющаяся самоподобной (см. [4], [5]).

4. Счетность количества обозначений

Очевидно также, что, располагая конечным алфавитом, можно иметь не более чем счётное количество обозначений (конечной длины). Множество подмножеств конечного множества конечно. Счетное повторение этой операции для начального конечного множества дает счетное множество.

Даже в случае, если имеется счетный алфавит, но сами обозначения содержат конечное число символов, итоговое количество обозначений счетно (ввиду счетности множества конечных подмножеств счетного множества).

Таким образом, следует различать точки на прямой (как показано выше, их несчетное количество) и их десятичные обозначения, которых, по означенным выше соображениям, счетное количество. Остается построить пересчет этих обозначений, не используя диагональный метод.

5. Счетность простых деревьев

Представления чисел на отрезке [0, 1) в n-ичной системе счисления (c m разрядами) изоморфны n-дереву (глубины m), что очевидно. На рис. 1а выделенная линия соответствует двоичному обозначению числа 0,011…, на рис. 1б - десятичному обозначению 0,089…. (номер слоя соответствует порядковому номеру цифры за запятой).

Пересчет n-дерева организуется следующим образом: при обходе считается 1-й слой, затем - 2-й, затем - 3-й и т. д. В m_дереве для всякой вершины r-го слоя ее номер не более чем nr. Для всех n и r из N nr < N, из чего следует счетность количества вершин дерева (и счетность его ветвей, имеющих начало в 0-м слое), а значит, и счетность количества n_ичных обозначений чисел на отрезке [0, 1).

Таким образом, несчетность множества точек на прямой и счетность количества n_ичных обозначений чисел на отрезке [0, 1) согласуются друг с другом. Доказана теорема. теорема нечетность гёдель

Теорема 5 (о счетности обозначений). Количество k-ичных (kN) обозначений чисел на отрезке [0, 1) отличается от количества точек на прямой на этом отрезке (несчетного) и является счетным.

Из этой теоремы следует естественный вывод, что не все изучаемые множества можно обозначить (на все изучаемые объекты обозначений не хватит, поскольку этих объектов мысли гораздо больше, чем счетное количество обозначений). Такое истолкование теоремы согласуется с интуитивными представлениями и поэтому является естественным.

Заключение

Как показано выше, классические утверждения (теоремы Гёделя, утверждения о несчетности числа точек на прямой) доказуемы без диагональных рассуждений, в семантике самопринадлежности.

Счетность же количества обозначений, счётность количества n_ичных обозначений чисел на отрезке [0, 1), не противоречит тому, что объектов мысли (точек на прямой) несчетное число, - не все из существующего (мыслимого) можно обозначить.

Список литературы

1. Зенкин А.А. Принцип разделения времени и анализ одного класса квазифинитных правдоподобных рассуждений (на примере теоремы Г. Кантора о несчетности) // Доклады Академии наук. 1997. Т.356, №6. С.733-735.

2. Френкель А., Бар-Хиллел И. Основания теории множеств / пер. с англ.; под. ред. А.С. Есенина-Вольпина. М.: Мир, 1966. 366 с.

3. Чечулин В.Л. О множествах с самопринадлежностью // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2005. Вып. 2(2). С.133-138.

4. Чечулин В.Л. Об упорядоченных множествах с самопринадлежностью // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2008. Вып. 4(20). С.37-45.

5. Чечулин В.Л. О свободе теории множеств с самопринадлежностью от известных парадоксов наивной теории множеств // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2010. Вып. 1 (1). С. 29-31.

Размещено на Allbest.ru