Talk:Structure (mathematical logic)

Ambiguity

Structure actually has two uses in math. logic: this and a fairly well established usage in structural proof theory due to Belnap. Shall we move this to Structure (model theory), and create Structure (proof theory)? --- Charles Stewart^(talk) 19:40, 15 February 2006 (UTC)

How common is the latter usage, really? My gut reaction is to leave this article where it is, and put a dab line at the top to the proof-theory concept, but I won't argue about it if you think the two notions have comparable footprints and want to have a dab page. --Trovatore 20:22, 15 February 2006 (UTC)

More Examples Needed

Some examples would be useful in this article (eg some simple examples on the integers with the natural ordering; eg a simple Hasse diagram of a poset). reetep 12:36, 17 November 2006 (UTC)

Now also covers universal algebra

Structures are just as important for universal algebra as they are for model theory. In fact, they are part of the common core of both subjects, and terminology is more or less the same. Since there was no equivalent article for universal algebra I extended this one to reflect this.

I added some new examples, but more non-technical examples are still needed. There could also be a paragraph which details the translations between our terms and those used in database theory. —Preceding unsigned comment added by Hans Adler (talk • contribs) 2007-11-15T23:49:32

It looks very good. I mean to expand the section on definability at some point.

Should the article be retitled now that it also covers universal algebra? The disambiguation page at Structure (mathematics) could be renamed and this could take that name. — Carl (CBM · talk) 00:51, 16 November 2007 (UTC)

I am not sure about that. The small disambiguation page is certainly not very nice, but I am afraid interest in this page won't be so substantial. Perhaps make structure (mathematics) a redirect to mathematical structure? That article is probably much more popular, and it could mention structure (mathematical logic) in the introduction. But I agree that renaming structure (mathematical logic) makes sense, since mathematical logic is at one extreme of the graph of areas which use the notion:

mathematical logic—model theory—universal algebra.

I was thinking about structure (model theory). In any case I would be happy with both options. --Hans Adler (talk) 23:26, 16 November 2007 (UTC)

Interpretation in what?

The article talks about the interpretation I of σ "in ${\mathcal {A}}$", where ${\mathcal {A}}=(A,\sigma ,I)$. This gives a kind of circularity: the interpretation interprets whatever it interprets in something that contains itself. But, actually, all that I needs to interpret σ is the domain A. I don't know how common the terminology is that is used now, but the following appears more proper to me:

Formally, a structure can be defined as a triple ${\mathcal {A}}=(A,\sigma ,I)$ consisting of a domain A, a signature σ, and an interpretation I over σ in terms of A.

...

Interpretation

The interpretation I of a structure ${\mathcal {A}}=(A,\sigma ,I)$ assigns to every function symbol f of σ a function $f^{\mathcal {A}}=I(f):A^{\operatorname {ar} (f)}\rightarrow A$, and to every relation symbol R of σ a set $R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }$.

 --Lambiam 14:45, 6 May 2008 (UTC)

This is slightly sloppy, but it's dramatically less sloppy than the very widespread convention of not even distinguishing between a structure and its domain. Although "interpretation" in this article is almost exactly the same thing as "interpretation" in the sense of Mendelson, this is only because it's contains almost the full information about the structure. (Almost, because we could increase the domain without changing the interpretation.) Normally this function is not named. I didn't intend to coin a word here; it didn't occur to me at the time that someone could treat it as more than a throw-away definition. If you treat it that way (i.e. we call this function the "interpretation [function]" because it is the part of the structure that controls how the signature is interpreted on the domain) you will probably see that it makes more sense.

The word should probably be removed or clearly marked as non-technical/unofficial. If you have a good solution that doesn't make the article unreadable, go ahead. But your proposal doesn't seem to solve the issue. Actually, I think it's worse because "interpretation of a structure" sounds as if the structure needed interpreting. --Hans Adler (talk) 18:50, 6 May 2008 (UTC)

I have found no reference for "interpretation"; Hodges (the new standard reference for model theory) doesn't name it at all, but Chang & Keisler (the old standard reference) call it "interpretation function". So I have renamed it, even though it's a bit clumsy. --Hans Adler (talk) 10:16, 8 May 2008 (UTC)

Russell

When I added, "In Russelian structure, the domain of a system of relations consists only of the fields of the relations, and these fields need not be sets." I was referring to a mathematical definition out of Principia, not to a philosophical discourse. This observation about the difference between model theory's definition of structure and Russell's definition was made Solomon, G (1990) 'What Became of Russell's Relation-Arithmetic?', Russell, vol 9: 168-73 and it is very consequential. The link to Russell's scientific philosophy was really only incidental to the fact that there is no good article on the mathematical foundation of Structural Realism nor is there a good article on Russell's relation arithmetic. Jim Bowery (talk)

I guess that what Carl (CBM) tried to explain to you in the limited space of an edit summary was that the present article is about a modern mathematical notion that thousands of mathematicians work with on a regular basis. From the modern point of view the definition in Principia is simply not "correct", i.e. not the generally agreed one. If I understand the Principia definition correctly (based only on what you wrote), then there are two differences:

1. Principia's structures are not equipped with a domain. The domain is defined as the union of the domains of the relations. – That's an extremely unpractical definition for anyone who actually wants to work with structures. In this respect the definition is clearly defective and obsolete.

2. Principia's structures allow class-sized domains (and relations). – This is like the difference between categories in general and small categories. There are technical difficulties in category theory because it does not restrict its scope to small categories, and model theory would have the same kind of problems if it used this more general definition. I suppose that is why, when people started to actually work with structures, they used the "small" definition. It makes sense to discuss this problem, but not in the lede, or at least not giving almost equal weight to a historical definition or one used only occasionally in connection to models of set theory. --Hans Adler (talk) 10:16, 1 December 2008 (UTC)

I'm sorry for the very terse explanation; I should have posted a longer note here. If this article had a "history" section, then perhaps Russell's structures could be mentioned there. But they are a very tangential point from the point of view of contemporary work, which I feel this article is intended to discuss. So I don't think the second sentence of the article should be spent describing them - the lede should discuss the most important points first. I have never seen Russell's structures discussed in the context of contemporary model theory, so mentioning them in the lede could give an incorrect impression that they are commonly studied.

I added another paragraph to the "generalizations" section that describes class models. I added a sentence there pointing out that the structures in Principia Mathematica could have a proper class as their domain. I'm not thrilled about that, though, because of my unfamiliarity with the details of the Principia. The notion of "proper class" was a relatively late development in the childhood of set theory and, from my point of view, is intimately related to the notion of a cumulative hierarchy in set theories that have that notion. I don't know if there is a parallel concept in Principia, which uses some sort of type theory rather than set theory. In other words, I don't know if it is anachronistic or revisionist to describe what Russell was doing from the viewpoint of ZFC, when he was not actually working in ZFC and ZFC was still in its infancy. — Carl (CBM · talk) 13:32, 1 December 2008 (UTC)

Jim - would you be able to write a longer section on "structures in Principia Mathematica"? That would be a nice addition but I don't have the background to write it. — Carl (CBM · talk) 13:55, 1 December 2008 (UTC)

I'm not competent to do so but the reason I am aware of this issue is that while working at HP's eSpeak project circa 2000, I hired a consultant, Tom Etter of whom I had become aware from his work on relational modeling of quantum systems at Interval Research. I've lost track of Tom but I preserved some of his results including The Expressive Power of Equality V5 which shows ZFC can be expressed using only equality (Mel Fitting reviewed it and stated to Raymond Smullyan "The result is correct."). It is my understanding from Tom that he based his work on Russell's approach to structure. Last I heard, Tom was living in Menlo Park but that was several years ago and I understand his wife passed away in that time. Jim Bowery (talk)

Request to clarify definition

Currently the definition section includes the statement: "A structure whose signature is σ is also called a σ-structure."

The preceding line defines a structure to include σ. So when would a structure ever NOT have a signature σ? So is it the case that any structure could be called a σ-structure?Gwideman (talk) 19:56, 10 December 2009 (UTC)

σ is a variable. If σ and τ are two different signatures, A is a σ-structure and B is a τ-structure, then A is not a τ-structure and B is not a σ-structure.

I will see if I can make this clearer in the text. Hans Adler 20:00, 10 December 2009 (UTC)

I see, so the problem here is that the symbol σ is being used to represent signatures in general, and also specific "values" of that signature. Maybe use a different symbol for a specific signature, like sigma with a subscript, and also provide an example so it's clear when we're moving from general to specific. Thanks Gwideman (talk) 20:05, 10 December 2009 (UTC)

After looking at the article I must say I don't see the problem. If we assume the normal mathematical conventions for dealing with variables it's perfectly clear. Are you perhaps more used to the conventions that are common in physics or chemistry? Your proposal sounds a bit like that. I am not happy with your idea since it's not an idiomatic way for expressing mathematics. Hans Adler 20:11, 10 December 2009 (UTC)

Yes, of course I'm unfamiliar with conventions used here, that's why I came to this page :-). I'm not stuck on particulars for distinguishing general from specific, just that they be distinguished somehow... which, by the way, you did nicely above using τ. So maybe a plausible edit would be

A structure having a particular signature, say τ, can be referred to as a τ-structure.

But having said that, I'm rather in the dark about what these signatures look like in practice (as noted in my request for exemplifying examples), and what kind of actual name a signature might have. Gwideman (talk) 20:26, 10 December 2009 (UTC)

Your wording is excellent. As to signatures, there is a more detailed article for them. I have made this clearer now with a "main article" link. But the idea is really very simple: The signature tells you what kinds of operations and comparisons are defined in the structure. Can you add two elements? Multiply? Compare them using ≤? In some structures you can, in others you can't. Hans Adler 20:36, 10 December 2009 (UTC)

Actually, your wording did suggest that there is something magical about the variable σ which is not the case. So I have rephrased it in a different way, after all. I guess you won't find it ideal, but hope it's at least a bit clearer now. Hans Adler 20:40, 10 December 2009 (UTC)

(Outdenting to avoid running off screen) Thanks, Hans, for your comments. I suspect part of the "magical" aspect is that the notation FancyA = (A,sigma,I) relies on the positions of the three slots to identify what they contain. As a naive reader I mistakenly assumed that the definition in the definition section is supplying names for those slots, whereas perhaps it is just showing example variables plugged into those slots. No matter, things are clearer now. —Preceding unsigned comment added by Gwideman (talk • contribs) 20:56, 10 December 2009 (UTC)

Request for the examples to exemplify

Currently the first examples section (1.4 Examples) describes examples but doesn't actually write them down.

It would be a great help if the structures discussed in the example section could be shown written in the form introduced in the definition:

A = (blah, blah, blah)

so we could see how this plays out. And that includes the supposedly "obvious way" in which this applies to rational numbers, real numbers etc. I'm sure the concepts are obvious, but the particulars of the notation are not. Thanks. Gwideman (talk) 20:01, 10 December 2009 (UTC)

Added: Is this Glossary_of_group_theory:

"...as algebraic structures of the form (G, •, e, −1), ..."

...an example of structure and notation as discussed on the current page, or is this some other notation?Gwideman (talk) 20:29, 10 December 2009 (UTC)

That's a different notation. The notation used in this article is the right one from a more abstract point of view. There are some common traditional notations that are a bit sloppy and don't actually contain the full information unless you read them in a specific way.

In this case the meaning is that G is the domain, • refers both to a multiplication symbol and its meaning as a function from G×G to G, e refers to both a constant symbol and its meaning as the unit element of the group, and -1 refers to both a symbol and the function from G to G that takes every element x to its inverse x^-1. Hans Adler 20:45, 10 December 2009 (UTC)

I see you've expanded the examples, very helpful. So basically, this notation starts with simply a triple that contains three single symbols representing a domain, a signature, and an interpretation, and depends on separate statements to expand on each of those. Although you've stated in words what sigma-f comprises, is there a particular way to write this down in this notation? Something like:

σ_f =(+,*,-,0,1)

Gwideman (talk) 21:04, 10 December 2009 (UTC)

The thing that is missing in that notation is the arity of the symbols. For example, in the list you just gave, is "-" a unary or a binary operation? Is "0" a constant symbol or a unary function symbol? Sometimes people do write a superscript on each symbol to make it possible to list them all: σ_f =(+²,*²,-¹,0⁰,1⁰). But I do not know how common this is; it is not very common in mathematical logic, so I must have seen it in the context of universal algebra once. I think it takes more effort to describe the convention than to just describe the symbols, at least for this article. — Carl (CBM · talk) 21:50, 10 December 2009 (UTC)

Thanks for filling in more details. I've no doubt my guess was inadequate, I was just hoping to prompt a complete example. You may well be right that this article is the wrong place to explain the notation it uses, but as long as math articles are going to use notation, I think it's only reasonable that there be some way for the reader to find their way to an explanation of the notation somewhere. Indeed, I stumbled in here myself looking for an explanation for notation used in another article! —Preceding unsigned comment added by Gwideman (talk • contribs) 23:20, 10 December 2009 (UTC)

Which article was that? Maybe I can fix it. Really we would like each article to be mostly self-contained in terms of notation, because we can't trust every reader to read every article, and because it is hard to keep many different articles all in sync with regards to notation. — Carl (CBM · talk) 00:49, 11 December 2009 (UTC)

Thanks for your comments/ Well, the current article is one. The article that sent me on this quest is Glossary_of_group_theory, though notation is only part of the problem with that page. But let me clarify: I'm not just looking for particular symbols to be described, I'm looking for an explanation of the notation system(s) themselves. Why? Because I want a concise and unambiguous statement of what the underlying concepts are, and this might be found in conjunction with a description of the notation used to capture those concepts.

As an example: We read in some narrative that a group is an example of a structure, and comprises a set, some operations and some constraints. Then we later read of a "subset" H of the group G. But is a group a set, or does it simply contain a set? Is the "subset of group" statement strictly legit, or is it shorthand for "subset of the set included in group G". While I realize that such matters are not defined by the notation, I had hoped to find enlightenment in discussions about the notation. This page here has the level of specificity I'm looking for: [1], though it might or might not be discussing a widely accepted convention.

So, efforts to make pages self contained I would certainly applaud, but my current quest is for descriptions of the notations used to describe the structure of math objects, with the components of the notation(s) spelled out, with examples.Gwideman (talk) 06:47, 11 December 2009 (UTC)

You have a valid point. In the official definition of a group it contains a set (its domain) as well as additional information. The way mathematicians think about it it is a set equipped with additional information. What this means is that in contexts where you would expect to hear about a set and the statement a priori makes no sense for a group, everybody agrees that when you mention the group you really mean its domain.

This is a fundamental part of how mathematical language works. I am not aware of any reliable (or other) sources that discuss the phenomenon in general and would love to hear about them if they exist. For structures it's exactly the same thing: Look at the second paragraph in the section Structure (mathematical logic)#Domain. It explains that even on the level of "precise" mathematical notation we often just put the structure itself instead of its domain. Thus we have a choice between use of a funny alphabet (structure ${\mathcal {A}}$ has domain A), use of cluttering notation (we call the structure itself A and denote its domain by |A|) and ambiguity (the same latter A sometimes refers to the structure and sometimes to its domain).

A practical example: Let A, B be structures. The statement "A is a substructure of B" refers to the structures. The statement "A is a subset of B" refers to the subset. The notation $A\subseteq B$, which could mean either because the symbol is used to denote either subset or substructure according to context, refers to the structures.

The relation between structures and groups is similar. Groups "are" structures but only in the sense that once you have fixed a specific signature σ for groups it's obvious how to translate every group into a σ-structure and vice versa.

All these language uses are not particular to mathematical language. E.g. "Washington explained its position at the Copenhagen summit." Even without more context it's clear that "Washington" doesn't refer to George Washington or a tomcat named after him. Neither does it refer to the city or the state. Not even to any person, body or organisation representing the city or state. It could mean all these things in appropriate contexts. Here it means someone/something representing the US.

The only thing that may be surprising at first is that mathematicians use language almost like everybody else. They are more precise, but they are not unusually pedantic in areas where no ambiguity can arise. Hans Adler 08:39, 11 December 2009 (UTC)

Thanks for the discussion, Hans -- very interesting. I think your "Washington" example is quite illuminating. You say "even without more context", yet the average reader of such a statement brings plenty of context to the sentence, knowing that Washington is a seat of government, that the place name is often used to stand for the administration. Similarly, in interpreting the utterances of mathematicians, other mathematicians bring a great deal of context to help fill in the shorthand. But that's not the case here on Wikipedia, where the audience doesn't necessarily have all the background from all the surrounding topics. Consequently, leaving out info that other mathematicians would regard as obvious pretty much guarantees ambiguity for readers not already versed in this area of mathematics.

In the "group" example I gave, your explanation is very reasonable, and also illustrates my point. Yes, it's no surprise that mathematicians reading "H is a subset of group G" can fill in that H is not a subset of G per se, but of G's domain. But if this is intended as expository narrative this elision prompts the non-expert reader to doubt their developing understanding of "group" -- is G actually a set? What exactly does "subset" mean in this context? Etc. I.e.: There's an audience that's quite capable of grasping the concepts, so long as they're not cast adrift by ambiguities.

Back to the matter at hand -- do you have a reference that describes this X = (feature, feature, feature...) style of notation for describing mathematical objects? In an earlier comment you wrote quite plainly that one notation convention was the "right" way (for this branch of math?) while a modestly different notation was older or sloppier... so I am eagerly hoping that this right way is documented somewhere. Gwideman (talk) 12:35, 11 December 2009 (UTC)

No, if you ever find such a thing let me know. It's a bit like linguistics applied to mathematical culture. These things are not usually made explicit. You are supposed to learn them along with learning the mathematics.

You should take care not to take my statements more literally than they are meant. The definition as a triple (A, σ, I) is really a right one. Instead we could define a structure as a triple (&sigma, A, I) or (I, A, &sigma). As long as we fix the order it doesn't matter which one we choose. Or we could define a structure as a quadruple (42, I, (σ, A), I), where 42 is just the number (always the same), I appears twice, and (σ, A) is a pair. This would be very weird, but still an instance of "the right" way of doing it. And there are other "right" ways of doing it that are harder to explain. The important question is: Does the formal definition contain exactly the information we want, no more, no less? E.g. (A, σ) doesn't, because it doesn't tell us what the connection between the symbols and the domain is.

Your questions make sense, but Wikipedia incorporates specialised technical encypledias, and this article falls into that area. Asking for an explanation that doesn't assume knowledge of mathematical language is a bit like asking for an explanation of a fine point of Chinese grammar, but insisting that it must be in English. It makes sense, but you are not likely to get it because most interested people will prefer it in Chinese. Hans Adler 12:52, 11 December 2009 (UTC)

> quadruple (42, I, (σ, A), I), with 42 is this kind of object the ultimate answer? 42 Very clever.

> Asking for an explanation that doesn't assume knowledge of mathematical language is a bit like asking for an explanation of a fine point of Chinese grammar, but insisting that it must be in English.

You mean like this? Chinese grammar

Yes, of course I realize that a single page cannot teach a reader a complex topic if they have no background at all. I do despair, however, when the missing ingredient is not background but rather overly terse or colloquial use of terminology or symbols. Anyhow, let's declare this topic fully chewed and move on :-). Thanks again Gwideman (talk) 15:59, 11 December 2009 (UTC)

Database comments in this article

"In database theory, structures with no functions are studied as models for relational databases, in the idiosyncratic form of relational models."

Is there a rationale or citation for relational models being described as "idiosyncratic"? And is this referring to The Relational Model, or to relational models of particular datasets?

I guess I'm also a little puzzled as to the point of mentioning databases at all. Sure, both Structure(math) and Relational Model identify a thing of interest, and a collection of features of that thing, and can be operated upon with logic of some type, but is there much more to it than that? What about semantic nets? Or programming language type systems? Gwideman (talk) 23:09, 10 December 2009 (UTC)

The point is that there is significant overlap between a part of database theory and a part of finite model theory. They research exactly the same things, but one side calls the objects of study structures, and the other calls them databases. As happens often in computer science, the abstract model for databases is extremely clumsy from a mathematical point of view. It is close to implementation in a computer and almost impossible to reason about precisely. I think I used the word "idiosyncratic" a long time ago, with no source. Nowadays I am a bit more careful about "original research", and it doesn't express exactly what I wanted to say anyway. I will just remove it. Hans Adler 01:27, 11 December 2009 (UTC)

Space

Is there a way to understand a topological space or measure space as a structure? Money is tight (talk) 15:59, 14 January 2010 (UTC)

You can understand a topological space as a 2-sorted structure: One sort for the points, and one for the open sets. But it's not a priori clear if this makes much sense. It depends on what you want to do with the space, once you have it as a structure. There have been several attempts to deal with topological spaces in model theory, e.g.:

• Chang and Keisler: Continuous Model Theory [2]
• Flum and Ziegler: Topological Model Theory
• Pillay: First Order Topological Structures and Theories, Journal of Symbolic Logic [3]
  • Schoutens: T-minimality [4]

I am less familiar with work related to measure theory, if it even exists. It's probably worth looking at continuous logic and metric structures. Hans Adler 18:50, 14 January 2010 (UTC)

Thanks. For categories, do you see them as two sorted structures (objects and arrows) with 4 function symbols, dom, cod, composition, and identity? Subject to the axioms... Composition isn't a total function does many sorted structures allow for this? Money is tight (talk) 00:06, 15 January 2010 (UTC)

Categories present no problem at all. We can use a 2-sorted approach with one sort for the objects and another for the morphisms. But as is well known, it's enough to work only with morphisms and represent the objects by their respective identity morphisms. In any case composition of morphisms is a partial function. The normal way to deal with this is to model it with a ternary relation that holds for (f,g,h) if (the composition of f and g exists and) h is the composition of f and g. If you want to avoid that, you follow Burmeister, A Model Theoretic Oriented Approach to Partial Algebras [5]. This approach works with generalised structures in an algebraic signature: The functions are allowed to be partial. It results in an interesting variant of universal algebra. Yet another approach would be to add a special element to the morphism sort which represents "undefined". Hans Adler 00:57, 15 January 2010 (UTC)

Definition

In the "Definition" section, the impression is given that a structure is only defined by its signature and not by axiomatic relations such as the existence of identity elements or inverses. But then, in the section "Induced substructures and closed subsets", it is mentioned that the rationals are the smallest substructure of the reals, generated by the empty set. This is not consistent. If only the <+,*,-,0,1> signature is relevant, then the integers Z are a smaller substructure. If on the other hand the axiomatic relations are also important, the "Definition" section needs to be more explicit on this. —Preceding unsigned comment added by 217.111.146.68 (talk) 08:58, 22 June 2010 (UTC)

This is a decent point, although I'm not sure in either case that it's exactly axioms that we're talking about. Rather, my immediate reaction is that the signature should also include the multiplicative inverse function (or, equivalently, division). I imagine the only reason whoever wrote the section didn't include it is that the zero of the field doesn't have an inverse. That is a slight annoyance, and I'm not sure how best to handle it in the text. --Trovatore (talk) 09:09, 22 June 2010 (UTC)

The signature of fields doesn't include a multiplicative inverse function, though, so I'm going to fix the article. — Carl (CBM · talk) 10:58, 22 June 2010 (UTC)

Is there really a standard "signature of fields"? Clearly there's more than one choice you could use. --Trovatore (talk) 17:58, 22 June 2010 (UTC)

I've seen some slight variants (e.g. whether − is unary or binary) but never one that contained division or inverse. Algebraist 18:05, 22 June 2010 (UTC)

In model theory, they usually take the signature of fields to be the signature of rings, which is to say they study the model theory of fields in the signature of rings. E.g. Hodges' Shorter Model Theory p. 10, Marker's Model Theory p. 17. — Carl (CBM · talk) 18:16, 22 June 2010 (UTC)

In that case maybe fields aren't a very good example for this article. --Trovatore (talk) 18:22, 22 June 2010 (UTC)

I think the point that a substructure doesn't have to satisfy the same theory as the original structure is somewhat relevant (cf. section 1.4). I think there is a nice parallelism between the second and third paragraphs of section 2.1. — Carl (CBM · talk) 18:27, 22 June 2010 (UTC)

In the "Domain" subsection of the "Definition" section, I altered "Very often the definition of a structure prohibits the empty domain" to "In classical first-order logic, the definition of a structure prohibits the empty domain." This was motivated by a recent discussion I had in which a computer science I was speaking to who knows quite a bit of logic had taken the previous version to mean that the model theory of classical first-order permits the empty domain which, of course, it does not. I have also augmented the associated footnote with a specific example of an inference rule that breaks when you allow the empty domain (Universal instantiation) and I have included a link to free logic in the footnote, whose model theory permits (well, sort of permits) empty domains and which, therefore, uses a qualified form of Universal Instantiation. --TXlogic (talk) 10:11, 17 December 2011 (UTC)

Typo in: Induced substructures and closed subsets ?

The definition quotes:

${\mathcal {A}}$ is called an (induced) substructure of ${\mathcal {B}}$ if

...

• the interpretations of all function and relation symbols agree on $|{\mathcal {B}}|$.

Shouldn't this read:

• the interpretations of all function and relation symbols agree on $|{\mathcal {A}}|$.

since $|{\mathcal {A}}|\subseteq |{\mathcal {B}}|$? — Ron van den Burg (talk) 13:29, 27 February 2011 (UTC)

Agreed. Fixed.

Homomorphisms: shouldn't the distinction between the symbol R and its interpretations be relevant here?

The article says:

Given two structures ${\mathcal {A}}$ and ${\mathcal {B}}$ of the same signature σ, a (σ-)homomorphism from ${\mathcal {A}}$ to ${\mathcal {B}}$ is a map $h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|$ which preserves the functions and relations. More precisely:

...

• For every n-ary relation symbol R of σ and any elements $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$, the following implication holds:

$(a_{1},a_{2},\dots ,a_{n})\in R\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R$.

However, since the interpretations of symbol $R$ ($R^{\mathcal {A}}$ and $R^{\mathcal {B}}$) are different, shouldn't the line read:

• For every n-ary relation symbol R of σ and any elements $a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|$, the following implication holds:

$(a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}$.

instead? — Ron van den Burg (talk) 13:50, 27 February 2011 (UTC)

Yes this looks correct, i.e. I agree with you. 69.143.122.185 (talk) 23:54, 26 January 2023 (UTC)

 Done I just edited the article to make the necessary changes (the conflation of the relation symbol in the object theory with its interpretations in the two structures A and B occurs at least twice in that section and I tried to fix all occurrences). 69.143.122.185 (talk) 00:07, 27 January 2023 (UTC)

Explanation of undo

Just to elaborate a little more on my undo in this edit.

It is true that at some level you can always replace a function by a relation giving the same information. For a unary function symbol f, you can substitute a relation symbol R, and interpret it via R(x,y) if and only if f(x)=y.

However, there are significant differences between languages that contain function symbols and ones that have only relation symbols. Function symbols have existential import, in the sense that if you have a structure for a language with a function symbol f, and a closed term t in the language, then the structure must contain an interpretation for f(t). Relation symbols don't give you that; a structure for a language containing our relation symbol R above is not guaranteed to have an object y such that the structure satisfies R(t,y).

This is important for lots of tools used to analyze structures. For example, the Ehrenfeucht–Fraïssé game is usually defined for languages that have only relation and constant symbols. If you allow non-nullary function symbols, the analysis gets more complicated. --Trovatore (talk) 22:17, 5 April 2015 (UTC)

The current Wikipedia defintion of the Ehrenfeucht–Fraïssé game is dissonant with your argument, as it specifically excludes function symbols: "Suppose that we are given two structures \mathfrak{A} and \mathfrak{B}, each with no function symbols and the same set of relation symbols..." How would you suggest this be resolved? Jim Bowery (talk) 06:42, 7 April 2015 (UTC)

Well, I was being conservative. I think there's a way to make them work with function symbols, but I don't really know how to do it. Since I have a vague notion that there's some way to get around the problem with sufficient work, I didn't want to flat-out assert that the technique can't be used at all. --Trovatore (talk) 20:59, 7 April 2015 (UTC)

Why Sets

Seems like as soon as we discuss the operations on structures, strangely, set theory pops up and everything is a set now. That's a little bit strange, because then these notions are not applicable to set theory, which is not based on sets; it's also not applicable to lambda-calculus, which has nothing to do with sets.

Can we get rid of using the term "set" at this level? It sounds like it's all turtles all the way down, with turtles replaced with sets.

Vlad Patryshev (talk) 02:44, 30 August 2021 (UTC)

Tarski's model-theoretic semantics for first-order logic uses a set theory (usually ZF or ZFC) to implement semantics for first-order logic theories. I.e. the use of sets is inherent to the field of model theory. So I don't understand the objection here. 69.143.122.185 (talk) 23:53, 26 January 2023 (UTC)

Math font typo in "Satisfaction relation"?

Satisfaction relation seems to have a typo:

It has both ${\mathcal {M}}$ and M. M seems to be a typo for ${\mathcal {M}}$.

If it isn't a typo, where M has appeared from? This needs to be explicitly said. --77.127.25.154 (talk) 08:26, 14 December 2021 (UTC)

 Done. The definition in section Structure_(mathematical_logic)#Definition says "${\mathcal {A}}=(A,\sigma ,I)$". This was tacitly applied to the letter "M", assuming tacitly "${\mathcal {M}}=(M,\sigma ,I)$" (I have made this explicit). To make the confusion complete, "$M$" was written as "M" (I have fixed this). - Thanks for noticing! - Jochen Burghardt (talk) 09:03, 14 December 2021 (UTC)

Strong homomorphism definition

The definition used in this article for "strong homomorphism" seems strange on the surface because it a priori assumes that the homomorphism is surjective. The problem with this definition has been discussed on math.stackexchange [6]https://math.stackexchange.com/questions/466657/two-definitions-of-strong-homomorphism, where they concluded that the definition in the Wikipedia article was possibly incorrectly copied from Chang, Keisler, which apparently assumes all homomorphisms are surjective throughout the book.

Another problem with the definition given in this article is the claim (which is in this article) that elementary embeddings are exactly the injective strong homomorphisms appears to be false. This is also mentioned in the math.stackexchange post. The claim doesn't appear to be true using this definition of "strong homomorphism". (Trying to better understand elementary embeddings is actually how I ended up in this section of the article.)

The definition of "strong homomorphism" that is ultimately agreed upon the math.stackexchange post is (i) $f$ is a homomorphism (so preserves relations) and (ii) $f$ also reflects relations i.e. for all ${\bar {a}}$ one has $R^{B}(f({\bar {a}}))\implies R^{A}({\bar {a}})$. The same definition is also used here [7]https://pdaniell.farm/archives/strong-homomorphisms as well as in this other math.stackexchange post [8]https://math.stackexchange.com/questions/1988514/what-is-strong-homomorphism?noredirect=1&lq=1

I would edit the article myself to get rid of the current definition and use the definition of "strong homomorphism" found on all of these websites, but I do not know (yet) of a textbook using this definition. I guess if after searching through model theory textbooks I find one that defines the concept I can edit the article later to at least mention that there is another definition out there. 69.143.122.185 (talk) 23:51, 26 January 2023 (UTC)