Algebra zbiorów - Algebra of sets

W matematyce , algebry zbiorów , nie należy mylić z matematycznej struktury z o algebry zbiorów , określa właściwości i praw zestawów , zestaw-teoretyczny operacje z unii , skrzyżowania i uzupełnianie oraz relacje z zestawu równości i zestaw włączenie . Zapewnia również systematyczne procedury oceny wyrażeń i wykonywania obliczeń, obejmujących te operacje i relacje.

Dowolny zbiór zbiorów zamknięty w ramach operacji mnogościowych tworzy algebrę Boole'a, w której operatorem join jest union , operatorem spełniającym jest przecięcie , operatorem dopełnienia jest dopełnienie zbioru , przy czym dolny i górny to rozpatrywany zbiór uniwersum . ${\displaystyle \varnic}$

Podstawy

Algebra zbiorów jest teoretycznym odpowiednikiem algebry liczb. Podobnie jak arytmetyka dodawanie i mnożenie są asocjacyjne i przemienne , więc są ustawione Unia i skrzyżowania; tak jak relacja arytmetyczna „mniejszy lub równy” jest zwrotna , antysymetryczna i przechodnia , tak samo jest relacja zbioru „podzbioru”.

Jest to algebra mnogościowych operacji sumy, przecięcia i dopełnienia oraz relacji równości i włączenia. Przez wprowadzenie do podstawowych zestawów patrz artykuł o zestawach , dla pełniejszego uwagę zobaczyć naiwnej teorii mnogości , a dla pełnego rygorystycznej aksjomatyczną leczenia zobaczyć aksjomatycznej teorii .

Podstawowe własności algebry zbiorów

Te binarne operacje zestawu Unii ( ) i przecięcie ( ) spełniają wiele tożsamości . Kilka z tych tożsamości lub „praw” ma dobrze ugruntowane nazwy. ${\ Displaystyle \ filiżanka}$${\ Displaystyle \ czapka}$

Własność przemienności :

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

Własność asocjacyjna :

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

Własność dystrybucyjna :

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

Połączenie i przecięcie zbiorów może być postrzegane jako analogiczne do dodawania i mnożenia liczb. Podobnie jak dodawanie i mnożenie, operacje sumy i przecięcia są przemienne i skojarzone, a przecięcie rozkłada się na sumę. Jednak w przeciwieństwie do dodawania i mnożenia, suma rozkłada się również na przecięcie.

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

Tożsamość :

• ${\ Displaystyle A \ filiżanka \ varnothing = A}$
• ${\ Displaystyle A \ czapka U = A}$

Komplement :

• ${\ Displaystyle A \ filiżanka A ^ {C} = U}$
• ${\ Displaystyle A \ czapka A ^ {C} = \ varnothing}$

Wyrażenia tożsamościowe (wraz z wyrażeniami przemiennymi) mówią, że podobnie jak 0 i 1 dla dodawania i mnożenia, Ø i U są elementami tożsamości odpowiednio 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łnień dają podstawowe własności nieco odwrotnej operacji jednoargumentowej komplementacji zbioru.

Poprzednie pięć par formuł — przemienna, asocjacyjna, rozdzielcza, identyczna i dopełniająca — obejmuje całą algebrę zbiorów w tym sensie, że można z nich wyprowadzić każde ważne zdanie w algebrze zbiorów.

Zauważ, że jeśli formuły z dopełnieniami są osłabione do reguły , to jest to dokładnie algebra liniowej logiki zdań . ${\ Displaystyle (A ^ {C}) ^ {C} = A}$

Zasada dualności

Każda z wymienionych powyżej tożsamości jest jedną z dwóch tożsamości, tak że każdą z nich można przekształcić w drugą, zamieniając ∪ i ∩, a także Ø i U .

Są to przykłady niezwykle ważnej i potężnej własności algebry zbiorów, a mianowicie zasady dualności dla zbiorów, która głosi, że dla każdego prawdziwego twierdzenia o zbiorach, twierdzenie dualne uzyskane przez zamianę sum i przecięć, zamianę U i Ø oraz odwrócenie wtrąceń jest również prawdziwe. O stwierdzeniu mówi się , że jest samodualne, jeśli jest równe własnemu dualizmowi.

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

Poniższa propozycja przedstawia sześć ważniejszych praw algebry zbiorów, obejmujących sumy i przecięcia.

TEZA 3 : W przypadku dowolnych podzbiorów A i B zbioru uniwersum U , zachodzą następujące tożsamości:

idempotentne prawa:

• ${\ Displaystyle A \ filiżanka A = A}$
• ${\ Displaystyle A \ czapka A = A}$

prawa dominacji:

• ${\ Displaystyle A \ filiżanka U = U}$
• ${\displaystyle A\cap \varnic =\varnic}$

prawa absorpcji :

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

Jak zauważono 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 na idempotentne prawo dla związku.

Dowód:

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

Poniższy dowód ilustruje, że dualność powyższego dowodu jest dowodem dualnym prawa idempotentnego dla unii, czyli prawa idempotentnego dla przecięcia.

Dowód:

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

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

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

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

Poniższa propozycja przedstawia pięć ważniejszych praw algebry zbiorów, obejmujących dopełnienia.

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

Prawa de Morgana :

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

podwójne uzupełnienie lub prawo inwolucji :

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

prawa dopełnienia dla zbioru wszechświata i zbioru pustego:

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

Zauważ, że prawo podwójnego dopełnienia jest samo-dualne.

Następne twierdzenie, które jest również samodwoiste, mówi, że dopełnienie zbioru jest jedynym zbiorem, który spełnia prawa dopełnienia. Innymi słowy, komplementacja charakteryzuje się prawami komplementarności.

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

wyjątkowość dopełnień:

• Jeśli , i , to${\ Displaystyle A \ filiżanka B = U}$${\displaystyle A\cap B=\varnothing}$${\ Displaystyle B = A ^ {C}}$

Algebra inkluzji

Poniższa propozycja mówi, że inkluzja , czyli relacja binarna jednego zbioru będącego podzbiorem drugiego, jest porządkiem częściowym .

PROPOZYCJA 6 : Jeśli ustawione są A , B i C, to obowiązuje następująca zasada:

refleksyjność :

• ${\displaystyle A\subseteq A}$

antysymetria :

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

przechodniość :

• Jeśli i , to${\displaystyle A\subseteq B}$${\displaystyle B\subseteq C}$${\ Displaystyle A \ podzbiór C}$

Poniższa propozycja twierdzi, że dla dowolnego zbioru S , w zestawie zasilania z S na zlecenie włączenia, jest ograniczonym kraty , a więc wraz z rozdzielczych i uzupełnienie powyższych przepisów, pokazują, że jest to Boole'a .

TEZA 7 : Jeżeli A , B i C są podzbiorami zbioru S, to obowiązuje następująca zasada:

istnienie najmniejszego elementu i największego elementu :

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

istnienie złączeń :

• ${\ Displaystyle A \ podseteq A \ filiżanka B}$
• Jeśli i , to${\ Displaystyle A \ podzbiór C}$${\displaystyle B\subseteq C}$${\ Displaystyle A \ filiżanka B \ podseteq C}$

istnienie spotkań :

• ${\ Displaystyle A \ czapka B \ podseteq A}$
• Jeśli i , to${\displaystyle C\podseteq A}$${\displaystyle C\subseteq B}$${\ Displaystyle C \ podseteq A \ czapka B}$

Poniższa propozycja mówi, że zdanie jest równoważne z różnymi innymi zdaniami zawierającymi sumy, przecięcia i uzupełnienia. ${\displaystyle A\subseteq B}$

TEZA 8 : Dla dowolnych dwóch zestawów A i B poniższe są równoważne:

• ${\displaystyle A\subseteq B}$
• ${\ Displaystyle A \ czapka B = A}$
• ${\ Displaystyle A \ filiżanka B = B}$
• ${\displaystyle A\setminus B=\varnothing}$
• ${\ Displaystyle B ^ {C} \ podseteq A ^ {C}}$

Z powyższej propozycji wynika, że ​​relację włączenia zbiorów można scharakteryzować za pomocą jednej z operacji sumy zbiorów lub przecięcia zbiorów, co oznacza, że ​​pojęcie włączenia zbiorów jest aksjomatycznie zbędne.

Algebra dopełnień względnych

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

PROPOZYCJA 9 : Dla każdego uniwersum U i podzbiory A , B i C o U następujące tożsamości posiadać:

• ${\ Displaystyle C \ setminus (A \ czapka B) = (C \ setminus A) \ filiżanka (C \ setminus B)}$
• ${\ Displaystyle C \ setminus (A \ filiżanka B) = (C \ setminus A) \ czapka (C \ setminus B)}$
• ${\ Displaystyle C \ setminus (B \ setminus A) = (A \ czapka C) \ filiżanka (C \ setminus B)}$
• ${\ Displaystyle (B \ setminus A) \ czapka C = (B \ czapka C) \ setminus A = B \ czapka (C \ setminus A)}$
• ${\ Displaystyle (B \ setminus A) \ filiżanka C = (B \ filiżanka C) \ setminus (A \ setminus C)}$
• ${\ Displaystyle (B \ setminus A) \ setminus C = B \ setminus (A \ filiżanka C)}$
• ${\displaystyle A\setminus A=\varnothing}$
• ${\displaystyle \varnic \setminus A=\varnic}$
• ${\ Displaystyle A \ setminus \ varnothing = A}$
• ${\ Displaystyle B \ setminus A = A ^ {C} \ czapka B}$
• ${\ Displaystyle (B \ setminus A) ^ {C} = A \ filiżanka B ^ {C}}$
• ${\ Displaystyle U \ setminus A = A ^ {C}}$
• ${\displaystyle A\setminus U=\varnothing}$

Zobacz też

• σ-algebra jest algebrą zbiorów, uzupełnioną tak, aby zawierała 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 , zbiór potęgowy , domknięty względem sumy arbitralnej, przecięcie skończone i zawierające i .${\ Displaystyle \ wp (X)}$${\ Displaystyle X}$${\displaystyle \pusty zestaw}$${\ Displaystyle X}$

Bibliografia

• 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, Co to jest matematyka?: Elementary Approach to Ideas and Methods , Oxford University Press US, 1996. ISBN  978-0-19-510519-3 . „SUPLEMENT DO ROZDZIAŁU II ALGEBRA ZBIORÓW” .

Zewnętrzne linki

• Operacje na zbiorach w ProvenMath