Talk:Model theory

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Start Class

Mid Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
See comment below on talk page

[edit] History, sources?

I'd expect an encyclopedia to give more about the history of model theory. Shouldn't seminal works by Tarski be among the references, at least? He's hardly mentioned. DanConnolly 18:21, 26 June 2007 (UTC)

[edit] comment of Logicnazi

Is not the last sentence of the first paragraph (i.e. what can be proven given a set of axioms) closer to proof theory?

Ughh, the completness part at least needs some work. What it means for a theory to be complete is quite differnt from the completness theorem. Logicnazi 12:11, 27 Aug 2004 (UTC)

Also the statement about a theory being maximally consistant set of sentences is just wrong. Only complete theories are maximal consistant set of sentences, e.g. the theory consisting of only pure truths of predicate calculus is closed under implication but hardly maximal (otherwise we could never add axioms!!) Logicnazi 12:13, 27 Aug 2004 (UTC)

Just so no one tries to re-add the statement it is simply NOT TRUE that a complete theory fully specifies a model. The Low-Skol theorems easily prove that complete theories will have models of differnt cardinalities. Logicnazi

[edit] Maximal consistent set

Anyone fancy creating this node and providing the necessary discussion here? I'm creating a link from Consistency proof, but I have more than enough to do around proof theory. If not, I'll get around to it eventually... ---- Charles Stewart 07:48, 22 Sep 2004 (UTC)

[edit] Category theory

Can someone add words that clarify the distinction between model theory and category theory? Is model theory supposed to be a broadened, extended, generalized category theory? Or was historically inspired by category theory, while ditching the weighty baggage of the concept of "class" and the cardinality of class? linas 16:04, 12 Mar 2005 (UTC)

I don't think they are related. MarSch 17:04, 19 Apr 2005 (UTC)

Category theory is more general than model theory. A topos, which is a type of category, can be understood as a model of a set theory or a logic. Archelon 00:56, 11 Jun 2005 (UTC)

See Intuitionistic_type_theory, specifically the section titled Categorical models of Type Theory. Perhaps something regarding the relation to topos theory merits inclusion in the article? Marc Harper 02:49, 6 December 2005 (UTC)

[edit] models of set theories

What is meant by "a model of a set theory"? Does it mean that you try to make a model in one set theory of the other set theory? MarSch 17:20, 19 Apr 2005 (UTC)

Yes. For example, countable models of set theory exist; that is, models of set theory with only a countable universe. Such models "think" they have uncountable sets, but since the underlying universe is countable in that case, they don't. Things like this can be confusing at first. - Gauge 04:54, 29 October 2005 (UTC)

[edit] Very confused!

If "a theory is defined as a set of sentences which is consistent", then "a theory has a model if and only if it is consistent" seems very confusing. By way of illustration, "a 'set of sentences which is consistent' has a model iff it is consistent", looks very much like tautology to me. The irony of that appearing in this article is not lost on me, but this article needs a more precise and expository rewrite.

The theory of an L-structure A over a language L is defined to be the set of L-formulae that are satisfied by A. In contrast, a theory over a language L is a set of sentences that is closed under deduction. Given a set of sentences S, you can close it up to get the theory of S, denoted Th(S). This is the smallest set of sentences containing S that is closed under deduction. Consistency is not required of a theory in order for it to be a theory, but it will only have a model if it is consistent. - Gauge 04:54, 29 October 2005 (UTC)

[edit] To Do List

I removed this "to do" list from the article, so I'm sticking it here.

TODO - Vaught's test. Extensions, Embeddings and Diagrams. To give a flavor, mentioning the hyperreals and/or the extension of the concepts of basis and dimension to strongly minimal theories would be good. (All of these need substantial filling out)

Josh Cherry 04:15, 21 Jun 2005 (UTC)

[edit] Definition of model theory

I don't think this article gives a very good sense, currently, of what model theory is. The way I would put it is, in most of mathematics you specify a structure and try to discover its theory (that is, what statements are true in the structure). In model theory, you turn this around: You specify the theory (the set of, usually, first-order statements) and look for properties of structures that satisfy it. Model theory, in other words, lives in the gap between elementary equivalence and isomorphism. The intro to Category:Model theory needs similar attention.

There seems to be a serious lack of articles on even the basic concepts of model theory (types, saturation, omitting types, homogeneity). Compactness at least exists on WP. --Trovatore 23:56, 26 November 2005 (UTC)

Actually, there is a saturated model article. I've added a bunch of the rest to Wikipedia:Requested articles/mathematics. --Trovatore 00:07, 27 November 2005 (UTC)

[edit] Infinitesimals

Might we discuss briefly (and provide links) how infinitesimals and nonstandard analysis can be developed from model theory? Or is it discussed somewhere, and I missed it? Thanks. MathStatWoman 18:04, 22 January 2006 (UTC)

p.s. ok, found link to hyperreals. MathStatWoman 18:07, 22 January 2006 (UTC)

[edit] Logical Constant

JA: The way I read it, constant means a symbol with a (relatively) fixed logical interpretation, that is, a logical constant like "and", "or", etc. So maybe some clarification of that is called for. Jon Awbrey 17:30, 6 August 2006 (UTC)

I don't recall hearing "logical constant" with that meaning (I would think a logical constant would be "true" or "false", or possibly a name for some other truth value in a multivalued logic). Where have you encountered this meaning? Do you have a ref? --Trovatore 20:19, 6 August 2006 (UTC)

JA: I'm not saying that it's my favorite usage, but it's pretty standard. Don't know who started talking that way — the distinction is already clear in Frege and Peano, but the vagaries of translation may smudge it there. Pretty sure that it's in Whitehead and Russell somewhere, as Gödel is basically just gistifying "the system obtained by superimposing on the Peano axioms the logic of PM" when he writes the following:

The basic signs of the system P are the following:

I. Constants: "~" (not), "∨" (or), "Π" (for all), "0" (nought), "f" (the successor of), "(", ")" (brackets). ... (Gödel 1931/1992, p. 42).

Kurt Gödel (1931), "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", B. Meltzer (trans.), R.B. Braithwaite (intro.), Basic Books, New York, NY, 1962. Reprinted, Dover Publications, Mineola, NY, 1992.

JA: Jon Awbrey 21:32, 6 August 2006 (UTC)

Wow. Well, that's a reference, for sure. I don't think it's used much these days, though. I suspect the terminology most used these days is due to Tarski rather than those earlier workers, but I don't know that for sure. --Trovatore 04:12, 7 August 2006 (UTC)

JA: I'm pretty sure that Tarski, Quine, etc. all use the term that way, though Tarski somewhat famously commented that he thought the distinction between logical signs and extralogical signs might be arbitrary and thus a parameter of the formal system chosen. But if it's not clear then it needs to be explained somewhere. Jon Awbrey 04:26, 7 August 2006 (UTC)

Logical sign sounds a good deal different from logical constant. I really would be pretty surprised if he used the precise term "logical constant" that way, assuming (as I think) he was the one who introduced the now-standard notions of non-logical symbols consisting of constant symbols, function symbols, and relation symbols. But I haven't read any of his original work, that I recall, so I'm certainly willing to be proved wrong. --Trovatore 04:49, 7 August 2006 (UTC)

JA: For example:

Among the signs comprising the expressions of this language I distinguish two kinds, constants and variables. I introduce only four constants: the negation sign 'N', the sign of logical sum (disjunction) 'A', the universal quantifier 'Π', and finally the inclusion sign 'I'. (Tarski, 1935/1983, p. 168).

Tarski, A. (1935), "Der Wahrheitsbegriff in den formalisierten Sprachen", Studia Philosophica 1, pp. 261–405. Translated as "The Concept of Truth in Formalized Languages", in Tarksi (1983), pp. 152–278.

Tarski, A. (1983), Logic, Semantics, Metamathematics: Papers from 1923 to 1938, J.H. Woodger (trans.), Oxford University Press, Oxford, UK, 1956. 2nd edition, John Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.

JA: Jon Awbrey 05:40, 7 August 2006 (UTC)

[edit] Article rating

The article is somewhat short, and could mention important ideas such as types, quantifier elimination, etc. These could be in summary style. There is no discussion of the history of the subject or of the current trends. The discussion on Godel's incompleteness theorem seems a little out of place here; a one-sentence clarification might be enough. CMummert 14:29, 25 October 2006 (UTC)

I'd go even further. The lead section is extremely misleading and does not at all reflect the content of what is ordinarily called "model theory". The two independence results given as examples (AC and CH) are ordinarily considered part of set theory, not model theory, though they use some elementary model-theoretic techniques. The lead needs a complete rewrite, preferably with input by a real live model theorist if we can find one. Are there any on WP? --Trovatore 15:52, 25 October 2006 (UTC)

The problem with rating these articles is that there is no grade between Start and B-class but many articles are in between the standards for them. I agree that this article is barely a B-class article, and that it needs significant work before it can be regraded as B+ or A class. After reading the rating gudelines again, I changed the rating to Start-class.

I also noticed the second para in the lead section, but I decided it was OK because it only claims that those are the "most famous results", which is probably correct because model theory is not well known outside of mathematical logic. If the rest of the article were stronger, that paragraph in the lead might help a lay reader to get into the spirit of the main article. CMummert 16:02, 25 October 2006 (UTC)

[edit] Shellgirl's recent edits

I have a few concerns about some of these additions. I will be very brief for now because I'm supposed to be working, but I didn't want her to do a lot of work that might be disputed later. So here is a short list; I'll look in more detail later.

The claim that model theory is based on the axiomatic method. This is not necessarily so; it can be treated as formally or informally as any other area of mathematics.
The identification of the Gödel incompleteness theorems as part of model theory. They are more typically thought of as proof theory or recursion theory, though certainly they have model-theoretic implications. --Trovatore 00:10, 6 April 2007 (UTC)

Jessica responds Hi!

First point. Although I am fond of the phrase "axiomatic method" (I think because I saw a talk given by Udi Hrushovski where he justified the new geometric tilt to model theory by saying something like, the axiomatic method and geometry have been interacting usefully since Euclid ) I understand your concern: I certainly don't want people to get the impression that model theory involves reams of formally correct first order proofs.

Second point. I agree. As much as I love and adore Gödel, and although I do consider his work with the constructible universe to be the work of a model theorist, his big results are clearly of most interest for foundations of math, set theory, proof theory, computability theory, and computer science (especially with the twist involving Kolmogorov complexity). Okay, the completeness theorem is arguably the most important theorem of model theory. But somehow it pales in comparison to the incompleteness theorem and the work on L. In my defense, I wasn't the one who put the incompleteness theorem in the first paragraph, I just reworded it.

Please let me know what you think of the new additions. I plan to make model theory an A class article. But it'll take a couple years and/or a bunch of model theorists jumping on board, especially since a lot of the work will involve making other pages.

Shellgirl 04:49, 6 April 2007 (UTC)

So first of all I want to say I'm delighted that someone who actually specializes in model theory is finally taking a look at this article. I'll just give some impressions in no particular order:

The lede is far too dense and technical. Wikipedia lede sections are supposed to summarize the whole article, but be accessible to as wide an audience as the subject matter permits. All of that information should go in the article, but most of it further down; at the top level we want to synthesize the content and give as broad an audience as possible (that would probably be professional mathematicians in general, for this sort of article) an idea of why it's important.
Really, you think the work on L is model theory? To me it's set theory. Of course the borderlines are fuzzy, but there isn't too much in Gödel's work on L that involves, say, types, which I've always thought of as more or less the defining feature of model theory.
I still don't really get how the axiomatic method is relevant. You could look at the model theory of models of some non-axiomatizable theory; say, true arithmetic. From my outsider's perspective, very roughly, if you fix the theory (even a non-axiomatizable one) and vary the models, then you're doing model theory, whereas if you fix a (set or class) model of set theory (to be, say, the complete V, or L, or L(R) ) and try to figure out its theory, then you're doing set theory. Does that sound like a reasonable rough demarcation to you?
Can't comment on the "geometric tilt"; I'm completely ignorant on that score.

But to sum up, great to have you on board! We can really use your help; I don't think there's a model theorist per se editing regularly. It would be useful for you to get familiar with the "house style", which is informally but fairly strictly adhered to. There are official manuals at WP:MOS and WP:MSM that you should at least scan, and other conventions that maybe aren't written down in a single place, but sometimes discussed at Wikipedia talk:WikiProject Mathematics. You might also like to add yourself to Wikipedia:WikiProject Mathematics/Participants. --Trovatore 07:03, 6 April 2007 (UTC)

I agree with you about the first paragraph. I'll take your advice about learning more about the house style, as well as basic social graces on wikipedia. Now that I've "been bold" I'll try to integrate myself.

I view skolemization as a method of model theory -- it is similar to Henkin's proof of the completeness theorem, which builds the model out of the syntax. Also, the Mostovski collapse is a model theoretic technique. As you say, the distinction is fuzzy. Also, I would prefer to leave a distinction like this to a working set theorist.
I'm off playing ultimate frisbee for the weekend. More changes next week.

Jessica Millar 12:23, 6 April 2007 (UTC)

[edit] underconstruction

I removed (commented out actually) the underconstruction template as I cannot see any edits to the article since 2 May 2007. Zero sharp 14:26, 9 May 2007 (UTC)

butbutbut... please restore it if you are actually, actively working on the article -- which I think is a fine idea! Zero sharp 14:32, 9 May 2007 (UTC)

I am working on it when I have time. There is lots of good stuff here, but the organisation needs a lot of work. I would be interested in comments about the organisation, because I think it is not right at the moment, but have not got a clear idea yet on what would be good. I see the following as a possibiility:

Initial motivation: elementary and pseudo elementary classes, decidability, QE, foundational issues: compactness and LS-theorems
Then maybe the basics of the classical theory: robinsons ideas, diagrammes, model completeness EF games, Horn sentences, definable sets and types and so on.
Imaginaries and interpretations.
Model theoretic constructions: omitting types theorem, Fraisse, ultraproducts, saturated, big, homogeneous structures, prime models. Hrushovskis construction.
Morleys theorem, Shelahs clasification theory and on to geometric stability theory.
o-minimality and related (definable completeness, weak o-minimality, d-minimality, thorn independence
recent important results and programmes (relating to each secion: eg. decidability of R_exp, some recent "pure model theory", valued fields - stable domination, maybe put Hrushovskis construction and the new Zilber analytic structures here, groups of finite morely rank, the implications for real geometry of o-minimality.

As regards computable model theory, I know nothing about it. I would be interested to know some more. As it regards this page, it is really close enough to the rest of (infinite, first order finitary) model theory, to warrent a section here? I look forward to your comments. Thehalfone 12:40, 22 June 2007 (UTC)

excellent! I worry a bit about leaving the article with empty sections... I guess at the least we could put whatever the appropriate stub/expand template is. I myself, just an amateur/layman/dilletante am very interested in Model Theory and would love to contribute to the article any way I can. Thanks Zero sharp 14:39, 22 June 2007 (UTC)

Hi Thehalfone,

The program above looks great, but not achievable in a single article, certainly not in the central article for a whole subject. What I would do in this article is try to give the basic thrust of what model theory does and hopes to accomplish, at a relatively high level. The central notions that need to be treated, I'd say, are those of model, isomorphism, elementary equivalence (and especially the fact that this is not the same as isomorphism), and types.

Then most of the above concepts should be farmed out to other articles where they can be treated in more detail. You might have roughly one subsection of the main article, per bullet point in your program above, where you mumble some generalities and point the reader to the detailed articles on the subject. This is what I've tried to do in the determinacy article; you might look at that and see what aspects of the organizational structure you think mught work here (leaving out, of course, those you think wouldn't be so good). --Trovatore 22:03, 22 June 2007 (UTC)

[edit] A couple of grammatical questions

pseudo elementary class or pseudo-elementary class?

the latter according to Hodges

non logical symbols or non-logical symbols?

I suppose the latter to be consistent

"any binary functions" or "binary functions"?

Theorys or Theories?

again the latter according to Hodges. I guess it was my edit that had all these problems. I will change it now.

Being a noob on Model theory, I don't want to make edits without getting a second opinion. 84.184.251.34 18:39, 26 June 2007 (UTC)

Thanks! Thehalfone 10:00, 27 June 2007 (UTC)

[edit] Pseudo-elementary -> elementary

The article defined "pseudo-elementary" classes as what is usually (Hodges, Chang-Keisler) called "elementary" classes. I corrected this and added a link to the relevant article, which, by the way, originally had a ~~wrong~~ non-optimal definition of elementary classes (requiring axiomatisability by a single sentence rather than a theory). Since Wikipedia has for some time been the number 1 source for (incorrect) information on pseudo-elementary classes on the web I have also covered them in the elementary classes article. If anybody has issues with the changes, please don't hesitate to contact me. --Hans Adler 16:19/20:01, 12 November 2007 (UTC)

[edit] Removed paragraph from introduction

I have removed the following paragraph below from the introduction. After my changes to the first paragraph it became a non sequitur, and anyway a bullet list of abstract examples is perhaps not ideal for an introduction.

For example:

One can classify structures depending on which sentences are true in them. This is generally a coarser classification than isomorphism classes.
One can classify sets of sentences depending on properties of classes of structures which satisfy them.
One has methods for finding or constructing structures satisfying a given set of sentences.
Given a structure, one can consider the sets definable within it via logical formulas. One can ask whether these sets have a "good" geometry.

--Hans Adler (talk) 14:38, 17 November 2007 (UTC)

[edit] Draft of a rewritten article

To address the obvious structural problems with this article as well as the question of duplication between the main article and those to which it refers, I came up with the following plan:

Give a quick overview of everything that is important in model theory.
Whereever possible define necessary notions intuitively by giving an example of their use rather than a definition. (Subarticles will invariably have more detail. With this approach we can actually profit from this.)
Organize by subfields rather than by methods, notions and theorems. Comparison between subfields can be done here better than anywhere else.
In spite of 3., tell a linear story.

I have tried it out in userspace, and it seems to work surprisingly well. Please have a look at my current (still very incomplete) draft here and comment on its talk page, or even better start editing in the draft if you like. --Hans Adler (talk) 15:49, 20 November 2007 (UTC)

I have now restructured the article and added my new sections (to avoid a longer fork in userspace). Some older material became redundant, since many notions are now defined in the sections on universal algebra, finite model theory and first-order logic. I have also removed many empty sections. I am going to write a section on classical model theory that will contain a large part of what is now in "Other notions". After that I will probably start with what I am really interested in (classification theory / stability theory). --Hans Adler (talk) 22:30, 28 November 2007 (UTC)

[edit] Defining Model Theory

As a model theorist, I'm still not quite satisfied with the opening paragraphs (though they're a lot better than they used to be). I think mainly I'd like to see more acknowledgement of the central role of the study of definable sets in contemporary model theory, to the extent that many researchers who call themselves model theorists spend more time thinking about categories of definable sets rather than classes of models.

As for how to define "model theory," the best one-sentence answer I've seen is from Hodges' Shorter Model Theory: "Model theory is about the classification of mathematical structures, maps, and sets by means of logical formulas." (Though I realize that strictly speaking this does not include some of the current research on abstract elementary classes.) I think this is a lot more informative than the somewhat cryptic formula "model theory = universal algebra + logic."

Other thoughts on this?

Skolemizer (talk) 09:15, 4 January 2008 (UTC)

This is a good point to raise. The opening paragraphs are always going to be difficult I think partly because model thoery has developed and evolved so quickly (and looks set to evolve a great deal more). It is difficult to try to summarise the work of say Robinson together with some modern applied model theory. I do think that more stress could be given to the study of definable sets (particularly if one conisders, for example, o-minimality: this field become widely accepted and used amongst real geometers who are still sometimes hesitant about working in models other than R). We have at the moment much more information about "classical" model theory here, and perhaps this has been approoached in the correct order. As we introduce more on modern model theory and applications, we can also think about improving the opening.

By the way, well done to all who have edited the article in the last few months! I have been rather busy and not been on Wikipedia. I was very pleasantly surprised to see how much the article has improved. Thehalfone (talk) 10:22, 6 March 2008 (UTC)

[edit] Unfortunate deletion of crucial examples

I am an applied mathematician taking an axiomatic and structural approach to physics. I am finding this approach is proving answers to long standing paradoxes in the subject. My view is that Model Theory has much to offer applied mathematics.

However, I find the presentation style of texts on mathematical logic to be rather inaccessible. I was very pleased to find an earlier edition of this article very helpful due to examples given. The excerpt I have pasted below was especially helpful in giving me an introductory understanding of structure and undecidability in mathematics that tends not to be given in books.

Unfortunately this text was deleted at 21:51 on 28 November 2007. The style of the article since is probably more structured but is in a language that suits pure mathematicians.

I believe the article could be significantly improved by the addition of examples throughout, or alternatively a section written with applied mathematicians in mind. I wonder if the following section could be reinstated.

[edit] Preliminaries

[edit] Languages and structures

The syntactical object we need is a language. This consists of some logical symbols (plus a binary relation symbol for equality of elements), a list of non-logical symbols known as the signature, and grammatical rules which govern the formation of formulae and sentences.

Let $L$ be a language, and $M$ a set. Then we can make $M$ into an $L$ -structure by giving an interpretation to each of the non-logical symbols of $L$ . The grammatical rules of $L$ are designed so that one can then give each formula and sentence of $L$ a meaning on $M$ . The class of $L$ -structures together with, for each structure, the interpretations of the symbols, formulae and sentences are the semantical objects which correspond to the language.

Examples.

Consider the first order language with non-logical symbols $\{ \times, +, -, 0, 1 \}$ , where the grammar is arranged so that $\times$ and $+$ are binary operation symbols, $-$ is a unary operation symbol and $0$ and $1$ are both constant symbols.

Then if $M$ is a set, $f_1,f_2:M^2 \to M$ are any binary functions, $f 3$ is any unary function, and $m 0, m 1$ are elements of $M$ then we can make $M$ an $L$ -structure by interpreting $\times$ by $f 1$ , $+$ by $f 2$ , $-$ by $f 3$ , $0$ by $m 0$ and $1$ by $m 1$ .

For example we can take the set of real numbers and interpret the symbols of $L$ by their usual meanings in the real numbers. If we ask a question such as "∃y (y × y = 1 + 1)" in this language, then it is clear that the sentence is true for the reals - there is such a real number y, namely the square root of 2.

One can also make the rational numbers into a structure (with the standard meanings for the symbols on the rationals). Then the sentence considered above is false for the rationals. A similar proposition, "∃y (y × y = − 1)", is false in the reals, but is true in the complex numbers, where i × i = − 1.

Steve Faulkner, 19 may 2008