1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 9, 2011 at 0:04
  • $\begingroup$ 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? $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 9, 2011 at 0:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – gowers
    Commented Jan 9, 2011 at 8:44
  • $\begingroup$ @Timothy: Why not? What you describe is just a richer language, allowing to define properties that depend on real-valued parameters. $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 9, 2011 at 11:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – gowers
    Commented Jan 9, 2011 at 16:44

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ In this case, I would be more than happy to learn how to bypass this triviality (which I surely didn't intend). $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 9, 2011 at 1:37
  • $\begingroup$ 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? $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 9, 2011 at 1:44
  • $\begingroup$ The bound property, which I have now named. $\endgroup$
    – user5810
    Commented Jan 9, 2011 at 2:03
  • $\begingroup$ OK, now I see clearer. $\endgroup$
    – Hans-Peter Stricker
    Commented Jan 9, 2011 at 2:10
  • $\begingroup$ 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. $\endgroup$
    – user5810
    Commented Jan 9, 2011 at 2:11
3
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Some take it as part of the definition of "graph property". $\endgroup$
    – Yuval Filmus
    Commented Jan 9, 2011 at 4:44
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .