Second-order logic in the context of "Satisfiability and validity"

In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory ${\displaystyle T}$ is consistent if there is no formula ${\displaystyle \varphi }$ such that both ${\displaystyle \varphi }$ and its negation ${\displaystyle \lnot \varphi }$ are elements of the set of consequences of ${\displaystyle T}$. Let ${\displaystyle A}$ be a set of closed sentences (informally "axioms") and ${\displaystyle \langle A\rangle }$ the set of closed sentences provable from ${\displaystyle A}$ under some (specified, possibly implicitly) formal deductive system. The set of axioms ${\displaystyle A}$ is consistent when there is no formula ${\displaystyle \varphi }$ such that ${\displaystyle \varphi \in \langle A\rangle }$ and ${\displaystyle \lnot \varphi \in \langle A\rangle }$. A trivial theory (i.e., one which proves every sentence in the language of the theory) is clearly inconsistent. Conversely, in an explosive formal system (e.g., classical or intuitionistic propositional or first-order logics) every inconsistent theory is trivial. Consistency of a theory is a syntactic notion, whose semantic counterpart is satisfiability. A theory is satisfiable if it has a model, i.e., there exists an interpretation under which all axioms in the theory are true. This is what consistent meant in traditional Aristotelian logic, although in contemporary mathematical logic the term satisfiable is used instead.

In a sound formal system, every satisfiable theory is consistent, but the converse does not hold. If there exists a deductive system for which these semantic and syntactic definitions are equivalent for any theory formulated in a particular deductive logic, the logic is called complete. The completeness of the propositional calculus was proved by Paul Bernays in 1918 and Emil Post in 1921, while the completeness of (first order) predicate calculus was proved by Kurt Gödel in 1930, and consistency proofs for arithmetics restricted with respect to the induction axiom schema were proved by Ackermann (1924), von Neumann (1927) and Herbrand (1931). Stronger logics, such as second-order logic, are not complete.

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier ${\displaystyle \forall }$ in the first-order formula ${\displaystyle \forall xP(x)}$ expresses that everything in the domain satisfies the property denoted by ${\displaystyle P}$. On the other hand, the existential quantifier ${\displaystyle \exists }$ in the formula ${\displaystyle \exists xP(x)}$ expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

The most commonly used quantifiers are ${\displaystyle \forall }$ and ${\displaystyle \exists }$. These quantifiers are standardly defined as duals; in classical logic: each can be defined in terms of the other using negation. They can also be used to define more complex quantifiers, as in the formula ${\displaystyle \neg \exists xP(x)}$ which expresses that nothing has the property ${\displaystyle P}$. Other quantifiers are only definable within second-order logic or higher-order logics. Quantifiers have been generalized beginning with the work of Andrzej Mostowski and Per Lindström.