прямо по Кантору: "под множеством мы понимаем любое соединение M определенных различимых объектов (которые будут называться элементами M) в единое целое"

понятие множества оформляет идею "принадлежности" ∈ (отношение между множеством и его элементами)

если F - это множество множеств, то можно образовать новое множество ⋃F, содержащее все элементы множеств, входящих в F. а разве оно не есть само F? нет, конечно: в ящике содержатся коробки, в каждой коробке - спички, но ящик-то спичек не содержит (что, быть может, против здравого смысла). ⋃F - спички из всех коробок, ссыпанные в кучу, что совсем не эквивалент множества коробок F (хотя от такой иллюзии трудно отвязаться)

В ТЕОРИИ МНОЖЕСТВ НИКОГДА НЕ БЫЛО НИКАКИХ ПРОТИВОРЕЧИЙ

острие критики логических парадоксов должно быть нацелено на содержащееся в них допущение, что для любого свойства P существует соответствующее множество элементов x, обладающих свойством P(x). но стоит лишь отвергнуть это допущение - так сразу же и логические парадоксы становятся невозможными

парадокс Рассела всего лишь доказывает (от противного), что не существует множества всех множеств, не являющихся собственными элементами ({ x | x ∉ x }) и, тем самым, не для любого свойства P обязано существовать множество { x | P(x) }. но никто из серьезных математиков никогда и не утверждал, что любое свойство должно определять множество - и во всяком случае, канторовское определение говорит нечто совершенно другое - в действительности, для любого предиката P из двух свойств P и ¬P не более одного является коллективизирующим. т.о., не более чем одна из формул { x | P(x) } и { x | ¬P(x) } может определять некоторое множество. пока начинающий не в состоянии судить, какая из этих формул имеет смысл, он должен полностью избегать обозначение { x | P(x) }

в канонической форме, система аксиом Цермело–Френкеля (ZFC) состоит из 9 аксиом. довольно часто аксиомы 1–8 рассматриваются отдельно от аксиомы 9 (Аксиомы Выбора). система аксиом Цермело–Френкеля без Аксиомы Выбора обозначается аббревиатурой ZF, с аксиомой выбора - ZFC (Zermelo–Fraenkel with Axiom of Choice)

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

Аксиома Выбора независима от остальных аксиом Цермело-Френкеля: ее нельзя ни доказать, ни опровергнуть в этой системе аксиом - если система Цермело-Френкеля непротиворечива, то она непротиворечива как в предположении, что Аксиома Выбора верна (это доказал Гёдель), так и в предположении, что Аксиома Выбора неверна (это доказал Коэн)

имеются шары, занумерованные натуральными числами. за минуту до полудня в ящик кладутся шары с номерами от 1 до 10, а шар 1 вынимается обратно. за 1/2 минуты до полудня кладутся шары от 11 до 20, а шар номер 2 вынимается обратно. за 1/3 минуты до полудня кладутся шары с номерами от 21 до 30, а шар с номером 3 вынимается обратно, и т.д. сколько шаров останется в ящике в полдень? кажущаяся парадоксальность в том, что на каждом шаге количество шаров в ящике увеличивается на 9 штук, и в полдень должно быть «бесконечное» их число. с другой стороны, шар с любым номером n будет вынут на n-м шаге, так что и остаться в ящике ничего не может. что думаете? условие маскирует некорректность задачи. откажемся от "сжатия" процесса к точке полудня, которое создает иллюзию того, что последовательность все-таки завершится и развернем его в "линейку": пусть добавление и изъятие шаров происходит попросту каждую секунду. теперь совершенно ясно, что при n→∞ количество шаров в ящике неограниченно растет; это означает, что какое бы N ни задали, можно указать номер шага n, при котором оно будет превышено! в оригинальной постановке задача по сути дела спрашивает: сколько шаров окажется в ящике при n→∞? но вопрос не имеет смысла: «бесконечность» - такого числа нет

в теории множеств вообще не говорят о количестве элементов, тем более о бесконечном их количестве; множества сравнивают только по мощности. постулируют существование множеств, из которых можно сколько угодно раз изымать по одному элементу - и мощность не изменится. их-то и называют "бесконечными"

несмотря на очевидную связь и похожесть символов принадлежности ∈ и включения ⊂, понятия "принадлежности" и "включения" - различны. принадлежность А∈В означает что А - ОДИН из элементов множества В (т.е. один из НЕДЕЛИМЫХ объектов, составляющих В), тогда как включение А⊂В означает, что А состоит из НЕКОТОРЫХ элементов множества В (может быть - лишь из одного элемента, но как множество)

принадлежность очевидным образом не обладает свойством рефлективности

принадлежность не обладает свойством транизтивности. контр-пример:
А=1, В={1,2,3}, A ∈ B, C={ {1,2,3}, {4,5,6} }, B ∈ C но A ∉ C

коммутативность операций ∩ и ∪

для любых множеств А и В выполнены равенства

ассоциативность операций ∩ и ∪

для любых множеств А, В и С выполняются равенства

две дистрибутивности

для любых множеств А, В и С выполняются равенства

булевы операции

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

булеан 2^U - это категория, объектами которой являются подмножества множества U, причем множество Morth(X,Y) пусто, если X = Y = ∅ и состоит из единственного элемента, если X ⊆ Y. композиции морфизмов соответствуют цепочкам X ⊆ Y ⊆ Z. множество 2^{2^U} естественно истолковывать как 2-категорию и т.д. с этой точки зрения вещественные числа образуют категорию, а множество всех множеств вещественных чисел образуют 2-категорию

множество n-элементных подмножеств множества U называется n-й "внешней степенью" множества U и обозначается через:

количество n-элементных подмножеств m-элементного множества называется "числом сочетаний из m по n", которое равно |Λⁿ(m)|. эти числа называются "биномиальными коэффициентами"

булевыми операциями называются четыре бинарные операции на множествах:

intersection, durchschnitt

пересечение является просто переводом конъюнкции с интенционального на экстенсиональный язык

Def : пересечением двух множеств X и Y называется множество X ∩ Y, состоящее из тех и только тех элементов, которые принадлежат обоим множествам X и Y:

аналогия с конъюнкцией эксплицируется следующим образом: если X - подмножество множества K, выделенное свойством P, а Y - подмножество того же множества, выделяемое свойством Q, то

пересечение множеств X и Y - это инфимум пары {X,Y}. иными словами, наибольшее множество Z такое, что Z ⊆ X и Z ⊆ Y. в частности, X ∩ Y = X ⇐⇒ X ⊆ Y

union, vereinigung

объединение является экстенсиональным аналогом дизъюнкции

Def : объединением множеств X и Y называется множество X ∪ Y, состоящее из тех и только тех элементов, которые принадлежат по крайней мере одному из множеств X и Y,

если, X и Y - подмножества множества K, выделенные свойствами P и Q, соответственно, то

объединение множеств X и Y определяется как супремум пары {X, Y}. иными словами, наименьшее множество Z такое, что Z ⊇ X и Z ⊇ Y. в частности, X ∪ Y = X ⇐⇒ X ⊇ Y

в TEX знак пересечения ∩ называется \cap, а знак объединения ∪ - \cup (кепка и чашка). чтобы не путать, чт.е. что, начинающему достаточно запомнить одно из трех следующих мнемонических соображений:

неприводимые множества

Def : множество X называется неприводимым если оно не может быть представлено как обьединение двух (открытых) множеств, не равных ему. в противном случае оно называется "приводимым"

операция разности множеств

Def : разностью двух множеств X и Y называется множество X \ Y, состоящее из тех и только тех элементов, которые принадлежат множеству X, но не принадлежат множеству Y,

если X - подмножество множества K, выделенное свойством P, а Y - подмножество того же множества, выделяемое свойством Q, то

разность можно определить так: разность множеств X и Y - это наибольшее подмножество в X, которое не пересекается с Y

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

разность множеств, вообще говоря, не является ни коммутативной, ни ассоциативной

для любых трех множеств имеет место включение

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

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

заменой левой дистрибутивности разности относительно пересечения и объединения являются формулы де Моргана, в которых пересечение и объединение меняются местами:

кажется, что эти формулы были известны всегда и невозможно представить, чтобы их не знали Лейбниц и Эйлер, однако в действительности, они были впервые опубликованы лишь деМорганом в 1848 году и Пирсом в 1867 году

в TEX’е знак теоретико-множественной разности \ называется \setminus

симметрическая разность

Def : симметрической разностью двух множеств A и B называется множество A Δ B, состоящее из тех и только тех элементов, которые принадлежат ровно одному из множеств A или B,

симметрическая разность обладает более замечательными свойствами, чем пересечение и объединение

именно свойства G3 и G5 отличают симметрическую разность от остальных булевых операций. подобно симметрической разности объединение имеет нейтральный элемент ∅, но ни для одного A ≠ ∅ не существует множества B симметричного к A по отношению к объединению, т.е. такого, что A ∪ B = ∅. для симметрической же разности каждое множество симметрично себе

в отличие от пересечения и объединения симметрическую разность нельзя определить для бесконечного семейства множеств

дизъюнктное объединение

Def : множества X и Y не пересекаются (дизъюнктны), если X ∩ Y = ∅. в противном случае они пересекаются

в случае, когда X и Y дизъюнктны, мы будем использовать для объединения X ∪ Y запись X ∐ Y и называть его дизъюнктным объединением

т.о. , Z = X ∐ Y по определению означает, что Z = X ∪ Y и X ∩ Y = ∅. это определение распространяется на любое количество объединяемых множеств. так, запись

о некоторых законах алгебры. множества

1. коммутативные законы:

2. ассоциативные законы:

т.о., объединение и пересечение ассоциативны

3. идемпотентные законы:

4. распределительные законы :

т.о., объединение и пересечение дистрибутивны

5. Законы Де Моргана:

законы Де Моргана также можно записать как:
(i) (A U B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ U B’

6. для любых двух конечных множеств A и B :

7. для любых трех конечных множеств A, B и C :

произведения и копроизведения

OP (Аксиома упорядоченных пар):
равенство двух упорядоченных пар (x,y) = (u,v) имеет место тогда и только тогда, когда x = u и y = v

x называется первой компонентой, а y - второй компонентой упорядоченной пары (x,y)

если множества A и B конечны, причем A содержит m элементов, а B содержит n элементов, то множество A × B тоже конечно и содержит m*n элементов. вообще, для любых двух конечных множеств A и B мощность их прямого произведения A×B равна произведению мощностей множеств A и B, |A×B| = |A | * |B|

λ> a = [1, 2, 3]
λ> b = [10, 11, 12, 13]
λ> c = sequence [a,b] >>= \ [k,t] -> return (k,t)
λ> c
[(1,10),(1,11),(1,12),(1,13),(2,10),(2,11),(2,12),(2,13),(3,10),(3,11),(3,12),(3,13)]
λ> length c
12

всегда, когда речь идет о двух независимо меняющихся величинах (абсцисса и ордината, модуль и аргумент, широта и долгота, целая и дробная часть, вертикали и горизонтали, ряд и место, масть и ранг, лицо и число и т. д.) мы имеем дело с прямым произведением

разложение множества в прямое произведение задает на нем нетривиальную структуру

прямое произведение множеств

прямое произведение двух множеств A и B это не просто некое множество A × B, а множество A × B вместе с отображениями

то же самое множество A×B вместе с другой парой отображений f:A×B→A, g:A×B→B может уже не быть прямым произведением множеств A и B

прямое произведение множеств дистрибутивно относительно булевых операций:

операция прямого произведения является не теоретико-множественной, а теоретико-категорной. результат применения булевых операций определен "на самом деле". в отличие от этого прямое произведение двух множеств определено "не единственным образом", а лишь с точностью до канонического изоморфизма

наивное прямое произведение A×B обладает универсальным свойством, любое другое прямое произведение множеств A и B канонически изоморфно ему, но равенство множеств является абсолютно бессмысленным понятием при рассмотрении прямых произведений, которые определены лишь с точностью до канонических изоморфизмов

понятие прямого произведения легко обобщается на любое КОНЕЧНОЕ число сомножителей. во многих элементарных руководствах прямое произведение конечного числа множеств беззастенчиво определяется по индукции как

копроизведение

Def: копроизведением называется пара отображений :

Тh: пусть C и D - два прямых произведения множеств A и B, с каноническими проекциями

функция

пусть S₁, S₂ - множества. соответствием называется любое подмножество P ⊂ S₁ × S₂. если пара (x,y) принадлежит P, то говорят: "соответствие P выполнено для пары (x,y)". это обозначается P(x,y)

соответствие обычно задается какой-либо формулой: например, если S₁ = S₂ = ℝ (множество вещественных чисел), то формулы x<y, x>y, x!=y задают соответствия

соответствие иногда называют отношением, или бинарным отношением

пусть на множестве S задано отношение ∼, удовлетворяющее следующим условиям

пусть заданы два множества A и B и некоторое правило, позволяющее каждому элементу a из множества A сопоставить какой-то элемент b из множества B. тогда говорят, что задано отображение, действующее из множества A в множество B

множества A и B, между которыми установлено взаимно-однозначное отображение, состоят из одинакового числа элементов. это наблюдение, очевидно верное в случае конечных множеств, обобщается на случай множеств бесконечных. а именно, считается,что мощности множеств A и B совпадают: |A| = |B| если между этими множествами можно установить взаимно-однозначное отображение. при этом множества A и B называются эквивалентными. т.о. , желая найти мощность какого-то бесконечного множества, строят его взаимно однозначное отображение на другое множество с уже известной мощностью. наиболее простым из бесконечных множеств является множество натуральных чисел ℕ. его мощность принято обозначать символом ℵ₀ (алеф-нуль) или c₀. множества, эквивалентные ℕ, называются счетными. т.о. , мощность любого счетного множества равна ℵ₀

пусть S₁, S₂ - множества. отображением, или функцией f : S₁ → S₂ называется такое соответствие Γ_f⊂S₁×S₂, что для каждого x∈S₁ существует единственный элемент y∈S₂, удовлетворяющий условию (x,y)∈Γ_f. множество Γ_f называется "графиком функции f". значением функции f на элементе x∈S₁ называется тот единственный элемент y∈S₂, для которого (x,y)∈Γ_f. это обозначается так: y=f(x)

если f(x) = y, то y называется "образом элемента x", а x - "прообразом y"

функция f : S₁ → S₂ называется "вложением", или "инъекцией", или "инъективным отображением", если для разных x,x'∈S₁ их образы не равны: f(x)!=f(x')

функция f : S₁ → S₂ называется "наложением", или "сюръекцией", или "сюръективным отображением", если f(S₁)=S₂ ; иначе говоря, каждый y∈S₂ является образом какого-то элемента S₁

если функция f : S₁ → S₂ - одновременно наложение и вложение, то она называется "биекцией", или "биективным отображением", или "взааимно однозначным отображением"

упорядоченное множество

пусть на множестве S задано отношение ≲. это отношение называется отношением частичного порядка, если выполнены следующие аксиомы:

говорят, что на множестве Х задан порядок, если для ∀ x,y,z ∈ X выполняются следующие условия:

порядок называется линейным (полным) если ∀ x,y ∈ X либо x < y либо y < x

к примеру, порядок на ℂ - нелинеен (частичен)

два вполне упорядоченных множества называются изоморфными, если между ними есть биекция, сохраняющая порядок

a causal set is a set S together with the relation, ≤, such that
1. if x ≤ y and y ≤ z, then x ≤ z ∀x, y, z ∈ S (transitive),
2. if x ≤ y and y ≤ x, then x = y ∀x, y ∈ S (non-circular),
3. for any given x, z ∈ S, the set of elements {y | x ≤ y ≤ z} is finite (locally finite)

suppose for a moment that nature were represented by an algebra, A. we will start, then, simply with an unevaluated algebraic expression. consider for example

it seems that an algebra might well provide a notion of irreversible time. in the case of an algebra, an event is a calculation. taking our algebra A=ℝ, for example, an event is the evaluation of 6+3 to give 9, or the evaluation of 5·2 to give 10. addition and multiplication are examples of uninvertible binary operations. therefore, an event can be seen to be irreversible, it cannot ‘unhappen’. for example, if we are given only the output of 9, it is impossible to tell if 9 came from the inputs of 6+3, or 8+1, or 4+5, etc. time, then, is simply a sequence of calculations, and is clearly irreversible. the related notion of ‘now’ can be seen to be an entirely local concept within the causal set

лемма Цорна и теорема Цермело

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

Th Цермело: во всяком множестве можно ввести такой порядок, что любое его непустое подмножество будет обладать наименьшим в этом множестве элементом

лучше всего думать о лемме Цорна как о гарантии того, что алгоритмы могут работать столько, сколько необходимо, прежде чем их остановит какое-то препятствие (будь то "цепь без верхней границы" или "максимальный элемент"). т.о., любая финитная конструкция, построенная с помощью алгоритма (например, выбор базиса для конечномерного векторного пространства), имеет хорошие шансы распространиться и на бесконечную ситуацию с помощью аргумента леммы Цорна.

хороший способ понять, что мы делаем, таков: мы рассматриваем действительные числа как векторное пространство над полем рациональных числел, и мы пытаемся построить базис этого векторного пространства, когда каждое действительное число является рациональной линейной комбинацией чисел из базиса и ровно одним способом. тогда, если мы определим значения f как угодно для чисел из такого базиса и определим значения f очевидным образом для рациональных линейных комбинаций этих чисел, мы получим функцию ℝ→ℝ, которая линейна по рациональным числам и, следовательно, аддитивна

теперь: ℝ, рассматриваемое как векторное пространство над ℚ, заведомо бесконечномерно. на самом деле оно имеет несчетную размерность. "имеет несчетную размерность" - "не может быть натянуто на счетное множество векторов", поэтому по определению неверно, что оно имеет базис

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

итак, мы ищем базис ℝ над ℚ, и все, что нам нужно сделать, чтобы найти базис любого векторного пространства, это взять максимальное линейно независимое множество

но почему должно существовать максимальное линейно независимое множество? разве это не та самая трудность, с которой мы столкнулись ранее: мы могли продолжать выбирать все более и более рационально независимые действительные числа, но, казалось, мы никогда не достигали точки, в которой мы больше не могли продолжать

давайте прервем этот пример для более общего обсуждения леммы Цорна (и как ее использовать)

так как же в общем понять необходимость леммы Цорна и как построить подходящее частично упорядоченное множество, чтобы применить ее? как правило, при этом пытаются построить какую-то структуру (например, основу для векторного пространства или правильное упорядоченое множество). кажется, что естественный способ сделать это состоит в том, чтобы построить структуру поэтапно, но стадий слишком много, чтобы это работало напрямую. однако, как только появится представление о том, что такое "этап" и каков процесс построения, можно использовать лемму Цорна, чтобы гарантированно завершить работу: частично упорядоченный набор будет состоять из всех объектов, которые предположительно могут быть "этапами построения", и каждый из этих объектов будет меньше другого, если он предшествует другому в процессе построения. если полученный частичный порядок удовлетворяет условию цепи и если максимальный элемент должен быть структурой того типа, который пытаются построить, то доказательство на этом завершено

эквивалентность

часто придется прибегать к одному трюку: считать различные элементы какого-то множества, эквивалентные в некотором смысле, за один элемент. он будет элементом нового множества, которое называют фактор-множеством - множество классов эквивалентных элементов (классов эквивалентности). переход к фактор-множеству - распространенный способ "укрупнить" первоначальное множество - проигнорировать различие элементов по факторам, которые в данной задаче не играют роли. что за эквивалентность такая? неважно. но для того, чтобы деление на классы было однозначно и непротиворечиво, любое отношение эквивалентности (~) должно удовлетворять трем естественным требованиям:
1) рефлексивность ( x ~ x )
2) симметричность (если x ~ y , то и y ~ x )
3) транзитивность (если x ~ y и y ~ z , то и x ~ z )
три вышеупомянутых требования гарантируют, что классы эквивалентных элементов никогда не будут попарно пересекаться - вот в чем их смысл