Парадокс Рассела в теории множеств

Введение

Парадокс в теории множеств

В математической логике парадокс Рассела (также известный как антиномия Рассела) — это парадокс теории множеств, опубликованный британским философом и математиком Бертраном Расселом в 1901 году. Парадокс Рассела показывает, что любая теория множеств, содержащая неограниченный принцип общности, приводит к противоречиям. Парадокс был независимо открыт ещё в 1899 году немецким математиком Эрнстом Цермело. Однако Цермело не опубликовал эту идею, которая оставалась известной лишь Дэвиду Гильберту, Эдмунду Гуссерлю и другим учёным Геттингенского университета. В конце 1890-х годов Георг Кантор, считающийся основателем современной теории множеств, уже осознал, что его теория приведёт к противоречию, о чём сообщил Гильберту и Рихарду Дедекинду в письме. Согласно принципу неограниченной общности, для любого достаточно чётко определённого свойства существует множество, состоящее только из тех объектов, которые обладают этим свойством. Пусть R — множество всех множеств, которые не являются элементами самих себя. (Это множество иногда называют «множеством Рассела».) Если R не является элементом самого себя, то по определению оно должно быть элементом самого себя; однако, если оно является элементом самого себя, то оно не является элементом самого себя, поскольку это множество всех множеств, которые не являются элементами самих себя. Полученное противоречие и есть парадокс Рассела. В символах:

Рассел также показал, что версию парадокса можно вывести в аксиоматической системе, построенной немецким философом и математиком Готлобом Фреге, тем самым подорвав попытку Фреге свести математику к логике и поставив под сомнение логицистскую программу. Два влиятельных способа избежать парадокса были предложены в 1908 году: теория типов Рассела и теория множеств Цермело. В частности, аксиомы Цермело ограничивали принцип неограниченной общности. С дополнительными вкладами Абрахама Френкеля теория множеств Цермело развилась в ныне стандартную теорию множеств Цермело — Френкеля (обычно известную как ZFC, включая аксиому выбора). Основное различие между решением парадокса Расселом и Цермело заключается в том, что Цермело модифицировал аксиомы теории множеств, сохраняя при этом стандартный логический язык, в то время как Рассел модифицировал сам логический язык. Язык ZFC, с помощью Торальфа Сколема, оказался языком логики первого порядка.

Неофициальное представление

Большинство множеств, с которыми обычно приходится сталкиваться, не являются элементами самих себя. Будем называть множество "нормальным", если оно не является элементом самого себя, и "аномальным", если оно является элементом самого себя. Очевидно, каждое множество должно быть либо нормальным, либо аномальным. Например, рассмотрим множество всех квадратов на плоскости. Это множество само по себе не является квадратом на плоскости, следовательно, оно не является элементом самого себя и, таким образом, является нормальным. В отличие от этого, дополнительное множество, содержащее всё, что не является квадратом на плоскости, само по себе не является квадратом на плоскости, и поэтому является одним из своих собственных элементов, то есть аномальным. Теперь рассмотрим множество всех нормальных множеств, R, и попытаемся определить, является ли R нормальным или аномальным. Если R нормальное, то оно будет содержаться в множестве всех нормальных множеств (в самом себе), и, следовательно, будет аномальным; с другой стороны, если R аномальное, то оно не будет содержаться в множестве всех нормальных множеств (в самом себе), и, следовательно, будет нормальным. Это приводит к выводу, что R не является ни нормальным, ни аномальным: парадокс Рассела.

Теоретические ответы множеств

Согласно принципу взрыва классической логики, из противоречия можно доказать любое утверждение. Поэтому наличие противоречий, таких как парадокс Рассела в аксиоматической теории множеств, является катастрофическим, поскольку если любая формула может быть доказана как истинная, это разрушает общепринятое значение истинности и ложности. Более того, поскольку теория множеств рассматривалась как основа для аксиоматического построения всех других разделов математики, парадокс Рассела угрожал основаниям математики в целом. Это стимулировало значительные исследования на рубеже XX века, направленные на разработку непротиворечивой (свободной от противоречий) теории множеств. В 1908 году Эрнст Зермело предложил аксиоматизацию теории множеств, которая избегала парадоксов наивной теории множеств, заменяя произвольное выделение множеств более слабыми аксиомами существования, такими как его аксиома выделения (Aussonderung). (Избежание парадокса не было первоначальной целью Зермело, а скорее документированием предположений, которые он использовал при доказательстве теоремы о хорошем упорядочении.) Модификации этой аксиоматической теории, предложенные в 1920-х годах Абрахамом Френкелем, Торальфом Сколемом и самим Зермело, привели к аксиоматической теории множеств, известной как ZFC. Эта теория получила широкое признание после того, как аксиома выбора Зермело перестала быть спорной, и ZFC остаётся канонической аксиоматической теорией множеств по сей день. ZFC не постулирует, что для каждого свойства существует множество всех объектов, обладающих этим свойством. Вместо этого она утверждает, что для любого множества X существует любое подмножество X, определяемое с помощью логики первого порядка. Объект R, определённый парадоксом Рассела выше, не может быть сконструирован как подмножество любого множества X и, следовательно, не является множеством в ZFC. В некоторых расширениях ZFC, особенно в теории множеств фон Неймана — Бернайса — Гёделя, объекты, подобные R, называются собственными классами. ZFC не содержит положений о типах, хотя кумулятивная иерархия имеет понятие слоёв, напоминающих типы. Сам Зермело никогда не принимал формулировку ZFC, предложенную Сколемом, использующую язык логики первого порядка. Как отмечает Жозе Феррейрос, Зермело настаивал на том, что "функциональные выражения (условия или предикаты), используемые для выделения подмножеств, а также функции замены, могут быть "полностью произвольными [ganz beliebig]"; современная интерпретация этого утверждения заключается в том, что Зермело хотел включить квантификацию высшего порядка, чтобы избежать парадокса Сколема. Около 1930 года Зермело также ввёл (очевидно, независимо от фон Неймана) аксиому основания, тем самым, как отмечает Феррейрос, "запрещая "циклические" и "необоснованные" множества, [ZFC] включила одну из важнейших мотиваций ТТ [теории типов] — принцип типов аргументов". Этот ZFC второго порядка, предпочтительный для Зермело, включая аксиому основания, позволил создать богатую кумулятивную иерархию. Феррейрос пишет, что "слои" Зермело по существу идентичны типам в современных версиях простой ТТ [теории типов], предложенных Гёделем и Тарским. Кумулятивную иерархию, в которой Зермело развивал свои модели, можно описать как вселенную кумулятивной ТТ, в которой разрешены трансфинитные типы. (Как только мы приняли импредикативную точку зрения, отказавшись от идеи, что классы конструируются, не является неестественным принять трансфинитные типы.) Таким образом, простую ТТ и ZFC теперь можно рассматривать как системы, которые "говорят" по существу об одних и тех же предполагаемых объектах. Основное различие заключается в том, что ТТ опирается на сильную логику высшего порядка, в то время как Зермело использовал логику второго порядка, а ZFC также может быть представлена в форме логики первого порядка. "Описание" первого порядка кумулятивной иерархии гораздо слабее, как показывает существование счётных моделей (парадокс Сколема), но оно обладает некоторыми важными преимуществами". В ZFC, заданном множестве A, можно определить множество B, состоящее ровно из тех множеств в A, которые не являются самими собой членами. B не может быть в A по той же логике, что и в парадоксе Рассела. Эта вариация парадокса Рассела показывает, что ни одно множество не содержит всего. Благодаря работам Зермело и других, особенно Джона фон Неймана, структура того, что некоторые считают "естественными" объектами, описываемыми ZFC, в конечном итоге стала ясной: это элементы вселенной фон Неймана V, построенной из пустого множества путём трансфинитной итерации операции взятия степени множества. Таким образом, теперь снова можно рассуждать о множествах неаксиоматическим образом, не сталкиваясь с парадоксом Рассела, а именно, рассуждая об элементах V. То, уместно ли рассматривать множества таким образом, является предметом споров среди различных точек зрения на философию математики. Другие решения парадокса Рассела, со стратегией, более близкой к стратегии теории типов, включают "Новые основания" Куайна и теорию множеств Скотта — Поттера. Ещё один подход — определить множественное отношение принадлежности с соответствующим образом модифицированной схемой выделения, как в теории множеств двойного расширения.

From the principle of explosion of classical logic, any proposition can be proved from a contradiction. Therefore, the presence of contradictions like Russell's paradox in an axiomatic set theory is disastrous; since if any formula can be proved true it destroys the conventional meaning of truth and falsity. Further, since set theory was seen as the basis for an axiomatic development of all other branches of mathematics, Russell's paradox threatened the foundations of mathematics as a whole. This motivated a great deal of research around the turn of the 20th century to develop a consistent (contradiction free) set theory. In 1908, Ernst Zermelo proposed an axiomatization of set theory that avoided the paradoxes of naive set theory by replacing arbitrary set comprehension with weaker existence axioms, such as his axiom of separation (Aussonderung). (Avoiding paradox was not Zermelo's original intention, but instead to document which assumptions he used in proving the well ordering theorem.) Modifications to this axiomatic theory proposed in the 1920s by Abraham Fraenkel, Thoralf Skolem, and by Zermelo himself resulted in the axiomatic set theory called ZFC. This theory became widely accepted once Zermelo's axiom of choice ceased to be controversial, and ZFC has remained the canonical axiomatic set theory down to the present day. ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it asserts that given any set X, any subset of X definable using first order logic exists. The object R defined by Russell's paradox above cannot be constructed as a subset of any set X, and is therefore not a set in ZFC. In some extensions of ZFC, notably in von Neumann–Bernays–Gödel set theory, objects like R are called proper classes. ZFC is silent about types, although the cumulative hierarchy has a notion of layers that resemble types. Zermelo himself never accepted Skolem's formulation of ZFC using the language of first order logic. As José Ferreirós notes, Zermelo insisted instead that "propositional functions (conditions or predicates) used for separating off subsets, as well as the replacement functions, can be 'entirely arbitrary [ganz beliebig]"; the modern interpretation given to this statement is that Zermelo wanted to include higher order quantification in order to avoid Skolem's paradox. Around 1930, Zermelo also introduced (apparently independently of von Neumann), the axiom of foundation, thus—as Ferreirós observes—"by forbidding 'circular' and 'ungrounded' sets, it [ZFC] incorporated one of the crucial motivations of TT [type theory]—the principle of the types of arguments". This 2nd order ZFC preferred by Zermelo, including axiom of foundation, allowed a rich cumulative hierarchy. Ferreirós writes that "Zermelo's 'layers' are essentially the same as the types in the contemporary versions of simple TT [type theory] offered by Gödel and Tarski. One can describe the cumulative hierarchy into which Zermelo developed his models as the universe of a cumulative TT in which transfinite types are allowed. (Once we have adopted an impredicative standpoint, abandoning the idea that classes are constructed, it is not unnatural to accept transfinite types.) Thus, simple TT and ZFC could now be regarded as systems that 'talk' essentially about the same intended objects. The main difference is that TT relies on a strong higher order logic, while Zermelo employed second order logic, and ZFC can also be given a first order formulation. The first order 'description' of the cumulative hierarchy is much weaker, as is shown by the existence of countable models (Skolem's paradox), but it enjoys some important advantages." In ZFC, given a set A, it is possible to define a set B that consists of exactly the sets in A that are not members of themselves. B cannot be in A by the same reasoning in Russell's Paradox. This variation of Russell's paradox shows that no set contains everything. Through the work of Zermelo and others, especially John von Neumann, the structure of what some see as the "natural" objects described by ZFC eventually became clear: they are the elements of the von Neumann universe, V, built up from the empty set by transfinitely iterating the power set operation. It is thus now possible again to reason about sets in a non axiomatic fashion without running afoul of Russell's paradox, namely by reasoning about the elements of V. Whether it is appropriate to think of sets in this way is a point of contention among the rival points of view on the philosophy of mathematics. Other solutions to Russell's paradox, with an underlying strategy closer to that of type theory, include Quine's New Foundations and Scott–Potter set theory. Yet another approach is to define multiple membership relation with appropriately modified comprehension scheme, as in the Double extension set theory.