Zápis stavitele - Set-builder notation

V teorii množin a její aplikace do logiky , matematiky a počítačové vědy , set-builder zápis je matematický zápis pro popis sady výčtem svých prvků , nebo uvádí vlastnosti, které jeho členové musí splňovat.

Definování sady vlastností je známý také jako set s porozuměním , set abstrakci nebo jako definující sadu v intension .

Sady definované výčtem

Sada může být popsán přímo výčtem všech jeho prvků mezi složenými závorkami, jako v následujících dvou příkladech:

• ${\ displaystyle \ {7,3,15,31 \}}$ je sada obsahující čtyři čísla 3, 7, 15 a 31 a nic jiného.
• ${\ Displaystyle \ {a, c, b \} = \ {a, b, c \}}$je množina obsahující a , b , ac , a nic jiného (mezi prvky množiny není žádné pořadí).

Někdy se tomu říká "metoda seznamu" pro specifikaci sady.

Když je požadováno označit množinu, která obsahuje prvky z pravidelné sekvence, lze použít notu s elipsami , jak ukazuje následující příklady:

• ${\ Displaystyle \ {1,2,3, \ ldots, 100 \}}$ je sada celých čísel mezi 1 a 100 včetně.
• ${\ displaystyle \ {1,2,3, \ ldots \}}$je množina přirozených čísel .
• ${\ Displaystyle \ {\ ldots, -2, -1,0,1,2, \ ldots \} = \ {0,1, -1,2, -2, \ ldots \}}$ je množina všech celých čísel.

Mezi prvky množiny neexistuje žádné pořadí (to vysvětluje a potvrzuje rovnost posledního příkladu), ale s notací elipsy používáme uspořádanou sekvenci před (nebo za) elipsou jako pohodlný notační prostředek pro vysvětlení, které prvky jsou v sadě. Je ukázáno prvních několik prvků sekvence, potom tři tečky ukazují, že pro pokračování sekvence by měla být použita nejjednodušší interpretace. Pokud by se napravo od elipsy neobjevila žádná ukončovací hodnota, je posloupnost považována za neomezenou.

Obecně označuje množinu všech přirozených čísel tak, že . Další notace pro je hranatá notace . Subtilní speciální případ je , ve kterém se rovná prázdné množině . Podobně označuje množinu všech pro . ${\ Displaystyle \ {1, \ tečky, n \}}$${\ displaystyle i}$${\ Displaystyle 1 \ leq i \ leq n}$${\ Displaystyle \ {1, \ tečky, n \}}$${\ displaystyle [n]}$${\ displaystyle n = 0}$${\ displaystyle [0] = \ {1, \ tečky, 0 \}}$ ${\ displaystyle \ emptyset}$${\ displaystyle \ {a_ {1}, \ dots, a_ {n} \}}$${\ displaystyle a_ {i}}$${\ Displaystyle 1 \ leq i \ leq n}$

V každém předchozím příkladu je každá sada popsána výčtem jejích prvků. Ne všechny sady lze popsat tímto způsobem, nebo pokud mohou, jejich výčet může být příliš dlouhý nebo příliš komplikovaný, než aby byl užitečný. Mnoho sad je proto definováno vlastností, která charakterizuje jejich prvky. Tuto charakterizaci lze provést neformálně pomocí obecné prózy, jako v následujícím příkladu.

• ${\ displaystyle \ {}$adresy na Pine Street je sada všech adres na Pine Street.${\ displaystyle \}}$

Prozaický přístup však může postrádat přesnost nebo může být nejednoznačný. Zápis tvůrce sady se tedy často používá s predikátem charakterizujícím prvky definované sady, jak je popsáno v následující části.

Sady definované predikátem

Zápis tvůrce sady lze použít k popisu sady, která je definována predikátem , tj. Logickým vzorcem, který je pro prvek sady vyhodnocen jako true , a v opačném případě false . V této podobě má zápis tvůrce sad tři části: proměnnou, oddělovač dvojtečky nebo svislé čáry a predikát. Vlevo od oddělovače je tedy proměnná a napravo od něj pravidlo. Tyto tři části jsou obsaženy v závorkách:

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

nebo

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

Svislá čára (nebo dvojtečka) je oddělovač, který lze číst jako „ takový “, „pro který“ nebo „s vlastností, která“. Říká se, že vzorec Φ ( x ) je pravidlo nebo predikát . Všechny hodnoty x, pro které predikát platí (je true), patří definované sadě. Všechny hodnoty x, pro které predikát neplatí, do sady nepatří. Je tedy množina všech hodnot x, které splňují vzorec Φ . Může to být prázdná množina , pokud vzorec nesplňuje žádná hodnota x . ${\ displaystyle \ {x \ mid \ Phi (x) \}}$

Zadání domény

V levé části svislého pruhu se může objevit doména E :

${\ displaystyle \ {x \ in E \ mid \ Phi (x) \},}$

nebo připojením k predikátu:

${\ Displaystyle \ {x \ mid x \ in E {\ text {and}} \ Phi (x) \} \ quad {\ text {or}} \ quad \ {x \ mid x \ in E \ land \ Phi (X)\}.}$

Symbol here zde označuje nastavené členství , zatímco symbol označuje logický operátor „a“, známý jako logická spojka . Tento zápis představuje množinu všech hodnot x, které patří k nějaké dané množině E, pro kterou je predikát pravdivý (viz „ Nastavit axiom existence existence “ níže). Pokud je to spojka , pak se někdy píše pomocí čárky místo symbolu . ${\ displaystyle \ land}$${\ displaystyle \ Phi (x)}$${\ Displaystyle \ Phi _ {1} (x) \ land \ Phi _ {2} (x)}$${\ displaystyle \ {x \ in E \ mid \ Phi (x) \}}$${\ Displaystyle \ {x \ in E \ mid \ Phi _ {1} (x), \ Phi _ {2} (x) \}}$${\ displaystyle \ land}$

Obecně platí, že to není dobrý nápad, aby zvážila soubory bez definování doménu, protože by to představovat podmnožinu ze všech možných věcí, které mohou existovat , pro něž predikát je pravda. To může snadno vést k rozporům a paradoxům. Například Russellův paradox ukazuje, že výraz, i když se zdánlivě dobře formoval jako výraz pro tvorbu sady, nemůže definovat množinu, aniž by vyvolal rozpor. ${\ Displaystyle \ {x ~ | ~ x \ not \ in x \},}$

V případech, kdy je množina E zřejmá z kontextu, nemusí být výslovně uvedena. V literatuře je běžné, že autor uvede doménu předem a pak ji nespecifikuje v notaci set-builderu. Autor může například říci něco jako: „Pokud není uvedeno jinak, proměnné je třeba považovat za přirozená čísla.“. Ačkoli v méně formálních kontextech, ve kterých lze doménu předpokládat, písemná zmínka je často zbytečná.

Příklady

Následující příklady ilustrují konkrétní sady definované zápisem tvůrce sady pomocí predikátů. V každém případě je doména uvedena na levé straně svislého pruhu, zatímco pravidlo je uvedeno na pravé straně.

• ${\ Displaystyle \ {x \ in \ mathbb {R} \ mid x> 0 \}}$je množina všech striktně kladných reálných čísel , která lze zapsat v intervalové notaci jako .${\ displaystyle (0, \ infty)}$
• ${\ Displaystyle \ {x \ in \ mathbb {R} \ mid | x | = 1 \}}$je sada . Tuto sadu lze také definovat jako ; viz ekvivalentní predikáty přinášejí stejné sady níže.${\ displaystyle \ {-1,1 \}}$${\ Displaystyle \ {x \ in \ mathbb {R} \ mid x^{2} = 1 \}}$
• Pro každé celé číslo m můžeme definovat . Jako příklad, a .${\ Displaystyle G_ {m} = \ {x \ in \ mathbb {Z} \ mid x \ geq m \} = \ {m, m+1, m+2, \ ldots \}}$${\ Displaystyle G_ {3} = \ {x \ in \ mathbb {Z} \ mid x \ geq 3 \} = \ {3,4,5, \ ldots \}}$${\ Displaystyle G _ {-2} = \ {-2, -1,0, \ ldots \}}$
• ${\ Displaystyle \ {(x, y) \ in \ mathbb {R} \ times \ mathbb {R} \ mid 0 <y <f (x) \}}$ je množina párů reálných čísel tak, že y je pro danou funkci f větší než 0 a menší než f ( x ) . Zde kartézský produkt označuje soubor spořádané páry reálných čísel. ${\ Displaystyle \ mathbb {R} \ times \ mathbb {R}}$
• ${\ Displaystyle \ {n \ in \ mathbb {N} \ mid (\ existuje k) [k \ in \ mathbb {N} \ land n = 2k] \}}$je množina všech sudých přirozených čísel . Značka znamená „a“, který je známý jako logické spojení . Znak stands znamená „existuje“, což je známé jako existenciální kvantifikace . Například je čten jako „existuje x takové, že P ( x )“.${\ displaystyle \ land}$${\ Displaystyle (\ existuje x) P (x)}$
• ${\ Displaystyle \ {n \ mid (\ existuje k \ in \ mathbb {N}) [n = 2k] \}}$je notační varianta pro stejnou sadu sudých přirozených čísel. Není nutné specifikovat, že n je přirozené číslo, jak to naznačuje vzorec vpravo.
• ${\ Displaystyle \ {a \ in \ mathbb {R} \ mid (\ existuje p \ in \ mathbb {Z}) (\ existuje q \ in \ mathbb {Z}) [q \ not = 0 \ land aq = p ] \}}$je množina racionálních čísel ; to znamená skutečná čísla, která lze zapsat jako poměr dvou celých čísel .

Složitější výrazy na levé straně notace

Rozšíření set-stavitele notace nahrazuje jednu proměnnou x s výrazem . Místo toho můžeme mít to, co bychom si měli přečíst ${\ displaystyle \ {x \ mid \ Phi (x) \}}$${\ displaystyle \ {\ Psi (x) \ mid \ Phi (x) \},}$

${\ Displaystyle \ {\ Psi (x) \ mid \ Phi (x) \} = \ {y \ mid \ existuje (x), y = \ Psi (x) {\ text {a}} \ Phi (x) \}}$.

Například:

• ${\ Displaystyle \ {2n \ mid n \ in \ mathbb {N} \}}$, kde je množina všech přirozených čísel, je množina všech sudých přirozených čísel.${\ displaystyle \ mathbb {N}}$
• ${\ Displaystyle \ {p/q \ mid p, q \ in \ mathbb {Z}, q \ not = 0 \}}$, kde je množina všech celých čísel, je množina všech racionálních čísel.${\ displaystyle \ mathbb {Z}}$${\ displaystyle \ mathbb {Q},}$
• ${\ Displaystyle \ {2t+1 \ mid t \ in \ mathbb {Z} \}}$ je množina lichých celých čísel.
• ${\ Displaystyle \ {(t, 2t+1) \ mid t \ in \ mathbb {Z} \}}$ vytvoří sadu párů, kde každý pár vloží celé číslo do korespondence s lichým celým číslem.

Pokud lze explicitně uvést inverzní funkce, výraz vlevo lze eliminovat jednoduchou substitucí. Zvažte sadu příkladů . Proveďte substituci , to znamená , pak nahraďte t v notaci nastaveného builderu, kterou chcete najít ${\ Displaystyle \ {2t+1 \ mid t \ in \ mathbb {Z} \}}$${\ displaystyle u = 2t+1}$${\ Displaystyle t = (u-1)/2}$

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

Ekvivalentní predikáty poskytují stejné množiny

Dvě sady jsou si rovny právě tehdy, pokud mají stejné prvky. Sady definované zápisem tvůrce sady jsou stejné, pouze pokud jsou jejich pravidla pro tvorbu sad, včetně specifikátorů domény, ekvivalentní. To je

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

kdyby a jen kdyby

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

Aby se tedy prokázala rovnost dvou sad definovaných zápisem tvůrce množin, stačí prokázat rovnocennost jejich predikátů, včetně kvalifikátorů domény.

Například,

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

protože dva predikáty pravidel jsou logicky ekvivalentní:

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

Tato ekvivalence platí, protože pro jakékoli skutečné číslo x máme právě tehdy, když x je racionální číslo s . Zejména jsou obě sady stejné jako množina . ${\ displaystyle x^{2} = 1}$${\ displaystyle | x | = 1}$${\ displaystyle \ {-1,1 \}}$

Nastavit axiom existence

V mnoha formálních teoriích množin , například v teorii množin Zermelo – Fraenkel , notace tvůrce množin není součástí formální syntaxe teorie. Místo toho existuje schéma axiomu množiny existence , které uvádí, že pokud E je množina a Φ ( x ) je vzorec v jazyce teorie množin, pak existuje množina Y, jejíž členy jsou přesně prvky E, které splňují Φ :

${\ Displaystyle (\ forall E) (\ existuje Y) (\ forall x) [x \ in Y \ Leftrightarrow x \ in E \ land \ Phi (x)].}$

Množina Y získaná z tohoto axiomu je přesně množina popsaná v notaci stavitele sady jako . ${\ displaystyle \ {x \ in E \ mid \ Phi (x) \}}$

Paralely v programovacích jazycích

Podobnou notací dostupnou v řadě programovacích jazyků (zejména Python a Haskell ) je porozumění seznamu , který kombinuje operace map a filtrů v jednom nebo více seznamech .

V Pythonu jsou závorky tvůrce sady nahrazeny hranatými závorkami, závorkami nebo složenými složenými závorkami, což dává seznam, generátor a množinové objekty. Python používá syntaxi založenou na angličtině. Haskell nahrazuje rovnátka tvůrce sady hranatými závorkami a používá symboly, včetně standardní svislé lišty tvůrce sad.

Totéž lze dosáhnout ve Scale pomocí Sequence Comprehensions, kde klíčové slovo "for" vrací seznam získaných proměnných pomocí klíčového slova "yield".

Zvažte tyto příklady zápisu set-builderu v některých programovacích jazycích:

	Příklad 1	Příklad 2
Set-builder	${\ Displaystyle \ {l \ | \ l \ v L \}}$	${\ Displaystyle \ {(k, x) \ | \ k \ in K \ wedge x \ in X \ wedge P (x) \}}$
Krajta	{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)

Zápis tvůrce sady a zápis porozumění seznamu jsou obě instance obecnějšího zápisu známého jako porozumění monad , což umožňuje operace podobné mapám/filtrům nad jakoukoli monadou s nulovým prvkem .

Viz také

• Glosář teorie množin

Poznámky