RELACIONES DE ORDEN

Def
Sea R ⊆ A × A una relación binaria

1. R es antisimétrica ⇐⇒
∀x, y ∈ A, xRy, yRx =⇒ x = y
2. R es antirreflexiva ⇐⇒ ∀x ∈ A, x  Rx
3. R es conexa ⇐⇒
∀x, y ∈ A, x = y =⇒ xRy o yRx.

En general: No reflexiva = antirreflexiva

Def
Sea R ⊆ A × A una relación binaria.
R es un orden parcial ⇐⇒ R es reflexiva, antisimétrica y transitiva.
R es un orden estricto ⇐⇒ R es antirreflexiva y transitiva.
Un conjunto A junto con un orden parcial R decimos que es un conjunto
parcialmente ordenado (conj.p.o.) y lo denotamos por (A,R).
Normalmente en vez de aRb escribimos a  b y (A, )
Para denotar órdenes estrictos usamos (A, )

Ej.

1. R1 ⊆ N × N xR1 y ⇐⇒ x ≤ y.
También podemos definirlo en Z, Q, R.
2. R2 ⊆ N+ × N+ xR2 y ⇐⇒ x/y.
3. R3 ⊆ P(A) × P(A) XR3 Y ⇐⇒ X ⊆ Y A cualquier conjunto.
4. R4 ⊆ N 2 × N 2
(x, y)R4 (x , y ) ⇐⇒ x ≤ x , y ≤ y  .
N = N, Z, Q, R.

Los siguientes son órdenes estrictos.

1. S1 ⊆ N × N xS1 y ⇐⇒ x < y.
También podemos definirlo en Z, Q, R.
2. S2 ⊆ N 2 × N 2
(x, y)S2 (x , y ) ⇐⇒ x < x , y < y .
N = N, Z, Q, R.
3. S3 ⊆ P(A) × P(A) XS3 Y ⇐⇒ X ⊂ Y .
4. S4 ⊆ P(A) × P(A) XS4 Y ⇐⇒ X ∩ Y = ∅. Al no ser reflexiva =⇒ no
es un orden
∅  R ∅ ya que ∅ ∩ ∅ = ∅

1
Proposición

1. Sea (A, ) un conj. p.o., entonces

∀x, y ∈ A, x  y ⇐⇒ x  y, x = y
es un orden estricto.
2. Sea (A, ) un orden estricto, entonces
∀x, y ∈ A, x  y ⇐⇒ x  y o x = y
es un orden.

Proposición
La relación inversa de un orden es también un orden.

1. Sea (A, ) un conj.p.o., definimos

∀x, y ∈ A, x y ⇐⇒ y  x
Entonces (A, ) es un conj.p.o.
2. Sea (A, ) un orden estricto, definimos
∀x, y ∈ A, x  y ⇐⇒ y  x
(A, ) es un orden estricto.

Def.
Sea (A, ) un conj.p.o. y sea  conexo, entonces (A, ) decimos que es un
orden total u orden lineal.
Análogamente (A, ) es un orden estricto lineal o un orden estricto total
si  es conexo.
Ej.1
R1 ⊆ N × N xR1 y ⇐⇒ x ≤ y es un orden total.
Ej.2
R2 ⊆ P(A) × P(A) XR2 Y ⇐⇒ X ⊆ Y no es un orden total ya que {0, 1} ⊆
{1, 2} ni {1, 2} ⊆ {0, 1}
Decimos que {0, 1} y {1, 2} son incomparables.
En otro caso decimos que son comparables.
Sea (A, ) un [Link] representarlo gráficamente mediante lo que
se conoce como Diagrama de Hasse Consiste en un conjunto de puntos
conectados por segmentos. Los puntos son los elementos del conjunto y cada
segmento ascendente entre x e y se interpreta que representa x  y. Los
segmentos que se deducen por transitividad no se dibujan.
Ej.
Sea (A, ) un conj.p.o. A = {2, 3, 4, 6, 8, 12}
x  y ⇐⇒ x / y

2
 8 12

Diagrama de Hasse
4 6

2 3

Proposición
Sea R ⊆ A × A un orden parcial y sea S ⊆ A. La restricción de R a S se
define como
R  S = R ∩ (S × S)
(S, R  S) es un conj.p.o.

Def.
Sean (A, A ) y (B, B ) conj.p.o. y sea f : A −→ B una función

1. f es monótona ⇐⇒ ∀x, y ∈ A, x A y =⇒ f (x) B f (y)

2. f preserva el orden ⇐⇒ ∀x, y ∈ A, x A y ⇐⇒ f (x) B f (y)
3. f es un isomorfismo de orden ⇐⇒ f es biyectiva y preserva el orden.

Si existe un isomorfismo de orden entre (A, A ) y (B, B ) entonces decimos

que (A, A ) y (B, B ) son isomorfos y escribimos ((A, A )  (B, B )).
Si (B, B ) = (A, A ) decimos que f es un (automorfismo).

Ej.

1. Sea f : P(Z) −→ P(Z)

f (X) = {x2 |x ∈ X}
f es monotona.
X ⊆ Y =⇒ f (X) ⊆ f (Y )
Pero f (X) ⊆ f (Y ) no implica X ⊆ Y .
X = {−2, 3} Y = {−4, 2, 3}
f (X) = {4, 9} ⊆ f (Y ) = {16, 4, 9} pero X ⊆ Y
2. Sea A = {2n|n ∈ N} B = {2n + 1|n ∈ N}
f : A −→ B
2n −→ 2n + 1

(A, ≤)  (B, ≤)
x ≤ y ⇐⇒ 2x + 1 ≤ 2y + 1

3
ELEMENTOS EXTREMOS Y EXTREMALES

Def.
Sea (A, A ) un conj.p.o. y S ⊆ A. Decimos que un elemento x ∈ S es

1. maximal en S ⇐⇒ y ∈ S tal que x  y.

2. el máximo de S (max(S)) ⇐⇒ y  x, ∀y ∈ S.
3. minimal en S ⇐⇒ y ∈ S tal que y  x.
4. el mı́nimo de S (min(S))⇐⇒ x  y, ∀y ∈ S.

Ej.
A = {2, 3, 4, 6, 8, 12} x  y ⇐⇒ x/y

8 12

4 6

2 3

2, 3 elementos minimales
8, 12 elementos maximales.
No hay máximo ni mı́nimo.

Prop.
Sea (A, A ) un conj.p.o. y S ⊆ A.

1. máximo de S =⇒ maximal en S pero maximal en S =⇒ máximo de S.

2. si S tiene un elemento máximo es único.
3. mı́nimo de S =⇒ minimal en S pero minimal en S =⇒ mı́nimo de S.
4. si S tiene un elemento mı́nimo es único.

Dem.

1. Sea x ∈ S máximo =⇒ y  x, ∀y ∈ S. Supongamos x no es un elemento

maximal, entonces existe y0 ∈ S tal que x  y0 como y0  x =⇒ x = y0
por la propiedad antisimétrica. Contradicción. En el ejemplo, 8, 12 son
maximales pero ni 8 ni 12 son máximos. (8  12 12  8)
2. Supongamos x, y son ambos máximos de S, entonces x  y ya que y es
máximo y y  x ya que x es máximo, luego x = y por la propiedad
antisimétrica.

Análogamente 3) y 4).

4
Teorema
Sean (A, A ) y (B, B ) conj.p.o. y sea f un isomorfismo de orden. ∀x ∈ A

1. x = max(A) ⇐⇒ f (x) = max(B)

2. x es maximal en A ⇐⇒ f (x) es maximal en B.
3. x = min(A) ⇐⇒ f (x) = min(B)
4. x es minimal en A ⇐⇒ f (x) es minimal en B.

Dem.
2)
=⇒)
Sea x maximal en A. Supongamos f (x) no es maximal en B, entonces existe
z ∈ B tal que f (x)  z. z = f (y) para algún y ∈ A ya que f es suprayectiva,
luego x  y pues f preserva el orden, luego x no es maximal. Contradicción.
⇐=)
Supongamos ahora que f (x) es maximal en B. Supongamos x no es maximal
en A, entonces existe y ∈ A tal que x  y, y como f es inyectiva f (x) = f (y)
y f (x)  f (y) ya que f preserva el orden, luego f (x) no es maximal en B.
Contradicción.

Ej.1
(Z, ≤) y (N, ≤) no son isomorfos.
N tiene elemento mı́nimo, el 0 y Z no.

Ej.2
A = {1, 2, 3, 4, 6, 8, 12} B = {2, 3, 4, 6, 8, 12, 24}
x A y ⇐⇒ x/y x B y ⇐⇒ x/y

8 12 24

8 12
4 6

4 6
2 3

1 2 3

min(A) max(A) max(B) min(B).

(A, A )  (B, B )

5
COTAS: INFIMOS Y SUPREMOS

Def.
Sea (A, A ) un conj.p.o. y S ⊆ A.

1. x ∈ A es una cota superior de S ⇐⇒ ∀u ∈ S, u  x.

Sup(S) = {x ∈ A|x cota superior de S}.
2. Si ∃min(Sup(S)) en A se llama supremo de S. (sup(S) = S.) Tiene
que cumplir:
a) ∀y ∈ S, y A x (x es cota superior de S)
b) x A z si z es cota superior de S (la menor de las cotas superiores).
3. x ∈ A es una cota inferior de S ⇐⇒ ∀u ∈ S, x  u.
Inf (S) = {x ∈ A|x es cota inferior de S}.
4. Si ∃max(Inf (S)) en A se llama ı́nfimo de S. (inf (S) = S.) Cumple:
a) ∀y ∈ S, x A y (x es cota inferior de S)
b) z A x si z es cota inferior de S (la mayor de las cotas inferiores).

Ej.
A = {1, 2, 3, 4, 6, 8, 12} x  y ⇐⇒ x/y

8 12

4 6

2 3

Let S = {4, 6}  S = 12 ∈ S S = 2 ∈ S
S no tiene máximo ni mı́nimo.
Sea S = {8, 12}   S S = 4 ∈ S

Ej.
Sea S = {sn |n ∈ N} donde sn es una aproximación de π y sn tiene n decimales.
s0 = 3
s1 = 3,1 S = π S = 3
s2 = 3,14
..
.

6
Prop.
Sea (A, A ) un conj.p.o. y S ⊆ A.

1. Si S tiene máximo x, S = x
2. Si S tiene mı́nimo y, S = y

Dem.

1. y  x, ∀y ∈ S
Sea z una cota superior de S, como x ∈ S, x  z. Luego x = S
2. Análogo.

Cadenas en un conj.p.o.
Sea (A, A ) un conj. p.o. y S ⊆ A.
S es una cadena si la restricción de  a S ( ∩S × S) es un orden lineal.

∀x, y ∈ S, x  y o y  x

Ej.1
A = {1, 2, 3, 4, 6, 8, 12, 24}

24 24 24

8 12 12 12

4 6
4 6

2 2
2 3

1 1 1

S1 = {1, 2, 4, 12, 24} S2 = {1, 2, 6, 12, 24} son cadenas.

Ej.2
S = {Pn |n ∈ N} es una cadena en (P(N), ⊆)
{0} ⊆ {0, 2} ⊆ {0, 2, 4} ⊆ · · ·
P0 P1 P2
S es una cadena infinita.

7
Extensión de un orden parcial

Def. Sea (A, A ) un conj. p.o., un orden ≤ sobre A se dice que es una exten-
sión total de  si cumple:

1. ≤ es un orden lineal
2. ∀x, y ∈ A, x  y =⇒ x ≤ y

Construir una extensión total ≤ de un orden parcial  dado, sobre un conjunto

finito A, se conoce como ordenación topológica de A.

Algoritmo de Ordenación Topológica.

(A, A ) conj. finito p.o. A = a0 , a1 , . . . , an−1 

(0) a0 es cualquier elemento minimal de A.

(1) a1 es cualquier elemento minimal de A − {a0 }.
..
.
(i) ai es un elem. minimal de A − {a0 , a1 , . . . ai−1 }.
..
.

El proceso termina cuando todo elemento de A ha sido elegido.

orden total: a0 ≤ a1 ≤ · · · ≤ an−1 .

Ej.
8
8 12
12

4 6 4

6
2 3
2

3, 2, 6, 4, 12, 8, 2, 4, 8, 3, 6, 12 también es posible.