Talk:Formal language/Archive 2

Structural linguistics

I once had a book entitled "Structural Linguistics". It appears to me that "formal" here is simply a synonym for "structural", and that "language" is being used to refer to "linguistics". Does structural linguistics merit a mention in this article? Unfree (talk) 22:37, 28 June 2009 (UTC)

Perhaps. Formal language theory is definitely a particular continuation of Structural Linguistics. However, linguistics is the study of natural languages, while formal language theory is mostly applied to artificial ones. Rp (talk) 19:11, 29 June 2009 (UTC)

Feminist grammar

I find nothing in Wikipedia about the alterations to English usage recommended by feminists. Unfree (talk) 22:37, 28 June 2009 (UTC)

You are clearly at the wrong article. There is a hatnote starting with "This article is about a technical term in mathematics and computer science" (my bold). Both of your questions relate to linguistics, so you probably want grammar framework or an article linked from there. Hans Adler 23:40, 28 June 2009 (UTC)

Every set of words

I agree with Hans Adler's edit earlier today. Once one fixes an alphabet, every set of words on that alphabet is a formal language. Moreover, I am not sure what "precise syntactical meaning, programmable for computer interpretation" means. If one starts with an uncountable alphabet, how could the language be programmable for computer interpretation in any sense? — Carl (CBM · talk) 16:09, 30 June 2009 (UTC)

We have a excessive general definition

In the sense defined in this article, one could create a 'formal language' exactly as English, but without empirical semantics. So, altrough even Routlegde Encyclopedia of Philosophy says that "In the most general sense, a formal language is a set of expressions", would be great to include a not-so-general definition in the article. (Rafael, 9 July 2009)

I don't see a problem. If you can give a precise definition of the grammatical sentences of English (actually I am sure you can't), or something that comes pretty close, then you can define a formal language that looks like English. Also, the set of all Wikipedia article source codes as of today midnight GMT is a formal language over the Unicode alphabet.

This is currently a mathematics and computer science article, and for these fields this is a well established standard definition. I am not aware of any variants, other than the occasional assumption that every language is defined by a grammar, which is made either for expository reasons or due to the author's confusion, and is not made in situations where the definition is used in a non-trivial way, i.e. for mathematical existence or non-existence proofs.

If you can find a different precise definition of the term 'formal language', say in linguistics, then it can be added to this article or put into a separate article; or perhaps it will be better known under a different name, and already have an article under that name. Hans Adler 15:01, 9 July 2009 (UTC)

This problem keeps coming up. The article should make it clear why the definition is what it is (namely, that formal language theory is devoted to studying formalisms for defining syntax). Rp (talk) 16:32, 9 July 2009 (UTC)

I agree. Unfortunately it's rare for mathematics texts to discuss the motivations for definitions in detail, so finding a reliable source for such an explanation might prove tricky. Hans Adler 17:21, 9 July 2009 (UTC)

A bit of explanation for this modeling decision is found at the very beginning of Chapter 1 in the Handbook: "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39. Maybe this can serve as a source, I am currently not aware of others. There might be some textbook on Computational Linguistics that elaborates more on this point, but this is a vague guess. Hermel (talk) 09:00, 10 July 2009 (UTC)

Another clue: the book that established most of the framework of formal language theory is called Syntactic structures. Rp (talk) 07:51, 21 July 2009 (UTC)

Merger proposal

It has been proposed to merge the stub Formal language theory into this article. Since it's only a stub, I agree. I guess one could write a big article on the topic. In that case the present article would serve as a simple introduction to just the basic notion, which is also used in fields not closely related to formal language theory. But a temporary merge is OK and probably beneficial. A section on formal language theory in this article might even attract more activity than the separate article. Hans Adler 08:26, 20 August 2009 (UTC)

I agree to merge, especially since it is a stub and reduplicates (only a small part of) the information found in this article. Hermel (talk) 12:15, 20 August 2009 (UTC)

I also agree. What is more, I propose to call the merged article Formal language theory: it may put an end to some of the unsatisfactory discussions we've seen here. Rp (talk) 19:58, 20 August 2009 (UTC)

I am not sure that renaming is a good idea. At the moment it wouldn't really reflect the content of the article, and it might even inspire someone to create a POV fork under the present name. Hans Adler 20:07, 20 August 2009 (UTC)

I'm also not sure about the renaming idea. I support the merge though (since I proposed it). --Robin (talk) 22:00, 20 August 2009 (UTC)

Redundant passage removed

I have just removed the following passage recently added to the article text by Gregbard:

"A formal language can be identified as its set of well formed formulas. If the set of all wffs of a formal language ${\mathcal {L}}$ is identical to the set of all wffs of a formal language ${\mathcal {L'}}$, then ${\mathcal {L}}$ is the same formal language as ${\mathcal {L'}}$; and if not, then it is not the same."

According to the mathematical definition given few lines before that passage, a formal language is nothing else than a set of words, or equivalently, of well formed formulas. Following this definition, the removed passage says that two sets of wffs are the same if the wffs they contan are the same. This is clearly true for any set, so where is the point? Hermel (talk) 16:39, 13 September 2009 (UTC)

I agree. — Carl (CBM · talk) 16:48, 13 September 2009 (UTC)

The reason it is of note is that it contrasts to formal systems in that a formal system cannot be identified by a set of all its theorems. Two formal systems ${\mathcal {S}}$ and ${\mathcal {S'}}$ may have all the same theorems and yet differ in some significant proof-theoretic way ( a formula A may be a syntactic consequence of a formula B in one but not another for instance). The statement itself seems very fundamental to the nature of a formal language, so as to just if its conclusion in the lead paragraph. Pontiff Greg Bard (talk) 22:31, 14 September 2009 (UTC)

The point you seem to want to stress is the following: A formal system is a certain mathematical object, of which a central property are its theorems. But a formal system is more than just a set of theorems, or formulas, and that is why we do *not* consider two formal systems equivalent already if the sets of their theorems are the same. In contrast, a formal language is nothing else than a set of words (in some contexts called wffs or theorems). Thus (of course) we consider two formal languages equivalent already if their wffs coincide. I want to explain my problem with the removed paragraph using a somewhat absurd analogy. The removed paragraph says something like

Two real numbers x,y are considered as being the same if their real parts coincide, i.e. $\Re (x)=\Re (y)$.

Of course, the above sentence no longer holds for complex numbers and thus "seems very fundamental to the nature of a real number". Yet this sentence about the real numbers makes sense only if one already has in mind more complicated objects (complex numbers). It is thus probably more appropriate to explain that difference in the article about formal systems – provided it needs to be explained at all. Hermel (talk) 13:21, 15 September 2009 (UTC)

Image

What exactly is the problem with the clear image explaining these basic relationships? I think if you do not see this as a correct understanding of things I would find that astonishing. These are the basics. Furthermore, I have seen this type of diagram in several different texts on the subject. If there is some clarification to make, I would welcome that, however blank stares or their equivalent will not suffice. Pontiff Greg Bard (talk) 23:52, 12 September 2009 (UTC)

I am quite confused about what the text "Formal languages" at the top is supposed to mean. The formal language consists of the well-formed formulas, so I would expect "formal language" to be in the second square instead of the top. Is it supposed to be a title? If so, I would suggest moving it to the caption. — Carl (CBM · talk) 00:18, 13 September 2009 (UTC)

This is very constructive, I may redo the image soon. It is true that a formal language is identical to its set of wffs. Basically "Formal languages" was intended as a title and also seemed to serve as the title of the "universe" which these squares are slicing up just fine. However if there is confusion, I will address it by removing the title. The diagram is saying that for any formal language there are symbols and strings of symbols ... and among those symbols and strings of symbols some are well formed formulas ... and among those well formed formulas some are theorems. In my mind a diagram like this helps the reader quite a bit. Pontiff Greg Bard (talk) 01:03, 13 September 2009 (UTC)

What exactly is the image conveying? Is it conveying this relationship: The set of theorems is a subset of the set of wffs. The set of wffs is a subset of $\Sigma ^{*}$? --Robin (talk) 02:24, 13 September 2009 (UTC)

That's what I get out of it, now that it has been updated. I don't have any problem with a Venn diagram illustrating the relationships between these things. In the context of the present article, there is an an additional, subtle point. A formal language, on its own, doesn't have "theorems"; one has to introduce some sort of deductive system to get that. So in the context of this article, only the outer two boxes in the diagram are truly relevant. — Carl (CBM · talk) 12:22, 13 September 2009 (UTC)

The content which provided much relevance has been repeatedly removed. I have tried to provide content on the use of formal languages in formal systems, proofs etcetera. It's a big waste of wonderful contributions in an area needing coverage, to which many of the math regulars have been quite hostile. Pontiff Greg Bard (talk) 22:37, 14 September 2009 (UTC)

Gregbard has solved the worst problem, but the image is still not appropriate for this article, at least not in its current position. (Perhaps in a new subsection on logic.) The problem is that the terms well-formed formula and theorem don't occur outside a logic context, and that this logic context is not the overwhelmingly dominating context for the discussion of formal languages at all. If we take ASCII as the alphabet we can consider the set of syntactically correct C programs. These are not called "well-formed formulas" to distinguish them from arbitrary strings of ASCII symbols. And as CBM pointed out, an analogue of "theorems" doesn't even exist in this case. Similarly for linguistics, the original context of formal languages: Given a formal grammar that approximates English, the syntactically correct English sentences are not normally called "well-formed formulas", and again there is no analogue for "theorems". Hans Adler 14:31, 13 September 2009 (UTC)

The image is inappropriate both here and at symbol (formal). CBM and Hans Adler explain it pretty well. The theorems that come from a given deductive system do constitute a formal language, just like grape juice fermentation constitutes a chemical reaction, but we wouldn't expect a large diagram about wine varieties at the top of the general article about chemistry. I'd suggest having a section about complexity classes, in which the theorems of some mathematical theories could be mentioned as examples of recursively enumerable languages. 207.241.229.56 (talk) 23:05, 15 September 2009 (UTC)

I have to strongly disagree with this very silly analogy. While almost all (if not all) the mathematical and computer use of formal language can expressed in terms of the logical uses of formal language, it is not true that all of chemistry consists in variations of grape juice. This content is either appropriate here or we need to create formal language (logic), which I am increasingly seeing as inevitable. Pontiff Greg Bard (talk) 21:09, 17 September 2009 (UTC)

I think it's a bit idiosyncratic to think of formal languages as a topic within mathematical logic, rather than one slightly intersecting it. I don't see a need for a separate logic-specific article about formal languages either, but that's a separate issue. Sure, all the stuff in Hopcroft and Ullman's book can be expressed in terms of mathematical logic, but so can basically everything else in mathematics (that's the whole point of mathematical logic). We still treat mathematical logic as a branch of mathematics, not the other way around. 207.241.229.56 (talk) 03:22, 18 September 2009 (UTC)

As I understand it, the goal of formal language (logic) is not to describe the usage in mathematical logic, but rather th explain the usage in some other, nebulous kind of logic. To the extent that formal languages are "studied" in mathematical logic, they are the same as in computer science and linguistics. But it's actually a stretch to claim that mathematical logic involves the study of formal languages, just as it would be a stretch to say that physics includes the study of functions because the position of a particle is a function of time. Mathematical logic uses the terminology of formal languages when it is convenient to do so, but otherwise is not particularly interested in the generalities of formal languages. I am going to touch up the lede on this point. — Carl (CBM · talk) 17:47, 18 September 2009 (UTC)

proposed expansion

The current state of the article seems pretty skimpy to me, despite the excessive diagram. I think it could be refactored/expanded with an outline something like this:

• Mathematical definition
• Formal grammars
• Chomsky hierarchy and relation between grammars and automata
• complexity classes
• deductive systems and theories
• maybe another topic or two, like infinitary languages

The logic section would allow getting in a mention of wff's and theorems. I might attempt this in my nonexistent free time. Anyone else is of course also welcome to.

207.241.229.56 (talk) 23:40, 15 September 2009 (UTC)

Please be careful not to elaborate on topics that have their own articles. Rp (talk) 00:22, 18 September 2009 (UTC)

Some of the topics that have their own articles shouldn't, and should be reabsorbed here. — Arthur Rubin (talk) 00:25, 18 September 2009 (UTC)

Are you referring to any of the six bullets above? — Carl (CBM · talk) 00:47, 18 September 2009 (UTC)

I was thinking in terms of having a paragraph or so about each of the bulleted topics, with a "main article: ..." link to the separate article about the topic. "Formal language" would become an overview article, since it reaches out into a lot of different areas. 207.241.229.56 (talk) 03:13, 18 September 2009 (UTC)

I also think the complexity classes should be mentioned. I added Kolmogorov complexity and descriptive complexity theory to "see also for now". Pcap ping 05:35, 19 September 2009 (UTC)

OMG

Having just read through the talk archive of this article, I see there's been longer-running disagreements than I'd realized. I admire Gregbard's enthusiasm but Hans Adler and CBM really do know what they're talking about. Greg, you might read the Hopcroft and Ullman book cited in the article. It is pretty accessible without requiring knowing a lot of math. It is probably the most reliable source in the subject. It has 9785 citations in Google Scholar [1] while Hunter's Metalogic has 56 citations.[2].

I think the article should be rewritten using the H&U book as the main authority for determining weight, with a few other topics like logical theories sprinkled in (and maybe also something from algebra, like the word problem for finite groups). The outline I gave further up should still more or less work.

I notice that the strings/wffs/theorems diagram is gone from this article now, but it is still in some other articles Theorem, Well-formed formula, Syntax (logic), and Symbol (formal), plus Formal language (logic) which is under deletion discussion. I think it is out of place in at least the wff, syntax, and symbol articles. I also don't understand its emphasis on wffs and theorems. CBM would know better than me, but I thought the king of logical theories was true arithmetic, to which I'd say the concept of theorems doesn't apply in the usual sense. The diagram is misleading regarding theories like this. Anyway I mention that to point out that there may still be problems related to the diagram.

I hope the disputes can be sorted out since I'm sure they are burning a lot of people's energy. I personally had a kind of epiphany when I first studied mathematical logic as an undergraduate. I wanted to apply ideas like models and interpretations to everything in life. I got over it. It wasn't quite as bogus as realizing that the universe is a giant burrito and starting a religion based on that, but maybe the comparison will make sense. From surprising statements like "I also believe that Theory and Theory (mathematical logic) are the same, and yet there are two articles. These splits are the result of politics not academics."[3] (e.g. literary theory is part of that topic in mathematical logic?!) I wonder if Greg also had one of those "Eureka" moments from Hunter's book and is pursuing it wherever it goes. If so, it's a wonderful feeling, but try not to take it too seriously. And I wouldn't be surprised if CBM and Hans experienced it even more intensely than I did, since they became research specialists in logic, while I'm just a computer guy. But their perspective at least now is very realistic.

I'm going to try to sign off and stay away from this topic rather than get sucked into it even more. Good luck everyone. 207.241.229.56 (talk) 07:38, 18 September 2009 (UTC)

Yes, OMG indeed. Pcap ping 11:17, 18 September 2009 (UTC)

Formal languages in logic

I think I found a good source for this. Arnon Avron, "What is a logical system?", section 1. On an alphabet, one may want to distinguish several syntactic categories, e.g. variables, and for a logical system, one needs to have a category of wffs. Category here needs to be understood as subset/sort. Note that the rest of a logical system should not be confused with the formal language, so other issues like deduction and what not are off-topic here. Pcap ping 14:40, 18 September 2009 (UTC)

Deduction may strictly-speaking be off-topic to an article about formal languages, but there seems to be an awful lot of confusion between formal languages, formal systems (which are also defined in syntactic terms) and formal semantics. A brief mention is clearly appropriate in order to motivate the distinction between these. --Classicalecon (talk) 15:56, 18 September 2009 (UTC)

Mention yes, takeover no. Pcap ping 16:47, 18 September 2009 (UTC)

I repeat, I think the confusion is due to the article trying to cover formal language theory (i.e. syntax only) under the title of formal language - which name is strongly associated with languages in which both syntax and semantics are formally defined and therefore strongly invites discussion of semantical aspects of such languages. Rp (talk) 17:10, 26 September 2009 (UTC)

Sentence

I moved this from the lede:

Formal languages are purely syntactical entities; they are defined without any reference to their meaning or semantics, either formal or informal.

The issue is that the following are mutually inconsistent:

• The set of formulas in the language of Peano arithmetic that are true in the standard model is a theory (mathematical logic)
• Every theory is a formal language
• A formal language is always definable without reference to the semantics of its words

Correct. The third statement is false. It is false because in this case, the semantics are defined entirely in terms of formal symbol manipulation rules. There isn't a clear-cut universally upheld between syntax and semantics in this area. Rp (talk) 10:30, 6 October 2009 (UTC)

The key point here is that every set of words in a particular alphabet will be a formal language, but only countably many sets of words over a finite language can possibly be finitely definable, much less syntactically definable. The bullets above are just one concrete instance of this phenomenon.

If we want to add something to the article to the effect that Hunter's book uses "formal language" in a more restricted sense, that should not be in the lede, since that would be just a point about a particular book. — Carl (CBM · talk) 02:06, 3 October 2009 (UTC)

The exact quote is "It must be possible to define both sets [referring to the set of A) symbols and B) the formation rules] without any reference to interpretation: otherwise the language is not a formal language." Carl, this makes complete sense otherwise mathematics wouldn't be useful at all. The whole point is that they are truths, the truth of which does not depend on any particular subject matter it is applied to. I find as least some issues in your first two statements:

1) seems to be breaking the rule directly, and so the question is 'Is #1 wrong or is it sometimes okay to let semantics creep into these definitions.' This is what I think is the essence of the problem in this case. You cannot define a formal language by saying "all the sentences that are true in this case, the other case, etcetera.... are formulas of a formal language L." That is expressly forbidden, and forbidden for a good reason. You no longer have claim to a rigorous system if you let this slide. Hunter gives several examples.

2 should be more precisely stated: "Every "formal theory" can be expressed as a formal language." I think the stronger claim that it is a formal language depends on the fact that there do not have to be any actual token instances of a formula in order for it to be a formula of a formal language -- I am pretty sure you were backing away from that claim in another discussion?! In any case, perhaps there is some kind of mish-mash when going from theory to language in this case?

Be well,Pontiff Greg Bard (talk) 23:39, 3 October 2009 (UTC)

There are huge numbers of sources for the claim that any set of words constitutes a formal language; here are some that I looked up on google books just now.

• "A (formal) language is a set of strings of symbols from some one alphabet." Introduction to automata theory, languages, and computation, John E. Hopcroft, Jeffrey D. Ullman, 1979, p. 2
• "Any set of words over [an alphabet] is called a formal language over [that alphabet]" Encyclopedia of Computer Science and Technology, Allen Kent, James G. Williams, p. 366
• "Subsets (finite or infinite) of [words over an alphabet] are referred to as (formal) languages over [the alphabet]." Handbook of Formal Languages: Word, language, grammar, Grzegorz Rozenberg, Arto Salomaa, p. 11
• "A formal language over an alphabet is any set of strings of characters of the alphabet" Discrete mathematics with applications, Susanna S. Epp, p. 243
• "A formal language is any proper or non-proper subset of the set of all strings which can be formed using zero or more symbols of the alphabet A" A Concise Introduction to Languages and Machines, Alan P. Parkes, p. 15
• "A (formal) language L over an alphabet is simply defined as any subset of [the set of words over the alphabet." A first course in formal language theory, V. J. Rayward-Smith, 1983
• "A language over [an alphabet] is any subset of [the set of words over the alphabet]." Theoretical computer science, Juraj Hromkovič , p. 22
• "By a language we simply mean a set of strings involving symbols from some alphabet." Introduction to languages and the theory of computation, John C. Martin, p. 28
• "A language is a subset of [the set of words over an alphabet], and every such subset is a language." An introduction to formal languages and automata, Peter Linz, p. 279. From p. 15: "A language is defined very generally as a subset of [the set of words over some alphabet]. ... any set of strings over [an alphabet] can be considered a language".

None of these authors (several of whom are writing books explicitly about formal languages) adds a caveat that the language must be syntactically definable. Several, however, explicitly use the word "any". The restriction to languages that can be defined "without any reference to interpretation" is simply an idiosyncrasy of Hunter's, not a generally-accepted definition of a formal language. — Carl (CBM · talk) 01:34, 4 October 2009 (UTC)

Um, Carl, I hate to do this to you, but not one of the several definitions you gave necessarily says anything about an interpreted word or an interpreted string of symbols etcetera. It still could be that these authors just take it for granted that they are uninterpreted, and it is still the case that the requirement holds. I would say that since that is the case for all of them, that they are purposely avoiding the issue in their language. Pontiff Greg Bard (talk) 01:42, 4 October 2009 (UTC)

Let L be "the set of all sentences in the language of arithmetic that are true in the standard model of Peano arithmetic". Then L is certainly some set of words over a finite alphabet, so according to all these authors L is a formal language. — Carl (CBM · talk) 01:44, 4 October 2009 (UTC)

...and that is a circular definition of a language defined as a language. L is the set of true sentences of a language, and oh by the way L is a language, and by the way it is a language useful for expressing truths. That doesn't work. Pontiff Greg Bard (talk) 01:49, 4 October 2009 (UTC)

Are you saying that set L is not actually well defined? L is the theory known as "true arithmetic" and is perfectly well defined. In the terminology explained at theory (mathematical logic), L is the "complete theory of the standard model of arithmetic using the signature of first-order arithmetic". — Carl (CBM · talk) 01:54, 4 October 2009 (UTC)

PS We even have an article on it: true arithmetic. — Carl (CBM · talk) 01:58, 4 October 2009 (UTC)

Carl, the article states explicitly that "true arithmetic" is not arithmetically definable. That is a separate issue from defining a formal language....although it is still consistent with my claim.-GB

Remember we are talking here about the claim I moved from the article,

"Formal languages are purely syntactical entities; they are defined without any reference to their meaning or semantics, either formal or informal."

It is true that formal languages are syntactical entities, in the sense that they are simply sets of words, and words are by definition syntactical entities. But there is no restriction on how the set of words that constitutes a formal language may be defined. In many cases there will be no definition, because there are uncountably many sets of words over any nonempty alphabet, but only countably many definitions of a set of words in English. — Carl (CBM · talk) 01:54, 4 October 2009 (UTC)

There does seem to be an explicit statement to the contrary in a reliable source. Furthermore, the many examples you have taken the time to gather (which I appreciate) do not serve to support the point you were trying to make. It seems for sure that things are being taken for granted here, and commonly so. So my question now is, "Should we take for granted that it is okay to allow the interpretation of a formal language to become part of its definition?" There does not seem to be any evidence given that we can, only that apparently we do anyway.

I don't think we should take things for granted on behalf of the reader. If you include any semantic element in defining a formal language, you can't use it to reason. Perhaps this is the issue? If you are not using the formal language to infer from one formula to another it doesn't matter at all? Because in the context of a formal system it has to be this way or it isn't a deductively sound system. Pontiff Greg Bard (talk) 19:35, 5 October 2009 (UTC)

The point of the sources I gathered was to document the standard definition of a formal language as any set of strings in a fixed alphabet. Do you dispute either of the following?

• There are several textbooks on formal languages that explicitly define a "formal language" as any set of strings over an alphabet

Why would I dispute it, it does not refute my point at all. "Any strings" means the same thing as "any strings regardless of their meaning."

• "The set of formulas in the signature of Peano arithmetic that are true in the standard model" is a set of strings over a finite alphabet

I wouldn't refute that either, it seems to be a sentence that makes sense and is true... however it also does not refute my point at all. It may be the case that the "formal language" being used is required to be defined only syntactically, and that you are in reality dragging a interpretation of a distinct, but apparently identical formal language into the picture with this fallacious move. You can't be defining the formal language at this point if you are already using it and saying what is true or not in the language. It must be a distinct formal language being used which is defined only syntactically, and only later down the road are you able to say anything about "true in a standard model". You can say they are the same, one, and identical; they can have all the same formulas in practice too; but if it is only that way by accident it isn't a formal language. If you define it the way you have, you do not have a deductively valid system. I'm sorry Carl, I don't see any way out of this other than to understand it. It absolutely is circular the way you have it.

It is true that Hunter does not follow the common definition, but (as I have been saying) this is apparently simply an idiosyncrasy of Hunter's. It doesn't mean that the majority of sources about formal languages are ignoring something. If anything, it means that Hunter has ignored the definition of "formal language" that is commonly used in books about formal languages. — Carl (CBM · talk) 19:44, 5 October 2009 (UTC)

It seems you are falling back on impugning the source. I don't agree that Hunter is idiosyncratic. I sought out my own copy because he was covering the material I was interested in after reading many other sources. I find his usage quite consistent with a lot of others. Hunter has quite a bibliography in the back as well. I think there is just a different body of literature out there for philosophers than there is for mathematicians. The attitude always seems to be that the philosophers are pretenders, when in reality that is not the case (especially in this particular case of deductive integrity). On certain issues the philosophers are going to deserve the final say, and on some issues the mathematicians deserve the final say. In the end it is a matter of giving each their due. I hope you are well Carl. Pontiff Greg Bard (talk) 20:41, 5 October 2009 (UTC)

If you argue that Hunter agrees with other texts, can you point to any other books, beside Hunter, who claim that a formal language is not just any set of strings, but only a set of strings that can be defined "without reference to their meaning or semantics, either formal or informal."? I went to the trouble of pointing out several books that do not make any such restriction. Moreover, those books are explicitly on the topic of formal languages, unlike Hunter's book. — Carl (CBM · talk) 22:07, 5 October 2009 (UTC)

One thing that may be confusing you is that, in the example of true arithmetic, there are two formal languages in play.

Formal language 1: the set of all well-formed formulas over the signature of Peano arithmetic. This formal language is syntactically definable.

Formal language 2: those elements of formal language 1 that happen to be true in the standard model of Peano arithmetic

So there is no circularity in the definition of language 2: it is a well-defined subset of the already well-defined formal language 1. On the other hand, there is no possible syntactical definition of language 2. If there were such a definition, then language 2 would be definable within Peano arithmetic, which is impossible. This is why Hunter's definition disagrees with the definition presented in the texts quoted above. — Carl (CBM · talk) 22:07, 5 October 2009 (UTC)

Carl, if you now agree with me that you were talking about what is in fact two languages, you actually have to go back and show that the initial one has any non-syntactic elements in its definition. It is very clear that the second one does, so that does not refute the point at all (still). It appears very much as a shell game to me, only why are you taken in by it? The book I am reading now is consistent with formal languages being uninterpreted until given an interpretation. This guy Sider has posted most of his book online. Check out pages 4, and 41, and the rest as well. It is all consistent with what I am saying.Pontiff Greg Bard (talk) 22:22, 5 October 2009 (UTC)

Could you explain how language 2 being a formal language is consistent with the claim that every language can be defined "without reference to their meaning or semantics, either formal or informal."? — Carl (CBM · talk) 00:34, 6 October 2009 (UTC)

The fact that there is any need to split the analysis into two languages is for what reason? It is so that there exists a formal language which is only syntactically defined. THAT is a formal language. The second one which depends on what is "true in the standard model" is not a formal language. This is consistent with what I was saying. I never said that number 2 was a formal language. I also think an understanding of what "formal" means is instructive. It's the language that only contains the forms of the expressions, not any meaning, etcetera. It would seem to be a fundamental part of what it means to be a formal language. Did you take a look at that online book? Would you now say that it is also idiosyncratic? Pontiff Greg Bard (talk) 22:07, 6 October 2009 (UTC)

Sider seems to be confused about formal languages. It seems clear that they are called "formal" to distinguish them from natural languages, which is necessary especially for the following two reasons: (1) They are a purely syntactical notion in the sense that any semantics is not part of the formal language, but something existing outside it. (Your extremist reading that such a semantics may not even be used to define the language is absurd and totally inconsistent with general mathematical practice.) (2) Also in contrast to natural languages, they are well defined. A single word either belongs to the language or not. We may not know whether it belongs to it, but that's a different matter. What can't happen is that status of a word as part of the language or otherwise depends on a speaker's mood, or changes through the invention of a neologism. This is my only attempt to explain this to you, for the reason given below. Hans Adler 23:33, 6 October 2009 (UTC)

Sider does not give any definition of "formal language" in general that I can see (particularly not on page 4 or 41, but I tried to scan the rest as well). On the other hand, Sider is focused on just a few particular formal languages, rather than formal languages in general. This is why I did not look to mathematical logic books in my list of references above, because they also are unlikely to need a definition of formal languages in general. — Carl (CBM · talk) 01:40, 7 October 2009 (UTC)

This is getting beyond ridiculous. Gregbard, you have no right to exploit the extreme patience of Carl, a subject matter expert and a voluntary contributor to Wikipedia, in this way. If you want to learn logic, take a philosophy or mathematics course at a university, or pay for a private tutor. Or pay Carl for his tutoring. But don't force him to tutor you for free. Wikipedia is not a suitable place for Randy to get history lessons from a professor of ancient history, and it is not a suitable place for you to get logic lessons from Carl.

Surely there is a point where an editor has demonstrated sufficient incompetence concerning a subject that they can be shown the door if they bother the experts in this way. ("The only book I trust, although I can't point to any particular reason to do so, disagrees with everybody else and therefore we have to follow this book." And similar nonsense.)

It does not matter whether Hunter got this definition wrong, whether he tried to introduce a new one different from the usual one (very unlikely I would think), or whether he was merely trying to explain that "a formal language is just a set of words" to non-mathematicians in words that this particular non-mathematician managed to interpret in an extremist way that has nothing to do with Hunter's intention. Carl is right and you are wrong, and every half-competent mathematician or computer scientist can see that with (or in many cases even without) a small amount of research. If you don't understand why it is your problem, and you have no right to make it Wikipedia's problem. Hans Adler 23:23, 6 October 2009 (UTC)

Uncivil Hans as usual. The only person demonstrating impatience is you. Very presumptuous too. Pontiff Greg Bard (talk) 02:13, 7 October 2009 (UTC)

As I was saying, Language 2 certainly meets the definition of "any set of symbols over a finite alphabet". That is my point: language 2 meets the definition of "formal language" that is used by the vast preponderance of texts about formal languages. Sider does not appear to directly give a definition of "formal language", unlike the sources I cited. — Carl (CBM · talk) 01:40, 7 October 2009 (UTC)

...and that makes complete sense if you take for granted that "symbols" means "uninterpreted symbols". You think its okay to take that for granted, and I do not. Sider does face up to this issue rather than ignore it so he doesn't take it for granted, same for Hunter. Be well Carl. Thanks for your patience. Pontiff Greg Bard (talk) 02:25, 7 October 2009 (UTC)

I do not know what you mean by "makes sense". It seems to me that Language 2 being a language flatly contradicts Hunter's definition, which is why I removed Hunter's definition from the lede. None of the references I pointed out makes any distinction between "interpreted" and "uninterpreted" symbols in the definition of a formal language. — Carl (CBM · talk) 02:32, 7 October 2009 (UTC)

A formal language is the same whether or not the symbols are interpreted. I don't so how any rational person (even Hunter) can come to a different conclusion. — Arthur Rubin (talk) 02:34, 7 October 2009 (UTC)