Maths - Gödel Proofs

Negation Complete

A formal system S is Negation Complete (AKA syntactically complete or deductively complete or maximally complete) if for each sentence (closed formula) φ of the language of the system either φ or ¬φ is a theorem of S.

Effectively Computable

 

Effectively Enumerable

Different Approach

Here is a video by Robert Harper where he gives an interesting take in this.

At about 37 min into this video he says: "what is true has unbounded quantifier complexity whereas any formalism is always relentlessly recursively innumerable" - Gödels theorem.

"there is a distinction between proof and truth"

(by formalism here I think he means formal logic?)

 


metadata block
see also:

Computation and Algebra

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

 

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to the software project, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2022 Martin John Baker - All rights reserved - privacy policy.