Metalogic

Metalogic is a study of formal languages of logic from both syntactic and semantic perspectives. Formal languages consist of vocabulary (constants, variables, connectives, etc.) and formation rules (or grammar) of formulas in the language. Semantics concerns the interpretations of the elements of formal languages. Syntax provides deductive devices for formal languages on the top of their vocabulary and formation rules. Some of the most important properties that are frequently studied in metalogic are: soundness, completeness (in various sense), compactness, decidability, etc.

Formal Languages of Logic

Formal languages are artificial languages designed to clearly express statements in various areas of studies. There are varieties of formal languages and they are chosen depending on the subjects and the purposes of studies. A formal language consists of vocabulary and formation rules. Vocabulary postulates the linguistic symbols that are used to build the expressions. (To see the point, consider natural languages. Say, English provides "small," "tall" and etc. as a part of its vocabulary.) The formation rules define the ways to build the expressions from the vocabulary. (Again in the case of English, we can form a noun phrase "small dog" based on the grammar of English.)

One of the simplest (but also the most important) examples of formal languages is the language of propositional logic (let us denote this language as PL). The vocabulary of PL consists of:

1. Propositional variables, p, q, r,…, (which are considered to stand for propositions)
2. Propositional connectives ${\displaystyle \lnot }$, ${\displaystyle \wedge }$, ${\displaystyle \vee }$, ${\displaystyle \rightarrow }$, ${\displaystyle \leftrightarrow }$, (interpreted as sentential connectives in natural language: not, and, or, if…then…, …if and only if…respectively in order)
3. parentheses, "(," ")."

The formation rules of PL are given inductively and define the permissible formulas in PL, called well-formed formulas (abbreviated as wff). The definition of wffs is as follows:

• a. A propositional variable is a wff.
• b. If ${\displaystyle \phi }$ is a wff, then ${\displaystyle \lnot \phi }$ is a wff.
• c. If ${\displaystyle \phi }$ and ${\displaystyle \psi }$ are both wffs, then ${\displaystyle (\phi \wedge \psi )}$, ${\displaystyle (\phi \vee \psi )}$, ${\displaystyle (\phi \rightarrow \psi )}$, ${\displaystyle (\phi \leftrightarrow \psi )}$ are all wffs.
• d. Things built from a, b, c exhaust the wffs.

Observe that, say, “ ${\displaystyle ((p\wedge \lnot q)\rightarrow r)}$” is a wff by this inductive definition. Other frequently used formal languages are first-order logic, second-order language, languages of modal logic, etc.

Semantics

(For a general explanation about Semantic in linguistics, see Semantics.)

Formal languages, as they are, just stipulate meaningless strings of symbols. Semantics takes care of the aspects about the meanings of the symbols in the language and defines the relevant important notions for linguistic expressions. An interpretation (also called a model, a structure, etc) of a given formal language determines various kinds of assignments to the symbols of the language. In our previous example, PL, an interpretation is a function ${\displaystyle I}$ that assigns one or zero (considered to be truth and falsity usually) to propositional variables. Likewise, interpretations for various kinds of languages are given in similar ways so that certain kinds of entities are assigned to the expressions of the languages.

The notion of truth is defined relative to an interpretation for all the wffs. For instance, in PL, the notion of truth is inductively defined as follows ( ${\displaystyle \phi }$ and ${\displaystyle \psi }$ are both wffs):

• a. p is true under ${\displaystyle I}$ (with p a propositional variable) iff ${\displaystyle I(p)=1}$.
• b. ${\displaystyle \phi \wedge \psi }$ is true under ${\displaystyle I}$ iff ${\displaystyle \phi }$ is true under ${\displaystyle I}$ and ${\displaystyle \psi }$ is true under ${\displaystyle I}$.
• c. ${\displaystyle \phi \vee \psi }$ is true under ${\displaystyle I}$ iff ${\displaystyle \phi }$ is true under ${\displaystyle I}$ or ${\displaystyle \psi }$ is true under ${\displaystyle I}$.
• d. ${\displaystyle \phi \rightarrow \psi }$ is true under ${\displaystyle I}$ iff ${\displaystyle \phi }$ is not true under ${\displaystyle I}$ or ${\displaystyle \psi }$ is true under ${\displaystyle I}$.
• e. ${\displaystyle \phi \leftrightarrow \psi }$ is true under ${\displaystyle I}$ iff ${\displaystyle \phi }$ is true under ${\displaystyle I}$ and ${\displaystyle \psi }$ is true under ${\displaystyle I}$, or ${\displaystyle \phi }$ is not true under ${\displaystyle I}$ and ${\displaystyle \psi }$ is true under ${\displaystyle I}$.

(To see how the definition works, consider, say, “ ${\displaystyle (p\vee \lnot q)}$” under an interpretation ${\displaystyle I}$ that assigns zero to both p and q. First, a wff ${\displaystyle \lnot q}$ is true under ${\displaystyle I}$ since ${\displaystyle q}$ is false ( ${\displaystyle I(q)=0}$). Thus, ${\displaystyle (p\vee \lnot q)}$ turns out to be true under ${\displaystyle I}$.) We often put " ${\displaystyle I\models \phi }$" to be read as " ${\displaystyle \phi }$ is true under ${\displaystyle I}$." Also, given an interpretation ${\displaystyle I}$, we call the theory of ${\displaystyle I}$ a set of wffs that are true under ${\displaystyle I}$.

Another set of important semantic notions are the notions of satisfiability and validity. These notions are defined based on the notion of truth. A wff ${\displaystyle \phi }$ in a formal language L is satisfiable if and only if there is an interpretation ${\displaystyle I}$ such that that ${\displaystyle \phi }$ is true under ${\displaystyle I}$. Similarly we call a set ${\displaystyle \Gamma }$ of wffs satisfiable if and only if there is an interpretation ${\displaystyle I}$ such that all the sentences in ${\displaystyle \Gamma }$ are true under ${\displaystyle I}$. For example, consider the wff " ${\displaystyle (p\wedge \lnot q)}$" and " ${\displaystyle p\wedge \lnot p}$." The former is satisfiable since it is true under the interpretation ${\displaystyle I}$ such that ${\displaystyle I(p)=1}$ and ${\displaystyle I(q)=0}$, while it is not difficult to see that the latter is not satisfiable. A wff ${\displaystyle \phi }$ is valid if and only if ${\displaystyle \phi }$ is true under all the interpretation for L. In PL, consider, say, the wff " ${\displaystyle p\vee \lnot p}$." This wff turns out to be true no matter which value, zero or one, p gets assigned; therefore, the wff is valid.

Syntax

(For a general explanation of Syntax in linguistics, see Syntax)

While the semantics of a formal language deals with the assignments of the meanings to the symbols and the relevant notions, truth, validity etc., the syntax of a formal language, in addition to the formation rules of wffs, deals with a transformation of wffs of distinguished forms based on the transformation rules. This transformational setting of a formal language is called a deductive system (based on the formal language).

Given a formal language, a deductive system is specified with the set of logical axioms and the rules of inferences. Logical axioms are given by wffs or forms of wffs, and the rules of inference determines the permissible ways of transforming given wffs. If a wff ${\displaystyle \phi }$ can be obtained as a result of transforming some of the logical axioms by the rules of inferences, ${\displaystyle \phi }$ is said to be provable or a theorem in the deductive system.

For instance, a deductive system in PL can be given as follows (for simplicity, the outermost parentheses of wffs are omitted below). First, we define formulas of the forms ${\displaystyle \phi \wedge \psi }$, ${\displaystyle \phi \vee \psi }$, ${\displaystyle \phi \leftrightarrow \psi }$ respectively as ${\displaystyle \lnot (\phi \rightarrow \lnot \psi )}$, ${\displaystyle \lnot \phi \rightarrow \psi }$, ${\displaystyle (\phi \rightarrow \psi )\wedge (\psi \rightarrow \phi )}$. Observe that, with this definition, we can always rewrite all the wffs in PL with only propositional variables, ${\displaystyle \lnot }$, and ${\displaystyle \rightarrow }$. Now, the logical axioms are given as the wffs of the forms that are specified in the following schemas:

• A1 ${\displaystyle \alpha \rightarrow (\beta \rightarrow \alpha )}$
• A2 ${\displaystyle (\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow ((\alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \gamma ))}$
• A3 ${\displaystyle (\lnot \alpha \rightarrow \lnot \beta )\rightarrow (\beta \rightarrow \alpha )}$

Also, the rule of inference of the deductive system is given as the following rule (generally called modus ponens and modus tollens):

• MP If you have the wffs of the forms ${\displaystyle \phi }$ and ${\displaystyle \phi \rightarrow \psi }$, then obtain ${\displaystyle \psi }$.

For example, observe that " ${\displaystyle p\rightarrow (q\rightarrow p)}$" is an axiom by A1 and that " ${\displaystyle (p\rightarrow (q\rightarrow p))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow p))}$" is an axiom by A3. Then, we obtain " ${\displaystyle (p\rightarrow q)\rightarrow (p\rightarrow p)}$" as a theorem in this deductive system by MP.

There are other types of deductive systems in PL and also there are various deductive systems in other types of formal languages.

On the top of deductive systems, we often consider additional nonlogical axioms (specified wffs other than logical axioms) that characterize the main subjects in a given area of study. In such cases, we consider axiomatic systems, which are specified as the set of nonlogical axioms (of course, deductive systems are also axiomatic systems in the sense that the set of specified nonlogical axioms is empty). Given an axiomatic system A, we call a wff provable in A if it is obtainable from logical axioms and the nonlogical axioms in A based on the rules of inferences.

Basic Metalogical Properties

Metalogic is the study of formal languages from semantic and syntactic perspectives. Among the metalogical properties of formal languages, we will look at some of the most basic and important ones below to get the sense about what the metalogical properties are like. The list consists of soundness, completeness (in at least two important senses), compactness, and decidability.

Soundness and Completeness

The first set of metalogical notions that we look at are the soundness and completeness. These notions connect the semantic notion of validity and the syntactic notion of provability (or theoremhood) in the following way. A deductive system is called sound if, for every wff ${\displaystyle \phi }$, the provability of ${\displaystyle \phi }$ implies the validity of ${\displaystyle \phi }$. Also, a deductive system is called complete if, for every wff ${\displaystyle \phi }$, the validity of ${\displaystyle \phi }$ implies the provability of ${\displaystyle \phi }$.

Many formal languages are known with respect to which semantics S and deductive systems D are given so that D is both sound and complete with respect to S. In fact, in our example of PL, its semantics and its deductive system are one of sound and complete formal systems. Also, it is well known that we can have semantics and deductive systems on the first-order logic that are both sound and complete, and also on modal logic.

However, there are other languages on which there are no complete deductive systems. One famous example is the second-order logic.

Compactness

The next metalogical property is compactness. This property mainly concerns the notion of satisfiablity. A language L is compact if, for every set ${\displaystyle \Gamma }$ of wffs in L, ${\displaystyle \Gamma }$ is satisfiable if every finite subset of wffs in ${\displaystyle Gamma}$ is satisfiable.

PL and other formal languages such as first-order logic and many languages for modal logic are known to be compact. However, languages such as second-order language are known not to be compact.

Completeness

Another important metalogical property is completeness in a different sense from the one above. An axiomatic system is complete if, for every wff ${\displaystyle \phi }$, either ${\displaystyle \phi }$ itself or ${\displaystyle \lnot \phi }$ is provable in A.

There are many axiomatic systems that are known to be complete. One famous example is Presburger arithmetic (roughly speaking, it is a theory in the first-order logic for the arithmetric only with addition) etc. On the other hand, there are many axiomatic systems that are known to be incomplete. Famous examples are Peano arithmetic, which is an axiomatic system for a full arithmetic.

Decidability

Decidability is also one of the important metalogical properties. One formulation of this property is as follows. A theory in a language L (for the definition of theory, see the paragraph above on the notion of truth in the semantics section) is said to be decidable if there is an effective procedure through which, for every wff ${\displaystyle \phi }$ in L, we can determine whether ${\displaystyle \phi }$ is in the theory or not.

There are various theories that are known to be decidable. For instance, Presburger arithmetic is one of them. On the other hand, Peano arithmetic is a famous example of the theories that are known to be undecidable.

References

ISBN links support NWE through referral fees

• Barwise, Jon and John Etchemendy. 2002. Language, Proof and Logic. CSLI Publication. ISBN 157586374X
• Boolos, George, John Burgess, and Richard Jeffrey. 2002. Computability and Logic, 4th ed. Cambridge University ISBN 0521809754
• Enderton, Herbert. 2002. A Mathematical Introduction to Logic, 2nd ed. Academic Press. ISBN 0122384520
• Hodges, Wilfred. 1997. A Shorter Model Theory. Cambridge University Press. ISBN 0521587131
• Mendelson, Elliott. 1997. Introduction to Mathematical Logic, 4th ed. Champan & Hall. ISBN 0412808307
• Troelstra A. S. and H. Schwichtenberg. 2000. Basic Proof Theory, 2nd. ed. Cambridge University Press. ISBN 0521779111

External links

All links retrieved November 9, 2022.

• Logic

General Philosophy Sources

• Stanford Encyclopedia of Philosophy
• The Internet Encyclopedia of Philosophy
• Paideia Project Online
• Project Gutenberg