Recursive definition of predecessor vertices in a graph

Question

In an directed acyclic graph $G = (V,E)$, how can I define a set $P_v \in V$ that includes a given vertex $v$ and all its direct and indirect predecessors?

I would define the direct predecessors $P^d_v = \{u \mid (u,v) \in E\} \cup \{v\}$, but I can't work out how to define it in this way to include all of the indirect predecessors as well (i.e., all predecessors of $u$ and then all predecessors of those predecessors of $u$, etc). My intuition is that I would have to use some sort of recursive definition, and I can write an algorithm for it, but I can't work out how to write it using set-builder notation.

EDIT:

Can I say something like this?

Starting with $P_v = \{v\}$, the set of predecessors can be constructed recursively in the following way:

$P_v = P_v \cup \{ b \mid (b,a) \in E, \forall a \in P_v\}$

does that make sense?

Answer 1

$P_v$ can be defined as the intersection of all "pred-closed" sets that contain $v$ where I call a set $A \subseteq V$ pred-closed, iff

$$\forall x \in A: (y,x) \in E \to y \in A\tag{p}$$ i.e. a set closed under the predecessor relationship.

So a simple lemma shows that any intersection of pred-closed sets is pred-closed.

And $V$ itself is trivially pred-closed.

So $P_v= \bigcap\{A \subseteq V: A \text{ pred-closed and } v \in A\}$ is well-defined and is pred-closed (and minimally so).

This is a common idea to avoid recursion (although there is nothing wrong with recursion per se, and it also doesn't imply an "algorithm" requirement...) and IMHO quite elegant. You can show that Elliot's set gives the same set in a DAG.

Answer 2

$$P = \{v\} \cup \{ p : \exists n \in \Bbb N: \exists v_1, v_2,\ldots v_n \in V: v_1=p, v_n=v \land \forall i \le n-1: (v_i, v_{i+1}) \in E \}$$ is one way to put it.