Completeness (logic)

In mathematical logic and metalogic, we talk about something called a complete system. A formal system is complete if it can prove every true statement, or formula as it is called, related to a certain property. If it cannot prove all such true statements, then the system is incomplete.

When we say a system is complete without saying more, we usually mean it is complete with regard to semantic validity. This means the system can show that every statement that is true in all situations is actually provable within the system.

The idea of completeness is very important because it tells us how much we can trust a system to prove what is truly true. A complete system can prove every true statement, which makes it very powerful and reliable for studying logic and mathematics.

Other properties related to completeness

Main articles: Soundness and Consistency

There is another idea called soundness that is connected to completeness. A system is sound if every result it proves actually matches what we know to be true. Soundness and completeness are important ideas that help us understand how well a system works.

Forms of completeness

Expressive completeness

A formal language is expressively complete if it can describe everything it is meant to describe.

Functional completeness

Main article: Functional completeness

A group of logical connections is functionally complete if it can express all possible logical statements.

Semantic completeness

Semantic completeness is the opposite of soundness in formal systems. A system is semantically complete when all its true statements, or tautologies, can be proven within the system. A system is sound if everything it proves is true. For example, Gödel's completeness theorem shows that first-order logic is semantically complete.

Strong completeness

A system is strongly complete if, for any set of starting ideas, every statement that follows from those ideas can be proven using the system.

Refutation completeness

A system is refutation complete if it can show that a group of statements cannot all be true at the same time. This means the system can prove that something is impossible.

Syntactical completeness

Main article: Complete theory

A system is syntactically complete if, for every statement, either the statement or its opposite can be proven within the system. Gödel's incompleteness theorem shows that some powerful systems, like Peano arithmetic, cannot be both consistent and syntactically complete.

Structural completeness

Main article: Admissible rule

In certain types of logic, a system is structurally complete if every rule that seems right can actually be proven using the system.

Model completeness

Main article: Model complete theory

A theory is model complete if every way to add to its models still keeps the theory's main ideas intact.