¿Wolfram dice que todos los grafos funcionales tienen un número numerable de vértices?

Question

¿Dice Wolfram aquí que todos los grafos funcionales tienen un número contable de vértices?

Permítase que un grafo funcional $G$ mapee la órbita de la siguiente función $f:\Bbb Z_p\to\Bbb Z_p$

$x\mapsto p^{-1}\cdot(x-(x\pmod p))$ a través de los enteros $p$-ádicos.

(Aquí $x\pmod p$ es la función que mapea al número natural $n$ representante de algún elemento de $\Bbb Z/p\Bbb Z$ que es $0\leq n) Entonces se puede pensar en $f$ como simplemente eliminando el dígito más significativo de cualquier número $p$-ádico.

Entonces este grafo funcional comprende infinitos subgrafos conectados. Los que tienen órbitas eventualmente periódicas de periodo $m$ pueden representarse por las palabras de Lyndon de base $p$ de longitud $m$. Luego quedan infinitos sin representar, y se necesita el axioma de elección para elegir representantes de ellos.

Estoy confundido por donde Wolfram dice;

y por lo tanto puede ser especificado por una función que mapea $\{1,...,n\}$ en sí misma

lo cual parece implicar que un grafo funcional debe ser contable. ¿Cómo se aplica esta oración a mi ejemplo? Porque estoy bastante seguro de que la estoy entendiendo mal.

Answer 1

Los gráficos funcionales en el artículo de MathWorld no solo serían numerables; serían finitos. Esto no es sorprendente de ver en ese artículo:

• Muchas, quizás la mayoría de las discusiones de teoría de grafos solo consideran grafos finitos; muchos resultados sobre grafos finitos no se extienden a grafos infinitos, o requieren considerablemente más trabajo para hacerlo. Si leo algo sobre teoría de grafos, no asumiría que se aplica a grafos infinitos a menos que esto se mencione específicamente.
• En particular, si el 50% del artículo está dedicado a detalles de implementación en Mathematica, que no puede lidiar con grafos infinitos, creo que es seguro decir que solo considera el caso finito.

Sin embargo, no hay nada de malo en hablar sobre un grafo funcional infinito; puede ser especificado por una función que mapea el conjunto de vértices $ V $ consigo mismo, pero no hay nada inherentemente malo con que $ V $ sea infinito. Algunas definiciones para grafos finitos se rompen para grafos infinitos antes de intentar probar cualquier cosa sobre ellos, pero este no es uno de ellos.

Tu ejemplo es un grafo funcional infinito no numerable perfectamente válido, aunque hay dos advertencias que siempre deben darse en esta situación:

1. Ten cuidado al aplicar cualquier teorema particular sobre grafos funcionales que encuentres, antes de comprobar si esos teoremas tienen sentido en contextos infinitos (y no numerables).
2. Si lo estás discutiendo con teóricos de grafos, debes ser sincero sobre el conjunto de vértices siendo infinito no numerable si quieres evitar cualquier confusión.