Return to Answer

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))\ \ \ \(**)$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

ADDED: Assume we define $Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$ where the $\phi_i(x)$ use the symbol $R$. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to $(**)$.

How do I have to think about this (kind of circular or impredicative definition)?

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))\ \ \ \(**)$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

ADDENDUM 1: Assume we define $Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$ where the $\phi_i(x)$ use the symbol $R$. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to $(**)$.

How do I have to think about this (kind of circular or impredicative definition)?

ADDENDUM 2: The "solutions" of the informal and sketchy "equation"

$$Rxy \equiv \neg(\exists x_1)...(\exists x_n) Rxx_1 \wedge ... \wedge Rx_ny$$

are exactly the trees.

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property () $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert () and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))\ \ \ \(**)$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

ADDED: Assume we define $Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$ where the $\phi_i(x)$ use the symbol $R$. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to $(**)$.

How do I have to think about this (kind of circular or impredicative definition)?

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a formula () $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert () and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property () $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert () and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?