Difference between revisions of "User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic"
From Machinelearning
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 <math>\Delta</math> semantically implies <math>\phi</math>, then it is possible to prove <math>\phi</math> using <math>\Delta</math> as assumptions. This meaning of completeness is the the topic of the completeness theorem.<br>The term "complete" can also apply to a ''theory'', in which case it is also called "negationcomplete". If a theory is negationcomplete, 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 negationcomplete, 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'' negationcomplete).  +   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 <math>\Delta</math> semantically implies <math>\phi</math>, then it is possible to prove <math>\phi</math> using <math>\Delta</math> as assumptions. This meaning of completeness is the the topic of the completeness theorem.<br>The term "complete" can also apply to a ''theory'', in which case it is also called "negationcomplete". If a theory is negationcomplete, 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 negationcomplete, 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'' negationcomplete).  
+    
+   Syntax vs semantics   I have a rough draft quiz about this that I should post.  
}  }  
Revision as of 04:56, 11 February 2019
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.
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 semantically implies , then it is possible to prove using as assumptions. This meaning of completeness is the the topic of the completeness theorem. The term "complete" can also apply to a theory, in which case it is also called "negationcomplete". If a theory is negationcomplete, it means that for every sentence , the theory proves either or (if it proves both, it is still negationcomplete, 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 negationcomplete). 

Syntax vs semantics  I have a rough draft quiz about this that I should post. 
 decides: decidable set/relation vs deciding a sentence vs a theory being decidable vs deciding every sentence vs a logic being decidable (decidability of logic has several equivalent formulations; this is the topic of the Entscheidungsproblem)
 soundness: sound logic (soundness theorem) vs sound theory
 truth in all interpretations (validity) vs truth in the intended interpretation (natural reading, standard interpretation): see User:IssaRice/Computability and logic/Intended interpretation versus all interpretations
 structure vs interpretation vs model: synecdoche problem
 interpretation: there's interpretation in the "structure" sense and also interpretation in the sense of embedding one theory inside another theory (e.g. doing arithmetic with sets)
 theory vs axioms: synecdoche problem
 language vs logic vs formal system vs system
 proves logically vs proves in a particular theory: each theory adds some nonlogical axioms that allows it to prove things that aren't logically valid
 : when a set of sentences comes before the symbol vs when a structure comes before the symbol: see User:IssaRice/Computability and logic/Models symbol
 deciding (corresponding to computable total functions) vs recognizing (semideciding, computably enumerating; corresponding to computable partial functions)
 algorithm vs program vs index vs Godel number
 algorithm vs function computed by algorithm: see User:IssaRice/Computability and logic/Function versus algorithm
 expresses vs captures (strong capture, weak capture): see User:IssaRice/Computability and logic/Expresses versus captures
 primitive recursive vs (general, μ) recursive
 vs
 formulas vs relations vs sets
 enumerating vs computably enumerating vs primitively recursively enumerating
More speculative:
 different kinds of diagonalization?
There are also some important equivalences to keep in mind:
 Turing computable = computable = recursive = unbounded loops
 Primitive recursive = bounded loops
 computably enumerating = semideciding
 computably enumerating in order = deciding
 diagonalization lemma = rogers fixed point theorem
 Kleene's T predicate, godel beta function, Prf(m,n)