Processing math: 100%

9 votos

¿Cuántos gráficos contables hay?

Aunque hay un número incontable de subconjuntos de N sólo hay un número contable de clases de isomorfismo de modelos contables infinitos -o contables, para abreviar- de la teoría vacía (sin axiomas) sobre una unario relación.

¿Cuántas clases de isomorfismo de modelos contables de la teoría vacía sobre una binario relación (también conocida como teoría de grafos) existen? Es decir, ¿cuántos grafos contables no etiquetados hay?

Un argumento que se puede esgrimir es el siguiente: Dado que el número de grafos no etiquetados con n nodos crece (más rápido que) exponencialmente (en lugar de crecer linealmente en el caso de una relación unaria), debe haber incontablemente muchos grafos no etiquetados contables. (Análogamente al caso de los subconjuntos: el número de subconjuntos de conjuntos finitos crece exponencialmente, así ( ) hay incontables subconjuntos de un conjunto contablemente infinito).

¿Cómo se puede dar rigor a este argumento?

2voto

John Fouhy Puntos 759

Quizá le interese una pregunta relacionada, pero bastante diferente. Supongamos que elegimos las aristas de un grafo contable al azar según alguna probabilidad p . ¿Cuántas gráficas diferentes esperamos obtener, si repetimos el experimento varias veces?

Se podría pensar que cada vez obtendremos un gráfico diferente, pero de hecho, con probabilidad 1 el gráfico generado será isomorfo al llamado Gráfico de Rado . Este es el mismo gráfico inmaterial de la probabilidad p e incluso se obtienen los mismos gráficos si las probabilidades no decaen demasiado rápido (bajo algunas condiciones arbitrarias ω -ordenación de las aristas).

La encantadora prueba es una ilustración del argumento de ida y vuelta - compruébalo.

1voto

aleksandar Puntos 189

En la "Teoría de los Modelos" de Wilfrid Hodges, p. 355, encontré como ejercicio

(c) si L es la firma con una símbolo de relación binaria, hay continuos no isomórficos ultrahomogéneos ω -categoría de firma L.

que parece un poco más fuerte: ultrahomogéneo y ω -¡Categórico!

0voto

S.Koch Puntos 315

Dejemos que G denota el conjunto de todos los grafos infinitos contables (simples no abalorios).

|G||R|

Para ver esto, construimos una función inyectiva f:2NG (Tomo N={1,2,} ), porque |2N|=|R| . Sea Pn denotan el gráfico de trayectorias en n vértices. Obsérvese que P1 es el gráfico trivial sin bordes. Para dos grafos G1,G2 y denotar su suma por G1G2 (gráficamente, nos limitamos a dibujar ambos gráficos uno al lado del otro, sin conectarlos). Esta operación es conmutativa y asociativa y podemos sin problema generalizarla a cualquier conjunto S de gráficos para obtener GSG . Además, para dos gráficos G1,G2 dejar G1G2 denotan la unión de G1 y G2 . Entonces, para cualquier gráfico G , GP1 es el gráfico que se obtiene añadiendo un nuevo vértice y aristas que conectan el nuevo vértice con todos los vértices de G .

Ahora defina f por f(A)=((nAPn)P1)nNAPn

Visualmente, dibujamos cada número en el plano (por su gráfico de trayectoria) y luego pegamos todos los números/grafos que están en el subconjunto A .

|G||R|

Podemos describir un multigrafo dirigido con una tupla (V,E,S,T) donde V es el conjunto de vértices, E es el conjunto de aristas y S,T son funciones de E a V que describe el vértice origen y el vértice destino de cada arista. El conjunto de todos los multigrafos dirigidos contables puede describirse entonces por G={(N,N,S,T):S,TNN}={N}×{N}×NN×NN

Obsérvese que este conjunto contiene muchos grafos que son isomorfos entre sí. También existe un mapa de inclusión natural desde G en G que puede obtenerse asignando los números naturales a los vértices y a las aristas y una dirección a cada arista, de modo que |G||G| . Además, se sabe que |NN|=|R| Así que |G|=|{1}×{1}×R×R|=|R2|=|R| .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X