User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic: Difference between revisions

No edit summary
No edit summary
Line 1: Line 1:
This page lists some important distinctions in introductory mathematical logic and computability theory. Bizarrely, most books won't even mention these distinctions, so you will probably be ''very'' confused at the start as you inevitably conflate these ideas.
This page lists some important distinctions in introductory mathematical logic and computability theory. Bizarrely, most books won't even mention these distinctions, so you will probably be ''very'' confused at the start as you inevitably conflate these ideas.
==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).
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>


{| class="wikitable"
{| class="wikitable"
Line 5: Line 15:
! 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. 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 || ||  
|}
|}


Retrieved from "https://machinelearning.subwiki.org/wiki/User:IssaRice/Computability_and_logic/Some_important_distinctions_and_equivalences_in_introductory_mathematical_logic"