CONTENIDO

1. conceptos elementales 2. el par ordenado y el producto cartesiano 3. Relaciones 4. Funciones 5. Familias 6. Funciones definidas en conjuntos potencia 7. Aplicaciones de funciones 8. Los números naturales 9. Orden 10. Los axiomas de Choice y el Lema de Zorn’s 11. El buen orden 12. Recursión transfinita y similitud. 13. Ordinales 14. Cardinales

Respuestas Referencias

CAPITULO 1 CONCEPTOS ELEMENTALES

1.0 x A∈ Se lee x es un elemento del conjunto A

x A∉ Se lee x no pertenece al conjunto A Axioma de extensión. A B= significa x A∈ si y solo si x B∈ . Definición de subconjuntos. A B⊂ significa si x A∈ entonces x B∈ A B⊄ significa A B⊂ y A B≠ , A es un subconjunto propio de B Si es una condición, entonces ( )S y { ( )}x y S y∈ si y solo si ( )S xAxioma de Especificación. Si A es un conjunto y es una condición, entonces ( )S x{ ( )}x x y S x∈ es un conjunto. Axioma de paridad. Si A y B son conjuntos, entonces existe un conjunto C tal que

y A C∈ B C∈

Definición de Par. { , } { }A B x x A o x B= ∈ ∈ Axioma de unión. Si C es un conjunto, entonces existe un conjunto U tal que si x X∈ para alguna , entonces X C∈ x U∈ . Definición de Unión. {C x x X= ∈U para alguna }X C∈

Definición de Intersección. Para C ≠∅ . {C x x X= ∈I para toda }x C∈ .

Definición de Complementos Relativos. { }.A B x x X y x B− = ∈ ∉ Si el conjunto A esta comprendido, denotamos A B− por B′ . Axioma de potencia. Si E es un conjunto, entonces existe un conjunto tal que si P

,X E⊂ entonces X P∈ . Definición de conjunto potencia. { }E x x E℘ = ⊂

Definición de conjunto vacío { }.x x x∅ = ≠ 1.1 Los siguientes símbolos son menudo utilizados para estudiar el álgebra de las

sentencias

∧ representa y ∨ representa o ¬ representa no

⇒ representa si…entonces…implica representa sí y solo sí ⇔

∃ representa existe para algún ∀ representa para todo

estos Simbolos son empleados de acuerdo a las siguientes reglas de construccion para sentencias. Si p y q son sentencias, entonces , , , ,p q p q p p q p q∧ ∨ ¬ ⇒ ⇔ son sentencias. Si p es una sentencia, entonces : , :x p x p∃ ∀ son sentencias. Por ejemplo, dado que , ,p q r son sentencias, se verifico que [( ) ]p q r¬ ∧¬ ∨ es una sentencia en el siguiente sentido. es una sentencia; por lo tanto q q¬ es una sentencia. p y son q¬

sentencias; por lo tanto p q∧¬ es una sentencia. p q∧¬ y r son sentencias por lo tanto es una sentencia es una sentencia. ( )p q∧¬ ∨ r [( ) ]p q r¬ ∧¬ ∨

El valor verdadero de las sentencias construidas de los primeros cinco símbolos son determinados formalmente de la definición de la tabla de verdades. Se tiene (utilizando 1 como un símbolo de verdadero y 0 como un símbolo de falso):

1 1 11 0 00 1 00 0 0

p q p q∧

1 1 11 0 10 1 10 0 0

p q p q∨

p q¬

1 00 1

1 1 11 0 00 1 10 0 1

p q p q⇒

1 1 11 0 00 1 00 0 1

p q p q⇔

Por ejemplo, si p es una sentencia falsa y q es una sentencia verdadera, entonces

,p q p q∧ ⇔ son falsas y p q⇒ , p q∨ , p¬ son verdaderas. Dos sentencias con el mismo valor verdadero son equivalentes ( = ). La equivalencia puede ser sistemáticamente verificada usando la tabla de verdades iterativamente como en estos ejemplos.

p q p⇒ ≡¬ ∨ q La columna para p q⇒ y la columna para p q¬ ∨ contienen los mismos valores

verdaderos

1 1 1 0 11 0 0 0 10 1 1 1 10 0 1 1 1

p q p q p p q⇒ ¬ ¬ ∨

p q q⇒ ≡¬ ⇒¬q 1 1 0 1 11 0 1 0 00 1 0 1 10 0 1 1 1

p q p q p p q⇒ ¬ ¬ ∨

( ) ( ) (p q r p q q r∧ ∨ ≡ ∨ ∨ ∧ ) ( ) ( ) ( )

1 1 1 1 1 1 1 11 1 0 1 1 1 0 11 0 1 1 1 0 1 11 0 0 0 0 0 0 00 1 1 1 0 0 0 00 1 0 1 0 0 0 00 0 1 1 0 0 0 00 0 0 0 0 0 0 0

p q r q r p p r p q p r p q p r∨ ∧ ∨ ∧ ∧ ∧ ∨ ∧

Usando la tabla de verdades, probemos cada equivalencia siguiente.

)) ( )) ( ))) ( )) ( )) ( ) () ( ) ())) ( ) ( ) () ( ) ( ) () ( )

a p q p qb p q p qc p q p qd p q p qe p q p q pf p q p q qg p q p q r rh p q p q q pi p q q pj p q q pk p q r p q p rl p q r p q p rm p p

⇒ ≡ ¬ ∨⇒ ≡ ¬ ∧¬∨ ≡ ¬ ¬ ∧¬⇒ ≡ ¬ ⇒¬⇒ ≡ ∧¬ ⇒¬⇒ ≡ ∧¬ ⇒⇒ ≡ ∧¬ ⇒ ∧¬⇔ ≡ ⇒ ∧ ⇒∧ ≡ ∧∨ ≡ ∨∧ ∨ ≡ ∧ ∨ ∧∨ ∧ ≡ ∨ ∧ ∨

≡ ¬ ¬

))

))

) ( ) ( )) ( ) ( )))

n p q r p q ro p q r p p rp p p pk p p p

∧ ∧ ≡ ∧ ∧∨ ∨ ≡ ∨ ∨∧ ≡∨ ≡

Estos ejercicios sugieren como la lógica es formalizada. Los estudiantes interesados en la materia deberán de consultar un libro de lógica.

1.2 Las expresiones ∀ y se relacionan de la siguiente manera: ∃ :x p∀ es

equivalente a ( : )x p¬ ∃ ¬ , o en palabras, (para toda x, p es verdadero) es equivalente a (este no es el caso de que haya una x tal que p sea falso). Probar esta equivalencia: ( ) : ( )x x X x Y¬ ∀ ∈ ⇒ ∈ es equivalente a ( ) : ( )x x X x Y∃ ∈ ∧ ∉ . Escrita fuera un resumen de estos teoremas usando la palabra subconjunto. Demostración.

X no es subconjunto de Y si y solo si hay un miembro de X que no este en Y 1.3 Pruebe que la igualdad para conjuntos es reflexiva, simetrica y transitiva; esto es

pruebe estos teoremas: a) X X= para todo conjunto X . b) Si ,X Y= entonces ,Y X= para todo conjunto , .X Y c) Para todo conjunto, , ,X Y Z si X Y= y ,Y Z= entonces X Z= Demostración a) .x X x X X X∈ ⇔ ∈ = por el axioma de extensión. b) x X x∈ ⇔ ∈Y es equivalente a x Y x X∈ ⇔ ∈ c) ( )x X x Y∈ ⇔ ∈ y ( )x Y x Z∈ ⇔ ∈ implica ( ).x X x Z∈ ⇔ ∈

1.4 Pruebe que la inclusión para conjuntos es reflexiva, antisimetrica, y transitiva;

esto es, pruebe estos teoremas a) X X⊂ para todo conjunto X .

b) X Y y Y X⊂ ⊂ implica X Y= para todos conjuntos , .X Y c) para todos conjuntos, , , .X Y Z si X Y y Y Z⊂ ⊂ entonces .X Z⊂ Demostración. a) x X∈ implica x X∈ . b) Si ,x X∈ entonces ,x Y∈ y si ,x X∈ entonces x X x Y∈ ⇔ ∈ . c) Si ,x X∈ entonces ,x Y∈ y ,x Y∈ entonces x Z∈ implica, si ,x X∈

entonces x Z∈ .

1.5 Sea .A B y B C⊆ ⊆ Pruebe que .A C⊆ Demostración Sea entonces esto es posible ya que c C y c B∈ ∉ B es un subconjunto propio de

ya que si entonces .C ,c A∉ ,c A∈ .c B∈

1.6 Sea .A B y B C y C A⊂ ⊂ ⊂ Pruebe que .A B C= = Demostración Para probar que A B= , solo necesitamos demostrar que todo miembro que pertenezca a B también es un elemento de .A

1.7 Sea Definimos .P U y Q U⊂ ⊂ ´ { } ´P x x U y x P y Q= ∈ ∉ similar. Pruebe que Pruebe además que ´P Q Q P⊂ ⇔ ⊂ .́ ( ´) .́P P=

Demostración. (si p entonces q) ( )) es equivalente a ( ) es equivalente de .

(si no q entonces no p y no no pp

1.8 Pruebe que .P∅⊂ Pruebe que P P⊂∅⇔ =∅

Demostración. El argumento ( , puede ser demostrado ciertamente. Si este argumento fuere falso, entonces podria existir un tal que Pero esto no puede ser ya que

)P

si x entonces x P∈∅ ∈y .y y y∈∅ ∉

.y∉∅ Por tanto .P∅⊂ 1.9 Por definición { }P Q x x P o x Q P Q∪ = ∈ ∈ = U{ , }

{ }P Q x x P y x Q P Q∩ = ∈ ∈ = I { , } Si P y son conjuntos, entonces pruebe que y Q P Q∪ P Q∩ son conjuntos.

Demostración. P y son conjutos implica que { es un conjunto por los axiomas de paridad, que en general implica que por el axioma de la unión y especificación.

Q }

X

P y Q{ , }.P QU

1.10 Pruebe que es un elemento neutral para la unión de conjuntos, i.e.,

∅

X X∪∅ =∅∪ =

Para todo conjunto .X Demostración. ( es equivalente a ()∅ ),x X o x∈ ∈ x X∈ ya que (x )∈∅ es siempre falso.

1.11 Sea X Y X∪ = para todo conjunto Pruebe que .X .Y =∅ Demostración. Si X Y X∪ = para todo conjunto ,X entonces .Y∅∪ =∅ Pero Por tanto

.Y Y∅∪ =.Y =∅

1.12 Pruebe que .X X∩∅ =∅ ∀

Demostración. (x X y x∈ ∉ )∅ ), es equivalente a (x∈∅ ya que ( )x∈∅ es siempre falsa.

1.13 Pruebe los siguientes teoremas: a) La conmutabilidad de la unión, . P Q Q P∪ = ∪b) La conmutabilidad de la intersección, .P Q Q P∩ = ∩ c) La asociatividad de la unión ( ) ( )P Q R P R Q∪ ∪ = ∪ ∪ .

.d) La asociatividad de la intersección ( ) ( )P Q R P R Q∩ ∩ = ∩ ∩ e) La distribución de la intersección con respecto a la unión

( ) ( ) ( )P Q R P Q P Q∩ ∪ = ∩ ∪ ∩ .

.f) La distribución de la unión con respecto a la unión

( ) ( ) ( )P Q R P Q P Q∪ ∩ = ∪ ∩ ∪g) La indempotencia de la unión .P P P∪ =h) La indempotencia de la intersección .P P P∩ = La solución probablemente salga mas fácil utilizando las equivalencias de 1.1: a) 1.1j, b) 1.1i, c) 1.1o, d) 1.1n, e) 1.1k, f) 1.1l, g) 1.1q, h) 1.1p.

1.14 Definimos, 1 0 {0},= ∪ 2 1 {1}= ∪ , 3 2 {2},= ∪ probar que 0, 1, 2, 3, son

conjuntos, estos conjuntos que son de notados por el símbolo para la no negatividad entera se muestran con frecuencia en estos ejercicios. Demostración. Sea A un conjunto. 0 { | }x x A y x x= ∅ = ∈ ≠ es un conjunto por el axioma de especificación. {0} es un conjunto por el axioma de paridad. 1 { es un conjunto por el axioma de unión y especificación. El mismo argumento se repite con 1, 2, 3, 4 sucesivamente remplazando 0.

0,{0}= U }

1.15 Exprese el conjunto $ usando solo los símbolos {,}, ∅ , , .

Solución 4 { ,{ },{ ,{ }},{ ,{ },{ ,{ }}}}.= ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅

1.16 Pruebe cual de estas sentencias es cierta o falsa:

)1 2 ) 1 2 0 ) (0 2) 1.)1 2 )1 2 2

a c eb d

∈ ∩ = ∩⊂ ∪ =

∈

{ }.

Solución. Solo c) es falsa. 1.17 En orden de generalizar la construcción de 1.14 asuma una secuencia intuitiva de

números Naturales conocido y demuestre por inducción matemática. Para cada numero natural n de fina un conjunto como sigue: nS 0 1, n n nS S S S+ = ∪ Pruebe que si

es un conjunto, entonces nS 1nS + es un conjunto. Concluir que es un conjunto para cada numero natural n. Finalmente, identificar n y ; Esto es, use el símbolo n para denotar él numero natural como intuitivamente se entendió y el conjunto construido. Estos conjuntos, 0, 1, 2, 3,… se usaran en ejercicios siguientes.

nS

nS

Solución.

La demostración es similar a la hecha en 1.14. 1.17.1 De cual de los siguientes conjuntos es x un miembro, x un subconjunto, x

ningún miembro y ningún subconjunto? ) {{ }, } ) { } {{ }}) ) { }) ) { } { }.

A x y D x xB x E x xC x F x

−∪

∅∩ ∪ ∅

Solución. x es un miembro: D, E, F. x es un subconjunto: B, E. x no es ningún miembro ni un subconjunto: A, C. Los miembros del conjunto x no se dan aquí y la respuesta esta en base a que x x∉

1.19 Demostrar que ) {{ , , }, { , , }, { , }} { , , , , , }) {{ , , }, { , , }, { , }} { }) {1} 1) {1} 1) { }) { } .

a a b c a d e a f a b c d e fb a b c a d e a f acde A A para todos los conjuntos Af A A para todos los conjuntos A

==

====

UIUIUU

1.20 Exprese los siguientes conjuntos usando los conjuntos 0, 1, 2, etc.

, , , , , ,∅ ∅ ℘∅ ∅ ℘℘∅ ∅ ℘℘℘∅U UU UUU .

Solución. 0, 0, 1, 0, 2, 0, {0, 1, 2, {1}}. 1.21 Sea {{2,5}, 4,{4}}. ( 4).X encuentre X= −I U

Solución. 4. 1.22 Construir ( 1)´ ´ 3donde A A℘ = −U para cualquier conjunto A

Solución. {1, 2}.

1.23 Construir ( 2 2)℘ −I U Solución. 0.

1.24 Sea construir {{{1, 2},{1}},{{1,0}}}.X = , , , , .X X X X XU I UU I I I U Solución. {{1, 2},{1},{1,0}}, 0, 3, no definidos, 0, {1}.

1.25 Sea construir {{1, 2},{2,0},{1,3}}.X = , , , , .X X X X XU I UU I I I U Solución. 4, 0, 3, no definidos, 0, 0.

1.26 Sea subconjuntos de U y sea el complemento relativo ( ´) con respecto a U Entonces pruebe lo siguiente:

, ,P Q R

) ´) ´) ( )́) ( )́) ( )́ (

a P Q P Qb P Q P Q Uc P Q P Q Pd P Q P Q Qe P Q P Q R R

⊂ ⇔ ∩ =∅⊂ ⇔ ∪ =⊂ ⇔ ∩ ⊂⊂ ⇔ ∩ ⊂⊂ ⇔ ∩ ⊂ ∩ ´).

)

Solución. El ejercicio 1.1 contiene notables equivalencias. 1.27 Pruebe que .A B A B A∪ = ⇔ ⊂

Solución. La sentencia ( ´x A o x B x A∈ ∈ ⇔ ∈ es equivalente a la sentencia ( )x B x A∈ ⇒ ∈ , que se puede verificar fácilmente utilizando la tabla de verdad.

1.28 Pruebe que .A B A A B∩ = ⇔ ⊂ Solución. La sentencia ( )x A y x B x A∈ ∈ ⇔ ∈ es equivalente a la sentencia ( ).x A x B∈ ⇒ ∈

1.29 De un ejemplo de dos conjuntos ,A B tal que ( ) ( ) ( ).A B A B∩ ≠ ∩I I I Por ejemplo, {1}, {0,1}.A B= =

1.30 Pruebe que ( ) ( ) ( ).A B A B∩ ⊂ ∩I I I Solución.

( ) ( ) ( ).x A B x∈ ∩ ⇒ ∈I I I A implica que para toda X si X A∈ y X B∈ entonces .x X∈ Implica que para toda X A B∈ ∩ uno tiene .x X∈ que en seguida implica que ( ).x A B∈ ∩I

1.31 De un ejemplo de dos conjuntos ,A B tal que ( ) ( ) ( ).A B A B℘ ∪ ≠ ℘ ∪ ℘

Solución. {1, 2} {0,1} {0, 2}.{1, 2} {0,1, 2}.∉℘ ∪℘ ∈℘

1.32 Asumiendo una región conocida de, los números reales, que subconjuntos están descritos aquí? 2{ | 2} { | | 2 | | 3 |}.x x x x x> ∩ − < + Solución. ( 2, )∞

1.33 Definimos a ( ) ( )A B A B B A+ = − ∪ − como la diferencia simétrica de los conjuntos .A y B Pruebe lo siguiente:

))) ( ) ( )) ( ) ( ) ())) .

a A Ab A B B Ac A B C A B Cd A B C A B A Ce A B A Bf A B A Bg A C B C A B

+∅ =+ = ++ + = + +∩ + = ∩ + ∩− ⊂ += ⇔ + =∅+ = + ⇒ =

)

1.34 Pruebe que { }A es un conjunto sin usar el axioma de paridad, dado que A es un

subconjunto.

Solución. { | }x x A y x A∈℘ = es un conjunto usando el axioma de potencia y de especificación.

CAPITULO 2 EL PAR OREDENADO Y EL PRODUCTO CARTESIANO

1.0 Definición del Par Ordenado. ( , ) {{ }, { , }}.a b a a b=

Definición de Producto Cartesiano. { | ( , ) lg lg }.A B x x a b para a un a A y a un b B× = = ∈ ∈

2.1 Construir los siguientes conjuntos:

) 2 3 ) 2 1 ) 1 1) 2 3 ) 1 2) 2 3 ) 0 1

a d gb ec f

∪ ×∩ ×× ×

×

Solución. a) 3, b) 2, c) {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)}, d) {(0,0), ( 1,0)}, e) {(0,0),(0,1)}, g){(0,0)}.

2.2 Demuestre que { , }x y no puede interpretarse como la definición para un par ordenado; demostrar que esta no tiene la propiedad ( , ) ( , )x y a b x a= ⇔ = y

y b=Solución. Si x b= y y y a= ,a b≠ entonces { , } { , }x y a b= y x a≠ y .y b≠

2.3 Un par ordenado es por definición un conjunto. Mostrar por ejemplo que no todo par ordenado tiene dos miembros. Solución. El par ordenado ( , )x x tiene solo el miembro { }.x

2.4 Pruebe esta preposición falsa: X Y Y X× = × para todo conjunto ,X Y El producto cartesiano es no conmutativo. Solución. Si y {0}X = {1},Y = entonces X Y Y X× ≠ × ya que

ya que 0 1(0,1) (1,0). 0 1,≠ ≠ .0 0y∈ ∉

2.5 Pruebe que el producto cartesiano es no asociativo. Solución. Si entonces {0}, {0}, {1},X Y Z= = = ( ) ( ).X Y Z X Y Z× × ≠ × × ( ) {((0,0),1)}; ( ) {(0, (0,1))}.X Y Z X Y Z× × = × × = (0,0) 0.≠

2.6 Dar un ejemplo de dos conjuntos ,X Y tal que .X Y Y X× = × Solución. Tomando al conjunto vació ∅

2.7 Pruebe que el producto cartesiano es distributivo con respecto a la unión: ( ) ( ) ( ) , , .X Y Z X Y X Z X Y Z× ∪ = × ∪ × ∀

Solución. ( , ) ( ) ,x y X Y Z x X∈ × ∪ ⇔ ∈ y y Y Z x X∈ ∪ ⇔ ∈ y ( ) ( ) ( ) ( , ) ( , )y Y o y Z x X y x Y o x X y x Z x y X Y o x y X Z∈ ∈ ⇔ ∈ ∈ ∈ ∈ ⇔ ∈ × ∈ × ⇔( , ) ( ) ( ).x y X Y X Z∈ × ∪ ×

2.8 Dar ejemplos de conjuntos tales que ( ) ( ) ( ).X Y Z X Y X Z∪ × ≠ ∪ × ∪

Solución. 1, 0.X Y Z= = =

2.9 Pruebe que ( , ) .x y x=I I Solución. {{ },{ , }} { }a x x y a x∈ ⇔ ∈I y { , }a x y∈ si a x= y ( ´a x o a y= = )

a x⇔ = 2.10 Pruebe [ ( , )] [ ( , ) ( , )] .x y x y x y∪ −I U UU UI y=

Solución. Pruebe primero que ( , ) { , }.x y x y=U Entonces a∈ ( { , })x yI ∪ ( { , } { })x y x−U U (a x y a y)⇔ ∈ ∈ o (( ´ )a x o a y∈ ∈ y

y o ) (a x a x∉ ⇔ ∈ )a y∈ .a y a y∈ ⇔ ∈ 2.11 Pruebe que .X X Y Y X Y× = × ⇒ =

Solución. Sea .x X∈ entonces ( , ) . ( , )x x X X x x Y Y∈ × ∈ × . .x Y X Y∈ ⊂ igualmente . .Y X Y X⊂ =

2.12 Pruebe que .X Y X Z y X Y Z× = × ≠ ∅⇒ =

Solución. Sea ya que sea .y Y∈ X ≠∅ .a X∈ entonces igualmente ( , ) . ( , ) . .a y Y a y X Z y Z∈ ∈ × ∈ . .Z Y Y Z⊂ =

CAPITULO 3 RELACIONES

3.0 Definición de una relación de X a .Y R es una relación de X a si y solo si en este caso escribiremos

Y.R X Y⊂ × xRy si ( , ) .x y R∈

Definición de imagen de una relación. Imagen { | ( , ) lg }.R y x y R para a una x X= ∈ ∈

Definición de preimagen de una relación. Preimagen { | ( , ) lg }.R x x y R para a una y Y= ∈ ∈

Definición. Una relación R en X (de X a X ) es

a) Reflexiva si y solo si para toda ,x X∈ ( , )x x R∈ b) Irreflexiva si y solo si para toda ,x X∈ ( , )x x R∉ c) Transitiva si y solo si ( , )x y R∈ y ( , )y z R∈ implica ( , )x z R∈ d) Intransitiva si y solo si ( , )x y R∈ y ( , )y z R∈ implica ( , )x z R∉ e) Simétrica si y solo si ( , )x y R∈ implica ( , )y x R∈ f) Antisimétrica si y solo si ( , )x y R∈ y ( , ) .y x R x y∈ ⇒ =

Definición de composición. Si R es relación de X a y es relación de Y a Y SZ entonces y {( , ) | ( , )S R x y x y R= ∈o ( , ) lg }.y z S para a una y Y∈ ∈

Definición de Relación Inversa. Si R es relación de X a entonces Y

1 {( , ) | ( , ) }.R y x x y R− = ∈

Definición una relación de Equivalencia en X es una relación reflexiva, simétrica y transitiva.

Definición Un orden en X es una relación reflexiva, antisimétrica y transitiva en .X

Definición Un orden estricto en X es una relación irreflexiva, antisimétrica y transitiva en .X

Definición Un orden R en X es total si y solo si ,x y X∈ implica ( , )x y R∈ o

( , ) .y x R∈ Definición de partición. P es una partición de X si y solo si

y , ,P X X P⊂℘ = ∅∉U P ,A B P∈ implica A B∩ =∅ o´ .A B= Teorema. Asociatividad con una relación de equivalencia R en un conjunto X es una partición / { / | }X R x R x X= ∈ en la cual / { |x R y y X= ∈ y ( , ) }.x y R∈

3.1 Liste todas las relaciones de { , , }X a b c= a { }.Y s= Solución.

, {( , ), ( , )}, {( , ), ( , )}, {( , ), ( , )}, {( , )}, {( , )}, .X Y a s b s a s c s b s c s a s c s× ∅

3.2 Liste todas las relaciones sobre el conjunto 1.

Solución. ∅ y 1 . 1×

3.3 Cuantas relaciones hay en un conjunto con n elementos? Solución.

2

2n

3.4 Sea R una relación de W a ,X una relación de S X a y T una relación de

a ,Y

Y .Z Pruebe la asociatividad de la composición: ( ) ( )T S R T S R.=o o o o Solución. ( , ) ( ) ( , )w z T S R w y S R∈ ⇔ ∈o o o y ( , )y z T∈ para alguna si y solo si

y y Y∈

(( , )w x R∈ ( , )x y S∈ para alguna )x X∈ y ( , )y z T∈ para alguna si y solo si ( , y

y Y∈)w x R∈ (( , )x y S∈ y ( , )y z T∈ para alguna para alguna )y Y∈

x X∈ ( , ) ( ) .w z T S R∈ o o

3.5 Sea una relación de S X a Pruebe que .Y 1S − es una relación de Y a .X Solución. Como y son conjuntos, Y X× S 1 {( , ) | ( , )S y x y x Y X− ∈ × ( , ) }y= x y S∈ es un conjunto por los axiomas de especificación. 1S − es una relación de a X ya que esto es un subconjunto de Y X

Y×

3.6 Defina {( , ) | ( , )xI x y x y X X= ∈ × y x }.y= Sea una relación de S X a

Pruebe que .Y

*yI S S= y * .xS I S= Demostración.

( ) ( , )y S A x y S∈ ⇒ ∈ para alguna x A∈ que implica .y Y∈( )( )z T S A∈ ⇔o ( , )x z T S∈ o para alguna x A∈ si y solo si ( , )x y S∈ y

para alguna ( , )y z T∈ y Y∈ y x A∈ si y solo si para alguna si y solo si

( , )y z T∈( )y S A∈ ( ( ( )).z T S A∈( ) ( )y S A S B∈ ∪ implica ( )y S A∈ o ( )y S B∈ que implica 1( , )x y S∈ para

alguna 1x A∈ o 2( , )x y S∈ para alguna 2x B∈ que implica 1( , )x y S∈ para alguna 1x A B∈ ∪ o 2( , )x y S∈ para alguna 2x B A∈ ∪ que implica que

( )y S A B∈ ∪ .).(y S A B∈ ∪ implica ( , )x y S∈ para alguna .x A B∈ ∪ Si x A∈ , entonces

( , )x y S∈ para alguna x A∈ flexible ( ).y S A∈ si en el otro sentido x B∈ , entonces ( , )x y S∈ para alguna x B∈ flexible ( ).y S B∈ en otro caso

( ) ( )y S A S B∈ ∪( ) ( , )y S A B x y S∈ ∩ ⇒ ∈ para alguna x B A∈ ∩ que implica x A∈ y x B∈ y

( , )x y S∈ para alguna x X∈ que implica ( ) ( )y S A S B∈ ∩

3.7 Sea una relación de S X a y T una relación de Y a .Y .Z Defina para , ( ) { | ( , )A X S A y x y S⊂ = ∈ para alguna }.x A∈ Pruebe que

( )( ) ( ( )T S A T S A=o ).).

Pruebe que Pruebe que

( ) ( ) ( ).S A B S A S B∪ = ∪( ) ( ) (S A B S A S B∩ ⊂ ∩

Solución.

1( , ) ( )y x S T −∈ ∩ si y solo si ( , ) ( , )x y S T x y S∈ ∩ ⇔ ∈ y ( , )x y T∈ si y solo si 1( , )y x S −∈ y 1( , )x y T −∈ si y solo si 1( , ) 1y x S T− −∈ ∩ . Similarmente para ∪

3.8 Sean y relaciones de S T X a Entonces pruebe .Y

1 1 1.− 1( )S T −∪ =( )S T S T− −∩ = ∩ 1 1.S T− −∪ Solución.

1( , ) ( )z x T S −∈ ⋅ ( , ) ( , )x y S T x y S⇔ ∈ ∩ ⇔ ∈ y 1( , ) ( , )x y T x y S −∈ ⇔ ∈ y 1( , )x y T −∈ 1( , ) 1x y S T−⇔ ∈ ∩ − , similarmente para .∪

3.9 Sea una relación de S X a y T una relación de Y a .Y .Z Pruebe entonces que

1 1( )T S S T− −=o o 1−

Solución.

1( , ) ( )x y S T −∈ ⋅ ( , ) ( , )x z T S x y S⇔ ∈ ⇔ ∈o y ( , )x y T∈ para alguna sí y solo sí

y Y∈1( , )x y T −∈ sí 1( , )x y S −∈ para alguna y Y∈ sí y solo sí 1 1( , )x y S T− −∈ o

3.10 Probar que para una relación en S X

S es reflexiva xI S⇔ ⊂ S es irreflexiva xI S⇔ ∩ =∅S es transitiva ( )S S S⇔ ⊂oS es intransitiva ( )S S S⇔ ∩ =o ∅S es simétrica 1S S −⇔ =S es antisimétrica 1

XS S I−⇔ ∩ ⊂ Solución.

Sea S reflexiva. Sea. Entonces x y= pero ( , )x x S∈ ya que S es reflexiva. De aquí ( , ) ( , ) . .Xx y x x S I S= ∈ ⊂ La prueba inversa sea

.XI S⊂ Sea .x X∈ ( , ) .Xx x I∈ pero .XI S⊂ más aun ( , ) .x x S∈ y S es reflexiva.

S es irreflexiva sí y solo sí ( , )x x S∉ para toda .x X∈ sí y solo sí ( , )x x S∉ para toda ( , ) Xx x I∈ sí y solo sí .XS I∩ =∅

Sea S transitiva. Si ( , ) ,x z S S∈ o entonces ( , )x y S∈ y para alguna ( , )y z S∈ .y X∈ Pero si S es transitiva, Entonces

( , ) ,x z S∈ . Inversamente sea . Asumiendo S S S⊂o S S S⊂o ( , )x y ∈ S y entonces ( , )y z S∈ ( , ) ,x z S S∈ o ya que también .S S S⊂o ( , ) .x z S∈ S es

transitiva. Sea S antitransitiva. Sea ( , ) ,x z S S∈ o entonces

( , )x y S∈ y ( , para alguna Además )y z S∈ .y X∈

( , ) .x z S∉ ( )S S S∩ =∅o inversamente, sea sea ( )S S S∩ =∅o( , )x y S∈ y ( , ) .y z S∈ ( , ) , ( , ) .x z S S x z S∈ ∉o

S Simétrica. Sí y solo sí ( ( , )x y S∈ implica sí y solo sí (

( , ) )y x S∈( , )x y ∈ S implica 1( , ) )y x S −∈ sí y solo sí 1 1.S S S S− −⊂ ⇔ =

Sea S antisimetrica. Asumiendo 1( , ) .x y S S −∈ ∩ entonces ( , )x y S∈ y 1( , ) .x y S −∈ ( , ) .y x S∈ por antisimetria

. ( , ) ( , ) .Xx y x y x x I= = ∈ inversamente, sea Sea 1 .XS S I−∩ ⊂

( , )x y S∈ y entonces ( , ) .y x S∈ ( , )x y S∈ y 1( , ) .x y S −∈ 1( , ) .x y S S −∈ ∩ ( , ) . .Xx y I x y∈ =

3.11 Sea una relación en S X Probar que si es transitiva y reflexiva, entonces

es cierto para la relación inversa? S

.S S S=o Solución. Si S es transitiva, entonces Sea .S S S⊂o ( , ) .x y S∈ Por reflexión

3.12 Construya todas las relaciones de equivalencia en el conjunto 3. Solución. Las particiones de3 { son {{0},{1},{2}}, {{0,1},{2}}, {{0,2},{1}}, {{1,2},{0}}, {{0,1,2}}.

0,1, 2}=

Las correspondientes relaciones de equivalencia son

3 3, {(0,1), (1,0)},I I ∪

3 3{(2,0), (0, 2)}, {(1,2), (2,1)}, 3 3.I I∪ ∪ × 3.13 Sea δ un conjunto no vacío de relación de equivalencia en un con junto X.

Pruebe que δI es una relación de equivalencia en X. Solución. Sea .S δ∈ ≠ ∅I Entonces .S X Xδ ⊂ ⊂ ×I Sea .( , ) .x X x x S S δ∈ ∈ ∀ ∈ Ademas ( , ) .x x δ∈ I Sea ( , ) .x y δ∈ I ( , ) .x y S S∈ δ∀ ∈ ( , ) .y x S S δ∈ ∀ ∈ ( , ) .y x δ∈ I Ahora sea ( , )x y y ( , )y z .δ∈ I ( , )x y y ( , para toda )y z S∈

.S δ∈ ( , )x z S∈ para toda .S δ∈ ( , )x z .δ∈ I 3.14 Sea X un conjunto. Verifique que la igualdad de conjuntos es una relación de

equivalencia en .X℘ Solución. La igualdad = { (A;B) | (A,B) X X∈℘ ×℘ y A = B}.

3.15 Construya todas las ordenaciones en el conjunto 3. Cuales son totales?

Solución. Hay 19 ordenaciones en 3:

3,I 3 {(0,1)},I ∪ 3 {(0,2)},I ∪

3 {(1, 2)},I ∪ 3 {(1,0)},I ∪ 3 {(2,0)},I ∪ 3 {(2,1)},I ∪ 3 {(0,1), (0, 2)},I ∪

3 {(0,1), (2,0), (2,1)},I ∪ 3 {(0,1), (1, 2), (0, 2)},I ∪ 3 {(0,1), (2,1)},I ∪ 3 {(1,0), (0, 2), (1, 2)},I ∪ 3 {(1,0), (2,0)},I ∪ 3 {(1,0), (1,2)},I ∪

3 {(1,0), (2,1), (2,0)},I ∪ 3 {(2,0), (1, 2), (1,0)},I ∪

3 {(2,0), (2,1)},I ∪ 3 {(0,2), (1,2)},I ∪

3 {(0,2), (2,1), (0,1)},I ∪ Las ordenaciones con 6 elementos son ordenaciones toteles. 3.16 Puede ser una relación de equivalencia? Una ordenación? ∅

Solución. Dado que ambas ordenación y relación de equivalencia son relaciones reflexivas, el único conjunto en el cual el conjunto vacío puede ser un orden o una relación de equivalencia es en el mismo conjunto vacío. Que es un Orden y una relación de equivalencia es facil de verificar.

3.17 Sea δ un conjunto no vacío de orden en Pruebe que .X δI es un orden. Solución. La prueba es analoga a la demostración en el ejercicio 3.13

3.18 Verifique que inclusión es un orden en .X℘ Solución. Cf. Ejercicio 1.4

3.19 Si es un orden en un conjunto S X y ,A X⊂ Pruebe que (S A A)∩ × es un orden en A . Pruebe que si es total en S ,X entonces (S A A)∩ × es total en A . Solución. Sea S un orden en X. ( )S A A A A.∩ × ⊂ × Sea x A∈ (x,x)∈A A× (x,x)∈S ( ).A A∩ × Sea (x,y)∈S ( ).A A∩ × y (y,x)∈S ( ).A A∩ × Y (x,y)∈S y (y,x)∈S. x = y. Sea (x,y) ∈ S ( ).A A∩ × y (y,z) ∈ S ( ).A A× (x,y) ∈ S y ∩(y,x)∈S. (x,z)∈S. ( , )x y A A∈ × y ( , )y z A A∈ × Por lo tanto

, ,x . ( , . ( , ) ( ).)y z A x A A x z S A A× ∈ ∩ × ).z∈ ∈ Por lo que S (A A∩ × es un orden en A. Sea S total en X. Sea , .x y A∈ Entonces ( , )x y S∈ o Pero ( , )y x S∈( , )x y A∈ × A y ( , ) .x y A A∈ × Por lo tanto ( , )x y o ( , ) ( ).y x S A A∈ ∩ ×

3.20 Pruebe que es un orden en 1S − X S⇔ es orden en .X Solución. Utilizando la condición del ejercicio 3.10, 1S − es un orden si y solo si

y 1S X− ⊂ × X 1XI S −⊂ y 1 1S S S 1− − −∩ ⊂ y se verifica

fácilmente.

1 1 1( ) XS S− − −∩ ⊂ I

3.21 Construya las siguientes relaciones en el conjunto 8, Contar con sus previos conocimientos de aritmética. El símbolo (-) en estos ejercicios significa diferencia aritmética y no la relación complemento.

a) donde ,≤ 8x y x y≤ ⇔ − ∈b) donde y ,≥ 8x y y x< ⇔ − ∈ 8x y− ∉ c) =, donde 0x y y x= ⇔ − =d) donde ,: x y y x⇔ −: es un entero divisible por 2 e)*, donde * 4x y x⇔ < − y f) s, donde x s y 1y x⇔ − =

Cuales relaciones son simétricas? Antisimétricas? Reflexiva? Irreflexiva? Transitiva? Antitransitiva? Cuales relaciones son ordenes? Relaciones de equivalencia? Para cada relación de equivalencia cual es la correspondiente partición de 8?

Solución.

a) S = {(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (3,3), (3,4), (3,5), (3,6), (3,7), (4,4), (4,5), (4,6), (4,7), (5,5), (5,6), (5,7), (6,6), (6,7), (7,7)} b) 8S I−c) 8I d) 8I ∪ {(0,2), (0,4), (0,6), (2,0), (2,4), (2,6), (4,0), (4,2), (4,6)

(6,0), (6,2), (6,4), (1,3), (1,5), (1,7), (3,1), (3,5), (3,7) (5,1), (5,3), (5,7), (7,1), (7,3), (7,5)}

e) {(5,0), (6,0), (7,0), (6,1), (7,1), (7,2)}. f) {(0,1), (1,2), (2,3), (3,4), (4,5), (5,6), (6,7)}.

Simetrica: c, d. Antisimetrica: a, b, c, e, f. Reflexiva: a, c, d. Irreflecciva: b, e, f. Transitiva: a, b, c, d, e. Antitransitiva: f. Ordenaciones: a, c. Relación de equivalencia: c, d. Para c: {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}}. Para d: {{0, 2, 4, 6}, {1, 3, 5, 7}}.

3.22 Sea L el conjunto de todas las líneas del plano euclidiano. Verifique que el

paralelismo es una relación de equivalencia en L.Verificar que particularmente es irreflexiva, simétrica, y una relación intransitiva.

3.23 Sea Q el conjunto de los números racionales. Y sea Q(x) el conjunto de todos los

polinomios en X con coeficientes racionales. Defina una relación en ( )A Q X Q= − como sigue: para todo , ,f g A f g g qf∈ ⇔ =p para alguna.

Probar que p es un orden estricto en A , es una (p ) I∪ totales? Solución. ( ) .A A⊂ ×p f p f ya que f qf= con grado da una contradicción. Note que consiste de polinomios de grado Suponga que

1q ≥[ ]Q X Q− 1.≥ f gp y y .g fp 1g q f= 2f q g= produce 1 2g q q g= y grado g > grado g que es una

contradicción. Ahora suponga que f gp y , g hp 1g q f= y Entonces con El orden no es total. Por ejemplo, los

siguientes polinomios no son comparables:

2 .h q g=

2 1( )h q q f= 1 2 2 1 2.q q q q= + ≥

2 1, 1, .x x x+ +

3.24 Si S es un orden en X. Pruebe que XS l− es un orden estricto. Si S es un orden en X. Pruebe que es un orden. XS l∪

Solución. Sea S un orden en X y considere . ,X XS I S I X X− − ⊂ × para Sea S X X⊂ ×

.x X∈ ( , ) Xx x I∈ y por lo tanto ( , ) .Xx x S I∉ − Sea ( , )x y y ( , ) .Xy x S I∈ − Entonces ( , )x y S∈ y ( , )y x S∈ implica .x y= Ahora sea ( , )x y y ( , ) .Xy z S I∈ − De esto se sigue que ( , ) .x z S∈ Entonces ( , ) .Xx z S I∈ − a menos que .x z= Si ,x z= entonces ( , )x y y ambos pertenecen a S, consecuentemente ( , )y x

.x y= Pero ( , ) Xx y S I∈ − implica x y≠ dando una contradicción.

3.25 Puede ser un orden estricto. ∅ Solución. El vacío es un orden estricto en cualquier conjunto X.

3.26 Sea S una relación en X. Pruebe que S es una relación en Pruebe que

SUU

S X⊂UU Solución. Esto debería mostrar que ( )S S⊂ ×UU UU .S Sα ∈U si y solo si ( , )x yα ∈ para alguna ( , ) ,x y S∈ si y solo si {{ },{ , }}x x yα ∈ para alguna ( , ) ,x y S∈ si y solo si { }xα ∈ o { , }x yα ∈ para alguna ( , ) .x y S∈ Sβ ∈UU si y solo si β α∈ para alguna ,Sα ∈U si y solo si { }xβ ∈ o { , }x yβ ∈ para alguna ( , ) ,x y S∈ si y solo si xβ = o yβ = para alguna ( , ) .x y S∈ Ahora si ( , ) ,x y S∈ nosotros tenemos x S∈UU y ,y S∈UU en consecuencia ( , ) .x y S∈ ×UU UU S

Sea .Sβ ∈UU Entonces xβ = de alguna ( , )x y S X X∈ ⊂ × o yβ = de alguna ( , ) .x y S X X∈ ⊂ × Por lo tanto .Xβ ∈

3.27 Sea S una relación de X en Y. Obtenga la preimagen de y la imagen

S X⊂

S Y⊂ Solución. x∈Preimagen de S. implica ( , ) .x y S X Y∈ ⊂ × .x X∈ y∈imagen de S implica ( , ) .x y S X Y∈ ⊂ × . y Y∈

3.28 Sea S una relación de X a Y. Pruebe que Pruebe que

1 .preimagenSl S −⊂ oS

S 1.imagenSl S −⊂ o Solución. x∈Preimagen de S. entonces existe un ( , ) .x y S∈ De aquí 1( , ) .x y S −∈

1( , ) .x x S S−∈ o Lo mismo para y. y∈imagen de S. entonces existe un 1( , ) .x y S∈ 1( , ) .y y S S −∈ o

3.29 Sea S un orden en X y T un orden en Y. sea 1 1 2 2 1 2(( , ), ( , )) ( , )x y x y P x x S∈ ⇔ ∈ y

1 2( , ) .y y T∈ Pruebe que P es un orden en X Y× (el producto orden). Solución.

( ) (P X Y X Y⊂ × × × ). Sea ( , ) .x y X Y∈ × x X∈ y .y Y∈ ( , )x x S∈ y ( , ) .y y T∈ (( , ), ( , )) .x y x y P∈ P es reflexiva. Ahora sea 1 1 2 2(( , ), ( , )) .x y x y P∈ y

2 2 1 1(( , ), ( , )) .x y x y P∈ Entonces 1 2( , )x x S∈ y 1 2( , )y y T∈ y 2 1( , )x x ∈S y

2 1( , ) .y y T∈ 1 2x x= y 1 2.y y= 1 1 2 2( , ) ( , ).x y x y= P es antisimétrica. Ahora sea

1 1 2 2(( , ), ( , ))x y x y P∈ y 2 2 3 3(( , ), ( , )) .x y x y P∈ 1 2( , )x x S∈ y 1 2( , )y y T∈ y

2 3( , )x x ∈ S . y 2 3( , )y y T∈ Por lo tanto 1 3( , )x x S∈ y 1 3( , ) .y y T∈

1 1 3 3(( , ), ( , )) .x y x y P∈

3.30 Sea S una relación de equivalencia en X y T una relación de equivalencia en Y. Sea 1 1 2 2 1 2(( , ), ( , )) ( , )x y x y P x x S∈ ⇔ ∈ y 1 2( , ) .y y T∈ Pruebe que P es una relación de equivalencia X Y×

Solución. Similar a 3.29.

3.31 Sea S un orden estricto en X y T un orden estricto en Y. En X Y× defina una

relación R como sigue: 1 1 2 2 1 2(( , ), ( , )) ( , )x y x y R y y T∈ ⇔ ∈ o 1 2[( , )x x S∈ y

1 2 ].y y= R es decir una ordenación por ultimas diferencias. Pruebe R es un orden estricto en X Y× Solución.

1 1 2 2 1 2{(( , ), ( , )) | ( , )R x y x y y y T= ∈ o 1 2[( , )x x S∈ y 1 2 ]}y y= es un conjunto usando el axioma de especificación en ( ) ( ).X Y X Y R× × × es reflexiva ya que

1 1 2 2(( , ), ( , ))x y x y R∈ implica 1 2( , )y y T∈ con 1 2y y≠ o esto implica 1 2( , )x x S∈ con 1 2.x x≠ en otro caso 1 1 2 2( , ) ( , ).x y x y≠ Ahora por antisimétria asumiendo ambos 1 1 2 2(( , ), ( , ))x y x y ∈R y 2 2 1 1(( , ), ( , )) .x y x y R∈ En los cuatro casos todo nos llevan a 1 1 2 2( , ) ( , ).x y x y= La transitivdad se demuestra de la misma forma.

3.32 Sean y particiones de S T X es mas fino que T si y solo si u implica

para alguna Pruebe que la relación que es más fina es un orden en el conjunto de todas las particiones de

S S∈u v⊂ .v T∈

X

Solución. Sea F el conjunto de todas las particiones de X. S es mas fina que S ya que

implica u para alguna u S∈ u⊂ .u S∈ Suponga que S es mas fina que T y T mas fina que S. u implica u para alguna S∈ v⊂ .v T∈ v T∈ implica que hay una tal que Cualquier otra uu S′∈ .v u′⊂ u′ = o u u′∩ =∅ ya que S es una partición. Puesto que u sea ≠ ∅ .a u∈ Entonces .a v∈ .a u′∈ Por lo tanto u y tenemos

.u u′∩ ≠∅u′= .u v= Similarmente, y concluimos que

Sea S mas fina que T y T mas fina que. sea .S T⊂ ,T S⊂

.S T= u S∈ u v⊂ para alguna para alguna .v T∈ u w⊂ .w U∈ Entonces S es mas fina que U, puesto que

para cada u S∈ existe .w U∈

3.33 Dar un ejemplo de un conjunto X y un conjunto δ de orden en X tal que δU no es un orden en X

Solución. Sea 2X = y {{(0,0), (0,1), (1,1)},{(0,0), (1,0), (1,1)}}δ = por ejemplo.

2 2,X Xδ = × = ×U que no es un orden. 3.34 Sea R una relación en X Pruebe que 1R R−∪ es la menor relación simétrica

incluida en R y que 1R R−∩ es la mayor relación simétrica incluida en .R

Solución. Sea R una relación en X. Sea δ el conjunto de todas las simetrías en X, cada una incluida en R. δU es una relación simétrica, por suponer ( , ) .x y δ∈U entonces ( , )x y S∈ para alguna .S δ∈ ( , ) .y x S δ∈ ⊂ U δ δ∈U . Rδ ∈U y es la mayor relación simétrica incluida en R. Ahora se deberá probar que 1.R Rδ −= ∩U 1( , ) .x y R R−∈ ∩ ( , )x y R∈ y

1( , ) .x y R−∈ 1( , )y x R−∈ y ( , ) .y x R∈ 1 .R R R−∩ ⊂ 1 .R R δ−∩ ∈ 1 .R R δ−∩ ⊂ U suponga que ( , ) .x y δ∈U Entonces ( , )x y S∈ para alguna .S δ∈ ( , ) .y x S∈

( , )x y y ( , ) .y x S∈ S R⊂ ( , )x y y ( , ) .y x R∈ 1( , ) .x y R R−∈ ∩ 1.R Rδ −⊂ ∩U Sea { |S Sδ = es una relación simétrica en X y R }.S⊂ .X X δ× ∈ .δ ≠ ∅ Defina ( ) .s R δ= I es la menor relación simétrica que incluye a R. ¿Por que?

( )s R

Ahora se deberá probar que 1( ) .s R R R−= ∪ Primero se prueba que 1R R−∪ es simétrica 1( , )x y R R−∈ ∪ implica ( , )x y R∈ o que

implica ( , )y x R∈

1( , )y x R−∈ o ( , )y x R∈ que implica 1( , ) .y x R−∈ De este modo 1R R δ−∪ ∈ así 1( ) .s R R R−⊂ ∪ Sea T una relación simétrica que incluye a R. Suponga 1( , ) .x y R R−∈ ∪ Si ( , ) ,x y R∈ entonces ( , ) .x y T∈ Si

1( , ) ,x y R−∈ entonces ( , ) .y x R∈ ( , ) .y x T∈ ( , ) .x y T∈ De aquí 1R R−∪ ⊂ T para toda .T δ∈ 1 ( ).R R s R−∪ ⊂

3.35 Sea R una relación en X tal que R es reflexiva y transitiva. R No es

necesariamente un orden ya que R no es necesariamente antisimetrica. Pruebe que existe una relación de equivalencia en S X y un orden R en tal que /X S( / , / ) ( , ) .x S y S R x y R∈ ⇔ ∈

Solución. Defina ( , )x y S∈ si y solo si ( , )x y R∈ y ( , ) .y x R∈ Que S es una relación de equivalencia se sigue de: ( , )x x S∈ puesto que ( , ) .x x R∈ ( , )x y S∈ implica ( , )x y R∈ y que implica ( ,( , )y x R∈ ) .y x S∈ Finalmente ( , )x y S∈ y

implica ( ,( , )z y S∈ )x y R∈ y ( , )y x R∈ y ( , )y z R∈ y que implica ( , )z y R∈( , )x z R∈ y ( , que implica )z x R∈ ( , ) .x z S∈

Como fue definida R es claro que resulta un subconjunto de Ahora ahí que checar que esta bien definida. Sea / /X S X S× . / /x S x S′ = y

/ / .Sy S y′ = ( / , / )x S y S R∈ implica ( , ) .x y R∈ Pero ( , )x x S′ ∈ implica ( , )x x R′ ∈ y ( , ) .x x R′ ∈ ( , implica ( ,)y y S′ ∈ )y y R′ ∈ y ( , )y y R′ ∈ ( , ) .x y R′ ′ ∈ ( / , / ) .x S y S R′ ′ ∈ Que R es orden se verifica a continuación. ( , )x x R∈ implica ( / , / ) .x S x S R∈ ( / , / )x S y S R∈ y ( / , / )y S x S R∈ implica ( , )x y R∈ y ( , )y x R∈ que implica ( , )x y S∈ que implica / / .x S y S= ( / , / )x S y S R∈ y ( / , / )y S z S R∈ implica ( , )x y y

que implica ( ,( , )y z R∈ )x z R∈ que implica ( / , / ) .x S z S R∈

CAPITULO 4 FUNCIONES

4.0 Definición. F es una función de X a Y si y solo si ,f X Y x X⊂ × ∀ ∈ hay una

tal que y Y∈ ( , ) ,x y f∈ 1( , ) ,x y f∈ y 2( , )x y f∈ implica 1 2y y= También por definición,

:f X Y→ significa que f es una función de X a Y con dominio f X= , condominio ,f Y= imagen { |f y y Y= ∈ y ( , )x y f∈ para alguna },x X∈ significa ( )y f x= ( , ) ,x y f∈

y es la imagen de x bajo f significa ( , ) ,x y f∈ x es la preimagen de y bajo f significa ( , ) ,x y f∈ y es el valor de la función f a x significa ( , ) ,x y f∈

Definición. Una función f de X a Y es una sobreyección (también llamada una sobre función) si y solo si para toda existe una y Y∈ x X∈ tal que ( , ) .x y f∈

:f X − >> Y significa f es una sobreyección de X a Y.

Definición. Una función f de X a Y es una inyección (también llamada una función uno a uno) si y solo si 1( , )x y f∈ y 2( , )x y f∈ implica 1 2.x x=

:f X > − > Y significa f es una inyectiva de X a Y. Definición. Una función f de X a Y es una biyección si y solo si f es inyectiva y sobreyectiva

:f X > − >> Y significa f es una biyección de X a Y. Una biyección es llamada también una equivalencia. En caso de que aya una

:f X > − >> Y , llamaremos al conjunto X y Y equivalencia: .X Y:

Definición. { | : }.XY f f X Y= → Definición. Sea : ,f A Y→ y Entonces es una restricción de :g B Y→ .g f⊂ g f y f es una extensión de .g( | ) ( ) .f B f B Y g= ∩ × = Definición de mapeo Cociente. Si es una partición de /X R X entonces la sobreyección : /X X Rφ − >> tal que ( ) /x x Rφ = es llamado el mapeo cociente (o mapeo cociente). Definición de función característica. Si A es un subconjunto de X, La función característica de A es la función : 2A Xχ → tal que ( ) 1A xχ = para x A∈ y ( ) 0A xχ = para .x A∉ Definición de Monoide. Un monoide es un par ordenado ( , )A w en el cual A es un conjunto y w es una operación asociada en A con un elemento neutral e.

Un operador en un conjunto A es una función w de A A× a A. Escribimos x w y para el valor de la operación w(x, y), e es un elemento neutral para la operación w sí y solo sí e w x = x w e = x para toda .x A∈ Definición de un Submonoide. Sea (A,w) un monoide. Un subconjunto S de A es un submonoide de, A sí y solo si ,x y S x w y S∈ ⇒ ∈ y y w x S∈ y .e S∈ Por abuso de lenguaje sea ( , un monoid es usual escribir G es un monoide. )G w Definición de Semigrupo. Un semigrupo izquierdo es un monoide ( , )A w con ley de cancelación izquierda, i.e., .x w y x w z y z= ⇒ = Definición de Grupo. Un monoide es un grupo si y solo si todo elemento de G es invertible. x es un elemento invertible de G sí y solo sí

( , )G wx w y y w x e= = para alguna

.y G∈ Los estudiantes que no encuentren suficiente estas definiciones para trabajar pueden consultar las referencias 18, 19, 20. 4.1 Sea quien representa a los enteros no negativos, los enteros, Q los

racionales y los números reales asumiendo un ACQUAINTANCE con estos conjuntos, damos un ejemplo de una función:

N ZR

a) de a un subconjunto propio de N , y una inyección no, Nb) que es una inyección de N a un subconjunto propio de , Nc) de a un subconjuunto propio de y una inyección no Z Zd) que es una inyección de Z a un subconjunto propio de , Ze) de a , R Nf) de a tal que para toda R N , ( ) .x f x x≠ Solución. Por ejemplo a) {( b) {(,0) | },n n∈N , 1) | },n n n+ ∈N c) {( d)

e) {(,0) | },n n∈Z

{( , 2 ) | },n n n∈Z , 0) | },x x∈R f) {( ,0) | {0}} {(0,1)}.x x∈ − ∪R

4.2 Pruebe que no toda inyección de un conjunto en sí mismo es una biyección. Solución. Ver solución de 4.1 b). 4.3 Construya una función a) de 1 a 1, b) de 0 a 1, c) de 2×3 a 6, de 6 a 2×3, ambas

biyecciones.

Solución. a) b) c) una biyección de {(0,0)}, ,∅ 2 3× a es

6

{((0,0),0), ((0,1),1), ((0, 2), 2), ((1,0),3), ((1,1), 4), ((1, 2),5)}. 4.4 Construya estos conjuntos.

a) c) e) g) i) 32 02 00 11 12b) d) f) h) j) 23 20 01 10 21

Solución. a)

{{(0,0), (1,0), (2,0)}, {(0,0), (1,0), (2,1)},{(0,0), (1,1), (2,0)}, {(0,0), (1,1), (2,1)},{(0,1), (1,0), (2,0)}, {(0,1), (1,0), (2,1)},{(0,1), (1,1), (2,0)}, {(0,1), (1,1), (2,1)}}.

b) {{(0,0), (1,0)}, {(0,1), (1,0)}, {(2,0), (1,0)},

{(0,0), (1,1)}, {(0,1), (1,1)}, {(2,0), (1,1)},{(0,0), (1, 2)}, {(0,1), (1, 2)}, {(0, 2), (1, 2)}}.

4.5 Suponga que existe una función de X a Y que no es una inyección. Pruebe que

X≠ ∅ y Y . ≠ ∅

Solución. Si X es igual al vacío entonces ,f = ∅ que es inyectiva, ya que si y

entonces 1( , )x y ∈∅

2( , ) ,x y ∈∅ 1 2.x x= si Y =∅ y f es una función de X a Y, entonces y también que nuevamente resulta una inyección. X =∅ ,f = ∅

4.6 Suponga que existe una función de X a Y que no es una sobreyección. Pruebe

que Y . ≠ ∅

Solución. Si Y y =∅ f es una función, entonces f es una sobreyección. 4.7 Pruebe que 4.℘℘℘∅ : significa equivalencia. : Solución. {(0 es una biyección. , 0), (1,1), ({1}, 2), (2,3)}

4.8 Pruebe que y 0 0BA A= ⇔ = 0.B ≠

Solución. Primero sea y 0A = 0.B ≠ Bf A∈ implica Pero no es una función de a Por lo tanto

0 0.f B⊂ × =0B ≠ 0.A = 0.BA ≠ Si en otro caso entonces

0 es una función de 0,B =

B a A y de nuevo 0.BA ≠ 4.9 Y XX Y= implica Probar .X Y=

Solución. Si sea YX ≠ ∅ .Y Xf X Y∈ = entonces el dominio ,f Y= puesto que .Yf X∈ Pero el dominio ,f X= puesto que .Xf Y∈ .X Y= Si en otro caso entonces por 4.8 Pero

0,YX =0.X = 0XY = también con lleva a 0.Y = Nuevamente

.X Y=

4.10 Pruebe que si ,A B⊂ entonces C CA B⊂

Solución. Sea .Cf A∈ Luego observar 0) ,f C A C B⊂ × ⊂ × 1) Para toda x C∈ hay una

(y por lo tanto ) tal que ( ,y A∈ y B∈ ) ,x y f∈ 2) 1( , )x y f∈ y 2( , )x y f∈ implica 1 2.y y= f es por lo tanto una función de C a B y por lo tanto es un miembro de .CB

4.11 Pruebe que si ,A B: entonces .C CA B:

Solución. Sea junto con : A∅ > − >> .B .Cf A∈ Entonces definimos : .CA B∅ > − >> Sea

.Cf A∈ Luego defina : C CA B∅ > − >> como sigue: ( ) .f fφΦ = o es inyectiva, puesto que

Φf gφ φ=o o implica .f g= Cf. 4.29 Φ es sobreyeciva,

puesto que para Cg B∈1 1( )g gφ φ φ− −Φ =o o o .g=

.

4.12 Sea :f X X→ Pruebe que si ,Xf I⊂ entonces .Xf I=

Solución. Para probar Xf I= queda por probar .XI f⊂ Sea .x X∈ Puesto que f es una función, ( , )x y ∈ f para alguna .y X∈ Pero de hipótesis Xf I⊂ esta dado. ( , ) .Xx y I∈ .x y= ( , ) .x x f∈ Por lo tanto .XI f⊂

4.13 Sea : .f X X→ Pruebe que si ,XI f⊂ entonces .Xf I=

Solución. Dado que ,XI f⊂ queda por probar que .Xf I⊂ Sea ( , ) .x y f∈ Entonces

.x X∈ ( , ) .Xx x I∈ ( , )x x f∈ ya que .XI f⊂ ( , )x x f∈ y ( , )x y ∈ f implica .x y= Por lo tanto ( , ) ( , ) .x y x x f= ∈ .X f I⊂

.

4.14 Sea :f X X→ y n un numero entero positivo tal que .nXf I= ( 1 .n nf f f+ = o )

Pruebe que f es una biyección.

Solución. Si entonces 1n = ,Xf I= que es una biyección. Suponga ahora que Suponga que

1.n >f no es una inyección. 1( ) ( )2f x f x= para alguna 1 2, ,x x X∈

1 2.x x≠ 1 11( ) ( )n n

2f f x f f x− −= para algunas 1 2,x x X∈ distintas. De aquí nf no es una inyección y ni particularmente, la inyección .XI

4.15 Sean A, B, C conjuntos tales que .B C∩ =∅ Pruebe que .B C B CA A A∪ ×:

Solución. Sea entonces B Cf A ∪∈ f f f′ ′′= ∪ donde ( )f f B A′ = ∩ × y .f f C A′′ = ∩ ×

ya que Ahora f f′′∩ = ∅ .B C∩ =∅ :f B A′ → y : .f C A′′ → Defina

( ) ( ) ( , ).f f f f f′ ′′ ′ ′′Φ = Φ ∪ = esto puede ser verificado sin ninguna dificultad que es una función, una inyección, y una sobreyección. Φ

4.16 ¿Es ( )B C B CA A ×: ?

Sea B Cf A ×∈ . Defina como sigue: : B C B CA ×Φ > − >> ( )A

( ) {( , ) | ( , ) Bf c g c g C AΦ = ∈ × y ( ) ( , )}.g b f b c= Como argumento Φ es inyectiva, Por lo tanto: 1 2( ) ( ).f fΦ = Φ ( , ) | ( , ) Bc g c g C A { ∈ ×

1( ) ( , )}g b f b c= =

2{( , ) | ( , ) ( ) ( , )}.Bc g c g C A g b f b c∈ × = 1 2( , ) ( , )f b c f b c= para toda b y

B∈,c C∈ 1 2.f f=

Para probar la propiedad sobreyectiva, sea h A Sea

( ) .B C∈ ( ) : .h c B A→( )( ) .h c b A∈ :f B C A× → tal que ( , ) ( )( ).f b c h c b=

Entonces ( ) {( , ) | ( , ) ( ) ( , )}Bf c g c g C A g b f b cΦ = ∈ × = {( , ) | ( , ) ( ) ( )( )}Bc g c g C A g b h c b= ∈ × = {( , ) | ( , ) ( ) ( )} .Bc g c g C A g b h c h= ∈ × = =

)C

4.17 Pruebe que ( ) .C C CA B A B× ×:

Solución. Defina tal que (: (C CA B A BΦ × > − >> × ( , ))( ) ( ( ), ( ))f g x f x g xΦ = para toda .x C∈ 1 2f f= y 1 2.g g= 1 1 2 2( , ) ( , ).f g f g= Para probar el mapeo sobreyectivo, sea h A h A( ) .CB∈ × .B∈ × Sea 1 2( ( ), ( )) ( ).h x h x h x= y

1

Ch A∈

2 .Ch B∈ 1 2( , ) .C Ch h A B∈ × 1 2( , )h h hΦ = ya que 1 2 1 2( , )( ) ( ( ), ( ))h h x h x h xΦ = para toda ( )h x= .x C∈

4.18 Pruebe que si R es el conjunto de todas las ordenaciones sobre el conjunto X y R

es el conjunto de todas las ordenaciones estrictas en X, entonces existe una biyección de R R> − >> .

Solución. Verifique que :Φ Ω > − >> Ω tal que ( ) XS S IΦ = ∪ es una inyección.

4.19 Pruebe que hay un conjunto ξ de todas las relaciones de equivalencia en un

conjunto X y un conjunto ℑ de todas las particiones de un conjunto X Pruebe que existe una biyección .ξΦ = > − >> ℑ

Solución.

{ | ( )S S X Xξ = ∈℘ × y es una relación de equivalencia en S }.X y es una partición de { |P P Xℑ = ∈℘℘ P }.X Defina :ξΦ > − >> ℑ tal que

Para probar que ( ) / .S X SΦ = Φ es inyectiva, sea ( ) ( ).S TΦ = Φ

/ /X S X T= . Sea ( , ) .x y S∈ / / .y S y T= ( ,x ) .y T∈ .S T⊂ de la misma forma Para probar que .T S⊂ .T S= Φ es una sobreyección, sea Defina .P∈ℑ

.A P

S A∈

= ×U A

Se puede entonces verificar que S es reflexiva, simetrica, y transitiva, que está pertenece a .ξ entonces se verifica que ( ) .S PΦ =

4.20 Sean P y Q las particiones de X. Se define la partición cruz de P y Q, P Q †

{ |A B A P= ∩ ∈ y Pruebe que P Q es mas fino que ambos P y Q y, mas aun, es la menor partición fina de ambos P y Q: P Q =sup{P,Q}. Sean R, S relaciones de equivalencia con correspondencia natural a P y Q. Pruebe que

corresponde a Pruebe que existe una partición que es inf{P,Q}.

} { }.B Q∈ − ∅ ††

R S∩ † .P Q Solución. P Q † { |A B A P= ∩ ∈ y Primero mostramos que P† Q es una partición de Sea

} { }.B Q∈ − ∅.X † .A B P Q∩ ∈ A P∈ y .B Q∈ A X⊂ y

Por tanto P Q.B X⊂

.A B X∩ ⊂ † .X⊂℘ Ahora sea .x X∈ Entonces .x P∈U y .x Q∈U x A∈ para alguna A∈P y x B∈ para alguna .B Q∈ x A B∈ ∩ para

alguna A∈P y .B Q∈ ( † ).x P Q∈U ( † ).X P Q⊂ U Ahora suponga Entonces existe una a tal que a( ) ( )A B C D .∩ =∅∩ ∩ ∈ ( ) ( ).A B C D∩ ∩ ∩

a∈A y implica Por lo tanto A=C. De la misma forma B=D. De aquí A∩ B=C∩D. Finalmente

a C∈ .A C∩ ≠∅†P Q∅∉ y por lo tanto es una

partición de X. †P Q

Para probar que es mas fino que P y Q sea A†P Q ∩ B †P Q∈ . Entonces A∈ P y A∩ B⊂A; B∈Q y A B B. Para probar que es la menor partición finita de ambos, sea N cualquier partición mas fina que P y Q. C∈N implica C⊂A para algún A∈P, C⊂B para algún B

∩ ⊂ †P Q

∈Q. C⊂A∩ B con A∩ B∈ . Así N es más fino que .

†P Q†P Q † sup{ ,P Q}P Q = .

Sea P={ |y y XR ∈ } y Q={ |y y XS ∈ } . Entonces =†P Q { | ,y z y z XR R∩ ∈ }

-{ =}∅ { | }y y y XR S∩ ∈ −{0} . Como y yR S∩ =∅ o y y

R S= .

x y yR S∈ ∩ si y solo si x y

R∈ y yS∈ si y solo si ( , )x y R∈ y ( , )x y S∈ si y

solo si ( , )x y R S∈ ∩ si y solo si x∈ yR S∩ . Con lo cual corresponde a

R S.

†P Q

∩ Sea { | y y es una relación de equivalencia en }U R U S U U Xϑ = ⊂ ⊂ . X X ϑ× ∈ implica que ϑ ≠∅ . T ϑ= I es una relación de equivalencia en X y es sup{ , }R S . Corresponde a esta relación de equivalencia la partición N. P y Q

son ambos mas finos que N. Sea A∈P. Entonces A= yR . x y

R∈ implica que

( , )x y R∈ , lo cual implica que , con lo cual x yT∈ . y y

R T⊂ . y CT = para

alguna C∈N. análogamente para Q. Entonces N es una cota inferior para P y Q. Ahora supóngase que tanto P como Q son más finos que M: Entonces R U y ⊂

S⊂U donde U es la relación de equivalencia asociada a M. Sea C∈N. entonces

C= yT para alguna y∈X. T U porque u⊂ ϑ∈ . y y

T ⊂ U . N es más fino que M.

N= inf . { , }P Q4.21 Sea . Defina X ≠∅ fSg si y solo si rango de f = rango para g

, Xf .g X∈ Pruebe que S es una relación de equivalencia en XX y que / 1XX S X℘ −: .

Solución. Que S sea una relación de equivalencia depende de tres propiedades de igualdad de conjuntos. Define : 1

XX XSΦ >→>℘ − tal que

( ) im , f f gfS SΦ = = S si y solo si im imf g= si y solo si

( ) ( )f gSΦ = Φ S . Entonces Φ es una función inyectiva. Ahora sea

A . Entonces A X y A1X∈℘ − ⊂ ≠∅ . Sea a∈ A. Define :f X A→ como sigue:

( )f x = x si x∈ A y ( )f x = a si x∉A. Entonces ( ) imf f ASΦ = = . Por lo tanto

es supreyectiva. La siguiente observación de que im∅∉ Φ es istructiva. Si imf φ= para alguna f XX∈ , entonces f=∅ . Pero XX∅∉ .

4.22 Asuma un conocimiento de los números reales, ¡ . Sea sea [0,1].X = ¡ , .f g X∈ Definimos para toda ( , ) ( ) ( ) 0f g S f x g x∈ ⇔ − ≥ [0,1].x∈ Pruebe que S es un orden. ¿Es el orden total? Solución ( , )f f ∈ S porque ( ) ( ) 0 0 [0,1]f x f x x− = ≥ ∀ ∈ . ( , )f g S∈ implica que f g= porque si y ( ) ( ) 0 [0,1]g x f x x− ≥ ∀ ∈ , entonces

. La transitividad también es fácil de verificar. El orden no es total. Por ejemplo,

( ) ( ) 0g x f x− =[0,1]x∀ ∈

( )f x x= y ( ) 1g x x= − + no son comparables porque (0) (0)f g− . 1 (1) (1g f= − = − )

4.23 Sea : 2A Xχ → la función caracteristica de X definida por el subconjunto A de

X . Pruebe donde : 2XXφ ℘ > − >> ( ) AAφ χ= para .A X⊂

Solución. Es claro que Φ es una función de X a . Que 2X Φ sea inyectiva se prueba como sigue: supóngase que ( ) ( )A BΦ = Φ . · ( ) (A B A B )x xχ χ χ χ= =

x X∀ ∈ .y∈A si y solo si ( ) 1A yχ = si y solo si ( ) 1B yχ = si y solo si y∈B. A=B. Para mostrar que es suprayectiva, sea f Φ 2X∈ . Define A={ | . A y ( ) 1}x x X f x∈ = X∈℘ y ( )A fΦ = .

4.24 Construir 2χ donde 3

2 2 .χ ∈

Solución. {(0 . ,1), (1,1), (2,0)} 4.25 Sea : ,f X Y→ Sea : ,g X Y→ { |A x x X= ∈ y ( ) ( )}f x g x= y sea

la inyección identidad. Mostrar que :i A X> − > .f i g i=o o Sea B cualquier

otro conjunto de X con la función inyectiva identidad de :j B X> − > B tal que .f j g j=o o Pruebe que .B A⊂

Solución. ( )( ) ( ( )) ( ) ( ) ( ( )) ( )( ) f i x f i x f x g x g i x g i x x A= = = = = ∀o o ∈ . Sea x∈B. Entonces ( ( )) ( ( ))f j x g j x= . ( ) ( )f x g x= . x∈A, pues x∈X y ( ) ( )f x g x= . B A. ⊂

4.26 Sea :f X Y→ y Pruebe que existe una relación de equivalencia :g X Y→ . R

en Y tal que si : /R Y Y Rφ − >> que es el mapeo cociente, entonces ,R Rg fφ φ= o

fo y mas aun, si T es cualquier otra relación de equivalencia en Y

tal que ,T Tgφ φ=o o entonces ,R T⊂ es mas fina que Por lo que existe una tal que

/Y R / .Y T: / /t Y R Y T− >> .R Tt φ φ=o .

Solución. Sea { ( ) y es una relación de equivalencia en talSS X X S YΣ = ∈℘ ×que }s sf gφ φ=o o . Por sφ se entiende al mapeo cociente asociado a la relación de equivalencia S. s sf gφ φ=o o si y solo si ( ) ( )s sf x g xφ φ=o o

x S∀ ∈ si y solo si ( ) ( ) f x g x x XS S= ∀ ∈ si y solo si ( ( ), ( )) f x g x S x X∈ ∀ ∈ .

X Y× ∈Σ porque Y es una relación de equivalencia en Y y ciertamente Y×( ( ), ( )) f x g x Y Y x X∈ × ∀ ∈ . Entonces Σ ≠∅ . R= ΣI es una relación de equivalencia en Y.. ver 3.13. Para mostrar que R Rf gφ φ=o o uno debe mostrar que ( ( ), ( ))f x g x R∈ . Pero ( ( ), ( )) f x g x S S∈ ∀ ∈Σ . Entonces ( ( ), ( )) f x g x R x X∈ Σ = ∀ ∈I . Como , R R T T= Σ ⊂ ∀ ∈I Σ . Define

:Y Yt R T→> tal que ( )y yt R T= . El hecho de que t es función es claro salvo,

posiblemente, esta propiedad: y zR R= implica que ( , )y z R∈ con lo cual

, que a su vez implica ( , )y z T∈ y zT T= . ( ) ( )y zt tR R= . t es suprayectiva: si

y YT ∈ T entonces ( )y yt R T= .

4.27 Sea :f X Y→ y Sea la identidad en Probar que : .g X Y→ g fo .X f es una

inyección y es una sobreyección. g

Solución. La prueba es similar a la de 4.14. 4.28 Sea :f X Y→ y Sea la identidad en : .g X Y→ g fo X y f go la identidad

en Probar que .Y f y son biyectivas y g 1.g f −=

Solución. Por 4.27, f es inyectiva y g es suprayectiva y tambien g es inyectiva y f es suprayectiva. Por lo tanto ambas son biyecciones. Ahora es ( , )x y f∈ . ( , ) Xx x I∈ implica que ( , )x z f∈ y ( , )z x g∈ para alguna z∈Y. ( , )x z f∈ y ( , )x y ∈ f implica que z=y. Entonces ( , )y z g∈ . Sea ( , )y x g∈ . Implica que

( , )y w g∈ y para algún w( , )w y f∈ ∈X. ( , )y w g∈ y ( , )y x g∈ implica que x=w. Por lo tanto ( , )x y f∈ . ( , )x y f∈ si y solo si ( , )y x g∈ . G= 1f − .

4.29 Sea Probar que si .Xh X∈ h fo h g,= o entonces f g= para toda , Xf g X∈ si

y solo si es una inyección. h

Solución. Supóngase que h no es inyectiva. Entonces 1( ) ( )h x h x2= para algunas

1 2,x x X∈ , 1 2x x≠ . Sean g, f funciones definidas como sigue: tal que y

:g X X→

1( ) g x x x X= ∀ ∈ :f X X→ tal que 2( ) f x x x X= ∀ ∈ . f, g XX∈ . f g. hof=hog.

≠

Supóngase que h f=hog y f o ≠ g. Si f ≠ g entonces 1( ) ( )1f x g x≠ para algún

1x ∈X. con 1 1( ( )) ( ( ))h f x h g x= 1( ) ( )1f x g x≠ significa que h no es inyección. 4.30 Sea Probar que si .Xh X∈ ,f h g h=o o entonces f g= para toda , Xf g X∈ si

y solo si es una sobreyección. h

Solución. Supóngase que h no es suprayectiva. Existe una 1x X∈ tal que . Como h1( ) h x x x X≠ ∀ ∈ XX∈ nunca toma el valor 1x , podemos concluir que

X 1{ }x≠ . Además, el teorema es verdadero si X=∅ . Entonces sea 2x X∈ con

2 1x x≠ . Define funciones f, g XX∈ como sigue: :f X X→ tal que 2( )f x x=

1 1 1, , ( ) ; :x X x x f x x g X X∀ ∈ ≠ − → tal que 2( ) g x x x X− ∀ ∈ . Entonces f g≠ y ( ( )) ( ( )) f h x g h x x X= ∀ ∈ .

Supóngase para la implicación opuesta que g h g h=o o y f g≠ . Entonces existe una 1x X∈ tal que 1( ) ( )2f x g x≠ . Entonces nunca toma el valor ( )h x 1x , de lo contrario . Entonces h no es suprayectiva. 1( ( )) ( ( ))h f x h g x≠ 1

4.31 Sea X un conjunto. Probar que XX junto con la hipótesis de que la funcional

identidad es un monoide.

Solución. La composición funcional es composición relacional, la cual se ha probado que es asociativa en el ejercicio 3.4. la operación en XX es el conjunto {(( , ), ) | (( , ), ) ( ) y }X X Xf g h f g h X X X h g f∈ × × = o . Que la composición de dos funciones sea una función deberá ser verificado. XI es, por supuesto, el elemento neutral.

4.32 Probar que ,ς El conjunto de inyecciones de ,X constituyen un submonoide de

y que este submonoide es un semigrupo izquierdo. ( ,XX o)

1 1

Solución. Se requiere demostrar que la composición de dos funciones inyectivas es inyectiva. implica que 2( ( )) ( ( ))g f x g f x= 2( ) ( )h x f x= por la inyectividad de g y 2( ) ( )1f x f x= implica que 1 2x x= por la inyectividad de f.

4.33 Probar que ,ς El conjunto de inyecciones de ,X constituyen un submonoide de y que este submonoide es un semigrupo derecho. ( ,XX o)

Solución. La composición de dos funciones suprayectivas es suprayectiva. y∈X implica que ( )f z = y para alguna z∈X. ( )f z X∈ implica que para alguna x∈X. Entonces existe una x

( )g x z=∈X tal que ( ( ))f g x y= . f g es suprayectiva. o

4.34 Sea .ϑ ς δ= ∩ Probar que ϑ es un submonoide de ( y, aun mas, es un

grupo. Este es llamado el grupo simétrico de , )XX o

X .

Solución. La composición de dos biyecciones es una biyección. Si f es una biyección, entonces 1f − es una biyección. 1 1

Xf f f f I− −= =o o . 4.35 Sea .f ϑ∈ Probar que f es una relación reflexiva si y solo si ,Xf I= la

identidad de .ϑ

Solución. Por 3.10, f es reflexiva si y solo si XI f⊂ . Por 4.13, XI f⊂ si y solo si XI f= .

4.36 Sea .f ϑ∈ Probar que f es una relación transitiva si y solo si f es un elemento

idempotete de ;ϑ i.e., 2.f f=

Solución. f es transitiva si y solo si f f ⊂o f por 3.10. f f f⊂o si y solo si f f f=o se prueba como sigue. Claramente f f f=o implica f f f⊂o .

Para el inverso, asúmase que ( , )x y f∈ . y∈X implica que para alguna z∈X. Entonces

( , )y z f∈( , )x z f f∈ o . ( , )z f∈ . ( , )x y f∈ y ( , )x z ∈x f implican

que y=z. Por lo tanto ( , )x y f f∈ o .

4.37 Sea f ϑ∈ . Prueba que f es una relación transitiva si y solo si f es un elemento idempotente de ϑ ; i. e., 2f f= .

Solución. f es simétrica si y solo si f= 1f − por 3.10 f= 1f − si y solo si Xf f I=o .

CAPITULO 5 Familias

5.0 Definición de familia. Una familia ( )i i IX ∈ es una función con dominio I y valor iX para cada

. i I∈Definición de la unión de una familia ( )i i IX ∈ .

( ) { |i i i Ii I

iX rango X x x X∈∈

= =UU ∈ para alguna }i I∈ .

Definición de la intersección de una familia ( )i i IX ∈ , I ≠∅ .

( ) { |i i i Ii I

iX rango X x x X∈∈

= =II ∈ para toda }i I∈ , I ≠∅

Definición del producto cartesiano de una familia ( )i i IX ∈ .

{( ) | }i i i I ii I

iX X x X∈∈

= ∈∏

Definición de la función proyección. Sean ( )i i IX ∈ , dados. Entonces definimos, J I⊂

:J i ii I i I

proj X X∈ ∈

→∏ ∏ tal que

( ) ( )J i i I i i Jproj X X∈ ∈=

5.1 Sea 0 { , }X a b= , 0 { }X A= , 0 { , , }X α β γ= , 3I = . Construye ( )i i IX ∈ y ii I

X∈∏ .

Solución.

0 1 2( ) {(0, ), (1, ), (2, )} {(0,{ , }), (1,{ }), (2,{ , , })}

{{(0, ), (1, ), (2, )},{(0, ), (1, ), (2, )},

{(0, ), (1, ), (2, )},{(0, ), (1, ), (2, )}, {(0, ), (1, ), (2,

i i I

ii I

X X X Xa b A

X a A a A

a A b Ab A

α β γ

α β

γ αβ

∈

∈

==

=

==

∏

)},{(0, ), (1, ), (2, )}}b A γ

5.2 Sea , 3I = iX i= para toda . Construye (3i∈ )i i IX ∈ y i

i I

X∈∏ .

Solución. 3( ) ; i i I i

i I

X I X∈∈

= =∏ ∅

5.3 Sea , 3I = 1oX = , , 1 2X = 3 3X = . Construye ( )i i IX ∈ y i

i I

X∈∏ .

Solución.

( ) {(0,1), (1,2), (2,3)}

{{(0,0), (1,0), (2,0)},{(0,0), (1,0), (2,1)},

{(0,0), (1,0), (2, 2)},{(0,0), (1,1), (2,0)}, {(0,0), (1,1), (2,1)},{(0,0), (1,1), (2, 2)}}

i i I

ii I

X

X∈

∈

=

=

==

∏

5.4 Prueba que 0 1

2i

i

X X X∈

× ∏: .

Solución. Define 0 12

: ii

f A A A∈

× >→>∏ tal que 0 1 0 1( , ) {(0, ), (1, )}f a a a a= . Prueba que

f es una biyección. 5.5 Sea . Prueba que existe una inyección de 2X ≠ ∅ 0 1X X× a

3i

i

X∈∏ ¿Sigue existiendo esta

inyección si 2X =∅ ? Solución. Sea . Define 2c X∈ ≠∅ 0 1

3

: ii

f X X X∈

× >→>∏ tal que

0 1 0 1( , ) {(0, ), (1, ), (2, )}f a a a a c= . Prueba que f es una biyección. si xX =∅ entonces

. En este caso existe una iyección si y solo si 3

ii

X∈

= ∅∏ 1X =∅ o 2X =∅ .

5.6 Prueba que existe una inyección de i

i I

X X∈

×∏ a ( ii I

)X X∈

×∏ . ¿Hay una biyeción?

Solución. Define : ( )i i

i I i I

A A A A∈ ∈

× >→> ×∏ ∏ ( , ( ) ) (( , ))i i I i i If a a a a tal que f ∈ ∈= . El

argumento de que f es una inyección es como sigue: Sea ( , ( ) ) ( , ( ) )i i I i i If a a f b b∈ ∈= .

. ( ,(( , )) (( , ))i i I i i Ia a a a∈ ∈= ) ( , ) i ia a b b i I= ∀ ∈ . a b= y i ia b i I= ∀ ∈ . a y

. y

b=( ) ( )i i I i i Ia b∈ ∈= ( , ( ) ) ( , ( ) )i i I i i Ia a b b∈ ∈= f .

En caso de que 2A I= = y 0 1 1A A= = no hay biyección. 5.7 Sea { | }jI j J∈ una partición de un conjunto I . Prueba entonces que

( )j

i ii I j J i I j

X X∈ ∈ ∈∏ ∏ ∏: .

Solución. define :j

i ij J i I i I

f A A∈ ∈ ∈

⎛ ⎞>→>⎜ ⎟⎜ ⎟

⎝ ⎠∏ ∏ ∏ tal que ((( ) ) ) ( )

ji i I j J i i If a a∈ ∈ = ∈

⎟⎟

. A cada

miembro de corresponde un miembro de j

ii J i I

A∈ ∈

⎛ ⎞⎜⎜⎝ ⎠

∏ ∏ ii I

A∈∏ y viceversa.

(( ) ) (( ) )ji i I j J i i I j Ja b∈ ∈ ∈ ∈j

= si y solo si ( ) ( ) j ji i I i i Ia b j∈ ∈ J= ∀ ∈ si y solo si

y si y solo si i ia b i I= ∀ ∈ j j J∀ ∈ i ia b i I= ∀ ∈ si y solo si ( ) ( )i i I i i Ia b∈ ∈= . f es una biyeción.

5.8 ¿Sucede que ( ) (Y Yi i

i I i I

)X X∈ ∈∏ ∏: ?

Solución. define tal que : ( )C C

ii I i I

A A∈ ∈

Φ >→>∏ ∏ ( )f gΦ = donde

. La motivación para este mapeo se puede seguir de estas

líneas:

( )( ) ( )( ) , g i c f c i i I c C= ∀ ∈ ∈)( C

ii I

f A∈

∈ ∏ si y solo si ( ) ii I

f c∈

∈ A∏ si y solo si ( )( ) if c i A∈ si y solo si

( ( )( )) Cc C if c i A∈ ∈ si y solo si (( ( )( )) ) C

c C i I ii I

f c i A∈ ∈∈

∈∏ .

5.9 Sean , ( ) familias dadas. Muestra que ( )i i IX ∈ i i IY ∈( , )

( ) ( ) (i i ii I i I i j I J

X Y X∈ ∈ ∈ ×

)iY× = ×U U U .

Solución. ( , ) ( ) ( )i

i I j Jjx y X

∈ ∈

∈ ×U UY si y solo si ii I

x X∈

∈U y ii I

y Y∈

∈U si y solo si ix X∈

para algún i y I∈ jy Y∈ para alguna j J∈ si y solo si jx X∈ y jy Y∈ para algún

si y solo si ( , )i j I J∈ × ( , ) i jx y X Y∈ × para algún ( , )i j I J∈ × si y solo si

( , )

( , ) i ji j I J

x y X∈ ×

∈ ×U Y .

5.10 Sea F el conjunto de todas las funciones real-valuadas definidas en el intervalo [0 . Expresa a F

como un conjunto exponencial y también exprésalo como un producto cartesiano. ,1]

Solución. o [0,1)

[0,1]

; i∈∏¡ ¡

[0,1]

, i ii

X X∈

=∏ ¡ .

5.11 Para un conjunto X ; sea la familia de todos los subconjuntos de ( )i i IX ∈ X indicados por si

mismos. i. e. ( ) 1I P X= − y iX i= . ii I

X∈∏ es llamado el conjunto de todas las funciones a

elegir de para X . ¿Es el nombre apropiado? Solución. .

( 1)i

i I A P X

X A∈ ∈ −

=∏ ∏( 1)A P X

f A∈ −

∈ ∏ si y solo si : ( 1)f P X X− → tal que

( )f A ∈ A . El hecho de que f asigna a todo subconjunto no vacío de X algún miembro de ese subconjunto, ha dado a f el nombre de “función de elección”. 5.12 Muestra que [ , 1)i i

i N

+

∈∏ ¡¡ : ¡

Solución. Define [ , 1): i i

i ω

+

∈

Φ >→>∏¡¡ ¡ tal que ( ) ( [ , 1))if f i i ω∈Φ = ∩ + .

( ) ( )f gΦ = Φ si y solo si ( [ , 1)) ( [ , 1))i if i i g i iω ω∈ ∈∩ + = ∩ + si y solo si

para toda i[ , 1) [ , 1)f i i g i i∩ + = ∩ + ω∈ si y solo si. f g= . entonces Φ es una inyección..

Para probar que es suprayectiva, sea Φ [ , 1)i i

i

gω

+

∈

∈∏ ¡ . Entonces

. ( ( )) ( ( ) [ , 1)) ( ( ))i ii i

g i g i i i g i gω ωω ω

∈ ∈∈ ∈

Φ = ∩ + =U U =

5.13 Sea dada con para cada 3( )i iX ∈ iX = ¡ 3i∈ . Encuentra cada uno de los siguientes conjuntos e

interpretalos geométricamente en 3¡ .

{0,1} 3 0 1 2{( ) | 1i iproj X ax bx cx∈ + + = con 0}a b c+ + ≠ 2

{0,1} 33

{( ) | 1}i i ii

proj X x∈∈

=∑ .

Solución. La primera es la proyección de un plano en el espacio de tres dimensiones en el plano

0 1X X− . Si , la proyección es el plano 0c ≠ 0 1X X− . En el segundo ejemplo, la esfera unitaria es proyectada en un disco cerrado unitario.

CAPITULO 6 Funciones definidas en conjuntos potencia

6.0 Definición. Dada :f X Y→ . define

__

: ( ) ( )f P X P Y→ tal que {__

( ) | ( , )f A y x y f= ∈ para alguna }x A∈ . __

1 : ( )f P Y PX− → tal que {1__( ) | ( , )f B x x y

−

f= ∈ para alguna }y B∈ .

6.1 Sea :f X Y→ . Muestra que 1__

f−

es suprayectiva si y solo si f es inyectiva. Solución. Sean f inyectiva, ( )A P X∈ , ( )B f A= . Entonces tenemos

1 1( ) ( ( ))f B f f A− −= A= ; probando asi que 1f − es suprayectiva.. Ahora, supongamos que f no es una inyección. Entonces 1( ) ( )1f x f x= para dos elementos distintos

1x y 2x de X . Entonces 1f − no es suprayectiva, puesto que 11{ } ( )x f B−≠ para cualquier

( )B P Y∈ . Si 1( )X f B−∈ entonces 11 2{ , } ( )x x f B−⊂ y 1

1( ) { }f B x− ≠ . Por otra parte, si 1

1 ( )x f B−∉ , entonces claramente 11{ }f x− ≠ .

6.2 Sea :f X Y→ . Muestra que 1__

f−

es inyectiva si y solo si f es suprayectiva. Solución. Sea f suprayectiva y asume que 1 1

1 2( ) ( )f B f B− −= . Sea 1 1y B∈ . Entonces,

como f es suprayectiva, 1 ( )y f x= para alguna x X∈ . 1 11 2( ) ( )x f B f B− −∈ = . 2( )f x y=

para alguna 2 2y B∈ . 1 2y y= porque los valores de la función son únicos, dejando así que 1 2y B∈ .

1 2B B⊂ . Con un argumento simétrico tenemos que 2 1B B⊂ . 1 2B B= . 1f − es inyectiva. Si f no es suprayectiva, existe un 1y Y∈ tal que 1 ( )y f X∉ . Entonces 1 1

1( ) ({ })f f y− −∅ = y f no es inyectiva. 6.3 Sea :f X Y→ . Muestra que f es inyectiva si y solo si la imagen inversa bajo f de cada

conjunto que consta de un solo elemento en la imagen de f es un conjunto que nuevamente consta de un solo elemento en el dominio de f .

Solución. Sea f inyectiva y Im( )y f∈ . 1({ })x f y−∈ si y solo si ( )f x = y

f. Como

, existe al menos una Im( )y∈ 1({ })x f y−∈ . Dado que f es inyectiva puede existir, a lo mas, una

x tal que ( )f x = y . Entonces 1({ })f y− es un conjunto que consta de un elemento. Si f no es inyectiva existen 1, 2x x distintos tales que 1 2( ) ( )f x f x y= = . 1

1 2 } ({ }){ ,x x f y−⊂ , que no es un conjunto de un solo elemento. 6.4 Sea :f X Y→ . Muestra que f es suprayectiva si y solo si la imagen inversa bajo f de todo

subconjunto no vacío de Y es un subconjunto no vacío de X.

Solución. si f es suprayectiva y B es un subconjunto no vacío de Y , sea .

para alguna

y B∈ ( )y f x=x X∈ . 1( )x f B−∈ .

Además, supongamos la imagen inversa de todo conjunto no vacío bajo f es un conjunto no vacío de X . Sea . Entonces { es un subconjunto no vacío de y Y∈ }y X . Sea y Y∈ . Entonces { es un

subconjunto no vacío de Y .

}y1({ })f y− ≠ ∅ . ( )f x y= para algún x X∈ . Por lo tanto f es

suprayectiva. 6.5 Da de una manera no trivial la hipótesis faltante para el siguiente teorema: Si :f X Y→ y

es una familia con para toda i( )i i IA ∈ ( )iA P X∈ I∈ , entonces __ __

( ) (i ii I i I

)f A f∈ ∈

=I I A .

Solución. f es inyectiva.

6.6 Sea :f X Y→ . ¿Sucede que 1 1__ __ __( ) ( ) (

1

)f A B f A f B− −

− = −−

) para cualquier

, (A B P Y∈ ? Solución. si. 1

1 2( )x f B B−∈ − si y solo si 1, 2y B y B∈ ∉ tal que ( )y f x= si y solo si 1

1( )x f B−∈ y 12( )x f B−∉ si y solo si 1 1

1 2( ) ( )x f B f B− −∈ − .

6.7 Sea :f X Y→ . ¿Sucede que __ __ __

( ) ( ) ( )f A B f A f B− ⊂ − para cualquier , ( )A B P X∈ ?

¿Sucede que __ __ __

( ) ( ) ( )f A f B f A B− ⊂ − para cualquier , ( )A B P X∈ ? Solución. Si, para la segunda inclusión. Sea 1( ) ( )y f A f A∈ = 2 . Entonces 1( )y f x= para

alguna 1 1x A∈ y para cualquier ( )y f x≠ 2x A∈ . Esto implica que 1( )y f x= para 1 1 2x A A∈ − ,

lo que implica que 1 2(y f A A∈ − ) . Entonces 1 2 1( ) ( ) ( )2f A f A f A A− ⊂ − . No para la primera

inclusión. Sean f no inyectiva, 1 2 1( ) ( ), 2y f x f x x x= = ≠ . Entonces sea 1 1 2{ , }A x x= y

. Esto nos da un contraejemplo. 2 2{ }A x=

6.8 Sean :f X Y→ , para toda i( )iA P X∈ I∈ . Muestra que __ __

( ) (i ii I i I

)f A f∈ ∈

⊂I I A . Da un

contraejemplo para __ __

( ) ( )i ii I i I

f A f A∈ ∈

⊂I I .

Solución. Si ( i

i I

)y f A∈

∈ I entonces existe una x tal que ( )y f x= y ix A∈ para toda

. Esto implica que i I∈ ( )ix f A∈ para toda i I∈ , de lo cual tenemos que ( )ii I

x f A∈

∈I . Para el

contraejemplo, sea . 0 12, {0, 1}, {0, 2}, {(0,0)(1,1)(2,1)}I A A f= = = = 6.9 Sea 2( , ) 2f x y x y= + para todos los reales ,x y .

a) ¿Cual es el dominio de f ? b) ¿Cual es el codominio de f ?

c) ¿Cual es el rango de f ?

d) ¿Cual es ? [0 es el intervalo cerrado en 1__([0,1])f

−

,1] ¡ . e) ¿Es f inyectiva o suprayectiva?

{ }( , ) | 2A x y x y= + = . ¿Cuál es ( )f A ?

Solución. a) ס ¡ . b) Cualquier conjunto que contenga los reales no negagivos. c) Los reales no negativos. d) No inyectiva, pues (0,1) (1,0)f f= pero suprayectiva si Im( ) Cod( )f f= . e) El disco cerrado unitario con centro en el origen. f ) [1, )∞ .

CAPITULO 7 Aplicaciones de funciones

7.0 Definición. Sea G con operación :w G G G× → un grupo. Representamos entonces a w como

multiplicación: si ,x y G∈ , entonces ( , )w x y xy= . Sea , S G⊂ a G∈ . Por definición

{ }|aS ax x S= ∈ y { }|Sa xa x S= ∈ . Un subconjunto de es un subgrupo normal de

si y solo si es subgrupo de G y

N G GN 1x Nx N− = para toda x G∈ .

Un grupo conmutativo (monoide) es un grupo (monoide) tal que la operación w es conmutativa; Gxy yx= para cualesquiera ,x y G∈ . Sean G , H grupos (monoides) con sus respectivas operaciones expresadas multiplicativamente.

:f G → H es un homomorfismo si y solo si ( ) ( ) ( )f xy f x f y= para cualesquiera ,x y G∈ y

( )G Hf e e= . 1__

ker ( )Hf f e−

= . Definiciones. ( , , un anillo conmutativo con identidad, es un conjunto junto con dos operaciones (aquí representadas por + y ⋅ ) tal que es un grupo conmutativo y ( ,

, )R + ⋅( , )R + )R ⋅ es un monoide conmutativo tal que

( )x y z xy xz+ = + para todo . , ,x y z∈ ¡ Un subanillo A de R es un ideal si y solo si rA para todo A⊂ r R∈ . Sean R y anillos conmutativos con identidades. S :f R → S si y solo si es un homomorfismo para el grupo aditivo y el monoide multiplicativo. Definición un anillo conmutativo K con identidad es un campo si y solo si todo elemento diferente de cero de K tiene inverso multiplicativo. Definición. Sea K un campo y V un grupo conmutativo y una función K V V× → dada (representada multiplicativamente) tal que: , , ( )k x y kx ky+ = + ( )k m x kx mx+ = + ( ) ( )k mx km x= , 1x x= para cualesquiera

, ,k m K∈ ,x y V∈ . Entonces V es un espacio vectorial sobre el campo K . Un álgebra V sobre el campo K es un espacio vectorial sobre el campo K en el cual una multiplicacion (V V ). V× → , ( ) ( ) ( )k xy kx y x ky= = ( ) ( )x yz xy z= , ( )x y z xy xz+ = + , ( )x y z xz yz+ = + para cualesquiera

7.1 Sea :f X Y→ . Existe una partición XR de X , una funcion suprayectiva : XX Rφ → y una

inyección 1 : Xf YR → tal que 1f fφ =o . Este teorema sera referido en ejercicios posteriores

como el teorema fundamental de mapeo. Solución. Define la relación R en X : 1 2( , )x x R∈ si y solo si 1( ) ( )2f x f x= . Verifica que R

es una relación de equivalencia. Asociada a la relación de equivalencia esta una partición XR y una

función ( ) : Xx X Rφ →> suprayectiva (el mapeo cociente) tal que ( ) xx Rφ = . Define 1 : Xf YR →

tal que 1( ) (x )f f xR = . Ahora haremos varias verificaciones para establecer el teorema. a) 1f está bien

definida: sea 1 2x xR R= . Entonces 1

1 1 1 1( ) ( ) ( ) ( )xf f x f x f 2xR R= = = con la igualdad interior que

se sigue de la equivalencia de 1x y 2x . b) 1f es una inyección: sea 11 1( ) (x xf f 2 )R R= . Entonces

1 2( ) ( )f x f x= . 1 2( , )x x R∈ . 1 2x xR R= . c)

1 1 1 1: ( )( ) ( ( )) ( ) (x )f f f x f x f f xRφ φ φ= = =o o = .

7.2 Un grupo es un par ordenado ( , , un conjunto G y una función )G w :w G G G× → llamada

operación. Muestra que el conjunto G puede ser “retomado” desde eñ conjunto de pares ordenados w; i. e. Muestra que y (({ |G x x w= ∈UUUU , ), )x y z w∈ para algunas },y z .

Solución. La imagen inversa

porque para una relación que es una función, se tiene que la preimágen es igual al dominio de (véase la definición de función).

es en sí misma una relación de G a G con preimágen . Entonces la preimágen (de )

es {

{( , )|( , ) y (( , ), ) para algúna }w x y x y w x y z w z G= ∈ ∈ =UU G×

para algún }G G G x x G G G G y× = = ∈ × ∈ ×UU

w wG G×

{ | ( ) y ( , )x y w

| y (( , ), ) para algunos , }x x w x y z w∈ ∈UUUU y z

)

. 7.3 Sea una familia no vacia de grupos. Muestra que ((( , ))i i i IG w ∈ ,i

i I

G w∈∏ es un grupo, donde w esta

definida como sigue: : i i i

i I i I i I

w G G G∈ ∈ ∈

× →∏ ∏ ∏ ,( , ) (( ) ( ) ) ( ( , ))i i I i i I i i i i Iw x y w x y w x y y = ∈ ∈ ∈= . Este grupo es

llamado el grupo producto. Solución. Como tenemos ( , )i i i iw x y G∈ ( ( , ))i i i i I i

i I

w x y G∈∈

∈∏ y está bien definido. El que

sea asociativo se muestra como sigue:

w

w

,

( , ( , )) (( ) , (( ) , ( ) ))(( ) , ( ( , ) )) ( ( ( , )))(( ( , )) , ( ) )( (( ) , ( ) ), ( ) )( ( , ), )

i i I i i I i i I

i i I i i i I i i i i i i I

i i i i I i i I

i i I i i I i i I

w x w y z w x w y zw x w y z w x w y zw w x y zw w x y zw w x y z

∈ ∈ ∈

∈ ∈

∈ ∈

∈ ∈ ∈

== =

===

∈

( )i i Ie e ∈= es el elemento identidad. ( , ) (( ) , ( ) ) ( ( , )) ( )i i I i i I i i i i I i i Iw x e w x e w x e x x∈ ∈ ∈ ∈= = = =

=

.

También . . También

.

( , )w e x 1 1 1( , ) (( ) , ( ) ) ( ( , )) ( )i i I i i I i i i I i i Iw x x w x x w x x e e− − −∈ ∈ ∈ ∈= = =

1( , )w x x e− =

7.4 Sea un subgrupo normal de un grupo G . Sea N ( , )x y S∈ si y solo si 1xy− ∈N . Muestra que S es

una relación de equivalencia en G. Define una operación en la partición G S como sigue:

( )y xyxS S S⋅ = . Muestra que la operación esta bien definida; i. e., es independiente del

representante de la clase de equivalencia XS . Muestra que respecto a la operación definida, G S es

un grupo, y lo llamamos el grupo cociente G N ; i. e. :G GN = S . Sea φ el mapeo cociente

GG S→> . Muestra que N es el elemento neutro de G N . Muestra que ( )Ge Nφ = . Prueba que

( )x x xS N φ= = .

Solución. es un subgrupo normal de un grupo G si y solo si es un subgrupo de y N N ( , )G g

1x Nx N− = para toda x G∈ . ( , )x y S∈ si y solo si 1xy− N∈ . Que sea una relación de

equivalencia se verifica como sigue.

S1xx e− N= ∈ . Sea 1xy N− ∈ . 1 1( )xy N− − ∈ . 1 1 1( )y x N− − − ∈ .

1yx− ∈N . Ahora sea 1xy N− ∈ y 1yz N− ∈ . 1 1xy yz N− − ∈ . 1xez N− ∈ . 1xz N− ∈ . Para probar que

la operación definida en G S es independiente del representante de la clase de equivalencia escogido, sea

1x xS S= y 1y y

S = S . Entonces 1xx N− ∈ , y 1yy− N∈ . Usando subíndices sobre como notación

para elementos de ,

n

N 1 1x n x= y 1 1y n y= . 1 1 1 11 1 1 1 2 1 1 1 1 2 1 1 3( ) ixy x y n x n y y x n x n x n n N− − − −= = = ∈ .

Entonces 1 1x y xyS = S . La operación en G S es asociativa.

( ) ( )( ) ( )y yz x yz xy z xy yx x xz z zS S S S S S S S S S S S= = = = = . e x ex x

S S S S= = .

x e xe xS S S S= = .

1 1x x xx eS S S S

− −= = .

1 1x x x es S S S

− −= =x .

( ) ( ) ( )xy yxxy xS S Sφ φ= = = yφ .

1{ | ( , ) } { | } { | }e x x e S x xe N x x N NS−= ∈ = ∈ = ∈ = . ( ) ee NSφ = = .

1( ) { | } { | }xx y yx N y y xN xNSφ −= = ∈ = ∈ = .

7.5 Sea :f X Y→ un homomorfismo de grupos. Entonces, por el teorema fundamental de mapeos,

existe una partición XT (una relación de equivalencia T en X con ( , )x y T∈ si y solo si

( ) ( )f x f y= ), una función suprayectiva : XXφ →> T (el mapeo cociente), una inyacción

1 : Xf YT >→ tal que 1f fφ =o . Sea , el kernel del homomorfismo 1__( )YN f e

−

= f . Muestra

que es subgrupo normal de N X y que ( , )x y T∈ si y solo si 1xy N− ∈ . Refiriendo al ejercicio

anterior, observa que XN es un grupo cociente ( X

T= ) y que φ es un epimorfismo. Prueba que

1f es monomorfismo (por definición un homomorfismo inyectivo). En suma: existe un grupo cociente

XN , un epimorfismo : XX Nφ →> , un monomorfismo 1 : Xf YN >→ tal que 1f f φ= o .

Prueba además que f es un monomorfismo si y solo si ker { }Xf e= . Solución. 1( )YN f e−= es un subgrupo de X si y solo si 1xy− N∈ para toda , x y N∈ . Sean

, x y N∈ . Entonces ( ) Yf x e= .. entonces 1xy N− ∈ y es un subgrupo. es un subgrupo normal si

y solo si

N N1x Nx N− = para toda x X∈ . Sea n N∈ . Entonces

1 1 1( ) ( ) ( ) ( ) ( ) ( )Y Yf x nx f x f n f x f x e f x e− − −= = = . Y se ha mostrado entonces que 1x Nx N− ⊂ . Sea

; n N∈ 1n x−= 1 1 11x xnx x x n x− − −= . Entonces y para toda 1N x N−⊂ x 1N x Nx−= x X∈ .

( , )x y T∈ si y solo si ( ) ( )f x f y= si y solo si 1( )[ ( )] Yf x f y e− = si y solo si 1( ) Yf xy e− = si y solo

si 1xy N− ∈ . 1 1 1 1( ) ( ) ( ) ( ) ( ) ( ) (y xy yx xf f f xy f x f y f fN N N N N= = = = ) .

[ ( ) ( )f x f y= implica x y= ] si y solo si [ 1( ) Yf xy e− = implica x y= ] si y solo si [ ( ) Yf a e=

implica ] si y solo si [Xa e= ( ) Yf a e= implica Xa e= ] si y solo si [ ker { }Xf e= ]. 7.6 Sean A un ideal de R , un anillo conmutativo con identidad, ( , )x y S∈ si y solo si x y A− ∈ .

Muestra que S es una relación de equivalencia en R . Define operaciones +,· en la partición RS de la

siguiente manera: ( )y x yx

S S S++ =

( )y xyxS S S⋅ =

y muestra que las operaciones estan bien definidas en RS . Prueba que R

S es un anillo

conmutativo con unidad. Denota este anillo con RA , al cual se le llama el anillo de la clase residual o anillo

cociente. Sea φ el mapeo cociente RR S→> . Muestra a que φ es un epimorfismo. Prueba que

__( )x x A xS φ= + = .

Solución. Primero, la relación definida es una relación de equivalencia en R . 0x x A− = ∈ . Si x y A− ∈ , lo que implica que . Sea y x A− ∈ x y A− ∈ y y z A− ∈ . Entonces ( ) ( )x y y z A− + − ∈ y z A− ∈. .

Sea 1xxS S= y 1yy

S = S . Entonces 1 Ax x ∈− y 1y y A− ∈ . 1 1( )x y x y A+ − + ∈ . Entonces

1 1( )( ) x yx yS

++ = S l la adición está bien definida. Ahora, consideremos , que representa miembros

de

aA , mostramos ahora que la multiplicación en la partición está bien definida. Sea

x 1 1 1 2, x a y y a= + = + 1 1 1 2 1 1 1 1 2 1 1 2 1 1 3( )( ). xy x a y a x y a y a x a a x y a= + + = + + + = + . Entonces

1 1xy x y A− ∈ y 1 1x yxyS S= .

La verificación de las leyes asociativa, conmutativa, y distributiva es trivial. Por ejemplo, aquí mostramos la ley distributiva:

( )( ) ( )y y z xy xz xy yx x xz x xz zS S S S S S S S S S S S

+ ++ = = = + = + .

e x ex xS S S S= = .

( )( ) ( ) (x y yx )x y xS S Sφ φ++ = = + = + yφ .

( ) ( ) ( )xy yxxy xS S Sφ φ= = = yφ .

{ | } { | } ( )x y y x A y y x A xS φ= − ∈ = ∈ + = .

7.7 Sea :f R Q→ un homomorfismo de anillos. Muestra que existe un anillo cociente RA , un

epimorfismo : RR Aφ →> , un monomorfismo 1 : Rf QA >→ tal que 1f f φ= o .

Solución. Uno aplica el teorema fundamental de mapeos y verifica las propiedades algebraicas como en 7.5. sea 1(0 )SA f −= . A es un ideal de R porque si ( ) 0 , ( ) 0S Sf x f y= = r R∈

S= y y

entonces y . Considerando a T como la relación de

equivalencia mencionada en el teorema fundamental de mapeos, tenemos ( ,

r R∈( ) 0Sf x y− = ( ) ( ) ( ) ( )0 0Sf rx f r f x f r= =

)x y T∈ si y solo si

( ) ( )f x f y= si y solo si si y solo si ( ) ( ) 0Sf x f y− = ( ) 0Sf x y− = si y solo si x y A− ∈ .

Entonces RA de 7.6 y R

T del teorema fundamental de mapeos es el mismo.

1 1 1( )( ) ( ) ( ) ( ) ( ) ( ) (y x yx xf f f x y f x f y f f1 )y

A A A A++ = = + = + = + A .

1 1 1 1( )( ) ( ) ( ) ( ) ( ) ( ) (y xyx xf f f xy f x f y f f )y

A A A A= = = = A .

7.8 Sea :f X Y→ . Muestra que existe una relación de equivalencia en S X , una función

suprayectiva : XX Sφ →> , una biyección : Xg S >→> ( )f X y una inyección (identidad)

: ( )f X Yψ >→ tal que f gψ φ= o o .

( )

f

g

X Y

X f XS

φ ψ

⎯⎯→

↓ ↑

⎯⎯→

Solución. Por el teorema fundamental de mapeos, existe una relación de equivalencia en S X ,

una suprayección : XX Sφ →> y una inyección 1 : Xf YS >→> tal que 1f f φ= o . Sea

: (Xg fS >→> )X tal que 1( ) ( )x xg fS S= y : ( )f X Yψ >→ tal que ( )y yψ = . Entonces

1f gψ= o y g es tanto suprayectiva, como inyectiva. Para toda ( )y f X∈ existe una x X∈ tal que

. Entonces ( )y f x= 1( ) gxy f S S= = .

7.9 Sean 1 :p A B A× →> tal que 1( , )p x y x= , 2 :p A B B× →> tal que 2 ( , )p x y y= ,

:f X A→ y . Muestra que existe un a única función :g X B→ : X A Bφ → × tal que

1p fφ =o y 2p gφ =o .

1 2

f g

p p

X

A A B B

φ↓

←⎯⎯ × ⎯⎯→

[ ]

1 2__

f g

i i

X

A A B B

φ↑

⎯⎯→ ∪ ←⎯⎯

Z ^

Solución. 1 :p A B A× →> y 2 :p A B B× →> son proyecciones. Sea la función

: X A Bφ → × definida como sigue: ( ) ( ( ), ( ))x f x g xφ = . Entonces

1 1 1( )( ) ( ( )) ( ( ), ( )) ( )p x p x p f x g x f xφ φ= = =o y

2 2 2( )( ) ( ( )) ( ( ), ( )) ( )p x p x p f x g x g xφ φ= = =o .

Ahora, sea ψ cualquier otra función de X a A B× tal que 1p fψ =o y 2p gψ =o . Supóngase que

1 2( ) ( , )x y yψ = . Entonces 1 1 2 1( , ) ( )p y y y f x= = y 2 1 2 2( , ) ( )p y y y g x= = . Entonces φ ψ= .

7.10 Sean , i A tal que __

( {0}) ( {1})A B A B∪ = × ∪ ×__

1 : A B→> ∪ 1( ) ( ,0)i x x= ,

tal que ,

__

2 :i B A B→> ∪

2 ( ) ( ,1)i x x= :f A X→ y . Muestra que existe un a única función

tal que

:g B X→__

: A B Xφ ∪ → 1i fφ =o y 2i gφ =o . Solución. ( {0}) ( {1}A B A B∪ = × ∪ × ) . Define : A B Xφ ∪ → tal que ( ,0) ( )a f aφ = y

( ,1) ( )b g bφ = . Entonces 1 1( )( ) ( ( )) ( ,0) ( )i a i a a f aφ φ φ= = =o y

2 2( )( ) ( ( )) ( ,1) (i b i b b g b)φ φ φ= = =o . La verificación de la unicidad es trivial. 7.11 Sean G un grupo, un conjunto. Para X ≠∅ , Xf g G∈ define :fg X G→ tal que

( )( )fg x ( ) ( )f x g x x X= ∀ ∈ . Muestra que es un grupo con la operación definida. Prueba que

si es un grupo conmutativo, entonces es conmutativo. Prueba que existe un monomorfismo (un homomorfismo inyectivo) .

XGG XG

: XG GΦ >→

Solución. la operación es asociativa. ( )( ) ( )( )( ) ( )[ ( ) ( )] [ ( ) ( )] ( ) ( )( ) ( ) ( ) ( )f gh x f x gh x f x g x h x f x g x h x fg x h x fg h x= = = = = . Sea la identidad de G . Entonces la función constante (también llamada e ) tal que e :e X G→ ( )e x e=

para toda x X∈ es la identidad de . XG ( )( ) ( ) ( ) (f )e x f x e x f x= = y ( .

Ahora, dada

)( ) ( ) ( ) ( )ef x e x f x f x= =:f X → G , sea la función con valores :g X G→ 1( ) ( ( ))g x f x −= que es, para cada x

la inversa en G . Entonces 1( )( ) ( ) ( ) ( )( ( ))fg x f x g x f x f x e−= = = . Similarmente, y cada

miembro de tiene inversa.

gf e=XG

Si es conmutativo, entonces se verifica fácilmente que también es conmutativo. Define

tal que es este miembro de , G XG: XG GΦ >→ ( )aΦ XG ( ) :a X GΦ → tal que ( )( )a x aΦ = para toda

x X∈ . En otras palabras, es la función constante con el valor . ( )aΦ a Φ es un homomorfismo, para . ( )( ) ( )( ) ( )( ) ( ( ) ( ))( )ab x ab a x b x a b xΦ = = Φ Φ = Φ Φ

Si , entonces G consta de una sola función. Si es entonces, no trivial, entonces no es inyectiva. Por otra parte, si supóngase que

X ≠∅ ∅ G ΦX ≠∅ ( ) ( )a bΦ = Φ . Entonces ( ) ( )a bΦ = Φ . Entonces

para toda ( )( ) ( )( )a x b xΦ = Φ x X∈ . Sea 1x un miembro de X ≠∅ . 1 1( )( ) ( )( )a x b xΦ = Φ .

, dándonos así Φ inyectiva. a b= 7.12 Sean R un anillo, un conjunto X ≠∅ . Prueba que existe un anillo XR y un monomorfismo

: XR RΦ >→ usando una construcción similar a la del ejercicio anterior. Muestra que es posible que R sea campo y XR no lo sea.

Solución. Las operaciones para el anillo de funciones son las siguientes y obvias: ( )( ) ( ) ( )f g x f x g x+ = + , ( )( ) ( ) ( )fg x f x g x= para toda x X∈ . El elemento cero del anillo es la

función constante con valor 0, x X∀ ∈ . Existen funciones en XR , dado que X tiene al menos dos elementos, que son el cero para algunos valores y diferente de cero para otros. Estas funciones no tienen inverso multiplicativo en XR . Entonces XR no es, en general, un campo aún cuando R lo es. 7.13 El conjunto es un anillo con las siguientes tablas de suma y multiplicación: 2

0 10 0 11 1 0

+

0 10 0 01 0 1

⋅

2X , el conjunto de las funciones características en un conjunto X ≠∅ , es entonces un anillo por el ejercicio anterior. Prueba los siguientes resultados.

1A B A B

A A

A B A B A B

χ χ χχ χχ χ χ χ χ

∩

′

∪

== −= + −

Prueba que el anillo conmutativo con identidad ( , ,PX )+ ∩ es isomorfo al anillo (2 , el anillo es llamado un anillo Booleano. Observa que la operación “+” junto con puede ser

tomado como diferencia simétrica (descrita en el ejercicio 1.32).

, , )X + ⋅( , ,PX + ∩) PX

Solución. Asúmase x A B∈ ∩ . Entonces x A∈ y x B∈ . ( )A x Iχ = y ( ) 1B xχ = .

( ) ( ) 1A Bx xχ χ = . ( )( )A B x 1χ χ = . Supongamos que x A B∉ ∩ . Entonces x A∉ o x B∉ .

( ) 0A xχ = o ( ) 0B xχ = . ( )( )A B x 0χ χ = . Entonces hemos probado que A B A Bχ χ χ∩ = . Si x A′∈ entonces x A∈ . ( ) 1A xχ = . 1 ( )A x 1χ− = . Entonces hemos probado que 1A Aχ χ′ = − . Si x A B∈ ∪ entonces ( x A∈ y x B∈ ) o ( x A∈ y x B∉ ) o ( x A∉ y x B∈ ). ( ( ) 1A xχ = y

( ) 1B xχ = ) o ( ( ) 1A xχ = y ( ) 0B xχ = ) o ( ( ) 0A xχ = y ( ) 1B xχ = ).

( ) ( ) ( ) 1A B A Bx x xχ χ χ χ+ − = . Además, si x A B∉ ∪ entonces x A∉ y x B∉ . ( ) 0A xχ = y

( ) 0B xχ = . ( ) ( ) ( ) ( ) 0A B A Bx x x xχ χ χ χ+ − = . Entonces A B A B A Bχ χ χ χ χ∪ = + − . En referencia a 4.23, uno sólo tiene que probar que Φ es un homomorfismo. Esto requiere que

A B A Bχ χ χ+ = + y A B A Bχ χ χ∩ = , lo cual puede ser verificado.

7.14 Sea R un anillo conmutativo con unidad. Para X ≠∅ , XR es un anillo por el ejercicio 7.10. Sean

, . Prueba que D X⊂ { | ( ) 0, y }XA f f x x D f R′= = ∀ ∈ ∈ A es un ideal de XR . Sea

y conjuntos tal que X ≠∅ D′ D′ contiene un único elemento y R un campo. Prueba que XR

A

es un anillo. Prueba que XR

A es un campo.

Solución. f A∈ y implica que g A∈ ( ) 0f x = y ( ) 0g x = para toda x D′∈ .

para toda ( ) ( ) 0f x g x− = x D′∈ . f g A− ∈ . Ahora supongamos que Xf R∈ y . g A∈ ( ) 0g x = para toda x D′∈ . para toda ( ) ( ) 0f x g x = x D′∈ . fg A∈ . A es un ideal.

Sea R un campo y . { }D a′ = A es entonces el conjunto de todas las funciones que son cero en .aXR

A

es un anillo por 7.6 y A es su elemento neutri. Para probar que XR

A es un campo, sea fA un elemento

no cero de XR

A . Entonces f A∉ y ( ) 0f a ≠ . Si 1 representa a la identidad multiplicativa de R ,

entonces representa a la función por el mismo símbolo. Sea g la función constante tal que

. en 1( ) ( ( ))g x f a −= ( ) ( ) 1 0f a g a − = R . Entonces 1fg A− ∈ o 1fg A= .

7.15 Sea un conjunto y X ≠∅ K un campo. Utilizando el hecho de que K con la adición es un grupo,

prueba que es un grupo conmutativo. Prueba que es un espacio vectorial sobre XK XK K utilizando la siguiente definición de producto escalar: para k K∈ y Xf K∈ define tal que .

Xkf K∈( )( ) ( ) kf x kf x x X= ∀ ∈

Solución. es un grupo conmutativo y es el conjunto de vectores para el espacio vectorial. Es fñacil al leer, verificar que estas propiedades son satisfechas:

XK

( ) ( ), ( ) , ( ) , 1km f k mf k m f kf mf k f g kf kg f f= + = + + = + = para todas , , k m K∈, Xf g K∈ .

7.16 Sean diferentes de cero. Sean ,m n∈¥ {1,2,..., }I m= y {1,2,..., }J n= y forma el conjunto

. Sea I J× K un campo. es definida como el conjunto de todas las matrices de sobre el campo

I JK × m n×K . Utiliza el ejercicio 7.14 para probar que I JK × es un espacio vectorial sobre el campo K .

Como es un conjunto de funciones, cualquier miembro de I JK × I JK × puede ser expresado en la notación de familias (toda función es una familia y toda familia es una función). Sea ( , ) ( , )( )i j i j I Ja ∈ ×

cualquier miembro de . Entonces relaciona la notación usual para una matriz; simplemente comprendiendo conjunto de índices y borrando la coma y el par de paréntesis: ( ) . Como

ejercicio escribe todas las propiedades de

I JK ×

I Jija K ×∈

I JK × que definen un espacio vectorial en esta notación de familias.

Solución. Para ( ), ( ) I J

ij ija b K ×∈ por definición ( ) ( ) ( )ij ij ij ija b a b+ = + . es un grupo:

, ( )

I JK ×

( ) [( ) ( )] [( ) ( )] ( )ij ij ij ij ij ija b c a b c+ + = + + 0ija = si 0 ( , )ija i j I J= ∀ ∈ × ,

, . Y por definición, en la multiplicación escalar: para ( ) ( )ij ija a− = − ( ) ( ) ( ) ( )ij ij ij ija b b a+ = + k K∈ ,

. Más aún, ,( ) ( )ij ijk a ka= ( )( ) ( ) ( )ij ij ijk m a k a m a+ = + [( )( )] ( ) ( )ij ij ij ijk a b k a k b= + ,

, 1 ( . [ ( )] ( )( )ij ijk m a km a= ) ( )ij ija a=g 7.17 Sean y {1,2,..., }J n= K un campo. Un espacio vectorial J JK × tiene un producto definido como

sigue: , J Jf g K ×∀ ∈ define ( )( , ) ( , ) ( , ) ( , ) ; J Jh J

fg i j f i h g h j i j J J fg K ×∈

= ∀ ∈ × ∈∑ . O

bien, en la notación de familias, ( )( ) ( )ih hj ih hj

h Ja b a b

∈

= ∑ .

Prueba que J JK × , el conjunto de todas las matrices cuadradas de n n× sobre el campo K , es un álgebra sobre K. Prueba que el producto no es conmutativo y que existe una matriz ( ) J J

ij Kδ ×∈ tal que

( )( ) ( )( ) ( ) ( ) J Jih hj ih hj ij ija a a a Kδ δ ×= = ∀ ∈ .

Solución. J JK × es un caso especial de I JK × que nos da propiedades de espacio vectorial. Las propiedades necesarias restantes se prueban de la siguiente manera:

[( )( )] ( ) ( )ih hj ih hj ih hjh J h J

k a b k a b k a a∈ ∈

= =∑ ∑

[ ( )]( ) ( )( ) ( ) ( )ih hj ih hj ih hj ih hjh J h J

k a b ka b ka b k a b∈ ∈

= = =∑ ∑

( )[ ( )] ( )( ) ( ) (ih hj ih hj ih hj ih hjh J h J

a k b a kb a kb k a b∈ ∈

= = =∑ ∑ ) .

Basándonos en la asociatividad y conmutatividad del campo K , uno puede probar la asociatividad del producto:

( )[( )( )] ( )( ) ( )

( ) ( ) ...

ih hm mj ih hm mj ih hm mjh J h J m J

ih hm mj ih hm mjh J m J m J h J

a b c a b c a b c

a b c a b c∈ ∈ ∈

∈ ∈ ∈ ∈

= =

= = =

∑ ∑ ∑

∑∑ ∑∑

Para probar la no conmutatividad, considera este ejemplo: {1, 2}J = ,

11 21 22 12

11 12 22 21

0; 10; 1

a a a ab b b b

= = = == = = =

0ijδ = si y i j≠ 1ijδ = si i tiene la propiedad requerida. j= 7.18 Sean E un monoide cualquiera, { | : , , ( ) }a a aH h h E E a E h x ax x E= → ∈ = ∀ ∈ . Prueba que

H es submonoide de . Prueba que existe un isomorfismo (homomorfismo biyectivo) . Prueba además que si

EE: EΦ >→> H E es un grupo, entonces H también lo es (teorema de

representacion de Cayley). Solución. . Define ( )( ) ( ) ( ) ( )b a b a b bah h x h h x h ax bax h x= = = = : E HΦ >→> tal que

. . Sea ( ) aa hΦ = ( ) ( ) ( )ab a bab h h h a bΦ = = = Φ Φ ( ) ( )a bΦ = Φ . a bh h= . para

toda

( ) ( )a bh x h x=x E∈ . . . Finalmente, la imagen homomórfica de un grupo es en sí misma un grupo. ae be= a b=

7.19 Muestra que es un anillo. Define como una sucesión de Cauchy si y solo si para ¥¤ s∈ ¥¤

0ε∀ > existe tal que si , entonces n∈¥ ,i j n≥ ( ) ( )s j s i ε− < (ε ∈¤ y ). Sea

. Prueba que es un subanillo de . Sea

,i j∈ ¥

{ | y es de Cauchy}S s s s= ∈ ¥¤ S ¥¤{ | y para 0 existe un : ( ) }N s s S n s i i nε= ∈ > < ∀ ≥ε . Prueba que es un ideal de .

Entonces

N SS

N es un anillo. Prueba que existe un monomorfismo : SNΦ >→¤ . Este ejercicio da

a la construcción números reales en base a sucesiones de Cauchy de números racionales. Solución. es el conjunto de sucesiones de Cauchy con valores racionales. Para probar que es un subanillo de , sean . Para

S S¥¤ , r s S∈ 2 0ε < existe un entero positivo tal que si , entonces 1n 1, i j n≥

2| ( ) ( ) |r i r j ε− < ; existe un entero positivo tal que si , entonces 2n 2, i j n≥ 2| ( ) ( ) |s i s j ε− < . Entonces

| ( )( ) ( )( ) | | ( ) ( ) ( ) ( ) | | ( ) ( ) | | ( ) ( ) |r s i r s j r i s i r j s j r i r j s i s j ε− − − = − − − ≤ − + − < para

. Por lo tanto . Ahora demostraremos la cerradura multiplicativa.

Nuevamente, sean . Existe un entero positivo tal que si , entonces | ( .

Más aún, para uno tiene o

1 2, max{ , }i j n n≥ r s S− ∈, r s S∈ 1n 1, i j n≥ ) ( ) | 1r i r j− <

1i n≥ 1 1| ( ) | | ( ) | | ( ) ( ) | 1r i r n r i r n− ≤ − < 11| ( ) | 1 | ( ) |r i r n B< + = . De igual

manera existe un entero positivo tal que si , entonces 2n 2i n≥ 2| ( ) | 1 | ( ) |s i s n B2≤ + = . Más aún, existe

un entero positivo tal que si , entonces 3n 3, i j n≥22| ( ) ( ) | Br i r j ε− < , y existe un entero positivo tal

que si , entonces

4n

4, i j n≥12| ( ) ( ) | Bs i s j ε− < . Ahora, ensamblando todas estas desigualdades, tenemos:

1 21 22 2

| ( )( ) ( )( ) | | ( ) ( ) ( ) ( ) || ( ) ( ) ( ) ( ) | | ( ) ( ) ( ) ( ) || ( ) || ( ) ( ) | | ( ) || ( ) ( ) |

B B

rs i rs j r i s i r j s jr i s i r i s j r i s j r j s jr i s i s j s j r i r jB Bε ε ε

− ≤ −≤ − + −≤ − + −< + =g g

dado que . Por lo tanto 1 2 3 4, max{ , , , }i j n n n n≥ , r s S∈ y es un subanillo. S Para mostrar que es un ideal de , sean N S , r s N∈ . Para 2 0ε > existe un entero positivo tal que si

, entonces 1n

1i n≥ 2| ( ) |r i ε< , y existe un entero positivo tal que si , entonces 2n 2i n≥ 2| ( ) |s i ε< . Entonces

| ( )( ) | | ( ) ( ) | | ( ) ( ) |r s i r i s i r i s i ε− = − ≤ + < para . Por lo tanto . Ahora, sean

. Existe un entero positivo tal que se , entonces 1 2max{ , }i n≥ n r s N− ∈

, r S s N∈ ∈ 1n 2i n≥1

| ( ) | Bs i ε< . Entonces

11| ( ) | | ( ) || ( ) | Brs i r i s i B ε ε≤ < g = n para . Por lo tanto 1 2max{ , }i n≥ rs N∈ . es un ideal del anillo

de sucesiones de Cauchy con valores racionales.

NS

Para probar que el anillo cociente SN es un campo, sea Sr

N ∈ N con 0rN ≠ N y demuestra la

existencia de s SN ∈ N tal que 1sr

N N N=g donde 0 y 1 son las sucesiones constantes con cada

valor igual a los números racionales 0 y 1 respectivamente. Primero existe un entero positivo y un racional positivo tal que | ( para toda i . Supóngase que éste no fuera el caso. Sea

nC ) |r i C≥ n≥ 0ε >

dado. Entonces existe un entero positivo n tal que si entonces , i j n≥ 2| ( ) ( ) |r i r j ε− < . Sea 2| ( ) |r m ε<

con m . Entonces n≥ | ( ) | | ( ) ( ) | | ( ) |r i r i r mr m ε≤ − + < para i . Por lo tanto . Pero esto

contradice que

n≥ r N∈0r

N ≠ N . Ahora continuemos en busca del recíproco, defínase una sucesión como

sigue:

s1( )( ) r is i = si y si ( ) 0r i ≠ ( ) 1s i = ( ) 0r i = . Entonces existe un entero positivo tal que si

, entonces | ( , y existe un entero positivo tal que si , entonces 1n

1i n≥ ) | 0r i C≥ > 2n 2, i j n≥2| ( ) ( ) |r i r j Cε− < . Entonces

2

2| ( ) (

( ))|1 1

( ) ( ) | ( ) |) ( ) | | | r i r i Cr i r j r i r j C

s i s j ε| ( ε−− = = < = si .

. .

1 2, max{ , }i j n n≥

s S∈ 1( ) ( ) 1 r i s i i n= ∀ ≥ 1( ) ( ) 1 0 r i s i i n− = ∀ ≥ . 1rs N− ∈ . Dando así 1rsN = N . Entonces

SN es un campo.

Defínase : SNΦ >→¤ con {( , ) | }( ) n q n Nq N

∈Φ = . Es decir, la imagen del número racional

bajo el mapeo Φ es la calse de equivalencia que contiene a la sucesión constante con cada valor igual a q .

Para mostrar que es inyectiv, sea . Entonces

q

Φ ( ) ( )qΦ = Φ p {( , ) | } {( , ) | }n q n n p nN N

∈ ∈=¥ ¥

{( , ) | }n q n n p n N∈ ∈¥ ¥

.

. {({( , ) | }∈ − , ) | }n q p n N− ∈ ∈¥ . Dada

10,hayunenteropositivonε < tal que | |q p ε− < . Pero esto es sólo posible si , probando así que Φ es inyectiva. Es fácil mostrar que

0q p− =Φ es un homomorfismo.

7.20 Define el -ésimo grupo de permutaciones como wl conjunto de las biyecciones del conjunto

con la composición como operación. Sean

n nS n

ns S∈ y

0

( )i j n

D xj xi≤ < <

= −∏ .

( ) ( )0

( ) ( )s j s ii j n

s kD x x≤ < <

= −∏

por definición. Define el signo de la permutación como s ( )( ) s Ds Dε = . es impar si s

( ) 1sε = − y es par si ( ) 1sε = . Prueba que ε es un homomorfismo de al grupo multiplicativo { 1nS ,1}− .

El kernel del homomorfismo ε es llamado el subgrupo alternante de . Construye , , , ,

, , , . nA nS 0S 0A 1S 1A

2S 2A 3S 3A Solución. 1( ) ( ) ( )D Dε σ σ= ; 1( ) ( ) ( )D Dε τ τ= . Entonces

1 1 1 1( ) ( )( )( ) ( ) ( ( )) ( ) ( ( )) ( ) ( ) ( ) ( ) ( )D D D DD D D Dε τ σ τ σ τ σ τ ε σ ε σ τ ε σ ε τ= = = = =o o g . 0 es el conjunto vacío y tiene una biyección, que es el conjunto vacío 0 { } 1S = ∅ = . La definición no

considera este caso mientras el signo esté involucrado. Sin embargo, si ε no es un homomorfismo, ( )ε ∅

debe ser 1. Así entonces también. 1 {0 1U = 0}= tiene exactamente una biyección {(0 , que es par.

Entonces

, 0)}

1 1 {{(0,0)}}S U= =

2 {0,1}= . 2

2

{{(0,0), (1,1)},{(0,1), (1,0)}}{{(0,0), (1,1)}}

SU

==

3 {0,1, 2}= .

3

2

{{(0,0), (1,1), (2,2)},{(0,1), (1,0), (2,2)},{(0,0), (1,2), (2,1)},{(0,2), (1,0), (2,1)},{(0,2), (1,1), (2,0)},{(0,1), (1,2), (2,0)}}

{{(0,0), (1,1), (2,2)},{(0,2), (1,0), (2,1)},{(0,1), (1,2), (2,0)}}

S

U

=

=

CAPITULO 8 Los números naturales

8.0 Definición. El sucesor del conjunto x es el conjunto { }x x x+ = ∪ .

Definición. Un conjunto sucesor es un conjunto A tal que 0 A∈ y si x A∈ , entonces x A+ ∈

Axioma de infinidad. Existe un conjunto sucesor.

Definición de ω , el conjunto de números naturales. Sea A un conjunto sucesor. Entonces { | y es un conjunto sucesor}S S PA Sω = ∈I .

Cinco teoremas en ω (axiomas de Peano). I. 0 ω∈ II. Si n ω∈ , entonces n ω+ ∈ . III. Si S ω⊂ , y si , 0 S∈ n S∈ siempre que n S∈ , entonces S ω= . IV. 0 n n ω+ ≠ ∀ ∈ . V. Si ,m n ω∈ y m , entonces n+ ≠ + m n≠ .

Dos lemas en ω .

i. n ω∀ ∈ , nunca ocurre que x n∈ y . n x⊂ii. Si x n∈ , entonces x n n ω⊂ ∀ ∈ .

Teorema de recursión para ω . Si y a X∈ :f X X→ , entonces existe una :u Xω → tal que

y (0)u a= ( ) ( ( )) u n f u n n ω+ = ∀ ∈ Definiciones. Un conjunto finito E es un conjunto equivalente a algún miembro de ω . Un conjunto no finito es un conjunto infinito. El número de elementos en un conjunto finito es el único miembro de ω al cual el conjunto es equivalente. Un conjunto enumerable es equivalente a ω o un miembro de ω . 8.1 En la página 42 del libro NST se establece que todos los pares no ordenados no constituyen un

conjunto. Prueba esta proposición. Solución. Sea un conjunto con la propiedad de que si { ,P }x y es cualquier par no ordenado,

entonces { , }x y ∈P P. Entonces U es un conjunto tal que si es cualquier conjunto, entonces =U zz U∈ . Esto contradice el teorema de Russel: ningún conjunto contiene cualquier conjunto. 8.2 Prueba que ω es un conjunto transitivo: si x ω∈ , entonces x ω⊂ . Prueba la siguiente propiedad de ω : si E es un conjunto no vacío de ω entonces existe un tal que .

k E∈ , k m m E m k∈ ∀ ∈ ≠

Solución. ( x ω∈ implica que x ω⊂ ) es equivalente a y n∈ implica que y nω ω∈ ∀ ∈ . Sea { | y implica }S n n y n yω ω= ∈ ∈ ∈ . Así S ω= por una fácil inducción. 8.3 Prueba la siguiente propiedad de ω : si E es un conjunto no vacío de ω entonces existe un

tal que . k E∈ , k m m E m k∈ ∀ ∈ ≠ Solución. sabemos del siguiente resultado: si E es un subconjunto no vacío de algún número natural, entonces existe un elemento tal que k E∈ k m∈ siempre que m es un elemento de E diferente de k utiliza este resultado para probar 8.3. Sea E ω⊂ , E ≠∅ . n E∈ para algún n ω∈ .

E n+∩ es entonces un subconjunto no vacío de n+ . Sea k E n+∈ ∩ tal que k m m E n+∈ ∀ ∈ ∩ , . Ahora, si m y , entonces m k≠ n+∉ m E∈ n m+ = o n m+ ∈ . Entonces si , también

es verdad que k m . k E n+∈ ∩

∈ 8.4 Sea ,m n ω∈ . Prueba que si y solo si m n∈ m n+ +∈ . Solución. Utilizando el orden total de ω , muestra la imposibilidad de otras alternativas. 8.5 Prueba que n n n ω∉ ∀ ∈ , el conjunto de los números naturales. Solución. En el lema “no sucede que x n∈ y ” sustituye n por n x⊂ x , teniendo así “no sucede que y ”. Como , uno tiene que n n∈ n n⊂ n n⊂ n n∉ . 8.6 Si n ω∈ y 0n ≠ , entonces . 0 n∈ Solución. Sea { | y (0 o 0)}S n n n nω= ∈ ∈ = . Obviamente 0 S∈ . Ahora supón que

. o 0 . Si entonces que contiene a 0 . Si 0 entonces

también contiene a . Por lo tanto

n S∈ 0n = n∈ 0n = 0 {0}n+ = ∪ n∈{ }n n n+ = ∪ 0 S ω= . Así, si 0n ≠ entonces 0 n n ω∈ ∀ ∈ .

8.7 La unión finita de conjuntos es finita. Solución. Sean E un conjunto finito y el número natural equivalente a m E . Sea

{ | y es equivalente a algún conjunto tal que es finito}S n n n F E Fω= ∈ ∪ . , para ello si es equivalente a , entonces

0 S∈0 F F =∅ y que es equivalente a . Supóngase que . Sea un conjunto equivalente a

E∪∅ = E mn S∈ F n+ . Entonces existe una biyección :f F n+>→> . Sea

tal que a F∈ ( , )a n f∈ . es equivalente a por la biyección E a− n {( , )}f a n− . Entonces por la hipótesis de inducción ( { })E F a∪ − es finito y equivalente a algún número natural porque p

( { })E F a E F∪ − = ∪ . Si entonces a E∉ { , }:g a p E F p+∪ ∪ >→> y E F∪ es equivalente al número natural p+ .

Por lo tanto . n S+ ∈ S ω= . 8.8 Ningún conjunto con dos elementos puede ser un subconjunto de un conjunto con un único

elemento. Solución. Sea A equivalente a 2 y B equivalente a 1. Supóngase que A B⊂ . Como A es equivalente a 2 , existe una biyección . :1g B>→> B tiene un solo elemento . (0)g A B⊂ implica que (0) (0f g )= y (1) (0)f g= y por lo tanto (0) (1)f f= , contradiciendo que f es biyección. 8.9 Sea ( )i iA ω∈ una familia tal que i i

A A i ω+ ∀ ∈ . Prueba que 0 , 0nA A n nω∀ ∈ ≠ . Solución. Sea 0 0{ | y ( , o 0)}n nS n n A A A A nω= ∈ ⊂ ≠ = . Obviamente 0 .

Supóngase que . Si , entonces

S∈n S∈ 0n = 1n+ = y , 0 1A A⊂ 0A A1≠ dados. Si ,

, entonces 0 nA A⊂

0 nA A≠ 0 nA A +⊂ , 0 n

A A +≠ , como n nA A +⊂ , n n

A A +≠ . Entonces . n S+ ∈ 8.10 En la página 47 del libro NST se da una prueba del axioma V de Peano usando dos lemas (ambos

citados en 8.0). Da una prueba del axioma V de Peano usando únicamente el segundo lema: prueba que implica que . n m+ = + n m=

Solución. Sean , m n ω∈ y supongamos que m n+ += . . Por esta igualdad de conjuntos uno puede concluir

{ } { }m m n n∪ = ∪

( ) y ( o m n m n∈ = o n m n m∈ = ). Así uno de los siguientes enunciados es verdadero: 1. m y , 2. y n , 3. n∈ n m∈ m n∈ m= n m∈ y m n= , 4. m n= y n m= . Las alternativas 2 ,3, 4 nos dan que . Supóngase que tenemos 1. n m= m n∈ y n . Por el lema citado, m y , teniendo que

m∈n⊂ n m⊂ n m= . Entonces, en todos los casos n m= . Utilizando otro

lema, uno puede, de hecho, probar que la alternativa 1 no puede suceder, pero ello no afecta la validez de esta demostración. 8.11 Sea ( )i iA ω∈ una familia tal que i i

A A i ω+⊂ ∀ ∈ . Además, sea . Prueba que 0iiA A

ω∈⊂U

,i jA A i j ω≠ ∀ ∈ . Solución. Es suficiente probar 0 iA A i ω= ∀ ∈ . Por un argumento como el de 8.9,

0 iA A i ω⊂ ∀ ∈ . Pero 0i jj

A A Aω∈

⊂ ⊂U y por lo tanta 0 iA A= .

8.12 Sea ( )i iX ω∈ una sucesión de conjuntos. Define

liminf( )i i i ij ji j

i ji

X X Xωω ωω +

∈∈ ∈∈ −

>

= =U I UIω∈

limsup( )i i ij i

i j

X Xωω ω

∈∈ ∈

>

= I U .

Prueba que liminf( ) limsup( )i i i iX Xω ω∈ ∈⊂ . Solución. liminf( )ix X ω∈∈ implica que i

i k

x X>

∈U para algún k ω∈ . Existe un k ω∈ tal

que ix X i k∈ ∀ > . iii j

X Xω∈>

∈U para cualquier j ω∈ porque si no, ix X i j∉ ∀ > .

( )ij i

i j

x Xω ω∈ ∈

>

∈ I U .

8.13 Si liminf( ) limsup( )i i i iX Xω ω∈ ∈= , entonces por definición

lim( ) liminf( ) limsup( )i i i i i iX X Xω ω ω∈ ∈= = ∈ . Encuentra los límites para los siguientes ejemplos: , el conjunto de los números reales [0, ]iX i= ⊂ ¡ [0,1 ]iX i= ,

si es par, [0 si es impar. [0,1]iX = i , 1]− i Solución. [0, ), {0}; lim sup [ 1,1], lim inf {0}∞ = − = 8.14 Una sucesión es definida creciente (con respecto a ⊂ ) si i i

X X +⊂ y de creciente si

iiX X i ω+ ⊂ ∀ ∈ . Prueba que sucesiones crecientes y decrecientes siempre tienen límites y que

lim( )i i iiX Xω ω∈ ∈

=U para la sucesión creciente y lim( )i i iiX Xω ω∈ ∈

= I para la sucesión

creciente.

Solución. Sea ( )i iX ω∈ una sucesión creciente; 1 i iX X i ω+⊂ ∀ ∈ . Entonces i jii j

X Xω∈>

=I .

liminf( )

limsup( ) ( )

liminf( )

i i i jj j j

i i i ij i j i

i

i i

X X X

X X X

X

ωω ω ω

ωω ω

ω

ω

∈∈ ∈ ∈

∈∈ > ∈

∈

∈

= =

= ⊂

=

UI U

I I U

Una prueba similar funciona para la sucesión decreciente. 8.15 El teorema de recursión se establece en 8.0. En cada uno de los siguientes ejemplos establece

quienes son , , , f a u X .

a) ,adición de números naturales, msb) mp , multiplicación de números naturales,

c) , exponenciación de números naturales, me

d) ( )n

n

d gu ndx

= , diferenciación de funciones,

e) , composición de funciones. ( ) nu n g= Solución.

a) X ω= , :f ω ω→ tal que ( ) , f x x a m+= = y :u ω ω→ tal que

. ( ) ( )mu n m n s n= + =b) X ω= , :f ω ω→ tal que ( ) ( ), 0xf x x m s m a= + = = , y :u ω ω→ tal que

( ) ( )mu n mn p n= =c) X ω= , :f ω ω→ tal que ( ) ( ), 1xf x xm p m a= = = , y :u ω ω→ tal que

. ( ) nu n m=d) X un conjunto de funciones que contienen todas las derivadas para cada función,

:f X X→ tal que ( ) , f g g a g′= = , y :u Xω → tal que . ( )( ) nu n g=e) X un conjunto de funciones para las cuales la composición está definida y que contiene a la

función identidad ( ), :id X X→ :f X X→ tal que

( ) nu n g= ( ) , , :f x x g a id u Xω= = →o . 8.16 Para cualquier x ω∈ , xs es la función de ω a ω definida recursivamente como sigue:

utilizando las funciones (0) , ( ) [ ( )]x x xs x s n s n+= = +Xs ′ define una operación en ω como

sigue: {(( , ), ) | (( , ), ) ( ) y ( )}xs x y z x y z z s yω ω ω= ∈ × × = .

Prueba que s es un conjunto, una función, y una operación en ω . Prueba que ω con la operación es un monoide conmutativo. Prueba además que s ω es un semigrupo. Solución. ω es un conjunto. El producto cartesiano de un conjunto es un conjunto, entonces ( )ω ω ω× × es un conjunto. Por el axioma de especificación, es un conjunto. s :s ω ω× →ω es

una función, pues es único. Una función de ( )xs y ω ω× a ω es una operación en ω . Para probar que s es una operación asociativa (adoptando la notación usual para una operación), debemos probar que ( ) ( ) , , x y z x y z x y z ω+ + = + + ∀ ∈ . Sea

{ | y ( ) ( ) para todas , }S n n x y n x y n x yω ω= ∈ + + = + + ∈ . Por definición

0 , ( )y y x y x y++ = + = + + 0. Entonces ( 0) ( )x y x y+ + = + + que implica que .

Supongamos que . Entonces 0 (0 S∈

n S∈ 0 )n n n+ + ++ = + = n S+. ∈ . es entonces el elemento nulo

para “+ ”. Además, se ha probado que 00

0 x x x ω+ = + ∀ ∈ . ( 0) 0n n n n+ + + 1= + = + = + . Sea

. 1 0{ | y 1 }S n n n nω += ∈ + = 1 0++ = = nos deja que 0 S∈ .

. Por lo tanto 1 (1 ) ( )n n n n+ + + + ++ = + = = +1 n S∈ implica que n+ S∈ . Y así

1 y y y ω++ = ∀ ∈ con estos preliminares, la conmutatividad de “+ ” puede ser probada. Sea { | y }S n n n y y nω= ∈ + = + . . Supongamos que n0 S∈ S∈ . Entonces

. Por lo

tanto n S .

( ) ( 1) (1 ) ( ) 1 ( ) 1 ( 1)n y n y n y n y y n y n y+ ++ = + + = + + = + + = + + = + + = + n+ ∈ S ω= .

Para probar la cancelación, sea { | y implica }S n n x n y n x yω= ∈ + = + = . 0 porque

implica que

S∈0x y+ = + 0 x y= . Supongamos que n S∈ . x n y n+ ++ = + implica que

( ) ( )x n y n++ = + + , lo cual implica que x n y n+ = + , con lo cual tenemos x y= . . n S+ ∈S ω= 8.17 , xx pω∀ ∈ es la función de ω a ω definida recursivamente como sigue:

( )(0) 0, ( ) ( ( ), )x xx n xp p p n x s p n+= = + = x

Utilizando las funciones xp define una operación en ω como sigue: ,

. Utilizando las funciones

(0) 0xp =

( ) ( ) ( ( ), )x x xp n p n x s p n x+ = + = xp define una operación en ω

como sigue: {(( , ), ) | (( , ), ) ( , ) y ( )}xp x y z x y z z p yω ω ω= ∈ × = . Prueba que ω con la opaeración p es un monide conmutativo. También orueba estos teoremas: para todas

, , x y z ω∈ a) ( )x y z xy xz+ = + ,

b) 1x x++ = , c) implica y 0x y+ = 0x = 0y = , d) implica o 0xy = 0x = 0y = , e) 1x y+ = implica 1x = o 1y = f) 1xy = implica 1x = y . 1y =

Solución. Similar a 8.16. 8.18 Construcción de los enteros. Sea el conjunto de los números naturales con las operaciones

adicion y multiplicación. Prueba que ¥

R definida como sigue es una relación de equivalencia en

: ×¥ ¥ (( , ), ( , ))x y u v R∈ si y solo si x v y u+ = + . Sobre la partición ( )R

×¥ ¥ define

dos operaciones: ( , ) ( , ) ( , )x y u v x u y v

R R R+ ++ =

( , ) ( , ) ( , )·x y u v xu yv xv yuR R R

+ += .

Prueba que estas operaciones estan bien definidas (independientes de los representantes elegidos), y muestra además que son conmutativas y asociativas y que “ ” distribuye con respecto a “ ”.

·+

Define : R×Φ >→ ¥ ¥¥ tal que ( ,0)( ) xx RΦ = . Muestra que Φ es monomorfismo para ambas

operaciones. Este monomorfismo identifica ciertos enteros con los números naturales. La notaciónes para el número natural

Φx y el entero ( )xΦ se usan indistintamente.

Por simplicidad, definimos R×= ¥ ¥¢ con las dos opeaciones “+ ” y ” · ” como los números enteros.

Muestra que cualquier miembro de ¢ tiene un inverso: N N N NR Rα β× ×∀ ∈ ∃ ∈ tal que

(0)α β+ = Φ . Prueba que ¢ es un anillo conmutativo con unidad. Prueba además que la cancelación multiplicativa no nula es posible: αβ αγ= y 0α ≠ implica que β γ= , 8.19 Construcción de los números racionales. Sean ¢ el conjunto de enteros, . Prueba

que , definida como sigue, es una relación de equivalencia en

* {0}= −¢ ¢S *×¢ ¢ : (( , ), ( , ))x y u v S∈ si

y solo si xv yu= . En *

S×¢ ¢ , define

( , ) ( , ) ( , )x y u v xv yu yvS S S

++ =

( , ) ( , ) ( , )·x y u v xu yvS S = S .

Prueba que estas operaciones estan bien definidas, que son ambas conmutativas y asociativas, y que “ · ”

es distributiva con respecto a “+ ”. Define *

: S×Ω >→ ¢ ¢¢ tal que ( ,1)( ) xx SΩ = .

Prueba que Ω es monomorfismo. Entonces los enteros son isomorfos a un subconjunto de *

S×¢ ¢ .

Define *

S×= ¢ ¢¤ como el conjunto de números racionales. Prueba que es un anillo conmutativo

con unidad. Prueba que si

¤

0α ≠ ∈¤ , entonces existe β ∈¤ tal que (1)αβ = Ω (o bien 1 es usando indistintamente la notación de los elementos de ¢ en ). Entonces es un campo. ¤ ¤8.20 X es Dedekind infinito si y solo si existe una inyección :f X >→ X tal que ( )f X X .

X es infinito si y solo si X no es equivalente a ningún miembro de ω . Prueba que X es infinito si y solo si X Dedekind infinito.

Solución. Supóngase que X no es infinito. Entonces existe una n ω∈ y una biyección

:f X n>→> y que X es Dedekind infinito. Entonces existe un subconjunto propio A de X y una biyección . La restricción de :g X A>→> f al dominio A mapea a A en un subconjunto propio de

. n ( | )f A a=>→> . 1( | )f A g f −o o es entonces una biyección de n en , un subconjunto propio de n . Lo cual es imposible. Entonces

aX no es Dedekind infinito.

Supongamos ahora que X es infinito. Entonces existe una :u Xω >→ . Sea que representa a la función sucesor.

s: {s 0}ω ω>→> − tal que ( ) 1s n n= + . Sea

1( ) {( , ) | y ( )}v u s u x x x X x u ω−= ∪ ∈ ∉o o . v es una biyección de X a un subconjunto propio de X . 8.21 Prueba que X es enumerable si y solo si X es equivalente a algún subconjunto de ω . Prueba

que un subconjunto de un conjunto enumerable es enumerable.

Solución. Sea X enumerable. Existe una :f X ω>→ . Sea A X⊂ . Entonces ( | ) :f A A ω>→ puesto que ( )f x ω∈ implica que ( | )( )f A x ω∈ y f una inyección implica que ( | )f A es una inyección.

Y con X enumerable. Prueba que Y es enumerable. 8.22 Sea :f X →> Solución. Dada :f X Y→> y X enumerable. Existe :g X ω>→ . Por el teorema

fundamental de mapeos existe XXf YS >→> . Sea χ una función de elección para X .

: ( ) {0 }p X Xχ − → tal que ( )A Aχ ∈ para todo A X⊂ , A ≠∅ . : X XSχ >→ porque

( ) (yxSχ χ= )S implica que ( ) yx

S Sχ ∈ y ( )y xSχ ∈ S , lo cual implica que yx

S S= .

Entonces 1 :g f Yχ ω− >→o o y Y es enumerable. 8.23 Prueba que ω es equivalente a ω ω× . Prueba que la unión enumerable de conjuntos

enumerables es enumerable. Solución. Defina :f ω ω× >→>ω tal que 1

2( , ) ( )( 1) 1f x y x y x y y= + + + + + . Esta función es inyectiva. Una prueba de ello es la siguiente: Caso 1. x y u v+ ≠ + . Supóngase que x y u v+ > + . Entonces 1x y u v+ ≥ + + .

( )( 1) ( 1)( 22 2

( )( 1)2

( )( 1)2

( 1

1.

x y x y u v u v

u v u v

u v u v

u v

v

+ + + + + + +

+ + +

+ + +

≥

= + +

≥ + +

)

)+

Un argumento similar prevalece para x y u v+ < + .

Caso 2. x y u v+ = + y . Tomemos . y v≠ y v>( )( 1) ( )( 1)

2 21 1x y x y u v u v+ + + + + ++ = + . ( )( 1)

2( )( 1) 1 u v u v 1x y x y y v+ + ++ + + + + > + + .

De manera similar para y v< . Entonces f es una inyección. Sea n ω∈ . Como ( 1)

2z z+ es una función creciente, entonces existe z ω∈ .

( 1) ( 1)( 2)2 2

z z z zn+ +≤ < + . Sea ( 1)21 z zy n += − − , x z y= − . Entonces ( , )f x y n= . f es

suprayectiva. :f ω ω× >→>ω . Como I está dado como un conjunto enumerable, entonces

i ii I i J

A A∈ ∈

=U Udonde J ω⊂ . está dado como enumerable para cada iA i J∈ . Sea : i if A i Jω>→ ∀ ∈ .

Sea : { } ig i iω ω>→> × ∀ ∈ω . Entonces : { } i i ig f A i i Jω>→ × ∀ ∈o .

8.24 Ningún número natural es miembro de si mismo. Para extender esta regularidad a los conjuntos en general, el siguiente axioma es adjuntado usualmente a los tomados previamente: Si , entonces existe un conjunto

X ≠∅x tal que x X∈ y x X∩ =∅ . Prueba que el axioma de

regularidad implica que x x∉ para todos los conjuntos x . 8.25 Prueba (usando el axioma de regularidad) que x y∉ o y x∉ para cualesquiera , x y .

8.26 Prueba (usando el axioma de regularidad) que dada la familia para alguna 1( ) , i i i ia aω∈ + ∉ai ω∈ .

8.27 Da un ejemplo de una familia ( )i ia ω∈ tal que 1 i ia a i ω+∈ ∀ ∈ .

Asumiendo el axioma de regularidad, prueba que si X X X⊂ × , entonces X =∅ .

CAPITULO 9 Orden

9.0 Que sea un conjunto ordenado significa que ( , )X ≤ X es un conjunto y ≤ es un orden en X . Si

la existencia del orden se da por entendida, entonces simplemente se dice que X es un conjunto ordenado. Definición. X es un conjunto totalmente ordenado si y solo si , x y X∈ implica que x y≤ o y x≤ Definiciones. Sean X un conjunto ordenado, a X∈ . es elemento minimal de a X si y solo si no existe

x X∈ tal que x a< ,

a es elemento maximal de X si y solo si no existe x X∈ tal que a x< . es elemento mínimo de a X o el mínimo elemento de X si y solo si . a x x X≤ ∀ ∈ es elemento máximo de a X o el máximo elemento de X si y solo si x a x X≤ ∀ ∈ . Definiciones. Sean X un conjunto ordenado, un subconjunto de S X y a X∈ . es cota superior de si y solo si a S x a x S≤ ∀ ∈ . es cota inferior de S si y solo si a a x x S≤ ∀ ∈ . o es el máximo del conjunto de las cotas superiores de . inf S glb S S o lu es el mínimo del conjunto de las cotas inferiores de . sup S b S S Definición. Sea X un conjunto ordenado. X es un conjunto bien ordenado si y solo si cada subconjunto no vacío de X tiene un elemento mínimo.

9.1 El siguiente es un diagrama para el conjunto ordenado ( , )X S , donde { , , , }X a b c d= y el

orden {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )}

{( , ), ( , ), ( , ), ( , )} X

S a a a b a c a d b b b c c c d da b a c a d b c I

== ∪

a

b d

c

b

b \

Cuales son los conjuntos y los órdenes para los siguientes dos diagramas?

c

d e f

b

a

_ \ _ \

_ \

g

f

b c d

a

\ _

_ b b \e

9.2 Dibuja diagramas para los siguientes conjuntos ( , )X S

a) { , , , , }, {( , ), ( , ), ( , ), ( , ), ( , ),

( , ), ( , )} X

X a b c d e S a d a c a b a e b ec e d e I

= =∪

b)

{ , , , , , , }, {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), (

X a b c d e f g S a g b g c g g e g fa e a f b e b f c ec

= =

, )} Xf I∪

c) { , , , }, {( , )} XX a b c d S c d I= = ∪

⊂ d) { , , }, ( )X P a b c S= =

Para cada ejemplo examina cuales elementos son maximales, minimales, máximo y mínimo. 9.3 Sea { , , , , }, {( , ), ( , ), ( , )}X a b c d e S a c b c d e= = . Prueba que es un orden estricto en S

X , no es total y tiene tres elementos minimales y dos maximales. Observa que el orden estricto es total si y solo si ,x y X∈ y x y≠ implica que xSy o . ySx

9.4 Prueba que si un conjunto ordenado X tiene dos elementos minimales distintos, entonces no tiene elemento mínimo.

9.5 Sean X un conjunto ordenado, A un subconjunto finito totalmente ordenado de X y sea . Prueba que . Da un ejemplo donde supa = A Amaxa = A no es totalmente ordenado y la

conclusión anterior es falsa. 9.6 Sea Q el conjunto de todos los órdenes en un conjunto X dado. es por si mismo un

conjunto ordenado. Prueba que T es un elemento maximal de ( , si y solo si T es total. Dibuja un diagrama para ( , en el caso donde

( , )Q ⊂)Q ⊂

)Q ⊂ 3X = . 9.7 Sea una relación antisimétrica en S X . Como ejemplo prueba que es posible que no exista orden

tal que . En otras palabras, no toda relación antisimétrica puede ser extendida a un orden. T S T⊂

9.8 Sea X un conjunto ordenado tal que todo subconjunto no vacío A de X con una cota superior en X tiene una cota inferior en X . Prueba que todo subconjunto no vacío B X⊂ con una cota inferior en X tiene una máxima cota inferior en X .

9.9 Sean X y Y conjuntos ordenados, :f X →> Y suprayectiva. Suponiendo que x y≤ si y solo si ( ) ( ) ,f x f y x y X≤ ∀ ∈ , prueba que f es inyección.

9.10 Sea X un conjunto ordenado. Para a X∈ , sea ( ) { | y }s a x x X x a= ∈ < ,

( ) { | y }s a x x X x a= ∈ ≤ . Prueba que ( ) ; ( )a X a X

s a X s a X∈ ∈

⊂ =U U ;

Si , entonces X ≠∅ ( ) ; ( ) mina X a X

s a s a X∈ ∈

= ∅ =I I ; si min X existe, de lo contrario

( )a X

s a∈

= ∅I .

9.11 Sea donde ( ) { ( ) | }S X s a a X= ∈ X es un conjunto ordenado dado. En define un

orden: si y solo si ( )S X

( ) ( )s a s b≤ a b≤ . Prueba que es un conjunto ordenado y es totalmente ordenado si y solo si

( )S XX es totalmente ordenado.

9.12 Sea una familia no vacía de relaciones de equivalencia en ( )i i IS ∈ X totalmente ordenada por la

inclusión. Prueba que es una relación de equivalencia en ii IS

∈U X .

Sea ( ) una familia no vacía de órdenes en i i IS ∈ X totalmente ordenada por inclusión. Prueba que

es un orden en ii IS

∈U X .

CAPITULO 10 Axioma de elección y lema de Zorn

10.0 Axioma de elección. Sea tal que ( )i i IX ∈ I ≠∅ y iX i I≠ ∅ ∀ ∈ . Entonces i

i I

X∈

≠ ∅∏Definición. f es una función de elección para X si y solo si : { }f PX X− ∅ → tal que ( )f A A∈ . Axioma de elección (formulación alterna). Para todo conjunto X existe una función de elección. Definición. Una cadena en X es un subconjunto totalmente ordenado de X . Lema de Zorn. Si X es un conjunto ordenado no vacío tal que toda cadena en X tiene una cota superior en X , entonces X contiene un elemento maximal.

Definición. Una familia de vectores ( )i i Ix ∈ en un espacio vectorial V sobre un campo K genera V si y solo

si x V∀ ∈ hay un subconjunto finito de J I tal que , i i ii Jx k x k K

∈= ∈∑ .

Definición. Una familia de vectores ( )i i Ix ∈ en un espacio vectorial V sobre un campo K es linealmente

independiente si cuando , es finito y J I⊂ J 0, i i ii Jx k x k K

∈= = ∈∑ , entonces . 0 ik i= ∀ ∈ J

Definición. Una familia de vectores ( )i i Ix ∈ en un espacio vectorial V sobre un campo K es una base si y

solo si es linealmente independiente y genera a V . ( )i i Ix ∈

10.1 Sean , 0n nω∈ ≠ y una familia de conjuntos no vacíos. Prueba que sin usar el

axioma de elección.

( )i i nX ∈ 0ii n

X∈

≠∏

10.2 Sea X una colección de conjuntos y sea { | para algún }Y B B A A X= ⊂ ∈ . Prueba que Y es un conjunto y además que M es un elemento maximal de Y si y solo si M es un elemento maximal de X .

10.3 Prueba que la siguiente proposición implica el lema de Zorn y es a su vez implicado por el. Sea un conjunto de conjuntos ordenados por inclusión. Para toda cadena no vacía en X ≠∅ C X sea

. Entonces C X∈U X tiene un elemento maximal.

10.4 Sea R un anillo conmutativo con unidad. Prueba que todo ideal propio de R es incluido en un ideal maximal propio de R .

10.5 Si V es un espacio vectorial sobre el campo K , entonces tiene una base. 10.6 Si T es un orden en el conjunto X , entonces existe un orden T en X tal que T T⊂ y T es total. 10.7 Prueba que existe una :f R → R ) tal que ( ) ( ) (f x y f x f y+ = + . Prueba que no toda f con

esta propiedad es de la forma ( )f x kx= para alguna k R∈ . 10.8 Prueba que la siguiente proposición, llamada el lema de Kuratowki, es equivalente al lema de Zorn.

Cada cadena en un conjunto ordenado ( , )X ≤ esta incluida en una cadena maximal. 10.9 Prueba que la siguiente proposición, llamada el postulado de Zermelo, es equivalente al axioma de

elección. Dada X , un conjunto de conjuntos ajenos no vacíos, entonces existe un conjunto tal que es un conjunto que consta de un solo elemento para cada Y X

FY F∩ ∈ .

CAPITULO 11 Buen orden

11.0 Definición. Un conjunto ordenado es un conjunto bien ordenado si y solo si todo subconjunto no vacío

de X contiene un elemento mínimo. Definición. En un conjunto ordenado el segmento inicial abierto determinado por a X∈ es el conjunto

. ( ) { | y }s a x x X x a= ∈ < Teoremas. (Principio de inducción transfinita para conjuntos bien ordenados). Si X es un conjunto bien ordenado y S tal que implica que X⊂ ( )s a S⊂ a S∈ , entonces S X= (Teorema del buen orden).. si X es un conjunto, entonces existe un orden R en X tal que ( , )X R es un conjunto bien ordenado. 11.2 Sean ( , )X T un conjunto bien ordenado, A X⊂ . Entonces prueba que es el elemento mínimo de a

A si y solo si im . ( ({ } ))T a A∩ × = A11.3 Sea ( , )X T un conjunto bien ordenado. Prueba que

{( , ) | ( , ) ( 1) y im( ( )) }f A a A a PX X T a A A= ∈ − × ∩ × = es un conjunto. Cual es la relevancia de f ?

11.4 Prueba que todo subconjunto de un conjunto bien ordenado es bien ordenado. 11.5 Sea B un conjunto y {( , ) | y es un orden en }X A R A B R A= ⊂ . Prueba que las relaciones

definidas a continuación son todas ordenes en X : 1( , ) ( , )A R B S< si y solo si A B⊂ y , R S⊂ 2( , ) ( , )A R B< S si y solo si A B⊂ y ( )R S A A= ∩ × ,

si y solo si [3( , ) ( , )A R B S< A B= o { | y ( , ) }BA x x B x b S I= ∈ ∈ − para alguna

] y b B∈ ( )R S A A= ∩ × . Que ordenes son mas fuertes? es mas fuerte que i< j< si y solo si ( , ) ( , )iA R B S< implica que

( , ) ( , )jA R B< S para todos ( , ), ( , )A R B S X∈ . Esto es ( ) ( )i j< ⊂ < . 11.6 Sea A un segmento inicial de un conjunto bien ordenado ( , )X ≤ . Prueba que un segmento inicial de

A (un conjunto ordenado por la restricción del orden en X ) es un segmento inicial de X . Prueba que un segmento inicial de X es un segmento inicial de A o incluye a A .

11.7 El teorema del buen orden. Sea X un conjunto. Prueba que es un conjunto no vacío. Define {( , ) | y ordena bien a }W A R A X R A= ⊂ ( , ) ( , )A R B S<

si y solo si [ { | y ( , ) }BA x x B x b S I= ∈ ∈ − para alguna b B∈ ] y ( )R S A A= ∩ × o, en términos menos formales, A y B son el mismo conjunto bien ordenado, o A es un segmento inicial de B . Prueba que < (llamada continuación) es un orden en W . Sea C una cadena en W . Muestra que y que ( p( preim , im ,)C C ∈U U W ,) Wreim , imC C ∈U U es una cota superior para .

Usa el lema de Zorn para mostrar que W tiene un elemento maximal

C( , )E T . Prueba que E X= y

concluye que T es un buen orden de X . 11.8 Prueba que existe un conjunto ordenado ( , )X S tal que si T ordena X y entonces ( ,S T⊂ )X T

no es bien ordenado.

11.9 Un subconjunto A de un conjunto ordenado X es cofinal en X en caso de que por cada elemento x X∈ existe un elemento tal que a A∈ x a≤ . Prueba que todo conjunto totalmente ordenado tiene un subconjunto cofinal bien ordenado.

La siguiente forma del principio de inducción transfinita es usualmente encontrada en la literatura. Si X es un conjunto bien ordenado y tal que implica que aS X⊂ ( )s a S⊂ S∈ y , entonces

. Muestra que la condición mimin X S∈

S X= n X S∈ es irrelevante.

CAPITULO 12 Recursión transfinita y similitud

12.0 Teorema de recursión transfinita. Sean W un conjunto bien ordenado, :f XΩ→ donde

{ | : ( ) para alguna }s a X a Wφ φΩ = → ∈ . Entonces existe U tal que :U W X→

( )( ) ( | )s aU a f U= . Definición. Sean ( , ), ( , )X R Y S conjuntos ordenados :f X →> Y es similitud siginifica 1 2( , )x x R∈

si y solo si 1 2( ( ), ( ))f x f x S∈ . f es una función que preserva orden significa que 1 2( , )x x ∈R implica

que 1 2( ( ), ( ))f x f x S∈ Teorema. Si f es similitud en X con un subconjunto de el mismo y X es bien ordenado, entonces

. ( ) x Xx f x≤ ∀ ∈ Teorema. Existe a lo más una similitud de un conjunto bien ordenado X a un conjunto bien ordenado Y . Teorema. Un conjunto bien ordenado nunca es similar a uno de sus segmentos iniciales. Teorema. Se X y Y son conjuntos bien ordenados, entonces uno de los siguientes es verdadero:

a) X es similar a Y , b) X es similar a un segmento inicial de Y , c) es similar a un segmento inicial de Y X .

Definición. Un conjunto ordenado no vacío ( , )L ≤ es una retícula si y solo si todo par de elementos de L tiene una mínima cota superior y una máxima cota inferior en L . Una retícula ( , )L ≤ es completa si y solo si todo subconjunto de L tiene una mínima cota superior y una máxima cota inferior en L . 12.1 ω es un conjunto bien ordenado. Sea dados.

Usando recursión transfinita prueba que existe una función 0 1 11; , , ..., ; : N

NN a a a Fω −∈ − ∈ →¡ ¡ ¡:u ω → ¡ tal que

0 1(0) , u(1) , ..., ( 1) Nu a a u N a 1−= = − = y

para . ( ) ( ( ), ( 1),..., ( 2), ( 1))u n F u n N u n N u n u n= − − + − − n N≥12.2 Como ejemplo del teorema establecido en el ejercicio anterior, considera este ejercicio en definición

recursiva. En busca de una solución de series de una ecuación diferencial como con ( ) ( ) 0y A x y B x y′′ ′+ + = (0) 0, (0) 1y y′= = uno sustituye i

iiy a x

ω∈=∑ en la ecuación

diferencial y compara coeficientes. Determina el valor de ( )i ia ω∈ por una formula recursiva, la cual

será del teorema anterior (F 2N )= . Concluye que la sucesión ( )i ia ω∈ es definida y por lo tanto la

serie de potencias también. iii

a xω∈∑

12.3 Muestra que :f {0}ω ω→ − tal que ( )f n n+= es una similitud. 12.4 Sea :f X >→> Y una similitud del conjunto ordenado ( , )X ≤ al conjunto ordenado .

Prueba que si esta bien ordenado, entonces ( , )Y ≤

( , )X ≤ ( , )Y ≤ es bien ordenado. 12.5 Sean , a conjuntos ordenados. Entonces una biyección ( , )X ≤ ( , )Y ≤ :f X >→> Y

2

es una

similitud si y solo si 1x x< cuando y solo cuando 1 2 1 2( ) ( ) ,f x f x x x X< ∀ ∈ .

12.6 Sean X t Y conjuntos ordenados. Prueba que si la biyección :f X >→> Y preserva orden y X es totalmente ordenado, entonces f es una similitud.

12.7 Prueba que el conjunto de todas las similitudes de un conjunto ordenado X forma un subgrupo del grupo simétrico en X .

12.8 Sean X y Y conjuntos ordenados y :f X >→> Yup( ( ))

una similitud. Entonces pruena que (sup ) s f A para toda A X⊂ para el cual sup A existe. f A =

12.9 Sea :f ω ω→ tal que satisface la condición 2(2 )nf n= . Para que valores de n ω∈ puede f posiblemente ser similitud de ω en un subconjunto de ω ?

12.10 Cuales son las similitudes de ω ? 12.11 Prueba que las únicas similitudes de ¢ son las translaciones, i. e., de la forma

. ( ) , f x x n n= + ∈¢12.12 Muestra que el subgrupo de similitudes de ¢ es equivalente a ¢ bajo la biyección natural

definida en el ejercicio 7.20. ordena el subgrupo de similitudes de tal manera que sea similitud. Φ

Φ12.13 Prueba que f definida por ( )f x ax b= + es similitud de ¡ si . Prueba que estas no son las

únicas similitudes de 0a >

¡ . 12.14 Si E es el conjunto de todas las relaciones de equivalencia en X , es el conjunto de todas las

particiones de F

X , y es la biyección natural, prueba que : EΦ >→> F Φ es una similitud para los conjuntos ordenados y . ( , )E ⊂ ( ,"mas fino que")F

12.15 Prueba que E , el conjunto de todas las relaciones de equivalencia en un conjunto no vacío X es una retícula completa. Prueba que la imagen de una retícula completa bajo una similitud también es retícula completa. Concluye que , el conjunto de todas las particiones de F X , es una retícula completa.

12.16 :f X >→> Y es una antisimilitud de conjuntos ordenados ( , ), ( , )X R Y S significa que 1 2x x≤

si y solo si 2 1 1 2( ) ( ), ,f x f x x x≤ ∀ ∈ X . Sea :f X >→> Y una antisimilitud de los conjuntos

ordenados ( , ), ( , )X R Y S . Entonces prueba que f es una similitud para los conjuntos ordenados 1( , ), ( , )X R Y S − .

12.17 Sean :f X >→> Y una antisimilitud de los conjuntos ordenados ( , ), ( , )X S Y S tal que ( , )X R

esta bien ordenado. Entonces prueba que 1( , )Y S − esta bien ordenado. 12.18 :f X >→> Y es una similitud de los conjuntos ordenados si y solo si ( , ), (Y,S)X R

:f X >→> Y es una similitud para los conjuntos ordenados . 1( , ), ( , 1)X R Y S− −12.19 Sea :f X >→> Y una similitud para los conjuntos ordenados ( , ), ( , )X R Y S . Si al menos uno de

los conjuntos 1( , ), ( , ), ( , ), ( , )1X R X R Y S Y S− − es bien ordenado, entonces f es la única similitud de X a Y .

12.20 Define ( , )X S como doblemente bien ordenado si y solo si todo subconjunto no vacío de X tiene tanto elemento mínimo como elemento máximo. Prueba que ( , )X S es doblemente bien ordenado si

y solo si ( , )X S y 1( , )X S − son bien ordenados. Prueba que ningún subconjunto infinito de ω puede ser doblemente bien ordenado, y por lo tanto, prueba que ningún conjunto infinito puede ser doblemente bien ordenado.

12.21 ¿Existen antisimilitudes de ω ? ¿de ¢ ? Del intervalo real (0, )∞ ? 12.22 Da un contraejemplo para esta proposición (una analogía al teorema de equivalencia dado en el libro

NST). Si X y Y son conjuntos ordenados y X es similar a un subconjunto de Y , y es similar a un subconjunto de

YX , entonces X es similar a Y .

CAPITULO 13 Ordinales

13.1 El axioma de sustitución. Si es una oración tal que para cada en un conjunto ( , )S a b a A , el

conjunto { | puede ser formado, entonces existe una función con dominio ( , )}b S a b F A tal que para cada ( ) { | ( , )}F a b S a b= a A∈ .

Definición. α es un número ordinal si y solo si α es un conjunto bien ordenado tal que

( ) s ξ ξ ξ α= ∀ ∈ . Teorema. Si α es un ordinal, entonces α+ es un ordinal Teorema. Si α es ordinal y β α∈ , entonces β es un ordinal. Teorema. Se α y β son ordinales similares, entonces α β= . Teorema. Cualquier conjunto de ordinales es totalmente ordenado, y para cualesquiera dos ordinales distintos α y β son equivalentes los siguientes: α β∈ , α β⊂ , β es una continuación de α . Teorema. Cualquier conjunto de ordinales es bien ordenado. Definición. Un ordinal infinito que es sucesor de un no ordinal es llamado un ordinal límite. Teorema. Para cualquier conjunto de ordinales existe un ordinal que es supremo para el conjunto. Teorema de conteo. Todo conjunto bienordenado es simila a un único ordinal. Definición. La suma ordinal de los conjuntos ajenos bien ordenados ( , )A R y ( , )B S es el conjunto bien ordenado ( , ( ) )A B R A B S∪ ∪ × ∪ . Definición. El producto ordinal de los conjuntos bien ordenados ( , )A R y ( , )B S es el conjunto bien

ordenado ( , )A B T× donde 1, 1 2 2(( ), ( , ))a b a b T∈ si y solo si ( 1 2 1 2 y ( , )b b a a= ∈ ¡ ) o

. Ver ejercicio 3.31. 1 2( , ) Bb b S I∈ − Definición. La suma α β+ de los ordinales α y β es el único ordinal similar a la ruma ordinal de los conjuntos bien ordenados {0}α × y {1}β × . Definición. El producto αβ de los ordinales α y β es el ñunico ordinal similar al producto ordinal de los conjuntos bien ordenados α y β . 13.2 ω es el mínimo conjunto sucesor un el caso en que A es cualquier conjunto sucesor, entonces

Aω ⊂ . ¿Existe un conjunto sucesor mas grande que cualquier conjunto sucesor en un conjunto no vacío dado de conjuntos sucesores? ¿Existe maximal o conjunto sucesor máximo?

13.3 Supóngase el axioma de sustitución y que ∅ es un conjunto. Prueba el axioma de especificación. 13.4 Prueba que el axioma de sustitución junto con el axioma de potencia y la existencia de

implican el axioma de apareamiento. ∅

13.5 α es un ordinal si y solo si α es un conjunto bien ordenado por ∈ y ( x α∈ implica x α⊂ ). 13.6 Si α es un conjunto totalmente ordenado por ∈ y si x α∈ implica x α⊂ y el axioma de

regularidad es asumido, entonces α es un ordinal. Ver ejercicio 8.21 para el establecimiento del axioma de regularidad.

13.7 Si α es un ordinal, no existe ordinal β tal que α β α+< < .

13.8 Si α es un ordinal, entoncesα α∉ 13.9 Si α es un ordinal, entonces no existe conjunto x tal que x α∈ y xα ⊂ . 13.10 ω es un ordinal. 13.11 Todo número natural es un ordinal. 13.12 Todo ordinal es un segmento inicial para algún otro ordinal. 13.13 Si A es un subconjunto no vacío de ordinales, entonces min A A= I .

13.14 Sea α un ordinal distinto de cero. Entonces α es un ordinal límite si y solo si α α=U .

13.15 α α+ =U .

13.16 Si α y β son ordinales y β α< , entonces β α≤U . 13.17 Si α es un número ordinal y α es un conjunto finito entonces α es un número natural. 13.18 Si X es un conjunto finito totalmente ordenado, entonces X es similar a algún número natural. 13.19 Prueba usando el lema de Zorn y el axiome de sustitución que todo conjunto bien ordenado es

similar a algún ordinal. 13.20 0α α+ = y 0 α α+ = para todos los ordinales α . 13.21 1α α ++ = para todos los ordinales α . 13.22 Da un ejemplo de un ordinal α tal que 1 α α ++ ≠ . 13.23 Da un ejemplo de un ordinal β tal que 1 β β ++ = . 13.24 Prueba la ley asociativa para la adición de ordinales. 13.25 Sean α y β ordinales. α β< si y solo si existe un ordinal 0γ ≠ tal que α γ β+ = . 13.26 Si 0γ > , entoncesα γ α+ > . 13.27 Si γ α γ β+ = + , entonces α β= . 13.28 Prueba que el ordinal γ mencionado en el ejercicio 13.25 es único. 13.29 Da u contraejemplo para la cancelación para la adición ordinal. 13.30 Si α β< , entonces γ α γ β+ < + . 13.31 Si α β≤ , entonces γ α γ β+ ≤ + . 13.32 Si γ α γ β+ < + , entonces α β< . 13.33 Si γ α γ β+ ≤ + , entonces α β≤ . 13.34 Si γ β γ≤ + , entonces 0 β≤ . 13.35 Si α β< , entonces α γ β γ+ ≤ + . 13.36 Da un contraejemplo para lo siguiente en ordinales:

Si α β< , entoncesα γ β γ+ < + . 13.37 Si α γ β+ < +γ , entonces α β< .

13.38 Si α β+ = + , entonces α β= . 13.39 Si α β< , entonces n nα β+ < + para todo número natural . n13.40 Si α α α+ = , entonces 0α = . 13.41 Si α β ω+ = , entonces αβ ω= . 13.42 ·0 0· 0α α= = . 13.43 ·1 1·α α α= = . 13.44 Prueba la ley asociativa para la multiplicación de ordinales. 13.45 Prueba que la multiplicación de ordinales es distributiva izquierda con respecto a la adición de

ordinales. 13.46 Si γ es diferente de cero y α β< , entonces γα γβ< . 13.47 Si γα γβ< , entonces α β< . 13.48 Si γ es diferente de cero, entonces γα γβ= implica α β= . 13.49 Si α β< , entonces αγ βγ≤ . 13.50 Si βγ αγ< , entonces β α< 13.51 γ βγ< para 0β ≠ .

13.52 Si γ no es ni cero ni un ordinal límite y α β< , entonces αγ βγ< . 13.53 αγ βγ= y γ no es ni cero ni un ordinal límite implica que α β= . 13.54 Si αγ βγ= y α β≠ , entonces 0γ = o bien γ es un ordinal límite.

13.55 Sean , , α β ε ordinales tales que ε αβ< . Entonces 1· 1ε α β α= + para algunos

1 1, α α β β< < . Más aún, la representación es única.

13.56 Si , α β son ordinales con 0α < , entonces β απ ρ= + para algunos ordinales , , 0 , 0π ρ π β ρ≤ ≤ ≤ ≤α . Más aún, la representación es única.

13.57 Un ordinal 0β ≠ es un límite ordinal si ω es un factor izquierdo de β . 13.58 Bajo la división izquierda por 2, un ordinal tiene un resíduo de 0 o 1. Clasifica cada una de ls

siguientes por pares e impares: a) ω b) 1ω + c) 1 ω+ d) 2( 1)ω +e) ( 1)2ω + .

13.59 Definiciones. Una secuencia ordinal ( )i i μα α ∈= es una función con dominio el ordinal μ y con

valores ordinales iα . ¿Que role toma el axioma de sustitución en esta definición? Una sucesión

ordinal ( )i i μα ∈ es una sucesión ordinal creciente si i j< implica que i jα α< para todas

, i j μ∈ . Denotamos por lim ii Mα

∈ a sup{ | }i iα μ∈ o bien, el límite de una sucesión ordinal

creciente es el supremo de la imagen de la sucesión.

Prueba que toda sucesión ordinal creciente tiene un límite. 13.60 Nos referimos a una vecindad del ordinal α a cualquier vecindad ( , )γ δ con γ α< y α δ< .

Estas son vecindades asociadas con la topología de orden; para mas detalles, uno se puede referir al libro General Topology de J. Kelley, p57. Se dice que una sucesión ordinal ( )i i μα ∈ tiene un

límite λ (con respecto a la topología de orden) si y sólo si la sucesión ordinal esta eventualmente en toda vecindad del ordinal λ ; esto es, dada una vecindad ( , )y δ de λ existe un ordinal

ν μ∈ tal que si iν ≤ , entonces ( , )iα γ δ∈ . Prueba que el límite de una sucesión ordinal creciente definida aquí coincide con la definición sup{ | }i iα μ∈ utilizada en el ejercicio 13.59. 13.61 Prueba que una sucesión ordinal estrictamente creciente es una similitud. 13.62 Prueba que ( )i i μα ∈ es la única sucesión ordinal estrictamente creciente con μ como índice y la

misma imagen que ( )i i μα ∈ . 13.63 Da un ejemplo de dos sucesiones ordinales estrictamente crecientes tales que lim lim lim( )i i ii i iμ μ μ iα β α

∈ ∈ ∈+ ≠ + β .

13.64 Sea el ordinal más pequeño que no es enumerable (no finito o no equivalente a Ω ω ). Prueba que si α ∈Ω , entonces α es enumerable.

13.65 Si A ⊂ Ω y A es enumerable, entonces sup A < Ω .

13.66 Prueba que es un punto de acumulación de Ω +Ω , pero ninguna sucesión en (una sucesión es una sucesión ordinal con índice

{ }+Ω − Ωω ) tiene un límite. Con la oración “Ω es un punto de

acumulación de +Ω ” queremos decir que toda vecindad de Ω en +Ω contiene a un miembro de además de +Ω Ω mismo.

13.67 Sea ( )i i μα ∈ una sucesión ordinal estrictamente creciente con μ un ordinal límite. Prueba que

limj ii μα α

∈≠ para todo j μ∈ . Además que lim ii μ

α∈

es tambien un ordinal límite.

13.68 Sea ( )i i μα ∈ una sucesión ordinal estrictamente creciente con 0μ = o μ un ordinal límite.

Entonces prueba que lim ii μα

∈ es el mínimo ordinal en la sucesión ordinal. Da un ejemplo para

ilustrar que lim ii μα

∈ podría ser posiblemente un ordinal límite.

13.69 Sea ( )i i μα ∈ una sucesión ordinal con índice distinto de cero, no necesariamente creciente. Retomando el ejercicio 13.59 para el significado de límite, prueba que si μ no es un ordinal

límite, entonces lim ii μα

∈ existe, y si μ es un ordinal límite, lim ii μ

α∈

no siempre existe.

13.70 Para una sucesión ordinal estrictamente creciente ( )i i μα ∈ con índice distinto de cero, prueba que

sup{ | } sup{ | }i ii iγ α μ γ α+ ∈ = + ∈μ .

13.71 Para una sucesión ordinal estrictamente creciente ( )i i μα ∈ prueba que

sup{ | } sup{ | }i ii iγ α μ γα∈ = ∈μ .

13.72 Da un contraejemplo para sup{ | } sup{ | }i ii iα μ γ α γ μ∈ + = + ∈ .

13.73 (sup{ | }) sup{ | }i ii iα μ γ α γ μ∈ = ∈ .

13.74 Sea una condición tal que para cada ordinal ( )S x α , se establece ( )S α . Si ( )S β para toda β α< implica ( )S α , entonces ( )S α para todo ordinal α .

13.75 Para cada sucesión ordinal ( )i i μα ∈ sea (( ) )i if μα ∈ un ordinal. Entonces para cada ordinal ν

existe un único ordinal ( )u ν tal que ( ) ( | )u f uν ν= donde | {( , ( )) |u u }ν β β β ν= ∈ . 13.76 Para cada ordinal ξ sea ( )g ξ un ordinal. Sea α un ordinal. Entonces para cada ordinal ν

existe un único ordinal ( )u ν tal que ( )u ν α= si 0ν = , ( ) ( ( ))u g uν β= si ν β += , ( ) sup{ ( ) | }u uν ζ ζ ν= < si ν es un ordinal límite. Más aún, |u ν es una función.

13.77 Para cada ordinal β existe un ordinal ( )sα β tal que ( )sα β α= si 0β = ,

( ) ( ( ))s sα αβ δ += si β δ += , ( ) sup{ ( ) | }s sα αβ ζ ζ β= < si β es un ordinal límite.

13.78 ( )sα β α β= + para cualesquiera ordinales α y β .

13.79 Para cada ordinal β existe un ordinal ( )pα β tal que ( ) 0pα β = si 0β = ,

( ) ( )p pα αβ δ α= + si β δ += , ( ) sup{ ( ) | }p pα αβ ζ ζ β= < si β es un ordinal límite.

13.80 ( )pα β αβ= para cualesquiera ordinales α y β .

13.81 Para cada ordinal β existe un ordinal βα tal que 1βα = si 0β = , β δα α α= ⋅ si δ β+ = ,

sup{ | }β ζα α ζ β= < si β es un ordinal límite.

13.82 Asociada a una sucesión ordinal ( )i i μα ∈ tenemos una sucesión ordinal de sumas parciales

( )i ki k μα +∈∈∑ definida como sigue:

Si , entonces ; si 0k = 0ii kα

∈=∑ k δ += , entonces i ii k i δδ

α α α∈ ∈

= +∑ ∑ ; y si k es un ordinal

límite, entonces . La suma de la sucesión ordinal ( )sup{ | }i ii k ik

ζα α

∈ ∈=∑ ∑ ζ < i i μα ∈ es la suma

parcial ii kα

∈∑ .

13.83 Sea ( )i i μα ∈ la sucesión ordinal tal que iα α= para toda i μ∈ . Entonces prueba que

ii kα αμ

∈=∑ .

13.84 Encuentra la suma de la sucesión ordinal ( )i i μα ∈ donde iα ω= para toda i μ ω∈ = .

13.85 Encuentra la suma de la sucesión ordinal ( )i i μα ∈ donde iα ω= para toda 1i μ ω∈ = + .

13.86 Asociada a una sucesión ordinal ( )i i μα ∈ tenemos una sucesión ordinal de productos parciales

( )i ki k μα +∈∈∏ definida como sigue:

Si , entonces ; si 0k = 1ii kα

∈=∏ k δ += , entonces i ii k i δδ

α α α∈ ∈

= ⋅∏ ∏ ; si k es un ordinal

límite, entonces . El producto de la sucesión ordinal sup{ | }i ii k ik

ζα α

∈ ∈=∏ ∏ ζ < ( )i i μα ∈ es el

producto parcial ii μα

∈∏ .

13.87 Sea ( )i i μα ∈ la sucesión ordinal tal que iα α= para toda i μ∈ . Entonces prueba que

iiμ

μα α

∈=∏ .

13.88 Encuentra la suma y el producto de la sucesión ordinal ( )i i μα ∈ donde iiα ω= para toda

i μ ω∈ = .

13.89 El producto de ordinales 0α y 1α es definido como el ordinal similar al conjunto ordenado

0 1α α× tal que 0 1 0 1( , ) ( , )x x y y< si y sólo si 1 1x y< o ( 0 0x y< y 1 1x y= ). Debate la

siguiente generalización. El producto de ordinales ( )i i μα ∈ es el ordinal similar al conjunto

ordenado ii μα

∈∏ tal que ( ) ( )i i i ix yμ μ∈ ∈< si y sólo si k kx y< para algún k μ∈ y i ix y=

para toda , i i kμ∈ > .

13.90 Sea ( )i i μα ∈ la sucesión ordinal definida como sigue: 0α ω= , ( )ωββα α+ = . Sea

0 sup{ | }iε α ι ω= ∈ . Prueba que 00

αω ε= .

CAPITULO 14 Cardinales

14.0 Teorema de Schröder-Bernstein. Si :f X Y>→ y , entonces existe una

. :g Y X>→

:h X Y>→> Definición de dominación.

° X Yp si y solo si existe una :f X Y>→ .

Teorema. La dominación es reflexiva, antisimétrica y transitiva. Teorema de Cantor. X PXp para todos los conjuntos X . “ p ” significa “ ” y no “ ”.

° p :

Definición de un número cardinal. α es un número cardinal si y solo si α es un número ordinal tal que si β es un ordinal y β α: , entonces α β≤ . El número cardinal de un conjunto X es el mínimo ordinal equivalente a X . Teorema. si y solo si card card YX = X Y: ; card card X Y< si y solo si X Yp . Definición. Sean y b números cardinales. Sean a X y Y conjuntos tales que y

. Entonces card X a=

card Y b=card a b X Y+ = ∪ si . X Y∩ =∅

card ab X Y= × . card b Ya X= .

14.1 Por definición, X es dominado por Y si y solo si existe una :f X Y>→ ; X es equivalente

a Y si y solo si existe una :f X >→> Y . Prueba a) La dominación es reflexiva; b) La dominación es transitiva; c) La dominación es antisimétrica; d) Dado cualquier conjunto X un conjunto Y tal que domina estrictamente a X ; e) Cualesquiera dos conjuntos son comparables respecto a la dominación.

14.2 Prueba que ω domina estrictamente a cualquier n ω∈ . 14.3 Usando el lema de Zorn prueba que cualesquiera dos conjuntos son comparables respecto a la

dominación. Esta prueba es una prueba alternativa a la dada en la página 89 de NST. 14.4 Prueba que ¡ es equivalente a (0 , un intervalo abierto unitario de ,1) ¡ . Prueba que (0 es

equivalente a [0 . Prueba que [0 es equivalente a [0 . ,1)

,1) ,1) ,1]14.5 Si 1X es equivalente a 2X y es equivalente a y 1Y 2Y 1 1 2 2X Y X Y∩ = ∩ =∅ , entonces

prueba que X Y∪ es equivalente a 2 2X Y∪ .

14.6 y A C: B D: implica que A B C D× ×: . 14.7 La adición de números cardinales es conmutativa y asociativa. La multiplicación de números

cardinales es conmutativa, asociativa y distributiva con respecto a la adición. 14.8 Para números cardinales , b y c , si a a b≤ , entonces a c b c+ ≤ + . 14.9 Para números cardinales , b y c , si a a b≤ , entonces ac bc≤ . 14.10 Para números cardinales , b , muestra que a

i bab a

∈=∑ .

14.11 Para números cardinales , b , muestra que a bi b

a a∈

=∏ .

14.12 Para números cardinales , b y c : a; ( ) ; ( )b c b c c c c bc b ca a a ab a b a a+ = = = .

14.13 Para números cardinales , b , , si a d a b≤ , entonces d da b≤ .

14.14 Para números cardinales , b ; a 0d ≠ , si a b< , entonces ad d b≤ , y si , entonces .

ad d< b

a b<14.15 Todo número cardinal infinito es un ordinal límite. 14.16 Sea 2c ω= . Prueba que 1 1 . Sea 1cω = = {0}n ω∈ − . Prueba que

nn nω ω ω ω ω ωω ω+ = = = + = = . Más aún. ( 1) nn n c ncω ωω c+ = = + = = =c c

. Y ( 12c c c c c cc cωω ω+ = = = + = = = ) 2c c cn cω+ = = = .

14.17 Sea una familia no vacía de números cardinales indizados por un conjunto ( )i i Ia ∈ I . Supón que

el conjunto { | no tiene máximo. Entonces }ia i I∈ i ji Ia a j I

∈> ∀ ∈∑ .

14.18 son números cardinales distintos. Prueba que existe un conjunto infinito de números cardinales (un conjunto de números cardinales no significa el conjunto de todos los números cardinales).

, 2 , 2ccωω =

14.19 Prueba que existe un único número cardinal mas grande que todo cardinal en la familia . ( , , 2 ,...)ccω

14.20 Si 1 y 1 para los números cardinales a , , , entonces . a d< ≤ b d< ≤ b d d da b=14.21 Prueba que ! cω = donde !ω se refiere a

{0}ii

ω+∈ −∏ .

14.22 Prueba que . ! 2cc =14.23 Prueba que todo cardinal no finito es primo (no es producto de dos cardinales menores). 14.24 Prueba que card ω=¢ . 14.25 Prueba que card ω=¤ . 14.26 Muestra que el número de polinomios con coeficientes racionales es ω ; i. e., card [ ]X ω=¤ . 14.27 Un número algebraico es cualquier raíz de un polinomio con coeficientes racionales. Prueba que el

número de números algebráicos es ω . 14.28 Prueba que el número de números reales es 2ω ; i. e., card 2ω=¡ . 14.29 Cual es la cardinalidad del conjunto de todas las funciones continuas de ¡ a ¡ ? 14.30 Sean B A⊂ y card card B Aω ≤ < . Cual es la cardinalidad de A B− ? 14.31 Está probado en la página 13 del libro “Finite dimensional vector spaces” de P. Halmos que si X

es una base para un espacio vectorial V con card , (n )X n ω= ∈ , y si Y es cualquier base finita de V , entonces también. Prueba esta generalización del teorema: si card Y=n X es una base para un espacio vectorial V y Y es cualquier base para V , entonces . Observe también el ejercicio 10.5.

card card Y X=

14.32 Prueba la existencia de un número infinito de cardinales infinitos α tales que ωα α< . 14.33 Prueba la existencia de un número infinito de cardinales β tales que ωβ β= . 14.34 ¿Cuantos grupos pueden ser construidos de un conjunto con ω elementos? 14.35 Supón que A tiene cardinalidad ω ¿cuál es la cardinalidad del conjunto de todos los

subconjuntos finitos de A ? 14.36 Sea A con cardinalidad c ¿cuál es la cardinalidad del conjunto de todos los subconjuntos finitos

de A ? ¿de subconjuntos enumerables de A ? 14.37 Sean A con cardinalidad para algún cardinal e , b un cardinal menor o igual a . ¿Cuántos

subconjuntos de 2e e

A hay de cardinalidad menor o igual que b ? 14.38 Da un ejemplo de un conjunto A con cardinalidad a para el cual el conjunto de los subconjuntos

enumerables tiene cardinalidad mayor que . a14.39 Para f ωω∈ sea ( ) { | y ( ) 0}s f x x f xω= ∈ ≠ . Sea .

Prueba que es enumerable. { | y ( ) es finito}f f s fωωℑ = ∈

ℑ