Talk:Interpretation (model theory)

Start

Don't be shy, go ahead, discuss this. --Cokaban (talk) 20:47, 27 April 2008 (UTC)

Is this just an elaboration of the concept in interpretation (logic)? Pontiff Greg Bard (talk) 22:33, 28 April 2008 (UTC)

I didn't pay much attention at first to the article about interpretation (logic) because it was not classified under mathematics, and from the first look it seemed dealing with logic in the common sense, not with the mathematical logic (which is an area of mathematics). After checking it more carefully, i can say that it is still hardly related to this article. Well, first of all, the problem is that there are two rather different meanings of interpretation in model theory (and in mathematical logic). Ideally, they should have been called differently, but our language is rather poor, so we call both interpretations.

1. The first, closer to the meaning of the article interpretation (logic), means simply assigning "semantic" values to symbols of a language. This is just a basis of relating formulae to structures.
2. The second meaning, defined in this article, deals with interpreting one structure in another. It also has a counterpart, dealing with interpreting one language in another. I have not had time yet to add a section about this second syntactic meaning.

Second, while articles about logic do not always fall into the category of mathematics, as they mix sometimes mathematical logic with common-sense logic and with philosophy, articles about model theory should always stay under mathematics, as model theory is a part of algebra, related to mathematical logic. In fact, the only places where something not purely algebraic appears in this article, is the use of first-order formulae. However, there is a way to define sets definable by first-order formulae in purely algebraic terms, without using such syntactic constructions as first-order formulae and languages.

Last, i am really concerned about the article interpretation (logic). The definition of the interpretation (assigning objects to symbols so as the symbols become the names of the objects) seems to be all messed up. Why is it required (b) to have a unique name for every object? It is the other way around: unique object for every name. In fact, it often happens that the domain is much larger than the language, so it would be impossible to assign a name to every object, and this is not required. Neither it is required that the name be unique. Then, (c) why would a function assign truth values to tuples? Functional symbols are interpreted by functions which assign objects to tuples of objects. What does this mean (d) that the property be consistent with the sequences of objects??? This makes no sense whatsoever. And what are predicate variables? In (c) there were functional symbols, but all of a sudden in (d) there appeared predicate variables. In (e), i simply do not know what a sentential letter is. This term does not appear on the page where it is linking. --Cokaban (talk) 29 April 2008 (UTC)

Definition

It is not immediately obvious to me that the notion as defined in our Wikipedia article is equivalent to that in the Ahlbrandt–Ziegler article. For example, the equivalence relation on the domain of ƒ of giving the same result in the target structure (here M) is required there to be definable in the source structure of ƒ (here N). The mapping given as example from (presumably) ℤ × (ℤ \ {0}) to ℚ would also be an interpretation under the definition of our article if the structure ℤ is not a ring, but merely the additive group of the integers. However, the relation ƒ(x₁, y₁) = ƒ(x₂, y₂) is not definable in that impoverished structure. Also, the text is rather dense and doesn't give much context. Aren't there textbook sources for this concept, instead of a research article?  --Lambiam 11:42, 1 May 2008 (UTC)

The relation you are asking about ($f(x)=f(y)$) is required to be definable in this article as well: it is (warning: abuse of terminology --- same as in this article!) the $f$-preimage of the relation "=", which is a set definable without parameters in $M$. I am pretty sure that the definition is the same, unless i've made some stupid mistake. The definition of this article does require the preimages of all operations and relations of the structure $M$ (including the relation "=", which is always assumed to be in the signature) to be definable. Vice versa, if the preimages of operations and relations are definable, then by induction preimages of all definable sets are definable. (It was not clear enough in this article, that a definable set is in general a subset of a Cartesian power of the structure.)

I think that interpretations are defined in all major textbooks on the subject, such as Hodges, Poizat, Marker, but i am not sure. However, sometimes only syntactic version is defined, that is an interpretation of one first-order language or theory in another. From model-theoretic point of view, the corresponding relation between the models of these theories is often more interesting. If you translate the definition of a "syntactic" interpretation of one theory in another into the terms of models of these theories, what you should obtain is the definition from this article. --Cokaban (talk) 13:21, 1 May 2008 (UTC)

Implicitly extending the notion of preimage thus is in my opinion an unnecessarily obscure way of presenting the definition. When ƒ: X → Y, I expect an ƒ-preimage to be a subset of X. Wikipedia is not printed on paper, and there is no need to make the text as dense as possible.  --Lambiam 20:06, 2 May 2008 (UTC)

I am not sure that you have understood the argument if you say this is obscure. The diagonal is clearly a definable subset of M², and therefore its preimage under f², which is a subset of N²ⁿ (actually an equivalence relation on Nⁿ) is required to be definable. While this definition might be explained more intuitively and in more detail, I have never seen a textbook which does (only a few of the most recent ones cover this topic at all), and we should keep in mind that this is fairly advanced graduate-level material. --Hans Adler (talk) 20:52, 2 May 2008 (UTC)

Well, I did not understand the definition given originally in the article, since I missed that "ƒ-preimage" was supposed to be interpreted as meaning "ƒ^k-preimage". I still think that was needlessly obscure; with this edit you have, however, clarified that point in the article. But how obvious is it that the diagonal is first-order definable? Are we dealing with equational logic here? The article only mentions "first-order formula". Is equality one of the "predicate variables"? How are the formal language and deductive system of the logic determined?  --Lambiam 23:31, 2 May 2008 (UTC)

Yes, in model theory "first-order logic" always means "first-order logic with equality". That's part of the general culture. I have seen only two or three technical papers about model theory without equality. Model theory has nothing to do with deductive systems; they never occur. It's just like algebra, only that instead of equations between polynomials we use first-order formulas. As to the formal language – in this case nothing is said about it, and so it's implicitly understood that everything is first-order. Does this answer your questions? It's not so easy to put this into the article, because the equality question shouldn't be repeated all over the 100 or so model theory articles, and matters around the choice of logic are a bit fuzzy. There are some contexts where we have a bit more or a bit less than first-order, and in these we would probably use literally the same definitions. So there is some value in the ambivalence. --Hans Adler (talk) 23:51, 2 May 2008 (UTC)

In formulating Wikipedia articles on model-theoretic topics we should not assume that the reader is already familiar with the general culture of model theory. Our First-order logic article, linked to by "first-order formula" in this article, is totally agnostic about the collection of predicate symbols (called "variables" in our article), constant symbols, and function symbols that can be used to construct the formulas of the formal language. That is what I meant by "formal language": to the unsuspecting reader its lexicon is totally undefined. Likewise for the non-logical axioms.

We don't have an article on Equational logic, but assuming such an article exists (and I think we ought to have one; the concept is referred to in several articles), it should introduce first-order logic with equality, and then we can use that as a link target for occurrences of "first-order" in our model-theoretic articles. Or we could have a section entitled "First-order logic in model theory" in the First-order logic article, explaining what the term means in a model-theoretic context, and use that as a link target for "first-order".  --Lambiam 10:43, 3 May 2008 (UTC)

I think that the definition in this article is good in the context of first-order languages without equality as well. Of course it will be different then from the definition of Ahlbrandt–Ziegler, but i believe this is because Ahlbrandt–Ziegler assume that "=" is always in the signature, and interpreted as equality. --Cokaban (talk) 16:40, 6 May 2008 (UTC)

For first-order logic with equality it's formally not part of the signature, but it's of course definable. --Hans Adler (talk) 18:26, 6 May 2008 (UTC)

Equational logic is not first-order logic with equality. It is first order logic (with equality) without negation (and without implication) and without quantifiers (although implicitly every free variable is quantified universally). It's essentially the syntactic side of universal algebra.

We can't duplicate a huge article like first-order logic for every little variation. There are several other, orthogonal, variations such as many-sorted logic that it doesn't discuss yet (but I hope this will change soon). If we want to cover every combination we are going to get into big trouble. What we can do, of course, is explain in first-order logic which variants are normally used in which areas. I would be curious to know what background you are coming from that you are surprised we are using logic with equality. I have a vague idea that perhaps artificial intelligence uses logic without equality, but I thought there weren't many fields which do that. --Hans Adler (talk) 18:26, 6 May 2008 (UTC)

I just follow the definitions as given here on Wikipedia, taking them seriously instead of treating them as metaphors. If that results in something that doesn't seem right and I'm not sure about the proper fix, I complain. My professional work, to the extent that it involved logics, has mainly been with non-mainstream uses of logic, and the only use I've had for the notion of model is in the definition of the Mod functor taking a higher-order logic to the set of its models, which is useful in defining a notion of refinement between logics. The non-logical part of the logic is just a parameter, and in fact it is convenient to treat the logical constants mostly as if they aren't.

I think Wikipedia should attempt to cover the major variations, which in many cases can be done by sketching the idea because the required formal adjustments are obvious, and in particular those variants that are actually being referred to in other articles (unless it makes more sense to define them on the spot where they are mentioned). Whether that is done in separate articles (which do not need to duplicate everything; the text could say "it's just like X except ...") or as part of a larger article is a matter of convenience. It makes sense to have a separate article on many-sorted logic that explains the general idea (which the current Many-sorted logic fails to do).  --Lambiam 04:49, 7 May 2008 (UTC)

I am taking back my last comment above. The definition in this article is intended for the context where the actual equality is always assumed definable. If the equality is not assumed definable, then defining an interpretation as a function (many to one) is probably not good enough, maybe a relation (many to many) would work better. --Cokaban (talk) 09:19, 8 May 2008 (UTC)

Lambiam, how would you define the multiplication in $\mathbb {Q}$ (i.e. its preimage under $f$), if $\mathbb {Z}$ was only an additive group? --Cokaban (talk) 14:05, 1 May 2008 (UTC)

The paper of Ahlbrandt and Ziegler, however, seems to be the first one where bi-interpretability was defined. --Cokaban (talk) 13:31, 1 May 2008 (UTC)

Feel free to add references and context! --Cokaban (talk) 13:50, 1 May 2008 (UTC)

Thanks for starting this article. I felt the need for it for a while, but I wasn't sufficiently motivated to do something about it.

I have transformed the inline reference to the Ahlbrandt-Ziegler paper into a plain reference at the end of the article. If it ever grows to considerable size or gets lots of references we can change this back, but this is how we usually do it for small articles in mathematical logic. In this part of Wikipedia we rarely get into the kind of argument where we have to prove things with sources. --Hans Adler (talk) 17:26, 1 May 2008 (UTC)1

Rarely? You guys work me over for sources every time! My goodness! I don't make this kind of stuff up. See what I'm talking about? Be well, Pontiff Greg Bard (talk) 19:11, 1 May 2008 (UTC)

Dear Pontiff Greg Bard, you do not want to discuss the issue by email, so i'll try to explain the situation here one last time. As a general rule, articles dealing with mathematics do not need to cite any sources. Whether or not an article makes sense and is true can be seen from the article itself. But, now, put yourself please in my shoes. Imagine i encounter an article where the author claims that 2+2=5 and $\textstyle \cos x=1-{\frac {x^{2}}{2}}$ by definition. If i do not want to be directly impolite with the author, i will try first to ask him for his sources, to try to understand what made him think that 2+2=5 and $\textstyle \cos x=1-{\frac {x^{2}}{2}}$, and whether he really means that. Imagine next that the author replies that he took these definition from MathWorld web site. I still do not want to be impolite, so i point out that these definitions are not the same as in MathWorld, and ask whether there are other sources used by the author, because i really want to understand whether he made these "facts" up (and his word for this does not suffice), or something in the literature made him believe so. (In fact, whether the author made the definition up or used some sources is not important at all. For example, i made up the definition in this article myself, even though it is similar to the one of Ahlbrandt & Ziegler. If the author made up himself that 2+2=4, that would be also fine with me, but if he says that 2+2=5, i ask for sources just to try to understand his way of thinking --- like a "shrink".) If the author does not answer the questions and keeps insisting that $\textstyle \cos x=1-{\frac {x^{2}}{2}}$, i will not see much use in keeping on with the discussion on talk pages, and may suggest a communication by email. I hope you see now, how complicated a situation i am in. --Cokaban (talk) 20:54, 1 May 2008 (UTC)

Merger proposal

I just realised that we already have an article interpretable structure, on exactly the same topic as this one. (I even did some minimal editing there, half a year ago, but I completely forgot about it afterwards.) --Hans Adler (talk) 22:34, 2 May 2008 (UTC)

Good idea. But then there should be a redirection from here to there. --Cokaban (talk) 11:05, 3 May 2008 (UTC)

Introduction

I do not agree with the first sentence in the introduction. I do not think that the idea of interpreting one structure in another has much to do with comparing their complexities, even though with a reasonable definition of complexity, a structure that interprets another one should be at least as complex as that other one. --Cokaban (talk) 11:09, 3 May 2008 (UTC)

Then my disclaimer "vague notion" wasn't strong enough. I still feel that we need some kind of introduction, because the proper definition is rather complicated. Many people who arrive at this article will be in the wrong place. I would like them to go away thinking "this isn't what I was looking for" rather than "this makes no sense at all". That's why I would like to start with some vague, high-level statement.

I will try something else. Please keep complaining (or improving) until we have something that you are happy with. --Hans Adler (talk) 11:21, 3 May 2008 (UTC)

This one i like better. --Cokaban (talk) 14:25, 3 May 2008 (UTC)

It would be nice if the definition paragraph explained the relationship between this and the "interpretation function" described in the structure (mathematical logic) article. 67.122.211.205 (talk) 06:24, 17 September 2009 (UTC)

Its still impenetrable. I thought I knew what an interpretation was, and I had to think hard to try to figure out if what I know agrees with what is written here. I was not able to come to a firm conclusion. This article is in dire need of expansion, simplification, re-write... linas (talk) 14:20, 20 September 2012 (UTC)

Bi-interpretation reducibility

I don't see what this notion of bi-interpretability of structures really adds to simple mutual interpretability, could someone please elaborate? For let $M$ and $N$ be mutually interpretable and $f\colon Y\to M$, $Y\subseteq N^{n}$, $g\colon X\to N$, $X\subseteq M^{m}$, and let $S\subseteq M^{k}$ be definable in $M$. Then its $f^{k}$-preimage is definable in $N$, and the $g^{kn}$-preimage of this preimage is in turn definable in $M$, which means the $f^{k}\circ g^{kn}$-preimage of $S$ is definable in $M$. So the composite interpretation of a definable set of a structure in itself is definable in itself, and so the structures are bi-interpretable according to the definition in the article. Am I wrong? Seriy.seriy (talk) 19:57, 25 September 2020 (UTC)

Weird question about the sans-serif italics legibility.

The italicized N^n looks more like N^7 in Tahoma (a commonly used sans-serif font in place of Arial as it distinguishes between capital i and lowercase L) with Chrome, due to the overlap in the letters. This is a problem when the base is M or N and the superscript has a vertical stroke on the lhs, and increasing font size in browser does nothing to help because the overlap is almost exact.

I'm tempted to add a narrow non-breaking space like " " (U+202F /  ) in front of all sans-serif italics superscripts in the article to make them legible, but I worry this might be seen as vandalism and I don't know if other users would agree it is even a good idea. Although I haven't noticed it until now, there are probably many cases of sans-serif italics superscripts already in the wiki where the overlap is an issue (e.g. N^k, N^m, M^h, etc.) and doing this kludge in one place might not be the best solution.

The article did confuse me for a bit as I tried to determine where the sequence of seven naturals was coming from, though. TricksterWolf (talk) 00:56, 30 July 2021 (UTC)