Talk:Completeness

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class High Priority  Field: Foundations, logic, and set theory

Contents

[edit] completeness

Would it not be a good idea to have Completeness as a dictionary style definition, leading off to:

  • Completeness (metric spaces)
  • Completeness (measures)
  • Completeness (logic)

etc? -- Anon

Yes, I agree that this would make a good disambiguation page. However at this point, it's not really necessary; the metric (or uniform) space concept is the only one that has had enough written about it to form an entire article. Thus, I have created Complete_space, which currently redirects here, in anticipation of this, and we can link to that page instead of this if we wish. However, I don't think that it's necessary to move the contents of this article over there, or to move links to this article over there, until we reach the point that there is either:

  • a great deal written about completeness in some other article (such as the article on lattices) that justifies branching it off to a new article, or
  • a great deal written about one of the other sorts of completeness in this article that justifies splitting this into two articles.

Then we can do the transition; otherwise, the move may be harmless but is largely a waste of time. IMO. -- Toby Bartels, Monday, June 10, 2002

The main content of this page may need to be moved to complete_metric, or something similar, but it would not be sensible to do this until Pages_that_link_here is fixed. -- Anon

If and when we move it, it should be to Complete_space, since we'll want to discuss other notions of complete spaces (complete uniform spaces, maybe even complete Cauchy spaces) under the heading Generalisations. — Toby Bartels, Sunday, July 14, 2002

Given that Complete measure is a separate article, I'm doing the move now. -- Toby 23:40 Feb 20, 2003 (UTC)


I removed

If V is separable, it follows that any vector in V can be written as a (possibly infinite) linear combination of vectors from S.

Linear combinations are by definition finite, so we would have to say a bit more to make this statement precise. Even then, I'm not sure that it is true in general (it surely works in Hilbert spaces though). AxelBoldt 18:12 29 May 2003 (UTC)

Our article now discusses infinite linear combinations. -- Toby Bartels 09:43, 26 Aug 2003 (UTC)

I agree that if non-mathematical usages are to be included, that should be a separate page. But perhaps in that case, this page should be moved to "Completeness (mathematics)", or, if that's a bit too narrow, "Completeness (mathematical sciences)". Michael Hardy 01:57, 15 Sep 2003 (UTC)

Michael, you said "Not all ordered fields are metric spaces; this is not merely a special case of the metric space case." You are correct, of course, but the concept of a Cauchy sequence is still meaningful in nonmetric ordered fields. Every ordered field has a unique subfield isomorphic to the rational numbers, so a Cauchy sequence is just one in which the difference between every pair of elements for some point onward corresponds to a rational number less than the given real number.

This won't work, (I'm thinking this out, even as I type.), since the differences between the elements in a Cauchy sequence need not be rational. It would work if instead of the subfield isomorphic to the rationals, we used the largest subfield isomorphic to a subfield of the reals. But it's not clear to me that such a subfield must always exist, or that it's always unique.

Please revert if what I wrote was Patent nonsense. But there is a connection between the two definitions, which should be made clear somehow. -- Daran 06:14, 15 Sep 2003 (UTC)

[edit] Proof theory subsection

The subection currently reads:

In proof theory and related fields of mathematical logic, a formal calculus is said to be complete with respect to a certain logic (i.e. with respect to its semantics), if every statement P that follows semantically from a set of premises G can be derived syntactically from these premisses within the calculus. Formally, implies . Especially, all tautologies of the logic can be proven. Even when working with classical logic, this is not equivalent to the notion of completeness introduced above (both a statement and its negation might not be tautologies with respect to the logic). The reverse implication is called soundness.

Two things: (i)This notion is not really native to proof theory, although it originated there, but is rather one of the fundamental ideas of model theory. (ii)Completeness is not restricted to logic; it makes perfect sense to talk about completeness wrt to any first-order theory. ---- Charles Stewart 11:52, 29 Sep 2004 (UTC)

[edit] tautologies

Lambiam, the goal here is to account for the properties of the logical system without regard to meaning or semantics. This is the primary, fundamental, canonical definition of completeness. What you say is true (of semantic completeness), however, that formulation of completeness is a little further down the road from syntactic completeness, so to speak.

Strictly speaking, it is not necessarily true, as you have worded it, that: "A logical system has "completeness" when all true sentences (given the semantics of the logic) are theorems, whereas a formal system has "soundness" when all theorems are true sentences." ...because we can talk about the completeness of logical systems without regard to semantics (the idea that certain sentences are true or false) at all. Pontiff Greg Bard (talk) 12:30, 27 January 2008 (UTC)

How would you determine whether (for example) the formula [a*](p → [a]p) → (p → [a*]p) is a tautology? The definition given in our article Tautology applies only to a rather narrow set of simple logics.  --Lambiam 17:42, 27 January 2008 (UTC)
"Tautology" is the more general term here. All "true sentences" are tautologies, however not all tautologies are "true sentences." That's a good quiz question. It looks like one of the principles of modal logic. That's a quantifier, not some kind of Kleene star right? I'm going to get back to you at some point for your example. It is the formation of the symbols, "→", "p", etc, that determine whether it is a tautology or not, not any interpretation of, for instance, p being true. So for instance, if your example is a tautology, then it is a token or the type of tautology that is:
[a*](x → [a]x) → (x → [a*]x)
I haven't taken a close look at tautology yet. The uninterpreted tautology may need elucidation. Be well, Pontiff Greg Bard (talk) 00:14, 28 January 2008 (UTC)
It is a theorem that is an easy consequence of axiom A6 of dynamic logic. The [...] is sort of a modal operator, and the argument like a* is from a Kleene algebra, where the * is the Kleene star.
I don't understand your sentence "it is a token or the type of tautology that is ...".
Can you give a source for a definition of "tautology" in the sense you understand it, and an example of a tautology that is not a true sentence? Or do you just mean that "A = A" is not true because "A" is a variable?
 --Lambiam —Preceding comment was added at 06:32, 28 January 2008 (UTC)
If that is a kleene star, I really don't know much about its properties. I cannot vouch for the accuracy of the above statement on those grounds. However, also, Please forgive my error. It's supposed to be:
"...it is a token of the type OF tautology that is..."
The things we are talking about are abstract objects. They are "types" of things. They do not exist in any particular place or time. We only see tokens of them. The ink on the paper, or the actual chalk on the board may also be a "tautology." However, it is the properties of the abstract version that we are talking about here.
I think your statement "...do you just mean that "A = A" is not true because "A" is a variable?" is another way of looking at the idea I am trying to explain. These are syntactic qualities. I will look further into these matters and try to get a good example. In lieu of that good example, I will provide the principle that makes me know that it exists: A formal system is complete with respect to the property of tautologousness iff every sentence that is a tautology is a theorem. (This is from the second definition in that bullet list). There do exist systems that are not complete with respect to the property of tautologousness. I think the FS system I described at Talk:Theorem qualifies, although I think there are better examples out there. Be well, Pontiff Greg Bard (talk) 07:54, 28 January 2008 (UTC)
If by FS you mean the system with theorems of the form †∗m+1†∗n then I must confess I haven't the foggiest idea what it means for a string of daggers and asterisks to be a tautology, and so your statement that this system may qualify as not being complete in your sense of the term carries no content for me. I am still waiting for (1) a source for a definition of "tautology" in the sense you understand it, and (2) an example of a tautology that is not a true sentence.  --Lambiam 12:56, 28 January 2008 (UTC)
I guess my next question is what does "carries no content for me" mean? Does it mean a) you just would like more clarification, b) you are indifferent to the clarifications I have made, and will be going ahead with your version, or c) you understand it as trivial, or d) something else? The other question I have is how long are you willing to wait for (1) and (2)? I think the fact that this type of formula can be a non-tautologous theorem should really inform and enhance your notion of tautology. That's is what I would like for the readers. Pontiff Greg Bard (talk) 15:10, 28 January 2008 (UTC) Pontiff Greg Bard (talk) 15:10, 28 January 2008 (UTC)
It carries no content for me in the sense that I am unable to assign meaning to that string of words, presumably in the same way you can't extract meaningful content from a statement that "the rights of cloud precede mutation". In technical terms, the utterance is inoperative as a truthbearer.
How long do you expect me to wait? Given the meaning of completeness that I know and see in the literature, the article is wrong, but you reverted my fix with arguments that I don't comprehend.  --Lambiam 18:35, 28 January 2008 (UTC)
Well Lambiam, let me first say that I appreciate your care and attention to these matters. Our discussion has been a pleasure on my part. As you may know, I am not always very diplomatic, so please forgive my forthright conjecture. I can tell you have studied this subject well. It is clear that you understand what you say you understand, and you are forthright on these points where you are not 100% clear. However, I think what you do understand is not permitting this new understanding. This actually is the more fundamental understanding, not trivial at all, perhaps you have been mathematically prejudiced.
The formal language with stars and daggers can form theorems, as described at Talk:Theorem. A good way to understand these things is like moving boxes. If you have a map (or a checkerboard or whatever), and some rules you can move boxes to some places and not others. The places the rules allow you to move a box is a theorem. Perhaps more appropriate to the analogy, the box is a theorem in some places not others. So this is a totally new understanding of theorem. It doesn't involve "true" or "proved." Calling a box a theorem will certainly seem strange to a mathematician, however this is what is going on behind the scenes. It is not appropriate to say "Well but it isn't REALLY a theorem." That would be missing the point entirely. It is exactly this that is the essence of theorem. This is what it is like to talk about syntax without semantics. The same analogy goes for tautologies, although I found theorem easier to explain.
I hope at some point this results in an "aha moment" rather than impatience with myself. I am only a cab driver, so I am learning a lot more from others than I am contributing. However, these appear to be concepts that mathematicians in general do not care about or, pay attention to, and that is fine. However, it should not be looked upon as foreign or hostile at all. Please look at it as filling in the philosophical perspective. It seems to me that in philosophy classes we are told that mathematicians study this area too, but the mathematicians are not told that we study this area too (or they are told and promptly shrug them off as pretenders --silly).
There are no deadlines on wp, so I don't really have a good answer. The next time I get to the university library perhaps? It seems that the article is tagged for no sources so it really boils down to what we agree on until there are. I guess I could rightly ask you when you will come up with sources for your language too, however I'm not that way. I am quite sure there are sources that support both formulations, however yours belongs a little later in the article because of it involves an interpretation of the pure thing we are talking about. There is no good statement about semantic completeness in the article, so I think your formulation (which I reverted) belongs in under that. However, I do not have a good canonical account, so I didn't put it in there because I could do it justice just yet. Be well, Pontiff Greg Bard (talk) 00:14, 29 January 2008 (UTC)
I have no problem with accepting †∗∗†∗ as a theorem of some logical system. What I don't get is what it means to state that it is, or is not, a tautology.
In the meantime, let me give some references to definitions of soundness and completeness in various texts:
The last of these is particularly interesting because the author uses the terminology "tautological consequence" but makes it explicit in the notation that this corresponds to the semantic notion of entailment, bolstering my contention that being a tautology is a semantic property.  --Lambiam 08:43, 29 January 2008 (UTC)
A semantic tautology is a wff of truth-functional propositional logic whose truth table column contains nothing but T's when these are interpreted as the truth-value Truth. A syntactic tautology is a wff of truth-functional logic whose truth table column contains nothing but T's when these T's are uninterpreted tokens rather than, say, truth-values. The rules for generating the truth table column tell us to use one of these uninterpreted T's in exactly those cases where semantic considerations would have led us to use the truth-value Truth. This can be found at this Glossary of first order logic. The syntactic qualities should be covered first, and then the many and varied semantic aspects should supplement. Like I implied earlier, we are both right. Be well, Pontiff Greg Bard (talk) 20:22, 29 January 2008 (UTC)
Thank you for your recent contribution to effective method. I learned something new about it. Pontiff Greg Bard (talk) 20:39, 29 January 2008 (UTC)

(exdent) May I say that I find the distinction between semantic tautology and syntactic tautology inane? I could likewise define semantic equality and syntactic equality. Take an equation such as 5 + 9 = 2 × 7. Evaluate both sides, using tables of addition and multiplication. If this results in equal numbers, interpreting the entries in the tables as numbers, it is semantic equality. If the same exercise leads to equal strings, interpreting the entries in the tables as strings of digits, it is syntactic equality. Well, the two notions will never give an observable difference, not for these equalities and not for tautologies. The statement that the two always give rise to the same verdict is itself a tautology. We may as well distinguish between normal tautologies, en upside-down tautologies, where the latter are obtained by Australians, New Zealanders, and some yoga practioning logicians. It is somewhat amazing that the author does not distinguish between semantic soundness and syntactic soundness. Whether semantic or syntactic, it doesn't say anything about how to defined the notion for other logical systems than propositional logic. It is hard to imagine a non-semantical method to evaluate quantifications.  --Lambiam 23:39, 29 January 2008 (UTC)

You understand that this kind of supports my whole "mathematical prejudice" theory do you not? You are going to interpret a number as a number, huh? Yeah that seems pretty silly. Only that is not what is going on here. It's not a number until it is interpreted as such, until then it is just a symbol. We are able to move symbols around on paper according to rules, and get other symbols that happen to preserve deductive qualities. This is the level of analysis we seek, because we want to make sure we have a legitimate deductive system, with no presuppositions (as you have made about the so-called "equal numbers" you speak of.) We can see today that Euclid fudged somewhat on the rigor of some of his proofs. I'm sure he thought it was okay at the time. Mathematics is orders of magnitude more complex today, so BE CAREFUL! ...and be well. Pontiff Greg Bard (talk) 15:04, 30 January 2008 (UTC)
I know that I really understand the meaning, but how do I know you are capable of real understanding of the concept of Truth and not just mechanically scanning for a column of uninterpreted "T" symbols? Even if you say you understand, for all I know, your "semantic" interpretation is nothing but pushing symbols around in a neural network. We are really getting into the other minds problem here. The distinction between the two notions of tautology is, however, really mainly silly because they necessarily always coincide. Would you ask someone who states "¬(A ∧ ¬A) is a tautology" to clarify whether they mean a semantic tautology or a syntactic tautology?  --Lambiam 19:03, 30 January 2008 (UTC)
Congratulations, you are now a philosopher. I will look into your answerable question at some point! Be well, Pontiff Greg Bard (talk) 22:20, 30 January 2008 (UTC)

[edit] Making it saner

This page is crazy! It is the Ersatz for the deceptively short disambiguation page for "Completion", mixes completely unrelated subjects, such as auditing, autocompletion, and complete metric spaces, etc, etc. I was originally looking for a link to completion of rings in commutative algebra, in order to add it to one of the articles I was editing, and was nary certain it's not even mentioned. Tells you how easy it is to find stuff here! I strongly propose at least to move out the mathematical uses of "complete" and "completion" that have nothing to do with logic, finances, or philosophy into "Complete (mathematics)", as was proposed by Michael Hardy already 5 years ago. Arcfrk (talk) 08:16, 1 March 2008 (UTC)

This page should be turned into a standard disambiguation page, conforming to the rules of MOS:DAB. Furthermore, it should be merged with Completion (disambiguation), so that the page starts with s.t. like "Complete, completeness and completion can refer to:". Finally, I think the page Completion should be moved to Well completion; it is zany that the latter use of the term, which is not even mentioned in any dictionary I have access to and does not occur (except for the Wikipedia article) in the first 100 Google hits for "completion", should have primacy. Funny fact: Quadratic reciprocity currently links to Completion.
Whether the above can garner consensus or not, there is no impediment to starting a page Complete (mathematics) now. However, I consider mathematical logic as much a field of mathematics as category theory, graph theory, analysis, and algebra, and I strongly disagree with the idea of banning the meanings in mathematical logic from such a page.  --Lambiam 08:56, 7 March 2008 (UTC)
I agree with the disambiguation proposal to merge. I would prefer it if we merely designated this article space as the disambiguation page without the "(disambiguation)" in the title. I'm not so keen on separating out the "(mathematics)" however. I find that whole (very strong apparently) tendency towards disintegration not helpful at all. Pontiff Greg Bard (talk) 18:20, 19 March 2008 (UTC)

[edit] Equivalent?

What is the difference between maximally complete and syntactically complete as defined? Similarly between deductively complete and semantically complete? (Actually there seems to be a misprint because semantically complete is referred to but not defined.) They seem to say the same thing. The page needs some cleaning up. —Preceding unsigned comment added by 81.210.255.97 (talk) 17:01, 17 March 2008 (UTC)

I'm not familiar with the terminology of "semantical completeness", but I suspect the property may be meant that is called "strong completeness" in the section on Mathematics. I'm also not sure how common and notable all these variants of the notion of completeness in logic are, since most are equivalent under mild assumptions that would tend to hold in logics unless they are specifically constructed to form a counterexample. Following the definitions of the article, maximal completeness implies syntactic completeness, but the converse implication does not necessarily hold. Take the logic whose sentences consist of a finite sequence of ¬ symbols followed by the symbol ⊥. The theorems are those sentences that have an odd number of ¬ symbols: {¬⊥, ¬¬¬⊥, ¬¬¬¬¬⊥, ...}. This logic is clearly syntactically complete. But ⊥ is not a theorem, and this sentence is also not a negation and therefore not the negation of any theorem. So the logic is not maximally complete. In general, a necessary condition for maximal completeness is that all unprovable sentences have the form of a negation; you can't have 1 < 0 as a sentence, so to speak. To me this seems to be both an unusual and a useless concept.  --Lambiam 09:58, 18 March 2008 (UTC)
I see that now the two have been merged. Since I have shown above that the two definitions are not equivalent, the old definition of maximally complete and the new one cannot both be right.  --Lambiam 00:50, 29 March 2008 (UTC)

In other articles of Wikipedia (eg Predicate Logic) there is reference to syntactic and semantic completeness: the former means that one can always prove P or NOT P; the second means that every statement that holds universally (in every model) can be proved. Are these equivalent? under what assumptions? —Preceding unsigned comment added by 92.50.98.91 (talk) 09:26, 1 April 2008 (UTC)

In general they are not equivalent. There is a problem with the notion of "holding universally". You have to fix certain symbols as constants. Otherwise, suppose we have a logic with 0-ary symbols ⊥ and ⊤. We can interpret ⊥ and ⊤ as, respectively, "false" and "true" in some models, but as "true" and "false" in other models. That means that basically no sentence holds in all models. If the logic is semantically sound, not even ⊤ is a theorem. Therefore we must fix certain symbols as logical constants, which however means that our pronouncements can no longer be about completely arbitrary logics. In the following I only use customary fixed interpretations: ⊥ means "false", ⊤ means "true", and ¬ means "not".
Take the logic whose formal language consists of only the sentences ⊥ and ⊤, and nothing else. The logic has a single axiom, ⊤, and no derivation rules. This logic cannot be syntactically complete, since neither ⊥ nor ¬⊥ is a theorem – the latter is not even a sentence of the language! But the system is semantically sound and complete.
If the logic is sound and syntactically complete, then it is also semantically complete: every true sentence is a theorem. The argument is as follows. Let P be an arbitrary true sentence. Then ¬P cannot be a theorem, since the system is sound. But then instead P is a theorem, since the system is syntactically complete.
Without the requirement of soundness, the implication does not follow. Take the logic whose sentences consist of a finite sequence of ¬ symbols followed by the symbol ⊥. The theorems are those sentences that have an even number of ¬ symbols: {⊥, ¬¬⊥, ¬¬¬¬⊥, ...}. This logic is clearly syntactically complete. The true sentences are those with an odd number of ¬ symbols, but none of these is a theorem, so this logic is semantically incomplete. It is also very unsound.  --Lambiam 01:08, 2 April 2008 (UTC)

[edit] Please disambiguate this

Below follows a list of articles about some form of completion or completeness. Note that I did not check all of them to see whether it is appropriate to treat them here.  --Lambiam 16:51, 20 March 2008 (UTC)

[edit] Math v logic again

L, Do you really believe that it is not generally true that:

"In mathematics, the notion of completeness is related to completeness in logic."

It seems that there is a tendency to write-out everything that connects math to logic. This is the math-centric thing I am always talking about.

It's another small point, but over time the consequences of this tendency have accumulated. Pontiff Greg Bard (talk) 22:59, 28 March 2008 (UTC)

To the extent that everything in mathematics is related to logic, it is true that the notion of (say) generalized function in mathematics is related to logic. However, that does not imply that the notion of generalized function in mathematics is related to generalized function in logic. In general, it is a nonsequitur to conclude from the fact that field A is related to field B, to the relationship of equally named concepts in these fields. The various things that mathematicians have called "complete", "completion" or "completeness" have hardly any relationship to each other beyond the common human-language meaning of complete. How does completeness of a measure relate to completeness of a formal system? About to the same extent as it relates to completeness of a dinner set.  --Lambiam 01:13, 29 March 2008 (UTC)

[edit] Check it out!

Sorry to have to say this, but I was shocked by the lack of competence of the contributors to this Wikipedia page. I mean: it's alright if students in logic make suggestions and express their perplexities, but an article on such a complex topic as completeness must -- and I repeat, must, absolutely must -- be written by someone that has a complete mastery of the field. There are professors of math that make very big and naive mistakes when they talk about, say, Goedel's completeness theorem. Thus, you can't just read a couple of books and then write a Wikipedia article on completeness! Gosh. Could you at least give this stuff to read to some competent people, such as von Plato. I am sure some of these people would be happy to point out mistakes and to make suggestions. -- About Greg Pontiff: how do you characterize a purely syntactical notion of completeness? I mean, in an interesting way for, say, first order logic? Just study Goedel's completeness theorem. Or, for all that, Wikipedia's page on propositional calculus. I mean, is this a basic learners' page where people talk freely about elementary topics in logic? —Preceding unsigned comment added by 85.35.108.114 (talk) 08:38, 18 April 2008 (UTC)

Okay, you are shocked at my incompetence. Welcome to Wikipedia "85" (you should log on). After you have been around a while (you know --past your second edit), you will probably find more shocking and amazing things. Hopefully some of the other more brilliant editors can make up for it. The only article that must -- and I repeat, must, absolutely must be written by experts is the article on CPR. This article is rated "start" in the scheme of things, it has a way to go before it is at a GA (good article) level. Any insight would be appreciated. Be well, Pontiff Greg Bard (talk) 09:59, 18 April 2008 (UTC)