Given a finite directed, possibly cyclic, graph $G=(E,V)$, I want to define set $X$ as the set of vertices $v$ that 1) satisfy $p(v)$ and 2) there exists a path to a vertex $w$ satisfying $q(w)$, such that all vertices on the path satisfy $p$.
I tried to define this recursively:
$X = \{v | p(v) \wedge \exists w:(v,w)\in E \wedge(w\in X \vee q(w) \}$
The problem is that this does not work with cycles, because a cycle could be both in and not-in the set, according to the definition.
How can I change the definition to be cycle-proof?
I don't exactly see what issues your definition has with cycles, but I am wary of the fact that the set definition refers to the set itself. In general this is dangerous and should be avoided to avoid some of the bigger problems in naïve set theory.
Here I will present an alternative, longer-winded definition that I think does the same thing.
Let $Q=\{w\mid q(w)\}$ denote the set of vertices that have property q. Now, let $$ X_1=Q\cup\{v\mid p(v)\text{ and there exists } w\in Q\text{ with }(v,w)\in E\}. $$ Now we can recursively define $$ X_i=X_{i-1}\cup\{v\mid p(v)\text{ and there exists } u\in X_{i-1}\text{ with }(v,u)\in E\}. $$
Then if the diameter of the graph is $d$, $X_d$ will be the desired set. If there is a cycle in your graph, this shouldn't be an issue.