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:

$(a,b)=(c,d)\iff a=c\land b=d$

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 $X\times Y$.

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

$~(a,b)=\{\{a\},\{a,b\}\}$

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) ∧ (∀ Y₁ ∈ p, ∀ Y₂ ∈ p : Y₁ ≠ Y₂ → (x ∉ Y₁ ∨ x ∉ Y₂)).

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 (∀ Y₁ ∈ p, ∀ Y₂ ∈ p : Y₁ ≠ Y₂ → (x ∉ Y₁ ∨ x ∉ Y₂)) é trivialmente verdadeira, dado que nunca acontece que Y₁ ≠ Y₂.

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 tales 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).