Definiciones Iniciales

Producto Cartesiano de A × B
A × B = {(a, b) | a ∈ A ∧ b ∈ B }
En particular, si A = B, se escribe A2 = {(a, b) | a ∈ A ∧ b ∈ A}

Relación
Sean A, B Conjuntos entonces R ⊆ A × B es una relación de A a B.

Dominio de R
Dom(R) = {a ∈ A | ∃b ∈ B((a, b) ∈ R)}

Rango de R
Ran(R) = {b ∈ B | ∃a ∈ A((a, b) ∈ R)}

Inversa de R
R-1 = {(b, a) ∈ B × A | (a, b) ∈ R}

Composición de S con R
S o R = {(a, c) ∈ A × C | (a, b) ∈ R ∧ (b, c) ∈ S}

Propiedades Posibles de las relaciones

Reflexiva
∀x ∈ R (x R x )

Simétrica
∀x, y ∈ R ( x R y -> y R x)

Transitiva
∀x,y,z ∈ R ( x R y ∧ y R z -> x R z)

Antisimetrica
∀x,y ∈ R ( x R y ∧ y R x -> x = y)

Irreflexiva
∀x ∈ A ((x, x) ∉ R)

Tricotomia
∀x ∈ A, ∀y ∈ A ( x R y ∨ y R x ∨ x = y)

Relaciones de Orden

Sea R una relación sobre un conjunto A, si R es Reflexiva, Transitiva y Antisimétrica se dice que R es un orden parcial sobre A.
Sera un orden total si ademas cumple que:
∀x,y ∈ A( x R y ∨ y R x)

Si R es irreflexiva y transitiva, se la llama un orden parcial estricto. Si ademas cumple Tricotomia, es un orden total estricto.

Elementos menores y mínimos

Sea R un Orden parcial en un conjunto A, B ⊆ A y b ∈ B. b es el elemento menor en B para R si ∀x ∈ B(b R x ). b es un elemento mínimo en B para R si ∀x ∈ B( x R b -> x = b ).

Nota: Sea R es un orden parcial sobre A y B ⊆ A. Se cumple que si B tiene un elemento menor, entonces este elemento es único, es mínimo y es el único mínimo. ( Sin embargo un elemento puede ser mínimo pero no ser menor. ) Si R es un orden total se cumple que si b es un elemento mínimo de B entonces es el menor elemento de B.

Cotas Inferiores y Superiores

Sea R un orden parcial en A, B ⊆ A y a ∈ A. a es una cota inferior de B si ∀b ∈ B( a R b ). Es una cota superior si ∀b ∈ B( b R a).

Sea U el conjunto de todas las cotas superiores de A, Si U tiene un elemento menor entonces este elemento es la cota superior menor de B.
Sea U el conjunto de todas las cotas inferiores de A, Si U tiene un elemento mayor entonces este elemento es la cota inferior mayor de B.

Cerraduras ( Closures )

Sea R una Relación en A. Sea S ⊆ A x A, si se cumple que: R ⊆ S,  S es reflexiva, ∀T ⊆ A x A( R ⊆ T ∧ T es reflexiva -> S ⊆ T) entonces S es la cerradura reflexiva de R.
De forma equivalente se definen las cerraduras Transitiva y Simétrica..

Relaciones de Equivalencia

Sea R una relación en A. Si R es reflexiva, simétrica y transitiva, se la llama una relación de equivalencia en A.  

Supongamos que A es un conjunto y F ∈ P(A), si se cumple que ∀X ∈ F, Y ∈ F( X ≠ Y -> X ∩ Y = ∅ ) se dice que F es disjunto en pares (pairwise disjoint). Si F cumple que: ∪F = A, F es disjunto en pares, ∀X ∈ F( X ≠ ∅ ), entonces F es una partición de A.

Toda relación de equivalencia establece una partición sobre el conjunto sobre el que esta definida.

Sea R una relación de equivalencia sobre A, x ∈ A. La clase de equivalencia de x respecto a R es el conjunto:
[x]R = { y ∈ A | y R x}
Se define entonces el conjunto de todas las clases de equivalencia sobre A determinados por R como A / R ( A modulo R ) tal que:
A / R = { [x]R | x ∈ A } = { X ⊆ A | ∃x ∈ A(X = [x]R)}

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006