1.4 Introduction to formal systems

Formal systems are the backbone of mathematical logic, providing a structured approach to reasoning and proof. They consist of an alphabet, formation rules, axioms, and inference rules that work together to create a framework for deriving theorems.

Understanding formal systems is crucial for grasping the foundations of mathematical logic. By exploring components like consistency and completeness, we can appreciate the power and limitations of these systems in proving mathematical truths.

Formal Systems

Components of formal systems

Top images from around the web for Components of formal systems

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Category:Logical connectives - Wikipedia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

1 of 3

Top images from around the web for Components of formal systems

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Category:Logical connectives - Wikipedia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

1 of 3

• Alphabet represents a finite set of symbols used to construct well-formed formulas (wffs) in the system (propositional variables, logical connectives, parentheses)
• Formation rules define the syntax of the formal system by specifying how to construct valid wffs from the alphabet (rules for combining propositional variables and logical connectives)
• Axioms serve as the foundational statements of the formal system that are accepted as true without requiring proof ($(P \rightarrow (Q \rightarrow P))$, $((P \rightarrow (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow (P \rightarrow R)))$)
• Inference rules allow the derivation of new wffs (theorems) from existing wffs by specifying the allowed logical steps (modus ponens, modus tollens, hypothetical syllogism)

Axioms and inference rules

• Axioms form the starting point for deriving theorems in the formal system by serving as the basic assumptions accepted as true (Peano axioms in arithmetic, Zermelo-Fraenkel axioms in set theory)
• Inference rules enable the creation of theorems from axioms and previously derived theorems by defining the valid logical steps that can be applied (rule of detachment, rule of substitution)
• Theorems represent new knowledge generated within the formal system through the application of inference rules to axioms and other theorems (Pythagorean theorem in geometry, fundamental theorem of arithmetic)

Consistency vs completeness

• Consistency ensures that no contradiction can be derived from the axioms, meaning it is impossible to prove both a wff and its negation within the system (consistent systems prevent logical paradoxes)
• Completeness guarantees that every true statement can be proven within the system, implying that for every wff, either the wff or its negation can be derived using the system's axioms and inference rules (complete systems can prove all true statements)
• Soundness implies that every theorem derived within the system is true, which entails consistency but not necessarily completeness (sound systems have only true theorems but may not be able to prove all true statements)

Proof construction in formal systems

1. Begin with the axioms of the formal system as the foundation for the proof
2. Apply inference rules to the axioms and previously derived wffs to generate new wffs
3. Repeat step 2, applying inference rules until the desired theorem is successfully derived

Example proof using modus ponens inference rule:

• Axiom 1: $P \rightarrow Q$
• Axiom 2: $P$
• Modus ponens inference rule: If $P \rightarrow Q$ and $P$ are true, then $Q$ must be true
• Theorem: $Q$ (derived by applying modus ponens to Axioms 1 and 2)