2
$\begingroup$

In general a representation theorem is — according to Wikipedia — a "theorem that states that every abstract structure with certain properties is isomorphic to a concrete structure". Wikipedia gives a list of canonical examples.

[Side remark: Interesting enough, the only genuinely set theoretical example (Mostowski's collapsing theorem) is filed under "category theory", and Dedekind's lemma which is fairly easy to grasp is missing in this list.]

I'd like to ask:

Can Gödel's completeness theorem be considered a representation theorem?

I dare to ask because

  1. Consistent logical formulae (or sets of, ie. theories) can be considered as (descriptions of) abstract structures
  2. The (set theoretical) models of such formulae (resp. theories) are concrete structures.

One important difference between Gödel's incompleteness theorem and some of the representation theorems listed at Wikipedia is, that not only in it's proofs (known to me) the concrete structures don't "come free with" the abstract structures — as most easily seen in the Dedekind case of posets — but that the proofs are non-constructive at all.

So I'd like to flank my question:

Is the Wikipedia "definition" of the notion of a representation theorem adequate or would practicing representation theorists refine it, e.g. to exclude "non-constructive" theorems.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2521/discussion-between-hans-stricker-and-anon)2012-02-16

1 Answers 1

6

The completeness theorem of Gödel for languages of arbitrary cadinality is, in the absence of the axiom of choice, equivalent to a well know representation theorem, the Stone representation theorem that says (among other things) that every Boolean algebra is isomorphic to an algebra of sets and this is in turn equivalent to a highly nonconstructive choice principle, the Boolean prime ideal theorem. So representation theorems do not have to be constructive.

But the completeness theorem is not a representation theorem because the model one creates (if "construct" sounds too constructive for your taste) is not isomorphic to the theory. It is in some sense an extension theorem that says, informally, that any consistent description can be extended to a complete description of everything. Since the initial description is not complete, we can complete it in several ways.

  • 0
    @Hans Stricker: Let $T$ be a consistent theory. Then a model of $T$ can be "constructed" from syntactic elements. Key words are the introduction of *Skolem functions*.2012-02-15