Definitivas

notas de la clase final

Hoy basé la discusión sobre las notas aquí abajo. La versión original de estas notas fue para un curso que dí en otra universidad hace un par de años. La intersección con nuestro curso es grande, pero ojo: la diferencia simétrica es no vacía - hay temas en estas notas que no vimos en clase este semestre, y hay temas que vimos en clase y no aparecen en las notas. Hoy repasamos en clase uno de esos temas (continuidad topológica y de funciones ordinales). Otra cosa: aún quedan cosas que traduje demasiado rápido de mi presentación anterior, que originalmente en inglés.

Haga clic en la imagen para bajar la discusión de hoy.





Por otro lado, les prometí un ejemplo de multiplicación de ordinales:

(ε₀.ω⁷.4 + ω⁵.12 + ω.4 + 3).(ω⁸.2 + ω².2 + 4) =

= (ε₀.ω⁷.4 + ω⁵.12 + ω.4 + 3).ω⁸.2 + (ε₀.ω⁷.4 + ω⁵.12 + ω.4 + 3).ω².2 + (ε₀.ω⁷.4 + ω⁵.12 + ω.4 + 3).4 =

= ε₀.ω⁷.4.ω⁸.2 + ε₀.ω⁷.4.ω².2 + ε₀.ω⁷.4.4 + ω⁵.12 + ω.4 + 3 =

= ε₀.ω⁷.ω⁸.2 + ε₀.ω⁷.ω².2 + ε₀.ω⁷.16 + ω⁵.12 + ω.4 + 3 =

= ε₀.ω¹⁵.2 + ε₀.ω⁹.2 + ε₀.ω⁷.16 + ω⁵.12 + ω.4 + 3 =

= ε₀.(ω¹⁵.2 + ω⁹.2 + ω⁷.16) + ω⁵.12 + ω.4 + 3

algunos problemas para examen - salón hoy

El salón para hoy es el 405-202 (edificio "nuevo" de matemáticas).

Aquí, aquí y aquí hay material de estudio para examen.

Clase mayo 31 (P. Zambrano)

Decimos que κ → (λ)^r_s (donde κ y λ son cardinales y r,s naturales distintos de cero) ssi para cada conjunto S de cardinal κ y cada partición {A_i}^s_i=0 de [S]^r en s clases existe H⊂ S tal que |H|≥λ y j tal que [H]^r⊂ A_j


Intuitivamente, decimos que κ → (λ)^r_s ssi para cada conjunto S de cardinal κ y cada coloreo de [S]^r en s colores existe H⊂ S tal que |H|≥λ y que [H]^r es monocromático.


En clase vimos un argumento de por qué 6 → (3)²₂ y por qué no se tiene que 5 → (3)²₂.


Adicionalmente, vimos algunos pasos cruciales de la prueba del teorema de Ramsey finito (dados k,r,s naturales distintos de cero, existe n natural tal que n → (k)^r_s).


Enunciamos (sin demostración) el teorema de Ramsey infinito que dice que ℵ₀ → (ℵ₀)^r_s para todo r,s natural distinto de cero.


Vimos algunas aplicaciones de este teorema, como las siguientes:


• Todo conjunto p.o. infinito tiene un subconjunto infinito totalmente ordenado o en el cual todos sus elementos no son comparables 2 a 2.


• Todo conjunto p.o. infinito tiene un subconjunto infinito que es isomorfo a (N,<) o que es isomorfo a (N,>).


Pedro Zambrano.

examen final

El examen final tendrá lugar el

jueves 9 de junio, a las 4 pm.


La clase final será (como previsto) el martes 7 de junio, a las 4 pm.

fecha del examen final

ojo: la fecha del examen final no necesariamente es el 7 de junio. Solicité cambio oficial de fecha, estoy pendiente de la respuesta.

Por favor, estén atentos al blog. Si todo va bien, el final será después del 7 de junio, y podremos tener la clase final el 7 de junio a las 4 de la tarde como previsto.

av

Martes 24 de mayo

(clase de Pedro Zambrano)

El pasado martes vimos que cf(2^κ) > κ (el cual es consecuencia del Lema de König) implica que 2^ℵ₀ no puede ser ℵ_ω y que este mismo hecho implica también que 2^ℵ₁ no puede ser ℵ_ω ni ℵ_ω1. Un hecho más general que resume estos dos anteriores es el siguiente: si α ≥ β entonces 2^ℵ_α no puede ser ℵ_ωβ. Si 2^ℵ_α es igual a ℵ_ωβ, entonces ℵ_α< cf(2^ℵ_α)=cf(ℵ_ωβ)≤ ℵ_β, lo cual claramente es una contradicción.




Por otro lado, vimos otras consecuencias del Lema de König como por ejemplo (ℵ_ω)^ℵ₀ > ℵ_ω (ya que ℵ_ω= ∑ _n<ωℵ_n< ∏_n<ωℵ_ω=(ℵ_ω)^ℵ₀




Otra consecuencia interesante del Lema de König es el hecho de que para κ cardinal se tiene que κ< κ^cf(κ) (ya que siendo κ_i (i< cf(κ)) una sucesión creciente de cardinales menores que κ tales que κ=∑_{i< cf(κ)} κ_i, tenemos que κ=∑_{i< cf(κ)} κ_i < ∏_{i< cf(κ)} κ=κ^cf(κ)).

Pedro Zambrano

temas con Pedro Zambrano

Básicamente trabajarán dos temas con Pedro: lema de König y aplicaciones (martes 24) y teorema de Ramsey (martes 31).

Lean cuidadosamente los capítulos sobre Ramsey en el libro... el martes 31 habrá un miniquiz de lectura.

Suerte,

av

curso de verano en UniAndes

Están invitados a tomar el curso de verano de Criptografía en los Andes. Hablen con Humberto Sarria para detalles de cómo inscribirlo.

CURSO DE VERANO EN UNIANDES

Fundamentos de Criptografía: seguridad demostrable

Profesora: Adriana Palacio (estudiante del doctorado de University of California at San Diego)

Junio 16 a julio 21 de 2005

Este curso introduce las ideas formales básicas de la criptografía moderna. Aplicaremos la teoría de "seguridad demostrable" al diseño y análisis de protocolos criptográficos prácticos. Consideraremos objetivos clásicos de la criptografía como son la confidencialidad, la autenticidad o integridad, y el intercambio autenticado de claves. Los temas a tratar incluyen cifrados en bloque, funciones pseudoaleatorias, cifrarios simétricos, funciones de hashing, códigos de autenticación de mensajes, cifrarios asimétricos, firmas digitales, y, si el tiempo lo permite, pruebas interactivas de cero conocimiento.

La criptografía es sólo una parte de un área mucho más amplia: la seguridad de computadores y redes. Hay muchos temas que están fuera del alcance de la criptografía y que no trataremos en este curso, como los virus, los gusanos, los ataques de buffer overflow, el control de acceso, la detección de intrusos, etc. No consideraremos asuntos de implementación. No habrá tareas de programación.

El curso involucra abstracción matemática y demostraciones. Uno de los aspectos más importantes es aprender a manejar estos conceptos. Aunque la meta siempre es obtener soluciones prácticas, el trabajo involucrado en el curso es teórico. El requerimiento básico es la madurez matemática. El estudiante debe ser capaz de leer y escribir definiciones, resultados y demostraciones matemáticas.

Ver más detalles aquí y aquí.

congreso

Haciendo clic en la imagen, llega al cronograma del congreso. Realmente vale la pena que aproveche esa oportunidad - habrá muchos cursillos, conferencias, etc. Inscríbase a tiempo.

Recomendado: el cursillo de Carlos Videla "El décimo problema de Hilbert, la conjetura de Mazur y curvas elípticas" (del martes al viernes en la semana del congreso, de 8:00 a 9:20).

König, Тихонов

El lema de König (teorema en ZFC) da una cantidad enorme de información sobre la exponenciación cardinal.

König: dado cualquier μ > 0, y dadas familias de cardinales (κ_i)_{i < μ} y (λ_i)_{i < μ} tales que 0 < κ_i < λ_i para cada i < μ, se tiene

∑_{i < μ}κ_i < ∏_{i < μ}λ_i


Las demostraciones fueron expuestas en clase por algunos de ustedes. Es clave detectar el uso de AE en estas.

Una primera aplicación muy sencilla y simpática es el teorema de Cantor como corolario de König: si tomamos μ = κ, κ_i = 1, λ_i = 2, obtenemos

κ < 2^κ.


Más sofisticado (detalles en clase - usar una función cofinal para armar los κ_is y los λ_is): el lema de König implica que

cf(2^κ) > κ.


Esta es información realmente novedosa: por ejemplo, esto implica que, aunque 2^ℵ₀ puede ser ℵ₁, ℵ₂, ℵ₃, etc., ¡NO puede ser igual a ℵ_ω! Tampoco (por lo mismo) puede ser igual a ℵ_ω+ω, etc.


Ejercicio: usando König, demuestre que ℵ_ω^ℵ₀ tiene que ser mayor que ℵ_ω.


-

Del inicio de definiciones que vimos hacia (la mitad de) la equivalencia entre AE y el teorema de Tíjonov, revise (por ejemplo en Munkres) las de topología, abierto, cerrado, frontera, clausura, interior. Revise los ejemplos que vimos.

Y recuerde que les pedí que investigaran cómo son las topologías de orden asociadas a los órdenes de los ordinales ω+1, ω+ω, ω+ω+1, ω₁, etc. ¡Para el martes!

AE, Vitali (1905), König, independencia, Tíjonov

Ya estamos llegando al final del curso. Adjuntamos a la lista de equivalentes a AE un par de ítems:

1. AE
   
2. LZ
   
3. PBO
   
4. Producto cartesiano de conjuntos no vacíos es no vacío
   
5. Teorema de Tíjonov (producto de compactos es compacto)
   

De estos demostramos en detalle la equivalencia entre los tres primeros (con el cuarto es casi inmediato), y solo la mitad de la equivalencia con Tíjonov (demostrar el teorema topológico, usando AE, es todo un teorema grande del curso de topología - naturalmente no lo hacemos aquí - pero demostrar que Tíjonov implica AE sí lo haremos el próximo martes).

Vitali (1905): existe un conjunto de reales que no es medible Lebesgue. Este resultado, extraño si uno pretende identificar "medible" con la intuición física, lo demostramos en detalle en clase. Resumiendo (y saltándome un montón de pasos), esta es la idea: considere la relación de equivalencia ≡ en R dada por r≡s ssi r-s es racional. Usando AE, arme un conjunto V que consta exactamente de un único representante por cada ≡-clase de equivalencia, y tal que V⊂[0,1]. Usamos las dos propiedades de las medidas

• μ(X+a) = μ(X), para todo real a ,
  
• si (X_i)_{i < ω} es una familia de conjuntos disyuntos dos a dos, entonces μ(∪_iX_i) = Σ_i μ(X_i)
  

Observe que

[0,1] ⊂ ∪_{q∈[-1,1]∩Q} (V + q) ⊂ [-1,2].

Finalmente, usando las propiedades mencionadas de medida, concluya que V no puede tener medida:

• Si μ(V) = 0, entonces μ(∪_{q∈[-1,1]∩Q} (V + q)) = 0, con lo cual 1 = μ([0,1]) = 0, absurdo.
  
• Si μ(V) = ε > 0, entonces μ(∪_{q∈[-1,1]∩Q} (V + q)) = ∞ ... pero entonces 3 = μ([-1,2]) > ∞ ... absurdo...
  

Nota: faltan posts sobre Tíjonov, sobre König, etc. Esté pendiente.

axioma de elección

Estudiamos la semana que pasó varias cosas en torno a AE:

1. AE - el enunciado: dada una familia F de conjuntos no vacíos, existe una función s : F → ∪ F tal que s(F)∈F, para todo F∈F (decimos que s es una "función selectora" para F).
   
   
   la situación básica
   
   
2. Lo anterior muchas veces no es necesario (como axioma aparte). Por ejemplo, en un caso extremo, si todos los elementos de la familia F son síngletons, no es necesario AE para armar la función s . O, en un caso más interesante, si los conjuntos en F son por ejemplo todos conjuntos no vacíos de números naturales, no es necesario AE: basta, por ejemplo, definir s(F) como el mínimo elemento de F. Pero AE sí es necesario en el caso general.
3. Compare estas dos situaciones: F₁ consta de todos los intervalos abiertos de números reales, F₂ consta de todos los conjuntos abiertos de números reales. ¿Cuál de las dos familias tiene funciones selectoras que podemos construir? ¿Cuál no?
4. Son equivalentes AE, LZ (Lema de Zorn) y PBO (Principio del Buen Orden). Demostramos los detalles de esa equivalencia en clase.
5. Muchas veces usamos LZ como un argumento sobre una "familia de aproximaciones" a algún objeto que queremos demostrar que existe. Así, la prueba usual de la existencia de bases para espacios vectoriales, con LZ, pasa por considerar la familia de todos los conjuntos independientes de vectores (las "aproximaciones a una posible base"), demostrar la clausura de las cadenas ascendentes (aquí, ⊂-ascendentes)... y usar el elemento maximal que garantiza LZ - mostrando que debe ser una base.
6. Al igual que la existencia de bases para espacios vectoriales, muchas otras construcciones realmente fundamentales en la matemática post-1900 dependen de AE... o al menos de buena parte de este. Así, son consecuencias de AE (y ¡no se pueden demostrar tan solo en ZF!) las siguientes: existencia de bases para espacios vectoriales, unión contable de conjuntos contables es contable, existencia de ideales maximales, existencia de ultrafiltros, teorema de Tijónov, producto cartesianos de conjuntos no vacíos es no vacío, teorema de Hahn-Banach...
7. Pero por otro lado, el Axioma de Elección ha resultado tener consecuencias extrañas - patológicas si uno las toma sin cierto cuidado. Las más famosas de estas son, tal vez, la existencia de un subconjunto no medible de los reales y la paradoja de Banach-Tarski, según la cual existe una descomposición en un número finito de pedazos de S² (la esfera unitaria en R³) tal que al recomponerlos de cierta manera adecuada, ¡¡¡terminan siendo isométricos a la unión de dos esferas unitarias!!!

El enlace en wikipedia a la paradoja de Banach-Tarski parece correcto.

a mirar

La vez pasada vimos algunas propiedades básicas de cofinalidades:

1. cf cf α = cf α
2. cf α siempre es un cardinal (es decir, un ordinal inicial)
3. cf α ≤ α

También calculamos algunas cofinalides, y la pregunta de uno de ustedes nos llevó a la definición de cardinales regulares y singulares.

Un cardinal infinito κ es regular si cf κ = κ. Cuando un cardinal infinito no es regular, lo llamamos singular.

Para pensar para el martes:

todo cardinal sucesor es regular

¿Por qué?

El martes seguiremos con algo de teoría de cofinalidades y empezaremos la discusión del Axioma de Elección.

de cofinalidades y otros temas

De hoy lo importante es

1. ¿Qué axiomas de ZF valen en distintos niveles de la jerarquía acumulativa de von Neumann?
2. Cofinalidades

Del primer tema quedó en claro

• V_ω satisface ZF - {Infinito}. Aquí es bien importante saber hacer el argumento de por qué vale Reemplazo, y por qué valen Pares, Partes y Uniones (recuerde que la clave es calcular los rangos de las construcciones correspondientes).
  
• V_ω+22 satisface ZF - {Partes,Pares}. Aunque ahora sí vale Infinito, fallan Pares y Partes ... ¿por qué?
  
• V_ω+ω satisface ZF - {Reemplazo}. Ahora valen Infinito, Pares y Partes... pero falla Reemplazo. Usted debe poder explicar por qué.
• V_ε0 satisface ZF - {Reemplazo}.
  

Quedó incompleto por qué V_ω1 satisface ZF - {Reemplazo}.

--------------------

De cofinalidades deben poder explicar (idealmente, a partir de la definición y armando diagramas) para el jueves

1. La definición
2. ¿Por qué es cierto que cf(α) ≤ α?
3. cf(α) siempre es un cardinal
   

ojo

mañana empezamos cofinalidades

lea en Jech-Hrbacek sobre el tema

temas de la vez pasada

Aunque tarde, ahí va el post. Vimos

1. El resto de propiedades básicas de la jerarquía de von Neumann.
   
   
   
   • Todos los niveles V_α son conjuntos transitivos.
     
   • α < β → V_α ⊂ V_β y V_α ∈ V_β.
     
   • V_α ∈ V_α+1 - V_α.
     
   • |V_ω+α| = beth_α (no tenemos símbolo para la letra hebrea beth fácilmente accesible en html).
     
   • α ∈ V_α+1 - V_α. Esta última es más difícil: en clase lo logramos usando lo que ya sabíamos sobre el rango de α ordinal (ran(α)=α), y usando el siguiente teorema.
     
   
   
2. Rangos como "mínimos niveles".


Teorema: dado un conjunto x cualquiera,


ran(x) = min {α∈ON | x∈ V_α+1 - V_α}.

grupos - ejercicios - notas

Mañana jueves no hay clase por la suspensión de actividades en la U. Hay varias cosas que quiero que trabajen de aquí al martes próximo.

Pero antes, por favor revisen sus notas y sus grupos en la lista:





El orden de toma de apuntes es A-E-C-B-F-H-G. En este momento el grupo F se encuentra tomando notas, hasta el martes 26 de abril (como en F hay cuatro personas, les corresponden cuatro sesiones). El grupo H, de un solo estudiante, viene después.

-

He aquí una lista de ejercicios que deben trabajar para el martes. No todos serán discutidos, pero ustedes son responsables de ese material.

1. x es ordinal ssi x es transitivo y todo subconjunto transitivo propio y de x es un elemento de x .
   
2. Definición (la jerarquía acumulativa de von Neumann):
   V₀ = ∅
   V_α+1 = P(V_α)
   V_γ = ∪_{α < γ} V_α
   
   Demuestre que el rango (visto en clase) de un conjunto x es el mínimo ordinal α tal que x∈V_α+1 .
   
3. Demuestre que para todo α , V_α es transitivo.
   
4. α < β ⇒ V_α ⊂ V_β
   

reordenando los naturales - α-sucesiones

Hubo en la clase pasada dos soluciones distintas del problema de reordenar los naturales, de tal manera que queden con tipo de orden ω³. Para varios de ustedes ya es claro cómo generalizar esa solución a ω⁴, etc.,ωⁿ, etc. Ahora hay que seguir - reordenar los naturales en tipo de orden ω^ω.

Otra cosa: recuerde que, dado un ordinal α, una α-sucesión en un conjunto X es una función

s : α → X


Así, las ω-sucesiones son las sucesiones común y corrientes, pero también podemos hablar de (ω+1)-sucesiones, (ω+ω)-sucesiones, ω₁-sucesiones, ω^ω-sucesiones ... incluso de 3-sucesiones.

Piense en la siguiente pregunta para el martes:

¿Para cuáles α existen α-sucesiones crecientes en los reales?

Recuerde que ω₁ es el mínimo ordinal no contable. (Veremos más adelante, rigurosamente, que existen ordinales no contables.)

ejercicios de mañana

Solamente recogeré mañana el ejercicio de ordenar los naturales con tipo de orden ω³. El de ordenarlos en tipo de orden ω^ω lo pueden seguir trabajando hasta el martes.

celulares y chocolate

De ahora en adelante pueden hablar por celular en clase. Lo único es que en caso de contestar llamada, usted deberá traer en la clase siguiente chocolate para todos los demás en el salón :)

el séptimo punto

También hay soluciones al séptimo punto. No están hechas en xfig, sino a mano... :(

Haga click en la imagen para bajarlas.

¡¡¡Soluciones al Parcial!!!

Haciendo click aquí puede bajar las soluciones al parcial.

Empezamos ordinales mañana.

ejercicios, material, etc.

El parcial del martes 29 requiere que usted esté muy bien preparado. Eso implica hacer todos los ejercicios asignados en el syllabus, y también poder hacer algo de ejercicios de material extra.

Hoy en clase volvimos a ver algunos modelos - con la pregunta natural ... ¿cuáles axiomas de ZF valen en esos modelos?

Recuerde tres en particular:

A = (ω,S), donde nSm ssi m=n+1

B = (ω, < )

C = (ω,R), donde nRm ssi aparece un 1 en la m-sima posición (contando a partir de cero, de derecha a izquierda) de la expansión binaria de n

(recuerde que vimos ejemplos de esta última relación en clase ... por ejemplo 64 y 35 pertenecen (¡en el sentido de R!) a 2⁶⁴+2³⁵.

Por otro lado, a continuación están los pdfs de los ejercicios que mencioné hoy:

Primera tanda

Segunda tanda

Tercera tanda

parece que está arreglado

Parece (cruzo los dedos) que el blog ya quedó arreglado. ¡Vaya susto! Parece que fue un grupo de niñitos de 15 años de Brasil el que se metió a todo el dominio (que incluye miles de cuentas), y cambió toda la información.

Por ahora no cuelgo nada de interés para el curso - digamos, hasta el jueves, pues no sé si sí quedó arreglado. Ya veremos.

av

isomorfismos, etc.

Bueno, tal vez no alcanzamos a cubrir todos los ejercicios ayer, pero creo que quedan con una buena idea para seguir por su cuenta con el tema de isomorfismos de estructuras. Quedó abierta la siguiente pregunta:

buscar algún X que satisfaga

(N,∧,∨,|,1,0) ≈ (P(X),∩,∪,⊂,∅,X)

o explicar por qué no puede existir tal X.


-

El martes seguimos viendo cardinales.

-

Estudie la demostración de Cantor-Bernstein que aparece en p. 66 del libro-texto.

-

Prepare los ejercicios (ver el syllabus de clase) de pp 68-69, 73 y 78-79 para la clase.

para el jueves

asegurarse de entender a fondo los problemas que finalmente no recogí hoy

traer los problemas 3.2 de la página 51 y los 5.2, 5.3, 5.4, 5.5 y 5.6 de la página 62 a clase.

Adicionalmente, veremos aplicaciones del teorema de Cantor-Bernstein.

funciones y "medición de tamaño" de conjuntos

Hoy nos dedicamos a seguir armando conexiones entre el tamaño de un conjunto y propiedades de funciones.

A es más pequeño que B ssi existe una función uno a uno de A en B - esto se denota |A|≤|B|.

A es equipotente con B ssi existe una función biyectiva f:A→B - esto se denota mediante |A|=|B|.

|A|<|B| quiere decir entonces que existe una función uno a uno de A en B, pero no existe ninguna que sea sobre, de A en B. Con esta notación, el Teorema de Cantor dice que para todo X, |X|<|P(X)|.

---

Una pregunta natural es la siguiente (Del Corral hizo esta pregunta en clase): si sabemos que existen funciones uno a uno f:A→B y g:B→A ... ¿podemos concluir que existe una biyección de A en B? La respuesta es sí - pero no es inmediato: hubo un clase un intento de un estudiante de dar una prueba "sencilla", pero vimos que garantizar la inyectividad al "mezclar" (digamos) f y g^-1 no es fácil.

Teorema (Cantor - Bernstein): si existen funciones uno a uno f:A→B y g:B→A, entonces A y B son equipotentes.

En clase empezamos a armar la demostración.

Sean entonces f:A→B y g:B→A funciones uno a uno.

Partimos A en tres zonas disjuntas Z_i, Z_p y Z_∞.

¡Definiremos (el martes) la biyección teniendo en cuenta estas tres zonas!

hoy

Hoy (finalmente) discutimos el axioma de Reemplazo. Primero que todo es un esquema axiomático, al igual que Comprensión. Dada una fórmula φ(x,y) que sea "funcional en x " (es decir, dado cualquier x , existe un único y tal que φ(x,y) vale), tenemos una instancia del axioma de Reemplazo así:

Reemplazo_φ: dado un conjunto a ,

b={y∈a|φ(x,y) vale, para cierto x en a}

es conjunto.

A diferencia de los demás axiomas, no hay por ahora ejemplos sencillos de construcciones que usen reemplazo. Más adelante, veremos (¡ojo!) que para construir el ordinal ω+ω requerimos (una instancia de) Reemplazo.

La tarea del jueves quedó aplazada para el martes, pero ahora deben entregar adicionalmente el siguiente ejercicio - también adaptado de HSW:

Sean A y B conjuntos no vacíos. Sea F una familia de conjuntos dada por F={X_(a,b)|(a,b)∈AxB}, tal que

X_(a,b) ∩ X_(a,c) = ∅

para todo a∈A , y para todo b,c ∈B tales que b≠c.

1. Muestre con los axiomas de Zermelo-Fraenkel la existencia de las familias mencionadas en la ecuación que sigue, y


2. Demuestre que

---

Por otro lado, después de discutir sobre clases de equivalencia y funciones, y sobre la noción de cardinal, vimos el

Teorema de Cantor Dado un conjunto X, |X| < |P(X)| - es decir (de acuerdo con las definiciones vistas en clase), dado un conjunto X, existen funciones inyectivas de X en P(X), pero no existe ninguna función sobre.

La prueba fue hecha en detalle en clase - realzo aquí que el argumento usa una diagonalización. No es esta la única vez que aparecerá un argumento de diagonalización en el curso.

tarea para el jueves próximo

Ahora que (casi) tenemos los axiomas de Zermelo-Fraenkel, podemos justificar muchas construcciones. Ojo: como aún no hemos visto el Axioma de Reemplazo, aún hay ciertos conjuntos que no podemos construir.

Fuera de los ejercicios asignados en el syllabus de clase, usted debe traer el jueves escritos los siguientes 4 ejercicios (adaptados de Holz, Steffens y Weitz):

1. Asegúrese de dar una construcción con todos los pasos de los siguientes conjuntos:

0, 1, 2, ω, s(ω) = ω ∪ {ω}

si a y b son conjuntos, y usamos la convención mediante la cual representamos la pareja ordenada (a,b) usando {a,{a,b}}, construya usando los axiomas los siguientes conjuntos

a x b
{P(x)|x∈a}
si a≠∅, entonces ∩a es conjunto

2. Demuestre que [a,b]={a,{a,b}} tiene la propiedad de los pares ordenados ([a,b]=[a',b'] ssi a=a' y b=b').

3. Sea f : A→ B una función. Defina G : P(B) → P(A) mediante

G(X) = f^-1(X) = {x∈ A|f(x)∈X}.

Demuestre que G es realmente una función.

Demuestre que G es inyectiva ssi f es sobreyectiva.

4. Para el orden dado en tablero hoy, calcule minimales, maximales, etc. (¡todo!) de la circunferencia de centro en el origen y radio 2. Son en total OCHO dibujos que debe entregar usando la convención verde-rojo usada en clase. No aceptaré dibujos sin esa convención.

Lo anterior hace parte de su nota, como un quiz. Recibiré las tareas hasta el momento de clase (9 am).

Por último, hay un BONUS para el MARTES 22 (un 5.0 extra para quien lo traiga resuelto correctamente):

Ejercicio bonus: demuestre que el axioma de pares se puede derivar de los demás axiomas de ZF. Ayuda:

1. Justifique por qué {∅,{∅}} es un conjunto.
2. Sean a y b conjuntos arbitrarios, y considere la fórmula ψ(x,y) = [(u=∅ ∧ v=a) ∨ (u={∅} ∧ v=b)], para aplicar el Axioma de Reemplazo.