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.
Best Answer
(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:
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.