Characterization of infinite paths in graphs

Question

First an introduction.

A directed graph we all know what is, and a graph is serial whenever every vertex has a successor. I do not consider the empty graph. A pair $(\mathcal{G},s)$ is called a rooted graph when $s \in \mathcal{G}$ and $\mathcal{G}$ is a directed serial graph.

Given a rooted graph $(\mathcal{G},s)$, a $(\mathcal{G},s)$-path is a function $\lambda: \mathbb{N} \rightarrow V(\mathcal{G})$ such that $\lambda(0) = s$ and for all $i \in \mathbb{N}$, $(\lambda(i),\lambda(i+1)) \in E(\mathcal{G})$. Given any rooted graph $(\mathcal{G},s)$, we define the set $N(\mathcal{G},s)$ as follows: $$N(\mathcal{G},s) = \{ X \subseteq V(\mathcal{G}) \mid \text{ exists a $(\mathcal{G},s)$-path $\lambda$ s.t. for all $i \in \mathbb{N}$, } \lambda(i) \in X \}$$

My question is, for what sets $N$ does there exist a rooted directed graph $(\mathcal{G},s)$ such that $N = N(\mathcal{G},s)$? I am looking for a way of describing (possibly infinite) directed serial graphs by giving a set of sets of vertices, each of which corresponds to an infinite path starting in a specific start vertex $s$. I call these sets neighbourhood sets (a slightly unfortunately name in graphs, I agree, but it comes from modal logic and its neighbourhood semantics, which I am applying this to).

I would like to make some restrictions on a family of sets so that I can say when such a family of sets do has a corresponding graph, i.e. given a set of sets $N$, which properties must $N$ have in order to have a rooted directed graph $(\mathcal{G},s)$ such that $N = N(\mathcal{G},s)$.

Define the non-monotonic core of $N$ as follows: $$N^{nc} = \{ X \in N \mid \not \exists Y \in N \text{ with } Y \subset X \}$$

I have come up with a few trivial properties that are all necessary, but they are not sufficient, not even when restricted to finite graphs. The properties are as follows:

• Safety: The universe itself (i.e. the vertex set $V$) has to be contained in $N$
• Reflexivity: There is an element $s$ such that when $X \in N$, we have that $s \in X$
• Upwards closed: If $X \in N$ and $X \subseteq Y \subseteq V$, $Y \in N$
• Countable case: If $X \in N^{nc}$, then $ |X| \leq \omega $
• If $X \in N^{nc}$ and $Y \in N^{nc}$ and $|X \cap Y| = |X \setminus Y| = |Y \setminus X| = \omega$, then there has to be at least another (or infinitely many) $Y \neq Z \in N^{nc}$ with $|X \cap Z| = |X \setminus Z| = |Z \setminus X| = \omega$

Now, it is trivial to check that the $N(\mathcal{G},s)$ satisfies the above properties for any directed graph $\mathcal{G}$, but they are not sufficient. Consider the following set: $$N = \{ \{s,1,2,3\}, \{s,1,2,4\}, \{s,1,3,4\} ,\{s,2,3,4\}, \{s,1,2,3,4\} \}$$ I have proven (in a very brute force manner) that the above cannot have a corresponding graph, so I will not give the proof here.

I am looking for the missing properties, and work that has been done in this area. I apologize in advance if I have not given enough explanation, I have been stuck in this problem too long now to see this clearly. If I should explain more, or give examples, please let me know, and I will.

Edit: Added some cases I didn't want to explain, but realized later I should put in anyway, but they both deals with infinite graphs, and I'm first and foremost after managing the subproblem that is finite graphs.

Answer 1

(Not an answer, but too long for a comment)

One way to look at what you're asking for is a theory in some appropriate language which axiomatizes that we have a serial directed rooted graph, and a collection of subsets of the graph which behaves like $N(\mathcal{G},s)$, where the part of the axiomatization that dictates the behaviour of $N(\mathcal{G},s)$ doesn't say anything about the graph relation on $\mathcal{G}$. I'll give an axiomatization where the part that talks about $N(\mathcal{G},s)$ does mention the graph relation, and I'll set it up in such a way that it'll seem unlikely that it can be redone without mentioning the graph relation. I'm not sure about this, it's just an idea, but it's too long for a comment.

The Language

Consider the language $(\bar{V}, \bar{N}, \bar{E}, \bar{s}, \bar{\epsilon})$ - two unary relation symbols, one binary relation symbol, one constant symbol, and another binary relation symbol, respectively. I'm going to set up a theory whose finite models will be precisely (sort of) those in which $(\bar{V}, \bar{E})$ is interpreted as a directed serial graph $\mathcal{G}$, $\bar{s}$ gets interpreted as a member $s$ of $\bar{V}$, $\bar{N}$ gets interpreted as $N(\mathcal{G},s)$, and $\bar{\epsilon}$ gets interpreted as the membership relation, a subset of $\bar{V} \times \bar{N}$. Setting up the right theory is easy, the only part that will require a little explanation is how we ensure $\bar{N}$ gets interpreted correctly.

Axiomatizing $N(\mathcal{G},s)$ when we're allowed to mention the edge relation

Consider a formula like: $$x_1 = \bar{s} \wedge x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$$ $$\wedge \bar{E}(x_1,x_2) \wedge \bar{E}(x_2,x_1) \wedge \neg \bar{E}(x_1,x_3) \wedge \neg \bar{E}(x_3,x_1) \wedge \neg \bar{E}(x_2,x_3) \wedge \neg \bar{E}(x_3,x_2)$$ It "says" we have three distinct $x_i$, the first one is $s$, and it tells you exactly which pairs stand in edge relation to one another and which don't. You can also tell by looking at it that it defines a set $\{ x_1, x_2, x_3\}$ which contains an infinite path starting at $s$, namely $x_1, x_2, x_1, x_2, \dots$.

Let's define $\mathcal{R}$ to be the set of formulas in the language $(\bar{s}, \bar{E})$ of the form $\phi(x_1, \dots , x_n)$ which say that the $x_i$ are distinct, and which tell you precisely which pairs of the $x_i$ stand in $\bar{E}$ relation to one another, and which don't. Define $\mathcal{R}^+$ to be those formulas $\phi \in \mathcal{R}$ such that for any rooted directed graph $((V,E),s)$, we have that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \in N((V,E),s)$.

$\mathcal{R}^-$ will be those $\phi$ such that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \not\in N((V,E),s)$.

Alright, now here's our theory:

1. (Rooted serial directed graph) $\bar{V}(\bar{s}) \wedge \forall x \bar{V}(x) \rightarrow [\neg \bar{E}(x,x) \wedge \exists y (\bar{V}(y) \wedge \bar{E}(x,y))]$
2. (Schema for what goes in $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^+$: $\forall \vec{x} \exists Y \forall x \left (\phi(\vec{x}) \rightarrow \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$
3. (Schema for what stays out of $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^-$: $\forall \vec{x} \forall Y \exists x \left (\phi(\vec{x}) \rightarrow \neg \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$

Checking this axiomatization works

It's clear that if $\mathcal{G} = (V,E)$ is a finite directed serial graph and $s \in V$, then $(V,N(\mathcal{G},s),E,s,\in)$ is a model of this theory. Conversely, if we have a finite model $(V,N_0,E,s,\epsilon)$ of this theory, then $(V,E)$ forms a directed serial graph with $s \in V$. Now let $N_1$ consist of those $Y \in N_0$ such that $\forall x (x \epsilon Y \rightarrow V(x))$. I claim that:

$N((V,E),s) = \{ \{x : x \epsilon Y\} : Y \in N_1\}$

But I won't prove this.

A remark about some "unnaturalness"

It should seem like I could have done things differently so that things looked more natural and the above claim could be proved more easily. The way I've written 2 and 3 are not the most natural, but I've done it for a reason. 2 says that if $\vec{x}$ is a tuple which is sure to contain an infinite path starting at $s$, then there's a member of $N$ consisting precisely of the members of $\vec{x}$. 3 says that if $\vec{x}$ is sure to not contain an infinite path starting at $x$, then there's nothing in $N$ consisting precisely of the members of $\vec{x}$. The formulas in 2 and 3 are in prenex normal form, where the matrix is a conditional where the left side only involves the symbols $\bar{E}$ and $\bar{s}$, and the right side only $\bar{N}$ and $\bar{\epsilon}$. Moreover, the antecedents have variables $\vec{x}$ and the consequents have variables $\vec{x}, Y, x$.

The point

You want a theory equivalent to axiom 1 and schemas 2 and 3 above, but you want to replace 2 and 3 with (probably finitely many) axioms which don't mention the symbol $\bar{E}$. I feel like there ought to be some interpolation-type theorem (along the lines of Craig Interpolation or Lyndon Interpolation) which says this can't happen, i.e. something which says that a theory in which each axiom mention either only $\bar{V}, \bar{E}, \bar{s}$ or only $\bar{V}, \bar{N}, \bar{s}, \bar{\epsilon}$ can't prove a theory which has axioms like those in schemas 2 or 3.