Par ordenado
Na Matemática, un par ordenado é unha colección de dous elementos tal que un dos elementos pode ser distinguido como o primeiro e o outro como o segundo, aínda que o primeiro e o segundo elemento sexan o mesmo. Un par ordenado con primeiro elemento a e segundo b é usualmente escrito como (a, b). Dous pares ordenados cumpren:
O conxunto de todos os pares ordenados nos cales o primeiro elemento vén dun conxunto X determinado e o segundo dun conxunto Y é chamado produto cartesiano de X e Y, escrito .
Listas ordenadas
Tríos ordenados e listas ordenadas son definidos recursivamente a partir da definición de par ordenado: un trío ordenado (a,b,c) pode ser definido como (a, (b,c)) ou como ((a, b), c); ou sexa, un par ordenado que contén outro par ordenado como elemento.
Esta abordaxe é espellada en linguaxes de programación: É posíbel representar unha lista de elementos como unha construción de pares ordenados aniñados. Por exemplo, a lista (1 2 3 4 5) tórnase (1, (2, (3, (4, (5, {})))) ). A linguaxe de programación Lisp usa estas listas como a súa estrutura de datos primaria.
Pares ordenados na teoría dos conxuntos
Na teoría dos conxuntos pura, onde existen soamente conxuntos, pares ordenados (a, b) poden ser definidos como o conxunto
Esa definición ten o nome de par de Kuratowski, e é ben básica, porque require apenas poucos axiomas para poder ser formulada (o axioma da extensión, o axioma da separación e o axioma do par ). A afirmación de que x sexa o primeiro elemento dun par ordenado p pode entón ser formulada como
- ∀ Y ∈ p : x ∈Y
e que x sexa o segundo elemento de p como
- (∃ Y ∈ p : x ∈ Y) ∧ (∀ Y1 ∈ p, ∀ Y2 ∈ p : Y1 ≠ Y2 → (x ∉ Y1 ∨ x ∉ Y2)).
Note que esa definición aínda é válida para o par ordenado p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }; neste caso a declaración (∀ Y1 ∈ p, ∀ Y2 ∈ p : Y1 ≠ Y2 → (x ∉ Y1 ∨ x ∉ Y2)) é trivialmente verdadeira, dado que nunca acontece que Y1 ≠ Y2.
Na formulación usual ZF da teoría dos conxuntos incluíndo o axioma da regularidade, un par ordenado (a, b) pode tamén ser definido como o conxunto {a, {a, b}}. De todas as formas, axioma da regularidade é necesario, dado que sen el, é posíbel considerar conxuntos x e z tais que x = {z}, z = {x}, e x ≠ z. Entón temos que
- (x, x) = {x, {x, x}} = {x,{x}} = {x, z} = {z, x} = {z, {z}} = {z, {z, z}} = (z, z)
malia querermos (x,x) ≠ (z,z).