Hubbry Logo
Formal systemFormal systemMain
Open search
Formal system
Community hub
Formal system
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Formal system
Formal system
Formal system
View on Wikipedia
from Wikipedia

A formal system (or deductive system) is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms.[1]

In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in mathematics.[2] However, in 1931 Kurt Gödel proved that any consistent formal system sufficiently powerful to express basic arithmetic cannot prove its own completeness. This effectively showed that Hilbert's program was impossible as stated.

The term formalism is sometimes a rough synonym for formal system, but it also refers to a given style of notation, for example, Paul Dirac's bra–ket notation.

Concepts

[edit]
This diagram shows the syntactic entities that may be constructed from formal languages. The symbols and strings of symbols may be broadly divided into nonsense and well-formed formulas. A formal language can be thought of as identical to the set of its well-formed formulas, which may be broadly divided into theorems and non-theorems.

A formal system has the following components, as a minimum:[3][4][5]

A formal system is said to be recursive (i.e. effective) or recursively enumerable if the set of axioms and the set of inference rules are decidable sets or semidecidable sets, respectively.

Formal language

[edit]
Part of a series on
Formal languages
Key concepts
Applications
Main articles: Formal language, Formal grammar, Syntax (logic), and Logical form

A formal language is a language that uses a set of strings whose symbols are taken from a specific alphabet, and operations used to form sentences from them. . Like languages in linguistics, formal languages generally have two aspects:

  • the syntax is what the language looks like (more formally: the set of possible expressions that are valid utterances in the language)
  • the semantics are what the utterances of the language mean (which is formalized in various ways, depending on the type of language in question)

Usually only the syntax of a formal language is considered via the notion of a formal grammar. The two main categories of formal grammar are that of generative grammars, which are sets of rules for how strings in a language can be written, and that of analytic grammars (or reductive grammar[6][unreliable source?][7]), which are sets of rules for how a string can be analyzed to determine whether it is a member of the language.

Deductive system

[edit]
Main articles: Inference, Logical consequence, and Deductive reasoning

A deductive system, also called a deductive apparatus,[8] consists of the axioms (or axiom schemata) and rules of inference that can be used to derive theorems of the system.[1]

In order to sustain its deductive integrity, a deductive apparatus must be definable without reference to any intended interpretation of the language. The aim is to ensure that each line of a derivation is merely a logical consequence of the lines that precede it. There should be no element of any interpretation of the language that gets involved with the deductive nature of the system.

The logical consequence (or entailment) of the system by its logical foundation is what distinguishes a formal system from others which may have some basis in an abstract model. Often the formal system will be the basis for or even identified with a larger theory or field (e.g. Euclidean geometry) consistent with the usage in modern mathematics such as model theory.[clarification needed]

An example of a deductive system would be the rules of inference and axioms regarding equality used in first order logic.

The two main types of deductive systems are proof systems and formal semantics.[8][9]

Proof system

[edit]
Main articles: Proof system and Formal proof

Formal proofs are sequences of well-formed formulas (or WFF for short) that might either be an axiom or be the product of applying an inference rule on previous WFFs in the proof sequence.

Once a formal system is given, one can define the set of theorems which can be proved inside the formal system. This set consists of all WFFs for which there is a proof. Thus all axioms are considered theorems. Unlike the grammar for WFFs, there is no guarantee that there will be a decision procedure for deciding whether a given WFF is a theorem or not.

The point of view that generating formal proofs is all there is to mathematics is often called formalism. David Hilbert founded metamathematics as a discipline for discussing formal systems. Any language that one uses to talk about a formal system is called a metalanguage. The metalanguage may be a natural language, or it may be partially formalized itself, but it is generally less completely formalized than the formal language component of the formal system under examination, which is then called the object language, that is, the object of the discussion in question. The notion of theorem just defined should not be confused with theorems about the formal system, which, in order to avoid confusion, are usually called metatheorems.

Formal semantics of logical system

[edit]
Main articles: Semantics of logic, Interpretation (logic), and Model theory

A logical system is a deductive system (most commonly first order logic) together with additional non-logical axioms. According to model theory, a logical system may be given interpretations which describe whether a given structure - the mapping of formulas to a particular meaning - satisfies a well-formed formula. A structure that satisfies all the axioms of the formal system is known as a model of the logical system.

A logical system is:

  • Sound, if each well-formed formula that can be inferred from the axioms is satisfied by every model of the logical system.
  • Semantically complete, if each well-formed formula that is satisfied by every model of the logical system can be inferred from the axioms.

An example of a logical system is Peano arithmetic. The standard model of arithmetic sets the domain of discourse to be the nonnegative integers and gives the symbols their usual meaning.[10] There are also non-standard models of arithmetic.

History

[edit]
Main articles: Formalism (philosophy of mathematics) and Formal logical systems

Early logic systems includes Indian logic of Pāṇini, syllogistic logic of Aristotle, propositional logic of Stoicism, and Chinese logic of Gongsun Long (c. 325–250 BCE).[citation needed] In more recent times, contributors include George Boole, Augustus De Morgan, and Gottlob Frege. Mathematical logic was developed in 19th century Europe.

David Hilbert instigated a formalist movement called Hilbert’s program as a proposed solution to the foundational crisis of mathematics, that was eventually tempered by Gödel's incompleteness theorems.[2] The QED manifesto represented a subsequent, as yet unsuccessful, effort at formalization of known mathematics.

See also

[edit]

References

[edit]

Sources

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Formal system

View on Grokipedia
from Grokipedia
A formal system is an abstract framework in and logic consisting of a defined over a of primitive symbols, a set of axioms serving as initial well-formed formulas, and a of rules that enable the syntactic derivation of theorems from the axioms. Formal systems facilitate rigorous by focusing exclusively on the manipulation of symbol strings according to specified rules, independent of any semantic interpretation or external meaning. This syntactic approach underpins key areas such as , which studies the structure of proofs, and , which examines interpretations of formal languages. Historically, the development of formal systems arose in the late amid efforts to eliminate ambiguities in mathematical foundations, with Gottlob Frege's Begriffsschrift (1879) providing the first complete formal axiomatic treatment of logic and arithmetic. advanced the idea in the 1920s through his program to formalize all of mathematics as a finite, consistent "game" of symbols, aiming to secure its foundations against paradoxes like Russell's. Despite their power, formal systems have inherent limitations, as demonstrated by Kurt Gödel's incompleteness theorems of 1931, which prove that any consistent formal system capable of expressing basic arithmetic is incomplete, meaning some true statements within its language cannot be proved using its axioms and rules. These theorems undermined Hilbert's full ambitions but highlighted the depth of in revealing ' boundaries. Today, formal systems are indispensable in for applications like , in programming languages, and of software and hardware, ensuring correctness through machine-checkable proofs. Notable examples include Peano arithmetic for natural numbers and Zermelo-Fraenkel (ZFC) for set-based , both of which illustrate how formal systems encode vast swaths of mathematical knowledge.

Core Components

Formal Language

In a formal system, the formal language constitutes the syntactic foundation, comprising a of symbols known as the from which finite strings are formed to create meaningful expressions. This language is defined recursively, ensuring that only specific combinations qualify as well-formed formulas (wffs), which are the valid syntactic objects of the system. The alphabet typically includes primitive symbols—basic, indivisible elements such as constants, variables, logical connectives, predicates, function symbols, and quantifiers—while derived symbols are abbreviations or composites built from primitives, such as biconditional (↔) defined via implication (→) and (¬). The formation rules, or syntax, specify how wffs are constructed inductively. For propositional logic, the consists of propositional variables (e.g., P,[Q](/page/Q),[R](/page/R)P, [Q](/page/Q), [R](/page/R)) and primitive connectives such as conjunction (∧\wedge), disjunction (∨\vee), and (¬\neg), along with parentheses for grouping. The recursive begins with atomic wffs as the propositional variables themselves; compound wffs are then formed by applying connectives, such as ¬P\neg P or (P∧[Q](/page/Q))(P \wedge [Q](/page/Q)). This ensures unambiguous , as every wff has a unique structure. For example, the expression (P∨¬[Q](/page/Q))(P \vee \neg [Q](/page/Q)) is a wff, while P∨P \vee is not, due to incomplete grouping. In first-order logic, the alphabet expands to include individual variables (e.g., x,y,zx, y, z), individual constants (e.g., a,ba, b), function symbols (e.g., ff for unary functions), predicate symbols (e.g., P1P^1 for unary predicates, R2R^2 for binary), and quantifiers (∀\forall for universal, ∃\exists for existential), in addition to the propositional connectives and parentheses. Terms are built recursively: variables and constants are terms, and if t1,…,tnt_1, \dots, t_n are terms, then f(t1,…,tn)f(t_1, \dots, t_n) is a term. Atomic wffs are equations like t1=t2t_1 = t_2 or predicate applications like P(t1,…,tn)P(t_1, \dots, t_n); compound wffs extend these with connectives and quantifiers, such as ∀x(P(x)∧Q(x))\forall x (P(x) \wedge Q(x)) or ∃yR(x,y)\exists y R(x, y). These rules recursively define terms and sentences (closed wffs without free variables), guaranteeing that the language provides a precise, ambiguity-free structure for all expressions in the formal system. The formal language thus interfaces with the deductive apparatus by supplying the wffs from which theorems are derived via inference rules.

Deductive Apparatus

In a formal system, the deductive apparatus consists of a set of axioms and rules that enable the derivation of theorems from initial assumptions within the . This structure, often termed a deductive system, provides a syntactic mechanism for generating new well-formed formulas (wffs) solely based on their form, without reference to meaning. Axioms serve as the foundational statements of the system, divided into logical axioms and non-logical axioms. Logical axioms are general tautologies inherent to the underlying logic, such as schemata that hold for all interpretations (e.g., ϕ∨¬ϕ\phi \lor \lnot \phi for the law of excluded middle in classical systems). These capture the universal principles of and are fixed across applications. Non-logical axioms, in contrast, are domain-specific assumptions tailored to the particular theory, such as Peano's axioms for arithmetic, which introduce concepts like successor functions beyond pure logic. Inference rules specify how existing wffs can be transformed to produce new ones, typically in a finite, mechanical manner. A primary example is , formally defined as: from premises AA and A→BA \to B, infer BB. This rule, central to systems like Hilbert's, allows detachment of consequents from conditionals when the antecedent is established. Other rules may include substitution or , but exemplifies the step-by-step expansion of derivable content. A proof within the deductive apparatus is a finite of wffs where the first is the desired , and each subsequent is either an or follows from prior formulas via an inference rule. Such sequences formalize the notion of derivability, denoted Γ⊢ϕ\Gamma \vdash \phi, indicating that ϕ\phi is deducible from a set of premises Γ\Gamma. This process relies on the syntax of the to ensure rigor and unambiguity. Syntactic deduction, as facilitated by the deductive apparatus, differs fundamentally from semantic entailment. Syntactic deduction concerns formal proofs constructed via axioms and rules, yielding theorems independent of interpretation. Semantic entailment, however, evaluates whether a formula holds true in all models satisfying the premises, linking syntax to meaning. While related through soundness and completeness theorems, the deductive apparatus operates purely syntactically.

Semantics and Interpretation

Semantics in formal systems assigns meaning to syntactic expressions by mapping them to elements within a specified , thereby connecting abstract symbols to concrete interpretations. This process, known as interpretation, bridges the gap between the formal 's rules of formation and well-formed formulas and their referential content in a . A key component of semantics is the notion of a or model, which consists of a non-empty set DD serving as the and interpretation functions for the non-logical symbols of the . Constants are interpreted as elements of DD, function symbols as mappings from tuples in DD to elements in DD, and predicate symbols as relations on DD. For instance, a binary predicate PP is interpreted as a subset of D×DD \times D, representing the pairs for which PP holds. These interpretations fix the "intended" meaning of the 's vocabulary relative to the chosen domain. Central to semantic evaluation is the definition of truth or satisfaction within a model, pioneered by in his recursive theory for . Satisfaction is defined inductively over the complexity of formulas: an P(t1,…,tn)P(t_1, \dots, t_n), where tit_i are terms, is satisfied by an assignment of values from DD to variables if the of their interpretations lies in the relation denoted by PP's interpretation. For compound formulas, satisfaction follows the logical connectives—e.g., a conjunction ϕ∧ψ\phi \land \psi is satisfied if both ϕ\phi and ψ\psi are—and quantifiers, where ∀xϕ\forall x \phi holds if ϕ\phi is satisfied under every variable assignment differing at most in xx, and similarly for . This Tarskian framework ensures that truth is materially adequate and formally precise, avoiding paradoxes by distinguishing object language from . The distinction between syntax and semantics underscores that syntactic rules manipulate symbols as arbitrary marks without inherent meaning, whereas semantics imposes external interpretations to determine truth values or validity. A sentence may be provable syntactically in a deductive yet require semantic verification for correspondence to ; this interplay supports theorems like , where provable sentences are true in all models. An illustrative application appears in , where the Herbrand universe provides a domain for skolemized formulas. After skolemization replaces existentially quantified variables with skolem functions, the Herbrand is the set of all ground terms generated from the language's constants and function symbols, serving as a minimal domain to test without arbitrary elements. Herbrand models over this then correspond to interpretations where atomic ground formulas are true exactly when they hold in some model of the original formula, facilitating resolution-based proof search.

Fundamental Properties

Soundness and Completeness

In formal systems, is a meta-theoretical that ensures the deductive apparatus does not derive invalid statements. Specifically, the states that if a ϕ\phi is provable from a set of Γ\Gamma (denoted Γ⊢ϕ\Gamma \vdash \phi), then ϕ\phi is semantically entailed by Γ\Gamma (denoted Γ⊨ϕ\Gamma \models \phi), meaning ϕ\phi holds true in every model satisfying Γ\Gamma. This guarantees that proofs preserve truth, linking the syntactic notion of derivation to semantic validity. The completeness theorem provides the converse relation, asserting that every semantically valid formula is provable. For , proved in 1930 that if Γ⊨ϕ\Gamma \models \phi, then Γ⊢ϕ\Gamma \vdash \phi, establishing that the Hilbert-style axiomatization captures all logical truths. This result demonstrates the adequacy of the formal system in exhaustively representing semantic entailments through syntactic means. In systems that are both and complete, syntactic consequence and semantic consequence are equivalent, allowing proofs to fully characterize logical validity without missing or extraneous derivations. This equivalence underpins the reliability of formal systems for reasoning, as it aligns deduction precisely with model-theoretic truth. For restricted fragments, such as propositional logic, completeness holds in a strong sense, where every tautology is provable. Hilbert-style systems for propositional logic, as formalized by Hilbert and Ackermann, achieve both and completeness, with the completeness result originally established by Emil Post in 1921.

Consistency and Decidability

In a formal system, consistency is the property that ensures no ϕ\phi and its ¬ϕ\neg \phi can both be derived as theorems. This syntactic condition prevents the system from deriving contradictions, meaning not every is provable. Consistency can be absolute, established through finitary methods independent of stronger assumptions, or relative, demonstrated by showing that if a base theory is consistent, then the extended system is also consistent. Proofs of consistency often rely on semantic models, where establishes that every consistent theory has a model, thereby confirming its consistency via . Finitary methods, such as Gentzen's in , provide absolute consistency proofs for systems like Peano arithmetic by reducing proofs to atomic forms without the cut rule, ensuring no contradictions arise through up to the ordinal ϵ0\epsilon_0. Decidability in a formal system refers to the existence of an that, for any sentence, determines whether it is provable within the system. Church's theorem (1936) proves that is undecidable, as there is no general to determine the validity or provability of arbitrary sentences, linking this to the undecidability of the via reductions. However, certain fragments are decidable; for instance, , which interprets over the integers without , admits a decision procedure using , as shown by Presburger in 1930. Independence arises when a statement is neither provable nor disprovable in a consistent system, highlighting its limitations. A prominent example is the in Zermelo-Fraenkel with the (ZFC), which Gödel (1940) showed is consistent relative to ZFC via the constructible universe, and (1963) proved independent by forcing a model where it fails.

Historical Development

Early Foundations in Logic

The origins of formal systems can be traced to , particularly 's syllogistic logic, which served as a proto-formal system for . In his , defined a as a deductive argument in which, given certain premises, a distinct conclusion necessarily follows, structured around categorical propositions involving subject and predicate terms connected by a copula. He identified four types of categorical sentences—universal affirmative (AaB: "Every A is B"), universal negative (AeB: "No A is B"), particular affirmative (AiB: "Some A is B"), and particular negative (AoB: "Some A is not B")—and organized valid inferences into three figures based on the position of the middle term, yielding 14 valid syllogistic moods such as Barbara (AaB and BaC imply AaC). These inference rules, including conversion (e.g., AeB implies BeA) and reductio ad impossibile, provided a systematic framework for evaluating arguments, though interpreted as a fragment of modern with assumptions of non-empty classes. Medieval logicians built upon Aristotelian foundations through developments in supposition theory and terminist logic, refining the semantics of terms in propositions. Supposition theory, emerging in the 12th–13th centuries, analyzed how terms "supposit" or stand for things in context, distinguishing personal supposition (terms referring to extra-linguistic entities) from material supposition (terms referring to themselves or concepts), which allowed for more precise handling of ambiguity in sentences. Terminist logic, associated with works like the Dialectica Monacensis, emphasized terms as the basic units of analysis, incorporating modal distinctions such as de dicto (propositional modality) and de re (real modality) to address quantified modal statements. A notable advancement came from John Buridan in the 14th century, who streamlined terminist methods in his Summulae de dialectica and developed a modal logic rejecting essentialist assumptions in favor of a temporalist approach using simultaneous supposition for alternatives, treating possibility and necessity symmetrically and influencing late medieval logical treatises. In the , the algebra of logic marked a shift toward symbolic manipulation, pioneered by in his 1854 work An Investigation of the Laws of Thought. Boole treated logical classes algebraically, using symbols like x and y to represent subsets of the universe (with 1 as the universe and 0 as the ), and defined operations such as for intersection (xy) and addition for disjoint union (x + y), governed by laws including commutativity (xy = yx), (x² = x), and distributivity (z(x + y) = zx + zy). This Boolean algebra replaced traditional syllogistic reasoning with algorithmic equation-solving, enabling the expansion theorem to derive conclusions from premises like "All X is Y" as x = vy, thus founding modern . Gottlob Frege advanced this trajectory in 1879 with , introducing the first formal notation for first-order predicate logic complete with quantifiers. Frege's two-dimensional script represented complex thoughts through functional expressions, negations, conditionals, and generality indicators (e.g., concavities for like "every" and Roman letters for variables), allowing precise formulation of quantified statements beyond subject-predicate structures. This system formalized inferences via axioms and rules, emphasizing the unsaturated nature of predicates as functions awaiting arguments, and laid the groundwork for modern despite initial resistance due to its novel notation. Subsequent developments bridged the late 19th and early 20th centuries. formalized the axioms of arithmetic in 1889, providing a rigorous symbolic foundation for natural numbers that influenced later axiomatic systems. Bertrand Russell's discovery of the paradox in (1901) highlighted foundational issues, leading to his and Alfred North Whitehead's Principia Mathematica (1910–1913), which attempted a comprehensive formalization of using ramified to avoid paradoxes. These works emphasized axiomatic rigor and symbolic precision, setting the stage for 20th-century efforts. A key limitation of these pre-20th-century systems was their lack of rigorous axiomatization; Aristotelian and medieval logics relied on intuitive rules without comprehensive axiomatic foundations, while Boole's algebra handled extensional relations but inadequately captured generality, and even Frege's early work used minimal axioms without full type distinctions or bivalence principles. This paved the way for 20th-century axiomatic refinements.

Modern Formalizations

In the 1920s, proposed a program to establish the foundations of through the complete formal axiomatization of all mathematical theories, aiming to prove their consistency using only finitary methods that avoid infinite processes. This approach sought to secure classical against the paradoxes uncovered in by reducing all proofs to concrete, combinatorial operations verifiable by humans, thereby providing an absolute foundation immune to revision. Hilbert's vision emphasized the axiomatic method as a tool for rigor, where formal systems would encapsulate in a finite set of symbols and rules, allowing consistency to be demonstrated without appealing to non-constructive ideal elements. Kurt Gödel's incompleteness theorems of 1931 profoundly impacted by demonstrating that any consistent formal system capable of expressing basic arithmetic is incomplete, meaning there exist true statements within the system that cannot be proved or disproved using its axioms and rules. The first theorem shows that such a system cannot prove its own consistency, while the second implies that if consistent, it cannot establish the consistency of any stronger system containing it. These results, derived through arithmetization of syntax and self-referential statements, revealed inherent limitations in formal axiomatization, shifting focus from absolute consistency proofs to relative ones and influencing subsequent developments in . Alfred Tarski's 1933 work provided a rigorous semantic foundation by defining truth for formal languages in a materially adequate and non-paradoxical manner, using a hierarchical structure of languages to distinguish object language from . His Convention T requires that a truth definition satisfy instances like "'Snow is white' is true snow is white," ensuring semantic concepts align with intuitive notions while avoiding liar paradoxes through syntactic levels. This framework enabled precise model-theoretic interpretations of formal systems, separating syntax from semantics and facilitating the study of satisfaction and validity in interpreted structures. Gerhard Gentzen's 1934 introduction of and advanced by offering systems that mimic human reasoning more closely than axiomatic methods, emphasizing structural rules for inference. uses introduction and elimination rules for logical connectives, allowing proofs to build intuitively from assumptions, while represents derivations as sequences of formulas separated by turnstiles, enabling cut-elimination theorems that normalize proofs and prove consistency for classical and intuitionistic logics. These innovations provided tools for analyzing proof complexity and substructural logics, bridging Hilbert's formalist ideals with more flexible deductive frameworks. The mid-20th century saw formal systems evolve toward type theory and category theory as alternatives to set-theoretic foundations, addressing paradoxes and incompleteness through structured hierarchies and abstract relations. Type theory, building on Bertrand Russell's ramified types and Alonzo Church's simple typed lambda calculus from the 1940s, imposes levels on expressions to prevent self-reference issues, enabling constructive mathematics where types classify terms and ensure well-formed computations. Church's system formalized higher-order logic with functional types, providing a basis for lambda calculi that underpin modern proof assistants. Meanwhile, category theory, formalized by Samuel Eilenberg and Saunders Mac Lane in 1945 and extended by William Lawvere's 1964 elementary theory of categories, treats mathematical structures via objects, morphisms, and compositions, offering a relational foundation that unifies diverse fields without privileging sets. Lawvere's approach axiomatizes categories to recover set theory internally, supporting variable-set foundations and emphasizing functorial semantics over extensional equality. These developments shifted formal systems toward modular, abstract frameworks suitable for both rigorous proof and computational implementation.

Applications and Extensions

In Mathematical Logic

Formal systems play a central role in the foundations of by providing axiomatic frameworks that encode the entirety of mathematical reasoning. Zermelo-Fraenkel set theory with the (ZFC) serves as the predominant formal system for this purpose, consisting of a first-order language with a single binary predicate for set membership and a set of axioms that govern the formation and properties of sets. Introduced by in 1908 and refined by in 1922 through the addition of the and adjustments to separation, ZFC enables the formal derivation of theorems across arithmetic, , and from its axioms. Within ZFC, all mathematical objects—such as numbers, functions, and spaces—are constructed as sets, ensuring a unified and rigorous basis for proofs that avoids paradoxes like Russell's through the axiom of foundation. In , formal systems facilitate the study of mathematical by interpreting their languages in diverse models, revealing relationships like between seemingly distinct objects. A for a formal system is a set equipped with interpretations of the system's non-logical symbols, allowing theorems to be evaluated as true or false within that model. The back-and-forth method, originating in Georg Cantor's work on dense linear orders and developed in by Roland Fraïssé, constructs between countable models of a by alternately extending partial to match elements from each side, ensuring equivalence under the theory's axioms. For instance, this technique proves that all countable dense linear orders without endpoints, such as , are , highlighting how formal systems classify up to elementary equivalence. Proof theory employs formal systems to analyze the strength and consistency of mathematical theories through ordinal assignments that measure proof complexity. assigns to a theory, like Peano arithmetic (PA), a proof-theoretic ordinal representing the supremum of ordinals embeddable into its cut-free proofs, providing a relative consistency proof via . Gerhard Gentzen's 1936 consistency proof for PA establishes that if up to the ordinal ϵ0\epsilon_0—the least fixed point of α↦ωα\alpha \mapsto \omega^\alpha—holds, then PA is consistent, as cut-elimination reduces proofs to quantifier-free forms without contradiction. This ordinal ϵ0\epsilon_0 quantifies PA's consistency strength, showing that stronger systems like require larger ordinals for analogous analyses. Recursion theory, or , uses formal systems to classify computable functions and their hierarchies within arithmetic. Formal systems like formalize the computable functions via schemes for zero, successor, and composition, extended by minimization in full recursion theory. (1938) asserts that for any computable functional Φe\Phi_e indexing partial recursive functions, there exists an index ii such that Φi=Φi(⟨i⟩)\Phi_i = \Phi_i(\langle i \rangle), enabling self-referential programs where a function can compute its own index and modify its behavior accordingly. This theorem underpins fixed-point constructions in , illustrating how formal systems capture the self-applicability of recursive definitions. Despite their power, formal systems face inherent limitations in , particularly regarding decidability. , posed in 1900, sought an to determine solvability of Diophantine equations—polynomial equations with coefficients and unknowns. Yuri Matiyasevich's 1970 proves this problem undecidable by showing that every recursively enumerable set is Diophantine, reducing halting to solutions via exponential growth encoded in polynomials like relations. Thus, no formal system encompassing arithmetic can decide all such equations, underscoring Gödel's incompleteness as a barrier to fully mechanizing .

In Computer Science and Computation

In , formal systems underpin the theoretical foundations of computation, particularly through models like and the , which define what is computable. A , introduced by in 1936, is an abstract formal system consisting of a tape, a read-write head, and a of states with transition rules that manipulate symbols on the tape. This system formalizes sequential computation and proves key results in , such as the undecidability of the . Similarly, the , developed by around 1936, serves as a formal system for expressing functions via abstraction and application, where terms like λx.M\lambda x. M denote functions that take input xx and yield output MM. Church's framework demonstrates the equivalence of lambda terms to computations under the Church-Turing thesis, establishing it as a foundational model for and higher-order functions. In , these formal systems extend to hierarchies like finite automata and pushdown automata, which recognize regular and context-free languages, respectively, providing computability bounds for algorithmic processes. Type systems in programming languages leverage formal systems to ensure program safety and correctness, with the simply-typed exemplifying this approach. Introduced by Church in 1940, the simply-typed augments the untyped version with base types (e.g., individuals and truth values) and function types σ→τ\sigma \to \tau, enforced by typing rules that prevent ill-formed expressions like applying a function to an incompatible type. This formal system guarantees strong normalization—every well-typed term reduces to a unique normal form—eliminating paradoxes such as the untyped calculus's self-application, and it directly influences type checkers in languages like ML and . By modeling types as a simply-typed itself, modern type systems support features like polymorphism and dependent types, enabling compile-time detection of errors and facilitating modular . Formal verification employs formal systems to prove properties of computational systems, notably through with (LTL). LTL, pioneered by Amir Pnueli in 1977, is a extending propositional logic with temporal operators like G\mathbf{G} (always) and F\mathbf{F} (eventually), allowing specifications of system behaviors over infinite execution paths, such as "a request is eventually granted" via G(request→Fgrant)\mathbf{G}(request \to \mathbf{F} grant). In , a formal system like a Kripke structure (states, transitions, and labeling) is exhaustively explored against LTL formulas using algorithms that translate specifications to automata, verifying properties like safety (no bad states) or liveness (progress). Tools implementing LTL model checking, such as SPIN, have scaled to industrial applications, detecting bugs in protocols by counterexample generation when properties fail. Hoare logic provides an axiomatic formal system for deductive verification of imperative programs, focusing on partial correctness. Proposed by C. A. R. Hoare in 1969, it uses triples {P}S{Q}\{P\} S \{Q\}, where precondition PP, statement SS, and postcondition QQ ensure that if PP holds before executing SS and SS terminates, then QQ holds afterward; axioms like assignment x:=ex := e yield {Q[e/x]}x:=e{Q}\{Q[e/x]\} x := e \{Q\}, and rules compose proofs for compound statements. This system formalizes reasoning about loops via invariants and has been extended to concurrent programs, underpinning tools like VCC for verifying device drivers through weakest precondition calculus. The Curry-Howard isomorphism bridges formal systems in logic and computation, interpreting proofs in as programs in . Originating in Haskell Curry and Robert Feys' 1958 work on and formalized by William Howard in 1980, it equates propositions with types (e.g., A→BA \to B as type of functions from AA to BB) and proofs with terms (introduction rules as lambda abstractions, elimination as applications). In intuitionistic settings, this yields the propositions-as-types principle, where normalization of proofs corresponds to program termination, influencing proof assistants like Coq that extract verified programs from logical proofs.

References

  1. https://cs.lmu.edu/~ray/notes/formalsystems/
  2. https://cse.buffalo.edu/~rapaport/formalsystems
  3. https://plato.stanford.edu/entries/formalism-mathematics/
  4. https://nuprl-web.cs.cornell.edu/Intro/FormalMath/formalmath.html
  5. https://plato.stanford.edu/entries/goedel/
  6. https://plato.stanford.edu/entries/logic-classical/
  7. https://sistemas.fciencias.unam.mx/~lokylog/images/Notas/la_aldea_de_la_logica/Libros_notas_varios/L_02_MENDELSON%2C%20E%20-%20Introduction%20to%20Mathematical%20Logic%2C%206th%20Ed%20-%20CRC%20Press%20%282015%29.pdf
  8. https://plato.stanford.edu/entries/logic-propositional/
  9. https://philomatica.org/wp-content/uploads/2017/04/ruax.pdf
  10. https://www.csc.kth.se/utbildning/kth/kurser/DA2210/vettig13/Forelasningar/F5.pdf
  11. http://intrologic.stanford.edu/chapters/chapter_04.html
  12. https://plato.stanford.edu/entries/model-theory/
  13. https://plato.stanford.edu/entries/tarski-truth/
  14. https://plato.stanford.edu/entries/meaning/
  15. https://mathworld.wolfram.com/HerbrandUniverse.html
  16. https://archive.org/details/grundzugedertheo0027hilb
  17. https://akirarabelais.com/wp-content/uploads/2024/12/dvdadlf.pdf
  18. https://encyclopediaofmath.org/wiki/Consistency
  19. https://plato.stanford.edu/entries/proof-theory/
  20. https://www.cmu.edu/dietrich/philosophy/docs/tech-reports/166_Sieg.pdf
  21. https://plato.stanford.edu/entries/goedel-incompleteness/
  22. https://philpapers.org/rec/GALCUT
  23. https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/haa-18/haa-18.pdf
  24. https://plato.stanford.edu/entries/continuum-hypothesis/
  25. https://plato.stanford.edu/entries/logic-ancient/
  26. https://plato.stanford.edu/entries/modality-medieval/
  27. https://plato.stanford.edu/entries/buridan/
  28. https://plato.stanford.edu/entries/boole/
  29. https://plato.stanford.edu/entries/frege/
  30. https://plato.stanford.edu/entries/peano-arithmetic/
  31. https://plato.stanford.edu/entries/russell-paradox/
  32. https://plato.stanford.edu/entries/principia-mathematica/
  33. https://plato.stanford.edu/entries/frege-logic/
  34. https://www.cmu.edu/dietrich/philosophy/docs/tech-reports/78_Sieg.pdf
  35. https://arxiv.org/pdf/math/0508572
  36. https://plato.stanford.edu/entries/tarski/
  37. https://www.digizeitschriften.de/download/pdf/266833020_0039/log32.pdf
  38. https://artscimedia.case.edu/wp-content/uploads/2013/07/14182623/Lawvere-ETCS.pdf
  39. https://people.math.ethz.ch/~halorenz/4students/LogikML/ZFC.pdf
  40. https://lps.elte.hu/andras/logtort4/independence_AoC.pdf
  41. https://resources.illc.uva.nl/emeriti/uploaded_files/inlineitem/zf.pdf
  42. https://www3.nd.edu/~apillay/pdf/lecturenotes_modeltheory.pdf
  43. https://math.berkeley.edu/~scanlon/225af13lectures/ModelTheoryNotes.pdf
  44. https://people.math.sc.edu/mcnulty/762/modeltheory.pdf
  45. https://arxiv.org/pdf/2506.22326
  46. https://www.math.ucla.edu/~ynm/papers/1602-002-1.pdf
  47. https://philpapers.org/rec/MOSKAS
  48. https://logic.pdmi.ras.ru/~yumat/personaljournal/H10history/H10histe.pdf
  49. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  50. https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf
  51. https://compcalc.github.io/public/church/church_calculi_1941.pdf
  52. https://www.classes.cs.uchicago.edu/archive/2007/spring/32001-1/papers/church-1940.pdf
  53. https://softwarefoundations.cis.upenn.edu/plf-current/Stlc.html
  54. https://dl.acm.org/doi/10.1109/SFCS.1977.32
  55. https://ntrs.nasa.gov/api/citations/19910003795/downloads/19910003795.pdf
  56. http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf
  57. https://disi.unitn.it/~bernardi/RSISE11/Papers/curry-howard.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.