Indstil notation

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

— Mættet af alle lige tal ,
udtrykt i form af sætnotation.

I mængdeteori og dens anvendelser til logik , matematik og datalogi er formen af et sæt en matematisk notation til at beskrive et sæt ved at angive dets elementer eller specificere egenskaber, som elementerne i sættet skal opfylde [1] .

Sæt defineret ved opregning

Et sæt kan beskrives ved at angive alle dets elementer inden i krøllede seler, som i følgende eksempler:

$\{7,3,15,31\}$ er et sæt med fire tal: 3, 7, 15 og 31 og intet mere.
$\{a,c,b\}=\{a,b,c\}$ er et sæt, der indeholder a , b og c og intet andet (rækkefølgen af elementerne i sættet tages ikke i betragtning, kun deres tilstedeværelse).

En sådan opgave kaldes undertiden "optællingsmetoden" for et bestemt sæt [2] .

Hvis man ønsker at specificere et sæt, der indeholder en regulær sekvens, kan ellipsen bruges , som vist i følgende eksempler:

$\{1,2,3,\ldots ,100\}$ er sættet af heltal mellem 1 og 100 inklusive.
$\{1,2,3,\ldots\}$ er mængden af alle naturlige tal .
${\displaystyle \{\ldots ,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \))$ er mængden af alle heltal.

Der er ingen rækkefølge i et sæt (dette forklarer, hvorfor lighed er sandt i det sidste eksempel), men når man bruger en ellipse, bruges den ordnede sekvens før (eller efter) ellipsen som en bekvem måde at forklare, hvilke elementer der hører til mængden . De første par elementer i sekvensen er vist, og den følgende ellipse antyder, at den enkleste fortolkning skal anvendes for at fortsætte sekvensen. Hvis der ikke er nogen værdi til højre for ellipsen, antages sekvensen at være uendelig.

Så betyder mængden af alle naturlige tal sådan, at . En anden notation for sæt er parentesnotation . En lille undtagelse er det tilfælde , hvor det tomme sæt er . På samme måde betegner sættet af alle for . $\{1,\dots ,n\}$ $jeg$ $1\leqslant i\leqslant n$ $\{1,\dots ,n\}$ $[n]$ $n=0$ $[0]=\{1,\dots ,0\}$ $\tomt sæt$ $\{a_{1},\dots,a_{n}\}$ $a_{i}$ $1\leqslant i\leqslant n$

I de givne eksempler er hvert sæt beskrevet ved at angive dets elementer. Ikke alle sæt kan beskrives på denne måde, eller selvom de kan beskrives på denne måde, kan opregningen af deres elementer være for lang eller for kompliceret til at bruge denne metode. Af denne grund er mange sæt defineret af egenskaber, der karakteriserer sættets elementer. Denne karakterisering kan gives uformelt ved hjælp af prosaisk sprog, som i det følgende eksempel.

$\{$ husnumre langs Kosygin Avenue er sættet af alle husnumre langs Kosygin Avenue. $\}$

Denne tilgang kan dog føre til tab af præcision eller tvetydighed. En adresseliste langs Kosygin Avenue kan således både betyde en liste over huse og en liste over lejligheder i disse huse.

Definition af sæt ved prædikater

Prædikater kan bruges til at skrive et sæt, snarere end en eksplicit opregning af elementer [3] . Denne form for sætnotation har tre dele: en variabel, et kolon eller lodret streg som separator og et boolsk prædikat . I dette tilfælde er der en variabel til venstre for afgrænseren og en regel til højre for den. Disse tre dele er omsluttet af krøllede seler:

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

eller

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

Afgrænsningen kan læses " sådan at " [4] , "for hvilken" eller "med ejendom". Formlen Φ( x ) kaldes en regel eller et prædikat . Alle værdier af variablen x , for hvilke prædikatet er sandt (det vil sige, det er sandt) tilhører det definerede sæt. Alle x -værdier, for hvilke prædikatet fejler, hører ikke til sættet. Således er mængden af alle x -værdier, for hvilke formlen Φ [5] er sand . Det kan være det tomme sæt, hvis ingen x- værdi opfylder formlen. $\{x\mid \Phi (x)\}$

Omfang

Omfanget af E kan vises til venstre for den lodrette bjælke [6] :

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

eller det kan kombineres med et prædikat:

\{x\mid x\in E{\text{ og }}\Phi (x)\}\quad {\text{or}}\quad \{x\mid x\in E\land \Phi (x)\}.

Symbolet ∈ betyder her at tilhøre mængden , mens symbolet betyder den logiske operator "AND", kendt som konjunktion . Denne notation repræsenterer sættet af alle x -værdier , der hører til et sæt E , for hvilket prædikatet evalueres til sandt , det vil sige sandt (se afsnittet " Eksistensens aksiom " nedenfor). Hvis er en ledsætning, så skrives formen nogle gange som , ved hjælp af et komma i stedet for . $\jord$ $\Phi (x)$ $\Phi _{1}(x)\land \Phi _{2}(x)$ ${\displaystyle \{x\in E\midt \Phi (x)\))$ ${\displaystyle \{x\in E\midt \Phi _{1}(x),\Phi _{2}(x)\))$ $\jord$

Generelt er det forkert at betragte et sæt uden at definere et omfang, da et domæne kan repræsentere en delmængde af alle mulige objekter, der kan eksistere, for hvilke prædikatet er sandt. Dette kan let føre til modsætninger og paradokser. For eksempel viser Russells paradoks , at udtrykket , selvom det ligner et velformet udtryk til at definere en mængde, ikke kan definere en mængde uden at få en modsigelse [7] . ${\displaystyle \{x~|~x\ikke \i x\))$

I tilfælde, hvor mængden E er klart defineret ud fra konteksten, kan den udelades. I litteraturen er det kutyme, at forfatteren på forhånd angiver definitionsdomænet, og så er domænet ikke angivet ved definition af mængder. For eksempel kan en forfatter skrive noget som: "Medmindre andet er angivet, tilhører variablerne naturlige tal."

Eksempler

De følgende eksempler illustrerer konkrete sæt defineret af prædikater. I hvert tilfælde er omfanget til venstre for den lodrette bjælke, mens reglen er til højre for den.

${\displaystyle \{x\in \mathbb {R} \mid x>0\))$ er mængden af alle strengt positive reelle tal , som kan skrives i intervalnotation som . $(0,\infty )$
${\displaystyle \{x\in \mathbb {R} \mid |x|=1\))$ er et sæt . Dette sæt kan også defineres som ; se afsnittet " ækvivalente prædikater definerer lige mængder " nedenfor. $\{-1,1\}$ $\{x\in \mathbb {R} \mid x^{2}=1\}$
For hvert heltal m kan vi definere . Som eksempler: og . ${\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)\))$ er mængden af par af reelle tal, således at y er større end 0 og mindre end f ( x ) for en given funktion f . Her betyder det kartesiske produkt mængden af alle ordnede par af reelle tal. $\mathbb {R} \times \mathbb {R}$
${\displaystyle \{n\i \mathbb {N} \mid (\eksisterer k)[k\in \mathbb {N} \land n=2k]\))$ er mængden af alle lige naturlige tal . Tegnet står for "AND"-operationen, som er kendt som konjunktion . Tegnet ∃ står for "eksisterer", som er kendt som den eksistentielle kvantifier . Så for eksempel læses det som "der er x sådan, at P ( x ) ...". $\jord$ $(\eksisterer x)P(x)$
${\displaystyle \{n\mid (\eksisterer k\i \mathbb {N} )[n=2k]\))$ er en anden måde at skrive det samme sæt af lige naturlige tal på. Det er ikke nødvendigt at kræve, at n er et naturligt tal, da dette følger af formlen i højre side.
$\{a\in \mathbb {R} \mid (\eksisterer p\i \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p ]\}$ er mængden af rationelle tal , det vil sige, at disse er reelle tal, der kan skrives som en kvotient af to heltal .

Mere komplekse udtryk i venstre side

Set-notationsudvidelsen erstatter den enkelte variabel x med udtrykket . Så i stedet kan vi have , som kan læses som $\{x\mid \Phi (x)\}$ $\{\Psi (x)\midt \Phi (x)\},$

\{\Psi (x)\mid \Phi (x)\}=\{y\mid \eksisterer (x),y=\Psi (x){\text{ og }}\Phi (x) \}

For eksempel:

${\displaystyle \{2n\midt n\in \mathbb {N} \))$ , hvor er mængden af alle naturlige tal er mængden af alle lige naturlige tal. $\mathbb {N}$
${\displaystyle \{p/q\mid p,q\in \mathbb {Z} ,q\not =0\))$ , hvor er mængden af alle heltal - dette er ℚ , mængden af alle rationelle tal. $\mathbb {Z}$
${\displaystyle \{2t+1\midt t\in \mathbb {Z} \))$ er mængden af ulige heltal.
${\displaystyle \{(t,2t+1)\midt t\in \mathbb {Z} \))$ opretter et sæt af par, hvor hvert par består af et heltal og dets tilsvarende ulige tal.

Hvis de inverse funktioner kan specificeres eksplicit, kan udtrykket til venstre elimineres ved simpel substitution. Lad os tage et sæt som eksempel . Vi laver en substitution , hvorfra vi får , så erstatter vi t i form af en sæt notation ${\displaystyle \{2t+1\midt 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} \}.

Ækvivalente prædikater definerer lige mængder

To sæt er lige, hvis og kun hvis de har de samme elementer. Sæt defineret af mængdenotationen er ens, hvis og kun hvis deres konstruktionsregler er ens, inklusive angivelse af definitionsdomænet. Det er

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

hvis og kun hvis

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

Derfor er det tilstrækkeligt at bevise ækvivalensen af deres prædikater, herunder deres domæner, for at bevise ligheden af to sæt defineret af notationen af et sæt.

For eksempel:

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

Da de to prædikatregler er logisk ækvivalente:

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

Denne ækvivalens gælder, fordi vi for ethvert reelt tal x har, hvis og kun hvis x er rationel og . Især begge sæt er lig med sættet . $x^{2}=1$ $|x|=1$ $\{-1,1\}$

Aksiomet for eksistensen af et sæt

I mange formelle mængdeteorier, såsom Zermelo-Fraenkel-systemet , er notationen af mængden ikke en del af teoriens formelle syntaks. I stedet er der et aksiomatisk skema for eksistensen af en mængde , som siger, at hvis E er en mængde, og Φ( x ) er en mængdeteoretisk formel, så er der en mængde Y , hvis medlemmer er nøjagtigt elementerne i E der opfylder betingelsen Φ :

(\forall E)(\eksisterer Y)(\forall x)[x\i Y\venstrehøjrepil x\i E\land \Phi (x)].

Mængden Y opnået fra dette aksiom er nøjagtig den mængde, der er beskrevet i form af mængdenotation . ${\displaystyle \{x\in E\midt \Phi (x)\))$

Paralleller i programmeringssprog

En lignende notation tilgængelig i mange programmeringssprog (især Python og Haskell ) er listeomsluttende , som kombinerer kort- og filteroperationerne på eller flere lister .

I Python erstattes sæt notationsparenteser med firkantede parenteser, parenteser eller krøllede parenteser for at definere henholdsvis en liste, generator og sæt af objekter. Python bruger engelsk syntaks. Haskell erstatter sæt parenteser med firkantede parenteser og bruger matematiske symboler, inklusive standard pipe karakter for sæt.

Det samme kan opnås i Scala ved hjælp af Sequence Comprehensions, hvor "for" nøgleordet returnerer en liste over variabler opnået ved hjælp af "yield" nøgleordet [8] .

Overvej følgende sæt opgaver i nogle programmeringssprog:

	Eksempel 1	Eksempel 2
Indstil notation	$\{l\ \|\ l\i L\}$	${\displaystyle \{(k,x)\ \|\ k\in K\wedge x\in X\wedge P(x)\))$
Python	{ l for l i L }	{( k , x ) for k i K for x i X hvis P ( x )}
Haskell	[ l \| l < -ls ]	[( k , x ) \| k <- ks , x <- xs , p x ]
Scala	for ( l <- L ) udbytte l	for ( k <- K ; x <- X hvis P ( x )) udbytte ( k , x )
C#	fra l i L vælg l	fra k i K fra x i X hvor P ( x ) vælg ( k , x )
SQL	VÆLG l FRA L_set	VÆLG k , x FRA K_set , X_set WHERE P ( x )

Sætnotationen og listeinkluderingen er specielle tilfælde af den mere generelle notation kendt som monadegeneratoren . Denne notation tillader operationer som kort/filter på enhver null C - monade .

Noter

↑ Rosen, 2007 , s. 111-112.
↑ Aufmann, Barker, Lockwood, 2007 , s. 6.
↑ Cullinan, 2012 , s. 44ff.
↑ Omfattende liste over sætteorisymboler . Math Vault (11. april 2020). Hentet 20. august 2020. Arkiveret fra originalen 18. august 2020.
↑ Weisstein, Eric W. Set . mathworld.wolfram.com . Hentet 20. august 2020. Arkiveret fra originalen 7. oktober 2020.
↑ Set-Builder-notation . mathsisfun.com . Hentet 20. august 2020. Arkiveret fra originalen 21. oktober 2020. (ubestemt)
↑ Irvine, Deutsch, 2016 .
↑ Sekvensforståelser . Scala. Hentet 6. august 2017. Arkiveret fra originalen 18. april 2021. (ubestemt)

Litteratur

Kenneth Rosen. Diskret matematik og dens anvendelser . — 6. - 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. - S. 6 ..
Michael J. Cullinan. En overgang til matematik med beviser. - Jones & Bartlett, 2012. - s. 44ff.
Andrew David Irvine, Harry Deutsch. Russell's Paradox // Stanford Encyclopedia of Philosophy . – 2016.