О понятиях множества и класса
“Eine Menge ist eine Zusammenfassung bestimmter wohlunterschiedener Objekte unserer Anschauung
oder unseres Denkens - welche die Elemente der Menge genannt werden - zu einem Ganzen.”
- Georg Cantor, «Grundlagen einer allgemeinen Mannigfaltigkeitslehre»
(“Множество это собрание воедино определённых различимых объектов нашего представления или нашего мышления, называемых элементами множества.”)
§ О слове множество.
Когда говоришь про теории множеств, многие думают что там слово “множество” используется в обыденном смысле, как “множество всех молекул, из которых состоит стул”, но на самом деле речь совершенно не об этом.
Создатель теории множеств (не какой-то конкретной аксиоматической теории, а теории множеств как области математики) Георг Кантор в общем действительно просто изучал свойства совокупностей идеализированных объектов - в первую очередь чисел (натуральных или вещественных) и списков, функций или собственно других множеств. Он, правда, в явном виде исключал “связанные с пространством или временем объекты и свойства”, так что молекулы в любом случае не подойдут. Какой-то фиксированной чётко аксиоматизированной теории Кантор не создал, и это было в порядке вещей в те времена.
Однако теория множеств, вошедшая в математику на столетие в качестве ассемблера, на который транслируют определения, построения и доказательства, это вполне конкретная теория множеств ZF(C) и её близкородственные вариации, называемые membership-based pure set theories. И они вообще говоря совершенно не о том, чтобы описать язык и поведение совокупностей объектов. Это о расширении логики первого порядка принципом рефлексии.
Давайте сперва о том, что такое логика первого порядка. Логика нулевого порядка (“пропозициональная логика”) задаётся для какого-то стартового набора атомарных утверждений {A, B, C}. Из атомарных утверждений формируются составные утверждения A ∧ B (“А и Б оба верны”), A ∨ B (“A или B верно”), A ⇒ B (“из верности A следует верность B”), ¬A (“A не верно”), и задаётся набор правил вывода, которые позволяют из одних составных утверждений выводить другие.
В логике первого порядка кроме утверждений появляются утверждения с параметрами типа “t пустой”. Из них также можно делать составные утверждения, плюс добавляются два оператора, превращающие утверждение с параметром в утверждение без параметра (ну или утверждение с несколькими параметрами в утверждение, в котором параметров на один меньше) - это операторы (∀t)At (“для всех t верно A(t)”) и (∃t)A t (“существует такой t, для которого выполняется A(t)”). Соответственно добавляются и правила вывода, касающиеся нововедённых операторов.
В терминах логики первого порядка удобно описывать всякие теории вроде теории групп. Мы задаём быстренько набор атомарных утверждений, потом описываем аксиомы (какой-то набор составных утверждений, описывающих setup теории) и при помощи правил вывода выводим из них всякие другие утверждения.
Очень заманчиво расширить рамки логики первого порядка, чтобы была возможность рассуждать о самих утверждениях. Это реализуется через принцип рефлексии - мы постулируем, чтобы для каждого утверждения-с-параметром At у нас возникла его “внутренняя реализация” {t | A(t)}. То есть мы добавляем в логику первого порядка атомарное утверждение (с двумя параметрами) t ∈ X, и набор аксиом, которые позволяют для любого утверждения-с-параметром At доказать, что (∃X)(∀t) A(t) ⇔ t ∈ X.
К сожалению, без некоторых модификаций логика первого порядка с рефлексией противоречива - про любое утверждение становится возможным доказать, что оно одновременно истинно и ложно. А версии логики первого порядка с рефлексией, где рефлексия немного ограничена, чтобы исключить противоречия - это как раз и есть наши membership-based pure set theories. Множества в них суть внутренние реализации утверждений-с-параметром, а атомарное отношение t ∈ X читается как “t является элементом X”.
Важно отметить, что кроме аксиом, позволяющих доказать (∃X)(∀t) A(t) ⇔ t ∈ X для всякого At в таких теориях множеств не допускается никаких аксиом, позволяющих доказать существование чего бы то ни было. Таким образом все “t”, существование которых мы можем доказать - множества. То есть множества могут состоять только из других множеств, никаких тебе “посторонних элементов” вроде молекул или там букв. Кроме того, в таких теориях нельзя построить множества, содержащие сами себя прямо или опосредованно - не может быть бесконечной последовательности множеств A ∈ B ∈ ··· ∈ Z. Таким образом все множества так это на самом деле просто деревья конечной глубины, все листья которых - пустое множество. Но вот порядок ветвления у таких деревьев совершенно не обязан быть конечным.
§ О слове класс.
Кантор знал о противоречивости неограниченного принципа рефлексии (он, правда, не называл это принципом рефлексии). Принцип рефлексии позволяет для любого множества X сформировать множество всех его подмножеств P(X), и Кантор доказал (используя схему преобразования - тоже частный случай неограниченного принципа рефлексии), что это множество строго больше исходного множества X. С другой стороны, принцип рефлексии позволяет образовать “множество всех множеств” V. Но P(V) тогда должно быть равно V, а по Кантор доказал, что строго больше. В «Grundlagen einer allgemeinen Mannigfaltigkeitslehre» Кантор уже весьма явно говорит о том, что бывают множества X, для которых можно в частности применять схему преобразований, а бывают классы (“Gesamtheiten”) множеств, такие как класс всех множеств V или множество всех ординалов Ord, и эти классы не являются множествами, т.к. (а) не вполне соответствуют определению, которое требует, чтобы объекты множества были определёнными и различимыми, (б) в определённом смысле “слишком велики”. Собственно то что элементы этих классов не являются по Кантору “определёнными” вытекает ровно из того, что классы “слишком большие”, чтобы можно было определить их элементы не скатываясь в замкнутый круг. Все эти рассуждения у Кантора довольно расплывчаты, и в конечном итоге остаётся непонятно, эквивалентны ли (а) и (б), и если нет, то какое соображение первично.
Через много лет после смерти Кантора будут сформулированы как теория множеств (и классов), базирующаяся на доктрине ограничения размера (фон Неймана-Гёделя-Бернайса), так и теория множеств Аккермана, базирующаяся на нециркулярности определений.
В обоих случаях, принцип рефлексии разбивается на две ступени.
1) Постулируется существование внутренней реализации (“класса”) для любого утверждения-с-параметром At, если из At следует что t множество (t ∈ V) - это называется вариант Аккермана. Можно постулировать существование внутренней реализации для любого утверждения-с-параметром At, если там внутри все связанные кванторами переменные (кванторы это операторы ∃ и ∀) множествозначные - это называется вариант фон Неймана.
В случае варианта Аккермана, чтобы сформировать класс, нам нужно доказать дополнительное свойство для утверждения-с-параметром, в другом случае (вариант фон-Неймана) проинспектировать его “грамматически” и убедиться, что оно имеет вот такую специальную форму. В обоих случаях мы успешно справляемся с тем, чтобы сохранить возможность определить классы такие как V и Ord, и одновременно недопустить применимость к ним схемы преобразования (которая, будь она доступна, немедленно позволила бы в присутствии пустого множества изготовить из V парадокс Рассела - “множество всех множеств, не содержащих себя”).
Эта ступень “принципа рефлексии” называется схемой образования классов. Но коль скоро классы можно формировать только из множеств, у нас очень связаны руки. Мы мало что можем сделать дальше с классом, пока у нас нет инструмента доказательства, что класс является множеством. Именно для этого нам нужен второй шаг. В варианте Аккермана для этого надо дополнительно “грамматически” проинспектировать утверждение At в определении класса - если в там не встречается константа V, то получившийся класс - множество. В варианте фон Неймана постулируется что любой класс либо равномощен V, либо его элемент. Соответственно, чтобы доказать, что класс является множеством, нужно вывести из его определения, что из него нет сюрьективного отображение в V.
При использовании любого из этих подходов получается элегантная теория множеств, причём одна и та же. То, что её традиционно используют в качестве “ассемблера математики” связано не с тем, что у выражать всё на свете через множества чем-то удобнее чем, например, через функции, а просто с тем, что это логика первого порядка с “насколько это возможно без противоречия“ рефлексией предикатов.
oder unseres Denkens - welche die Elemente der Menge genannt werden - zu einem Ganzen.”
- Georg Cantor, «Grundlagen einer allgemeinen Mannigfaltigkeitslehre»
(“Множество это собрание воедино определённых различимых объектов нашего представления или нашего мышления, называемых элементами множества.”)
§ О слове множество.
Когда говоришь про теории множеств, многие думают что там слово “множество” используется в обыденном смысле, как “множество всех молекул, из которых состоит стул”, но на самом деле речь совершенно не об этом.
Создатель теории множеств (не какой-то конкретной аксиоматической теории, а теории множеств как области математики) Георг Кантор в общем действительно просто изучал свойства совокупностей идеализированных объектов - в первую очередь чисел (натуральных или вещественных) и списков, функций или собственно других множеств. Он, правда, в явном виде исключал “связанные с пространством или временем объекты и свойства”, так что молекулы в любом случае не подойдут. Какой-то фиксированной чётко аксиоматизированной теории Кантор не создал, и это было в порядке вещей в те времена.
Однако теория множеств, вошедшая в математику на столетие в качестве ассемблера, на который транслируют определения, построения и доказательства, это вполне конкретная теория множеств ZF(C) и её близкородственные вариации, называемые membership-based pure set theories. И они вообще говоря совершенно не о том, чтобы описать язык и поведение совокупностей объектов. Это о расширении логики первого порядка принципом рефлексии.
Давайте сперва о том, что такое логика первого порядка. Логика нулевого порядка (“пропозициональная логика”) задаётся для какого-то стартового набора атомарных утверждений {A, B, C}. Из атомарных утверждений формируются составные утверждения A ∧ B (“А и Б оба верны”), A ∨ B (“A или B верно”), A ⇒ B (“из верности A следует верность B”), ¬A (“A не верно”), и задаётся набор правил вывода, которые позволяют из одних составных утверждений выводить другие.
В логике первого порядка кроме утверждений появляются утверждения с параметрами типа “t пустой”. Из них также можно делать составные утверждения, плюс добавляются два оператора, превращающие утверждение с параметром в утверждение без параметра (ну или утверждение с несколькими параметрами в утверждение, в котором параметров на один меньше) - это операторы (∀t)At (“для всех t верно A(t)”) и (∃t)A t (“существует такой t, для которого выполняется A(t)”). Соответственно добавляются и правила вывода, касающиеся нововедённых операторов.
В терминах логики первого порядка удобно описывать всякие теории вроде теории групп. Мы задаём быстренько набор атомарных утверждений, потом описываем аксиомы (какой-то набор составных утверждений, описывающих setup теории) и при помощи правил вывода выводим из них всякие другие утверждения.
Очень заманчиво расширить рамки логики первого порядка, чтобы была возможность рассуждать о самих утверждениях. Это реализуется через принцип рефлексии - мы постулируем, чтобы для каждого утверждения-с-параметром At у нас возникла его “внутренняя реализация” {t | A(t)}. То есть мы добавляем в логику первого порядка атомарное утверждение (с двумя параметрами) t ∈ X, и набор аксиом, которые позволяют для любого утверждения-с-параметром At доказать, что (∃X)(∀t) A(t) ⇔ t ∈ X.
К сожалению, без некоторых модификаций логика первого порядка с рефлексией противоречива - про любое утверждение становится возможным доказать, что оно одновременно истинно и ложно. А версии логики первого порядка с рефлексией, где рефлексия немного ограничена, чтобы исключить противоречия - это как раз и есть наши membership-based pure set theories. Множества в них суть внутренние реализации утверждений-с-параметром, а атомарное отношение t ∈ X читается как “t является элементом X”.
Важно отметить, что кроме аксиом, позволяющих доказать (∃X)(∀t) A(t) ⇔ t ∈ X для всякого At в таких теориях множеств не допускается никаких аксиом, позволяющих доказать существование чего бы то ни было. Таким образом все “t”, существование которых мы можем доказать - множества. То есть множества могут состоять только из других множеств, никаких тебе “посторонних элементов” вроде молекул или там букв. Кроме того, в таких теориях нельзя построить множества, содержащие сами себя прямо или опосредованно - не может быть бесконечной последовательности множеств A ∈ B ∈ ··· ∈ Z. Таким образом все множества так это на самом деле просто деревья конечной глубины, все листья которых - пустое множество. Но вот порядок ветвления у таких деревьев совершенно не обязан быть конечным.
§ О слове класс.
Кантор знал о противоречивости неограниченного принципа рефлексии (он, правда, не называл это принципом рефлексии). Принцип рефлексии позволяет для любого множества X сформировать множество всех его подмножеств P(X), и Кантор доказал (используя схему преобразования - тоже частный случай неограниченного принципа рефлексии), что это множество строго больше исходного множества X. С другой стороны, принцип рефлексии позволяет образовать “множество всех множеств” V. Но P(V) тогда должно быть равно V, а по Кантор доказал, что строго больше. В «Grundlagen einer allgemeinen Mannigfaltigkeitslehre» Кантор уже весьма явно говорит о том, что бывают множества X, для которых можно в частности применять схему преобразований, а бывают классы (“Gesamtheiten”) множеств, такие как класс всех множеств V или множество всех ординалов Ord, и эти классы не являются множествами, т.к. (а) не вполне соответствуют определению, которое требует, чтобы объекты множества были определёнными и различимыми, (б) в определённом смысле “слишком велики”. Собственно то что элементы этих классов не являются по Кантору “определёнными” вытекает ровно из того, что классы “слишком большие”, чтобы можно было определить их элементы не скатываясь в замкнутый круг. Все эти рассуждения у Кантора довольно расплывчаты, и в конечном итоге остаётся непонятно, эквивалентны ли (а) и (б), и если нет, то какое соображение первично.
Через много лет после смерти Кантора будут сформулированы как теория множеств (и классов), базирующаяся на доктрине ограничения размера (фон Неймана-Гёделя-Бернайса), так и теория множеств Аккермана, базирующаяся на нециркулярности определений.
В обоих случаях, принцип рефлексии разбивается на две ступени.
1) Постулируется существование внутренней реализации (“класса”) для любого утверждения-с-параметром At, если из At следует что t множество (t ∈ V) - это называется вариант Аккермана. Можно постулировать существование внутренней реализации для любого утверждения-с-параметром At, если там внутри все связанные кванторами переменные (кванторы это операторы ∃ и ∀) множествозначные - это называется вариант фон Неймана.
В случае варианта Аккермана, чтобы сформировать класс, нам нужно доказать дополнительное свойство для утверждения-с-параметром, в другом случае (вариант фон-Неймана) проинспектировать его “грамматически” и убедиться, что оно имеет вот такую специальную форму. В обоих случаях мы успешно справляемся с тем, чтобы сохранить возможность определить классы такие как V и Ord, и одновременно недопустить применимость к ним схемы преобразования (которая, будь она доступна, немедленно позволила бы в присутствии пустого множества изготовить из V парадокс Рассела - “множество всех множеств, не содержащих себя”).
Эта ступень “принципа рефлексии” называется схемой образования классов. Но коль скоро классы можно формировать только из множеств, у нас очень связаны руки. Мы мало что можем сделать дальше с классом, пока у нас нет инструмента доказательства, что класс является множеством. Именно для этого нам нужен второй шаг. В варианте Аккермана для этого надо дополнительно “грамматически” проинспектировать утверждение At в определении класса - если в там не встречается константа V, то получившийся класс - множество. В варианте фон Неймана постулируется что любой класс либо равномощен V, либо его элемент. Соответственно, чтобы доказать, что класс является множеством, нужно вывести из его определения, что из него нет сюрьективного отображение в V.
При использовании любого из этих подходов получается элегантная теория множеств, причём одна и та же. То, что её традиционно используют в качестве “ассемблера математики” связано не с тем, что у выражать всё на свете через множества чем-то удобнее чем, например, через функции, а просто с тем, что это логика первого порядка с “насколько это возможно без противоречия“ рефлексией предикатов.