12.2 Representability and Expressibility

Formal systems are mathematical frameworks with precise rules for manipulating symbols. They're crucial for studying logic and foundations of math. Representability and expressibility are key concepts, showing how these systems can encode functions and describe concepts.

Proving representability involves constructing formulas that capture specific functions or relations. However, formal systems have limitations in what they can express, as revealed by famous theorems like Gödel's Incompleteness Theorems and Tarski's Undefinability Theorem.

Formal Systems and Metamathematics

Representability vs expressibility in formal systems

Top images from around the web for Representability vs expressibility in formal systems

• 

  A Friendly Introduction to Mathematical Logic - Milne Open Textbooks View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

• 

  Cartesian Worldview – Introduction to History and Philosophy of Science View original

  Is this image relevant?

• 

  A Friendly Introduction to Mathematical Logic - Milne Open Textbooks View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Representability vs expressibility in formal systems

• 

  A Friendly Introduction to Mathematical Logic - Milne Open Textbooks View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

• 

  Cartesian Worldview – Introduction to History and Philosophy of Science View original

  Is this image relevant?

• 

  A Friendly Introduction to Mathematical Logic - Milne Open Textbooks View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

1 of 3

• Representability encodes functions or relations within formal system through formulas corresponding to given function or relation
• Expressibility describes concepts within formal system language articulating properties or relationships
• Key differences: representability encodes specific functions/relations while expressibility relates to descriptive power of system's language (primitive recursive functions, Gödel's incompleteness theorems)

Proving representability in formal arithmetic

• Primitive recursive functions always representable in formal arithmetic systems like Peano Arithmetic proved by induction on function complexity
• Basic arithmetic operations representable:
  • Addition: $\phi_+(x, y, z) \equiv z = x + y$
  • Multiplication: $\phi_×(x, y, z) \equiv z = x × y$
• Relations representable:
  • Less than: $\phi_<(x, y) \equiv \exists z(z \neq 0 \land x + z = y)$
  • Equality: $\phi_=(x, y) \equiv x = y$
• Proof techniques construct formula capturing function/relation, show formula satisfies representability definition, use induction for complex functions

Limitations of formal system expressibility

• Gödel's Incompleteness Theorems reveal limitations on consistency and completeness, systems cannot prove own consistency
• Tarski's Undefinability Theorem demonstrates arithmetic truth not arithmetically definable, limiting expressibility of semantic concepts
• Löwenheim-Skolem Theorem shows limitations on cardinality expressibility in first-order logic
• Church-Turing Thesis relates computability limits to formal system expressibility
• Implications: not all intuitively true statements provable within system, some concepts require stronger/different formal systems to express

Representability for metamathematical statements

• Gödel numbering encodes metamathematical statements as numbers allowing formal systems to "talk about" own properties
• Diagonalization method used in self-reference proofs crucial for many metamathematical results
• Provability predicate represents provability concept within formal system used to formulate statements about system's proving capabilities
• Expressibility of metamathematical concepts includes consistency, completeness, and soundness statements
• Computer science applications: halting problem relates to expressibility, Rice's theorem demonstrates limitations on program analysis