Talk:Type (model theory)

Example of a type

The example about ${\sqrt {2}}$ confuses me. I have corrected the obvious problem: If $x={\sqrt {2}}$ (say, in reals) then for y smaller than $-{\sqrt {2}}$ it is not true that $y^{2}>2\implies y>x$ (there is nothing about considering just positive reals in the article).

The definition of type that I know requests that if $\phi (x)$ and $\psi (x)$ belong to the type in a certain model, then also $\exists x(\phi (x)\wedge \psi (x))$ holds in the model (that is, $\phi \wedge \psi$ is consistent with the model). Thus, if the example statements about ${\sqrt {2}}$ are meant as a type in model of rationals then we would need examples of two conditions that are also met by some rational number. Or maybe what is meant by the example is a type in the theory of arithmetics, because being consistent with a model of a theory and being consistent with a theory are differnt things?

I am not an expert on this, so a second opinion would be helpful.82.208.2.227 15:23, 25 September 2006 (UTC)

Two replies to the above. 1. As regards the example, it now reads $y>0\land y^{2}>2\implies$. 2. In general a (partial) type is not required to be a filter. Any (partial) type has however its set of concequences which is a filter of the set of formulae. I prefer to use (partial) types this way, it is not however totally standard. Something else: The word type is often used to mean complete type, and partial type is used for the general notion. Unfortunately there is not widespread agreement on this, different papers have a different convention. In my experience, the latter view of types being complete is more widespread, as in many areas one need only consider complete types. Comments? Thehalfone 10:25, 3 October 2006 (UTC)

1. Yes, I have corrected the example and noted it on the discussion page because I felt that a little explanation is in order. Sorry, if it confused anyone. I still think that the definitions could be cleared up a bit (preferably by an expert). 2. The lecture on logic that we have had (at Charles University, Prague) used the opposite convention. 82.208.2.227 20:07, 12 October 2006 (UTC)

I appreciate a lot the content of this article, but the language looks pretty obscure and at times just awkward. I wonder if somebody could improve it. Not being a specialist in type theory, I'd rather abstain from doing it myself. --Vlad Patryshev 16:06, 12 April 2007 (UTC)

lede needs help

I agree that the article as it stands lacks sufficient context, and I've tried to add a better lede, but what I'm missing is _why_ types are significant, or some kind of analogy as to what they're _like_ -- for example it was explained to me that the diagram of a structure is 'analogous' to the multiplication table for a group -- I cannot find any similar useful and correct analogy for types that would provide motivation for why we study them. The rest of the article does (I think) a good job explaining what types are and what you can do with them. Help! Zero sharp (talk) 18:33, 15 August 2008 (UTC)

saturated structures

There should also be a link/mention of saturation since that concept is defined in terms of types Zero sharp (talk) 18:36, 15 August 2008 (UTC)

Omitting Types

Given a complete n-type p one can ask if there is a model of the theory that omits p, in other words there is no n-tuple in the model which realizes p. If p is an isolated point in the Stone space, i.e., if {p} is an open set. It is easy to see that every model realizes p (at least if the theory is complete). The omitting types theorem says that conversely if p is not isolated then there is a countable model omitting p (provided that the language is countable).

This is really unhelpful to me and I know at least basic model theory. There needs to be an explanation of the relationship between topology and model theory - the link to the topological notion of an open point doesn't help me to understand how an element of a model's domain can be isolated. What exactly are the conditions under which a type is omitted? —Preceding unsigned comment added by Dr satsuma (talk • contribs) 12:10, 12 March 2010 (UTC)

Incorrect example of elementary extension

The example where one constructs the elementary extension of the natural numbers with order is not actually elementary, as the model satisfies the sentence there are two elements with no immediate predecessor, which the naturals do not satisfy. — Preceding unsigned comment added by 84.248.64.88 (talk) 23:11, 12 February 2012 (UTC)

I'm not sure why you think the other model satisfies that sentence. If you're correct about that, then of course you're also correct that it's not an elementary extension, but I don't think you are. Nonstandard models of arithmetic all have the property that there is only one element that does not have an immediate predecessor. --Trovatore (talk) 23:17, 12 February 2012 (UTC)

As far as I can tell, there is no example where an elementary extension is constructed. Just one that says "Here's a type, if we could realize this in some elementary extension this is what we'd end up with." And then a warning that this isn't the same as just adding one element to realize the type because that element would be definable and so the extension would not be elementary. In reality, by compactness, we can realize the type in some elementary extension. As the property "There exists a unique element x such that for all y we have x not equal to s(y)" is first order and true in true arithemetic (or PA if you want), it will be true in the elementary extension given by compactness. So, I'm guessing your confusion was just with you thinking the non-example was an example. 24.131.192.199 (talk) —Preceding undated comment added 22:47, 13 February 2012 (UTC).

I'm quite confident that the example given is not an elementary extension. If the language only contains the ordering, then adding the integers on top of the naturals would make it an elementary extension, as no new element without immediate predecessors would be added. If the language contains addition, multiplication and so forth, then constructing an elementary extension would not be so easy.

Anyway, the statement that ${\mathcal {N}}$ and ${\mathcal {N'}}$ are elementarily equivalent is not true. Now for example the formula $\exists x\exists y(x\neq y\wedge \forall z(x\leq z)\wedge \forall w<y\exists w'(w<w'<y))$ is true in ${\mathcal {N}}'$ but not in ${\mathcal {N}}$. — Preceding unsigned comment added by 128.214.20.122 (talk) 07:38, 14 February 2012 (UTC)

Please explain what you mean by "the example given". As far as I can tell, 24.131.192.199 is correct; no well-specified "example" is given. In particular, nothing in the text says what ${\mathcal {N'}}$ is supposed to be; it just says that it's the part of the elementary extension that lives above the standard naturals. --Trovatore (talk) 08:21, 14 February 2012 (UTC)

By the example given I mean the model ${\mathcal {N}}^{\ast }$. In the article one quite explicitly constructs the model ${\mathcal {N}}^{\ast }$ and the ordering on it by attaching two copies of the naturals end to end. After the construction it is claimed that "${\mathcal {N}}^{*}$ is an elementary extension of ${\mathcal {N}}$ (w.r.t. $L(\mathbb {N} )$)", which is not true. Hence the claim after that about isolation doesn't make sense either. — Preceding unsigned comment added by 84.248.64.88 (talk) 16:26, 14 February 2012 (UTC)

No, the article does not in fact do that. I suspect you're assuming that ${\mathcal {N'}}$ is supposed to be isomorphic to ${\mathcal {N}}$, or at least order-isomorphic? But the text nowhere says that. Or, if it does, then please give the specific quote so we know what you're talking about. --Trovatore (talk) 16:31, 14 February 2012 (UTC)

No, I'm not confusing elementary equivalence with order isomorphism. :) The article reads: "This can be remedied by a new structure, ${\mathcal {N}}^{*}$ say, with domain $\mathbb {N} \cup \mathbb {N} '$ where $\mathbb {N} \cap \mathbb {N} '=\emptyset$ and $\leq ^{*}:=\leq \cup \leq '\cup \,\mathbb {N} \times \mathbb {N} '$. ${\mathcal {N}}^{*}$ is an elementary extension of ${\mathcal {N}}$ (w.r.t. $L(\mathbb {N} )$)". But these two structures are not elementarily equivalent, as the formula I wrote above shows. — Preceding unsigned comment added by 84.248.64.88 (talk) 16:39, 14 February 2012 (UTC)

And if this is meant to be some kind of "nonexample" of elementary equivalence, then this is not clear from the article. — Preceding unsigned comment added by 84.248.64.88 (talk) 17:01, 14 February 2012 (UTC)

I don't see how there's enough information given about $\mathbb {N} '$ for you to conclude that the structures are not elementarily equivalent. Are you assuming that $\mathbb {N} '$ has a least element? It doesn't assert that anywhere. --Trovatore (talk) 18:24, 14 February 2012 (UTC)

Perhaps the IP is assuming that $\mathbb {N} '$ is another copy of $\mathbb {N}$. This is not the case. One can arrange for it to be a copy of $\mathbb {N}$ times the rationals in a certain sense, but defining operations involves more work. Thus, one could use the ultrapower construction. Tkuvho (talk) 18:29, 14 February 2012 (UTC)

Ah, I did assume $\mathbb {N} '$ being a copy of the naturals. I see your point now, and everything makes sense. Denoting the added elements by $\mathbb {N} '$ confused me, and probably will confuse other people as well. Also, there's no mention of the language of the model, and as only the ordering is mentioned, I think most people will assume that the language is just $\{\leq \}$. In this case, just putting a copy of the integers on top of the naturals suffices to give an elementary extension, and the ultrapower construction or the integers times the rationals is not needed. Kreipas (talk) 18:45, 14 February 2012 (UTC)

$\mathbb {N} '$ is just another copy of the naturals. This is intentionally suggestive. The article even makes a point that you can't just add finitely many elements. The ordering though is not the standard ordering. I guess that could be clearer in the article, or we could just call it $\mathbb {Z}$; that is what's really going on anyway, and there's a lot of expense for novices reading this as written I'm sure. The language I think is relatively clear ("take the natural numbers with the ordering"). But, there's really no cost in making it more explicit (something like "take $\langle \mathbb {N} ,\leq \rangle$, the natural numbers with it's standard well ordering"). You're certainly right that this example can be made clearer and encyclopedic. I'll try to change it around later today if no one else does. Wgunther (talk) 19:32, 14 February 2012 (UTC)

Hmm, honestly I don't think this is a good idea. First of all, by calling the standard model ${\mathcal {N}}$ or $\mathbb {N}$, you're suggesting that addition and multiplication are around, whereas if I now understand correctly, you just want the order. In that case it would probably be best to call it ω, which is the order type of the naturals.

Secondly, when you say $\mathbb {N'}$ is "just a copy" of the naturals, you seem to be allowing yourself to re-interpret the non-logical symbols on it. In that case, the only thing $\mathbb {N'}$ has in common with the naturals is cardinality; that is, you really just mean some countably infinite set. Then an "intentionally suggestive" notation of $\mathbb {N'}$ is more "suggestive" than you actually want. --Trovatore (talk) 22:35, 14 February 2012 (UTC)

I rewrote the example. I think it's more understandable now and the structures are less nebulous. People can feel free to revert if they think it was better before. Wgunther (talk) 16:20, 15 February 2012 (UTC)

The notion of an elementary extension apparently includes also the arithmetic operations. My impression is that constructing such an extension is not a simple matter and may involve the axiom of choice or some weaker form of it. The example you presented seems to simple to have a chance of being an elementary extension. Can you source it? Tkuvho (talk) 16:32, 15 February 2012 (UTC)

Which operations are included in the notion depends on the language. If you're working in a language whose only non-logical symbol is the ordering, then you only have to worry about the ordering. If the language includes plus and times, then you have to worry about addition and multiplication. I haven't read Wgunther's example yet, but I think for a first example it is probably just as well to stick to ordering only, as long as it's very clear to the reader that that's what we're doing. (In some sense I belive there is no "explicit" example of a proper elementary extension of the naturals with plus and times — what "explicit" means is usually not very well specified, which is a recurring problem in WP articles where the axiom of choice comes up.) --Trovatore (talk) 16:45, 15 February 2012 (UTC)

One sense of "explicit" is provably impossible by Tenenbaum's theorem. At any rate, your point should be clearly spelled out in the article. If all one is looking for is the order, than the disjoint union of N and Z seems to do the trick, no? Tkuvho (talk) 17:34, 15 February 2012 (UTC)

Right, our model isn't so complicated. It's just the theory of omega with membership. It is finitely axiomatizable and decidable. It actually would still be even if you added the successor function for ordinals too. And yes, the disjoint union of N and Z does the trick. That is what my example is, I just assumed that Z is disjoint from N to make it just a union. Then defining the ordering in the extended structure is a bit simpler to write down. Enderton would probably be a good enough source. Chapter 3 talks about these models of the natural number. 3.2 talks about (essentially) our specific example, and how the nonstandard models of N with < and S are the same as with just N with S, which is just N with any Z chains you want. Wgunther (talk) 19:47, 15 February 2012 (UTC)

First line is hard to understand and imprecise

In model theory and related areas of mathematics, a type is a set of first-order formulas in a language L with free variables x₁, x₂,…, x_n which are true of a sequence of elements of an L-structure ${\mathcal {M}}$.

This line is hard to understand because it is complicated and imprecise. The way it is stated, it can be interpreted as "a type is just a set of satisfiable formulas". Is the "sequence of elements" fixed for a given type? Is a type a set of _all_ formulas that are true of a sequence?

Given paragraph Model theory#Types, I guess that the following is meant:

Given a language L, an L-structure ${\mathcal {M}}$ and a sequence $b=(b_{1},b_{2},\dots ,b_{n})$ of elements of the universe of ${\mathcal {M}}$, the type of $b$ is the set of all first-order formulas with free variables $x_{1},x_{2},\dots ,x_{n}$ which are satisfied by $b_{1},b_{2},\dots ,b_{n}$.

Is this correct?

Anyway, wouldn't it make more sense to talk about the basic idea of types in the first sentence in order to build up some intuition before giving a formal definition? That would mitigate such imprecisions intrinsic to natural language. -- 188.192.83.224 (talk) 06:13, 20 June 2012 (UTC)