Лекции по упорядоченным множествам и универсальной алгебре. Гуров С.И. - 11 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

¤
F
M
M
M
M
F
M
X = {X
1
, . . . , X
n
} X
i
∈ U
i = 1, n
M = F
M
=
[
σ=(σ
1
, ..., σ
n
) ∈N
M
⊆ 2
n
n
\
j=1
X
σ
j
j
=
[
k ∈I
M
⊆{1, ..., 2
n
}
s
k
. (∗)
N
M
I
M
M n
2
n
{1, . . . , 2
n
} X
X
s 6= ∅
s ⊆ M s ∩ M = ∅ x ∈ s
x ∈ X
i
i = 1, . . . , n (∗)
F
1
F
2
F
1
= F
2
¤
r X Y
X r Y = X ∩ Y ⊕
X ⊕ Y = (X ∩ Y ) ∪ (X ∩ Y ) X ⊕ Y = (X ∪ Y ) r (X ∩ Y )
X r (Y r Z) = (X r Y ) ∪ (X ∩ Z) ;
X r (Y ∩ Z) = (X r Y ) ∪ (X r Z) ;
X r (Y ∪ Z) = (X r Y ) ∩ (X r Z) ;
X ⊕ (Y ⊕ Z) = (X ⊕ Y ) ⊕ Z ;
X ⊕ Y = Y ⊕ X ;
1.2. Àëãåáðû ìíîæåñòâ                                                               11


Äîêàçàòåëüñòâî ïï. 1 è 3) ëåãêî ïðîâîäÿòñÿ ïî èíäóêöèè, à 2) ñëåäóåò èç 1).          ¤

    Èç ëåììû ñëåäóåò, ÷òî ïîëó÷àåìàÿ â ñîîòâåòñòâèè ñ îïðåäåëåíèåì ñîâîêóïíîñòü ñî-
ñòàâëÿþùèõ íåêîòîðîé ñèñòåìû ìíîæåñòâ íå çàâèñèò îò ïîðÿäêà âûáîðà ýòèõ ìíîæåñòâ
è, òàêèì îáðàçîì, îïðåäåëåíèå íàáîðà ñîñòàâëÿþùèõ êîððåêòíî.
    Èòàê, âñå ñîñòàâëÿþùèå ñèñòåìû ìíîæåñòâ ñóòü êîíñòèòóåíòû. Âûðàæåíèå FM , çà-
äàþùåå íåêîòîðîå ïîäìíîæåñòâî M àëãåáðû ìíîæåñòâ âèäå îáúåäèíåíèÿ ðàçëè÷íûõ
ýëåìåíòàðíûõ ïåðåñå÷åíèé íàçûâàåòñÿ íîðìàëüíîé ôîðìîé Êàíòîðà äëÿ M íàä ñîîò-
âåòñòâóþùèìè ïîïàðíî ðàçëè÷íûìè ìíîæåñòâàìè. Äâå íîðìàëüíûå ôîðìû Êàíòîðà,
îòëè÷àþùèåñÿ ïîðÿäêîì îáúåäèíåíèÿ ýëåìåíòàðíûõ ïåðåñå÷åíèé, áóäåì ñ÷èòàòü ýêâèâà-
ëåíòíûìè, ïîñêîëüêó îíè, î÷åâèäíî, çàäàþò îäíî è òîæå ìíîæåñòâî.
Òåîðåìà 1.1 (Âåíí). Åñëè â àëãåáðå ìíîæåñòâ áóëåâî ðàâåíñòâî âûïîëíåíî äëÿ íåêî-
òîðîé íåçàâèñèìîé ñèñòåìû ïîäìíîæåñòâ, òî îíî ñïðàâåäëèâî äëÿ ëþáîé ñèñòåìû
ïîäìíîæåñòâ.
Äîêàçàòåëüñòâî. Ðàññìîòðèì íåïóñòîå ìíîæåñòâî M , ïðåäñòàâëåííîå íîðìàëüíîé ôîð-
ìîé Êàíòîðà FM íàä íåçàâèñèìîé ñèñòåìîé ìíîæåñòâ X = {X1 , . . . , Xn } ( Xi ∈ U ,
i = 1, n ):
                                 [        \n             [
                                              σ
               M = FM =                      Xj j =             sk .           (∗)
                            σ=(σ1 , ..., σn ) ∈NM ⊆ 2n j=1   k ∈IM ⊆{1, ..., 2n }

(çäåñü NM è IM  ñîîòâåòñòâóþùèå ìíîæåñòâó M ñîâîêóïíîñòè âåðøèí n-ìåðíîãî
åäèíè÷íîãî êóáà 2n è ìíîæåñòâà {1, . . . , 2n } íîìåðîâ ñîñòàâëÿþùèõ ñèñòåìû X ). Çà-
ìåòèì, ÷òî äëÿ çàâèñèìîé ñèñòåìû X óêàçàííîå ïðåäñòàâëåíèå ìîæåò îòñóòñòâîâàòü.
Òàêîå ïðåäñòàâëåíèå åäèíñòâåííî ñ ó÷¼òîì ââåä¼ííîé âûøå ýêâèâàëåíòíîñòè.
   Çàìåòèì, ÷òî åñëè s 6= ∅  ñîñòàâëÿþùàÿ êàêîé-ëèáî íåçàâèñèìîé ñèñòåìû ìíî-
æåñòâ, òî ëèáî s ⊆ M , ëèáî s ∩ M = ∅. Äàëåå, ñïðàâåäëèâîñòü x ∈ s ïîëíîñòüþ
îïðåäåëÿåò èñòèííîñòü x ∈ Xi äëÿ âñåõ i = 1, . . . , n. Â ñèëó ýòîãî ïðåäñòàâëåíèå (∗)
îñòà¼òñÿ ñïðàâåäëèâûì è åäèíñòâåííûì äëÿ ëþáîé ïðîèçâîëüíîé íåçàâèñèìîé ñèñòåìû
ìíîæåñòâ (äëÿ çàâèñèìîé ñèñòåìû ìîãóò ïîÿâèòüñÿ è äðóãèå ïðåäñòàâëåíèÿ). Ïîýòîìó
åñëè â íåçàâèñèìîé ñèñòåìå äâà áóëåâûõ âûðàæåíèÿ F1 è F2 èìåþò îäíè è òå æå ñî-
ñòàâëÿþùèå, òî ñïðàâåäëèâîñòü èëè íåñïðàâåäëèâîñòü ðàâåíñòâà F1 = F2 ñîõðàíèòñÿ è
â ëþáîé äðóãîé íåçàâèñèìîé ñèñòåìå.                                                  ¤

   Èç òåîðåìû ñëåäóåò, ÷òî ðàâåíñòâî â àëãåáðå ìíîæåñòâ äîñòàòî÷íî ïðîâåðèòü íà îäíîé
äèàãðàììå Ýéëåðà-Âåííà ñ íåçàâèñèìîé ñèñòåìîé ìíîæåñòâ. Èõ è íàçûâàþò ìíîæåñòâà-
ìè îáùåãî ïîëîæåíèÿ. Èíòåðïðåòàöèÿ æå âûðàæåíèé ëþáîé áóëåâîé àëãåáðû ñîîòíîøå-
íèÿìè ìíîæåñòâ îáîñíîâûâàåòñÿ ïðèâåä¼ííîé íèæå òåîðåìîé 1.3.
   Îáúåäèíåíèå, ïåðåñå÷åíèå è äîïîëíåíèå áóäåì ñ÷èòàòü îñíîâíûìè òåîðåòèêî-
ìíîæåñòâåííûìè îïåðàöèÿìè. Îáû÷íî ââîäÿò è ïðîèçâîäíûå îïåðàöèè íàä ìíî-
æåñòâàìè. Íàïðèìåð, îïåðàöèÿ r (ðàçíîñòè ) ìíîæåñòâ X è Y îïðåäåëÿåòñÿ
êàê X r Y       = X ∩ Y , à îïåðàöèÿ ⊕ (èõ ñèììåòðè÷åñêîé ðàçíîñòè ) êàê
X ⊕ Y = (X ∩ Y ) ∪ (X ∩ Y ). Ëåãêî ïîêàçûâàåòñÿ, ÷òî X ⊕ Y = (X ∪ Y ) r (X ∩ Y ). Â àë-
ãåáðå ìíîæåñòâ îáû÷íî èñïîëüçóþòñÿ ñëåäóþùèå ëåãêî ïðîâåðÿåìûå ñâîéñòâà óêàçàííûõ
ïðîèçâîäíûõ îïåðàöèé:

     X   r (Y r Z) = (X r Y ) ∪ (X ∩ Z) ;
     X   r (Y ∩ Z) = (X r Y ) ∪ (X r Z) ;
     X   r (Y ∪ Z) = (X r Y ) ∩ (X r Z) ;
     X   ⊕ (Y ⊕ Z) = (X ⊕ Y ) ⊕ Z ;
     X   ⊕Y = Y ⊕X;

Страницы