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.

  • 3
    $\begingroup$ Representation theory is not the "theory of representing concrete theories". I also fail to see any reason whatsoever for the incompleteness theorem to be a "representation theorem", if anything it is the complete opposite. It tells us that under some constraints there is no concrete model. $\endgroup$ – Asaf Karagila Feb 15 '12 at 10:22
  • $\begingroup$ Please help me to fix the misunderstandings: a) I used the term "representation theory" only in the tag, else I talked about representation theorems. b) I asked about the completeness theorem (sic!), not about the in completeness theorem. $\endgroup$ – Hans-Peter Stricker Feb 15 '12 at 10:27
  • $\begingroup$ As for (a) my point was exactly aimed to the tag. Much like [logic] does not apply for everything which requires "a logical thinking" and [set-theory] has nothing to do with just any questions with sets. As for (b)... I guess that is what happens when you're hungover. However the point remains, the completeness theorem just connects syntax and semantics - it does not imply anything is isomorphic to another. $\endgroup$ – Asaf Karagila Feb 15 '12 at 10:36
  • $\begingroup$ As for (a): I see your point, but I want to leave the tag, since there is no tag for "rep. theorems", and there is - presumably - a connection between "rep. theory" and "rep. theorem". As for (b): Maybe you are right, but for me it's discussion-worthy whether the compl. theorem really just connects syntax and semantics and whether it really does not imply anything about one thing being isomorphic to another. $\endgroup$ – Hans-Peter Stricker Feb 15 '12 at 10:43
  • 1
    $\begingroup$ There is no direct connection between representation theory and representation theorems; this is why I approved the edit deleting the tag from the question. $\endgroup$ – anon Feb 15 '12 at 11:13

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.

  • $\begingroup$ Thank you! I definitely was not aware of the fact that Gödel's CT was equivalent to Stone's RT. Is this commonly known (and easy to proof), or do you have a reference? The second part of your answer I understand better. Should I restrict my question to categorical theories? $\endgroup$ – Hans-Peter Stricker Feb 15 '12 at 10:56
  • $\begingroup$ How crucial is "arbitrary cardinality" and "absence of AC"? $\endgroup$ – Hans-Peter Stricker Feb 15 '12 at 11:04
  • $\begingroup$ I guess it is known to many logicians. A book that makes the connection very clear is "Models and Ultraproducts" by Bell and Slomson. The "Handbook of Analysis and its Foundations" contains the proof too, and so does "The Axiom of Choice" by Jech. The relation to logic is, very roughly, that a theory can be seen as a family of sets of sentences closed under subsets and fpairwise union. If it is consistent, it doesn't contain the set of all sentences. Together, this means that a consistent theory is an ideal. Now a maximal consistent family is therefore a prime ideal. $\endgroup$ – Michael Greinecker Feb 15 '12 at 11:10
  • $\begingroup$ For countable theories, the completeness theorem is provably in ZF. Essentially, you can list all propositions and inductively decide wheter the should be assigned the value true or false. $\endgroup$ – Michael Greinecker Feb 15 '12 at 11:13
  • $\begingroup$ Thanks. This is really helpful. (Referring to: "I guess it is known...") $\endgroup$ – Hans-Peter Stricker Feb 15 '12 at 11:13

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.