# Graph properties: definability and decidability

[This is a side question to Supervenience in mathematics.]

There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not MSO-, TC-, or LFP-definable, but maybe in another, even more expressive language.

To claim that a graph property is not definable at all, would mean, that there is no language (in the class of all languages) in which it is definable. But what is this class of all languages? Is it definable?

One doesn't have to be bothered by undefinable properties, because "whereof one cannot speak, thereof one must be silent" (Wittgenstein). But alas, there's an alternate way of defining graph properties: by Turing machines.

One might try to identify the set of graph properties with the set of (equivalence classes of) Turing machines which take adjacency matrices as input, eventually halt, and give 0 or 1 as output, giving the same output for "isomorphic" matrices.

This set of properties isn't decidable (because of the halting property), but it's definable.

Does it make sense to ask, whether there are graph properties (as Turing machines) that are not definable in any conceivable (logical) language?

-
What requirements do you ask of a language? Does it need to have a countable vocabulary? Is its syntax recursive? What requirements do you ask of its semantics? – Andrés Caicedo Jan 9 '11 at 0:04
Good questions. Is there any chance to have a complete list of them, each with a definite list of answers, thus specifying all conceivable languages? – Hans Stricker Jan 9 '11 at 0:07
Is this really a question about graphs? For instance, take the property "has edge-density at most p". This will be definable if and only if the real number p is (between 0 and 1 and) definable. – gowers Jan 9 '11 at 8:44
@Timothy: Why not? What you describe is just a richer language, allowing to define properties that depend on real-valued parameters. – Hans Stricker Jan 9 '11 at 11:43
What is your definition of "graph property"? The one I'm familiar with is "subset of the set of all graphs that's isomorphism invariant" (and here I'm talking about finite graphs). If the real number p isn't definable, then neither is the graph property "has edge-density at most p". It's definable in terms of p, but p isn't definable so that doesn't help much. – gowers Jan 9 '11 at 16:44

Yes, but it's trivial.

For all graph properties prop, with p(.) defined by p(g) if and only if g has property prop, prop is definable in FO+p.

-
In this case, I would be more than happy to learn how to bypass this triviality (which I surely didn't intend). – Hans Stricker Jan 9 '11 at 1:37
But first of all I want to understand your argument better: which property is your p(.) supposed to denote? You write "p(g) iff g has the property" - but WHICH property? – Hans Stricker Jan 9 '11 at 1:44
The bound property, which I have now named. – Ricky Demer Jan 9 '11 at 2:03
OK, now I see clearer. – Hans Stricker Jan 9 '11 at 2:10
The only ways I could think of to bypass this triviality would trivially make it equivalent to whether the property is definable in a particular language. – Ricky Demer Jan 9 '11 at 2:11

Almost any language I can think of (FO theories, etc) isinvariant under isomorphism, i.e. if $\cal A$ satisfies the sentence $\sigma$ then so does $h(\cal A)$ for any isomorphism $h$. Hence if a class of graphs is not closed under isomorphism, it will not be definable in any conceivable language.

(Of course, such classes of graphs would not be very interesting).

-
Some take it as part of the definition of "graph property". – Yuval Filmus Jan 9 '11 at 4:44

I, like gowers in the comments, don't think it is a question which have anything to do with graphs in particular, as soon as you define graph property to be something recognizable by a Turing machine.

Indeed you can enumerate graphs by natural numbers (for example by enumerating the possible adjacency matrices) Then the set of graphs having a given property in your sense is precisely a recursive set of natural numbers.

Now, for every recursively enumerable set A of natural numbers there exists a polynomial p such that $$x \in A \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0),$$ which, afaiu, is a kind of a definition in a logical language you're after.

-