There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):

Can a class of objects or structures of a given kind X that is characterized by some "external condition" Y be defined by a condition Z in their respective "internal" language, and if so: how?

Well-known examples ("external condition" = "internal condition"):

  1. groups $G$ isomorphic to a subgroup of the symmetric group on $G$ = all groups (Cayley's theorem)

  2. graphs embeddable in the plane = graphs not containing a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski's theorem)

  3. numbers n of trees on k labeled vertices = numbers n = kk-2 for some k > 1 (Cayley's theorem on trees)

  4. numbers n with only one group of order n = numbers n = p1 · p2 · ... · pk for some k > 0, where the pi are distinct primes and no pj-1 is divisible by any pi (cyclic numbers, see Sloane's A003277)

Further examples from MO:

Question #1: What's the proper way to characterize this pattern of questions? What's the common context / rationale?

Question #2: How is the introductory question to be posed properly?

  • 4
    $\begingroup$ This is much too meta for MO. $\endgroup$ – Harry Gindi Feb 16 '10 at 1:28
  • 5
    $\begingroup$ I think this is way too philosophical and discussion-y to work on MO. Though you have made an admirable attempt at putting it in the form of a question, I don't think it's a question that "has an answer" (i.e. it's really bait for a discussion). I'd vote to close it as "not a real question", but I don't want to close unilaterally. If it acquires two or three other votes to close, then I'll vote to close too. $\endgroup$ – Anton Geraschenko Feb 16 '10 at 3:16
  • 3
    $\begingroup$ @Anton: Considering I just gave a reasonable answer. Would you consider not closing if I promise not to discuss the matter further? $\endgroup$ – François G. Dorais Feb 16 '10 at 3:20
  • $\begingroup$ @FGD: You know that your answer can still be voted up if the question is closed. The only thing closing a question does is make it so other people can't answer it. $\endgroup$ – Harry Gindi Feb 16 '10 at 3:26
  • $\begingroup$ @fpqc: I did not know that. Thanks! $\endgroup$ – François G. Dorais Feb 16 '10 at 3:29

There are three sibling theorems of logic which guarantee that such characterizations are bound to happen.

[The wikipedia entries need some work. I suggest you look up these theorems in a good logic book, for example Hodges's Model Theory or his more accessible Shorter Model Theory.]

I will focus on the Beth Definability Theorem, though the other two siblings lead to similar conclusions in slightly different contexts.

Suppose you have a first-order language L0 and a larger language L. Let T be a theory in L and let φ(x) be a formula of the larger language L with the following property. Whenever A1 and A2 are two models of T which have the same universe A and the same interpretation for all parts of the small language L0, then A1 ⊧ φ(a) iff A2 ⊧ φ(a) for all a ∈ A. Beth's Definability Theorem says that there must be a formula φ0(x) of the smaller language L0 such that T ⊦ ∀x(φ(x) ↔ φ0(x)).

The connection with your question is as follows. The base language L0 is the 'internal' language of the structures you really care about, while the larger language L has some additional 'external' data. The theory T characterizes the structures with external data that you care about, and φ(x) is a property of such structures that you are interested in. If φ(x) is sufficiently independent of the external data, then φ(x) must be equivalent to an internal formula φ0(x).

Not all of the examples you give are easily cast into this formalism, but the basic flavor is the same. Unfortunately, the Beth Definability Theorem (and its proof) does not say much on how to find the internal formula φ0(x) but, at least, it says that the search will not be in vain.

  • $\begingroup$ Hm... Are any of the examples from the question easily cast into this formalism? $\endgroup$ – Sridhar Ramesh Feb 16 '10 at 5:38
  • $\begingroup$ 1 & 3 are pretty straightforward. (Though not very interesting.) $\endgroup$ – François G. Dorais Feb 16 '10 at 6:02
  • $\begingroup$ Oh, I see now that 1 says "isomorphic to a subgroup of the symmetric group on G" and not just "isomorphic to a subgroup of some symmetric group". I can see how to cast that first one into this formalism. But I couldn't see how to cast the latter. $\endgroup$ – Sridhar Ramesh Feb 16 '10 at 6:10
  • $\begingroup$ No, wait, actually, I can't see how to cast the first one into this formalism; what I was thinking of doing doesn't work quite right. Could you perhaps illustrate exactly what T, L, phi, and phi_0 should be? $\endgroup$ – Sridhar Ramesh Feb 16 '10 at 6:15
  • $\begingroup$ I had misread 3 when I wrote the above comment. However, 3 & 4 are trivially realized by taking L to be a suitable extension of arithmetic, but then the result is utterly trivial. $\endgroup$ – François G. Dorais Feb 16 '10 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.