Luis Felipe Melo Jiménez
Director: Gabriel Padilla
24 de Noviembre de 2010
Categorías tipo Ramsey
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
1. Preliminares
Preliminares Ramsey Clásico
Preliminares Categóricos
2. Ramsey desde las categorías
3. Categorías de Ramsey
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
La teoría de Ramsey involucra variadas ideas matemáticas. Debe su nombre al
matemático Británico Frank Plumpton Ramsey y cuenta con dos características muy
especiales que podríamos sintetizar en dos palabras: sencillez y adaptación. A partir
del simple principio del casillero la teoría de Ramsey se interesa en responder el
siguiente problema general: “¿Cuán grande debe ser cierto objeto matemático para
que al partirlo de cierto modo alguna de sus particiones cumpla una propiedad
dada?” Aunque los comienzos fueron como es natural parte de la teoría combinatoria;
esta sencilla idea se ha adaptado a otros muchos contextos y ha resultado útil en
campos como la teoría abstracta de conjuntos, la teoría de espacios euclideos, teoría
de grafos, espacios vectoriales y la teoría de categorías que nos ocupa aquí.
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Dado un conjunto finito designamos por el conjunto de sus
subconjuntos de tamaño
.
E claro que si el tamaño de es menor que entonces .
Notación ,
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Dado un conjunto finito designamos por el conjunto de sus
subconjuntos de tamaño
.
E claro que si el tamaño de es menor que entonces .
Notación ,
Sea no vacio un conjunto finito, y sea una función desde
hasta el conjunto de los primeros enteros no negativos
. Llamamos entonces una - de a la
familia , donde para cada entre y .
Definición
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Dada una función que determine una r-partición
decimos que , es subconjunto
- de respecto a la -partición si existe
alguna entre y tal que , es decir, si todos sus
subconjuntos de tamaño están en una de las clases definidas
por la función .
Conjunto -
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Si la cardinalidad del conjunto es usamos la notación para
indicar que dada una partición cualquiera de índice fijo siempre
existirá algún subconjunto de tamaño al menos tal que es
-homogéneo respecto a la partición dada; es decir, al partir en
partes, siempre habrá algún subconjunto de tamaño al
menos y una tal que .
Si no se cumple la propiedad para los números especificados entonces
usamos la notación , al mínimo número tal que lo
denotamos y lo llamamos, número de Ramsey para la tripla .
Propiedad de Ramsey
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ejemplo rápido de
Pentagrama 2-coloreado sin triángulos monocromáticos
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Ramsey Clásico
Dados números naturales existe un numero natural
, tal que para cualquier se tiene
.
Notese que el teorema se tiene trivialmente si no se cumple
Teorema de Ramsey Finito
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Una categoría es una quíntupla ordenada en donde
y son dos clases de conjuntos llamadas respectivamente objetos y
morfismos de la categoría, y son “asignaciones” que dan a cada
elemento de la clase un único elemento de la clase y por último una
asignación que va desde una subclase de hacia .
es el “producto cartesiano” de las clases, i.e., la clase cuyos
elementos son todos los pares ordenados que podemos formar con
elementos de . Estos objetos cumplen cuatro condiciones
Categoría
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Condiciones de la Categoría (1)
i) Empalme: Escribimos , es decir, pertenece a la subclase de
si y solo si , cumplen
y .
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Condiciones de la Categoría (1)
i) Empalme: Escribimos , es decir, pertenece a la subclase de
si y solo si , cumplen
y .
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
ii) Asociatividad de la asignación : se tiene que para
morfismos cualesquiera en .
iii) Condición de Pequeñez: Dados la subclase de los elementos de a
los que les asigna y les asigna forman un conjunto (es decir son
pocos posiblemente el conjunto vacío) este conjunto lo designamos
.
iv) Identidad: Para cada elemento existe un elemento de que deno-
taremos tal que y para morfismos cualesquiera
siempre que la composición tenga sentido según la condición de empalme.
Condiciones de la Categoría (2)
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Sean y ℬ categorías, una asignación ℱ que consista de
1. Una asignación que a cada objeto de la categoría asigna un objeto de la
categoría ℬ, .
2. Una familia de funciones .
para todo en los objetos de , es llamada un funtor si cumple con
i) para todo en los objetos de .
ii) para todo y y todo
objetos de .
Funtor
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Preliminares Categóricos
Sean dos funtores, una transformación natural es una tripla
ordenada donde
Transformacion Natural
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
i. Par cada objeto de , usualmente denotado es un morfismo de .
ii. Para cada morfismo en el siguiente diagrama conmuta
Preliminares Categóricos
Sean dos funtores, una transformación natural es una tripla
ordenada donde
Transformacion Natural
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
i. Par cada objeto de , usualmente denotado es un morfismo de .
ii. Para cada morfismo en el siguiente diagrama conmuta
Preliminares Categóricos
Sean dos funtores, una transformación natural es una tripla
ordenada donde
Transformacion Natural
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Una categoría es una subcategoría de la categoría si se cumplen las siguientes
cuatro condiciones.
i. La clase de los objetos de es una subclase de la clase de los objetos de .
ii. La clase de los morfismos de es una subclase de la clase de los morfismos
de .
iii. El dominio, el codominio y las composiciones que hacen los morfismos de
corresponden a los que tienen como objetos de .
iv. Cada -identidad es una -identidad.
Subcategoría
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Las categorías son usadas para capturar muchas nociones conjuntistas, por ende es
natural definir una categoría cuyos objetos son la clase de los conjuntos y
cuyos morfismos las funciones, podemos definir nuevas categorías con los mismos
objetos pero distintos morfismos, como que tiene los mismos objetos que
pero usando relaciones. O podemos “quitar” objetos y encontrarnos una nueva
categoría, es el caso de que consiste en los subconjuntos finitos con funciones,
notemos que entre dos objetos de existen los mismos morfismos que cuando
son considerados objetos de lo que no pasa cuando los consideramos objetos
de .
Rel, Set y Fin
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dado un objeto de una categoría, un subobjeto de es un par ordenado
donde es otro objeto de la categoría y es un monomorfismo, es
decir, que se cumple
o en otras palabras es izquierdo cancelable respecto a la composición de
morfismos.
Subobjeto, Monomorfismo
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dados dos objetos de una categoría llamemoslos y vamos a designar por al
conjunto de todos los subobjetos de cuyo primer elemento en la pareja ordenada
sea , en el contexto de las categorías tipo Ramsey lo llamaremos subobjetos de
de índice , no hay que confundir este concepto con .
Subobjetos de de índice ,
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Dado un objeto de la categoría y una s-coloracion de los subobjetos de un objeto
cuyo primer elemento sea , es claro que cualquier morfismo
determina una función entre los subobjetos de con primer elemento ,
Ramsey desde las categorías
Dados dos objetos de una categoría llamemoslos y vamos a designar por al
conjunto de todos los subobjetos de cuyo primer elemento en la pareja ordenada
sea , en el contexto de las categorías tipo Ramsey lo llamaremos subobjetos de
de índice , no hay que confundir este concepto con .
Subobjetos de de índice ,
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dada una coloración , tiene un subobjeto monocromático de
orden si la función es constante, a decir, el subobjeto que determina la
función .
Subobjeto Monocromatico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dada una coloración , tiene un subobjeto monocromático de
orden si la función es constante, a decir, el subobjeto que determina la
función .
Subobjeto Monocromatico
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dados números naturales existe un objeto tal que para
cualquier y cualquier -coloración existe un subobjeto
de índice monocromático respecto a
Teorema de Ramsey para Categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías
Dados números naturales existe un objeto tal que para
cualquier y cualquier -coloración existe un subobjeto
de índice monocromático respecto a
Teorema de Ramsey para Categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Si consideramos como morfismos las funciones inyectivas entre
naturales, entendiéndolos como cardinales finitos, tenemos el mismo
teorema finito de Ramsey, podemos considerar otros contextos como
espacios vectoriales y encontrar nuevas interpretaciones del teorema de
Ramsey para categorías.
Ramsey desde las categorías
Categorías Tipo Ramsey
Luis Felipe Melo Director: Gabriel Padilla
Ramsey desde las categorías