MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 4 added 194 characters in body

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

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.
show/hide this revision's text 3 added 410 characters in body

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))$$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)?
show/hide this revision's text 2 added 13 characters in body

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a formula 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?
show/hide this revision's text 1