Set -builder notation - Set-builder notation

I uppsättningsteori och dess tillämpningar på logik , matematik och datavetenskap är set-builder-notation en matematisk notation för att beskriva en uppsättning genom att räkna upp dess element eller ange de egenskaper som dess medlemmar måste uppfylla.

Att definiera uppsättningar med egenskaper är också känt som uppsättningsförståelse , uppsättningsabstraktion eller som att definiera en uppsättnings avsikt .

Uppsättningar definierade genom uppräkning

En uppsättning kan beskrivas direkt genom att räkna upp alla dess element mellan lockiga parenteser, som i följande två exempel:

• ${\displaystyle \{7,3,15,31\}}$ är uppsättningen som innehåller de fyra siffrorna 3, 7, 15 och 31, och inget annat.
• ${\displaystyle \{a,c,b\}=\{a,b,c\}}$är uppsättningen som innehåller a , b och c , och ingenting annat (det finns ingen ordning bland elementen i en uppsättning).

Detta kallas ibland "roster -metoden" för att specificera en uppsättning.

När det är önskvärt att beteckna en uppsättning som innehåller element från en vanlig sekvens, kan en ellipsnotation användas, såsom visas i följande exempel:

• ${\displaystyle \{1,2,3,\ldots ,100\}}$ är uppsättningen heltal mellan 1 och 100 inklusive.
• ${\displaystyle \{1,2,3,\ldots \}}$är uppsättningen naturliga tal .
• ${\displaystyle \{\ldots ,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \}}$ är uppsättningen av alla heltal.

Det finns ingen ordning bland elementen i en uppsättning (detta förklarar och validerar likheten i det sista exemplet), men med ellipsnotationen använder vi en ordnad sekvens före (eller efter) ellipsen som ett bekvämt notationsmedel för att förklara vilka element finns i en uppsättning. De första elementen i sekvensen visas, sedan indikerar ellipserna att den enklaste tolkningen bör tillämpas för att fortsätta sekvensen. Om inget avslutningsvärde visas till höger om ellipserna anses sekvensen vara obegränsad.

I allmänhet betecknar uppsättningen av alla naturliga tal så att . En annan notation för är parentesnotationen . Ett subtilt specialfall är , i vilket är lika med den tomma uppsättningen . På samma sätt betecknar uppsättningen alla för . ${\displaystyle \{1,\dots ,n\}}$${\displaystyle i}$${\displaystyle 1\leq i\leq n}$${\displaystyle \{1,\dots ,n\}}$${\displaystyle [n]}$${\displaystyle n=0}$${\displaystyle [0]=\{1,\dots ,0\}}$ ${\displaystyle \emptyset }$${\displaystyle \{a_{1},\dots ,a_{n}\}}$${\displaystyle a_{i}}$${\displaystyle 1\leq i\leq n}$

I varje föregående exempel beskrivs varje uppsättning genom att räkna upp dess element. Inte alla uppsättningar kan beskrivas på detta sätt, eller om de kan kan deras uppräkning vara för lång eller för komplicerad för att vara användbar. Därför definieras många uppsättningar av en egenskap som kännetecknar deras element. Denna karakterisering kan göras informellt med allmän prosa, som i följande exempel.

• ${\displaystyle \{}$adresser på Pine Street är uppsättningen av alla adresser på Pine Street.${\displaystyle \}}$

Prosa -metoden kan dock sakna noggrannhet eller vara tvetydig. Således används set-builder-notation ofta med ett predikat som kännetecknar elementen i uppsättningen som definieras, såsom beskrivs i följande avsnitt.

Uppsättningar definierade av ett predikat

Set-builder-notation kan användas för att beskriva en uppsättning som definieras av ett predikat , det vill säga en logisk formel som utvärderas till true för ett element i uppsättningen och falskt annars. I denna form har set-builder-notationen tre delar: en variabel, ett kolon eller vertikal stapelavskiljare och ett predikat. Således finns det en variabel till vänster om separatorn och en regel till höger om den. Dessa tre delar finns i lockiga parenteser:

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

eller

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

Den vertikala stapeln (eller kolon) är en separator som kan läsas som " sådan ", "för vilken" eller "med egenskapen som". Formeln Φ ( x ) sägs vara regel eller predikat . Alla värden på x för vilka predikatet håller (är sant) tillhör den uppsättning som definieras. Alla värden för x som predikatet inte håller tillhör inte uppsättningen. Således är uppsättningen av alla värden för x som uppfyller formeln Φ . Det kan vara den tomma uppsättningen om inget värde av x uppfyller formeln. ${\displaystyle \{x\mid \Phi (x)\}}$

Ange domänen

En domän E kan visas till vänster om det vertikala fältet:

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

eller genom att ansluta den till predikatet:

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

Symbolen den här anger angivet medlemskap , medan symbolen betecknar den logiska "och" -operatorn, känd som logisk konjunktion . Denna notation representerar mängden av alla värden för x som tillhör en given uppsättning E för vilken predikatet är sant (se " Ange existensaxiom " nedan). Om är en konjunktion , skrivs den ibland med hjälp av ett komma istället för symbolen . ${\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 }$

I allmänhet är det inte en bra idé att överväga uppsättningar utan att definiera en domän, eftersom detta skulle representera delmängden av alla möjliga saker som kan finnas för vilka predikatet är sant. Detta kan lätt leda till motsättningar och paradoxer. Till exempel visar Russells paradox att uttrycket, även om det till synes är välformat som ett set -builder -uttryck, inte kan definiera en uppsättning utan att skapa en motsättning. ${\displaystyle \{x~|~x\not \in x\},}$

I de fall uppsättningen E är tydlig från sitt sammanhang kanske den inte uttryckligen anges. Det är vanligt i litteraturen att en författare anger domänen i förväg och sedan inte anger den i set-builder-notationen. Till exempel kan en författare säga något som: "Om inte annat anges ska variabler betraktas som naturliga tal.". Även i mindre formella sammanhang där domänen kan antas är ett skriftligt omnämnande ofta onödigt.

Exempel

Följande exempel illustrerar särskilda uppsättningar som definieras av set-builder-notation via predikat. I varje fall anges domänen på vänster sida av det vertikala fältet, medan regeln anges på höger sida.

• ${\displaystyle \{x\in \mathbb {R} \mid x>0\}}$är uppsättningen av alla strikt positiva reella tal , som kan skrivas i intervallnotation som .${\displaystyle (0,\infty )}$
• ${\displaystyle \{x\in \mathbb {R} \mid |x|=1\}}$är uppsättningen . Denna uppsättning kan också definieras som ; se ekvivalenta predikat ger lika uppsättningar nedan.${\displaystyle \{-1,1\}}$${\displaystyle \{x\in \mathbb {R} \mid x^{2}=1\}}$
• För varje heltal m kan vi definiera . Som ett exempel, och .${\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)\}}$ är mängden par av reella tal så att y är större än 0 och mindre än f ( x ), för en given funktion f . Här betecknar den kartesiska produkten uppsättningen ordnade par reella tal.${\displaystyle \mathbb {R} \times \mathbb {R} }$
• ${\displaystyle \{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}}$är uppsättningen av alla jämna naturliga tal . Den skylten står för "och", som är känd som logiskt samband . ∃ -tecknet står för "there exist", som kallas existentiell kvantifiering . Så läses till exempel som 'det finns ett x så att P ( x ) ".${\displaystyle \land }$${\displaystyle (\exists x)P(x)}$
• ${\displaystyle \{n\mid (\exists k\in \mathbb {N} )[n=2k]\}}$är en notativ variant för samma uppsättning jämna naturliga tal. Det är inte nödvändigt att ange att n är ett naturligt tal, eftersom detta antyds av formeln till höger.
• ${\displaystyle \{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}}$är mängden rationella tal ; det vill säga reella tal som kan skrivas som förhållandet mellan två heltal .

Mer komplexa uttryck på vänster sida av notationen

En förlängning av set-builder-notationen ersätter den enda variabeln x med ett uttryck . Så istället för kan vi ha det som bör läsas ${\displaystyle \{x\mid \Phi (x)\}}$${\displaystyle \{\Psi (x)\mid \Phi (x)\},}$

${\displaystyle \{\Psi (x)\mid \Phi (x)\}=\{y\mid \exists (x),y=\Psi (x){\text{ and }}\Phi (x)\}}$.

Till exempel:

• ${\displaystyle \{2n\mid n\in \mathbb {N} \}}$, där är uppsättningen av alla naturliga tal, är uppsättningen av alla jämna naturliga tal.${\displaystyle \mathbb {N} }$
• ${\displaystyle \{p/q\mid p,q\in \mathbb {Z} ,q\not =0\}}$, där är uppsättningen för alla heltal, är uppsättningen av alla rationella tal.${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {Q} ,}$
• ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$ är mängden udda heltal.
• ${\displaystyle \{(t,2t+1)\mid t\in \mathbb {Z} \}}$ skapar en uppsättning par, där varje par sätter ett heltal i korrespondens med ett udda heltal.

När inversa funktioner uttryckligen kan anges kan uttrycket till vänster elimineras genom enkel substitution. Tänk på exempeluppsättningen . Utför substitutionen , det vill säga , ersätt sedan t i set -buildernotationen för att hitta ${\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} \}.}$

Ekvivalenta predikat ger lika uppsättningar

Två uppsättningar är lika om och bara om de har samma element. Uppsättningar som definieras av set builder -notering är lika om och bara om deras uppsatta byggregler, inklusive domänspecifikatörerna, är likvärdiga. Det är

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

om och endast om

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

Därför är det tillräckligt för att bevisa likheten mellan två uppsättningar som definieras av set -buildernotation, det är tillräckligt att bevisa likvärdigheten för deras predikat, inklusive domänkvalificeringarna.

Till exempel,

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

eftersom de två regelns predikat är logiskt ekvivalenta:

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

Denna ekvivalens gäller eftersom vi för alla reella tal x har om och bara om x är ett rationellt tal med . I synnerhet är båda uppsättningarna lika med uppsättningen . ${\displaystyle x^{2}=1}$${\displaystyle |x|=1}$${\displaystyle \{-1,1\}}$

Ange existensaxiom

I många formella uppsättningsteorier, till exempel Zermelo - Fraenkel -uppsättningsteori , är uppsättningsbyggnation inte en del av teorins formella syntax. Istället finns ett axiomschema för uppsatt existens , som säger att om E är en uppsättning och Φ ( x ) är en formel på språket i uppsättningsteorin, så finns det en uppsättning Y vars medlemmar är exakt elementen i E som uppfyller Φ :

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

Uppsättningen Y erhållen från detta axiom är exakt den uppsättning som beskrivs i uppsättningsbyggarens notation som . ${\displaystyle \{x\in E\mid \Phi (x)\}}$

Paralleller i programmeringsspråk

En liknande notering tillgänglig på ett antal programmeringsspråk (särskilt Python och Haskell ) är listförståelsen , som kombinerar kart- och filteroperationer över en eller flera listor .

I Python ersätts set-builderns hängslen med hakparenteser, parenteser eller lockiga hängslen, vilket ger lista, generator respektive uppsatta objekt. Python använder en engelskbaserad syntax. Haskell ersätter set-builder-hängslen med fyrkantiga parenteser och använder symboler, inklusive den vanliga set-builder-vertikala stapeln.

Detsamma kan uppnås i Scala med hjälp av sekvensförståelser, där nyckelordet "för" returnerar en lista över de variabler som gavs med hjälp av nyckelordet "avkastning".

Tänk på dessa exempel på set-builder-notering i vissa programmeringsspråk:

	Exempel 1	Exempel 2
Set-builder	${\displaystyle \{l\ |\ l\in L\}}$	${\displaystyle \{(k,x)\ |\ k\in K\wedge x\in X\wedge P(x)\}}$
Pytonorm	{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)

Set-builder-notationen och listförståelse-notationen är båda förekomster av en mer allmän notation som kallas monadförståelser , vilket tillåter kart-/filterliknande operationer över alla monader med ett nollelement .

Se även

• Ordlista med uppsättningsteori

Anteckningar