Nonfirstorderizability

Last updated February 10, 2024

In formal logic, nonfirstorderizability is the inability of a natural-language statement to be adequately captured by a formula of first-order logic. Specifically, a statement is nonfirstorderizable if there is no formula of first-order logic which is true in a model if and only if the statement holds in that model. Nonfirstorderizable statements are sometimes presented as evidence that first-order logic is not adequate to capture the nuances of meaning in natural language.

The term was coined by George Boolos in his paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)".^[1] Quine argued that such sentences call for second-order symbolization, which can be interpreted as plural quantification over the same domain as first-order quantifiers use, without postulation of distinct "second-order objects" (properties, sets, etc.).

Examples

Geach-Kaplan sentence

A standard example is the Geach–Kaplan sentence: "Some critics admire only one another." If Axy is understood to mean "x admires y," and the universe of discourse is the set of all critics, then a reasonable translation of the sentence into second order logic is:

\exists X(\exists x,y(Xx\land Xy\land Axy)\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land Axy\rightarrow Xy))

That this formula has no first-order equivalent can be seen by turning it into a formula in the language of arithmetic . Substitute the formula ${\textstyle (y=x+1\lor x=y+1)}$ for Axy. The result,

\exists X(\exists x,y(Xx\land Xy\land (y=x+1\lor x=y+1))\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land (y=x+1\lor x=y+1)\rightarrow Xy))

states that there is a set $X$ with these properties:

There are at least two numbers in $X$
There is a number that does not belong to $X$ , i.e. $X$ does not contain all numbers.
If a number $x$ belongs to $X$ and $y$ is $x + 1$ or $x - 1$ , $y$ also belongs to $X$ .

A model of a formal theory of arithmetic, such as first-order Peano arithmetic, is called standard if it only contains the familiar natural numbers $0, 1, 2, ...$ as elements. The model is called non-standard otherwise. Therefore, the formula given above is true only in non-standard models, because, in the standard model, the set $X$ must contain all available numbers $0, 1, 2, ...$ . In addition, there is a set $X$ satisfying the formula in every non-standard model.

Let us assume that there is a first-order rendering of the above formula called $E$ . If $\neg E$ were added to the Peano axioms, it would mean that there were no non-standard models of the augmented axioms. However, the usual argument for the existence of non-standard models would still go through, proving that there are non-standard models after all. This is a contradiction, so we can conclude that no such formula $E$ exists in first-order logic.

Finiteness of the domain

There is no formula $A$ in first-order logic with equality which is true of all and only models with finite domains. In other words, there is no first-order formula which can express "there is only a finite number of things".

This is implied by the compactness theorem as follows.^[2] Suppose there is a formula $A$ which is true in all and only models with finite domains. We can express, for any positive integer $n$ , the sentence "there are at least $n$ elements in the domain". For a given $n$ , call the formula expressing that there are at least $n$ elements $B n$ . For example, the formula $B 3$ is:

\exists x\exists y\exists z(x\neq y\wedge x\neq z\wedge y\neq z)

which expresses that there are at least three distinct elements in the domain. Consider the infinite set of formulae

A,B_{2},B_{3},B_{4},\ldots

Every finite subset of these formulae has a model: given a subset, find the greatest $n$ for which the formula $B n$ is in the subset. Then a model with a domain containing $n$ elements will satisfy $A$ (because the domain is finite) and all the $B$ formulae in the subset. Applying the compactness theorem, the entire infinite set must also have a model. Because of what we assumed about $A$ , the model must be finite. However, this model cannot be finite, because if the model has only $m$ elements, it does not satisfy the formula $B m+1$ . This contradiction shows that there can be no formula $A$ with the property we assumed.

Other examples

The concept of identity cannot be defined in first-order languages, merely indiscernibility.^[3]
The Archimedean property that may be used to identify the real numbers among the real closed fields.
The compactness theorem implies that graph connectivity cannot be expressed in first-order logic.^{[ clarification needed ]}

Related Research Articles

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canonical normal form, it is useful in automated theorem proving and circuit theory.

In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any", "for all", or "for any". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other words, it is the predication of a property or relation to every member of the domain. It asserts that a predicate within the scope of a universal quantifier is true of every value of a predicate variable.

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not assume the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing the natural numbers. It was first published by Ernst Zermelo as part of his set theory in 1908.

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propositional logic, it provides a canonical normal form useful in automated theorem proving.

Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.

Tarski's axioms are an axiom system for Euclidean geometry, specifically for that portion of Euclidean geometry that is formulable in first-order logic with identity. As such, it does not require an underlying set theory. The only primitive objects of the system are "points" and the only primitive predicates are "betweenness" and "congruence". The system contains infinitely many axioms.

In set theory, $-induction$ , also called epsilon-induction or set-induction, is a principle that can be used to prove that all sets satisfy a given property. Considered as an axiomatic principle, it is called the axiom schema of set induction.

In mathematical logic, Heyting arithmetic $is an axiomatization of arithmetic in accordance with the philosophy of intuitionism. It is named after Arend Heyting, who first proposed it.$

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with " $" and " " of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.$

In mathematics, a set $is inhabited if there exists an element .$

In logic, the monadic predicate calculus is the fragment of first-order logic in which all relation symbols in the signature are monadic, and there are no function symbols. All atomic formulas are thus of the form $, where is a relation symbol and is a variable.$

General set theory (GST) is George Boolos's (1998) name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.

In mathematical logic, a formula is satisfiable if it is true under some assignment of values to its variables. For example, the formula $is satisfiable because it is true when and, while the formula is not satisfiable over the integers. The dual concept to satisfiability is validity; a formula is valid if every assignment of values to its variables makes the formula true. For example, is valid over the integers, but is not.$

In mathematical logic the theory of pure equality is a first-order theory. It has a signature consisting of only the equality relation symbol, and includes no non-logical axioms at all.

In mathematical logic, the quantifier rank of a formula is the depth of nesting of its quantifiers. It plays an essential role in model theory.

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 $in the first order formula expresses that everything in the domain satisfies the property denoted by . On the other hand, the existential quantifier in the formula 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.$

References

↑ Boolos, George (August 1984). "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)". The Journal of Philosophy. 81 (8): 430–449. doi:10.2307/2026308. JSTOR 2026308. Reprinted in Boolos, George (1998). Logic, Logic, and Logic. Cambridge, MA: Harvard University Press. ISBN 0-674-53767-X.
↑ Intermediate Logic (PDF). Open Logic Project. p. 235. Retrieved 21 March 2022.
↑ Noonan, Harold; Curtis, Ben (2014-04-25). "Identity". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy .

External links

Printer-friendly CSS, and nonfirstorderisability by Terence Tao

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[boolos-to-be-1] Boolos, George (August 1984). "To Be Is to Be a Value of a Variable (or to Be Some Values of Some Variables)". The Journal of Philosophy. 81 (8): 430–449. doi:10.2307/2026308. JSTOR 2026308. Reprinted in Boolos, George (1998). Logic, Logic, and Logic. Cambridge, MA: Harvard University Press. ISBN 0-674-53767-X.

[2] Intermediate Logic (PDF). Open Logic Project. p. 235. Retrieved 21 March 2022.

[3] Noonan, Harold; Curtis, Ben (2014-04-25). "Identity". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy .

[1]

[2]

[3]