Ställ in notation

${\displaystyle \{n\in \mathbb {Z} \mid (\exists k\in \mathbb {Z} )[n=2k]\))$

— Mängden av alla jämna tal ,
uttryckt i termer av mängdnotation.

I mängdteorin och dess tillämpningar på logik , matematik och datavetenskap är formen av en mängd en matematisk notation för att beskriva en mängd genom att lista dess element eller specificera egenskaper som elementen i mängden måste uppfylla [1] .

Uppsättningar definierade av uppräkning

En uppsättning kan beskrivas genom att lista alla dess element inuti lockiga hängslen, som i följande exempel:

$\{7,3,15,31\}$ är en uppsättning som innehåller fyra nummer: 3, 7, 15 och 31 och inget mer.
$\{a,c,b\}=\{a,b,c\}$ är en mängd som innehåller a , b och c och inget annat (ordningen på elementen i mängden beaktas inte, bara deras närvaro).

En sådan uppgift kallas ibland för "uppräkningsmetoden" för en viss uppsättning [2] .

Om man vill specificera en uppsättning som innehåller en vanlig sekvens, kan ellipsen användas , som visas i följande exempel:

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

Det finns ingen ordning i en mängd (detta förklarar varför likhet är sant i det sista exemplet), men när man använder en ellips används den ordnade sekvensen före (eller efter) ellipsen som ett bekvämt sätt att förklara vilka element som hör till mängden . De första elementen i sekvensen visas, och följande ellips föreslår att den enklaste tolkningen bör tillämpas för att fortsätta sekvensen. Om det inte finns något värde till höger om ellipsen, antas sekvensen vara oändlig.

Så betyder mängden av alla naturliga tal så att . En annan notation för set är parentesnotation . Ett litet undantag är fallet där är den tomma uppsättningen . På samma sätt betecknar uppsättningen av alla för . $\{1,\dots ,n\}$ $i$ $1\leqslant i\leqslant n$ $\{1,\dots ,n\}$ $[n]$ $n=0$ $[0]=\{1,\dots ,0\}$ $\emptyset$ $\{a_{1},\dots ,a_{n}\}$ $a_{i}$ $1\leqslant i\leqslant n$

I de givna exemplen beskrivs varje uppsättning genom att lista dess element. Inte alla uppsättningar kan beskrivas på detta sätt, eller även om de kan beskrivas på detta sätt, kan uppräkningen av deras element vara för lång eller för komplicerad för att använda denna metod. Av denna anledning definieras många uppsättningar av egenskaper som kännetecknar elementen i uppsättningen. Denna karakterisering kan ges informellt med hjälp av prosaiskt språk, som i följande exempel.

$\{$ husnummer längs Kosygin Avenue är uppsättningen av alla husnummer längs Kosygin Avenue. $\}$

Detta tillvägagångssätt kan dock leda till förlust av precision eller oklarhet. En lista med adresser längs Kosygin Avenue kan alltså betyda både en lista över hus och en lista över lägenheter i dessa hus.

Definiera mängder med predikat

Predikat kan användas för att skriva en uppsättning, snarare än en explicit uppräkning av element [3] . Denna form av setnotation har tre delar: en variabel, ett kolon eller vertikal streck som avgränsare och ett booleskt predikat . I det här fallet finns det en variabel till vänster om avgränsaren och en regel till höger om den. Dessa tre delar är inneslutna i lockiga hängslen:

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

eller

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

Avgränsaren kan läsas " så att " [4] , "för vilken" eller "med egenskap". Formeln Φ( x ) kallas en regel eller ett predikat . Alla värden för variabeln x för vilka predikatet är sant (det vill säga det är sant) tillhör den definierade mängden. Alla x -värden för vilka predikatet misslyckas tillhör inte uppsättningen. Således är mängden av alla x -värden för vilka formeln Φ [5] är sann . Det kan vara den tomma uppsättningen om inget x -värde uppfyller formeln. $\{x\mid \Phi (x)\}$

Omfattning

Omfattningen av E kan visas till vänster om den vertikala stapeln [6] :

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

eller det kan kombineras med ett predikat:

\{x\mid x\in E{\text{ och }}\Phi (x)\}\quad {\text{eller}}\quad \{x\mid x\in E\land \Phi (x)\}.

Symbolen ∈ betyder här att tillhöra mängden , medan symbolen betyder den logiska operatorn "AND", känd som konjunktion . Denna notation representerar uppsättningen av alla x -värden som tillhör någon uppsättning E för vilken predikatet utvärderas till sant , det vill säga sant (se avsnittet " Existensens axiom " nedan). Om är en konjunktion skrivs formen ibland som , med kommatecken istället för . $\landa$ $\Phi (x)$ $\Phi _{1}(x)\land \Phi _{2}(x)$ $\{x\in E\mid \Phi (x)\}$ ${\displaystyle \{x\in E\mid \Phi _{1}(x),\Phi _{2}(x)\))$ $\landa$

I allmänhet är det felaktigt att betrakta en uppsättning utan att definiera ett omfång, eftersom en domän kan representera en delmängd av alla möjliga objekt som kan existera för vilka predikatet är sant. Detta kan lätt leda till motsättningar och paradoxer. Russells paradox visar till exempel att uttrycket , även om det ser ut som ett välformat uttryck för att definiera en mängd, inte kan definiera en mängd utan att få en motsägelse [7] . $\{x~|~x\inte \in x\}$

I de fall där mängden E är tydligt definierad från sammanhanget kan den utelämnas. I litteraturen är det vanligt att författaren anger definitionsdomänen i förväg, och då anges inte domänen vid definition av mängder. Till exempel kan en författare skriva något i stil med: "Om inget annat anges tillhör variablerna naturliga tal."

Exempel

Följande exempel illustrerar konkreta uppsättningar definierade av predikat. I varje fall är omfattningen till vänster om den vertikala stapeln, medan regeln är till höger om den.

$\{x\in \mathbb {R} \mid x>0\}$ är mängden av alla strikt positiva reella tal , som kan skrivas i intervallnotation som . $(0,\infty )$
${\displaystyle \{x\in \mathbb {R} \mid |x|=1\))$ är en uppsättning . Denna uppsättning kan också definieras som ; se stycket " ekvivalenta predikat definierar lika mängder " nedan. $\{-1,1\}$ ${\displaystyle \{x\in \mathbb {R} \mid x^{2}=1\))$
För varje heltal m kan vi definiera . Som exempel: och . ${\displaystyle G_{m}=\{x\in \mathbb {Z} \mid x\geqslant m\}=\{m,m+1,m+2,\ldots \))$ ${\displaystyle G_{3}=\{x\in \mathbb {Z} \mid x\geqslant 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 betyder den kartesiska produkten uppsättningen av alla ordnade par av reella tal. $\mathbb {R} \times \mathbb {R}$
${\displaystyle \{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\))$ är mängden av alla jämna naturliga tal . Tecknet står för operationen "AND", som kallas konjunktion . Tecknet ∃ står för "exists", vilket är känt som den existentiella kvantifieraren . Så till exempel läses det som "det finns x så att P ( x ) ...". $\landa$ $(\exists x)P(x)$
${\displaystyle \{n\mid (\exists k\in \mathbb {N} )[n=2k]\))$ är ett annat sätt att skriva samma uppsättning av jämna naturliga tal. Det är inte nödvändigt att kräva att n är ett naturligt tal, eftersom detta följer av formeln på höger sida.
$\{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 dessa är reella tal som kan skrivas som en kvot av två heltal .

Mer komplexa uttryck på vänster sida

Tillägget set notation ersätter den enskilda variabeln x med uttrycket . Så istället kan vi ha , som kan läsas som $\{x\mid \Phi (x)\}$ $\{\Psi (x)\mid \Phi (x)\},$

\{\Psi (x)\mid \Phi (x)\}=\{y\mid \exists (x),y=\Psi (x){\text{ och }}\Phi (x) \}

Till exempel:

${\displaystyle \{2n\mid n\in \mathbb {N} \))$ , där är mängden av alla naturliga tal är mängden av alla jämna naturliga tal. $\mathbb {N}$
${\displaystyle \{p/q\mid p,q\in \mathbb {Z} ,q\not =0\))$ , där är mängden av alla heltal - detta är ℚ , mängden av alla rationella tal. $\mathbb {Z}$
${\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 består av ett heltal och dess motsvarande udda tal.

Om de inversa funktionerna kan specificeras explicit, kan uttrycket till vänster elimineras genom enkel substitution. Låt oss ta en uppsättning som exempel . Vi gör en substitution , varifrån vi får , sedan ersätter vi t i form av en uppsättning notation ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \))$ $u=2t+1$ $t=(u-1)/2$

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

Ekvivalenta predikat definierar lika mängder

Två uppsättningar är lika om och endast om de har samma element. Mängder som definieras av mängdnotationen är lika om och endast om deras konstruktionsregler är lika, inklusive indikationen av definitionsdomänen. Det är

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

om och endast om

(\forall t)[(t\i A\land P(t))\Leftrightarrow (t\in B\land Q(t))]

Därför, för att bevisa likheten mellan två mängder definierade av notationen av en mängd, är det tillräckligt att bevisa likvärdigheten för deras predikat, inklusive deras domäner.

Till exempel:

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

Eftersom de två predikatreglerna är logiskt likvärdiga:

(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 endast om x är rationell och . I synnerhet är båda uppsättningarna lika med uppsättningen . $x^{2}=1$ $|x|=1$ $\{-1,1\}$

Axiomet för existensen av en uppsättning

I många formella mängdteorier, såsom Zermelo-Fraenkel-systemet , är notationen av mängden inte en del av teorins formella syntax. Istället finns det ett axiomatiskt schema för förekomsten av en mängd , som säger att om E är en mängd och Φ( x ) är en mängdteoriformel, så finns det en mängd Y vars medlemmar är exakt elementen i E som uppfyller villkoret Φ :

(\forall E)(\exists Y)(\forall x)[x\in Y\Leftrightarrow x\in E\land \Phi (x)].

Mängden Y som erhålls från detta axiom är exakt den mängd som beskrivs i form av mängdnotation . $\{x\in E\mid \Phi (x)\}$

Paralleller i programmeringsspråk

En liknande notation tillgänglig i många programmeringsspråk (särskilt Python och Haskell ) är listomslutning , som kombinerar kart- och filteroperationerna en eller flera listor .

I Python ersätts anteckningsparenteser med hakparenteser, parenteser eller klammerparenteser för att definiera en lista, generator respektive uppsättning objekt. Python använder engelsk syntax. Haskell ersätter uppsättningsparenteser med hakparenteser och använder matematiska symboler, inklusive standardpipetecknet för uppsättningar.

Samma sak kan uppnås i Scala med hjälp av Sequence Comprehensions, där nyckelordet "for" returnerar en lista med variabler som erhållits med nyckelordet "yield" [8] .

Tänk på följande uppsättningsuppgifter i vissa programmeringsspråk:

	Exempel 1	Exempel 2
Ställ in notation	${\displaystyle \{l\ \|\ l\in L\))$	${\displaystyle \{(k,x)\ \|\ k\in K\wedge x\in X\wedge P(x)\))$
Pytonorm	{ l för l i L }	{( k , x ) för k i K för x i X om P ( x )}
Haskell	[ l \| l < -ls ]	[( k , x ) \| k <- ks , x <- xs , p x ]
Scala	för ( l <- L ) ger l	för ( k <- K ; x <- X om P ( x )) ger ( k , x )
C#	från l i L välj l	från k i K från x i X där P ( x ) välj ( k , x )
SQL	VÄLJ l FRÅN L_set	SELECT k , x FROM K_set , X_set WHERE P ( x )

Mängden notation och listinkludering är specialfall av den mer allmänna notationen som kallas monadgeneratorn . Denna notation tillåter operationer som map/filter på valfri noll C -monad .

Anteckningar

↑ Rosen, 2007 , sid. 111–112.
↑ Aufmann, Barker, Lockwood, 2007 , sid. 6.
↑ Cullinan, 2012 , sid. 44ff.
↑ Omfattande lista över uppsättningsteorisymboler . Math Vault (11 april 2020). Hämtad 20 augusti 2020. Arkiverad från originalet 18 augusti 2020.
↑ Weisstein, Eric W. Set . mathworld.wolfram.com . Hämtad 20 augusti 2020. Arkiverad från originalet 7 oktober 2020.
↑ Set-Builder Notation . mathsisfun.com . Hämtad 20 augusti 2020. Arkiverad från originalet 21 oktober 2020. (obestämd)
↑ Irvine, Deutsch, 2016 .
↑ Sekvensförståelser . Scala. Hämtad 6 augusti 2017. Arkiverad från originalet 18 april 2021. (obestämd)

Litteratur

Kenneth Rosen. Diskret matematik och dess tillämpningar . — 6:a. - New York, NY: McGraw-Hill, 2007. - S. 111-112. - ISBN 978-0-07-288008-3 .
Richard Aufmann, Vernon C. Barker, Joanne Lockwood. . - Brooks Cole, 2007. - P. 6 ..
Michael J. Cullinan. En övergång till matematik med bevis. - Jones & Bartlett, 2012. - s. 44ff.
Andrew David Irvine, Harry Deutsch. Russell's Paradox // Stanford Encyclopedia of Philosophy . — 2016.