Notacja konstruktora zestawów - Set-builder notation

W teorii zbiorów i jej zastosowaniach w logice , matematyce i informatyce , notacja konstruktora zbiorów jest notacją matematyczną opisującą zbiór przez wyliczenie jego elementów lub określenie właściwości , które muszą spełniać jego elementy .

Definiowanie zestawów właściwościami jest również znany jako ustawionej zrozumienia , ustawionej abstrakcji albo jako określenie zestawu za intencji .

Zestawy zdefiniowane przez wyliczenie

Zestaw można określić bezpośrednio wylicza wszystkie jego elementy, pomiędzy klamrami, jak w dwóch przykładach:

• ${\ Displaystyle \ {7,3,15,31\}}$ to zestaw zawierający cztery liczby 3, 7, 15 i 31 i nic więcej.
• ${\displaystyle \{a,c,b\}=\{a,b,c\}}$jest zbiorem zawierającym a , b i c , i nic więcej (nie ma porządku wśród elementów zbioru).

Jest to czasami nazywane „metodą dyżurów” określania zestawu.

Gdy pożądane jest oznaczenie zbioru zawierającego elementy z regularnego ciągu, można zastosować zapis elipsy , jak pokazano w następnych przykładach:

• ${\ Displaystyle \ {1,2,3, \ ldots, 100 \}}$ to zbiór liczb całkowitych od 1 do 100 włącznie.
• ${\ Displaystyle \ {1,2,3, \ ldots \}}$jest zbiorem liczb naturalnych .
• ${\displaystyle \{\ldots,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \}}$ to zbiór wszystkich liczb całkowitych.

Nie ma porządku wśród elementów zbioru (to wyjaśnia i potwierdza równość ostatniego przykładu), ale w notacji wielokropek używamy uporządkowanej sekwencji przed (lub po) wielokropku jako wygodnego nośnika notacji do wyjaśnienia, które elementy są w zestawie. Pokazanych jest kilka pierwszych elementów ciągu, następnie wielokropki wskazują, że dla kontynuowania ciągu należy zastosować najprostszą interpretację. Jeżeli na prawo od wielokropka nie pojawia się żadna wartość końcowa, ciąg jest uważany za nieograniczony.

Ogólnie oznacza zbiór wszystkich liczb naturalnych, takich jak . Inną notacją dla jest notacja nawiasowa . Subtelnym przypadkiem specjalnym jest , w którym jest równy zestawowi pustemu . Podobnie oznacza zbiór all for . ${\ Displaystyle \ {1, \ kropki, n \}}$${\displaystyle i}$${\displaystyle 1\leq i\leq n}$${\ Displaystyle \ {1, \ kropki, n \}}$${\displaystyle [n]}$${\displaystyle n=0}$${\ Displaystyle [0] = \ {1, \ kropki, 0 \}}$ ${\displaystyle \pusty zestaw}$${\ Displaystyle \ {a_ {1}, \ kropki, a_ {n} \}}$${\displaystyle a_{i}}$${\displaystyle 1\leq i\leq n}$

W każdym poprzednim przykładzie każdy zestaw jest opisany przez wyliczenie jego elementów. Nie wszystkie zbiory można opisać w ten sposób, a jeśli to możliwe, ich wyliczenie może być zbyt długie lub zbyt skomplikowane, aby było użyteczne. Dlatego wiele zbiorów jest zdefiniowanych przez właściwość charakteryzującą ich elementy. Ta charakterystyka może być wykonana nieformalnie przy użyciu ogólnej prozy, jak w poniższym przykładzie.

• ${\ Displaystyle \ {}$Adresy na ulicy Pine Street to zbiór wszystkich adresów na ulicy Pine Street.${\ Displaystyle \}}$

Jednak podejście prozatorskie może być niedokładne lub niejednoznaczne. Tak więc notacja konstruktora zestawów jest często używana z predykatem charakteryzującym elementy definiowanego zestawu, jak opisano w poniższej sekcji.

Zbiory zdefiniowane przez predykat

Notacja konstruktora zestawu może służyć do opisywania zestawu zdefiniowanego przez predykat , czyli formułę logiczną, której wynikiem jest true dla elementu zestawu i false w przeciwnym razie. W tej formie notacja set-builder składa się z trzech części: zmiennej, separatora dwukropka lub pionowej kreski oraz predykatu. Tak więc po lewej stronie separatora znajduje się zmienna, a po prawej reguła. Te trzy części znajdują się w nawiasach klamrowych:

${\ Displaystyle \ {x \ mid \ Phi (x) \}}$

lub

${\ Displaystyle \ {x: \ Phi (x) \}.}$

Pionowa kreska (lub dwukropek) jest separatorem, który można odczytać jako „ taki, że ”, „dla czego” lub „z właściwością to”. Mówi się, że formuła Φ( x ) jest regułą lub predykatem . Wszystkie wartości x, dla których predykat ma wartość (jest prawdą), należą do definiowanego zestawu. Wszystkie wartości x, dla których nie obowiązuje orzeczenie, nie należą do zbioru. Jest to więc zbiór wszystkich wartości x, które spełniają formułę Φ . Może to być zbiór pusty , jeśli żadna wartość x nie spełnia formuły. ${\ Displaystyle \ {x \ mid \ Phi (x) \}}$

Określanie domeny

Domena E może pojawić się po lewej stronie pionowego paska:

${\ Displaystyle \ {x \ w E \ mid \ Phi (x) \}}$

lub dołączając go do orzeczenia:

${\ Displaystyle \ {x \ mid x \ w E {\ tekst { i}} \ Phi (x) \} \ quad {\ tekst {lub}} \ quad \ {x \ mid x \ w E \ ziemi \ Phi (x)\}.}$

Symbol ∈ oznacza przynależność do zbioru , podczas gdy symbol oznacza operator logiczny „i”, znany jako koniunkcja logiczna . Ten zapis reprezentuje zbiór wszystkich wartości x, które należą do jakiegoś danego zbioru E, dla którego orzeczenie jest prawdziwe (patrz " Ustaw aksjomat istnienia " poniżej). Jeśli jest spójnikiem , to czasami zapisuje się go , używając przecinka zamiast symbolu . ${\displaystyle \land}$${\ Displaystyle \ Phi (x)}$${\ Displaystyle \ Phi _ {1} (x) \ ziemia \ Phi _ {2} (x)}$${\ Displaystyle \ {x \ w E \ mid \ Phi (x) \}}$${\ Displaystyle \ {x \ w E \ mid \ Phi _ {1} (x), \ Phi _ {2} (x) \}}$${\displaystyle \land}$

W ogóle, to nie jest dobry pomysł, aby rozważyć zestawy bez definiowania domenę, ponieważ byłoby to stanowią podzbiór o wszystkich możliwych rzeczy, które mogą występować , dla którego orzeczenie jest prawdą. Może to łatwo prowadzić do sprzeczności i paradoksów. Na przykład paradoks Russella pokazuje, że wyrażenie, chociaż pozornie dobrze uformowane jako wyrażenie budujące zbiór, nie może zdefiniować zbioru bez wywołania sprzeczności. ${\ Displaystyle \ {x ~ | ~ x \ nie \ w x \},}$

W przypadkach, gdy zbiór E jest jasny z kontekstu, może nie być wyraźnie określony. W literaturze często zdarza się, że autor podaje domenę z wyprzedzeniem, a następnie nie określa jej w notacji set-builder. Na przykład autor może powiedzieć coś takiego: „O ile nie zaznaczono inaczej, zmienne należy traktować jako liczby naturalne”. Choć w mniej formalnych kontekstach, w których można założyć dziedzinę, wzmianka pisemna jest często zbędna.

Przykłady

Poniższe przykłady ilustrują poszczególne zestawy zdefiniowane przez notację konstruktora zestawów za pomocą predykatów. W każdym przypadku domena jest podawana po lewej stronie pionowego paska, a reguła po prawej stronie.

• ${\ Displaystyle \ {x \ w \ mathbb {R} \ mid x> 0 \}}$jest zbiorem wszystkich ściśle dodatnich liczb rzeczywistych , które można zapisać w notacji interwałowej jako .${\displaystyle (0,\infty)}$
• ${\ Displaystyle \ {x \ w \ mathbb {R} \ mid | x | = 1 \}}$to zestaw . Ten zestaw można również zdefiniować jako ; zobacz równoważne predykaty dają równe zbiory poniżej.${\ Displaystyle \ {-1,1 \}}$${\ Displaystyle \ {x \ w \ mathbb {R} \ mid x ^ {2} = 1 \}}$
• Dla każdej liczby całkowitej m możemy zdefiniować . Jako przykład i .${\ Displaystyle G_ {m} = \ {x \ w \ mathbb {Z} \ mid x \ geq m \} = \ {m, m + 1, m + 2, \ ldots \}}$${\ Displaystyle G_ {3} = \ {x \ w \ mathbb {Z} \ mid x \ geq 3 \} = \ {3,4,5 \ ldots \}}$${\ Displaystyle G_ {-2} = \ {-2,-1,0, \ ldots \}}$
• ${\ Displaystyle \ {(x, y) \ w \ mathbb {R} \ razy \ mathbb {R} \ mid 0 <y < f (x) \}}$ jest zbiorem par liczb rzeczywistych takich, że y jest większe od 0 i mniejsze od f ( x ) dla danej funkcji f . Tutaj iloczyn kartezjański oznacza zbiór uporządkowanych par liczb rzeczywistych.${\ Displaystyle \ mathbb {R} \ razy \ mathbb {R}}$
• ${\ Displaystyle \ {n \ w \ mathbb {N} \ mid (\ istnieje k) [k \ w \ mathbb {N} \ ziemi n = 2 k] \}}$jest zbiorem wszystkich parzystych liczb naturalnych . Znak oznacza „i”, który jest znany jako logicznej koniunkcji . Znak ∃ oznacza „istnieje”, co jest znane jako kwantyfikacja egzystencjalna . Na przykład jest czytane jako „istnieje x takie, że P ( x )”.${\displaystyle \land}$${\displaystyle (\istnieje x)P(x)}$
• ${\ Displaystyle \ {n \ mid (\ istnieje k \ w \ mathbb {N}) [n = 2 k] \}}$jest wariantem notacyjnym dla tego samego zbioru parzystych liczb naturalnych. Nie jest konieczne określanie, że n jest liczbą naturalną, ponieważ wynika to ze wzoru po prawej stronie.
• ${\ Displaystyle \ {a \ w \ mathbb {R} \ mid (\ istnieje p \ w \ mathbb {Z}) (\ istnieje q \ w \ mathbb {Z}) [q \ nie = 0 \ ziemia aq = p ]\}}$jest zbiorem liczb wymiernych ; czyli liczby rzeczywiste, które można zapisać jako stosunek dwóch liczb całkowitych .

Bardziej złożone wyrażenia po lewej stronie notacji

Rozszerzenie notacji set-budowniczy zastępuje pojedynczej zmiennej X z wypowiedzi . Więc zamiast , możemy mieć co należy przeczytać ${\ Displaystyle \ {x \ mid \ Phi (x) \}}$${\ Displaystyle \ {\ psi (x) \ mid \ Phi (x) \}}$

${\ Displaystyle \ {\ psi (x) \ mid \ Phi (x) \} = \ {y \ mid \ istnieje (x), y = \ psi (x) {\ tekst {i}} \ Phi (x) \}}$.

Na przykład:

• ${\ Displaystyle \ {2n \ mid n \ w \ mathbb {N} \}}$, gdzie jest zbiorem wszystkich liczb naturalnych, jest zbiorem wszystkich parzystych liczb naturalnych.${\ Displaystyle \ mathbb {N}}$
• ${\ Displaystyle \ {p / q \ średni p, q \ w \ mathbb {Z}, q \ nie = 0 \}}$, gdzie jest zbiorem wszystkich liczb całkowitych, jest zbiorem wszystkich liczb wymiernych.${\ Displaystyle \ mathbb {Z}}$${\ Displaystyle \ mathbb {Q} ,}$
• ${\ Displaystyle \ {2t + 1 \ średni t \ w \ mathbb {Z} \}}$ jest zbiorem nieparzystych liczb całkowitych.
• ${\ Displaystyle \ {(t, 2t + 1) \ średni t \ w \ mathbb {Z} \}}$ tworzy zestaw par, gdzie każda para umieszcza liczbę całkowitą w korespondencji z nieparzystą liczbą całkowitą.

Gdy funkcje odwrotne mogą być wyraźnie określone, wyrażenie po lewej stronie można wyeliminować przez proste podstawienie. Rozważmy przykładowy zestaw . Dokonaj podstawienia , czyli , a następnie zastąp t w notacji konstruktora zbioru, aby znaleźć ${\ Displaystyle \ {2t + 1 \ średni t \ w \ mathbb {Z} \}}$${\displaystyle u=2t+1}$${\displaystyle t=(u-1)/2}$

${\ Displaystyle \ {2t + 1 \ mid t \ w \ mathbb {Z} \} = \ {u \ mid (u-1)/2 \ w \ mathbb {Z} \}}.$

Równoważne predykaty dają równe zbiory

Dwa zestawy są równe wtedy i tylko wtedy, gdy mają te same elementy. Zestawy zdefiniowane przez notację konstruktora zestawów są równe wtedy i tylko wtedy, gdy ich reguły konstruktora zestawów, w tym specyfikatory domeny, są równoważne. To jest

${\ Displaystyle \ {x \ w A \ mid P (x) \} = \ {x \ w B \ mid Q (x) \}}$

wtedy i tylko wtedy gdy

${\displaystyle (\forall t)[(t\in A\land P(t))\Leftrightarrow (t\inB\land Q(t))]}$.

Dlatego, aby udowodnić równość dwóch zbiorów zdefiniowanych przez notację konstruktora zbiorów, wystarczy udowodnić równoważność ich predykatów, w tym kwalifikatorów dziedzinowych.

Na przykład,

${\ Displaystyle \ {x \ w \ mathbb {R} \ mid x ^ {2} = 1 \} = \ {x \ w \ mathbb {Q} \ mid | x | = 1 \}}$

ponieważ dwa predykaty reguł są logicznie równoważne:

${\ Displaystyle (x \ w \ mathbb {R} \ ziemia x ^ {2} = 1) \ Leftrightarrow (x \ w \ mathbb {Q} \ ziemia | x | = 1).}$

Ta równoważność zachodzi, ponieważ dla dowolnej liczby rzeczywistej x mamy wtedy i tylko wtedy, gdy x jest liczbą wymierną z . W szczególności oba zestawy są równe zestawowi . ${\ Displaystyle x ^ {2} = 1}$${\ Displaystyle | x | = 1}$${\ Displaystyle \ {-1,1 \}}$

Ustaw aksjomat istnienia

W wielu formalnych teoriach mnogości , takich jak teoria mnogości Zermelo-Fraenkla , notacja konstruktora mnogości nie jest częścią formalnej składni teorii. Zamiast tego istnieje schemat aksjomatu istnienia zbioru , który stwierdza, że ​​jeśli E jest zbiorem, a Φ( x ) jest formułą w języku teorii mnogości, to istnieje zbiór Y, którego elementy są dokładnie elementami E, które spełniają Φ :

${\ Displaystyle (\ dla wszystkich E) (\ istnieje Y) (\ dla wszystkich x) [x \ w Y \ Leftrightarrow x \ w E \ ziemi \ Phi (x)].}$

Zbiór Y otrzymany z tego aksjomatu jest dokładnie zbiorem opisanym w notacji konstruktora zbiorów jako . ${\ Displaystyle \ {x \ w E \ mid \ Phi (x) \}}$

Paralele w językach programowania

Podobną notacją dostępną w wielu językach programowania (zwłaszcza w Pythonie i Haskell ) jest list składany , który łączy operacje mapowania i filtrowania na jednej lub kilku listach .

W Pythonie nawiasy klamrowe konstruktora zestawów są zastępowane nawiasami kwadratowymi, nawiasami lub nawiasami klamrowymi, co daje odpowiednio obiekty list, generator i set. Python używa składni opartej na języku angielskim. Haskell zastępuje klamry konstruktora zestawów nawiasami kwadratowymi i używa symboli, w tym standardowej pionowej kreski konstruktora zestawów.

To samo można osiągnąć w Scali, korzystając ze zrozumiałości sekwencji, gdzie słowo kluczowe „for” zwraca listę otrzymanych zmiennych za pomocą słowa kluczowego „yield”.

Rozważ te przykłady notacji konstruktora zestawów w niektórych językach programowania:

	Przykład 1	Przykład 2
Kreator zestawów	${\ Displaystyle \ {l \ | \ l \ w l \}}$	${\ Displaystyle \ {(k, x) \ | \ k \ w K \ klin x \ w X \ klin P (x) \}}$
Pyton	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Haskell	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]
Scala	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
C#	from l in L select l	from k in K from x in X where P(x) select (k,x)
SQL	SELECT l FROM L_set	SELECT k, x FROM K_set, X_set WHERE P(x)

Notacja konstruktora zestawów i notacja list składanych są przykładami bardziej ogólnej notacji znanej jako tłumaczenia monad , która pozwala na operacje podobne do map/filtrów na dowolnej monadzie z elementem zerowym .

Zobacz też

• Słowniczek teorii mnogości

Uwagi