Relaciones

Sabemos que:

Definición. - Decimos que r es una relación binaria, si r es un conjunto de pares ordenados.

Notación. - Si B=A entonces se dice que r es una relación binaria en A

y se denotara como: (A,r)

Notación. - Decimos que x está relacionado con y si 

lo que se denotara como:  xry

Para cualquier relación se pueden definir los conceptos de Dominio, Imagen, campo, relación inversa y composición.

4.-

a) y b) si n,m tienen el mismo sucesor entonces n=m

5.- Principio del buen orden (PBO)

Centremos nuestra atención en el último axioma, debe de ser claro que lo que dice es que todo conjunto no vacío de naturales siempre tiene un número más pequeño, un pilar por decirlo así, lo más interesante es que esto es equivalente al principio de inducción matemática (PIM), que dice:

Sea P(n) una cierta propiedad para cada natural n

Si 

i)  P (1) es cierta y

ii) Suponiendo que P(k) es cierta se puede demostrar que P(k+1) lo es 

entonces P es cierta para todos los Naturales

o, dicho de otra manera

Demostremos que ambos principios son equivalentes.

PBO implica PIM

Demostración. - 

Suponemos el PBO

Y dada una propiedad P(n) tal que 

Entonces por PBO este conjunto tiene un elemento mínimo llamémoslo s*

 

.

Demostremos ahora la otra implicación

PIM implica PBO

Demostración. - 

Tenemos como hipótesis el PIM y supongamos que:

QED

Para terminar el tema digamos que el principio de inducción lo podemos interpretar como si la propiedad que queremos demostrar en los naturales fueran un conjunto de piezas de domino acomodadas para caer, tenemos que tener una pieza inicial (el 1) y dada la n-esima pieza la n+1-esima pieza tiene que acomodarse bien para que pueda darse la secuencia de caída.

Si todo está bien acomodado la propiedad será verdad para todas las piezas (los naturales).

Ejemplos

Dada la siguiente proposición

Demostrémosla usando el PIM