Formal Systems

Mathematical Logic · Axiom Academy

The precise mathematical framework underlying logic and computation Mathematical Logic • Unit 5 - Godel's Theorems A formal system (also called a formal theory or deductive system ) is a complete mathematical framework for deriving theorems from axioms using precise rules. Formal Definition: Formal System A formal system is a tuple consisting of: = A formal language (alphabet and well-formed formulas) = A set of axioms (initial statements assumed true) = A set of inference rules (transformation rules) Component 1: The Formal Language The language of a formal system defines the symbols we can use and how to combine them into meaningful statements. The basic symbols of the language. For example, in propositional logic: Rules for combining symbols into valid statements. These are the syntactically correct expressions in . Example: is a WFF, but is not. The Language is Purely Syntactic At this stage, formulas have no meaning or truth value. The language only specifies which strings of symbols are grammatically correct. Axioms are the foundational statements of the formal system that we accept as true without proof. All other statements (theorems) are derived from axioms. The axioms form a distinguished subset of well-formed formulas: Effective vs. Ineffective Axiom Systems There exists an algorithm to determine whether any given formula is an axiom. Example: Peano Arithmetic has a finite list of axiom schemas that can be mechanically checked.

This is the written version of the interactive lesson above. See the full Mathematical Logic course.