Algebra zbiorów

Ten artykuł dotyczy ogólnie algebraicznych właściwości operacji na zbiorach. Aby zapoznać się z algebrą logiczną zbiorów, zobacz Pole zbiorów .

W matematyce algebra zbiorów , której nie należy mylić z matematyczną strukturą algebry zbiorów i , definiuje właściwości i prawa zbiorów , teoretyczne operacje mnogościowe sumowania , przecinania i dopełniania oraz relacje równości zbioru zbioru włączenie . Zapewnia również systematyczne procedury oceny wyrażeń i wykonywania obliczeń, obejmujących te operacje i relacje.

Każdy zestaw zbiorów zamknięty w ramach operacji teorii mnogości tworzy algebrę Boole'a z operatorem łączenia będącym sumą , operatorem meet jest przecięcie , operatorem dopełnienia jest dopełnienie , dnem jest ∅ {\ displaystyle \ varnothing}, a górą jest ${\ displaystyle \ varnothing}$ rozważany wszechświat .

Podstawy

Algebra zbiorów jest teorią mnogości analogiem algebry liczb. Tak jak dodawanie i mnożenie arytmetyczne są asocjacyjne i przemienne , tak samo suma i przecięcie zestawów; tak jak relacja arytmetyczna „mniejsza lub równa” jest zwrotna , antysymetryczna i przechodnia , tak samo jest z relacją zbioru „podzbioru”.

Jest to algebra teoriomnogościowych operacji łączenia, przecinania i dopełniania oraz relacji równości i inkluzji. Aby zapoznać się z podstawowym wprowadzeniem do zbiorów, zobacz artykuł o zbiorach , pełniejszy opis zob. naiwna teoria mnogości , a pełne rygorystyczne traktowanie aksjomatyczne — zob . aksjomatyczna teoria mnogości .

Podstawowe własności algebry zbiorów

Operacje binarne sumy zbiorów ( $)$ i przecięcia ( $)$ wiele tożsamości _ Kilka z tych tożsamości lub „praw” ma dobrze ugruntowane nazwy.

Właściwość przemienna :

• ${\ Displaystyle A \ kubek B = B \ kubek A}$
• ${\ Displaystyle A \ czapka B = B \ czapka A}$

Właściwość asocjacyjna :

• ${\ Displaystyle (A \ kubek B) \ kubek C = A \ kubek (B \ kubek C)}$
• ${\ Displaystyle (A \ czapka B) \ czapka C = A \ czapka (B \ czapka C)}$

Własność rozdzielcza :

• ${\ Displaystyle A \ filiżanka (B \ czapka C) = (A \ filiżanka B) \ czapka (A \ filiżanka C)}$
• ${\ Displaystyle A \ czapka (B \ filiżanka C) = (A \ czapka B) \ filiżanka (A \ czapka C)}$

Łączenie i przecinanie zbiorów można postrzegać jako analogiczne do dodawania i mnożenia liczb. Podobnie jak dodawanie i mnożenie, operacje sumowania i przecinania są przemienne i asocjacyjne, a przecięcie rozdziela się na sumę. Jednak w przeciwieństwie do dodawania i mnożenia, suma rozdziela również na przecięcie.

Dwie dodatkowe pary właściwości obejmują specjalne zbiory zwane zbiorem pustym Ø i zbiorem wszechświata ${\ displaystyle U}$ ; razem z dopełnienia ( $. Można$ dopełnienie $jako$ zapisać jako , $A$ prim) Pusty zbiór nie ma członków, a zbiór wszechświata ma wszystkich możliwych członków (w określonym kontekście).

Tożsamość :

• ${\ Displaystyle A \ kubek \ varnothing = A}$
• ${\ Displaystyle A \ czapka U = A}$

Komplement :

• ${\ Displaystyle A \ kubek A ^ {C} = U}$
• ${\ Displaystyle A \ czapka A ^ {C} = \ varnothing}$

Wyrażenia tożsamości (wraz z wyrażeniami przemiennymi) mówią, że podobnie jak 0 i 1 dla dodawania i mnożenia, Ø i U są odpowiednio elementami tożsamości dla sumy i przecięcia.

W przeciwieństwie do dodawania i mnożenia suma i przecięcie nie mają elementów odwrotnych . Jednak prawa dopełniacza dają podstawowe właściwości nieco odwrotnej jednoargumentowej operacji uzupełniania zbioru.

Poprzednie pięć par wzorów — formuły przemienne, asocjacyjne, rozdzielcze, tożsamościowe i uzupełniające — obejmuje całą algebrę zbiorów w tym sensie, że można z nich wyprowadzić każde ważne twierdzenie w algebrze zbiorów.

Zauważ, że jeśli formuły dopełniacza są osłabione do reguły $^ {C}) ^ {C} = A}$ , to jest to dokładnie algebra zdaniowej logiki liniowej .

Zasada dualności

Zobacz także: Duality (teoria porządku)

Każda z podanych powyżej tożsamości jest jedną z pary tożsamości, z których każda może zostać przekształcona w drugą przez zamianę ∪ i ∩, a także Ø i U .

Są to przykłady niezwykle ważnej i potężnej własności algebry mnogości, a mianowicie zasady dualności dla zbiorów, która stwierdza, że ​​dla każdego prawdziwego twierdzenia o zbiorach, twierdzenie dualne otrzymane przez zamianę związków i przecięć, zamianę U i Ø oraz odwrócenie inkluzji jest również prawdą. O instrukcji mówi się, że jest samo-dualna, jeśli jest równa swojej własnej liczbie podwójnej.

Niektóre dodatkowe przepisy dotyczące związków i skrzyżowań

Poniższe twierdzenie określa sześć ważniejszych praw algebry mnogości, obejmujących sumy i przecięcia.

Twierdzenie 3 : Dla dowolnych podzbiorów A i B zbioru wszechświata U zachodzą następujące tożsamości:

prawa idempotentne :

• ${\ Displaystyle A \ kubek A = A}$
• ${\ Displaystyle A \ czapka A = A}$

prawa dominacji:

• ${\ Displaystyle A \ kubek U = U}$
• ${\ Displaystyle A \ czapka \ varnothing = \ varnothing}$

prawa absorpcji :

• ${\ Displaystyle A \ kubek (A \ czapka B) = A}$
• ${\ Displaystyle A \ czapka (A \ kubek B) = A}$

Jak wspomniano powyżej, każde z praw podanych w twierdzeniu 3 można wyprowadzić z pięciu podstawowych par praw podanych powyżej. Jako ilustrację poniżej podano dowód dla prawa idempotentnego dla unii.

Dowód:

${\ Displaystyle A \ kubek A}$	${\ Displaystyle = (A \ kubek A) \ czapka U}$	przez prawo tożsamości przecięcia
	${\ Displaystyle = (A \ kubek A) \ czapka (A \ kubek A ^ {C})}$	ustawą uzupełniającą dla unii
	${\ Displaystyle = A \ kubek (A \ czapka A ^ {C})}$	przez rozdzielne prawo unii nad przecięciem
	${\ Displaystyle = A \ kubek \ varnothing}$	przez prawo dopełnienia dla skrzyżowania
	${\ displaystyle = A}$	przez prawo tożsamości dla związku

Poniższy dowód ilustruje, że podwójność powyższego dowodu jest dowodem podwójności prawa idempotentnego dla sumy, a mianowicie prawa idempotentnego dla przecięcia.

Dowód:

${\ Displaystyle A \ czapka A}$	${\ Displaystyle = (A \ czapka A) \ kubek \ varnic}$	przez prawo tożsamości dla związku
	${\ Displaystyle = (A \ czapka A) \ kubek (A \ czapka A ^ {C})}$	przez prawo dopełnienia dla skrzyżowania
	${\ Displaystyle = A \ czapka (A \ kubek A ^ {C})}$	przez rozdzielne prawo przecięcia nad zjednoczeniem
	${\ Displaystyle = A \ czapka U}$	ustawą uzupełniającą dla unii
	${\ displaystyle = A}$	przez prawo tożsamości dla skrzyżowania

Przecięcie można wyrazić w postaci różnicy zbioru:

${\ Displaystyle A \ czapka B = A \ setminus (A \ setminus B)}$

Niektóre dodatkowe prawa dotyczące uzupełnień

Poniższe twierdzenie podaje pięć ważniejszych praw algebry mnogości, obejmujących dopełnienia.

Twierdzenie 4 : Niech A i B będą podzbiorami wszechświata U , wtedy:

Prawa De Morgana :

• ${\ Displaystyle (A \ kubek B) ^ {C} = A ^ {C} \ czapka B ^ {C}}$
• $\ Displaystyle (A \ czapka B) ^ {C} = A ^ {C} \ kubek B ^ {C}}$

podwójnego dopełnienia lub inwolucji :

• ${\ Displaystyle {(A ^ {C})} ^ {C} = A}$

uzupełniają prawa dla zbioru wszechświata i zbioru pustego:

• ${\ Displaystyle \ varnic ^ {C} = U}$
• ${\ Displaystyle U ^ {C} = \ varnothing}$

Zauważ, że prawo podwójnego dopełnienia jest samopodwójne.

Kolejne twierdzenie, również samodualne, mówi, że dopełnienie zbioru jest jedynym zbiorem, który spełnia prawa dopełnienia. Innymi słowy, komplementacja charakteryzuje się prawami dopełniacza.

Twierdzenie 5 : Niech A i B będą podzbiorami wszechświata U , wtedy:

wyjątkowość uzupełnień:

• $= \ varnothing}$ = ∅ $B$ to $B = A ^{C}}$

Algebra inkluzji

Następujące twierdzenie mówi, że inkluzja , czyli binarna relacja jednego zbioru będącego podzbiorem drugiego, jest porządkiem częściowym .

PROPOZYCJA 6 : Jeśli A , B i C są zbiorami, to zachodzi:

zwrotność :

• ${\ Displaystyle A \ subseteq A}$

antysymetria :

• ${\ Displaystyle A \ subseteq B}$ i ${\ Displaystyle B \ subseteq A}$ wtedy i tylko wtedy, gdy ${\ displaystyle A = b}$

przechodniość :

• Jeśli i ${\ Displaystyle B \ subseteq C}$ do $to$ ⊆ $A \ subseteq C$

Następujące twierdzenie mówi, że dla dowolnego zbioru S , zbiór potęgowy S , uporządkowany przez inkluzje , jest siatką ograniczoną , a zatem wraz z powyższymi prawami rozdzielności i dopełnienia pokazuje, że jest to algebra Boole'a .

Twierdzenie 7 : Jeżeli A , B i C są podzbiorami zbioru S , to zachodzi:

istnienie najmniejszego i największego elementu :

• ${\ Displaystyle \ varnothing \ subseteq A \ subseteq S}$

istnienie sprzężeń :

• ${\ Displaystyle A \ subseteq A \ kubek B}$
• ${\ Displaystyle A \ subseteq C}$ do b $\ Displaystyle B \ subseteq C}$$do {\ Displaystyle A \ kubek B \ subseteq C}$ to

istnienie spełnia :

• ${\ Displaystyle A \ czapka B \ subseteq A}$
• do ${\ Displaystyle C \ subseteq A}$$}$ { $C$ \

$,$ że stwierdzenie jest równoważne różnym innym stwierdzeniom obejmującym związki, przecięcia i

Twierdzenie 8 : Dla dowolnych dwóch zbiorów A i B następujące są równoważne:

• ${\ Displaystyle A \ subseteq B}$
• ${\ Displaystyle A \ czapka B = A}$
• ${\ Displaystyle A \ kubek B = B}$
• ${\ Displaystyle A \ setminus B = \ varnothing}$
• $} \ subseteq A ^ {C}}$

Powyższe twierdzenie pokazuje, że relacja włączenia zbioru może być scharakteryzowana przez jedną z operacji sumy zbioru lub przecięcia zbioru, co oznacza, że ​​pojęcie włączenia zbioru jest aksjomatycznie zbędne.

Algebra dopełnień względnych

Poniższe twierdzenie wymienia kilka tożsamości dotyczących względnych uzupełnień i różnic w teorii mnogości.

Twierdzenie 9 : Dla dowolnego wszechświata U i podzbiorów A , B i C z U zachodzą następujące tożsamości:

• $\ setminus (A \ czapka B) = (C \ setminus A) \ kubek (C \ setminus B)}$
• ${\ Displaystyle C \ setminus (A \ kubek B) = (C \ setminus A) \ czapka (C \ setminus B)$
• $\ setminus (B \ setminus A) = (A \ czapka C) \ kubek (C \ setminus B)$
• ${\ Displaystyle (B \ setminus A) \ czapka C = (B \ czapka C) \ setminus A = B \ czapka$
• $) \ kubek C = (B \ kubek C) \ setminus (A \ setminus C)}$
• ${\ Displaystyle (B \ setminus A) \ setminus C = B \ setminus (A \ kubek C)}$
• ${\ Displaystyle A \ setminus A = \ varnothing}$
• ${\ Displaystyle \ varnothing \ setminus A = \ varnothing}$
• ${\ Displaystyle A \ setminus \ varnothing = A}$
• $\ Displaystyle B \ setminus A = A ^ {C} \ czapka B}$
• ${\ Displaystyle (B \ setminus A) ^ {C} = A \ kubek B ^ {C}}$
• ${\ Displaystyle U \ setminus A = A ^ {C}}$
• ${\ Displaystyle A \ setminus U = \ varnothing}$

Zobacz też

• σ-algebra to algebra zbiorów, uzupełniona o przeliczalnie nieskończone operacje.
• Aksjomatyczna teoria mnogości
• Obraz (matematyka) #Właściwości
• Pole zestawów
• Lista ustalonych tożsamości i relacji
• Naiwna teoria mnogości
• Zestaw (matematyka)
• Przestrzeń topologiczna - podzbiór , $mocy$ , zamknięty względem dowolnego związku, skończonego przecięcia i zawierający $∅$$emptyset$ i ${\ displaystyle X}$ .

•   Stoll, Robert R.; Teoria mnogości i logika , Mineola, NY: Dover Publications (1979) ISBN 0-486-63829-4 . „Algebra zbiorów”, s. 16–23 .
•   Courant, Richard, Herbert Robbins, Ian Stewart, Czym jest matematyka?: Elementarne podejście do idei i metod , Oxford University Press US, 1996. ISBN 978-0-19-510519-3 . „SUPLEMENT DO ROZDZIAŁU II ALGEBRA ZBIORÓW” .

Linki zewnętrzne

• Operacje na zbiorach w ProvenMath