¿Cuántos gráficos contables hay?

Question

Aunque hay un número incontable de subconjuntos de $\mathbb{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?

Answer 1

He aquí una forma explícita de producir grafos continuos-múltiples no isomórficos por pares (simples, no dirigidos, sin bucles).

Comience con un $3$ -ciclo entre vértices etiquetados $-2,-1,0$ . Al vértice $-1$ adjuntar una cola (= camino) de longitud $1$ y al vértice $-2$ adjuntar una cola de longitud $2$ . Ahora, para cada entero positivo $n$ , adjuntar una cola de longitud $n$ al vértice $0$ y etiquetar el vértice terminal en esta cola $n$ . (Así que tenemos algunos vértices que no hemos etiquetado, pero ciertamente sólo un número contable de ellos).

Ahora céntrate en los vértices marcados $1,2,3,\ldots$ : colorear los Impares de rojo y los pares de verde. Consideremos el conjunto de todos los posibles grafos bipartitos en este conjunto de vértices, es decir, en los que todas las aristas conectan el rojo con el verde. Es evidente que hay un número continuo: por ejemplo, incluso las opciones independientes de incluir / no incluir las aristas $1--2$ , $1--4$ , $1--6$ y así sucesivamente da un conjunto de cardinalidad continua. Afirmo que todos estos grafos son no isomórficos por pares. De hecho, el único ciclo de tres en cualquiera de ellos está formado por los vértices $-2,-1,0$ y de ello se deduce fácilmente que cualquier isomorfismo entre dos de estos grafos lleva $0$ a $0$ , $-1$ a $-1$ y $-2$ a $-2$ . De esto se deduce que para todo $n \in \mathbb{Z}^+$ , un isomorfismo toma el vértice etiquetado $n$ al vértice etiquetado como $n$ y, por lo tanto, todos los vértices son fijos.

(Por cierto, el argumento que sugieres no me parece en absoluto válido. Tengo la firme sospecha de que hay teorías de primer orden tales que el número de modelos no isomórficos de tamaño finito $n$ crece al menos exponencialmente con $n$ pero para la que sólo hay un número contable de clases de isomorfismo de modelos contables).

Añadido : Quiero asegurarme de que las rutas de $0$ a $n$ siguen siendo no isomórficas por pares cuando se añaden aristas, por lo que es mejor modificar ligeramente la construcción. Por ejemplo, llamar al penúltimo vértice del camino $p_n$ y adjuntar una longitud más una cola en $p_n$ , por lo que ahora $p_n$ tiene grado $3$ .

Answer 2

Una forma es construir una inyección a partir de $2^{\mathbb{N}}$ (o de algún otro conjunto incontable) al conjunto de grafos contables. Hay muchas, muchas maneras de hacer esto.

Esta es una manera: Construiré un gráfico contable correspondiente a una función $f: \mathbb{N} \rightarrow \{0,1\}$ . El gráfico tiene vértices $y$ y $x_{n,i}$ para $n \in \mathbb{N}$ y $1 \leq i \leq n+1$ . Para cada uno de los fijos $n$ conectamos $x_{n,i}$ para todos $i$ (en una cadena como sugiere Alex, o un bucle, o un gráfico completo cualquiera servirá). Entonces añadimos una arista desde $y$ a $x_{n,1}$ si $f(n)=1$ .

Esto es realmente una inyección; podemos recuperar $f$ .

Editar: Al principio tenía una construcción multigráfica, con múltiples aristas a cada vértice, que no es lo que quería la pregunta. He modificado la construcción para hacer un gráfico simple.

Answer 3

Aquí hay una biyección entre $[0,1) \subset \mathbb{R}$ que es incontable, y una colección no isomorfa por pares de grafos contablemente infinitos:

Para $x \in [0,1)$ , dejemos que $0.x_1 x_2 x_3 ....$ sea su única expansión decimal (así $0\le x_i<10$ para cada $i$ y ninguna expansión termina en infinitos 9's). Construye el gráfico $G_x$ de la siguiente manera: empezar con el ciclo de 3 en $\{a,b,c\}$ ; adjuntar la cadena infinita $(a,1,2,3,...)$ al nodo $a$ y colocar una cadena de longitud $x_i$ a cada nodo $i \ge 1$ .

Una mínima modificación de esto (utilizar la longitud de la cadena $x_1 x_2 ... x_i$ en lugar de $x_i$ ) da una biyección que preserva la relación de orden: $G_x$ es un subgrafo de $G_y$ si y sólo si $x \le y$ .

Answer 4

Supongo que te refieres a un gráfico contable que es contablemente infinito. También asumiré que tu relación puede ser una relación binaria arbitraria y no sólo simétrica ya que pareces estar interesado en ese caso.

En este caso son incontables. Pues, un caso especial de una relación binaria es un orden total. No necesitamos añadir nada a la teoría para tener un orden total; es sólo un caso especial y el ordenamiento se preservará por isomorfismo. Hay incontables órdenes no isomórficos en un conjunto totalmente ordenado.

En efecto, dejemos $N$ sean los números naturales. Sea $S$ sea un subconjunto de $N$ . Sustituir cada $s\in S$ por una copia de $\mathbb{Q}\cap [0,1]$ donde $\mathbb{Q}$ son los racionales. Es fácil demostrar que si $S\not = T$ entonces se obtendrán órdenes no isomórficas de esta manera. Pero hay incontables subconjuntos de $N$ .

Por tanto, hay un número incontable de órdenes en un conjunto contable.

Answer 5

Otra forma muy sencilla de demostrar que son incontables es con los ordenamientos de los pozos: Por definición, las ordenaciones de un conjunto contable son $\aleph_1$ .

EDITAR: He aquí otra forma sencilla de demostrar que lo son $2^{\aleph_0}$ muchos. Toma todos menos uno (llamémoslo $p$ ) de los nodos contables y ordenarlos con el orden estándar de los números naturales. Esto esencialmente asigna a cada uno de estos nodos un número natural. Ahora utiliza el nodo sin bordes $p$ que mantuvimos para describir las funciones características: Para cada subconjunto $X$ de los números naturales añade una arista desde el nodo que denota $n$ a $p$ si y sólo si $n\in X$ . Es trivial ver que todos estos gráficos no son isomorfos: Si dos de ellos lo fueran, dos conjuntos diferentes de números naturales coincidirían.