How can we define a relation $\in^*$ inductively such that it looks deep inside sets?

Question

My task is this:

We can't look "deep" inside sets with $\in$. How can a relation $\in^*$ be defined s.t. $x\in^*\{y,\{x\}\}$ and $x\in^*\{\{\{\{x\}\}\}\}$?

Any help or explanation will be more than welcome.

Answer 1

Well, if you're okay with an inductive definition, it's pretty straightforward: say $x \in^* y$ iff either $x \in y$ or there is a $z \in y$ so that $x \in^* z$.

This definition looks circular, but by the well-foundedness of sets it's fine - the only way you could get into an infinite regression would be to have a sequence $\cdots \in x_k \in x_{k - 1} \in \cdots \in x_2 \in x_1 \in x_0 \in y$ that you have to check. But no sequence like that exists, so there's always a "bottom" layer to check.

If you want a closed-form solution (that is, a single expression) then the best solution I can give is the one Crostul gave in the comments; $a \in^* b$ $a \in b$ or there exists a whole number $k$ and a collection $a_1 \in a_2 \in \cdots \in a_k \in b$ so that $a \in a_1$. That's not very satisfying, though, personally.