¿Caminos infinitos que conectan dos vértices?

Question

Se trata de la continuación de otro pregunta sobre los recorridos infinitos que, hay que reconocerlo, estaba mal planteada. Espero que esta pregunta esté mejor planteada.

El gráfico $N$ con un conjunto de vértices $V(N) = \mathbb{N}$ y $(x,y) \in E(N)$ si $x < y$ contiene trayectorias de longitud arbitraria que conectan 0 y un $n$ .

El gráfico $Q$ con un conjunto de vértices $V(Q) = \mathbb{Q}$ y $(x,y) \in E(Q)$ si $x < y$ contiene caminos de longitud arbitraria que conectan 0 y 1.

Por supuesto, ambos grafos contienen caminos infinitos, que empiezan en 0, pero no terminan en ninguna parte.

Es más o menos obvio, que $N$ no contiene un camino de longitud infinita que conecte 0 y un $n\in \mathbb{N}$ (porque todos $n$ son finitos).

Pero es difícil (para mí) "ver" y tener una idea de por qué $Q$ no contiene ningún camino de longitud infinita que conecte 0 y 1: cada camino finito entre 0 y 1 es un subconjunto finito de $E(Q)$ : $\lbrace (0,q_1),(q_1,q_2),...,(q_n,1)\rbrace$ . ¿Por qué no puede haber un infinito subconjunto de ese tipo?

¿Es imposible definir "ese tipo", es decir, la propiedad "ser un camino que une 0 y 1", o podemos definirla (tal vez en lógica de segundo orden) pero demostrar que ningún subconjunto infinito de $E(Q)$ con esta propiedad?

Answer 1

¿Por qué no puede haber un subconjunto infinito de ese tipo?

De qué ¿De qué tipo? Hans, sigues negándote a ser más preciso sobre lo que quieres que haga esta definición, y hasta que no empieces a hablar con algo de precisión no sé qué hay que decir más allá de "las definiciones estándar no permiten hablar de un camino infinito que conecta dos puntos porque los caminos infinitos no tienen dos puntos finales" o las otras cosas que ya he dicho en respuesta a tu última pregunta.

Answer 2

Creo que entiendo lo que quiere decir. Para ver por qué no hay conjuntos infinitos, intenta formular "ese tipo de camino" (los que conectan 0 con 1) como un conjunto: Podríamos intentar dejar que $P = \{\text{paths }\alpha \text{ in } Q| \alpha \text{ starts at 0 and ends at 1}\}$ pero un conjunto infinito nunca termina, así que nuestro vocabulario es escaso. Intentemos algo más preciso: Sea $P=\{(v_0,v_1),(v_1,v_2),\ldots,(v_{n-1},v_n)|v_0=0,v_n=1\}$ pero esto supone intrínsecamente que la longitud del camino es finita, es decir, $n$ . Sé que esto no es una prueba, pero me parece que la "conectividad" (al menos en los grafos) es una propiedad finita.

Para distinguir entre los dos caminos planteados por @tomcuchta y @Theo, habría que asignar pesos a las aristas, y entonces la definición de camino mínimo cambia drásticamente. La razón por la que vemos las secuencias relacionadas de números reales como diferentes es porque la distancia entre los valores se reduce (o se mantiene constante). Pero la distancia entre dos vértices en $Q$ sigue siendo siempre 1. En $Q$ los vértices son simplemente etiquetado con los elementos de $\mathbb{Q}$ . Por lo tanto, como los vértices no se acercan entre sí, nunca se llega más cerca de 1, siguiendo el camino dado por tomcuchta.

Puede que haya otras formas de describir la posibilidad de caminos infinitos, y me interesaría oírlas, pero dada la forma en que has formulado tu pregunta más arriba, no creo que se pueda hablar de un camino infinito con dos puntos finales. El camino dado por tomcuchta es infinito, pero no termina en 1 (ni en ningún otro lugar).

Answer 3

El problema inherente a esta idea es que, aunque se podría construir algo así como un camino infinito entre dos puntos (utilizando definiciones adecuadas), habría que construirlo como una secuencia de vértices/borde indexados por un conjunto totalmente ordenado donde:

1. Existen elementos infinitamente grandes. Es decir, un elemento $ω ∈ A$ donde el conjunto $\left\{α ∈ A| α < ω\right\}$ tiene cardinalidad infinita.

2. Cada elemento tiene un único sucesor y predecesor, excepto posiblemente los elementos máximo y mínimo. El predecesor es importante porque hace que el camino esté intuitivamente "enlazado".

3. Existen elementos mínimos y máximos (el inicio y el final del camino).

Estas condiciones impiden indexar los vértices utilizando cualquier conjunto bien ordenado (la prueba es bastante sencilla y se basa en el requisito de los predecesores). Esto excluye los ordinales y los números naturales, pero no el conjunto de números hipernaturales, que no está bien ordenado pero cumple todas las cualidades anteriores (por ejemplo, considere el intervalo $[1 ... H]$ para algún hipernatural infinito $H$ ).

En este caso, el conjunto de vértices/borde que componen el camino sería incontable, por lo que no se podrían etiquetar los vértices utilizando $ℚ$ . No conozco ningún conjunto contable que tenga estas propiedades, pero probablemente los haya.