индекс
инъекция - отображение f множества X в множество Y (f : X → Y), при котором
разные элементы множества X переводятся в разные элементы множества Y
"если два образа при отображении совпадают, то совпадают и прообразы"
иньекция - это "вложение"

сюрьекция - отображение f множества X на множество Y (f : X → Y ), при котором
каждый элемент множества Y является образом хотя бы одного элемента множества X
"все элементы Y являются образами элементов Х"
сюрьекция - это "покрытие"


  • intersection (durchschnitt)
  • union (vereinigung)
  • разность
  • симметрическая разность
  • дизъюнктное объединение
  • произведение и копроизведение
  • порядок на множестве
  • сигма-алегбры
  • топология
  • метрическое пространство

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

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

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

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


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

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

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

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

          Λⁿ(U) = { X ⊆ U | |X| = n }

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

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


    intersection, durchschnitt

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

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

        X ∩ Y = { z | z ∈ X /\ z ∈ Y } 

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

          X ∩ Y = { z ∈ K | P (z) } ∩ { z ∈ K | Q (z) } = { z ∈ K | P (z) /\ Q (z) } 

    пересечение множеств 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 = { z | z ∈ X  \/  z ∈ Y } 

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

        X ∪ Y  =  { z ∈ K | P (z) }  ∪  { z ∈ K | Q (z) } = { z ∈ K | P (z) \/ Q (z) } 

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

    * * *

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


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

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

        X \ Y = {x ∈ X | x ∉ Y } 

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

        X \ Y   =   {x ∈ K  |  P(x)} \ {x ∈ K  |  Q(x)}   =   {x ∈ K  |  P(x) /\ ¬Q(x)} 

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

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

        A ∩ B = A \ (A \ B) 

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

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

        (A \ B) \ C ⊆ A \ (B \ C) 
    левая часть состоит из тех x ∈ A, которые не лежат ни в B, ни в C, в то время как правая часть и, тем самым, содержится в A \ B. правая же часть состоит из тех x ∈ A, который не лежат в B \ C и, тем самым содержит A \ B

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

        x ∈ A  /\  x ∉ B  /\  x ∉ C, 
    в то время как правая часть – из тех x, для которых
        (x ∈ A  /\  x ∉ B) \/ (x ∈ A  /\  x ∈ C) 

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

        (A ∩ B) \ C = (A \ C) ∩ (B \ C)
        (A ∪ B) \ C = (A \ C) ∪ (B \ C) 

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

        A \ (B ∩ C) = (A \ B) ∪ (A \ C)
        A \ (B ∪ C) = (A \ B) ∩ (A \ C)

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

    * * *

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


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

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

       A Δ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) 

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

    G1: ассоциативность

    (X Δ Y) Δ Z = X Δ (Y Δ Z) 

    G2: существование нейтрального элемента

    A Δ ∅ = A = ∅ Δ A 

    G3: существование симметричного элемента

    A Δ B = ∅ = B Δ A 

    G4: коммутативность

    X Δ Y = Y Δ X 

    G5: инволютивность

    A Δ A = ∅ 

    D: дистрибутивность

    A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C) 

    именно свойства 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 = ∅. это определение распространяется на любое количество объединяемых множеств. так, запись

          A = X ∐ Y ∐ Z 
    означает, что A = X ∪ Y ∪ Z, причем X ∩ Y = ∅, X ∩ Z = ∅, Y ∩ Z = ∅


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


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

    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|

    листинг Haskell


    λ> 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

    конец листинга

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

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


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

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

        X × (Y ∪ Z) = (X × Y) ∪ (X × Z)
        (X ∪ Y) × Z = (X × Z) ∪ (Y × Z)
    
        X × (Y ∩ Z) = (X × Y) ∩ (X × Z)
        (X ∩ Y) × Z = (X × Z) ∩ (Y × Z)
    
        X × (Y \ Z) = (X × Y) \ (X × Z)
        (X \ Y) × Z = (X × Z) \ (Y × Z)
    
        X × (Y Δ Z) = (X × Y) Δ (X × Z)
        (X Δ Y) × Z = (X × Z) Δ (Y × Z)

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

          pr1 : A × B → A
         (a, b) → a
    и
         pr2 : A × B → B
         (a, b) → b 
    называемыми (каноническими) проекциями A × B на первый и на второй сомножитель, соответственно

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

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

    Def: прямым произведением двух множеств A и B называется множество A × B вместе с отображениями

        pr1 : A × B → A
    и
        pr2 : A × B → B
    называемыми каноническими проекциями A × B на первый и второй множитель, удовлетворяющее следующему универсальному свойству: для любого множества C и любых отображений
        f : C → A
    и 
        g : C → B 
    существует единственное отображение
        (f, g) : C → A × B 
    такое, что
        f = pr1 ◦ (f, g)
    и
        g = pr2 ◦ (f,g)

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

           π1 : C → A,
           π2 : C → B 
    
           ρ1 : D → A
           ρ2 : D → B 
    тогда существует единственная биекция φ : C → D такая, что πi = ρi ◦ φ

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

    * * *

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

        X1 ×... × Xn = (X1 ×... × Xn-1) × Xn 
    при этом на той же странице авторы говорят, что прямое произведение некоммутативно
        X × Y ≠ Y × X 
    оба эти утверждения не могут быть верными одновременно, так как статус коммутативности и ассоциативности для прямых произведений абсолютно одинаков:
  • с точностью до равенства ни ассоциативность, ни коммутативность не имеют место
  • с точностью до эквивалентности обе они имеют место
  • в действительности,

          (X × Y) × Z ≠ X × Y × Z ≠ X × (Y × Z)
    так как второе из них состоит из упорядоченных троек, в то время как первое и третье состоят из упорядоченных пар. в то же время с точностью до канонических изоморфизмов
          (X × Y) × Z ≈ X × Y × Z ≈ X × (Y × Z)
    но, конечно, в том же самом смысле X × Y ≈ Y × X


    множества, кольца и меры

    пусть задано множество S. множество всех подмножеств S обозначается 2^S и называется "булеан"

    пусть U ⊂ 2^S - некоторый набор подмножеств S

    U называется кольцом, если для любых A,B ∈ U

    принадлежaт U

    отображение µ : U → ℝ называется конечно-аддитивной мерой (аддитивной функцией множества или валюацией), если для любых A,B ∈ U выполняется:

            µ (A ∪ B) = µ A + µ B − µ (A ∩ B)


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

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

    1. x < y , y < z ⇒ x < z
    2. x < x
    3. x < y , y < x ⇒ x = y

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

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

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

    это эквивалент аксиомы выбора

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

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


    алегбра событий теорвера

    множество A, элементами которого являются подмножества множества Ω (не обязательно все) называется "алгеброй событий", если оно удовлетворяет следующим условиям:

    из свойств A1 и A2 следует, что пустое множество также содержится в множестве событий. из A3 следует, что вместе с любым конечным набором событий алгебра содержит их объединение

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

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

    множество X, элементами которого являются подмножества множества Ω (не обязательно все) называется "сигма-алгеброй" ("сигма-алгеброй событий"), если выполнены следующие условия:

    пример: пусть Ω = {♠, ♣, ♦, ♥} — пространство элементарных исходов. следующие наборы подмножеств Ω являются алгебрами:

  • A = {Ω, ∅} = {{♠, ♣, ♦, ♥}, {}} — тривиальная алгебра
  • A = {Ω, ∅, {♦}, Ω\{♦}} = {{♠, ♣, ♦, ♥}, {}, {♦}, {♠, ♣, ♥}}
  • сигма-алгебра

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

    пусть множество D есть множество подмножеств некого множества Ω. D называют сигма-алгеброй если:

    для любого множества можно построить тривиальную сигма-алгебру, которая содержит только {∅,Ω} и еще одну тривиальную сигма-алгебру, которая содержит все подмножества множества Ω

    алгебру, подобную сигма-алгебре, можно построить и на операции симметрической разности, заменив требование S3 на похожее, но с использованием Δ:

    листинг Хаскеля


         -- symmetry difference properties tests
         -- input : no
         -- output : tests results
    
    import Test.HUnit
    import Data.Set as D
    import Data.List as L
    
         -- create different sets
    e = D.empty
    x = D.fromList [1,2,3]
    y = D.fromList [1]
    z = D.fromList [2,3]
    
         -- create sigma- algebra
    algebra = [e, x, y, z]
    
         -- define operation
    symDiff :: Ord a => Set a → Set a → Set a
    symDiff x y =
      let a = D.difference x y
          b = D.difference y x
      in D.union a b
    
    
        -- test suit
    
        --  A Δ B = B Δ A
    test_symmetry_comm =
      assertBool
        "test for commutativity of symmetric difference " $
        L.all (==True) $
        L.map (\ a -> L.all (==True) $
                     L.map (\ b -> (symDiff a b) == (symDiff b a))
                     algebra
              )
        algebra
    
        -- A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C)
    test_symmetry_distr =
      assertBool
        "test for distributivity " $ L.all (== True) $
        L.map (\ set1 ->   L.all (== True) $
          L.map (\ set2 -> L.all (== True) $
            L.map (\ set3 ->
               (D.intersection set1 (symDiff set2 set3)) ==
               (symDiff (D.intersection set1 set2)
                        (D.intersection set1 set3))
                    ) algebra
                ) algebra
            ) algebra
    
        -- (X Δ Y) Δ Z = X Δ (Y Δ Z)
    test_symmetry_assoc =
      assertBool
        "test for associativity of symmetric difference: " $
        L.all (== True) $
          L.map (\ set1 ->   L.all (== True) $
            L.map (\ set2 -> L.all (== True) $
              L.map (\ set3 ->
                    (symDiff (symDiff set1 set2) set3) ==
                    (symDiff set1 (symDiff set2 set3))
                    ) algebra
                  ) algebra
                ) algebra
    
    
    test_closureness =
      let fAction = \ k -> L.all (flip L.elem algebra) $ L.map (symDiff k) algebra
      in  assertBool
            "test closureness of symmetric symmetry "
            (L.all (== True) $ L.map fAction algebra)
    
    
            -- run all tests
    
    main =
      runTestTT $ TestLabel "testing Sigma-algebra" $ TestList $ Prelude.map TestCase
        [ test_symmetry_assoc
        , test_symmetry_comm
        , test_symmetry_distr
        , test_closureness
        ]

    конец листинга


    топология

    семейство подмножеств Τ некоторого множества Ω называется "топологией Τ на Ω", если семейство обладает следующими свойствами:

    множество с заданной на нем топологией называется "топологическим пространством"

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

    метрическое пространство

    "метрическим пространством" называется пара {X,d}, где X — некоторое множество, и d(x1,x2) — неотрицательная невырожденная симметричная функция от пар элементов из X, удовлетворяющая неравенству треугольника. функция d называется "метрикой"

    любое метрическое пространство является топологией по определению. обратное - неверно

    любое метризируемое топологическое пространство - хаусдорфово


    индекс