0
$\begingroup$

This is a follow-up to another question concerning infinite paths which was admittedly ill-posed. I hope this question is posed better.

The graph $N$ with vertex set $V(N) = \mathbb{N}$ and $(x,y) \in E(N)$ iff $x < y$ contains paths of arbitrary length connecting 0 and an appropriate $n$ .

The graph $Q$ with vertex set $V(Q) = \mathbb{Q}$ and $(x,y) \in E(Q)$ iff $x < y$ contains paths of arbitrary length connecting 0 and 1.

Of course, both graphs contain infinite paths, starting from 0, but ending nowhere.

It's more or less obvious, that $N$ doesn't contain a path of infinite length connecting 0 and an $n\in \mathbb{N}$ (because all $n$ are finite).

But it's hard (for me) to "see" and get a feeling why $Q$ doesn't contain a path of infinite length connecting 0 and 1: each finite path between 0 and 1 is a finite subset of $E(Q)$: $\lbrace (0,q_1),(q_1,q_2),...,(q_n,1)\rbrace$. Why cannot there be an infinite subset of that kind?

Is it impossible to define "that kind", i.e. the property "being a path connecting 0 and 1", or can we define it (in second order logic maybe) but prove, that no infinite subset of $E(Q)$ with this property exists?

  • 0
    Why wouldn't the path 0->1/2, 1/2->3/4, 3/4->7/8, ... be an infinite path connecting 0 and 1?2011-05-17
  • 1
    I guess you're picturing $Q$ as the rational points on the real line. But maybe this helps: How do you distinguish between the sequence given by tomcuchta and the sequence $0,1,2,3,\ldots$ *purely in terms of the graph $Q$*? In other words: any two adjacent vertices have distance $1$, so the picture of $\mathbb{Q} \subset \mathbb{R}$ is completely misleading.2011-05-17
  • 0
    The difference is: in N the only candidate for an endpoint of an infinite path is $\omega$ which is not in V(N). In Q I have a candidate endpoint which *is* in V(Q). And I have paths of arbitrary lengths to that given endpoint.2011-05-17
  • 2
    Hans: but that's exactly the point I was trying to make! there is **no such thing** as a *candidate endpoint* if you're thinking purely in terms of the graph $Q$. The vertices of tomcuchta's path all have distance $1$ to the vertex $1$, even if the "candidate endpoint" supposedly is $1$.2011-05-17
  • 1
    @Hans: I think you're still thinking of the vertices as *numbers,* but the rationals are just useful *labels* for the vertices of your graph. Your graph has none of the inherent structure of the rationals. An equivalent formulation of $Q$ is a digraph where every vertex has infinitely many in-edges and infinitely many out-edges.2011-05-17
  • 0
    Maybe one can show rigorously that any cardinality-neutral definition would boil down to "being the vertex set of a path in the line graph connecting its first and last vertex (= edge)" - which is obviously **circular**!2011-05-17
  • 0
    What if you model the graph using hyper-real numbers? You can just let there be an edge between $v$ and $v + 1$ for every $v ∈ {^*}ℤ = V$, and then there exists an infinite path between $0$ and $H$.2014-04-06

3 Answers 3

0

The inherent problem in this idea is that while you could construct such a thing as an infinite path between two points (using suitable definitions), you'd have to construct it as a sequence of vertices/edges indexed by a totally ordered set where:

  1. There exist infinitely large elements. That is, an element $ω ∈ A$ where the set $\left\{α ∈ A| α < ω\right\}$ has infinite cardinality.

  2. Every element has a unique successor and predecessor, except for possibly the maximal and minimal elements. The predecessor is important because it makes the path intuitively 'linked'.

  3. There exist minimal and maximal elements (the start and end of the path).

These conditions preclude indexing the vertices using any well-ordered set (the proof is quite simple, and relies on the requirement for predecessors). This excludes ordinals and natural numbers, but not the set of hyper-natural numbers, which isn't well-ordered but fulfills all of the qualities above (e.g. consider the interval $[1 ... H]$ for some infinite hyper-natural $H$).

In this case, the set of vertices/edges that make up the path would be uncountable, and so you couldn't label the vertices using $ℚ$. I'm not familiar with any countable sets that have these properties, but there probably are.

  • 0
    This is an interesting idea, but I am missing one thing: the index set should itself be connected in some sense. Otherwise a ray starting in $a$ and a "reverse" ray ending in $b$ could be combined into a single index set, which could be used to show that the disjoint union of two rays is connected. (See also [this answer](http://math.stackexchange.com/a/1725369/246783).) This is a very undesirable side-effect of your definition, interesting as your idea may be, and therefore it is my opinion that we should only consider finite paths when talking about connectivity.2016-04-03
4

Why cannot there be an infinite subset of that kind?

Of what kind? Hans, you are still refusing to be any more precise about what you want this definition to do, and until you start talking with some precision I don't know what there is to say beyond "the standard definitions do not allow you to speak of an infinite path connecting two points because infinite paths do not have two endpoints" or the other things I already said in response to your last question.

  • 0
    I tried to be (more) precise: I am looking for a rigorous definition of "path connecting two vertices" which is neutral with respect to the path's length and - maybe - a rigorous proof why such a path *must* be finite. (I find it not so clear what you mean by "the standard definitions do not allow you to speak of an infinite path connecting two points".)2011-05-17
  • 2
    @Hans: in the standard definitions, a path is already declared to be finite: a path between two vertices $u, v$ is a collection of vertices $u = u_0, u_1, u_2, ... u_n = v$ such that $u_i$ is connected to $u_{i+1}$ by an edge. There is no need for proof here. If you would like to offer an alternate definition of "path," then please make it clear that you are doing so (I already offered one in the previous question, but again, it involves modifying a topology on the graph).2011-05-17
  • 0
    @Hans: I suppose if you are really insistent on avoiding mentioning the length specifically, one might say that a path in a graph is a subgraph isomorphic to a connected tree with no edges of degree greater than $2$. Then the only paths are either finite, infinite in one direction (one end), or infinite in both directions (zero ends). Would you like to see a proof of this? (The keyword here is "connected," which is a condition that itself is about finite paths.)2011-05-17
  • 0
    I take your offer: Yes, I'd like to a proof of this.2011-05-17
  • 0
    @Hans: I don't think this is likely to help anything, since the finiteness is already implicit in the graph-theoretic definition of connectedness. So first let me ask you a question: do you think that the graph-theoretic definition of connectedness is reasonable?2011-05-17
  • 0
    Yes, it is reasonable, but it rules out from the very beginning to even think and talk about "infinite connectedness".2011-05-17
  • 0
    @Hans: yes, that is the point I'm trying to make. So do you accept this or not? Again, I already discussed in my answer to your previous question how to make sense of "infinite connectedness" by modifying the topology. Do you want to talk about _that_, or do you want to keep trying to talk about "infinite connectedness" in a setting where it doesn't fit?2011-05-17
  • 0
    I am sorry, but I'm not really convinced that talking about "infinite connectedness" can or should or must be ruled out by definition: I still don't understand why there cannot be another ("better") definition. For the moment, I'd like to take a deeper look at the topological approach you suggested - and stop the discussion.2011-05-17
  • 0
    @Hans: here's a basic reason. A graph can be thought of as a 1-dimensional simplicial complex in a natural way (http://en.wikipedia.org/wiki/Simplicial_complex): as a topological space, roughly speaking it is obtained by thinking of each edge as a copy of $[0, 1]$. With the standard topology on such a thing, which is there for a good reason, the resulting space is connected if and only if it is path-connected if and only if it is connected in the usual graph-theoretic sense.2011-05-17
  • 0
    @Hans: I never claimed that there wasn't another definition. In fact, quite the opposite: I _showed you another definition._ What I claimed, and have been claiming, is that the standard definitions do not allow you to talk about infinite connectedness, and also that the standard definitions are generally there for a good reason.2011-05-17
  • 0
    @Qiaochu: I really thank you a lot for the time and efforts you spend.2011-05-17
3

I, for one, think I understand what you mean. To see why there are no infinite sets, try to formulate "that kind of path" (the ones connecting 0 to 1) as a set: We could try letting $P = \{\text{paths }\alpha \text{ in } Q| \alpha \text{ starts at 0 and ends at 1}\}$ but an infinite set never ends, so our vocabulary is lacking. Let's try something more precise: Let $P=\{(v_0,v_1),(v_1,v_2),\ldots,(v_{n-1},v_n)|v_0=0,v_n=1\}$ but this is inherently assuming that the length of the path is finite, namely, $n$. I know this isn't a proof, but it seems to me that "connectedness" (at least in graphs) is a finite property.

In order to distinguish between the two paths brought up by @tomcuchta and @Theo, you would need to assign weights to the edges, and then the definition of minimal path changes drastically. The reason we see the related sequences of real numbers as different is because the distance between the values is shrinking (or staying constant). But the distance between two vertices in $Q$ is still always 1. In $Q$, the vertices are just labelled with the elements of $\mathbb{Q}$. So, since the vertices are not getting closer to one another, you never get any closer to 1, following the path given by tomcuchta.

There may be other ways to describe the possibility of infinite paths, and I'd be interested to hear them, but given the way you've formulated your question above, I don't think you can speak of an infinite path with two endpoints. The path given by tomcuchta is infinite, but it does not end at 1 (or anywhere else).

  • 0
    Or to make the picture even more drastic: the path $0, 1/2, 3/4, \ldots$ has constant distance to $1$ (on the vertices) so you're travelling on the sphere around $1$ with respect to the usual path metric.2011-05-17
  • 1
    @Theo yes, that's another good way to look at it. Actually, the way he has $Q$ defined, its a digraph (edges only move in the positive direction), so the distance from any vertex in the path to 1 is 1, and the distance from 1 to any vertex in the path is (dare I say it?) infinite.2011-05-17
  • 0
    I think your second definition is a good one. It shows why you need a last point. I was thinking of trying to rescue the infinite path by allowing $P$ to have order type $\omega +1$, so defining $P=\{(v_0,v_1),(v_1,v_2),\ldots,(v_{\omega},v_{\omega+1})|v_0=0,v_{\omega+1}=1\}$, but how do you say $(v_{\omega},v_{\omega+1})$ connects to what came before? There is no $(v_{\omega-1},v_{\omega})$. I don't see any good way to get past the limit, which is why we don't talk of infinite paths.2011-05-17