[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?

semantics? $\endgroup$ – Andrés E. Caicedo Jan 9 '11 at 0:04