Talk:Completeness

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)

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)

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†∗ⁿ 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:

• Michael O'Donnell. In Handbook of Logic in Artificial Intelligence and Logic Programming pp. 40–41.
• Greg Restall. An Introduction to Substructural Logics pp. 181–182.
• Torkel Franzen. Inexhaustibility: A Non-exhaustive Treatment pp. 107–108.
• Robert L. Causey. Logic, Sets, and Recursion p. 72

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)

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)

This discussion is very old, but the well completion page is now a redirect to its more common meaning, related to drilling wells - which has nothing to do with the concept of mathematical completeness. Every page that links to that article uses it in that context. This talk-page is the only place that links to "well completion" to refer to the mathematical sense. Nimur (talk) 14:35, 4 May 2010 (UTC)

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)

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)

• AI-complete
• ASR-complete
• Almost complete
• Bounded complete poset
• Chain complete
• Co-NP-complete
• Co-RE-complete
• Command line completion
• Complete (album)
• Complete (box set)
• Complete (complexity)
• Complete Boolean algebra
• Complete Heyting algebra
• Complete active space
• Complete algebraic variety
• Complete bipartite graph
• Complete category
• Complete coloring
• Complete contract
• Complete economic integration
• Complete game

• Complete graph
• Complete group
• Complete homogeneous symmetric polynomial
• Complete information
• Complete intersection
• Complete lattice
• Complete market
• Complete measure
• Complete metric space
• Complete mixing
• Complete numbering
• Complete partial order
• Complete protein
• Complete quadrangle
• Complete quotient
• Complete set of commuting observables
• Complete set of invariants
• Complete theory
• Completeness (cryptography)
• Completeness (order theory)
• Completeness (statistics)

• Completion (ring theory)
• Early completion
• Feature complete
• Functional completeness
• Gödel's completeness theorem
• Hamiltonian completion
• Knuth-Bendix completion algorithm
• Line completion
• Model complete theory
• NL-complete
• NP-complete
• P-complete
• PSPACE-complete
• Pattern completion
• Sharp-P-complete
• Strongly NP-complete
• Turing completeness
• Weakly NP-complete
• Word completion

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)

yet another kind of completeness

The diode logic article mentions that "diode-resistor logic ... is not a complete logic family." Is there already an article that discusses the various kinds of "complete logic family", and what makes them complete? Perhaps under some other name? Or should I start such an article? --68.0.124.33 (talk) 04:32, 2 October 2008 (UTC)

"Extreme Completeness"

I removed (twice now) the following text:

A formal system is extremely complete or complete in the extreme sense iff every sentence is a theorem. Not all formal systems are intended to express "truths" or "falsehoods," however for those that do an extremely complete formal system is the same as an inconsistent formal system.

Until or unless a citation for this particular meaning of 'extreme completeness' is forthcoming, this text doesn't belong in the article. Zero sharp (talk) 01:33, 30 January 2009 (UTC)

The appropriate thing to do in cases like this is place a citation tag, not delete. That is what those tags are for. It would be nice if people looking for certain terms could find them -- even if certain special people don't use them. Pontiff Greg Bard (talk) 02:43, 30 January 2009 (UTC)

I eagerly await your citation, which I'm sure you just didn't have right at hand when you were inserting your 'special' usage of the term. Zero sharp (talk) 07:51, 30 January 2009 (UTC)

The formulation is inappropriate anyway. Every sentence being a theorem is a standard definition of an inconsistent deductive system going back at least to Tarski. It has nothing to do with expressing truth or falsehood, and it is a mainstream usage. Even if Gregbard manages to dig a reference for his term, the standard term should come first, and not vice versa. — Emil J. 10:53, 30 January 2009 (UTC)

Quelle surprise, no citation, no hits on google for anything other than this page or mirrors of it for the phrase 'extremely complete', therefore removing (for the third time now) as unsourced neologism. Zero sharp (talk) 22:32, 12 February 2009 (UTC)

Functional Analysis

I have my problems with the paragraph

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

I doubt that the statement is correct. Take for example the prominent separable Banach space V:=C[0,1], the space of continuous real valued functions on the unit interval [0,1] with the topology of uniform convergence and take S:={1,X,X^2, ...} to be set of all monomials. Then, by Weierstrass Approximation Theorem, S is a complete subset of V. However, an infinite linear combination of monomials is a power series. And a power series which converges always gives you a differentiable function (even a real analytic function). But there are functions in C[0,1] which are not differentiable. So, the statement must be false. Unless I dont understant the statement correctly. I hope, someone can explain this.--131.234.106.197 (talk) 17:05, 23 February 2011 (UTC)

Definition of an inconsistent system

I think the current definition of inconsistency is misleading in one case and wrong in others: "A formal system is inconsistent if and only if every sentence is a theorem."

This equivalence holds in some systems, e.g., classical first-order logic, but not in others, e.g., paraconsistent logic. Even in the systems where it holds, in all of the dozens of books that I have read, this fact is proven as a theorem and even has special names, e.g., the inconsistency effect or principle of explosion. I think the definition should be changed to agree with usual practice: a theory or formal system is inconsistent iff some formula and its negation are both theorems. Also, on the stricter logical meaning of "sentence" (a formula with no free variables), the equivalence as stated above is not as strong as it could be because it holds for all formulas. I will gladly change the definition if no one has objections. Cheers, Honestrosewater (talk) 05:06, 15 January 2012 (UTC)

I'm not even sure a definition of inconsistency is needed here since a) an article about completeness and b) where consistency it is used in the definitions of completeness, it is linked to the page on consistency. I'll remove it. mjog (talk) —Preceding undated comment added 23:28, 9 January 2013 (UTC)

"if and only if"

I removed "and only if" from the three main logical definitions of completeness since this implies soundness is required. If it was indeed "iff", then the correct symbolic version of, say semantic completeness, would actually be: $\models _{\mathcal {S}}\varphi \ \leftrightarrow \ \vdash _{\mathcal {S}}\varphi$, a formulation which is which is not terribly useful in a discussion of completeness. mjog (talk) 23:43, 9 January 2013 (UTC)

The “and only if” should be removed as definitions should use plain “if” per MOS:MATH, nevertheless your explanation makes no sense at all. The symbolic translation of “A formal system S is semantically complete if and only if every tautology of S is a theorem of S” is

$\mathrm {Complete} (S){\mathrel {\color {red}\leftrightarrow }}\forall \varphi \,(\models _{S}\varphi \to {}\vdash _{S}\varphi ),$

where I’ve highlighted the “if and only if” part, and similarly for the other definitions. As you can see, the equivalence you removed is in a different place than you claim, and is completely harmless.—Emil J. 13:15, 10 January 2013 (UTC)

Ah yes, you're absolutely right. Perhaps that confusion is part of the reason MOS:MATH suggests using a plain "if". mjog (talk) 22:53, 10 January 2013 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Completeness/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

what do you mean, prop calculus is syntactically complete? You just said, for every wff A, either A or its negation is provable. Afaik, neither "p" nor its negation is a theorem of prop calc.

Last edited at 06:44, 18 April 2008 (UTC). Substituted at 19:53, 1 May 2016 (UTC)