section_path: Basic concepts/Formal systems
section_name: Formal systems
paragraph_text: Formal systems
  
  A formal system of logic consists of a formal language together with a set of axioms and a proof system used to draw inferences from these axioms. In logic, axioms are statements that are accepted without proof. They are used to justify other statements. Some theorists also include a semantics that specifies how the expressions of the formal language relate to real objects. Starting in the late 19th century, many new formal systems have been proposed.
  
  A formal language consists of an alphabet and syntactic rules. The alphabet is the set of basic symbols used in expressions. The syntactic rules determine how these symbols may be arranged to result in well-formed formulas. For instance, the syntactic rules of propositional logic determine that " P ∧ Q {\displaystyle P\land Q} " is a well-formed formula but " ∧ Q {\displaystyle \land Q} " is not since the logical conjunction ∧ {\displaystyle \land } requires terms on both sides.
  
  A proof system is a collection of rules to construct formal proofs. It is a tool to arrive at conclusions from a set of axioms. Rules in a proof system are defined in terms of the syntactic form of formulas independent of their specific content. For instance, the classical rule of conjunction introduction states that P ∧ Q {\displaystyle P\land Q} follows from the premises P {\displaystyle P} and Q {\displaystyle Q}. Such rules can be applied sequentially, giving a mechanical procedure for generating conclusions from premises. There are different types of proof systems including natural deduction and sequent calculi.
  
  A semantics is a system for mapping expressions of a formal language to their denotations. In many systems of logic, denotations are truth values. For instance, the semantics for classical propositional logic assigns the formula P ∧ Q {\displaystyle P\land Q} the denotation "true" whenever P {\displaystyle P} and Q {\displaystyle Q} are true. From the semantic point of view, a premise entails a conclusion if the conclusion is true whenever the premise is true.
  
  A system of logic is sound when its proof system cannot derive a conclusion from a set of premises unless it is semantically entailed by them. In other words, its proof system cannot lead to false conclusions, as defined by the semantics. A system is complete when its proof system can derive every conclusion that is semantically entailed by its premises. In other words, its proof system can lead to any true conclusion, as defined by the semantics. Thus, soundness and completeness together describe a system whose notions of validity and entailment line up perfectly.