Jump to content

Talk:Theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
(Redirected from Talk:Formal theorem)

Grothendieck's universes

[edit]

The sentence "A notable exception is Wiles's proof of Fermat's Last Theorem, which involves the Grothendieck universes whose existence requires adding a new axiom to the set theory" is completely misleading and should be removed.

First of all, even without entering a technical discussion, it cannot be in the second paragraph of the page, giving the idea that this is an important point. FLT is proved in any reasonable mathematical sense, it is accepted by the mathematical community without any doubt.

Moreover, the sentence is almost entirely false, see for example all the discussions in https://mathoverflow.net/questions/35746/inaccessible-cardinals-and-andrew-wiless-proof. It's not true that "many specialists think that it is possible [to remove the use of Grothendieck's universes]". The reality is that all the specialists that care about this have checked and are sure Grothendieck's universes can be avoided here, and those who don't care simply don't care about logical foundations.

Removed by me as WP:OR

[edit]

I removed the sentence "A notable exception is Wiles's proof of Fermat's Last Theorem, which involves the Grothendieck universes whose existence requires the addition of a new axiom to the set theory.[a]" as WP:OR. The author is free to revise to include reliable external references. Erxnmedia (talk) 12:52, 16 May 2023 (UTC)[reply]

I have edited the revert to reflect the current state of play: McLarty's old article was cited, but not a more recent article of his reproving the universe-dependent ingredients in a way that doesn't use universes. I agree that this shouldn't be in the second paragraph, because the situation is more subtle than a generic WP reader is prepared for. But keeping it in a discussion later about what a theorem really relies on might be ok. 110.174.47.229 (talk) 22:50, 16 May 2023 (UTC)[reply]

Fermat's Last Theorem is not special in this regard. Enormous amounts of modern number theory and algebraic geometry make use of Grothendieck universes on a superficial level. And everyone in the field agrees that any particular statement can also be established without universes by taking a bit more care. (Case in point: the Stacks Project is a 8000-page reference text on algebraic geometry, and it carefully avoids universes. But many other texts don't bother taking this care.) The entire discussion of ZFC vs ZFC+u should not be so high up on this page. It would make much more sense to have it in a later section. — Preceding unsigned comment added by 132.230.196.70 (talk) 05:49, 17 May 2023 (UTC)[reply]

Article does not correctly cover theorem in logic

[edit]

The article as it stands seems to me to be trying to put too much into a single article. The lede describes what mathematicians normally consider to be a theorem in mathematics, but in logic it means something different. In logic, a theory is simply a set of sentences, usually closed under logical consequence, and a sentence that is a member of that set is a theorem of that theory. As such, any sentence can be a theorem of some theory or other. It doesn't have to be true (the theory might be unsound), and it doesn't have to be provable (the theory might be unaxiomatizable). If I am reading the history correctly, this article was merged with a different one about formal theories. I would suggest that this merger has had unfortunate consequences, and it should either be undone, or the article should be split into separate sections. As it stands, the article contradicts the article Theory_(mathematical_logic) Dezaxa (talk) 13:21, 22 September 2021 (UTC)[reply]

You must be more accurate and quote the sentences of one article that are contradictory with sentences of the other article. If there are errors in one of the articles, they must be clearly specified. In any case splitting an article is a wrong way for fixing errors.
As far as I understand, you are summarizing a particular point of view on mathematical logic, without any source allowing verifying whether this point of view is a common one (see WP:NPOV). As far as I know, it depends on the context (the logic that is used) whether "theorem" is a synonym of "statement" (well formed formula) or if it is the result of a deductive reasoning (proof). This variability is clearly stated in the article: However, according to Hofstadter, a formal system often simply defines all its well-formed formula[s] as theorems. [...] Different sets of derivation rules give rise to different interpretations of what it means for an expression to be a theorem.
So, I strongly oppose your suggestion of undoing an old merger. Another reason for that is that following your suggestion requires an editor who well knows the rules of Wikipedia, and has a wide knowledge of mathematical logic. I doubt that there is an editor who has these competences and is willing doing this job. D.Lazard (talk) 14:19, 22 September 2021 (UTC)[reply]
I don't think Dezaxa is suggesting that all well-formed sentences are theorems, but only a particular subset of them closed under logical consequence. --Trovatore (talk) 16:49, 22 September 2021 (UTC)[reply]
No theory closed under logical consequence can be "unaxiomatizable"; you can just take all of the statements of the theory to be axioms. In that case they are all provable, having proofs with one step.
It's true that the axioms don't have to be true in the standard interpretation of the language, if there is one, or even in any interpretation in the case of an inconsistent theory. That's a valid criticism of the opening sentence, which currently suggests that axioms need to be "generally accepted"; there is a strong tradition of using axioms that are believed to be false in the standard interpretation (e.g. axiom of constructibility, axiom of determinacy) as means toward an end.
I think this point is too confusing to treat in detail in the first sentence. It could be treated in the body of the article, with an explanatory footnote added to the first sentence to avoid lies to children. --Trovatore (talk) 16:49, 22 September 2021 (UTC)[reply]
The very first sentence of the article Theory_(mathematical_logic) correctly states that a theory is a set of sentences in a formal language. The sentences that make up a theory are its theorems. This is standard stuff that you will find in any textbook of mathematical logic. As such, any wff can be a theorem of some theory or another. It does not have to be true and it does not have to be provable. When I said 'axiomatizable' I should perhaps have said 'recursively axiomatizable' - it is fairly common to say simply 'axiomatizable'. But in any case, an axiom set is required to be decidable, so an undecidable theory does not axiomatize itself.
What counts as a theory does not depend on context, or on the logic that is used. If you close a set of sentences under the consequence relation of a non-classical logic, for example, you just get a different theory.
I agree that demerging the article is not a good option, but the lede should make it clear that it relates only to how the word theorem is used in mathematics, not in logic. The section on logic could then make it clear that within logic, theorem has a much broader sense. The relation between the two seems to be that mathematicians are typically only concerned with theorems that are true and/or interesting. Theories that are unsound and banal also contain theorems. Dezaxa (talk) 21:20, 23 September 2021 (UTC)[reply]
"An axiom set is required to be decidable." Hmm? Who says? --Trovatore (talk) 00:57, 25 September 2021 (UTC)[reply]
Curiously, some sources require an axiom set to be decidable and some don't. Mendelson has: "Most often one can effectively decide whether a given wff is an axiom, in which case a formal theory is called an axiomatic theory". In any event, though one can say in a trivial sense any theory proves its theorems, we normally think of a proof of a theorem as being some non-trivial derivation proceeding from a recursive set of axioms. In this stronger sense at least, not all theorems are provable, since not all theories are recursively axiomatizable. Also, any inconsistent theory has all wffs as theorems, but we wouldn't normally describe such theorems as having been proved. Dezaxa (talk) 19:27, 26 September 2021 (UTC)[reply]
Well, whether they've "been" proved or not, they're certainly provable. This does seem to be going off on a tangent, though.
I think there are two separate issues here. One is that the language in the lead currently requires axioms to be "generally accepted", which isn't always true, as sometimes axioms are added instrumentally or provisionally. The other is the disconnect between theorems as formal strings and theorems as propositions; that is, the meanings of those strings. For example, it's a theorem of Peano arithmetic that every natural number is a sum of four squares, but (after some macro expansion that I'm not going to bother with) one formal theorem of formal PA is the string ""
The second issue is probably the original motivation for the formal theorem (or whatever it was called) fork of this article, and in some sense it's a fair point, but that article frankly struck me as a POV fork, and the distinction is not one that mathematicians, or even mathematical logicians, really linger over in practice; the formal theorem is usually just treated as a codified way of expressing the proposition.
I think it would be useful to provide an explanatory footnote to address the first issue. The second issue could possibly be treated somewhere in the body somewhere, but I don't think it's necessary to talk about it in the introduction. --Trovatore (talk) 20:12, 26 September 2021 (UTC)[reply]

I have rewritten the beginning of the lead in a more encyclopedic tone, and moved its remainder in a specific section called § Epistemological considerations. IMO, most of this section and of a large part of the article consists of WP:OR and nonneutral point of view, and deserve to be completely rewritten. D.Lazard (talk) 07:26, 28 September 2021 (UTC)[reply]

The section on theorems in formal logic still needs a substantial revision. I'll have a go at it over the next couple of days. The section called Derivation of a theorem seems to me to be superfluous. One of the maddening problems with this area is that some writers conflate theory with formal system, which seems to me distinctly unhelpful, if not actually just wrong. I agree that the section on Epistemological considerations is odd. Dezaxa (talk) 08:01, 29 September 2021 (UTC)[reply]

Thanks D.Lazard; generally nice work. I have some concerns about a couple of bits:
In the main stream of mathematics, the axioms and the inference rules are implicitly those of Zermelo–Fraenkel set theory with the axiom of choice. Generally, an assertion that is explicitly called a theorem is a proved result that is not an immediate consequence of other known theorems.
I think this over-reifies the informal convention that the assumptions you don't have to mention explicitly are ZFC specifically, and particularly suggests that "main stream mathematicians" (by the way, "mainstream" is just one word) think about ZFC very much. Mathematicians who prefer to think of themselves as formalists will sometimes suppose that they're just generating theorems of ZFC, but they hardly ever call out, say, an instance of the Replacement axiom. Moreover, ZFC was not even formalized until the early 1900s — do we really think that the notion of "theorem" has fundamentally changed since the 19th century? I don't.
And finally, it's not even true in practice. Take Fermat's last theorem — it was initially proved using Grothendieck universes, which can't even be formalized in ZFC (they require a mild large-cardinal assumption). As far as I know no one has yet succeeded in removing this assumption, though I haven't kept up on details. And yet few dispute that it's been proven.
The other bit that I have some issues with is the discussion of conjectures, which assert that FLT was "not a theorem" before the proof was found. But of course it was always a theorem; we just didn't know the proof. --Trovatore (talk) 17:50, 29 September 2021 (UTC)[reply]

I agree with Travatore that it is overstating the matter to say that ZFC is implicit. Perhaps we could swap the word 'implicitly' for 'commonly'. The sentence "In logic and other areas of mathematics, an assertion can be called a theorem only if the deductive system and the axioms (that is the logical theory) are explicitely specified, since the possibility of proving the assertion may depend on the used theory." - really does not make much sense. In logic, the set of theorems is the theory. I can modify this when I have done revising the section on theorem in logic.
What I have learned from consulting a number of texts is that there are two distinct ways of defining theory in logic. The more popular camp, which includes Enderton and many others, is that a theory is just a set of sentences, usually closed under logical consequence. The other, which includes Mendelson, conflates theory with formal system, making a theory a structure containing a formal language, a deductive system and a set of non-logical axioms. The relationship between them seems to be that a theory in the first sense is the set of sentences proved by a theory in the second sense, i.e. it is the extension of it. The problem now is that if I give both definitions of theory, this article will become inconsistent with the Theory_(mathematical_logic) article, which goes with the first definition. Looks like I may need to edit that one too. Dezaxa (talk) 20:12, 29 September 2021 (UTC)[reply]
To be honest I don't think it's particularly important to distinguish between those two senses; they're pretty much equivalent. The other two questions (whether axioms need to be true or otherwise "accepted", and whether theories are collections of meaningful propositions or simply of uninterpreted strings) are probably more important to treat somehow in this article. --Trovatore (talk) 20:39, 29 September 2021 (UTC)[reply]
I can add something about that. In proof theory, at least, theories certainly can be collections of uninterpreted strings, though for ordinary working mathematicians this is not how they would use them. Another slight difference I have noted with different accounts is that some authors consider a theory to be closed under semantic consequence (), and others under derivability (). The first makes it easier to separate a theory from a formal system, but at the cost of making it so that a theory without a formal semantics does not actually qualify as a theory. The second requires a deductive system. Of course if the underlying logic is sound and complete then the two are extensionally equivalent. Dezaxa (talk) 01:07, 30 September 2021 (UTC)[reply]

Recent edits

[edit]

@D.Lazard - your revision to the lead on 3 October is incorrect, and unless you can give a good reason, I propose to revert it. 1. What is an 'assertion'? Is it the same as a statement or a sentence or what? 2. You are conflating the concept of a formal language and a theory. They are completely different things. A language consists of the rules that determine what qualifies as a wff. A theory is a set of closed wffs (sentences). A theorem is an element of a theory. Theorems are not deduced "from the basic terms of a language". 3. Deduction rules are not "part of" a theory. A theory is a set of sentences, a rule is not a sentence, so a rule cannot be part of a theory. Deduction rules only come into the picture when a theory is closed under a derivability relation. Many accounts of theories define a theory to be closed under semantic consequence, which means they can be defined without reference to a deduction system. 4. The sentence about Gödel's incompleteness theorems does not belong in the lead, and in any case is too inaccurate to be useful. Dezaxa (talk) 05:05, 4 October 2021 (UTC)[reply]

The disputed edit consisted of replacing a paragraph recently added by Dezaxa. This Dezaxa's paragraph does not respect the guidelines of WP:LEAD, WP:MATH#Article introduction and WP:TECHNICAL. Also, it does not respect the policy of WP:NPOV.
In other words Dezaxa's paragraph is not written in order to be understandable by readers who are not specialists of logic, and, for people who can understand it, it gives a highly partial view of theorems in mathematical logic. Examples of these issues: A reader of this article is not supposed to know the meaning of "formal" in mathematical jargon; this word is used twice in the first sentence, linked to articles that do not exply this term. The concept of formal language is defined in the linked article, but it is a technical tool that should not be needed here. Moreover, the paragraph is highly biased, as it suggests that the theory of formal languages is the only part of logic that deals with theorems, and that logic does not studies proofs of theorems (statements that are not theorems have not their place in the suggested formalism). Also, the paragraph suggests that logic is concerned only by syntax, and that semantics is outside logic. Also, in the part of the lead that is related to logic, it is essential to mention Gödel's incompleteness theorems, and they do not fit in Dezaxa's paragraph (indeed, as they belong to logic, and they are fundamental theorems about theorems, they must mentioned in the lead of an article about theorems).
About may version: My version can certainly be improved. In particular I agree that "assertion" can be replaced by "statement". Also, I'll slightly modify the current version of the article for being coherent with the linked article. D.Lazard (talk) 08:24, 4 October 2021 (UTC)[reply]
@D.Lazard - your revision is still incorrect, and your comments about my paragraph are completely unfounded. My paragraph was no more technical or jargon-laden than the one you replaced it with. In fact it was less so. You complain that I used the word 'formal' twice, when your paragraph uses 'formalized', 'well-formed formulas' and 'formal language'. You say the concept of formal language is not needed here, but you have referenced it yourself. My paragraph does not give a partial or biased view of theorems. In the body of the article I have referenced eight standard textbooks of mathematical logic that support the account I have given. I did not anywhere say that "logic does not study proofs of theorems". Also, I did not say that logic is concerned only with syntax: in fact I said the opposite in the body of the article and left the lead neutral as between syntax and semantics. You removed the point about theories being sets and added the footnote that "this is avoided here for clarity and also for not depending on set theory" even though the second paragraph of the lead, which you wrote, says that the axioms and inference rules used to prove theorems are "almost always those of Zermelo-Fraenkel set theory". I don't believe it is essential to mention Gödel's incompleteness theorems in the lead, but if you are going to do it, they need to be stated correctly. Dezaxa (talk) 17:24, 4 October 2021 (UTC)[reply]
The problem is not what you wrote, it is what a non-expert reader understands, and what is suggested to them by the formulation. If you talk only of syntax and if you dont explain the reason for which the syntax has been elaborated (that is proving theorems about theorems), your text will not be useful to anybody who has never followed a course of logic, and will definitively be non convenient for an encyclopedia, even if it is correct for a course introduction.
Similarly, Gödel's theorem are among the results that every mathematician should know of. They must be mentioned and linked to in the lead, but the lead is not the place for their formal statement, specially if the article about them is linked to. Again, WP:Wikipedia is not a textbook.
Well, let wait the opinion of other editors. D.Lazard (talk) 18:16, 4 October 2021 (UTC)[reply]

ZFC and Grothendieck universes again

[edit]

First, let me say that I would love love love for it to turn out that the proof of FLT depends essentially on Grothendieck universes and inaccessible cardinals. If you want to get me something for Christmas, make that be true :-)

But I gather that the folks most in a position to have an opinion think that this is very unlikely. The machinery is developed using Grothendieck universes, and it's bothersome to work around it, which is why no one has technically done it. But that is not particularly surprising, contrary to the footnote that claims it's "astonishing", or at least not particularly more surprising than the already possibly surprising fact that you can find out new things about the natural numbers by reasoning with the real numbers, already a large conceptual leap higher.

The reason that this is an issue at all is the language surrounding ZFC, which as I've mentioned above, I find problematic for other reasons. The notion of "theorem" has not changed all that much since Euclid, but ZFC was only laid out in the 20th century. I think that ZFC is a convenient fallback for mathematicians who want to think of themselves as deriving results purely in an axiomatic system, but don't really want to bother with the details. Don't get me wrong — I'm a set theorist by training, and the formalization of ZFC is a signal accomplishment. But I doubt that it merits calling out as part of the background meaning of "theorem". --Trovatore (talk) 05:58, 5 November 2021 (UTC)[reply]

Since this comment was posted, the article has been changed a couple of times so that it now includes a brief treatment of Wiles proof of Fermat's last theorem and the Grothendieck universe, including a recent citation asserting that a work-around was found to avoid depending on the machinery based on the Grothendieck universe. i.e. Wiles revised proof follows from ZFC.
That all appears to be correct, and supported by citations. But to my eye, it seems like an unnecessary distraction this early in the article. Mainstream math is usually based on ZFC, but there's an exception that is not really an exception since someone has found a work-around. It just doesn't make sense to include that material at that point in the article.
Also, my understanding is that a large portion of Algebraic Geometry depends on the Grothendieck universe - that would seem to be a better example of an exception to "mainstream math is based on ZFC" than the non-example of Wiles proof. And if we're going to discuss alternatives or exceptions to ZFC, what about the continuum hypothesis or Godel Bernays set theory?
My take is that the article reads better without all that side discussion:
In mainstream mathematics, the axioms and the inference rules are commonly left implicit, and, in this case, they are almost always those of Zermelo–Fraenkel set theory with the axiom of choice (ZFC), or of a less powerful theory, such as Peano arithmetic. Generally, an assertion that is explicitly called a theorem is a proved result that is not an immediate consequence of other known theorems. Moreover, many authors qualify as theorems only the most important results, and use the terms lemma, proposition and corollary for less important theorems.
If we want to go into all that, my take is to treat it later in the article, although it appears to be well covered elsewhere so I don't really think it's necessary. Mr. Swordfish (talk) 12:21, 17 May 2023 (UTC)[reply]
I spoke too soon about it being well covered elsewhere. The Wiles's_proof_of_Fermat's_Last_Theorem article doesn't mention the Grothendieck universe or whether it can be proven from ZFC. Mr. Swordfish (talk) 14:30, 17 May 2023 (UTC)[reply]
The side discussion is placed here for explaining "almost always". Nevertheless, I agree that it does not belong to the text of the lead. This is why I have moved a less technical version of the side discussion into an explanatory footnote. D.Lazard (talk) 14:32, 17 May 2023 (UTC)[reply]

Possibly missing (and conflicting partial) definition of a theorem in logic

[edit]

In the section Theorem#Theorems in logic one expects a definition of a theorem in logic but it seems that that is missing and that the presentation may be misleading. One finds the informal sentence: «In mathematical logic, a formal theory is a set of sentences within a formal language. A sentence is a well-formed formula with no free variables. A sentence that is a member of a theory is one of its theorems, and the theory is the set of its theorems. »

This defines a theory in mathematical logic and says that all members of a theory are theorems of that theory, but it does not define logical theorems - though in the following sentence it is explained that « Usually a theory is understood to be closed under the relation of logical consequence. » but this does not define "theory" or "theorem". In fact the last part seems unconventional and conflicting with the rest of this wiki page: Enderton in his textbook on logic, p110 defines « Then for a set of formulas , the theorems of will be the formulas which can be obtained from by use of the rule of inference (some finite number of times). » Theorems according to Enderton's book thus include wff which are not sentences, ie which have free variables, thus since Enderton uses the same definition of "theory" as here there exist a theory which does not contain all its theorems, in particular a theory which is not the set of its theorems. The informal definition in this wiki page seems to correspond to Enderton's definition: a theorem is any logical consequence of a set of formulas, it may contain free variables.

I thus suggest defining the formal concept of theorem in logic directly, and separately defining "theory" in logic. I suggest using Enderton's definitions - which apply to all quantified logics, with the already present caveat that logical consequence can be replaced by semantic consequence - and noting explicitly that theories do not necessarily contain all their theorems, but in general only contain the closed theorems - those which are closed formulas, sentences. Sorry for the nitpicking, if i came to this page it is because the page on Presburger arithmetic uses the undefined term "nontheorem" to define "decidable", and that leads in that page to a nonnegligible ambiguity about the notion of decidable theory - which does not have to be complete, but the PrA page left this ambiguity and that on "nontheorem" unsettled as PrA is complete, so i added a note near "nontheorem" to clarify.

There are surely better presentations than i suggest. It may be useful to survey classic logic textbooks and present all the definitions they use, ideally with a short presentation of pros, cons, and typical use cases of each notion - like why a theory is usually defined as a set of closed formulas. Plm203 (talk) 21:23, 13 September 2024 (UTC)[reply]
Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).