Para uporządkowana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Para uporządkowana – w matematyce kolekcja obiektów o dwóch współrzędnych (elementach, rzutach) umożliwiająca jednoznaczne wyróżnienie dowolnego z obiektów, z których jeden nazywany jest poprzednikiem (pierwszą współrzędną, pierwszym elementem lub rzutem lewostronnym), a pozostały następnikiem (drugą współrzędną, drugim elementem lub rzutem prawostronnym). Zwyczajowym zapisem pary uporządkowanej jest (a, b), gdzie a jest pierwszą współrzędną, a b – drugą. W notacji tej para uporządkowana może być mylnie brana za przedział otwarty na zbiorze liczb rzeczywistych, z tego powodu korzysta się również z wariantu \langle a, b \rangle. Para jest „uporządkowana” w następującym sensie: (a, b) oznacza coś innego niż (b, a), o ile a \ne b.

Przykłady[edytuj | edytuj kod]

Przykładem pary uporządkowanej mogą być współrzędne punktu na płaszczyźnie, a także, wynikające z odpowiedniego utożsamienia, liczby zespolone. Ogólnie obiektami a i b w parze nie muszą być liczby, formalnie zdefiniowana grupa jest właśnie parą uporządkowaną (zbiór wraz z działaniem).

Ogólne[edytuj | edytuj kod]

Niech (a_1, b_1) oraz (a_2, b_2) będą dwiema parami uporządkowanymi. Własnością charakteryzującą (lub definiującą) parę uporządkowaną jest tożsamość

(a_1, b_1) = (a_2, b_2) \iff (a_1 = a_2 \and b_1 = b_2).

Pary uporządkowane mogą mieć za elementy inne pary uporządkowane. Z tego powodu para uporządkowana może służyć definicji rekurencyjnej krotek (n-tek) uporządkowanych (uporządkowanych list n-elementowych). Na przykład trójka uporządkowana (a, b, c) może być zdefiniowana jako \big(a, (b, c)\big), jedna para zagnieżdżona w innej. To podejście znajduje swoje odzwierciedlenie w językach programowania komputerów, gdzie można skonstruować listę elementów za pomocą zagnieżdżonych par uporządkowanych: lista (1 \; 2 \; 3 \; 4 \; 5) oznacza (1, (2, (3, (4, (5, \{\}))))). Język Lisp używa tego typu list jako podstawowej struktury danych.

Zbiór wszystkich par uporządkowanych, których poprzednik należy do zbioru X, a następnik – do zbioru Y, nazywa się iloczynem kartezjańskim X oraz Y, co zapisuje się X \times Y. Relacja dwuargumentowa nad dziedziną X \cup Y jest podzbiorem X \times Y.

Definicje teoriomnogościowe[edytuj | edytuj kod]

Własność charakterystyczna par uporządkowanych, wspomniana w poprzedniej sekcji, jest wszystkim co konieczne do zrozumienia istoty par uporządkowanych matematyce. Dlatego para uporządkowana może być postrzegana jako pojęcie pierwotne, którego aksjomatem jest wspomniana własność charakteryzująca. Podejście to wykorzystywała grupa N. Bourbakiego w swojej Teorii mnogości wydanej w 1954 roku, długo po podaniu odpowiedniej definicji przez Kuratowskiego (zob. niżej). Definicja Kuratowskiego została włączona do drugiego wydania Teorii mnogości wydanej w 1970 roku.

Niżej podano kilka definicji teoriomnogościowych pary uporządkowanej.

Definicja Wienera[edytuj | edytuj kod]

Pierwszą teoriomnogościową definicję pary uporządkowanej zaproponował w 1914 roku Norbert Wiener[1]:

(x, y) := \bigg\{\big\{\scriptstyle{\{x\},\{\}}\big\}, \big\{\{y\}\big\}\bigg\}.

Zauważył on, że definicja ta umożliwiła zdefiniowanie typów Principia mathematica za pomocą zbiorów. W Principia Mathematica używano typów, dlatego relacje wszystkich arnościpojęciami pierwotnymi.

Definicja Hausdorffa[edytuj | edytuj kod]

Mniej więcej w tym samym czasie co Wiener (1914) swoją definicję zaproponował Felix Hausdorff:

(a, b) := \{\{a, 1\}, \{b, 2\}\},

„gdzie 1 i 2 są dwoma różnymi obiektami różnymi od a i b[2].

Definicja Kuratowskiego[edytuj | edytuj kod]

W 1921 roku Kazimierz Kuratowski przedstawił dzisiaj przyjmowaną definicję[3] pary uporządkowanej (a, b):

(a,b)_K := \big\{\scriptstyle{\{a\}, \{a, b\}}\big\}

Definicja pozostaje prawidłowa, jeśli pierwsza i druga współrzędna są identyczne, tzn.

p = (x, x) = \big\{\scriptstyle{\{x\}, \{x, x\}}\big\} = \big\{\scriptstyle{\{x\}, \{x\}}\big\} = \big\{\scriptstyle{\{x\}}\big\}.

Dla danej pary uporządkowanej p własność „x jest pierwszym elementem” może być wyrażone jako

\forall\;Y \in p \colon x \in Y,

a własność „x jest drugim elementem p” jako

\left(\exist\;Y \in p \colon x \in Y\right) \and \left(\forall\;Y_1, Y_2 \in p \colon Y_1 \ne Y_2 \rarr (x \notin Y_1 \or x \notin Y_2)\right).

Należy zauważyć, że definicja ta jest dalej prawidłowa dla pary uporządkowanej

p = (x, x) = \big\{\scriptstyle{\{x\}, \{x, x\}}\big\} = \big\{\{x\}, \{x\}\big\} = \big\{\{x\}\big\};

w tym przypadku wyrażenie

\left(\forall\;Y_1, Y_2 \in p \colon Y_1 \ne Y_2 \rarr (x \notin Y_1 \or x \notin Y_2)\right) jest spełnione trywialnie, ponieważ nigdy nie zachodzi przypadek Y_1 \ne Y_2.

Inną metodą jest skorzystanie z działań iloczynu i sumy zbiorów:

\bigcap p = \bigcap \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cap \{x, y\} = \{x\},
\bigcup p = \bigcup \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cup \{x, y\} = \{x, y\}.

Wtedy x to jedyny element zbioru \bigcap p. Uzyskanie y wymaga rozważenia dwóch przypadków:

  • jeśli \bigcup p = \bigcap p, to \{x\} = \{x, y\} i y = x;
  • jeśli \bigcup p \ne \bigcap p, to \{x\} \ne \{x, y\}, a więc \{y\} = \bigcup p \setminus \bigcap p, czyli y to jedyny element tego zbioru.

Warianty[edytuj | edytuj kod]

Powyższa definicja Kuratowskiego pary uporządkowanej jest „adekwatna” w tym sensie, iż spełnia własność charakteryzującą parę uporządkowaną (tzn. jeśli (a, b) = (x, y), to a = x i b = y), ale również arbitralna, ponieważ istnieje wiele innych adekwatnych definicji o podobnej lub mniejszej złożoności, jak na przykład:

  • (a, b)_{odwr\acute ocona} := \big\{ \scriptstyle\{b\}, \{a, b\} \big\},
  • (a, b)_{kr\acute otka} := \big\{a, \scriptstyle\{a, b\} \big\},
  • (a, b)_{01} := \big\{ \scriptstyle\{0, a\}, \{1, b\} \big\}.

Para „odwrócona” jest mało interesująca, ponieważ brak jej jakiejkolwiek oczywistej zalety (lub wady) względem pary Kuratowskiego. „Krótka” para jest tak nazywana, ponieważ w jej definicji korzysta się z dwóch, a nie trzech nawiasów. Ma ona jednak tę wadę, iż dowód własności charakteryzującej parę (zobacz wyżej) wymaga użycia aksjomatu regularności ZFC. Co więcej, jeśli przyjmie się standardową definicję liczb naturalnych, to 2 jest zbiorem \{0, 1\} = \big\{\scriptstyle{0, \{0\}}\big\}, który jest nieodróżnialny od pary (0, 0)_{kr\acute otka}.

Dowód własności charakteryzującej[edytuj | edytuj kod]

Twierdzenie: (a, b)_K = (c, d)_K wtedy i tylko wtedy, gdy a = c oraz b = d.

Definicja Kuratowskiego 
Jeżeli a = b, to
(a, b)_K = \big\{\scriptstyle{\{a\}, \{a, b\}}\big\} = \big\{\{a\}, \{a, a\}\big\} = \big\{\{a\}\big\},
oraz
(c, d)_K = \big\{\scriptstyle{\{c\}, \{c, d\}}\big\} = \big\{\{a\}\big\},
stąd \{c\} = \{c, d\} = \{a\}, a więc c = d = a = b.
Jeżeli a \ne b, to wtedy \big\{\scriptstyle{\{a\}, \{a, b\}}\big\} = \big\{\{c\}, \{c, d\}\big\}.
Załóżmy, że \{c, d\} = \{a\}. Wówczas c = d = a i dlatego \big\{\scriptstyle{\{c\}, \{c, d\}}\big\} = \big\{\{a\}, \{a, a\}\big\} = \big\{\{a\}, \{a\}\big\} = \big\{\{a\}\big\}. Ale wtedy \big\{\scriptstyle{\{a\}, \{a, b\}}\big\} również równałoby się \big\{\scriptstyle{\{a\}}\big\}, czyli b = a, co przeczy a \ne b.
Założenie \{c\} = \{a, b\} dające a = b = c przeczy a \ne b.
Dlatego \{c\} = \{a\} lub c = a oraz \{c, d\} = \{a, b\}.
Jeżeli byłoby prawdą, że d = a, to \{c, d\} = \{a, a\} = \{a\} \ne \{a, b\}, sprzeczność. A więc d = b i dlatego a = c i b = d.
Odwrotnie: a = c oraz b = d, to \big\{\scriptstyle{\{a\}, \{a, b\}}\big\} = \big\{\{c\}, \{c, d\}\big\}. Stąd (a, b)_K = (c, d)_K.
Definicja odwrócona 
Prawdą jest, że (a, b)_{odwr\acute ocona} = \big\{\scriptstyle{\{b\}, \{a, b\}}\big\} = \big\{\{b\}, \{b, a\}\big\}  = (b, a)_K.
Jeżeli (a, b)_{odwr\acute ocona} = (c, d)_{odwr\acute ocona}, to (b, a)_K = (d, c)_K, stąd b = d oraz a = c.
W przeciwną stronę, jeżeli a = c i b = d, to \big\{\scriptstyle{\{b\}, \{a, b\}}\big\} = \big\{\{d\}, \{c, d\}\big\}, a więc (a, b)_{odwr\acute ocona} = (c, d)_{odwr\acute ocona}.

Definicja Quine'a-Rossera[edytuj | edytuj kod]

Rosser (1953)[4] przyjął definicję pary uporządkowanej pod wypływem Willarda Van Ormana Quine'a, która wymaga wcześniejszego zdefiniowania liczb naturalnych. Niech \mathbb N będzie zbiorem liczb naturalnych oraz

\varphi(x) = (x \setminus \mathbb N) \cup \bigg\{n+1\colon n \in (x \cap \mathbb N)\bigg\}.

Przyłożenie tej funkcji zwiększa o jeden liczbę naturalną w x. W szczególności \varphi(x) nie zawiera liczby 0, a więc dla dowolnych zbiorów x oraz y

\varphi(x) \ne \{0\} \cup \varphi(y).

Parę uporządkowaną (A, B) definiuje się jako

(A, B) = \bigg\{\varphi(a)\colon a \in A\bigg\} \cup \bigg\{\varphi(b) \cup \{0\}\colon b \in B\bigg\}.

Wydobycie wszystkich elementów z pary nie zawierających 0 i anulowanie \varphi daje A. Podobnie można odzyskać B z elementów pary zawierających 0.

W teorii typów oraz w teoriach mnogości takich jak New Foundations, które zasadzają się na teorii typów, para ta ma ten sam typ co jej rzuty (stąd też nazywa się ją parą uporządkowaną „typ-poziom”). Dlatego definicja ta ma tę zaletę, iż funkcja zdefiniowana jako zbiór par uporządkowanych ma typ tylko o jeden wyższy niż typ jej argumentów. Szczegółowe informacje o parze uporządkowanej w kontekście teorii mnogości Quine'a znajdują się w pozycji Holmesa (1998).[5].

Definicja Morse'a[edytuj | edytuj kod]

Teoria mnogości Morse'a-Kelleya (Morse, 1965)[6] korzysta w swobodny sposób z klas właściwych. Morse zdefiniował parę uporządkowaną tak, aby jej rzuty mogły być, obok zbiorów, klasami właściwymi (definicja Kuratowskiego na to nie zezwala). Najpierw zdefiniował on pary uporządkowane, których rzuty są zbiorami, na modłę Kuratowskiego. Następnie przedefiniował parę (x, y) jako \left(x \times \{0\}\right) \cup \left(y \times \{1\}\right), gdzie składowe iloczyny kartezjańskie są parami Kuratowskiego na zbiorach. To właśnie ten drugi krok sprawia, że prawidłowe są pary, których rzuty są klasami właściwymi. Powyższa definicja Quine'a-Rossera również umożliwia użycie klas właściwych jako rzutów.

Teoria kategorii[edytuj | edytuj kod]

Produkt teoriokategoryjny A \times B w kategorii zbiorów reprezentuje zbiór par uporządkowanych, których poprzedniki należą do A, a następniki wzięte są z B. W tym kontekście własność charakteryzująca jest konsekwencją własności uniwersalnej produktu oraz faktu, iż elementy zbioru X mogą być utożsamiane z morfizmami z 1 (zbioru jednoelementowego) w X. Choć różne obiekty mogą mieć wspomnianą własność uniwersalną, to są one wszystkie naturalnie izomorficzne.

Trójki, czwórki, …, n-ki uporządkowane[edytuj | edytuj kod]

Information icon.svg Zobacz też: ciąg (matematyka).

Za pomocą pojęcia pary uporządkowanej można zdefiniować indukcyjnie kolejno trójki, czwórki, …, n-ki uporządkowane. W żargonie informatycznym, pojęcia te występują zbiorczo pod nazwą krotek (n-elementowych).

Dla n > 2 n-kę uporządkowaną

(a_1, a_2, \dots, a_n)

definiuje się jako parę uporządkowaną

 \left(a_1, (a_2, \dots, a_n)\right)

lub

\left((a_1, \dots, a_{n-1}), a_n\right).

Do celów technicznych można przyjąć umowę, że

(a_1) = \{a_1\}

oraz

() = \varnothing.

Przypisy

  1. Praca Wienera „A Simplification of the logic of relations” została przedrukowana wraz z wartościowym komentarzem na stronach 224nn w van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1979-1931, Harvard University Press, Cambridge MA, ISBN 0-674-32449-8 (pbk.). van Heijenoort wyraża uproszczenie w następujący sposób: „Zdefiniowanie pary uporządkowanej dwóch elementów za pomocą operacji klasowych sprawia, iż uwaga redukuje teorię relacji do teorii klas”. (By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes)
  2. zob. wprowadzenie do pracy Wienera w van Heijenoort 1967:224
  3. zob. wprowadzenie do pracy Wienera w van Heijenoort 1967:224. van Heijenoort zauważa, że zbiór wynikowy, który reprezentuje parę uporządkowaną „ma typ wyższy o 2 od swoich elementów (jeśli są tego samego typu)” (has a type higher by 2 than the elements (when they are of the same type)); przedstawia również źródła, które, pod pewnymi warunkami, pokazują jak typ może być zredukowany do \scriptstyle 1, czy \scriptstyle 0.
  4. John Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.
  5. Holmes, Randall, 1998. Elementary Set Theory with a Universal Set. Academia-Bruylant. Wydawca wielkodusznie wyraził zgodę na rozproszenie tej monografii w sieci. Prawa autorskie są zarezerwowane.
  6. Morse, Anthony P., 1965. A Theory of Sets. Academic Press