Bestilt par - Ordered pair

I matematikk er et ordnet par ( a , b ) et par objekter. Rekkefølgen objektene vises i paret er signifikant: det bestilte paret ( a , b ) er forskjellig fra det bestilte paret ( b , a ) med mindre a = b . (I kontrast er det uordnede paret { a , b } det uordnede paret { b , a }.)

Ordnede par kalles også 2-tupler , eller sekvenser (noen ganger lister i en informatikk-kontekst) med lengde 2. Ordnede par skalarer kalles noen ganger todimensjonale vektorer . (Teknisk sett er dette et misbruk av terminologi siden et ordnet par ikke trenger å være et element i et vektorrom .) Oppføringene til et bestilt par kan være andre ordnede par, noe som muliggjør rekursiv definisjon av bestilte n -par (ordnede lister over n objekter). For eksempel kan den bestilte trippelen ( a , b , c ) defineres som ( a , ( b , c )), dvs. som ett par nestet i et annet.

I det bestilte paret ( a , b ) kalles objektet a den første oppføringen , og objektet b den andre oppføringen av paret. Alternativt kalles objektene den første og andre komponenten , den første og andre koordinaten , eller venstre og høyre projeksjon av det bestilte paret.

Kartesiske produkter og binære relasjoner (og dermed funksjoner ) er definert i form av ordnede par.

Generaliteter

La og bli bestilt par. Da er den karakteristiske (eller definerende ) egenskapen til det bestilte paret: ${\ displaystyle (a_ {1}, b_ {1})}}$ ${\ displaystyle (a_ {2}, b_ {2})}$

{\ displaystyle (a_ {1}, b_ {1}) = (a_ {2}, b_ {2}) {\ text {if and only if}} a_ {1} = a_ {2} {\ text {og }} b_ {1} = b_ {2}.}

Den settet av alle ordnede par, hvis første inngang er i noen sett A og hvis andre inngang er i noen sett B kalles kartesiske produktet av A og B , og skriftlig A x B . En binær relasjon mellom settene A og B er en delmengde av A x B .

Den $(en, b)$ notasjon kan brukes til andre formål, særlig som betegner åpen intervaller på den reelle tall linje . I slike situasjoner vil konteksten vanligvis gjøre det klart hvilken mening som er ment. For ytterligere avklaring kan det bestilte paret betegnes med variantnotasjonen , men denne notasjonen har også andre bruksområder. ${\ textstyle \ langle a, b \ rangle}$

Venstre og høyre projeksjon av et par p er vanligvis angitt med henholdsvis $π$ ₁ ( p ) og $π$ ₂ ( p ), eller med $π$ _ℓ ( p ) og $π$ _r ( p ). I sammenhenger der vilkårlige n -tupler vurderes, $π$ ⁿ
_i( t ) er en vanlig notasjon for den i -komponenten av en n -tupel t .

Uformelle og formelle definisjoner

I noen innledende matematiske lærebøker gis en uformell (eller intuitiv) definisjon av ordnet par, for eksempel

For to objekt $a$ og $b$ er det ordnede paret $(a, b)$ en notasjon som angir de to objektene $a$ og $b$ , i den rekkefølgen.

Dette blir vanligvis etterfulgt av en sammenligning med et sett med to elementer; påpeker at i et sett må $a$ og $b$ være forskjellige, men i et ordnet par kan de være like, og at selv om rekkefølgen for å liste elementene i et sett ikke spiller noen rolle, endres i et ordnet par i rekkefølgen på forskjellige oppføringer det bestilte paret.

Denne "definisjonen" er utilfredsstillende fordi den bare er beskrivende og er basert på en intuitiv forståelse av orden . Som det noen ganger påpekes, vil det imidlertid ikke komme noen skade ved å stole på denne beskrivelsen, og nesten alle tenker på bestilte par på denne måten.

En mer tilfredsstillende tilnærming er å observere at den karakteristiske egenskapen til ordnede par gitt ovenfor er alt som kreves for å forstå rollen til ordnede par i matematikk. Derfor kan det ordnede paret tas som en primitiv forestilling , hvis tilhørende aksiom er den karakteristiske egenskapen. Dette var tilnærmingen som N. Bourbaki -gruppen tok i sin Theory of Sets , utgitt i 1954. Imidlertid har denne tilnærmingen også sine ulemper, ettersom både eksistensen av ordnede par og deres karakteristiske egenskaper må antas aksiomatisk.

En annen måte å håndtere ordnede par på er å definere dem formelt i sammenheng med settteori. Dette kan gjøres på flere måter og har fordelen av at eksistens og den karakteristiske egenskapen kan bevises ut fra aksiomene som definerer settteorien. En av de mest siterte versjonene av denne definisjonen skyldes Kuratowski (se nedenfor), og hans definisjon ble brukt i den andre utgaven av Bourbakis Theory of Sets , utgitt i 1970. Selv de matematiske lærebøkene som gir en uformell definisjon av ordnede par vil ofte nevne den formelle definisjonen av Kuratowski i en øvelse.

Definere det bestilte paret ved hjelp av settteori

Hvis man er enig i at settteori er et tiltalende grunnlag for matematikk , må alle matematiske objekter defineres som sett av noe slag. Derfor hvis det bestilte paret ikke blir sett på som primitivt, må det defineres som et sett. Flere settteoretiske definisjoner av det ordnede paret er gitt nedenfor (se også).

Wieners definisjon

Norbert Wiener foreslo det første settet teoretiske definisjonen av det bestilte paret i 1914:

{\ displaystyle \ left (a, b \ right): = \ left \ {\ left \ {\ left \ {a \ right \}, \, \ emptyset \ right \}, \, \ left \ {\ left \ {b \ right \} \ right \} \ right \}.}

Han observerte at denne definisjonen har gjort det mulig å definere typer av Principia Mathematica som sett. Principia Mathematica hadde tatt typer, og derav relasjoner mellom alle arter, som primitive .

Wiener brukte {{ b }} i stedet for { b } for å gjøre definisjonen kompatibel med typeteori der alle elementene i en klasse må være av samme "type". Med b nestet i et tilleggssett, er dens type lik . ${\ displaystyle \ {\ {a \}, \ emptyset \}}$

Hausdorffs definisjon

Omtrent samtidig som Wiener (1914) foreslo Felix Hausdorff sin definisjon:

{\ displaystyle (a, b): = \ venstre \ {\ {a, 1 \}, \ {b, 2 \} \ høyre \}}

"hvor 1 og 2 er to forskjellige objekter som er forskjellige fra a og b."

Kuratowskis definisjon

I 1921 tilbød Kazimierz Kuratowski den nå aksepterte definisjonen av det bestilte paret ( a , b ):

{\ displaystyle (a, \ b) _ {K} \;: = \ \ {\ {a \}, \ \ {a, \ b \} \}.}

Vær oppmerksom på at denne definisjonen brukes selv om den første og den andre koordinaten er identiske:

{\ displaystyle (x, \ x) _ {K} = \ {\ {x \}, \ {x, \ x \} \} = \ {\ {x \}, \ \ {x \} \} = \ {\ {x \} \}}

Gitt noen bestilte par p , kan egenskapen " x er den første koordinaten til p " formuleres som:

{\ displaystyle \ forall Y \ in p: x \ in Y.}

Egenskapen " x er den andre koordinaten til p " kan formuleres som:

{\ displaystyle (\ finnes Y \ i p: x \ i Y) \ land (\ for alle Y_ {1}, Y_ {2} \ i p: Y_ {1} \ neq Y_ {2} \ rightarrow (x \ notin Y_ {1} \ lor x \ notin Y_ {2})).}

I tilfelle at venstre og høyre koordinater er identiske, er den høyre konjunkten trivielt sann, siden Y ₁ ≠ Y ₂ aldri er tilfelle. ${\ displaystyle (\ forall Y_ {1}, Y_ {2} \ in p: Y_ {1} \ neq Y_ {2} \ rightarrow (x \ notin Y_ {1} \ lor x \ notin Y_ {2})) }$

Slik kan vi trekke ut den første koordinaten til et par (ved å bruke notasjonen for vilkårlig kryss og vilkårlig forening ):

{\ displaystyle \ pi _ {1} (p) = \ bigcup \ bigcap s.}

Slik kan den andre koordinaten trekkes ut:

{\ displaystyle \ pi _ {2} (p) = \ bigcup \ left \ {\ left.x \ in \ bigcup p \, \ right | \, \ bigcup p \ neq \ bigcap p \ rightarrow x \ notin \ bigcap p \ høyre \}.}

Varianter

Den ovennevnte Kuratowski -definisjonen av det bestilte paret er "tilstrekkelig" ved at den tilfredsstiller den karakteristiske egenskapen som et ordnet par må tilfredsstille, nemlig det . Spesielt uttrykker det tilstrekkelig 'rekkefølge', der det er usant med mindre . Det er andre definisjoner, av lignende eller mindre kompleksitet, som er like tilstrekkelige: ${\ displaystyle (a, b) = (x, y) \ venstrehøyre pil (a = x) \ land (b = y)}$ ${\ displaystyle (a, b) = (b, a)}$ ${\ displaystyle b = a}$

${\ displaystyle (a, b) _ {\ text {reverse}}: = \ {\ {b \}, \ {a, b \} \};}$
${\ displaystyle (a, b) _ {\ text {short}}: = \ {a, \ {a, b \} \};}$
${\ displaystyle (a, b) _ {\ text {01}}: = \ {\ {0, a \}, \ {1, b \} \}.}$

Den omvendte definisjonen er bare en triviell variant av Kuratowski -definisjonen, og har som sådan ingen uavhengig interesse. Definisjonen kort er såkalt fordi den krever to snarere enn tre par seler . Å bevise at kort tilfredsstiller den karakteristiske egenskapen krever Zermelo - Fraenkel -setteteoriens aksiom for regelmessighet . Dessuten, hvis man bruker von Neumanns settteoretiske konstruksjon av de naturlige tallene , så er 2 definert som settet {0, 1} = {0, {0}}, som ikke kan skilles fra paret (0, 0) _kort . Nok en ulempe med det korte paret er det faktum at selv om a og b er av samme type, er elementene i det korte paret ikke det. (Men hvis en = b så korte versjonen holder å ha kardinalitet 2, som er noe man kunne forvente av noen "pair", inkludert "ordnet par". Merk også at den korte versjonen er brukt i Tarski-Grothendieck mengdelære , som Mizar -systemet er basert på.)

Beviser at definisjoner tilfredsstiller den karakteristiske egenskapen

Bevis: ( a , b ) = ( c , d ) hvis og bare hvis a = c og b = d .

Kuratowski :
Hvis . Hvis a = c og b = d , så er {{ a }, { a, b }} = {{ c }, { c, d }}. Således ( a, b ) _K = ( c, d ) _K .

Bare hvis . To tilfeller: a = b , og a ≠ b .

Hvis a = b :

( a, b ) _K = {{ a }, { a, b }} = {{ a }, { a, a }} = {{ a }}.

( c, d ) _K = {{ c }, { c, d }} = {{ a }}.

Dermed er { c } = { c, d } = { a }, som innebærer a = c og a = d . Ved hypotese er a = b . Derfor b = d .

Hvis a ≠ b , betyr ( a, b ) _K = ( c, d ) _K {{ a }, { a, b }} = {{ c }, { c, d }}.

Anta at { c, d } = { a }. Så c = d = a , og så {{ c }, { c, d }} = {{ a }, { a, a }} = {{ a }, { a }} = {{ a }}. Men da er {{ a }, { a, b }} også lik {{ a }}, slik at b = a som motsier a ≠ b .

Anta at { c } = { a, b }. Deretter er a = b = c , som også motsier a ≠ b .

Derfor er { c } = { a }, slik at c = a og { c, d } = { a, b }.

Hvis d = a var sant, så er { c, d } = { a, a } = { a } ≠ { a, b }, en motsetning. Dermed er d = b tilfelle, slik at a = c og b = d .

Omvendt :
( a, b ) _revers = {{ b }, { a, b }} = {{ b }, { b, en }} = ( b, a ) _K .

Hvis . Dersom ( a, b ) _revers = ( c, d ) _revers , ( b, a ) _K = ( d, c ) _K . Derfor er b = d og a = c .

Bare hvis . Hvis a = c og b = d , så er {{ b }, { a, b }} = {{ d }, { c, d }}. Således ( a, b ) _revers = ( c, d ) _revers .

Kort:

Hvis : Hvis a = c og b = d , så er { a , { a, b }} = { c , { c, d }}. Dermed ( a, b ) _kort = ( c, d ) _kort .

Bare hvis : Anta at { a , { a, b }} = { c , { c, d }}. Så en er i venstre side, og dermed i høyre side. Fordi like sett har like elementer, må ett av a = c eller a = { c, d } være tilfelle.

Hvis a = { c, d }, med samme resonnement som ovenfor, er { a, b } på høyre side, så { a, b } = c eller { a, b } = { c, d }.

Hvis { a, b } = c så er c i { c, d } = a og a er i c , og denne kombinasjonen motsier regelmessighetens aksiom, ettersom { a, c } ikke har noe minimalt element under relasjon "elementet i . "

Hvis { a, b } = { c, d }, så en er et element av en , fra en = { c, d } = { a, b }, igjen motsier regularitet.

Derfor må a = c holde.

Igjen ser vi at { a, b } = c eller { a, b } = { c, d }.

Alternativet { a, b } = c og a = c innebærer at c er et element av c , som motsier regelmessighet.

Så vi har a = c og { a, b } = { c, d }, og så: { b } = { a, b } \ { a } = { c, d } \ { c } = { d }, så b = d .

Quine – Rosser definisjon

Rosser (1953) brukte en definisjon av det bestilte paret på grunn av Quine som krever en forhåndsdefinisjon av de naturlige tallene . La oss være settet med naturlige tall og definere først ${\ displaystyle \ mathbb {N}}$

{\ displaystyle \ sigma (x): = {\ start {cases} x, og {\ text {if}} x \ not \ in \ mathbb {N}, \\ x+1, og {\ text {if} } x \ in \ mathbb {N}. \ end {cases}}}

Funksjonen øker argumentet hvis det er et naturlig tall og lar det være som det ellers er; tallet 0 vises ikke som funksjonell verdi av . Som er settet med elementene i ikke i gang med ${\ displaystyle \ sigma}$ ${\ displaystyle \ sigma}$ ${\ displaystyle x \ smallsetminus \ mathbb {N}}$ ${\ displaystyle x}$ ${\ displaystyle \ mathbb {N}}$

{\ displaystyle \ varphi (x): = \ sigma [x] = \ {\ sigma (\ alpha) \ mid \ alpha \ in x \} = (x \ smallsetminus \ mathbb {N}) \ cup \ {n+ 1: n \ in (x \ cap \ mathbb {N}) \}.}

Dette er settbildet til et sett under , noen ganger betegnet med også. Bruk av funksjon på et sett x øker ganske enkelt hvert naturlige tall i det. Spesielt inneholder den aldri tallet 0, slik at for alle sett x og y , ${\ displaystyle x}$ ${\ displaystyle \ sigma}$ ${\ displaystyle \ sigma '' x}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ varphi (x)}$

{\ displaystyle \ varphi (x) \ neq \ {0 \} \ cup \ varphi (y).}

Videre definere

{\ displaystyle \ psi (x): = \ sigma [x] \ cup \ {0 \} = \ varphi (x) \ cup \ {0 \}.}

Ved dette inneholder det alltid tallet 0. ${\ displaystyle \ psi (x)}$

Til slutt definerer du det bestilte paret ( A , B ) som den usammenhengende foreningen

{\ displaystyle (A, B): = \ varphi [A] \ cup \ psi [B] = \ {\ varphi (a): a \ i A \} \ cup \ {\ varphi (b) \ cup \ { 0 \}: b \ i B \}.}

(som er i alternativ notasjon). ${\ displaystyle \ varphi '' A \ cup \ psi '' B}$

Ekstrahering av alle elementene i paret som ikke inneholder 0 og å løsne utbytter A . På samme måte kan B gjenvinnes fra elementene i paret som inneholder 0. ${\ displaystyle \ varphi}$

For eksempel er paret kodet som angitt . ${\ displaystyle (\ {\ {a, 0 \}, \ {b, c, 1 \} \}, \ {\ {d, 2 \}, \ {e, f, 3 \} \})}$ ${\ displaystyle \ {\ {a, 1 \}, \ {b, c, 2 \}, \ {d, 3,0 \}, \ {e, f, 4,0 \} \}}$ ${\ displaystyle a, b, c, d, e, f \ notin \ mathbb {N}}$

I typeteori og i utvekster derav, for eksempel den aksiomatiske settteorien NF , har Quine-Rosser-paret samme type som sine anslag og betegnes derfor som et "type-nivå" ordnet par. Derfor har denne definisjonen fordelen av at en funksjon , definert som et sett med ordnede par, kan ha en type bare 1 høyere enn typen av dens argumenter. Denne definisjonen fungerer bare hvis settet med naturlige tall er uendelig. Dette er tilfellet i NF , men ikke i typeteori eller i NFU . J. Barkley Rosser viste at eksistensen av et slikt ordnet par på type nivå (eller til og med et "typehevende med 1" ordnet par) innebærer uendelig aksiom . For en omfattende diskusjon av det ordnede paret i sammenheng med Quinian -setteteorier, se Holmes (1998).

Cantor – Frege definisjon

Tidlig i utviklingen av settteorien, før paradokser ble oppdaget, fulgte Cantor Frege ved å definere det bestilte paret med to sett som klassen av alle relasjoner som holder mellom disse settene, forutsatt at begrepet relasjon er primitivt:

{\ displaystyle (x, y) = \ {R: xRy \}.}

Denne definisjonen er ikke tillatelig i de fleste moderne formaliserte settteorier og ligner metodisk på å definere kardinalen til et sett som klassen av alle sett som er ekvipotente med det gitte settet.

Morse definisjon

Settteorien til Morse - Kelley gjør gratis bruk av riktige klasser . Morse definerte det bestilte paret slik at anslagene kunne være riktige klasser så vel som sett. (Kuratowski -definisjonen tillater ikke dette.) Han definerte først ordnede par hvis fremskrivninger er sett på Kuratowskis måte. Deretter omdefinerte han paret

{\ displaystyle (x, y) = (\ {0 \} \ times s (x)) \ cup (\ {1 \} \ times s (y))}

hvor komponenten kartesiske produkter er Kuratowski -sett med sett og hvor

{\ displaystyle s (x) = \ {\ emptyset \} \ cup \ {\ {t \} \ midt t \ i x \}}

Dette gir mulige par hvis anslag er riktige klasser. Quine - Rosser -definisjonen ovenfor innrømmer også riktige klasser som projeksjoner. På samme måte er trippelen definert som en 3-tupel som følger:

{\ displaystyle (x, y, z) = (\ {0 \} \ times s (x)) \ cup (\ {1 \} \ times s (y)) \ cup (\ {2 \} \ times s (z))}

Bruken av singleton -settet som har et innsatt tomt sett tillater tupler å ha den unike egenskapen at hvis a er en n -doble og b er en m -doble og a = b så n = m . Bestilte trippler som er definert som bestilte par, har ikke denne egenskapen med hensyn til bestilte par. ${\ displaystyle s (x)}$

Aksiomatisk definisjon

Ordnede par kan også bli introdusert i Zermelo - Fraenkel settteori (ZF) aksiomatisk ved bare å legge til ZF et nytt funksjonssymbol for arity 2 (det er vanligvis utelatt) og et definerende aksiom for : ${\ displaystyle f}$ ${\ displaystyle f}$

{\ displaystyle f (a_ {1}, b_ {1}) = f (a_ {2}, b_ {2}) {\ tekst {hvis og bare hvis}} a_ {1} = a_ {2} {\ tekst {og}} b_ {1} = b_ {2}.}

Denne definisjonen er akseptabel fordi denne utvidelsen av ZF er en konservativ forlengelse .

Definisjonen bidrar til å unngå såkalte tilfeldige setninger som (a, a) = {{a}}, {a} ∈ (a, b), hvis Kuratowskis definisjon (a, b) = {{a}, {a, b }} var brukt.

Kategoriteori

Kommutativ diagram for settproduktet X ₁ × X ₂ .

En kategori-teoretiske produkt A x B i en kategori av settene representerer settet av ordnede par, med det første element som kommer fra A og den andre kommer fra B . I denne sammenheng er den karakteristiske egenskapen ovenfor er en konsekvens av den universelle egenskap av produktet, og det faktum at elementene i et sett X kan identifiseres med morphisms fra 1 (a et element sett) for X . Selv om forskjellige objekter kan ha den universelle egenskapen, er de alle naturlig isomorfe .

Languages

In other projects