User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
! Term !! Distinction !! Further reading | ! Term !! Distinction !! Further reading | ||
|- | |- | ||
| Completeness || The term "complete" can apply to a ''logic'', in which case it is also called "semantically complete". If a logic is semantically complete, it means that if a set of sentences <math>\Delta</math> semantically implies a sentence <math>\phi</math> (i.e. every interpretation that makes every sentence in <math>\Delta</math> true also makes <math>\phi</math> true), then it is possible to prove <math>\phi</math> using <math>\Delta</math> as assumptions. This meaning of completeness is the topic of Gödel's completeness theorem.<br>The term "complete" can also apply to a ''theory'', in which case it is also called "negation-complete". If a theory is negation-complete, it means that for every sentence <math>\phi</math>, the theory proves either <math>\phi</math> or <math>\neg \phi</math> (if it proves both, it is still negation-complete, but it is also inconsistent, so is not an interesting theory). This meaning of completeness is the topic of Gödel's first incompleteness theorem (which states that certain theories of interest are ''not'' negation-complete). || | | Completeness || The term "complete" can apply to a ''logic'', in which case it is also called "semantically complete". If a logic is semantically complete, it means that if a set of sentences <math>\Delta</math> semantically implies a sentence <math>\phi</math> (i.e. every interpretation that makes every sentence in <math>\Delta</math> true also makes <math>\phi</math> true), then it is possible to prove <math>\phi</math> using <math>\Delta</math> as assumptions. This meaning of completeness is the topic of Gödel's completeness theorem. In addition, this form of completeness can be stated in another way by saying that any consistent set of sentences is satisfiable (has a model).<br>The term "complete" can also apply to a ''theory'', in which case it is also called "negation-complete". If a theory is negation-complete, it means that for every sentence <math>\phi</math>, the theory proves either <math>\phi</math> or <math>\neg \phi</math> (if it proves both, it is still negation-complete, but it is also inconsistent, so is not an interesting theory). This meaning of completeness is the topic of Gödel's first incompleteness theorem (which states that certain theories of interest are ''not'' negation-complete). || | ||
|- | |- | ||
| Syntax vs semantics || || I have a rough draft quiz about this that I should post. Also see <ref>https://www.hedonisticlearning.com/posts/the-pedagogy-of-logic-a-rant.html#syntax-versus-semantics</ref> | | Syntax vs semantics || || I have a rough draft quiz about this that I should post. Also see <ref>https://www.hedonisticlearning.com/posts/the-pedagogy-of-logic-a-rant.html#syntax-versus-semantics</ref> | ||