Что может являться источником информации. Невозобновляемые ресурсы: проблема рационального использования
АКСИОМАТИЧЕСКАЯ ТЕОРИЯ МНОЖЕСТВ направление в математической логике, занимающееся изучением аксиоматическим методом объектов теории множеств.
Под аксиоматической теорией множеств также понимается любая конкретная система, формализующая теорию множеств. Аксиоматическая теория множеств возникла в начале 20 века в Европе в связи с парадоксами теории множеств, показавшими, что наивная теория множеств приводит к противоречиям. Устранение парадоксов оказалось возможным только на пути аксиоматического ограничения принципа, состоящего в том, что всякое свойство определяет множество всех объектов, обладающих этим свойством. Различные ограничения приводят к различным вариантам аксиоматической теории множеств.
Первая и наиболее известная из аксиоматических теорий множеств — теория Цермело—Френкеля, определяющая построение множеств шаг за шагом, т. е. на каждом конечном или трансфинитном шаге рассматриваются только те множества, все элементы которых уже построены на предшествующих шагах. Понятие трансфинитного шага также находит в этой теории строгое определение. Эта теория формулируется в Є-языке, то есть в языке с единственным исходным неопределяемым символом Є принадлежности: хЄХ понимается как «х есть элемент множества Х». Множество Y называется подмножеством множества Х, если каждый элемент множества Υ принадлежит и множеству Х (обозначается YЄХ).
Ключевыми в теории Цермело-Френкеля (теории ZF) являются следующие аксиомы.
1) Аксиома экстенсиональности (объёмности), утверждающая, что любые два множества, содержащие одни и те же элементы, равны друг другу.
2) Аксиома выделения, утверждающая, что совокупность всех элементов данного множества, удовлетворяющих определённому свойству, является множеством.
3) Аксиома бесконечности, утверждающая существование бесконечного множества определённого вида, именно, непустого множества Х такого, что хЄХ=>{х}ЄХ, где {х} - множество, единственным элементом которого является х.
4) Аксиома степени, утверждающая, что совокупность Р(Х) всех подмножеств данного множества является множеством.
5) Аксиома подстановки, утверждающая, что если для каждого элемента х данного множества Х каким-то образом задано множество f(х), то совокупность {f(х):хЄХ} всех так определённых множеств f(х) является множеством.
6) Аксиома регулярности, утверждающая, что каждое непустое множество Х содержит Є-минимальный элемент х, т. е. х не содержит элементов множества Х.
К этой системе может присоединяться аксиома выбора АС, утверждающая, что для любого множества Х, состоящего из непустых попарно не имеющих общих элементов множеств х, существует множество Υ, имеющее ровно один общий элемент с каждым хЄХ. Расширенная таким образом система обозначается ZFC.
Аксиомы 1-4 и аксиома выбора были введены Э. Цермело в 1908 году; вместе с некоторыми аксиомами технического характера они образуют аксиоматическую теорию множеств Цермело Z или ZC (соответственно, в отсутствии или присутствии аксиомы выбора). Аксиома 5 была введена А. Френкелем и норвежским математиком Т. Сколемом в 1922 году, аксиома 6 - Дж. фон Нейманом в 1923.
К теориям Z и ZF примыкают теория типов, соответствующая первым ω + ω шагам описанной выше схемы трансфинитного построения множеств, где ω первое трансфинитное число (равное порядковому типу множества всех натуральных чисел), и теория классов фон Неймана - Бернайса - Гёделя NBG, в которой вместе с множествами разрешается рассматривать и классы, т. е. совокупности множеств, которые сами не являются множествами (например, класс всех множеств); формально классы отличаются от множеств тем, что они не являются элементами других классов (и множеств). На совершенно иной идее построена аксиоматическая теория множеств Куайна NF, в которой требуется, чтобы все переменные формулы, выражающей рассматриваемое свойство, могли быть индексированы так, что индекс у был ровно на единицу больше индекса х всякий раз, когда выражение хЄу встречается в этой формуле.
Развитие аксиоматической теории множеств показало, что объекты содержательной математики могут рассматриваться как множества, соответственно каждое утверждение содержательной математики может быть сформулировано как утверждение о множествах, и, наконец, каждое математически корректное доказательство может быть формализовано как доказательство в теории ZFC (в большинстве случаев достаточной является теория ZC). В этом смысле аксиоматическая теория множеств ZFC является аксиоматическим базисом современной математики.
Аксиоматическая теория множеств позволила доказать формальную неразрешимость, т. е. невозможность получить ответ «да» или «нет» на поставленный вопрос, для таких проблем, как проблема континуума, проблема измеримости и ряд других проблем в дескриптивной теории множеств.
Лит.: Гедель К. Совместимость аксиомы выбора и обобщенной континуум-гипотезы с аксиомами теории множеств // Успехи математических наук. 1948. Т. 3. Вып. 1; Новиков П. С. О непротиворечивости некоторых положений дескриптивной теории множеств // Труды математического института Академии Наук СССР. 1951. Т. 38; Quine W. О. van. Set theory and its logic. Camb., 1963; Френкель А. А., БарХиллел И. Основания теории множеств. М., 1966; Коэн П. Дж. Теория множеств и континуум-гипотеза. М., 1969; Справочная книга по математической логике. М., 1982. Ч. 2: Теория множеств.
К началу ХХ века стройное здание теории множеств стало давать трещины. Привычные рассуждения перестали казаться безупречными ввиду обнаружившихся противоречий – антиномий теории множеств. Это привело к пересмотру основных концепций теории – содержания самого понятия множества, принципов формирования множеств и т.д. Попытки разрешить противоречия стимулировали развитие аксиоматической теории множеств. Приведём примеры теоретико-множественных антиномий.
Антиномия Рассела
.
Если– некоторое множество, то, как правило,
т.е.не содержит себя в качестве элемента.
Однако если, скажем,– множество всех множеств, то
Обозначим черезсовокупность всех таких множеств
что
Содержит ли множествосебя в качестве элемента? Если
то для множестваусловие
не соблюдается; значит,
Если же
тоудовлетворяет условию
значит,
Итак, оба предположения,
и
приводят к противоречию.
В качестве одного
из путей разрешения этого парадокса
было предложено не считать способ
формирования множества
корректным. Такая точка зрения серьёзно
отличалась от представлений “наивной”
теории множеств, где считалось, что
всякое чётко определённое правило
позволяет сформировать множество.
Вопрос о том, какие правила следует
считать чётко определёнными, а какие
нет, является трудным и не имеет к
настоящему времени удовлетворительного
ответа. Кроме того, следует, по-видимому,
запретить множества
удовлетворяющие соотношениям вида
и т.д., а также убывающие цепочки вида
Антиномия “деревенский парикмахер” является вариантом парадокса Рассела. Предположим, что в некоторой деревне поселился парикмахер, который решилбрить всех, кто не бреется сам. Должен ли он брить самого себя? Если да, то значит, он не бреется сам, поэтому он себя не бреет – противоречие. Если нет, то он сам не бреется, поэтому он должен себя брить, и мы опять получаем противоречие.
В этом парадоксе условие “брить всех, кто не бреется сам” является противоречивым, а потому невыполнимым. Природу этой внутренней противоречивости нельзя считать выясненной до конца. Ещё менее ясным кажется ответ на вопрос, какие условия являются противоречивыми, а какие нет.
Антиномия Кантора
.
Пусть
– множество всех множеств, а
– множество всех его подмножеств. Так
как
содержит все множества, то
поэтому
Однако по теореме Кантора
– противоречие.
В отличие от предыдущих антиномий, в которых участвовали лишь самые простейшие понятия теории множеств, в антиномии Кантора присутствуют более сложные понятия: множество всех подмножеств, отображение, взаимно однозначное соответствие. Этого парадокса можно избежать, если запретить использование “множества всех множеств”. В тех аксиоматических системах, где допускается класс всех множеств , теорема Кантора доказывается в более слабой форме.
Примером логического парадокса является парадокс лжеца.
Антиномия Эвбулида (илипарадокс лжеца ). Предположим, что некоторый субъект произносит фразу:“высказывание, которое я сейчас произношу, ложно” . Истинно это высказывание или ложно? Если оно истинно, то субъект сказал правду, а значит, это высказывание ложно. Если же оно ложно, то аналогичные рассуждения показывают, что оно истинно.
Один из путей выхода из создавшегося положения – признать, что не про всякое суждение можно сказать, истинно оно или ложно.
Преодолеть теоретико-множественные антиномии можно созданием строгой аксиоматической теории. Вопрос о непротиворечивости создаваемой аксиоматической теории, за редким исключением, является трудным и достаточно тонким (исключение, например, составляет исчисление высказываний, для которого вопрос о непротиворечивости был решён в предыдущей главе сравнительно просто). До сих пор в аксиоматике теории множеств Цермело – Френкеля, излагаемой ниже, противоречий обнаружено не было. Однако это обстоятельство лишь придаёт нам уверенность в непротиворечивости теории, но не служит доказательством непротиворечивости. Часто непротиворечивость какой-либо теории выводят из непротиворечивости другой теории, вызывающей меньшее сомнение. Например, непротиворечивость геометрии Лобачевского (утверждающей, что через точку вне прямой можно провести более одной прямой, не пересекающей данную) может быть доказана, если принять в качестве факта непротиворечивость евклидовой геометрии. Аналогичным образом из непротиворечивости теории множеств можно вывести непротиворечивость теории действительных чисел.
Современная теория множеств строится на системе аксиом - утверждений, принимаемых без доказательства, - из которых выводятся все теоремы и утверждения теории множеств. Система аксиом является стандартной системой аксиом для теории множеств. К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело - Френкеля с аксиомой выбора.
Значение математической логики в нашем и прошлом столетии сильно возросло. Главной причиной этого явилось открытие парадоксов теории множеств и необходимость пересмотра противоречивой интуитивной теории множеств. Было предложено много различных аксиоматических теорий для обоснования теории множеств, но как бы они не отличались друг от друга своими внешними чертами, общее для всех них содержание составляют те фундаментальные теоремы, на которые в своей повседневной работе опираются математики. Выбор той или иной из имеющихся теорий является в основном делом вкуса; мы же не предъявляем к системе, которой будем пользоваться, никаких требований, кроме того, чтобы она служила достаточной основой для построения современной математики.
Опишем теорию первого порядка NBG, которая в основном является системой того же типа, что и система, предложенная первоначально фон Нейманом (1925), (1928), а затем тщательно пересмотренная и упрощенная Р. Робинсоном (1937), Бернайсом (1937-1954) и Гёделем (1940). (Будем в основном следовать монографии Гёделя, хотя и с некоторыми важными отклонениями.) Теория NBG имеет единственную предикатную букву и не имеет ни одной функциональной буквы или предметной константы. Чтобы быть ближе к обозначениям Бернайса (1937-1954) и Гёделя (1940), мы будем употреблять в качестве переменных вместо x1, x2, … прописные латинские буквы X1, Х2, ... (Как обычно, мы используем буквы X, Y, Z, ... для обозначения произвольных переменных.) Мы введем также сокращенные обозначения ХY для(X, Y) и XY для (X, Y). Содержательно знак понимается как символ отношения принадлежности.
Следующим образом определим равенство:
Определение. Х=Y служит сокращением для формулы.
Таким образом, два объекта равны тогда и только тогда, когда они состоят из одних и тех же элементов.
Определение. служит сокращением для формулы (включение).
Определение. XY служит сокращением для Х Y & X ≠ Y (собственное включение).
Из этих определений легко следует
Предложение 1.
(а) Х = Y (X Y & Y X);
(b) Х = Х;
(с) Х = Y Y = Х;
(d) Х = Y (Y = Z Х = Z);
(е) Х = Y (ZX ZY).
Теперь приступим к перечислению собственных аксиом теории NBG, перемежая формулировки самих аксиом различными следствиями из них и некоторыми дополнительными определениями. Предварительно, однако, отметим, что в той «интерпретации», которая здесь подразумевается, значениями переменных являются классы. Классы - это совокупности, соответствующие некоторым, однако отнюдь не всем, свойствам (те свойства, которые фактически определяют классы, будут частично указаны в аксиомах. Эти аксиомы обеспечивают нам существование необходимых в математике классов и являются, достаточно скромными, чтобы из них нельзя было вывести противоречие). (Эта «интерпретация» столь же неточна, как и понятия «совокупность», «свойство» и т. д.)
Назовем класс множеством, если он является элементом какого-нибудь класса. Класс, не являющийся множеством, назовем собственным классом.
Определение. M(X) служит сокращением для Y(XY) (X есть множество).
Определение. Pr(X) служит сокращением для M(X) (X есть собственный класс).
В дальнейшем увидим, что обычные способы вывода парадоксов приводят теперь уже не к противоречию, а всего лишь к результату, состоящему в том, что некоторые классы не являются множествами. Множества предназначены быть теми надежными, удобными классами, которыми математики пользуются в своей повседневной деятельности; в то время как собственные классы мыслятся как чудовищно необъятные собрания, которые, если позволить им быть множествами (т. е. быть элементами других классов), порождают противоречия.
Система NBG задумана как теория, трактующая о классах, а не о предметах. Мотивом в пользу этого послужило то обстоятельство, что математика не нуждается в объектах, не являющихся классами, вроде коров или молекул. Все математические объекты и отношения могут быть выражены в терминах одних только классов. Если же ради приложений в других науках возникает необходимость привлечения «неклассов», то незначительная модификация системы NBG позволяет применить ее равным образом как к классам, так и к «неклассам» (Мостовский ).
Мы введем строчные латинские буквы x1, x2, … в качестве специальных, ограниченных множествами, переменных. Иными словами, x1 A (x1) будет служить сокращением для X (M(X)A (X)) , что содержательно имеет следующий смысл: «A истинно для всех множества, и x1 A (x1) будет служить сокращением для X (M(X)A (X)), что содержательно имеет смысл: «A истинно для некоторого множества». Заметим, что употребленная в этом определении переменная X должна быть отличной от переменных, входящих в A (x1). (Как и обычно, буквы х, y, z, ... будут употребляться для обозначения произвольных переменных для множеств.)
П р и м е р. Выражение ХхyZA (X, х, y, Z) служит сокращением для
ХXj (М(Xj)Y(M(Y)&ZA (X, Xj, Y, Z))).
Х = Y (XZYZ).
Предложение 2. Система NBG является теорией первого порядка с равенством.
xyzu (u z u = xu = y), т. е. для любых множеств х и у существует множество z такое, что х и у являются единственными его элементами.
х y (у х), т. е. существует множество, не содержащее никаких элементов.
Из аксиомы N и аксиомы объемности следует, что существует лишь единственное множество, не содержащее никаких элементов, т. е. 1x y (у х). Поэтому мы можем ввести предметную константу 0, подчиняв ее следующему условию.
Определение. y (y 0).
Так как выполнено условие единственности для неупорядоченной пары, то можем ввести новую функциональную букву g(х, y) для обозначения неупорядоченной пары х и у. Впрочем вместо g(х, y) мы будем писать {х, у}. Заметим, что можно однозначно определить пару {X, Y} для любых двух классов Х и Y, а не только для множеств х и у. Положим {X, Y} = 0, если один из классов X, Y не является множеством. Можно доказать, что
NBG 1Z((M(X)&M(Y)&u (u Z u = X u = Y)) ((M(X) M(Y))&Z=0)).
Этим оправдано введение пары {X, Y}:
Определение. (М(Х) & М(Y) & u (и {X, Y} u = X u = Y))
((M(X) M(Y)) & {X, Y} = 0).
Можно доказать, что NBG x y u (u {х, у} u = x u = y) и NBG x y (M({х, у})).
Определение. = {{Х}, {X, Y}}. называется упорядоченной парой классов Х и Y.
Никакого внутреннего интуитивного смысла это определение не имеет. Оно является лишь некоторым удобным способом (его предложил Ку-ратовский) определить упорядоченные пары таким образом, чтобы можно было доказать следующее предложение, выражающее характеристическое свойство упорядоченных пар.
Предложение 3.
NBG x y u v ().
Доказательство. Пусть = . Это значит, что {{x}, {x, y}} = {{u}, {u, v}}. Так как {х} {{x}, {x, y}}, то {x} {{u}, {u, v}}. Поэтому {x} = ={u} или {х} = {u, v}. В обоих случаях х = и. С другой стороны, {u, v} {{u}, {u, v}} и, следовательно, {u, v} {{x}, {x, y}}. Отсюда {u, v} = {x} или {u, v} = ={x, y}. Подобным же образом {x, y} = {u} или {х, у}={и, v}. Если или {u, v} = ={x} и {х, y} = {u}, то х = и = у = v, в противном случае {и, v} = {х, у} и, следовательно, {и, v} = {u, у}. Если при этом v ≠ u, то y = v, если же v = u, то тоже y = v. Итак, в любом случае, y = v.
Oбобщим понятие упорядоченной пары до понятия упорядоченной n-ки.
Определение
= Х,
Так, например, и
В дальнейшем индекс NBG в записи NBG опускается.
Нетрудно доказать следующее обобщение предложения 3.
Эти аксиомы утверждают, что для некоторых свойств, выраженных формулами, существуют соответствующие классы всех множеств, обладающих этими свойствами.
А к с и о м а В1. X u v (X u v) (- отношение).
А к с и о м а В2. X Y Z u (u Z u X & u Y)
(пересечение).
А к с и о м а В3. X Z u (u Z u X) (дополнение).
А к с и о м а В4. X Z u (u Z v (X)) (область
определения).
А к с и о м а В5. X Z u v (Z u X).
А к с и о м а В6. X Z u v w (Z X).
А к с и о м а В7. X Z u v w (Z X).
С помощью аксиом В2-В4 можно доказать
X Y 1Z u (u Z u X & u Y),
X 1Zu (u Z u x),
X 1Zu (u Z v (X)).
Эти результаты оправдывают введение новых функциональных букв ∩, −, D.
Определения
u (u X ∩ Y u X & u Y) (пересечение классов Х и Y).
u (u u X) (дополнение к классу X).
u (u D (X) v (X)) (область определения класса X).
(объединение классов Х и Y).
V = (универсальный класс).
X − Y = X ∩
Общая теорема о существовании классов.
Предложение 4. Пусть φ (X1,…,Xn, Y1,…, Ym) – формула, переменные которой берутся лишь из числа X1,…,Xn, Y1,…, Ym . Назовём такую формулу предикативной, если в ней связными являются только переменные для множеств (т.е. если она может быть приведена к такому виду с помощью принятых сокращений). Для всякой предикативной формулы φ (X1,…,Xn, Y1,…, Ym)
Zx1 …xn (Z φ (x1,…,xn, Y1,…, Ym)).
Доказательство. Мы можем ограничиться рассмотрением только таких формул φ, которые не содержат подформул вида Yi W, так как всякая такая подформула может быть заменена на x (x = Yi & x W), что в свою очередь эквивалентно формуле x (z (z x z Yi) & x W). Можно также предполагать, что в φ не содержатся подформулы вида XX, которые могут быть заменены на u (u = X & u X), последнее же эквивалентно u (z (z u z X) & u X). Доказательство проведем теперь индукцией по числу k логических связок и кванторов, входящих в формулу φ (записанную с ограниченными переменными для множеств).
1. Пусть k = 0. Формула φ имеет вид xi xj, или xj xi, или xi Yi, где 1 ≤ i < j ≤ n. В первом случае, по аксиоме В1, существует некоторый класс W1 такой, что
xixj (W1 xi xj).
Во втором случае, по той же аксиоме, существует класс W2 такой, что
xixj (W2 xj xi),
и тогда, в силу
XZ u v (Z X),
существует класс W3 такой, что
xixj (W3 xj xi).
Итак, в любом из первых двух случаев существует класс W3 такой, что
xixj (W φ (x1,…,xn, Y1,…, Ym)).
Тогда, заменив в
XZ v1…vkuw (Z X)
X на W, получим, что существует некоторый класс Z1 такой, что
x1… xi-1xixj (Z1 φ (x1,…,xn, Y1,…, Ym)).
Далее, на основании
XZ v1…vmx1…xn (
ZX)
там же при Z1 = X, заключаем, что существует класс Z2 такой, что
x1 … xi xi+1 … xj (Z2 φ (x1,…,xn, Y1,…, Ym)).
Наконец, применяя
XZ v1…vmx1…xn (Z X)
(1)
там же при Z2 = Х, получаем, что существует класс Z такой, что
x1…xn (Z φ (x1,…,xn, Y1,…, Ym)).
Для остающегося случая xi Yi теорема следует из (1) и
XZ x v1…vm (Z x X).
2. Предположим, что теорема доказана для любого k < s и что φ содержит s логических связок и кванторов.
(a) φ есть ψ. По индуктивному предположению, существует класс W такой, что
x1…xn (W ψ (x1,…,xn, Y1,…, Ym)).
Теперь остается положить Z = .
(b) φ есть ψ θ. По индуктивному предположению, существуют классы Z1 и Z2 такие, что
x1…xn (Z1 ψ (x1,…,xn, Y1,…, Ym)) и
x1…xn (Z2 θ (x1,…,xn, Y1,…, Ym)).
Искомым классом Z в этом случае будет класс.
(c) φ есть x ψ. По индуктивному предположению, существует класс W такой, что
x1…xnx (W ψ (x1,…, xn, x, Y1,…, Ym)).
Применим сперва
XZ x1 … xn (Z y (X)).
при X = и получим класс Z1 такой, что
x1 … xn (Z1x ψ (x1,…, xn, x, Y1,…, Ym)).
Теперь положим окончательно Z = , замечая, что x ψ эквивалентно x ψ.
Примеры. 1. Пусть φ (X, Y1, Y2) есть формула uv (X = & u Y1 & v Y2). Здесь кванторы связывают только переменные для множеств. Поэтому, в силу теоремы о существовании классов, Z x (x Z uv (x = & u Y1 & v Y2)), а на основании аксиомы объемности, 1Z x (x Z uv (x = & u Y1 & v Y2)). Поэтому возможно следующее определение, вводящее новую функциональную букву:
Определение. x (x Y1 Y2 uv (x = & u Y1 & v Y2)). (Декартово произведение классов Y1 и Y2).
Определения. X2 обозначает X X (в частности, V2 обозначает класс всех упорядоченных пар).
Xn обозначает Xn-1 X (в частности, Vn обозначает класс всех упорядоченных n-ок).
Rel(X) служит сокращением для Х V2 (X есть отношение).
2. Пусть φ (X, Y) обозначает Х Y. По теореме о существовании классов и на основании аксиомы объемности, 1Zx (x Z x Y). Таким образом, существует класс Z, элементами которого являются все подмножества класса Y.
Определение. x (x P (Y) x Y). (P (Y): класс всех подмножеств класса Y.)
3. Рассмотрим в качестве φ (X, Y) формулу v (X v & v Y).
По теореме о существовании классов и на основании аксиомы объемности, 1Zx (x Z v (x v & v Y)), т.е. существует единственный класс Z, элементами которого являются все элементы элементов класса Y и только они.
Определение. x (x (Y) v (x v & v Y)). ((Y): объединение всех элементов класса Y)
4. Пусть φ (X) есть u (X =). По теореме о существовании классов и на основании аксиомы объемности, существует единственный класс Z такой, что x (x Z u (x =)).
Определение. x (x I u (x =)). (Отношение тождества.)
Следствие. Для всякой предикативной формулы φ (X1,…,Xn, Y1,… …, Ym)
1W(W Vn & x1…xn (W
φ (x1,…,xn, Y1,…, Ym)).
Доказательство. В силу предложения 4, существует класс Z, для которого x1…xn (Z φ (x1,…,xn, Y1,…, Ym)). Очевидно, искомым классом W является класс W = Z ∩ Vn; его единственность вытекает из аксиомы объемности.
Определение. Для всякой предикативной формулы φ (X1,…,Xn, Y1,… …, Ym) через φ (x1,…,xn, Y1,…, Ym)) обозначается класс всех n-ок, удовлетворяющих формуле φ (x1,…,xn, Y1,…, Ym)), т. е. u (u φ (x1,…,xn, Y1,…, Ym) x1…xn (u = & φ (x1,…,xn, Y1,… …, Ym))). Следствие оправдывает такое определение. В частности, при n = 1 получим u (u φ (x, Y1, …, Ym) φ (u, Y1,…, Ym)) (иногда вместо φ (x1,…,xn, Y1,…, Ym) применяют запись {| φ (x1,…,xn, Y1,…, Ym)}).
Примеры. 1. Пусть φ есть Y. Обозначим (Y) сокращенно через, тогда V2 & x1x2(Y Y). Назовем обратным отношением класса Y.
2. Пусть φ есть v (Y). Обозначим через R(Y) выражение (v (Y)). Тогда u (u R(Y) v (Y)). Класс R(Y) называется областью значений класса Y. Очевидно, R(Y) = D().
Заметим, что аксиомы В1 - В7 являются частными случаями теоремы о существовании классов, т. е. предложения 4. Иными словами, вместо того, чтобы выдвигать предложение 4 в качестве схемы аксиом, можно с тем же результатом ограничиться лишь некоторым конечным числом его частных случаев. Вместе с тем, хотя предложение 4 и позволяет доказывать существование большого числа самых разнообразных классов, нам, однако, ничего еще не известно о существовании каких-либо множеств, кроме самых простых множеств таких, как 0, {0}, {0, {0}}, {{0}} и т. д. Чтобы обеспечить существование множеств более сложной структуры, введем дальнейшие аксиомы.
xyu (u y v (u v & v x)).
Эта аксиома утверждает, что объединение (х) всех элементов множества х является также множеством, т. е. x (M((х))). Множество и (х) обозначают также через и v.
Средством порождения новых множеств из уже имеющихся является образование множества всех подмножеств данного множества.
xyu (u y u x).
Эта аксиома утверждает, что класс всех подмножеств множества х есть также множество; его будем называть множеством всех подмножеств множества х. В силу этой аксиомы, x (M(P (х))).
Примеры.
P (0) = {0}.
P ({0}) = {0, {0}}.
P ({0, {0}}) = {0, {0}, {0, {0}}, {{0}}}.
Значительно более общим средством построения новых множеств является следующая аксиома выделения.
xY zu (u z u x & u Y).
Таким образом, для любого множества х и для любого класса Y существует множество, состоящее из элементов, общих для х и Y. Следовательно, xY (M (x ∩ Y)), т. е. пересечение множества с классом есть множество.
Предложение 5. xY (Y x M (Y)) (т. е. подкласс множества есть множество).
Доказательство. x (Y x Y ∩ x = Y) и x (M (Y ∩ x)).
Так как всякая предикативная формула A(у) порождает соответствующий класс (предложение 4), то из аксиомы S следует, что для любого множества х класс всех его элементов, удовлетворяющих данной предикативной формуле A(у), есть множество.
Однако для полного развития теории множеств потребуется аксиома, более сильная, чем аксиома S. Введем предварительно несколько определений.
Определения Un (X) означает xyz (X & X y = z).
(X однозначен.)
Fnc (X) означает X V2 & Un (X). (X есть функция.)
Y 1 X означает X ∩ (Y V). (Ограничение Х областью Y.)
Un1 (X) означает Un (X) & Un (). (X взаимно однозначен.)
X‘Y
Если существует единственное z такое, что X, то z = X‘y; в противном случае X‘y = 0. Если Х есть функция, а у - множество из области определения X, то X‘y есть значение этой функции, примененной к у (В дальнейшем будем по мере необходимости вводить новые функциональные буквы и предметные константы, как только будет ясно, что соответствующее определение может быть обосновано теоремой о единственности. В настоящем случае происходит введение некоторой новой функциональной буквы h с сокращенным обозначением Х‘Y вместо h (X, Y)).
X‘‘Y = R(Y 1 X). (Если Х есть функция, то X‘‘Y есть область значений класса X, ограниченного областью Y.)
{\slider}{slider=- Аксиома замещения.}
x (Un (X) yu (u y v (X & v X))).
Аксиома замещения утверждает, что если класс Х однозначен, то класс вторых компонент тех пар из X, первые компоненты которых принадлежать, является множеством (эквивалентное утверждение: M(R (x 1X))) Из этой аксиомы следует, что если Х есть функция, то область значений результата ограничения Х посредством всякой области, являющейся множеством, также есть множество.
Следующая аксиома обеспечивает существование бесконечных множеств.
x (0 x & u (u x u {u} x)).
Аксиома бесконечности утверждает, что существует такое множество х, что 0 x, и если и x, то и {и} также принадлежит х. Для такого множества х, очевидно, {0} x, {0, {0}} x, {0, {0}, {0, {0}}} x и т. д. Если теперь положим 1 = {0}, 2 = {0, 1}, … , n = {0, 1, … , n – 1}, то для любого целого п ≥ 0 будет выполнено п х, и при этом 0 ≠ 1, 0 ≠ 2, 1 ≠ 2, 0 ≠ 3, 1 ≠ ≠ 3, 2 ≠ 3, …
Список аксиом теории NBG завершен. Видно, что NBG имеет лишь конечное число аксиом, а именно: аксиому Т (объемности), аксиому Р (пары), аксиому N (пустого множества), аксиому S (выделения), аксиому U (объединения), аксиому W (множества всех подмножеств), аксиому R (замещения), аксиому I (бесконечности) и семь аксиом существования классов В1-В7.
Убедимся теперь в том, что парадокс Рассела невыводим в NBG. Пусть Y = (x x) ,т. е. х (х Y х х). (Такой класс Y существует, в силу теоремы о существовании классов (предложение 4), так как формула х х предикативна.) В первоначальной, т. е. не сокращенной, символике эта последняя формула записывается так: X (M(X) (X Y X X)). Допустим M(Y). Тогда Y Y Y Y, что, в силу тавтологии (A A) A & & A, влечет Y Y Y Y. Отсюда по теореме дедукции получаем M(Y)(Y Y Y Y), а затем, в силу тавтологии (B (A & A)) B , получаем и М(Y). Таким образом, рассуждения, с помощью которых обычно выводится парадокс Рассела, в теории NBG приводят всего лишь к тому результату, что Y есть собственный класс, т. е. не множество. Здесь имеем дело с типичным для теории NBG способом избавления от обычных парадоксов (например, парадоксов Кантора и Бурали-Форти).
Определения X Irr Y означает y (y Y X) & Rel (X).
(X есть иррефлексивное отношение на Y.)
X Tr Y означает Rel (X) & uvw (uY & vY & wY &
& X &X & X X).
(X есть транзитивное отношение на Y.)
X Part Y означает (X Irr Y) & (X Tr Y).
(X частично упорядочивает Y.)
X Con Y означает Rel(X) & uv (uY & vY & u ≠ v
X X).
X Tot Y означает (X Irr Y) & (X Tr Y) & (X Con Y).
(X упорядочивает Y.)
X We Y служит обозначением для Rel(X) & (X Irr Y) & Z (ZY &
& Z ≠ 0 y (y Z & v (v Z & v ≠ y X &
& X))).
(X вполне упорядочивает Y, т. е. отношение Х иррефлексивно на Y, и всякий непустой подкласс класса Y имеет наименьший в смысле отношения Х элемент.)
Аксиома выбора является одним из самых знаменитых и наиболее оспариваемых утверждений теории множеств.
Следующие формулы эквивалентны:
Аксиома выбора (АС): Для любого множества х существует функция f такая, что для всякого непустого подмножества у множества х f‘ y y (такая функция называется выбирающей функцией для х).
Мультипликативная аксиома (Mult): Для любого множества х непустых и попарно непересекающихся множеств, существует множество у (называемое выбирающим множеством для х), которое содержит в точности по одному элементу из каждого множества, являющегося элементом х.
u (u x u ≠ 0 & v (v x & v ≠ u v ∩ u = 0))
yu (u x 1w (w u ∩ y)).
Принцип в полне упорядочения (W. O.): Всякое множество может быть вполне упорядочено. x y (y We x).
Трихотомия (Trich): xy (x y y x).
Лемма Цорна (Zorn): Если в частично упорядоченном множестве х всякая цепь (т. е. всякое упорядоченное подмножество) имеет верхнюю грань, то в х существует максимальный элемент.
xy ((y Part x) & u (u x & y Tot u v (v x &w (w u w =
= v y))) v (v x &w (w x y))).
Доказательство.
1. (W. O.) Trich. Пусть даны множества х и у. Согласно (W. O.), х и у могут быть вполне упорядочены. Поэтому существуют такие порядковые числа α и β, что х α и y β. Но так как α β или β α, то либо x y, либо y x.
2. Trich (W. O.). Пусть дано множество х. Согласно теореме Хартогса, существует такое порядковое число α, которое не равномощно никакому подмножеству множества х. Тогда, в силу Trich, х равномощно некоторому подмножеству у порядкового числа α, и вполне упорядочение Еу множества у порождает некоторое вполне упорядочение множества х.
3. (W. O.) Mult. Пусть х есть некоторое множество непустых, попарно непересекающихся множеств. Согласно (W. O.), существует отношение R, вполне упорядочивающее множество (х). Следовательно, существует такая определенная на х функция f, что f‘u для любого и х есть наименьший относительно R элемент и. (Заметим, что и (х).)
4. Mult AC. Для любого множества х существует функция g такая, что если и есть непустое подмножество х, то g‘и = u {и}. Пусть х1 -область значении функции g. Легко видеть, что х1 является множеством непустых попарно непересекающихся множеств. На основании Mult, для х1 существует выбирающее множество у. Отсюда, если 0 ≠ u и u х, то и {и} х1 и у содержит и притом единственный элемент из и {и}. Функция f‘ u = v является искомой выбирающей функцией для х.
5. АС Zorn. Пусть у частично упорядочивает непустое множество х таким образом, что всякая y-цепь в х имеет в х верхнюю грань. На основании АС, для х существует выбирающая функция f. Рассмотрим произвольный элемент b множества х, и по трансфинитной индукции определим функцию F такую, чтобы выполнялось F‘0 = b и F‘α = f‘u для любого α, где u есть множество всех таких верхних граней v множества F‘‘ α относительно упорядочения у, что v х и v F‘‘ α. Пусть β есть наименьшее порядковое число, которому соответствует пустое множество верхних граней v множества F‘‘ β относительно упорядочения v, принадлежащих x и не принадлежащих F‘‘ β. (Порядковые числа, обладающие таким свойством, существуют; в противном случае функция F была бы взаимно однозначной с областью определения Оп и с некоторым подмножеством множества х в качестве области значений, откуда по аксиоме замещения R следовало бы, что Оп есть множество.) Пусть g = β 1 F. Функция g взаимно однозначна и что если α
Аксиоматика теории множеств
Пояснение к аксиомам ZFC
Аксиомы ZFC включают в себя:
0) группу высказываний о равенстве множеств (1 аксиома),
1) группу высказываний о существовании множеств (2 аксиомы),
2) группу высказываний об образовании множеств из уже имеющихся множеств (3 аксиомы и 2 схемы), в которой можно выделить три подгруппы,
3) группу высказываний об упорядоченности образованных множеств (2 аксиомы).
0. Критерий равенства множеств в ZFC
Следующее высказывание выражает необходимое условие идентичности двух множеств.
Аксиома экстенсиональности (Аксиома объёмности)
Примечание
«Аксиому объёмности» можно сформулировать следующим образом: «Если каждый элемент первого множества принадлежит второму множеству, а каждый элемент второго множества принадлежит первому множеству, тогда первое множество идентично второму [множеству].»
Достаточное условие идентичности двух множеств имеет вид и выводится из аксиом предиката , а именно:
, , где - любое математически корректное суждение об , а - то же самое суждение, но об .Соединение указанного достаточного условия [идентичности множеств] с аксиомой объёмности даёт следующий критерий равенства множеств:
1. Аксиомы ZFC о существовании множеств
«Аксиома объёмности» была бы бесполезным высказыванием, если бы не существовало ни одного множества или существовало только одно множество.
Следующие два высказывания гарантируют существование по меньшей мере двух разных множеств, а именно: а) множества, в котором нет ничего, и б) множества, содержащего бесконечное количество элементов.
Примечание
«Аксиому [существования] пустого множества» можно сформулировать следующим образом: «Существует [по меньшей мере одно] множество без единого элемента.»
Доказывается, что «аксиома пустого множества» равносильна высказыванию . Поэтому единственному множеству можно присвоить имя. Употребительны два имени: и . Используя указанные имена, «аксиому пустого множества» записывают так:
и , гдеПримечание
«Аксиому бесконечности» можно сформулировать следующим образом: «Существует [по меньшей мере одно] „бесконечное множество“, которое состоит из .»
Высказывание о существовании бесконечного множества отличается от (ложного в данной аксиоматике) высказывания о существовании «множества всех множеств» ().
2. Аксиомы ZFC об образовании множеств
Следующие пять высказываний можно назвать аксиомами образования множеств [из имеющихся множеств, включая и по меньшей мере одну ].
Каждое из этих пяти высказываний создано на основе высказывания , которое выводится из аксиом предиката .
Эти пять высказываний можно объединить в следующие подгруппы:
2.0) группу постулатов об образовании множеств путём перечисления их элементов,
2.1) группу деклараций об учреждении и об упразднении семейств множеств,
2.2) группу схем образования множеств с помощью математически корректных суждений.
2.0. Постулаты об образовании множеств путём перечисления их элементов
Простейший способ образовать новое множество [из уже имеющихся множеств] состоит в том, чтобы «ткнуть пальцем» в каждое множество, которое должно стать элементом [образуемого множества]. В ZFC указанный способ образования множеств представлен одной аксиомой, в которой «тыканье пальцем» моделируется с помощью предиката .
, что естьПримечание
«Аксиому [неупорядоченной] пары» можно сформулировать следующим образом: «Из любых двух множеств можно образовать „неупорядоченную пару“, то есть такое множество , каждый элемент которого идентичен данному множеству или данному множеству ».
Примеры
Доказывается, что «аксиома пары» равносильна высказыванию . Поэтому единственному множеству можно присвоить имя . Используя указанное имя, «аксиому пары» записывают так:
илиСледующие две аксиомы, именуемые «аксиомой множества подмножеств» и «аксиомой объединения», можно рассматривать как естественное дополнение к «аксиоме пары». Чтобы убедиться в этом, заметим следующее.
Известно, что каждое множество имеет подмножества , включая [копию пустого множества] и [копию самого множества] . Иначе говоря,
.Руководствуясь «аксиомой пары», из названных подмножеств можно образовать неупорядоченную пару . Назовём эту пару семейством .
Если можно образовать семейство из двух подмножеств множества , тогда можно объявить об образовании семейства из всех подмножеств множества .
Чтобы объявить об образовании семейства достаточно потребовать, чтобы каждый элемент названного семейства был подмножеством множества , а каждое подмножество названного множества было элементом семейства . Иначе говоря, , что равносильно предложению , , .Если можно объявить об учреждении семейства , тогда можно объявить об упразднении названного семейства.
Мыслимы различные способы упразднения семейства , включая: 1) его полное упразднение (уничтожение), то есть , что равносильно , 2) его фиктивное упразднение (резервирование), то есть , что равносильно , 3) его реверсивное упразднение (расформирование), то есть , что равносильно . Поскольку , постольку предложение равносильно предложению , которое подразумевает предложение , которое является частным случаем высказывания .
Из изложенного следует, что высказывания и можно считать независимыми условно.
2.1.0 Аксиома множества подмножеств (Аксиома булеана)
, что есть , гдеПримечание
«Аксиому множества подмножеств» можно сформулировать следующим образом: «Из любого множества можно образовать „суперкучу“, то есть такое множество , каждый элемент которого является [собственным либо несобственным] подмножеством данного множества .»
Примеры , так как
Доказывается, что «аксиома множества подмножеств» равносильна высказыванию . Поэтому единственному множеству можно присвоить имя , которое произносится: «множество всех подмножеств [множества] » или «булеан [множества] ». Используя указанное имя, «аксиому множества подмножеств» записывают так:
или , что естьПримечание
Аксиому объединения [множеств] можно сформулировать следующим образом: «Из любого семейства множеств можно образовать „кучу-малу“, то есть такое множество , каждый элемент которого принадлежит по меньшей мере одному множеству данного семейства ».
Примеры
Доказывается, что аксиома объединения равносильна высказыванию . Поэтому единственному множеству можно присвоить имя , которое произносится: «объединение множеств семейства ». Используя указанное имя, аксиому объединения записывают так:
или .Объединение множеств семейства () не следует путать с пересечением множеств семейства (), о котором известно:
, то есть2.2. Схемы образования множеств с помощью математически корректных суждений
Среди математических высказываний встречаются аксиомы связи, включая:
а) аксиому связи между алгебраической операцией (сложить) и алгебраической операцией (умножить)
,б) аксиому связи между отношением порядка (меньше или равно) и алгебраической операцией (сложить)
Следующие два высказывания, именуемые «схемой выделения» и «схемой преобразования», являются аксиомами связи между множествами (например, множеством ) и математически корректными суждениями (например, суждением ).
«Схема выделения» и «схема преобразования» выражают следующую простую мысль: «Каждое математически корректное суждение об элементах любого множества приводит к образованию [того же самого или другого] множества.»
Математически корректные суждения, фигурирующие в «схеме выделения», позволяют «довести [до товарного вида]» множества, которые образованы, например, с помощью аксиомы булеана. Поэтому указанные математические суждения аналогичны штихелям, надфелям, часовым отвёрткам и иным доводочным инструментам.
Математически корректные суждения, фигурирующие в «схеме преобразования», позволяют создавать «[математические] изделия» из ["неотёсанных"] множеств, образованных, например, с помощью аксиомы булеана. Поэтому указанные математические суждения аналогичны прецизионным станкам.
, что есть , где - любое математически корректное суждение о , но не о множестве и не о множестве .Примечание
Схему выделения [подмножеств] можно сформулировать следующим образом: «Из каждого множества можно выделить [по меньшей мере одно] подмножество , высказав суждение о каждом элементе данного множества .»
Примеры
Доказывается, что схема выделения равносильна высказыванию . Поэтому единственному подмножеству можно присвоить имя . Используя указанное имя, схему выделения записывют так:
илиСхема выделения равносильна счётному множеству аксиом.
, что естьПримечание
Схему преобразования [множеств] можно сформулировать следующим образом: «Любое множество можно преобразовать в [то же самое или другое] множество , высказав любое истинное математически корректное функциональное суждение обо всех элементах данного множества .»
Примеры
Доказывается, что в схеме преобразования множество единственно. Поэтому указанному множеству можно присвоить имя . Используя указанное имя, схему преобразования записывают так:
илиСхема преобразования равносильна счётному множеству аксиом.
3. Аксиомы ZFC об упорядоченности множеств
Следующие два высказывания определяют упорядоченность множеств, которые образованы из и каждой с помощью аксиом образования множеств. Образно говоря, высказывания об упорядоченности множеств образуют «сортировочный цех» теории ZFC, тогда как высказывания об образовании множеств образуют «производственный цех» этой теории.
Примечание
«Аксиому регулярности» можно сформулировать следующим образом: «В любом семействе множеств есть [по меньшей мере одно] множество , каждый элемент которого не принадлежит данному семейству .»
Примеры Сравните с высказываниями и , а также . Сравните с высказываниями и . Сравните с высказываниями и .
Примечание
«Аксиому выбора» можно сформулировать следующим образом: «Из любого семейства непустых попарно непересекающихся множеств можно выбрать „делегацию“, то есть такое множество , в котором есть по одному элементу от каждого множества данного семейства .»
Пример Предположим, что семейство образовано из множества неотрицательных чётных чисел и множества неотрицательных нечётных чисел. В таком случае, выполнены все условия «аксиомы выбора», а именно: , , . Следовательно, можно образовать по меньшей мере одну «делегацию» в составе одного «делегата» (например, нуля) от множества и одного «делегата» (например, единицы) от множества . Действительно: . .
Примечания
1. Если ZFC непротиворечива, то ее непротиворечивость не может быть доказана средствами ZFC, согласно второй теореме Гёделя.
Введение
Значение математической логики в нашем и прошлом столетии сильно возросло. Главной причиной этого явилось открытие парадоксов теории множеств и необходимость пересмотра противоречивой интуитивной теории множеств. Было предложено много различных аксиоматических теорий для обоснования теории множеств, но как бы они не отличались друг от друга своими внешними чертами, общее для всех них содержание составляют те фундаментальные теоремы, на которые в своей повседневной работе опираются математики. Выбор той или иной из имеющихся теорий является в основном делом вкуса; мы же не предъявляем к системе, которой будем пользоваться, никаких требований, кроме того, чтобы она служила достаточной основой для построения современной математики.
§1. Система аксиом
Опишем теорию первого порядка NBG, которая в основном является системой того же типа, что и система, предложенная первоначально фон Нейманом , , а затем тщательно пересмотренная и упрощенная Р. Робинсоном , Бернайсом и Гёделем . (Будем в основном следовать монографии Гёделя, хотя и с некоторыми важными отклонениями.) Теория NBG имеет единственную предикатную букву
и не имеет ни одной функциональной буквы или предметной константы. Чтобы быть ближе к обозначениям Бернайса и Гёделя , мы будем употреблять в качестве переменных вместо x1, x2, … прописные латинские буквы X1, Х2, ... (Как обычно, мы используем буквы X, Y, Z, ... для обозначения произвольных переменных.) Мы введем также сокращенные обозначения ХY для(X, Y) и XY для (X, Y). Содержательно знак понимается как символ отношения принадлежности.Следующим образом определим равенство:
Определение. Х=Y служит сокращением для формулы
.Таким образом, два объекта равны тогда и только тогда, когда они состоят из одних и тех же элементов.
Определение.
служит сокращением для формулы (включение).Определение. X
Y служит сокращением для Х Y & X ≠ Y (собственное включение).Из этих определений легко следует
Предложение 1.
Х = Y (X Y & Y X); Х = Х; Х = Y Y = Х; Х = Y (Y = Z Х = Z); Х = Y (ZX ZY).Теперь приступим к перечислению собственных аксиом теории NBG, перемежая формулировки самих аксиом различными следствиями из них и некоторыми дополнительными определениями. Предварительно, однако, отметим, что в той «интерпретации», которая здесь подразумевается, значениями переменных являются классы. Классы - это совокупности, соответствующие некоторым, однако отнюдь не всем, свойствам (те свойства, которые фактически определяют классы, будут частично указаны в аксиомах. Эти аксиомы обеспечивают нам существование необходимых в математике классов и являются, достаточно скромными, чтобы из них нельзя было вывести противоречие). (Эта «интерпретация» столь же неточна, как и понятия «совокупность», «свойство» и т. д.)
Назовем класс множеством, если он является элементом какого-нибудь класса. Класс, не являющийся множеством, назовем собственным классом.
Определение. M(X) служит сокращением для
Y(XY) (X есть множество).Определение. Pr(X) служит сокращением для
M(X) (X есть собственный класс).В дальнейшем увидим, что обычные способы вывода парадоксов приводят теперь уже не к противоречию, а всего лишь к результату, состоящему в том, что некоторые классы не являются множествами. Множества предназначены быть теми надежными, удобными классами, которыми математики пользуются в своей повседневной деятельности; в то время как собственные классы мыслятся как чудовищно необъятные собрания, которые, если позволить им быть множествами (т. е. быть элементами других классов), порождают противоречия.
Система NBG задумана как теория, трактующая о классах, а не о предметах. Мотивом в пользу этого послужило то обстоятельство, что математика не нуждается в объектах, не являющихся классами, вроде коров или молекул. Все математические объекты и отношения могут быть выражены в терминах одних только классов. Если же ради приложений в других науках возникает необходимость привлечения «неклассов», то незначительная модификация системы NBG позволяет применить ее равным образом как к классам, так и к «неклассам» (Мостовский ).
Мы введем строчные латинские буквы x1, x2, … в качестве специальных, ограниченных множествами, переменных. Иными словами,
x1 A (x1) будет служить сокращением для X (M(X)A (X)) , что содержательно имеет следующий смысл: «A истинно для всех множества, и x1 A (x1) будет служить сокращением для X (M(X)A (X)), что содержательно имеет смысл: «A истинно для некоторого множества». Заметим, что употребленная в этом определении переменная X должна быть отличной от переменных, входящих в A (x1). (Как и обычно, буквы х, y, z, ... будут употребляться для обозначения произвольных переменных для множеств.)П р и м е р. Выражение
ХхyZA (X, х, y, Z) служит сокращением для ХXj (М(Xj)Y(M(Y)&ZA (X, Xj, Y, Z))).А к с и о м а Т. (Аксиома объемности.) Х = Y