Teoría de Conjuntos para Estudiantes de Ciencias - José Alfredo Amor Montaño - Pedro Samuel

Vista previa del material en texto

T e m a s d e m a t e m á t i c a s
Teoría de 
conjuntos
para estudiantes 
de ciencias
José Alfredo Am or Montano
José Alfredo Amor Montano
T e o r í a d e c o n j u n t o s
PARA ESTUDIANTES DE CIENCIAS
F a c u l t a d d e C i e n c i a s , U N A M
Amor Montano, José Alfredo.
Teoría de conjuntos para estudiantes de ciencias / José 
Alfredo Amor Montano. — 2a ed., reimp. -- México : UNAM, Facultad 
de Ciencias, 2011.
v i i i , 117 p. ; 22 cm. — (Las prensas de ciencias) (Temas de 
matemáticas)
B ibliografía: p. 117 
ISBN 378-970-32-2454-3
1. Teoría de los conjuntos. 2. Lógica simbólica y matemática.
I. Universidad Nacional Autónoma de México. Facultad de Ciencias.
I I . t . I I I . Ser. IV. Ser.
51i.322-scdd20 Biblioteca Nacional de México
Teoría de conjuntos para estudiantes de ciencias 
T edición, 2005 
l4 reimpresión, 2008 
2- reimpresión, 2 de agosto de 2011
© D.R. 2011. Universidad Nacional Autónoma de México.
Facultad de Ciencias.
Ciudad Universitaria. Delegación Coyoacán,
C. P. 04510, México, Distrito Federal. 
editoriales@ciencias.unam.mx
ISBN: 978-970-32-2454-8
Diseño de portada: Laura Uribe.
Prohibida la reproducción parcial o total de la obra, por cualquier medio, 
sin la autorización por escrito del titular de los derechos patrimoniales.
Impreso y hecho en México.
mailto:editoriales@ciencias.unam.mx
A Jitdith Márquez Guzmán
P r e f a c i o
Este libro fue escrito pensando en ser usado como un texto introduc­
torio a la teoría de conjuntos, para estudiantes de ciencias. Sin embargo 
el hecho de que sea introductorio no significa que sea fácil ya que los con­
ceptos se presentan con todo el rigor moderno, en un lenguaje preciso y 
haciendo la distinción entre colección (determinada por una propiedad) 
y conjunto.
Este texto nació de las notas de clase de un curso de Teoría de 
Conjuntos I impartido por el autor en la Facultad de Ciencias de la 
UNAM a un grupo de 18 excelentes estudiantes de matemáticas y física 
en 1993. Este material ya organizado y revisado por el autor, fue escrito 
en Scientific Word para lo cual se contó con la valiosa colaboración de 
Favio Miranda. El texto fue usado y nuevamente revisado y ampliado, 
en otro curso de Teoría de Conjuntos impartido en 1995. El resultado es 
el presente texto.
La introducción es un desarrollo muy intuitivo pero muy riguroso del 
concepto de conjunto, diferenciándolo del concepto de colección o clase 
determinada por una propiedad, ya que todo conjunto es una colección 
o clase pero no a la inversa. También se aclaran algunos prejuicios sobre 
el concepto de conjunto; se precisa el concepto constructivo de conjunto 
y se dan algunos teoremas básicos por ejemplo, que la colección de todos 
los conjuntos no es un conjunto.
En el capítulo uno se desarrolla el álgebra de conjuntos: par orde­
nado, relaciones, particiones y funciones. Ordenes parciales, totales y 
buenos; conjuntos bien fundados y conjuntos con inducción fuerte. Se 
dan relaciones entre estos conceptos generales, por ejemplo un conjunto 
con una relación, es bien fundado si y sólo si cumple inducción fuerte. 
Esto generaliza la relación entre el Principio de Inducción Matemática 
y el principio del Buen Orden.
El capítulo dos contiene la construcción de los números naturales, de
dos maneras, con el objeto de definirlos de un modo natural y probar 
su existencia de un modo general. Se prueban los axiomas de Peano: 
el Teorema de Recursión para números naturales es la parte central de 
este capítulo, que incluye otras caracterizaciones de los naturales y su 
aritmética.
En el capítulo tres se presenta la aritmética cardinal transfinita a 
partir de los conceptos de equipotencia y de dominancia; el Teorema de 
Cantor, la relación entre finitos, infinitos, Dedekind-iníinitos y el Teore­
ma de Cantor-Schróder-Bernstein. Quedan abiertas tres preguntas que 
requieren del Axioma de Elección.
El capítulo cuatro está dedicado al Axioma de Elección, se presentan 
diez equivalentes y se resuelven las tres preguntas pendientes del capítulo 
tres: la dominancia es relación total, todo conjunto infinito es Dedekind- 
infinito y tiene un subconjunto numerable y para todo cardinal infinito 
k, k ■ k = k. Se ve más aritmética cardinal, se prueban el Lema de 
Zorn y el Teorema del Buen Orden y termina con una aplicación y otras 
versiones del Axioma de Elección muy usadas en muy diferentes ramas 
de las matemáticas.
Todos los capítulos tienen variados ejercicios, algunos con sugeren­
cias.
Agradezco a. mis alumnos de los dos cursos mencionados pues me 
permitieron tener esa extraordinaria, sensación de enseñarles teoría de 
conjuntos y compartirla con ellos. Agradezco el apoyo de Fundación 
UNAM para la mitad del proyecto y quiero agradecer especialmente a 
Favio Miranda Perea. su valiosa colaboración, ya que él fue alumno en 
1993 y profesor junto conmigo en 199-5 y sin él este texto no se hubiera 
podido realizar como se pensó. Para la segunda impresión de este libro 
se agregaron algunos comentarios y detalles de definiciones, ejemplos y 
demostraciones, que complementan el original, para lo cual conté con 
la valiosa colaboración de Mariana Martínez González quien corrigió las 
erratas encontradas y elaboró el complemento en LaTex.
C o n t e n i d o
INTRO DUCCIÓ N 1
o.i Acla ra c io n es so br e el c o n c e p t o
DE CONJUNTO....................................................................... 7
0.2 C o n s t r u c c ió n d e c o n j u n t o s .................................... 9
0.3 E l c o n j u n t o u n iv e r s o l o c a l .................................... 13
1 ÁLGEBRA DE CONJUNTOS 18
1.1 PAR ORDENADO................................................................... 19
1.2 R e l a c i o n e s ......................................................................... 20
1.3 Ó rd e n e s p a r c ia l e s , t o t a l e s y b u e n o s;
CONJUNTOS BIEN FUNDADOS E INDUCCIÓN FUERTE. 
PARTICIONES....................................................................... 21
1.4 FUNCIONES ......................................................................... 24
2 LOS NÚM EROS NATURALES, INDUCCIÓN
Y RECURSIÓN 28
2.1 LOS NÚMEROS NATURALES............................................. 29
2.2 EL TEOREMA DE RECURSIÓN PARA NÚMEROS
NATURALES.......................................................................... 43
2.3 S is te m a s d e p e a n o ......................................................... 50
2.3.1. UNICIDAD DE SISTEMAS DE PEA N O ...................53
2.4 A r i tm é t i c a e n l o s n a t u r a l e s ................................. 55
2.5 V a r i a n t e s d e l t e o r e m a d e r e c u r s i ó n .............. 56
3 EQUIPOTENCIA, FINITUD, DO M INANCIA
Y ARITM ÉTICA CARDINAL 61
3.1 EQUIPOTENCIA................................................................... 61
3.2 FINITUD ................................................................................68
3.2.1 OTRAS PROPIEDADES DE FINITOS....................... 71
3.2.2. D e f in ic io n e s a l t e r n a t i v a s d e f i n i t u d . . 74
3.3 D o m in a n c ia ...................................................................... 78
3.4 A r i tm é t i c a c a r d i n a l ....................................................82
4 EL AXIOM A DE ELECCIÓN 92
4.1 A lg u n o s e q u iv a l e n te s d e l a x io m a
d e ele c c ió n ( A E ) .............................................................. 95
4.2 MÁS ARITMÉTICA CARDINAL...........................................106
4.3 UNA APLICACIÓN DEL LEMA DE Z O R N ......................... 114
BIBLIOGRAFÍA 117
I n t r o d u c c i ó n
Un conjunto es una colección de objetos considerada como un todo; 
es decir, considerada como una unidad. Brevemente, podemos decir que 
un conjunto es una multiplicidad considerada como una unidad.
Los objetos que pertenecen a un conjunto se llaman sus elementos 
y estos pueden ser cualquier tipo de objetos que no sean colecciones obien pueden ser conjuntos.
Con la palabra “objeto” . nos referimos a los objetos de estudio de la 
Teoría de Conjuntos (T.C.).
Los objetos de estudio de la T.C. quedan intuitivamente descritos 
con las siguientes ideas:
1 . Si x no tiene elementos, entonces x es un objeto de la T.C.
2. Si x es un conjunto, entonces x es un objeto de la T.C.
3. Los únicos objetos de la T.C. son los descritos en 1 y 2.
Una parte fundamental en el estudio de una teoría cualquiera, es el 
lenguaje de esa teoría y en la teoría de conjuntos en particular, esto 
es muy importante, por lo que daremos una descripción intuitiva de su 
lenguaje como usualmente se presenta en la actualidad:
El lenguaje de la T.C. es un lenguaje de predicados que tiene como 
símbolos lógicos a los siguientes: no (->); y (a ); o (v ); si... entonces... 
(=»); si y sólo si (<£>); para todo (V); existe (3); símbolo de identidad (=); 
variables individuales (x i ,x 2 ,xs,...). El lenguaje tiene como símbolo de 
predicado de dos argumentos'a! símbolo de pertenencia (e).
En el lenguaje de la T.C., las variables x\, X2, x-¿,...., que comúnmente 
denotamos x,y,z,...., varían sobre los objetos de la T.C.. La relación 
binaria que interpreta al símbolo de pertenencia es una relación que se 
aplica entre objetos de la T.C.. Así pues, las únicas afirmaciones simples 
del lenguaje son de dos tipos, la igualdad x — y y la pertenencia x £ y.
Una propiedad es una afirmación en el lenguaje de la T.C. que se 
refiere obviamente a objetos de la T.C.; por ejemplo “3 y (y 6 x)”es una 
propiedad que se refiere al objeto x, y que significa que x tiene al menos 
un elemento.
Todo conjunto está determinado por una propiedad; es decir, para 
todo conjunto A. hay una propiedad, digamos P, tal que:
x e A x cumple P.
Con esta idea, denotamos o abreviamos A, como:
{x | x cumple P }
lo cual se lee: la colección de objetos x tales que x cumple la propiedad P.
Para tener algunos ejemplos, denotemos con 0 a un conjunto que no 
tiene elementos y denotemos con {a, b) a un conjunto cuyos elementos 
son exactamente los objetos a y b. Ejemplos de conjuntos caracterizados 
por una propiedad son:
1. 0 = {x | x x}, es una abreviatura para la caracterización:
x 6 0 x ^ x.
La propiedad es x ^ x.
2. {a, b} — {x [ x = a V x = 6}, es una abreviatura para la caracteri­
zación:
x € {a, b} ^ (x — a V x = b).
La propiedad en este caso es (x = aV x — b).
Así. en general, si B es un conjunto (es decir, suponiendo ya, 
que B es conjunto), la propiedad acerca objetos de la T.C. que 
determina a B es la propiedad “x £ B y‘, es decir:
B = {x i x € B}.
Ahora bien, si P es una propiedad cualquiera (acerca de objetos 
de la T.C.), la notación:
{a: | x cumple P }
es usualmente conocida como la colección o clase de todos los ob­
jetos que cumplen la propiedad P; es decir, es la colección o clase 
determinada por la propiedad P.
Veamos otros ejemplos:
3. Si P es la propiedad “x = x”, entonces {x | x = x} representa, la 
colección o clase de todos los objetos x de la T.C. que cumplen 
x = x; es decir, representa a la colección o clase de todos los 
objetos de la T.C..
4. Si P es la propiedad “x € y" donde y es un objeto fijo de la T.C. 
entonces {x | x € y} representa la colección o clase de todos los 
objetos que pertenecen al objeto fijo y. En este caso, si y tiene 
elementos, la colección anterior representa al mismo objeto fijo y. 
Si y no tiene elementos, la colección anterior representa al objeto 
0 dado antes, ya que en este caso particular, para cualquier x se 
cumple:
x € y (x x)
pues y no tiene elementos.
Nótese en este último caso que si y es el conjunto vacío entonces 
no tiene elementos y
{x | x e y} = y = 0,
pero si y no tiene elementos, no necesariamente es el conjunto vacío 
pues es posible que sea un objeto que no sea conjunto y
{x | x G y} = 0 # y.
Así pues, ser vacío y no tener elementos no son conceptos 
equivalentes si se permite la posibilidad de que existan objetos que 
no sean conjuntos.
5. Si P es la propiedad -‘x ^ x" . ésta determina a la colección 
{x | x x} que representa a una colección que no tiene objetos la 
cual es el conjunto 0.
6. Si P es la propiedad “i = a V i = í)”l entonces {x \ x — a V x = b} 
representa a la colección que tiene a los objetos a y 6 y nada más. 
Tal es el conjunto denotado {a, b}.
Una colección o clase es pues, un modo de referirnos a todos los 
objetos que cumplen una propiedad. Así pues, si
C — { x \ x cumple la propiedad P }
entonces, el decir “¡r 6 C” únicamente es un modo de decir "x cumple 
la propiedad P."
Si C es un conjunto, entonces í:x G C” es una afirmación del lengua­
je de la T.C. Si C no es un conjunto, entonces ;‘x e C”no es una afir­
mación del lenguaje, sino un abuso de él, para abreviar: "x cumple la 
propiedad P.”
Con este modo de hablar para referirnos a { x \ x cumple P }. 
podemos decir entonces de acuerdo a lo aclarado al principio, que todo 
conjunto es una colección o clase de objetos de la T.C. determinada por 
una propiedad. De aquí no se sigue necesariamente la afirmación inversa, 
de que toda colección o clase de objetos determinada por una propiedad, 
sea un conjunto.
El concepto ingenuo de conjunto, consiste en considerar que toda 
colección o clase determinada por una propiedad, sea un conjunto; es 
decir: “para cualquier propiedad P, {x | x cumple P} es un conjunto”, o 
bien, dicho en el lenguaje de T.C. y llamando A a la colección de los x que 
cumplen P, considerar que: “para cualquier propiedad P, 3 AWx(x G A 
<=> x cumple P ).”
Tal concepto es muy “intuitivo”, claro y útil, por ejemplo:
0 = {x | x x}
{a, 6} = {x | x = o V x = b} 
aU b — {x \ x e a V x €: b} 
ac = {x | x ^ a} 
a fll) = {x | x € a A x G b}
P(o) = {x \ Wy (y € x => y € a)}
{a} = {x | x = a}
Ahora bien, si consideramos a la colección B = {x | x £ x}, que 
abrevia i £ 5 » x ^ x , B está determinada por la propiedad “x ^ x” (no 
pertenecer a sí mismo), ¿es B un conjunto?
La noción ingenua dice que sí. Sin embargo, si B fuera un conjunto 
entonces tiene sentido preguntarse si 5 € B o si B ^ B.
Si B G B entonces B £ B. Pero, si B £ B entonces B G B de donde
necesariamente B G B y B ^ B. Lo cual es absurdo. De aquí que B no
es un conjunto. ¿Pero por qué sucede esto? ¿por qué razón este concepto 
de conjunto tan “intuitivo”, tan claro y tan útil, es inconsistente?
Obsérvese que si B — {x | x ^ x} entonces V x ( x G B <=$■ x £ x) .
Sucede que hay una verdad lógica que niega la existencia de tal 
conjunto B y que de hecho niega el principio del concepto ingenuo de 
conjunto.
Una verdad lógica, es una afirmación que es verdad en todos los 
casos posibles; es decir, es verdad independientemente del universo de 
variación de las variables e independientemente de las relaciones involu­
cradas en ella. La verdad lógica a la que nos referimos anteriormente, es 
la siguiente:
“En cualquier universo de individuos y para cualquier relación bi­
naria entre individuos de ese universo, no hay ahí. en ese universo, un 
individuo que tenga esa relación con todos los individuos de ese 
universo, que no tengan esa relación consigo mismos y sólo con esos.”
Simbólicamente, la verdad lógica anterior, se puede representar co­
mo sigue, si R denota la relación binaria cualquiera sobre el universo 
cualquiera, entonces:
~‘3yVx(xRy <í=> ->(xi?x))
Es fácil probar, por reducción al absurdo, que tal afirmación debe 
ser necesariamente verdadera en cualquier interpretación, para cualquier 
universo y para cualquier relación R. En particular, si el universo es el de 
los conjuntos y la relación que interpreta a i? es la relación de pertenencia 
, tenemos entonces que:
-i3yVx(x € y x ^ x)
Pero recuérdese que Vx(x € B -t» x ^ x), de donde la verdad lógica 
mencionada nos garantiza que: no existe B en el universo de los conjun­
tos. Es decir, B no es un conjunto.
Compárese nuevamente el principio de la teoría ingenua de los con­
juntospara la propiedad x f x con la verdad lógica en el caso de los 
conjuntos y la relación de pertenencia.
3yVx(x € y <=> x ^ x) Principio de la teoría ingenua, 
para P = x £ x.
->3yVx(x 6 y ■$> x g x) Verdad lógica.
Queda entonces claro por qué la teoría ingenua de conjuntos, tan 
intuitiva, clara y útil, es inconsistente ¡porque contradice a una verdad 
lógica!. No es un problema teórico conjuntista.
Es sólo un problema de la intuición que contradice una verdad de la 
lógica clásica elemental.
Por todo lo anterior, podemos concluir que todo conjunto es una 
clase, pero no toda clase es un conjunto.
o . l A c l a r a c io n e s s o b r e e l c o n c e p t o 
d e c o n j u n t o
En lo que sigue, haremos la aclaración de algunos prejuicios sobre el 
concepto de conjunto.
1) El concepto aislado de “elemento” no tiene sentido pues no sig­
nifica nada realmente, por lo que no debe existir la confusa división de 
objetos de la teoría de conjuntos, en conjuntos y elementos. La clasifi­
cación que podríamos hacer de los objetos de la teoría de conjuntos es: 
conjuntos y no conjuntos. El primer concepto intuitivo básico es el de 
conjunto y el segundo es la relación de pertenencia o de “ser elemen­
to de”. A los objetos que forman un conjunto, los llamamos elementos 
de ese conjunto. “Ser elemento de” es una relación de dos argumentos, 
también llamada “pertenencia”de un objeto a otro, donde el segundo 
objeto es un conjunto y el primero puede o no ser conjunto. Así pues, 
ser elemento de. es una relación y no una propiedad.
2) Un conjunto puede tener como elementos suyos a conjuntos; de 
hecho un conjunto puede tener solamente a conjuntos como sus elemen­
tos. ya que los objetos que pertenecen a un conjunto pueden ser cualquier 
tipo de objeto de la T.C., en particular conjuntos. Debe observarse que 
cualquier conjunto es elemento de otro conjunto, por ejemplo, del con­
junto unitario que lo tiene a él como su único elemento.
Si A es un conjunto, entonces {̂ 4} denota al conjunto cuyo único 
elemento es A y A 6 {^4}. El conjunto {,4} se llama el unitario de A.
3) Si A es un conjunto, A E A no es un concepto contradictorio. 
Análogamente A 0 A no es contradictorio. La afirmación A € A significa 
que A es un elemento de A, lo cual puede suceder, si A = {A}. La 
afirmación A A significa que A no es elemento de A, es decir, que no 
es elemento de sí mismo; esto sucede por ejemplo con 0 ya que 0 0 0. 
¿Hay conjuntos A tales que A E A ? No se puede dar una respuesta 
definitiva, pues ello depende de la teoría de conjuntos de que se trate, 
pero sí podemos dar una respuesta parcial muy precisa e importante; una
respuesta parcial es que: es consistente suponer que los haya: es decir, 
con la suposición de que existan no se llega a contradicción alguna. La 
siguiente es una representación informal e intuitiva de un conjunto con 
esta propiedad:
^ = ..... }}}}
Este es un conjunto, cuyo único elemento es un conjunto, cuyo único 
elemento es un conjunto, cuyo único...
Así A € A. Desde luego, también es consistente suponer que no los 
haya; es decir, suponiendo que no los hay no se llega a contradicción 
alguna.
4) Si x ,w son objetos de la T.C., entonces el hecho de afirmar que 
x € w es cierto, presupone necesariamente que w es un conjunto, pero 
x puede ser o puede no ser un conjunto. Es posible que se esté abusan­
do del lenguaje y que w sea una clase que no es conjunto; entonces, si 
w = {z \ z cumple P}, es decir, si P es una propiedad que determina a 
w, entonces “x € tu” es simplemente un abuso de lenguaje que abrevia 
la afirmación “x cumple P.”
5) Formalizar aclarando el lenguaje y precisar los enunciados básicos 
o axiomas de la teoría de conjuntos, no necesariamente la vuelve anti­
intuitiva; al contrario, pues al precisar el lenguaje y las suposiciones 
iniciales acerca de los conjuntos, se tiene más claro el concepto de con­
junto y se precisa con todo rigor lo qus se afirma y lo que se prueba 
evitándose ambigüedades y confusiones acerca de una teoría tan básica 
y tan poderosa como lo es la teoría de conjuntos.
6) La idea ingenua de conjunto es una idea equivocada por ser 
contradictoria con la lógica elemental, pues confunde el concepto de 
conjunto con el de clase o colección determinada por una propiedad. 
El concepto correcto de conjunto se adquiere al dejar establecido cómo 
construimos conjuntos.
Las respuestas naturales a la pregunta ¿cómo construimos conjuntos?
serán una serie de procedimientos constructivos mentales con los cuales 
formamos conjuntos; estos procedimientos serán tomados como los 
axiomas constructivos de la teoría. Otros axiomas no constructivos serán 
los que nos especifiquen propiedades fundamentales acerca del concepto 
de conjunto; así, la definición rigurosa de conjunto queda dada por los 
axiomas de la teoría y por el concepto constructivo de conjunto.
0.2 C o n s t r u c c i ó n d e c o n j u n t o s
Un conjunto que podemos construir sin usar objetos en lo absoluto es 
el conjunto que no tiene elementos o conjunto vacío, al cual denotamos 
con 0. (Axioma del Conjunto Vacío).
Ahora bien, dados dos objetos (conjuntos o no) A y B, podemos 
construir el conjunto cuyos elementos son exactamente esos, al cual de­
notarnos como {*4, B} y lo llamamos el par de A y B. (Axioma del Par). 
También podemos construir el conjunto cuyo único elemento es A al cual 
denotamos como {,4} y lo llamamos el unitario de A (caso particular del 
Axioma del Par con A = B). En general para cualquier número finito 
de objetos A\,A<i,...,An construimos el conjunto
{A\,A2, ■■■■ -4n} 
cuyos elementos son exactamente esos.
Si x, y son conjuntos, decimos que x es un subconjunto de y si todo 
elemento de x es elemento de y y esto lo denotamos x C y, en el lenguaje 
de la T.C. esto lo decimos así:
\/z{z £ x =» z £ y)
en tal caso decimos también que x está incluido en y, o que x está con­
tenido en y. Por ejemplo:
{ A } C { A , B } , <DC{A}
0 C X, cualquiera que sea el conjunto X.
Los objetos x y y son iguales si son el mismo objeto y esto lo denota­
mos con x = y. Con x ^ y denotamos que no son el mismo. Como se ha 
visto, lo único que interesa de los conjuntos son sus elementos, así que si 
dos conjuntos tienen los mismos elementos, entonces serán iguales como 
conjuntos. Así, si x y y son conjuntos, x = y significa que x y y son 
el mismo conjunto, es decir, que tienen los mismos elementos: todo ele­
mento de x es elemento de y y todo elemento de y es elemento de x: por 
lo tanto si x y y son conjuntos, entonces x — y significa x C y y y C x. 
(Axioma de Extensionalidad). Por ejemplo:
{A, B} = {B, A }, {A} = {A, .4}, {3,4} = {3 + 1,5 — 2}
0 {4}, 0 yí {0}, Si A B entonces {A} ^ {4, B}
Por esta razón, el conjunto vacío denotado 0 es único.
Si x G A decimos que x es elemento de A o que x pertenece a A
o que A tiene como elemento a x o simplemente que A tiene a x. Si 
A C B decimos que A esta contenido en B o que B contiene a A o que 
A está incluido e n B , o que A es subconjunto de B.
Por lo anterior la expresión “tiene”. es diferente de la expresión “con­
tiene”. Veamos algunos ejemplos:
Sea A — {6, {0}} con 6 ^ 0 . Entonces A tiene a {0} porque 
{0} G {b, {0}}, pero A no contiene a {0} pues {0} no esta contenido en 
A ya que 0 ^ 4 . Por otro lado A contiene a 0, pues 0 C A , pero A no 
tiene a 0 , es decir 0 ^ A . Así pues, A tiene a {0} pero no lo contiene 
y A contiene a 0 pero no lo tiene.
Hemos usado la notación:
{x | x tiene tal propiedad}
para referirnos a la colección de todos los objetos x tales que cumplen 
esa propiedad. Si un conjunto está descrito de esta manera diremos que 
está descrito por comprehensión. Por ejemplo, dados los conjuntos A y 
B , podemos construir los nuevos conjuntos:
AU B = {x \ x € A o x E B ) llamado unión de A y B.
AC\B = { x \ x E A y x £ B } llamado intersección de A y B.
Un conjunto de conjuntos es un conjunto cuyos elementos son todos 
conjuntos. Escomún llamar “familia de conjuntos” a un conjunto de 
conjuntos.
En general dado un conjunto de conjuntos C, podemos construir los 
nuevos conjuntos:
(J C — {x | hay un A 6 C tal que x G A} llamado unión de C 
(Axioma de Unión).
Si C 0. Pl C = {x ¡ para todo A € C ,x € A} llamado intesección 
de C (posteriormente probaremos que podemos construir este conjunto 
usando los axiomas) debe ser claro con estos conceptos y esta notación, 
que:
A u B = \ J { A ,B } y A n B = f ) { A ,B } .
Otra manera de denotar conjuntos es con un conjunto I de índices o 
indicadores, por ejemplo
C = {Ai | i € 1}
denota al conjunto de los objetos A t donde i es el índice, elemento del 
conjunto I, que indica a qué objeto Ai se hace referencia. Si C = {Ai \
i £ 1} donde cada Az es un conjunto, entonces (J C se puede denotar 
también como:
} J C = \ j A i = {x | hay i G I tal que x G Ai}
íei
t
Análogamente, s r f r- 0 :
C — P |Ai = {x | para todo i G / . i S -4t}.
i€l
Una manera muy importante y útil de construir conjuntos es la 
siguiente: dado un conjunto A y una propiedad P, expresada en forma 
precisa con el lenguaje, construimos el conjunto:
{ x G A \ x cumple P}.
(Axioma de Separación o de Comprchcnsión).
Aquí es necesario hacer una observación muy importante, debe ser 
clara la diferencia entre este proceso constructivo que llamamos Axioma 
de Separación, y el concepto ingenuo de conjunto como colección deter­
minada por una propiedad; pues aquí está ya dado un objeto A que es un 
conjunto y consideramos la colección de elementos de A. determinados 
por la propiedad dada P.
Simplemente estamos separando de A, a los elementos suyos que 
cumplen la propiedad P. Al aplicar lo anterior, A puede ser un conjunto 
suficientemente grande para que se considere como universo local o uni­
verso del discurso, pero A debe ser un conjunto ya sea por suposición o 
porque se haya probado antes.
En todos los ejemplos descritos por comprehensión debe haber un 
conjunto previo del cual se hace la separación de los elementos suyos 
que cumplen la propiedad que describe al conjunto. Este es el modo 
más común de describir conjuntos en matemáticas; sólo debe quedar 
claro que la colección de la cual se separa el conjunto, sea un conjun­
to (posiblemente muy grande como para considerarlo nuestro conjunto 
universo), para tener la seguridad de que la colección separada sea un 
conjunto por el axioma de separación.
Otro conjunto que podemos construir, dado un conjunto A. es el 
conjunto
P{A) = {x \ x C A }
llamado potencia de A o partes de A. (Axioma del Conjunto Potencia). 
Nótese que los elementos de este conjunto P(A) son únicamente conjun­
tos ya que son los subconjuntos de A. Nótese también que el símbolo 
C no es un símbolo original del lenguaje, sino que se definió como un 
símbolo de relación binaria tal que:
x Q y <=*> Vz{z G x =>• 2 € y)
E je m p l o s
P(0) = {0} , P ( {0 } ) = { 0 , { 0 } } , P ( { ü ,6}) = { 0 , { a } , { 6 } , { a , 6 } }
Como para todo conjunto A se cumple que 0 C A y que A C A 
entonces 0 6 P(A) y A € P(A).
Si A y B son conjuntos podemos construir el conjunto ‘'diferencia de 
.4 menos B ” denotado con A — B:
A — B = {x \ x E A y x tfí B}
Nótese que {A — B) C A, es decir, (A — B) e P(A). Nótese también 
que-*4 — B = {x € A I x £ B j queda construido a partir del axioma de 
separación, al separarlo de A con la propiedad x f B.
0.3 EL CONJUNTO UNIVERSO LOCAL
Cuando se usa la teoría de conjuntos, se tiene como referencia, ex­
plícita ó implícitamente, un universo del discurso; es decir, un marco 
de referencia dentro del cual se trabaja. Este universo del discurso de los 
conjuntos es lo que se conoce como conjunto universal o universo local y 
debe ser un conjunto. Este concepto es relativo al área de interés en que 
se trabaja; por ejemplo en el análisis real, este universo es el conjunto:
R U P(R) U P (1 U P (1 ))U P (P (S )) U ... U l 2 U P(R 2) U P(P{ M2))
U ... U Rn U P(Rn) UP{P(Rn)) U ...
Ahora podemos definir la operación "complemento relativo”, relativa 
al universo del discurso. Si X es el universo local o conjunto universal y A 
es un conjunto de ese universo, es decir A € X definimos el complemento 
relativo X — A de A respecto al universo X como A c :
Ac = X - A = { z € X \ z <¿A}
Aquí, si suponemos que A £ A. tenemos que A € X — A — Ac.
Obsérvese que X — A C X. Si X es nuestro universo local, debemos 
suponer que A C X, pues todos los elementos de A deben ser de nuestro 
universo, si no, no estarían en nuestro discurso.
Algunas veces, X está implícito o sobreentendido; en este caso se 
escribe A c = {z | z A] pero debe entenderse que cada z tal que 2 G Ac 
está en X, es decir, que A c está incluido en el conjunto universal X.
E je r c ic io i
a) A U (f) B) — 'J C) \ C e B} suponiendo B # 0.
b ) ' A n (U-B) = U Í ( ^ n C ) \ C e B ) .
c) Si 6 € A entonces b C |J A y f"| A C b.
d) Si A C B entonces U A C U B e n - ^ C p l A
e) \ jP (A ) = A y A C P ( \ J A ) .
Obsérvese que P((J .4) A pues si A — { {a, 6}, {c, d} } y 
a 7̂ b, a ^ c,.
b d,b c entonces {b, c} € P ([J A) pero {6, c} ^ A.
f) A C B si y sólo si P(A) C P(B).
g) (A - B) U (B - 4 ) = ( i 4 U B ) - ( i n B ) .
h) X - U A = C\{X - C | C e A}. X es el conjunto 
universo local.
i) X - C \ A = U { X - C \ C & A } . 
j) A C B c si y sólo si A Pi B = 0.
k) A n ( B u C ) = { A n B ) u ( A n C n B c).
1) A = {AC \B) \ j {AC \Bc).
m) Si a 6 B entonces P(a) € -P(-P(U &))•
Sugerencia: Usar (c) y (f).
n) P ( A ) n P ( B ) = P( AHB) .
o) P ( A ) u P ( B ) C P ( A u B ) .
Obsérvese que P(A U B) £ P(A) U P(B).
Sean A = {a, b} B — {b,c} (a 7 ̂b, b ^ c, a ^ c) entonces 
se tiene
{a, c} € P{A U B), pero {a,c} $ P{A) y {a, c} P{B) 
p) X - ( X - A) = A. 
q) X - Ü) = X y X - X = <t).
. r) A u ( X - A ) = X y A n ( X - A ) = 0. 
s) A C j5 si y sólo si X - S C X - A .
t) U ^ - U 5 C U ( . A - B ) p e r o U ( A - B ) ^ U > l - U S . 
u ) n ( ¿ u B ) = ( ( V ) n ( n ¿ ? ) y U ( ^ n 5 ) c ( U A ) n ( U S ) . 
v) n U C = f ] { C ] D \ D e C } y
UC\C C C ) { { J D \ D e C } V t D y D ^ Q .
E J E R C IC IO I I . Probar la equivalencia de las siguientes afirma­
ciones acerca de un conjunto 2 cualquiera. Tales afirmaciones pueden 
ser ciertas o no, dependiendo del conjunto z; si z las cumple, decimos 
que 2 es transitivo.
a) 'ix'iy(si x € y y y £ z entonces x G z)
b) Vy (si y € 2 entonces y C z)
c) [ j z C z
d) z C P(z)
e) U P ( z ) C P ( z )
f) VxVj/(si x E y y y Q z entonces x C z)
g) Z£P( P( Z) )
Algunos ejemplos de conjuntos 2 que cumplen lo anterior son:
i- ( M 0 M W } }
II. { 0 , { 0 } 1{ 0 , { 0 } } }
Algunos ejemplos de conjuntos z que no cumplen lo anterior son:
i- (M W U M ® } } }
I I . { 0 , { 0 } , { 0 . { 0 } , { { 0 } } } }
III. {0,{0, {0}},{{0, {0}}}}-
Se deja como ejercicio al lector verificar que los ejemplos anteriores 
cumplen con lo que se afirma de ellos.
Consideramos de fundamental importancia que haya quedado claro 
que el universo local o universo del discurso es un conjunto, ya que no 
hay que confundirlo con la colección o clase de todos los conjuntos, pues 
dicha colección no es un conjunto, es una colección o clase que no es 
conjunto, a las que se llama también clases propias. Para enfatizar la 
importancia de este hecho, lo demostraremos en seguida.
TEOREMA 1. Para todo conjunto, hay un conjunto que no le 
pertenece.
P ru eb a : Sea A un conjunto cualquiera. Sea
B = {x | x E Ayx £ x}
Entonces B es un conjunto por el Axioma de Separación, ya que 
está separado de A con la propiedad de no pertenecer a sí mismo. 
Obsérvese que:
x E B x E A y x S: x. (*)
Entonces B 0 A, pues si B GA entonces se tiene que:
B é B B E B. pero además
B€A (*)
B 6 B =► B i B.
Como B E B o B f. B. entonces tenemos que:
B E B y B g B o
Por lo tanto B ^ A.o
COROLARIO. Ningún conjunto puede tener como elementos suyos 
a todos los conjuntos. Es decir, el universode todos los conjuntos no es
un conjunto. Es una clase que no es conjunto, o sea una clase propia.
TEOREMA 2. Para toda clase no vacía C de conjuntos, 
p| C = {:r | V y G C (x € y) }
es un conjunto único.
Prueba: Como C # 0, sea w G C. Entonces w es un conjunto y 
P |C = {x | Vy € C{x G y)} = {x G w ¡ Vy G C(x G y)} es un 
conjunto por el Axioma de Separación. Q C es único por el Axioma de 
Ext ensionalidad. □
Obsérvese que no se pidió que la clase o colección de conjuntos C, 
fuera un conjunto; sino únicamente que sea no vacía. De hecho C puede 
ser una clase propia y sin embargo p |C es un conjunto, si C 7̂ 0.
TEOREMA 3. No hay un conjunto x tal que P(x) G P(x).
P ru eb a : Supongamos lo contrario y sea x tal que P(x) € P{x)
g<>o P(x) C x. Sea R = {y € x \ y £ y}. Si x es conjunto. R lo es por 
el Axioma de Separación.
Obsérvese que:
R C x. o R G P(x) C x, o R E x.
— ' O O X ' O O
Pero:
R £ R => R £ R y además 
R ^ R ^ R é x o R ^ R o R g R
f~ r - O O
Así pues R £ R ^ R £ R. T¿ Por lo tanto no hay tal conjunto £.□
C o r o l a r io . No hay un conjunto al que le pertenezcan todos 
sus subconjuntos. Es decir, no existe un conjunto x tal que cumple
V y{ y C x —> y G x). Así pues, si una clase x cumple esto, 
sería una clase propia.
1 A l g e b r a d e c o n j u n t o s
l . l P a r o r d e n a d o
El par ordenado de x y y denotado < x, y > debe construirse de tal 
modo que cumpla:
< x, y > = < z, w > si y sólo si x = 2 y y = w
es decir, si x 7¿ y entonces < x , y > ^ < y , x > lo cual signifi­
ca que el orden es esencial. Hay varias definiciones que cumplen lo 
anterior, cualquiera de ellas sirve; la usual es la siguiente, debida a 
Kuratovuski, 1921 :
< x ,y > = {{x}, {x,y}}
Se puede verificar que si x, y € A, < x, y > € P(P(A))
En general, la n-ada ordenada se define para n > 2 como:
< X i , . . . , X „ > = < < X i j . . . , X n —i > , X n >
y para el caso n = 1, se define < x > = x. Otras posibles definiciones 
del par ordenado de x, y son:
< x, y > = { {x, 0}, {y, {0}}} (Hrbacek Jech, 1978)
< x ,y > = { { {x}.0 }, { {y} }} (Wiener 1914)
Si se intenta generalizar la definición de Kuratowski para una terna 
ordenada (x ,y , z ) como:
( x , y , z ) = { {x } ,{x ,y } , {x ,y , z } } 
no se tendrá éxito, pues fracasa la idea de ordenado; por ejemplo:
( 0,{ 0},0 ) = {{0}, {0, {0}}, {0, {0}}} = {{0},{0,{0}}}.
( 0, 0, {0}) = {{0},{0},{0,{0}}} = {{0},{0, {0}}}.
por lo tanto. ( 0, {0}, 0 ) - ( 0, 0, {0} ) pero los segundos y los terceros 
elementos de las ternas son diferentes: {0} 0 y 0 {0}. Además, para
cualquier a, (a, a, a) — < a, a >; un par sería igual que una terna!.
En lo que sigue, usaremos la definición de par ordenado de Kuratowski. 
Obsérvese que < a, a > = {{a}}.
1.2 R e l a c i o n e s
A partir de los conjuntos A y B podemos construir el conjunto A x B 
de todos los pares ordenados < x, y > tales que x 6 A y y € B. Se puede 
verificar que A x B C P(P(A U B)).
An es el conjunto de todas las n-adas ordenadas de elementos de .4:
A n = (...((.4 x A) x A)... x A) x .4 (n veces A)
Una relación binaria es un conjunto de pares ordenados. Si r es una 
relación, el dominio de r es el conjunto:
Dom(r) = {x \ hay y tal que < i , ¡ / > £ r }
y la imagen de r es el conjunto:
Im(r) — { y \ hay x tal que < x .y > £ r) .
Obsérvese que el dominio de una relación es el conjunto formado por el 
primer elemento de cada par ordenado de la relación y la imagen es el 
conjunto formado por el segundo elemento de cada par ordenado de la 
relación.
El campo de r es el conjunto Carn(r) — Dom(r) U Im(r).
Dada una relación r con Dom(r) C A y Im(r) C 5 , se tiene asociada 
una relación inversa r -1 tal que resulta de invertir los pares ordenados 
que pertenecen a r:
r~l = {< b,a > € B x A \< a,b > e r} 
y se tiene que Dom(r~l ) — Im[r ) C B y /m (r_1) — Dom(r) C A
D E F IN IC IÓ N . Sean r C A x B, s C B x C relaciones binarias 
entonces definimos la relación composición s o r como s o r — {< x, z > |
< x ,y > € r y < y, z > E $ para alguna y £ B} C A x B.
Una relación de n-argumentos, n-aria o de aridad n sobre A es un 
subconjunto de An. Sea r una relación binaria o de aridad 2 sobre un 
conjunto A. es decir r C A2. Obsérvese que:
r C i 2 « Cam(r) C A 
A C Cam(r) <=> Vx € 4̂ 3y € j4(< x,y >€ r o < y , x > 6 r)
Si < z.y > e r, decimos que 2 está r-relacionado con y y también lo 
escribimos como z r y.
1.3 Ó RDENES PARCIALES, TOTALES Y BUENOS;
CONJUNTOS BIEN FUNDADOS E INDUCCIÓN FUERTE.
P a r t ic io n e s
Con “sii”abreviamos “si y sólo si". En lo que sigue, r C A x A.
Definimos:
i) < A, r > es un Conjunto Parcialmente Ordenado (COPO) sii para 
todo x € A, < x, x ><£ r (r antirreflexiva en A) y para todo x , y , z € A, 
si < x, y > E r y < y , z > E r entonces < x, z > G r, (r es transitiva en 
A).
ii) < A. r > es un Conjunto con Tricotomía (C O T R I ) sii para todo
x .y € A, x = y o < x, y > e r o < y, x > £ r , y sólo una.
iii) < A, r > es un Conjunto Totalmente (o linealmente) Ordenado 
{COTO) sii < A, r > es COPO y es COTRI.
iv) < A,r > es un Conjunto Bien Ordenado (COBO) sii < A, r > 
es COPO y para todo x C A, si x ^ 0 entonces ha}' y G x tal que para 
todo z £ x: < y, z > G r o y — z\ tal y se llama el r-mínimo de x.
v) < A,r > es un Conjunto Bien Fundado (C O B F ) sii para todo 
x C A, si x 0 entonces hay y <E x tal que para todo z E x ,< z , y >£ r; 
tal y se llama un r-minimal de x. Obsérvese que puede no sor único.
vi) < A ,r > es un Conjunto con Inducción Fuerte (C O IF ) sii para 
todo x C A, si para todo y € A, el hecho de que todos los elementos de 
A r-relacionados con y estén en x, implica que y G x entonces A C x.
Las seis anteriores propiedades de conjuntos con una relación binaria 
quedan relacionadas entre sí en la forma que indica el siguiente diagrama 
donde las flechas representan implicación:
COIF ------- COBO ------- * CO BF
COPO COTRI
Relación entre órdenes parciales, totales y buenos 
con relaciones bien fundadas e inducción fuerte.
Como ejemplo probaremos dos de las implicaciones anteriores: 
COIF =» COBF.
Sea < A, r > COIF. Sea X C A y X ± 0.
Veamos por reducción al absurdo que X tiene un elemento 
r-minimal. Supongamos que X no tiene un r-minimal. Probaremos que 
(*) Vy G A(yw G A[wry =$■ w G (A — X)) => y G (A — X) ) :
Sea pues y G A tal que Vio G A(wry =>■ w G (A — X)). Si y G X 
entonces como \/w G A{wry => w £ X) , tendremos que y será un
r-minimal en X , contra la suposición; de aquí que y <£. X , es decir, 
y € A — X con lo que queda probado (*).
Ahora, como < A ,r > COIF y (A - X ) C A, se tiene por (*) que
A = A — X de donde, como X C A, X — 0 o" .
Así pues, X sí tiene un r-minimal y < A ,r > es un COBF.a
C OBF => COIF.
Sea < A, r > COBF. Sea X C A. Queremos probar que:
(V y € A(Vw € A(w r y ^ w E X ) ^ y E X)) => A C X.
Supongamos que no se cumple A C. X. Entonces A — X ^ 0 y 
además ( A - X ) C A . Sea pues y un r-minimal en ( A - X ) : entonces 
iw G A(w r y => w f (A - A)); entonces Vw G A(w r y => w G X ), pero 
y $ X, entonces tenemos que 3y G A(Vw G A(w r y =» w G X ) A y ^ X) 
de donde se tiene por contrapositiva que < A .r > es COIF.a
Sea r C A x A :
i) r es la relación diagonal o identidad sii para todo
x ,y G A, < x ,y >G r sii x = y.
Si I cIa denota la relación identidad en A, Id a — {< x ,x > \ x G 4̂}.
ii) r es reflexiva sii para toda x G A, < x . x >G r. En este caso 
A C Cam(r) y por lo tanto Cam(r) = A. Obsérvese que r es reflexiva 
¿ii Id a Q r.
iii) r es simétrica sii para todo x. y G A, si < x, y > G r entonces
< y .x > E r.
Obsérvese que r es simétrica sii r = r _1.
iv) r es transitiva sii para todo x , y , z € A , si < x , y > G r y
< y, z > € r entonces < x, z > G r. Obsérvese que r es transitiva sii
r o r C r.
v) r es antisimétrica sii para toda x , y €. A , si < x . y > E r y
< y, x > E rentonces x — y.
vi) r es una relación de equivalencia sobre A sii r es reflexiva, simétri­
ca y transitiva. En este caso Cam{r) - A. Si r es una relación de
equivalencia sobre A, definimos para cada x E A, el conjunto
[x] = {y |< x, y > € r} llamado la clase de equivalencia de x módulo
r. Es inmediato que [x] = [y] sii < x , y > E r, pues y E ¡y] y r es
simétrica y transitiva. El conjunto cociente de A módulo la relación de 
equivalencia r, es
A / r — {[x] | x € A}.
vii) r es “sin puntos aislados” sii para toda x E A hay y E A tal qucf
< x .y > € r o < y .x > E r. Es decir, para todos, o están r-relacionados 
con alguien o alguien con ellos.
viii) r es euclidiana sii para todo x, y, z E A. si < x ,y >E r y
< x, 2 >€ r entonces < y ,z >E r.
Una partición de A es un conjunto P , P C P(A) que cumple:
1) Para todo x, y E P, si x ^ y entonces x D y = 0.
2) U P = A
3) Para todo x € P, x 0.
Si r es una relación de equivalencia sobre A, entonces 
A / r — {[x] | x E A} es una partición de A. donde [x] = {y j< x, y >E r}. 
Si P es una partición de A, entonces
r = {< x .y > E A x A \ hay a E P tal que x ,y E a} C A x A
es una relación de equivalencia sobre A.
1.4 F u n c i o n e s
Una función es una relación F con la propiedad de que 
para todo x € Dom(F) hay una única y tal que < x .y > E F. Es usual 
llamar a tal única y, el valor de F en x y denotarla y = F(x);
Im ( F ) — {F(x) | x E Dom(F)}, también se denota como F[Dom(F)\.
Decimos que F es función de A en B y lo escribimos F : A —> B, 
si Dom(F) = A. Irri(F) = F[^4] C B y F es una función. Si F es una 
función de A en B, decimos que B es el codominio o contradominio de 
F. Obsérvese que Im(F) C B: así pues, el contradominio de una función 
es cualquier conjunto que contenga a la imagen.
F es uno a uno o invectiva sii para cada y € Im(F) hay una única x 
tal que < x .y > € F (es decir F(x) = y).
Es decir, si x . z € Dom(F) y x ^ z entonces F(x) F(z)\ o bien, 
si x, z 6 Dom(F) y F(x) = F(z) entonces x — z.
F es sobre B o suprayectiva sii Im(F) = B. Claramente toda función 
F es sobre Im(F).
F : A —* B es bivección sii F es uno a uno y es sobre B.
Si F : A —’ B es una función invectiva, la relación inversa de F 
denotada F -1' es una función cuyo dominio es Dom(F~1) = Ivi(F) y 
cuya imagen es Im (F ~ 1) = Dom(F), es decir:
F - 1 : Im(F) -» Dom{F).
Además, F _1 es función invectiva. Si F no es inyectiva, entonces la 
relación inversa de F es una relación que no es función.
Si F : A —* B y G : D —* C, tales que I m ( F ) C Dom(G), entonces 
podemos definir la composición de las funciones F y G, que es una 
función de A en C denotada G o F : A —*• C y tal que para toda x <E A :
■ G o F(x) = G(F(x)). Es decir,
G o F = {< x. y > e Dom(F) x Im(G) | < F(x) ,y > e G }
Es fácil verificar que, si F y G son invectivas, entonces (G o F) es 
inyectiva, y también que si F y G son suprayectivas, entonces (Go F) es 
suprayectiva. Por lo tanto, si F y G son bivectivas. (G o F) es biyectiva. 
Es fácil ver que la composición es asociativa sobre las funciones, pero no 
es conmutativa.
Una operación n-aria o de n argumentos en A es una función de An 
en A.
Si A es un conjunto de funciones, entonces |J A es una función sii
V F, G € A: V x € (Dom(F) n Dom,(G)), F(x) = G(x). Esto último
significa que las funciones de A son compatibles dos a dos.
Es inmediato que Dorn({J A) = y Dorn(F) y que Im(\J A) =
F £ A
U Im(F) en el caso de que U A sea función. Un caso particular es 
F € A
el siguiente: si A es un conjunto de funciones y < A. C> es COTO. 
entonces (JA es una función.
/
E j e r c ic io i i i
1) Pruebe que con las definiciones dadas de producto cartesiano 
y de par ordenado:
a) < x, y > = < z, w > sii x — z y y — w.
b) < x. y > = < y, x > sii x = y.
c) A x B = U {A x { b } \ b e B}.
d) ^ x U JB = U { - 4 x c | c e S } .
e) Pruebe que :
[(W - A) x y] U [W x (■Y - B)] — W x Y - A x B .
f) Sean ^ 4 ^ 0 y C j ¿ 0 entonces: A C B y C C D sii 
A x C C B x D.
2) Verifique que si x .y € A entonces < x .y > G P(P(A)).
3) Verifique que A x B C P(P(A U B )).
4) Pruebe que toda relación de equivalencia sobre un conjunto A 
determina una partición de A. c inversamente. De hecho, dé usted 
una biyección entre el conjunto de todas las relaciones de equi­
valencia sobre A y el conjunto de todas las particiones de A.
5) Toda relación r sobre A cumple lo siguiente:
a) r es relación de equivalencia sii r es simétrica, transitiva y 
sin puntos aislados.
b) r es simétrica y antisimétrica sii r está incluida en la 
relación diagonal o identidad.
c.) r es relación de equivalencia sii r -1 es relación de 
equivalencia.
d) Vx e Dom(r) < x, x >€ r _1 o r y Vy € Im(r)
< y , y > £ r o r ' 1.
e) r es relación de equivalencia sii r es reflexiva y euclidiana.
6) Sea r una relación binaria sobre A , pruebe que:
a) r reflexiva, antisimétrica y transitiva (r orden reflexivo) => 
r — {< a, a > \ a € A} es antirreflexiva y transitiva (orden 
estricto).
b) r es antirreflexiva y transitiva (r orden estricto) => 
r U {< a, a >\ a € .4} es reflexiva, antisimétrica y 
transitiva (orden reflexivo).
7) Pruebe las relaciones de implicación entre órdenes parciales, to­
tales y buenos con relaciones bien fundadas e inducción fuerte, 
dadas en el diagrama correspondiente y que no fueron probadas.
8) Sean F : A -> B y G : B -> C:
a) Si Go F : A —* C es biyectiva. entonces F es invectiva, y 
G es suprayectiva..
b) Dar un ejemplo en el cual G o F : A —>C sea biyectiva 
pero F sea no suprayectiva y G sea no invectiva.
c) Dar un ejemplo en el cual F sea invectiva y G sea 
suprayectiva. pero G o F sea no inyectiva y no 
suprayectiva.
9) Si < A. r > es COBO, B C A y r' = rDB x B, entonces < B,r ' > 
es COBO.
2 LO S NÚMEROS NATURALES,
INDUCCIÓN Y RECURSIÓN
2.1 LOS NÚMEROS NATURALES
Idea intuitiva: que cada natural sea el conjunto de los naturales 
anteriores a él y en ese caso el orden sea la pertenencia.
0 = 0 
1 = {0} = {0}
2 = {0,1} = {0, {0}}
n = {0,1,2,.... n — 1} 
n + 1 = {0,1,2 ,...,n}
O b s e r v a c i o n e s . De los ejemplos anteriores, basados en la 
idea intuitiva, las siguientes propiedades deben de cumplirse si n , m son 
números naturales:
i) < n, €> es un orden total (COTO), (E es una relación 
antirreflexiva, transitiva y total dentro de n).
ii) n € m=> n Q m (rn transitivo).
iii) n < m = > n E m y n C m .
7í
iv) n + 1 = n U {n}.
v) n tiene “n” elementos.
Las siguientes definiciones son para cualquier conjunto de con­
juntos x:
D e f i n i c i ó n . El sucesor de x es x u {x}.
D E F I N I C I Ó N , x es transitivo si y sólo si Vy(y G x => y C x).
E J E R C I C I O . Probar las siguientes equivalencias de la definición de 
conjunto transitivo para un conjunto z:
a) VxVy(si x G y y y € z entonces x G z).
b) Vy (si y G 2 entonces y C z).
c) 1J z C. z.
d) z C P ( z ) .
e) U P(z)<ZP(z).
f) Va:Vy( s i x G y y y C z entonces x C z).
P R O P I E D A D E S D E L O S C O N J U N T O S T R A N S I T I V O S
P R O P O S I C I Ó N 1 . A es transitivo si y sólo si P{A) es transitivo 
P r u e b a :
=í>) Sea A transitivo. Sea x G P{A), entonces x C A.
Sea y € x => y €A ^ y C A o y € PÍA). Así, x C P(A).
■4=) Sea P(A) transitivo. Sea y €A, entonces {y} C A de donde 
{y}€ P(A ) =4> {y} C P(A) ^ y € P{A), así que y C A .n
P R O P O S I C I Ó N 2 . Si A es transitivo entonces U A es transitivo. 
P r u e b a : Supongamos que A es transitivo. Sea x € U A o 3 y € .4 
tal que x G y. Por hipótesis y C A de donde x G A. De aquí es inmediato 
que x C (J A. Así pues |J A es transitivo.
Se observa que el inverso no es cierto, como contraejemplo se tiene 
el siguiente:
Sea A = {0. {{0}}. {0. {0}}}- Entonces (JA = {{0}, 0} es transitivo 
pero A no.
P R O P O S I C I Ó N 3. x es transitivo si y sólo si (J(x U {x}) = x. 
P r u e b a :
=>) Supongamos que x es transitivo.
C)Sea z G U í21 u 3 y G x U {x} tal que z e y
i) y e x z € x (Transitividad de x)
ii) y = x => z € x (Pues z & y)
Así pues, z G x.
2 ) Sea z G x. Como x G x U {x} entonces 2 € [J(x U {x}).
<=) Sea y G x. Entonces y G x U {x}.
Sea z € y z e (J(^ U {x}) y por hipótesis z 6 x. Así y C x 
y x es transitivo. □
E j e m p l o s d e c o n j u n t o s t r a n s i t i v o s
(TI) { 0 . {0} , {{0}} } Donde G no es total ni transitiva.
(T2) { 0 , {0} , { 0 , {0} } } Donde G es total y transitiva.
(T3) { 0 , {0} . { 0 . {0} } . O } Donde fí = {ft}, € es no total
transitiva.
(T4) {g. b, c, b', 0} donde a — {0, b, b'}. b — {0. c. b'}, b' = {0, c}. 
c = {0, a}, con c ^ b , c ^ b ' , G es to tal y no transitiva.
E j e m p l o s d e c o n j u n t o s n o t r a n s i t i v o s
(NT1) { 0 , {{0}} , {0 , {0}} } Donde € es no total transitiva. 
(NT2) { 0 , {0} , { 0 . {0} . {{0}} } } Donde G es total y transitiva.
(NT3) { 0 , { 0 , {0} } . { { 0 . {0} } } } Donde G no es total ni
transitiva.
(NT4) {d , {{d. 0}}, {d: 0}} Donde d = {{{d, 0}}} y G es total no 
transitiva. Aquí d es un conjunto raro, pues pertenece a un 
elemento de un elemento suyo, es decir d € (J U d-
Los ejemplos anteriores muestran que:
i) A transitivo no implica que 6 sea transitiva en A (TI). Y E tran­
sitiva en A no implica que A es transitivo (NTl), (NT2).
ii) A transitivo no implica que E sea total en A (TI). Y E total en 
A no implica que A sea transitivo (NT2)
iii) € transitiva en A 110 implica que E sea total en A (NTl). Y £ 
total en A 110 implica que € sea transitiva en A (NT4).
P R O P O S I C I Ó N 4 . Si A es transitivo y € es transitiva en A entonces 
para cualquier x £ A, x es transitivo.
P ru eb a : Sea- A transitivo tal que E es transitiva en A. Sea x E A. Sean 
z E y y y Ex-,
z E y E x => y E A, z E A 
o z € x pues £ es transitiva en A o x es transitivo.nOO A OO
¿Cómo caracterizar a los números naturales? Los números naturales 
deben ser conjuntos transitivos y bien ordenados por £. Si pedimos sólo 
que sean transitivos no basta. (TI). Si pedimos sólo que 6 sea transitiva 
o total no basta por (NT2).
Para que un conjunto sea un natural pediremos entonces que sea 
transitivo y que la relación £ sea un COBO.
Pero aún con esto no basta pues
{1,2,..., n, n U {n},...}
de ser un conjunto, sería transitivo y € sería un buen orden en él. pero
es infinito y los naturales no lo son. o
Pediremos entonces que todo subconjunto no vacío tenga máximo 
respecto a la relación €, es decir:
Ww[w C a i A t u ^ 0 4 - 3 y E uNz E w(z 6 y V z = y)}
con lo que se tendrá la finitud.
D E F I N I C I Ó N , x es un número natural si y sólo si:
i) x es conjunto transitivo (Vy € x(y C x))
ii) < x, G> es un Conjunto Bien Ordenado (COBO).
iii) Todo subconjunto no vacío de x tiene un G máximo, es 
decir:
Vtu[u) C x A w 0 =>■ 3y G w V2 6 ui(z G y V z = y)] 
T e o r e m a 4
a) Los números naturales no se pertenecen a sí mismos, es decir:
Si x es un número natural entonces x £ x.
b) Los números naturales son conjuntos de números naturales; es 
decir:
Si x -es un número natural,
entonces para cualquier y G x, y es un número natural.
P rueba :
a) Sea x un natural. Si x G x =>■ 3 y G x tal que y G y pero esto 
contradice el hecho de que < x . G> COPO. Así pues x x.
b) Sea x un natural. Sea y G x.
i) y es transitivo: Sea u € v G y. Como x es transitivo se
tiene v G x, y u G x, por ser G transitiva en x se tiene u G y.
ii) < y , G> es COBO , pues y G x =i> y C x (por ser x transitivo)
y como < x, G> es COBO y ser COBO se hereda, para 
subconjuntos entonces < y, G> es COBO.
Ver ejercicio III, 9).
iii) Dado un subconjunto no vacío de y, es un subconjunto no 
vacío de x por lo que ahí tiene un G-máximo (es decir, que 
todo subconjunto tenga un máximo, se hereda).'
Así pues y es un número natural.□
Consideremos la propiedad "ser número natural” y consideremos la 
clase:
N = {x ¡ x es un número natural}
¿N es un conjunto? No lo sabemos, lo veremos más adelante. Obsérvese 
que si N fuera conjunto, sería transitivo pues: x € N =>■ x C N (Teorema
4.b).
Recordemos los Axiomas de Peano. para caracterizar a los números 
naturales:
1) 0 es número natural.
2) Si n es número natural, el sucesor de n es número natural.
3) 0 no es sucesor de ningún número natural.
4) Si el sucesor de n es igual al sucesor de m entonces n — rn.
5) Si A es un conjunto de naturales tal que 0 £ i y para todo
número natural n. si n G A entonces (sucesor de n) € A, entonces 
todos los naturales están en A, es decir, N = A.
Este último axioma se puede ver también como:
5’) Si P es una propiedad acerca de números naturales tal que 0 
cumple P y para todo número natural n, si n cumple P entonces (suce­
sor de n) cumple P, entonces todos los naturales cumplen P.
O bservación. La equivalencia de las dos versiones se tiene así:
5’) => 5) Dado A, P es “x 6 A'' .
5) => 5’) Dada P, A es {x | x 6 N y x cumple P}, y A es conjunto,
si N lo es.
T e o r e m a 5
a) 0 es número natural.
b) Si x es número natural entonces S'(x) = x U {x} es número 
natural.
P r u e b a :
a) Es trivial pues 0 = 0 cumple la propiedad ser número natural, 
por vacuidad.
b) Sea x un número natural. Veamos que x U {x} es número 
natural.
i) x U {x} es transitivo. Sea y € x U {x}, hay dos casos:
y 6 x; por ser x transitivo se tiene i / C i C x u {x} 
y — x; con lo que y — x C x U {x}
ii) € es antirreflexiva en x U {x}. Si y E x U {x}, se tienen los 
casos:
y € x\ con lo que y 0 y por ser 6 antirreflexiva en x. 
y = x; por el Teorema 4 x £ x, es decir y £ y.
iii) € es transitiva en iu { x } . Si u, v, w E xU {x} y suponemos 
que u E v E w, entonces hay cuatro casos:
u, v ,w E x =$■ u E w por ser E transitiva en x.
u, v E x y w = x =>• u E x por ser x transitivo con lo
que u E w.
Los otros dos casos no son posibles:
v = x =£■ x € tü, x transitivo y w 6 x => x € x. 
u — x => x € v. x transitivo y v € x => x € x.
Pero x E x es una contradicción por ser E antirreflexiva en 
x U {x} por ii).
iv) Todo subconjunto no vacío de x U {x} tiene máximo y 
mínimo.
Sea y C x U {x}, y ^ 0. entonces:
y n x = 0=>y = {x} donde x es máximo y mínimo 
de {x}.
y fl x 0, se tiene j / f l i C x ^ j / f l x tiene máximo 
y mínimo y y n x — y — {x} de donde el mínimo de 
y fl x es el E-mínimo de y, aún si x € y. Ahora 
bien, si x E y, entonces el E-máximo de y es x y si 
x £ y. entonces el E-máximo de yDx es el €-máximo 
de y, ya que en este caso y C x y y fl x = y.a
Ya sabemos que 0 E N y que: x S N ^ i U {x} E N. pero 
N = {x | x es número natural } 
es una. clase que no sabemos si es un conjunto. Esto motiva la siguiente
D E F I N I C I Ó N . Un conjunto A se llama inductivo si y sólo si:
i) 0 E A.
ii) Vy (y E A => y U {y} E A).
¿Hay conjuntos inductivos? Obsérvese que si N fuera un conjunto, 
sería conjunto inductivo por el Teorema 5.
O bservación. No se puede probar, con los axiomas que tenernos, 
que haya conjuntos inductivos. Obsérvese que intuitivamente un conjun­
to inductivo es infinito, pues debe tener los siguientes elementos:
0 ;{0};{0,{0}} ;{0,{0},{0,{0}}}
AXIOMA DE INFINITO. “Hay un conjunto inductivo.” Es decir:
3x [0 € £ A y y ( y € x => y Li {y} 6 x)] o bien:
3 x V z [z = 0 V 3 iu (w € x A z = w U {w}) => z e x]
Obsérvese que por el Teorema 2, la intersección de todos los conjuntos 
inductivos, es un conjunto, es decir:
D i x | x es inductivo }
es un conjunto, suponiendo que hay un conjunto inductivo. Por el Teo­
rema 2, únicamente requerimos que haya conjuntos inductivos, no que 
la colección de los conjuntos inductivos fuera un conjunto, pues no lo es 
realmente.
D e f i n i c i ó n . Sea u = p){ x \ x es conjunto inductivo}.
u> es un conjunto por dos razones: el Axioma de Infinito y el Teorema 
2; es inmediato que es un conjunto inductivo, es el menor conjunto in­
ductivo (con el orden de C) y está contenido en todo conjunto inductivo.
TEOREMA 6. Todo número natural pertenece a u>.O bien: Todo 
número natural pertenece a todo conjunto inductivo. 0 bien:
Vx[x número natural => VA(A inductivo x € A)].
O abreviado:
y x £ N V A inductivo (x € A).
O más breve:
N C u) — P) {x | x es inductivo}.
P ru eb a : Por reducción al absurdo. Supongamos que existe x número 
natural y existe A conjunto inductivo, tales que x A. Entonces S(x) — 
x U {x} € N, x G (S(x ) — A) ^ 0 y S(x) - A C S(x).
x e N 
x $ A 
z = max{ y ] 
y = m¡n( S(x) - Aj
S{ x ) - A
Sea pues y el G-mínimo de S(x) — A ; se tiene y C S(x) pues 
y € S(x) y 5(x) es transitivo, además y C A ( pues Vio 6 y(w € A ), 
pues w ¿ S( X) — A ya que y es el G-mínimo de S(x) — A).
Como y G S(x) , por el Teorema 4 b) tenemos que y G N. Si y — 0
entonces, por ser A inductivo, y G A "o. o y ^ 0. Sea z el G-máximo de 
y; como y C A, z G A =? S(z) G A por ser A inductivo.
Veamos que y — S(z), con lo que tendríamos y = S(z) G A o.
C) Sea u G y- u £ ¿>(z) = > u £ z y u ^ z .
Como u, z G y y G es orden total en y. por tricotomía se tiene
2 G u. lo cual contradice el hecho de que z es G-máximo de. y.
Así pues: u G y u G S'(z).
2 ) z £ y y y transitivo => z C y, <>o S(z ) = z U {z} C y.D
COROLARIO. N es un conjunto, N = u>, N es transitivo e inductivo.
P ru eb a : Debe ser claro que N = {x G ui \ x es número natural } 
es un conjunto por el axioma de separación, ya que u> es conjunto. N es 
transitivo por el Teorema 4 (b).
La otra contención, u> C N, se da automáticamente pues N es inducti­
vo por el Teorema 5, y í¿ está contenido en todos los conjuntos inductivos 
(ya que lj es la intersección de todos los conjuntos inductivos). Así pues 
N C u por el teorema 6 y lo C N, por lo ya dicho, por lo tanto N = u>.
COROLARIO (Principio de Inducción Matemática)
Si A C N tal que 0 € A y Vn G N(n € A => S(n) G A) entonces 
A = N.
Debe ser claro que las hipótesis significan que A es un conjunto 
inductivo por lo que u = N C A y entonces A = N.
TEOREMA 7 (Axiomas de Peano)
1) 0 € N.
2) Si x € N entonces S(x ) = x U {x} G N.
3) Vx G N (0 ¿ S(x)).
4) Vx, y G N (S(x ) = S(y) => x = y). Es decir, 5 es invectiva.
5) Si A C N, 0 G A y Yn(n G A S(n ) G 4̂) entonces N Cj A y por 
lo tanto A = N.
P r u e b a :
1) y 2) son una reformulación del Teorema 5.
3) Sea x g N. S(x) — x U { x } 0, pues x G S(x) y x £ 0 .
4) Supongamos S(x) — x U {x} — y U {y} — S(y). Si x ^ y entonces
vl e j / y j / G x ^ x e x o Por ser x transitivo.
De otro modo, si suponemos S(x) = xU{x} = yL){y} = S(y). Como 
sabemos que si x es transitivo, x = U(x u {x}) Y como x .y transitivos 
tenemos:
x = y (x U {x}) = |J ( y U {y}) = y
de donde x — y.
5) Sea A C N tal que 0 G A y Vn G A(S(n) G A). Entonces A es un 
conjunto inductivo, de donde N C A y por tanto N = A.
LEM A . Sean m .n elementos de N. Entonces m G n si y sólo si 
S(m) G S(n). Es decir, la operación sucesor es compatible con G en N. 
P r u e b a : La prueba es por inducción (inciso 5 del teorema 7):
=£•) Sea A = {n E N [ Vm E N(m E n => S(m) G S(n))}.
0 G A. por vacuidad Vm G N (m. £ 0). Sea n 6 A. Sea m E N tal que 
m G S(n) = n U {n}
m E n =$■ S (m ) € S'(n) C S(S(n )) ^ S{m) E S(S(n)). 
m = n => S(m ) — S(n) E S(S{n)) ^ S(m) G S(S(n)).
o S(n) E A.OO V '
<=) Sea B = {n G N | Vm € N (S(m) E S(n) => rn E n)}.
O g B . pues Vm G N(5(m) ^ 5,(0)) yaque S(m) G 0u{0} => S{m ) = 0 'o. 
Sea n G B. Sea. m E N tal que S (m ) G S(S(n)) = S(n) U {5(n)}.
S(rn) E S{n) => m E n C S{n). neB
S(m) = S (n ) => m — n E 5(n) (inciso 4 del teorema 7). 
o S(n) E B .□OO x
LEM A . Para todo n elemento de N. n = 0 o existe un elemento p 
de N tal que n = S(p).
P ru eb a : Sea T = {n € N | n = 0 V 3p E N (n = 5(p))}. Es claro 
que 0 G r .
Supongamos k ET.
Entonces k E N y obviamente 5(fc) G T. Por inducción se llega a 
que T = N.
T e o r e m a 8 . N con la relación G es un Conjunto Bien Ordenado 
(COBO).
P r u e b a :
i) V« G N (n ^ n). Es el teorema 4.
ii) Vn, m,p 6 N(n E m A m E p => n E p). Si n E m y rn € p como p 
es transitivo porque p E N, entonces n E p.
iii) m ,n E N => m E n V n E rn V m = n; y sólo uno de los tres.
Aunque ser relación total o sea < N, G> C O T R I , se sigue de que 
todo subconjunto no vacío tenga primer elemento, es necesario probarlo; 
lo probaremos usando inducción:
- Sólo uno de los tres:
m € n y n E m = $ - m E m ( por ser m transitivo) 'o .
vm £ n y m = n = > m € r n o .
- Al menos uno: Sea A = {n E N | Vm 6 N ( m £ n V n € r a V n = rn)}. 
Veamos que A es inductivo.
• 0 E A. Sea Q = {rn € N | ü E m V m = 0}. Veamos que Q es 
inductivo:
0 6 Q. púas 0 = 0.
Supongamos que m E Q.
0 E m => 0 E m C rn U {rr¿} — S(m) o 0 E S(m). 
m = 0=¿>0e0U {0} = 5(0) = S(m) ^ 0 G S(m).
Así pues S(rn) E Q. Entonces N = Q, es decir, 
V m 6 N ( 0 € m V m = 0). o O g Av y oo
• Supongamos que n E A. Sea m E N
m E n => rn E n U {n} — S(n). 
nCS(n)
m = n = ¥ m — n E n U {n} = S(n).
nErri S(n) E S(m) = m U {m}
( L E M A )
o 5(n) G m V S(n) — m.
Entonces como m € n V n € rn V n — m, tenemos que: 
m £ S{n) V m = S(n) V S(n) £ m. 
o 5(n) 6 A.oo V '
Por lo tanto N = A (pues N = u> está contenido en todo inductivo) 
es decir:
Vn £ N Vm £ N (m £ n V m — n V n £ m).
iv) V M C N , M ^ 0 3 A: £ M Vn £ M (A; £ n V k = n).
Podemos abreviar (k € n V k = n ) como k £ n.
Sea Ai C N y Ai ^ 0. Sea m £ Ai, si consideramos S(m) flAf C S(m),
claramente m £ S'(m) n Aí ^ 0 y 5(m) £ N ya que m £ N. Sea /c el
mínimo de S(m) C\M, con el orden £ en S(m). Entonces k es el £-míni- 
mo de Ai, pues sea n £ M, entonces por la tricotomía ya demostrada 
(iii), n £ 5(m) o n = S(m) o S(m) e n :
n € S(rn) => n € ¿>(m) H Ai = k € n V fc = n.
v ' O O
S(m) £ n => A: £ m. £ S(m) £ n (pues m £ S(m) Pl M)
de donde se tiene A: £ n.
5(rn) = n => k € m € 5(rn) — n o A: € n.
En todos los casos A: £ n. por lo que A: es el 6-mínimo de M .o
COROLARIO. N con £ es un Conjunto con Inducción Fuerte. 
P ru eb a : Se demostró anteriormente que COBO => COIF.a 
Así pues, se cumple Inducción Fuerte para los números naturales, la 
cual podemos expresar como:
VA C N [Vy £ N[Vz(z £ y => z 6 X ) => y £ A] =► N C A]
donde el segundo símbolo £ expresa la relación “menor” y los demás € 
representan pertenencia, aún cuando significan exactamente lo mismo.
O bien como:
WX C N [Vy G N[y
COROLARIO. Sean m. n elementos de N. Entonces m 6 n si y sólo 
si m C n y m ^ n.
P ru eb a : Sean m, n € N.
=>) m € n => m C n (por ser n transitivo) pero m # n pues m G n 
o m C n y m n.OO '
<=) m C n y m = ^ n = > - m € n V n G m (Teorema 8, iii)).
Pero n € m C n = > n € n o 0 m G n.o
OO
Usaremos indistintamente N y w ya que N = u; se probó en el Coro­
lario del Teorema 6. Todo lo dicho para N se puede reescribir con u.
E j e r c i c i o . Usando que < u , e > es un COBO o que es un COIF. 
pruebe el siguiente Principio Especial de Inducción para w.
'iX C o>[Vn € uiBm 6 X (n € m) A Vn 6 u>(s(n) G X => n G X) =>
u; C X j.
E j e r c ic io s
1) Probar que para todo conjunto A:
a) P{A) transitivo => A transitivo.
b) A transitivo e inductivo [JA — A.
2) Sean:
^ = { { W ,0 } ,{{«}}}
a) Calcular |J fl A fl U A Y U f ) f l U •'4'-
b) Para cualquier conjunto B, en general no se tiene ninguna 
de las dos contenciones entre U fl P e D U P-
3) Sea T un conjunto no vacío de relaciones transitivas, es obvio 
que fl T, |J T son relaciones.
a) ¿Es p| T relación transitiva?
b) ¿Es U T relación transitiva?
4) Sea < A, r > COTO, / : A — » A tal que:
\fx,y G A[x r y f (x) r f(y)}
a) Probar que / es inyectiva.
b) Probar el inverso: Vx. y G A[f(x) r f (y) => x r y).
5) Sea S(x) = x U {x}. Pruebe que:
a) Vm, n G u>(S(rri) = S(n ) rri — n).
b) Vm,n G oj(S(rn) € S(n ) 4» m E n ).
2.2 E l TEOREM A DE RECU RSIÓN PARA NÚM EROS 
NATURALES
TEOREMA DE RECURSIÓN PARA NATURALES
Sea A un conjunto, a € A y sea / : A — > A. Entonces hay una única 
función h: u> — > A, tal que:
h( 0) = a 
h(s(n)) = f{h(n ))
Consideremos lo que queremos probar:
0) h existe, es decir, que h es un conjunto.
1) Para todo elemento n d e u existe un x € A tal que
< n, x > G h\ es decir
Dorriih) — w, Im(h) C A.
2) Si < n, x > G h y < n, y > 6 h entonces x = y, es decir que h 
es función.
3) < 0, a > G h: es decir que /i(0) = a
4) Si < n, x > G h entonces < s (n ),/(x ) > £ h\ es decir, que
5) Que tal función sea única.
Dicho algebraicamente: Para cualquier aplicación 0 — » a, y cualquier 
/ : A — » A hay una única extensión que es un homomorfismo
h < u>, s, 0 > — ’< A, f , a >,
es decir
h(s(n)) — f{h(n )) para toda n 6 u y h( 0) = a
DEFINICIÓN. Diremos que v es una función adecuada con 
respecto a / si :
i) v es función, dorn(v) C u>,im(v) C ,4.
ii) Si 0 6 dom(v) entonces t/(0) = a.
iii) Si s(n) G dom(v) entonces n € dorn(v) y v{s(nj) = f (v(n)).
En lo que resta de la demostración diremos que v es función adecuada 
si lo es con respecto a / .
Sea A = { v G P(u x A) \ v es función adecuada }
Observación 1. {< 0, a >} € Á con lo que A 0.
Observación 2. A es un conjunto por Axioma de Separación.
Observación 3. h — [JÁ es un conjunto por la Observación 2) y 
por el Axioma de 1a. Unión.
Observación 4. Aunque (JA es único por Axioma de Ex- 
tensionalidad, este no prueba la unicidad de una función h que cumpla 
el enunciado del teorema, ya que podría haber sido construida de otro 
modo.
Probaremos ahora que tal conjunto h es una función con dominio u; y 
cuya imagen está contenida en A y que cumple lo pedido en el enunciado 
del teorema.
LEMA 1. Cualesquiera dos funciones adecuadas son compatibles, 
es decir, para todas v, w € A y para toda n £ u) se tiene que:
n 6 dom[y) fl dorn(w) =► v(n) = w(n).
P ru eb a : Sean v, w G Á. Es suficiente mostrar que
D = { n € u > \ n £ dom(v) fl dom(w) => v(n) = w(n)}
es un conjunto inductivo, pues entonces N = u; — D y v ,w serán com­
patibles.
- 0 € D. pues supongamos que 0 € dom(v)C\dom(w) como v y w son 
funciones adecuadas se tiene que v(0) — a — t¿>(0).
- Supongamos n G D y que s(n) € dom(v) Pl dom(w), entonces
n G dom(y) H dom(w) y por hipótesis inductiva v(n) = w(n). Como 
v, w son funciones adecuadas v(s(n)) — = f(w(n)) — w(s(n)).
Así s(n) G D.a
LEMA 2. La unión arbitraria de funciones adecuadas es una función 
adecuada.
P ru eb a : Sea B C A. Veamos que (J B es función adecuada:
i) Por el Lema 1, B es un sistema compatible de funciones por lo 
que 1J B es una función.
Además 1J B es una función que cumple:
d o m ( \ jB )= (J dom{v) C u>
v €.B
im(\JB) = [J im(v) C A
v(zB
ii) Supongamos que 0 G dom(lJB) = 1J dom(v), esto implica
v£.B
que 0 G dom(v) para alguna v G B, de ahí que v(0) = a, por lo tanto 
como v C U B, tenemos que (U ^)(0) — y(0) — a-
iii) Supongamos que s(n) G dom([JB) — 1J dom(v), esto im-
v£B
plica que s(n) G d o m (vo) para alguna vo 6 B C A, de ahí que 
n G dom(vo) y vq(s(n)) — f{vo(n)). Como vo G B se tiene tío C (J-B y 
además d o m (vo) C (J d o m (v ) = d o m ( \J B ) , por lo cual n G d o m ({ J B )
y U # 0 0 ) ) = «o(s(n)) = f(vo(n)) = f({JB(n)) .a
LEMA 3. Todo número natural está en el dominio de alguna función 
adecuada. Es decir: para cualquier n € u> existe v G A tal que n 6 
dom(v).
P ru eb a : Basta ver que E — {n G u> | G A(n G dom(v))} es un 
conjunto inductivo.
- ü G E pues {< 0, a >} G A y 0 € dom({< 0, a >}) = {0}.
- Supongamos n G E: sea v € A tal que n G dom(v). Sea
v' - v U {< s(«). >}
es obvio que s(n) e dom(v'). Veamos que v’ G A y en conclusión que 
s(n) G E.
i) v' es función:
- Si s(n) dom(v) entonces v y {< s(n). f (v(n)) >} son funciones 
compatibles y su unión, que es v' es función.
- Si s (n) G dorn(v) entonces n G dorn(v) y ií(s(n)) = f (v(n)) por lo 
que v1 — v G A, es función, además de la definición de v' , dom(v') C u; y 
im(v') C A.
ii) Supongamos 0 € dom(v') — dom(v) U {s(n)}. Entonces como 
0 s(n) tenemos que 0 G dom(v), de donde -¡/(O) — v(0) — a.
iii) Sea s(m) € dom(v') = dom(v) U {s(n)}. Hay dos casos:
- Si s(m) G dom(v) entonces m G dom(v) C dorn(v') y además
v'(s(m) = v(.s(m)) = f{v{m)) = f(v'{m)).
- Si s(m) — s(n) entonces m = n, por lo tanto por hipótesis inductiva, 
tenemos que m = n € dom(v) C dom(v') y de ahí.
v ' ( s ( m )) = i / ( s ( n ) ) = f ( v (n ) ) = f{ v ( m ) ) = f ( v ' ( m ) ) . a
P ru e b a del Teorem a de R ecursión (p rim era versión). Sea
h = U ^- Ya se vió que como A es conjunto, h = (JA es conjunto por 
Axioma de Unión. Así pues, < n, m > G h si y sólo si existe v
€ Á tal que (n = 0 y m = a) o existe p € u que cumple p € dom{v),
n = s{p) y 7Ti = f(v(p))
Por Lema 2, h es función adecuada y por Lema 3, dom(h) = uj .
Así h : uj — *■ A cumple:
h(0) = a 
h(s(n)) = f(h(n))
Unicidad Sean h, h! : u¡ — » A que cumplen
h{0) = h'{0) - a 
h{s(n)) = f(h{n)), h'(s(n)) = f( t i(n))
Entonces como dom{h) = dom(h') — u j , para cualquier n £ ¡j. se
tiene n € dom(h) n dom(h!) de donde por Lema 1, h(n) = h!(n) para
toda n 6 u j . Así pues h — h'a
E J E R C I C I O . Sea f : A — * A y a e A. Entonces por el Teorema, de 
Recursión existe una única función h : u — > A tal que
h( 0) = a 
h(s(n)) = f{h(n))
Pruebe que si / es inyectiva y a f. im(f ) , entonces h es inyectiva.
E j e r c i c i o
a) Probar que hay una única función g : w — ► u tal que,
5(0) = 2 
g{s{n)) = 3 + (g(n))
para toda n € w.
b) Dar un definición explícita de la función g anterior (es decir,
una definición no recursiva) que debe ser de la forma 
g(m) = n 4^ ....
o bien
9 = { < rn, n > |
donde “...."indica una expresión rigurosa y precisa, donde no 
ocurre “<?”.
Prueba del Teorema de Recursión (segunda versión). Sea
B — {G € P(w x A) |< 0, a > G G y Vn G ¿jVt g A
(< n.x >G G =í>< s(n) , f (x) > 6 G)}
O bservación 1. B ^ 0 pues (ui x ,4) € i3. por lo tanto p| B es un 
conjunto.
O bservación 2. B es un conjunto. Aunque esto no es necesario 
para que p| B sea un conjunto, por Teorema 2.
Observación 3. Si definimos g : u x A — > u x A tal que para 
toda n € u> y x £ A, g(< n , x >) = < s (n ) , f ( x ) >, es claro que 
es función pues s, f son funciones respectivamente. Podemos pensar a 
cada G e B, como un conjunto generado o que contiene a lo generado a
partir de {< 0, a >} por la operación g, es decir como el mínimo conjunto
generado por g a partir de < 0, a > . Sea h = p |i?. Es fácil ver que h 
satisface < 0, a > G h y que < n ,x > G h implica < s(n), f ( x ) > G h.
Obsérvese que: h(x) = y <s> < x .y > 6 G para todo G G B. Es obvio 
que im(h) C A.
Sólo resta mostrar que 1) dom(h) = w y 2) h es función.
1) Es obvio que dom(h) C u. Veamos que dom(h) es inductivo:
i) 0 G dom(h) pues < 0, a > 6 h.
ii) Supongamos n G dom(h) entonces podemos encontrar x G A 
tal que < n, x > 6 h pero entonces por la propiedad 
satisfecha por h, < s (n) , f ( x ) > G h de donde s(n) G dom(h).
Así pues u = dom(h).
2) Es suficiente ver que
F = {n G uj | V s c , y < n, x > € h y < n ,y > € h x — y} 
es un conjunto inductivo:
i) 0 € F pues si hubiese x y tales que < 0, x > € h y también
< 0,y > G h entonces a ^ x o a ^ y.
Supongamos sin pérdida de generalidad que a ^ x y sea 
h! = h — {< 0, x >}. Se observa que h! C h. 
h' cumple < 0, a > G h' pues < 0, a > G h — {< 0. x >} ya que
x a.
h' satisface < n ,w > G h => < s(n) , f(w) > € h! pues 
supongamos < n,w > € bl entonces < n ,w > € h por lo tanto
< s (n ) , f (w ) > 6 h, pero como < s(n), f(w) > ^ < 0,x > 
pues 0 s(n) para toda n € u>, se tiene < s(n), f (w) > G b!.
Así pues hl G B y /i' C h y h' t- h. o (Contradice la definición
de /i = H B ). Por lo tanto 0 G F.
ii) Supongamos n G F. Entonces n G w y por 1) n G dom(h) 
por lo tanto hay un único x G A tal que < n, x > E h. 
Sabemos que < s(n). f{x) > G h. Supongamos ahora
< s(n),w > G h y w ^ f(x).
Sea h! = h — {< s(n), >}. Veamos que h' G 5:
h' satisface < 0. a > G h' pues < s(n),w > ^ < 0, a >.h' satisface < m ,v > G =£• < s(m), f ( v ) > £ b! pues 
supongamos < m ,v > G h', entonces < m ,v > G h por lo cual
< s(rri). f(v) > G b!.
- Si s(m) # s(n) entonces < s (m ) , f (v ) > ^ < s(n),w > por 
lo tanto < .s(m). f ( v ) >G /i'.
- Si s(m) = s(n) entonces m — n. por lo tanto
< m, v > = < n. v > pero n G F, entonces v = x,
< s{m), f(v) > — < $(m), f (x ) > por ser / función. Como 
f ( x ) w entonces < s(m), /(u ) > G h'. Así pues h! G B y
/ í 'C / i = f)B pero h! ^ h o Por lo tanto w = f (x ) y s(n) G F.
De lo anterior, F es inductivo, u — F y h es función. 
Unicidad: Sean h, t í funciones que cumplen:
0) h existe; es decir, que h es un conjunto.
1) Para todo elemento n £ ui existe < n ,y > € tí, es decir,
dom(h) = u, im(h ) C A
2) Si < n, x > E h y < n, y > € h entonces x = y; es decir que /i es 
función.
3) < 0, a > € /i; es decir que h(0) = a.
4) Si < > e h entonces < s(ri),f(x) > € h; es decir, que
/i(s(n)) = f(h(n))
Sea D = {n € lo \ h(n) = h'(n)} C Veamos que D es inductivo:
- 0 € D ; por 3, h(0) = a = h'(0).
- Si k e D entonces h(k) = h'(k)\ por 4, h{s(k)) = h'(s(k)) pues 
f(h(k)) = f(h'(k)) por lo tanto s(k) £ D.
Así D es inductivo, w = D y para toda n £ D, h(n) = h!{n) por lo
que
h = t í □
EJERCICIO. Sea h — f]B . como en la prueba anterior; demuestre 
que:
i) < 0, a > £ h
ii) < n ,x > E h => < s(n), f (x ) > E h
E j e r c i c i o . Sean < A ,r >,< B , s > C O TR I y COPO respecti­
vamente, y sea / : A — » B tal que V x, y £ A(x r y => f (x ) s f(y))- 
Entonces probar que:
i) / es inyectiva.
ii) Vx,y £ A ( x r y o f (x ) s f(y))
2.3 Si s t e m a s d e p e a n o
Un sistema de Peano es una terna < N,7 , e > constituida por un 
conjunto N de objetos, una función 7 de un argumento y un elemento e 
£ N que se comportan como los números naturales: cualquier elemento 
es; o "el cero”o es “un sucesor” . Pero podría pensarse así, si e es "el 
cero”y 7 es la “función sucesor”:
e — ♦ 7(e)
Z 1 \
7 n+1(e) 7Í7(e))
\ / 
7n(c) .... «- 73(e)
o asi
e — ♦ 7(e) — ► 72(e)— * ..... — ♦ 7n(e)
/ \
™+ 1 (e) 7 ” + 1 (e)
T I
7 m (e) .... <— 7 n + 2 (e)
o así
e— ■> 7(e)— ♦ 72 (e )— * 7 3 (e )— - ......— > 7 n (e)
o así
e— + 7(e)— ♦ 72(e)— > 73(e)— ♦ 74(e)--- — ♦ 7n(e)— + 
7n+1(e)— ♦ .........
¿Qué queremos?
1) Que e GN
2) Que 7 esté definida en todo N y que sea función con valores en 
N, es decir:
Vx € N 3!j/ £ N tal que < x. y > € 7.
Además:
3) Vx eN e 7(x), es decir e ̂ ¿771(7).
4) 7 n(e) 7 m(e) si n 7 ̂ m ó 7(1) 7(2/) si x ^ </. Es decir, 7
inyectiva.
5) VA C N [e € A y 7 [.A] C A => A = N] (Inducción).
Para que sea único salvo isomorfismo, i.e. sea como los naturales.
Observación. Si se cumple 1), 2), 3) y 4), N será infinito.
Consideremos u>, s : u — > u, 0 e u; entonces podemos considerar la 
terna < í¿ ,s ,0 >. Ya sabemos que esta terna cumple 1), 2), 3), 4) y 5). 
Cabe recordar que s — {< n, n U {n} >| n £ u>} y 0 = 0.
DEFINICIÓN. Un sistema de Peano es una terna <N,7,e> tal que: 
N es un conjunto, 7:N— >N ( es decir 7 C NxN y 7 es función con 
dom(7) = N y im (7) C N ), y e GN tales que:
i) e ̂ im (7).
ii) 7 es inyectiva.
iii) YA C N[e G A y 7 [A] C A =$> N = A}.
Si se cumple e £ A y 7 [A] C A, decimos que A es e-7-inductivo.
TEOREMA 9. < w ,s,0 > es un sistema de Peano.
Ya se probó: Teorema 7. Además se probó que < w,€> es COBO, y 
que s es compatible con £: n £ m o s(n) £ s(m).
2.3.1. UNICIDAD DE SISTEMAS DE PEANO
TEOREMA 10. Sea <N ,7 , e > un sistema de Peano, entonces
< u, s. 0 > es isomorfo a <N ,7 , e >. Es decir, hay una función 
h : ui — • N tal que es inyectiva y suprayectiva y “preserva la estructura” , 
es decir:
1) h(s(n)) — 7 (h(n))
2) h{0) - e
P ru eb a : Como 7 :N— >N y e G N, por el Teorema de Recursión 
para naturales, hay una única h : u — * N tal que:
i) h(0) = e
ii) Vn G ui(h(s(n)) ~ 7 (/i(n)))
Como 7 es inyectiva y e ^ im(7 ), por un ejercicio anterior (después 
de la prueba del Teorema de Recursión), la h es inyectiva. Sólo falta ver 
que h es suprayectiva, es decir. im(h) = N. Sabemos que im(h) C N, 
veamos que im{h) es e-7 -inductivo:
i) e G im(h). pues e = h(0).
ii) Sea x G im{h), de aquí x — h(n) para algún n 6 lo. Entonces 
como 7 es función 7 (x) = 7 {h(n)) = h(s(n)) G im(h).
Así pues, por el inciso iii) de la deñnición de Sistema de Peano, se 
tiene im(h) — N
E J E R C IC IO . Si < N . 7 , e > es un Sistema de Peano, entonces:
7m(7) — N — {e}
Veamos ahora una caracterización del orden de los números natura­
les, utilizando el Teorema de Recursión.
T e o r e m a 1 1 . Sea A ^ 0, T C A x ,4. Si < A . t > cumple:
i) A no tiene r-máximo, es decir Vx G A 3 y G A(x r y).
ii) < A . t > es COBO.
iii) Todo subconjunto no vacío acotado de A. tiene r-máximo. Es 
decir, VB C A si B ^ 0 tal que 3y G AVx G B ( x t y o x - y), entonces
3x e B Vz € B(z t x o z = x).
Entonces < A , t > = < lü,E>
Prueba: Sea a el r-mínimo de A. Sea / : A — > A tal que
Vx 6 A, f (x ) es el r-mínimo de {y € A I x t y} C A.
Obsérvese que a existe y / está bien definida por las hipótesis i) y
ii). Por el Teorema de Recursión, existe una única h : u> — > A tal que:
i) h(ü) = a.
ii) h(s(n)) = f(h(n)).
Obsérvese que: Vx e A, x r f (x ) por definición de f(x) , por lo tanto
Vn € u)[h(ri) r f(h(n)) — h(s(n))}
dado que Vn € u>(h(n) € A) y por la propiedad recursiva de h. Así pues 
tenemos [h(n) r /i(s(n))] para toda n € u.
Veamos que h es isomorfismo:
1) Vm,n € oj [m € n => h(m) r h(n)]. Basta ver que el conjunto
D = {n € u) | Vm (m € n => /i(m) r /2-(n))}
es inductivo:
i) 0 € D pues Vm € u>(m ^ 0).
ii) Supongamos n € £>. Sea m g w tal que m S s(n) = n U {n}.
- S im g n entonces como n £ D se tiene /i(m) r h(n) r h(s(n))
- Si m = n entonces por ser /i función h(m) = /i(n) r /i(s(n)) 
en cualquier caso se tiene s(n) € D.
2) /i es inyectiva y Vm. n G a;(m G n h(m)Th(n)) por 1) y por ser 
<u>,€> y < A, r > COTOS. Véase ejercicio anterior a
la sección 2.3.
3) Veamos finalmente que h es suprayectiva; es decir, irn(h) = A.
Si no fuese así, A — im(h) ^ 0. Sea pues p el r-mínimo de
A — im(h). Entonces B = {q € A \ q t p} está acotado 
superiormente por p y B C im(h). Además B ^ 0 (si no. p sería
m ínim o de A y entonces p = a = h (0) G im(h) o ).
Sea pues q el r-máximo de B (existe por hipótesis iii)). Como 
q t p. ya sabemos que q € irri(h), es decir, q — h(m) para algún 
m G lo. Pero obsérvese que p es el mínimo elemento de A mayor 
que q.
Es decir p — mínimo d e {x £ A \ q t x} (pues si hubiese
p' r p con p' el m ínim o se tendría q r p' r p y q no sería m áxim o
V
de B o ). Por lo anterior,
P ~ /(<?) — f{h{m )) - h(s(m)) € im(h ) o 
así que im(h) — A.
Tenemos pues que h es un isomorfismo y < u, €> = < A. r > .□
2.4 ARITM ÉTICA EN LOS NATURALES
T E O R E M A 12 . Hay una única operación + : w x u> — » lo ta l que:
Vm € ui(m + 0 = m)
Vm, n G u(m + s(n) — s(m + n)).
P ru eb a : Sea m € lo. Inmediato del Teorema de Recursión
con A — lo, a = m> f = s
3! m + ( ) : lo — ► lo
tal que lo cumple.
Ahora definimos + : lo x lo — * lo tal que
Vn, m G Lo(m + n = m + (n))
Queda claro que esta función es única también por el Teorema de Re­
cursión. □
C o r o l a r i o . Vm e w(m + 1 = s{m)).
P ru eb a : Considérese m + ( ) : u> — * lo. Se tiene entonces:
m -)-1 = m + (1) = s(m -I- 0) = s(m).
T E O R E M A 13 . Hay una única operación • : u X ÜJ --- ► (ju tal que:
Vm € u)(m -0 = 0)
Vm, n e u)(m ■ s(n) = m + (m ■ n ))
P ru eb a : Sea m € w.
Inmediato del Teorema de Recursión con A = u, a = 0, f — m + ( ),
3! m • ( ) : uj — > u
tal que lo cumple.
Ahora definimos • : u x ui — > u> tal que Vn. m £ ¡¿{m ■ n = m ■ (n)).
C O R O L A R IO . Vm 6 w (m ■ 1 = rn).
P rueba :
m ■ 1 = m ■ (1) = m ■ (s(0)) = m + ( m ■ 0) = m + 0 = m. 
E j e r c i c i o s
1) La operación + : u x lo — > u> es conmutativa, asociativa y 
0 es neutro.
2) La operación