Para uporządkowana.html

Para uporządkowana – w matematyce struktura składająca się z dwóch wyróżnionych obiektów, z których jeden nazywany jest pierwszą współrzędną (pierwszym elementem lub rzutem lewostronnym), a pozostały 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 powyższej notacji tej para uporządkowana może być mylnie brana za przedział otwarty na prostej rzeczywistej, z tego powodu korzysta się również z wariantu $\left \langle a,b\right \rangle$ . Para jest „uporządkowana” w sensie, iż $(a, b)$ różni się od $(b, a)$ o ile $a$ i $b$ nie oznaczają tych samych obiektów.

edytuj Przykłady

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 obiekty $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).

edytuj Ogólne

Niech $(a 1, b 1)$ oraz $(a 2, b 2)$ będą dwiema parami uporządkowanymi. Własnością charakteryzującą lub określają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.

Pojęcie pary uporządkowanej odgrywa kluczową rolę podczas definiowania iloczynu kartezjańskiego oraz relacji.

edytuj Definicje teoriomnogościowe

Charakterystyczna własność par uporządkowanych, wspomniana w poprzedniej sekcji, jest wszystkim co niezbędne do zrozumienia sposobu użycia par uporządkowanych w literaturze matematycznej. Jednakże w celu dobrego ufundowania matematyki uważano za pożądane wyrażenie definicji każdego rodzaju obiektu matematycznego za pomocą zbiorów, co w przypadku pary uporządkowanej uczyniono na kilka sposobów.

edytuj Definicja Wienera

Norbert Wiener zaproponował pierwszą teoriomnogościową definicję pary uporządkowanej w 1914 roku:

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

Zauważył on, że definicja ta umożliwia wyrażenie wszystkich typów Principia Mathematica za pomocą samych zborów (w Principia Mathematica relacje wszystkich arności są pojęciami pierwotnymi).

edytuj Standardowa definicja Kuratowskiego

W aksjomatycznej teorii zbiorów para uporządkowana $(a, b)$ definiowana jest zwykle, za wybitnym polskim matematykiem Kazimierzem Kuratowskim, jako zbiór:

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

Zdanie, iż $x$ jest pierwszym elementem pary uporządkowanej $p$ może być wyrażone jako

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

a że $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łniona 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.

edytuj Warianty definicji

Powyższa definicja pary uporządkowanej jest „trafna” 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 definicji, które nie są bardziej skomplikowane i również są trafne. Przykładami innych możliwych definicji są

$(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” prawie nigdy nie jest używana, ponieważ brak jej jakiejkolwiek oczywistej zalety (lub wady) nad zwyczajową parą Kuratowskiego. „Krótka” para ma tę wadę, iż dowód własności charakteryzującej parę (zobacz wyżej) jest bardziej skomplikowany niż dla pary Kuratowskiego (wymagane jest użycie aksjomatu regularności). Co więcej, ponieważ liczba $2$ definiowana jest często jako zbiór $\{0, 1\} = \big\{\scriptstyle{\{\}, \{0\}}\big\}$ , to mogłoby to oznaczać, że $2$ to para $(0, 0)_{kr\acute otka}$ .

edytuj Dowód własności charakteryzującej pary uporządkowane

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

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

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}$ .

edytuj Definicja Quine'a-Rossera

Rosser (1953) mocno eksploatował definicję pary uporządkowanej dzięki pracom Willarda van Ormana Quine'a. Definicja Quine'a-Rossera 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$ .

Ta definicja pary uporządkowanej ma jedną zaletę. 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 funkcja, zdefiniowana jako zbiór par uporządkowanych, ma typ tylko o jeden wyższy niż tyo jej argumentów. Szczegółowe informacje o parach uporządkowanych w kontekście teorii mnogości Queine'a znajduje się w pozycji Holmesa (1998).

edytuj Definicja Morse'a

Teoria mnogości Morse'a-Kelleya, założona przez Morse'a (1965), korzysta w swobodny sposób z klas właściwych. Morse zdefiniował parę uporządkowaną tak, aby jej rzuty mogłyby 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. Definicja Rossera w poprzedniej sekcji również umożliwia użycie klas właściwych jako rzutów.

edytuj Teoria kategorii

Produkt to najbliższe parze uporządkowanej pojęcie teorii kategorii. Choć wiele obiektów może pełnić rolę pary, wszystkie są równoważne w sensie izomorfizmu kategorii.

edytuj Literatura

(en) 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.
(en) Morse, Anthony P., 1965. A Theory of Sets. Academic Press
(en) J. Barkley Rosser, 1953. Logic for mathematicians. McGraw-Hill.

edytuj Zobacz też

przegląd zagadnień z zakresu matematyki