Empty domain

Last updated
In modern logic only the contradictories in the square of opposition apply, because domains may be empty.

(Black areas are empty,
red areas are nonempty.) Square of opposition, set diagrams.svg
In modern logic only the contradictories in the square of opposition apply, because domains may be empty.

(Black areas are empty,
red areas are nonempty.)

In first-order logic, the empty domain is the empty set having no members. In traditional and classical logic domains are restrictedly non-empty in order that certain theorems be valid. Interpretations with an empty domain are shown to be a trivial case by a convention originating at least in 1927 with Bernays and Schönfinkel (though possibly earlier) but oft-attributed to Quine's 1951 Mathematical Logic. [1] The convention is to assign any formula beginning with a universal quantifier the value truth, while any formula beginning with an existential quantifier is assigned the value falsehood. This follows from the idea that existentially quantified statements have existential import (i.e. they imply the existence of something) while universally quantified statements do not. This interpretation reportedly stems from George Boole in the late 19th century but this is debatable. In modern model theory, it follows immediately for the truth conditions for quantified sentences:

In other words, an existential quantification of the open formula φ is true in a model iff there is some element in the domain (of the model) that satisfies the formula; i.e. iff that element has the property denoted by the open formula. A universal quantification of an open formula φ is true in a model iff every element in the domain satisfies that formula. (Note that in the metalanguage, "everything that is such that X is such that Y" is interpreted as a universal generalization of the material conditional "if anything is such that X then it is such that Y". Also, the quantifiers are given their usual objectual readings, so that a positive existential statement has existential import, while a universal one does not.) An analogous case concerns the empty conjunction and the empty disjunction. The semantic clauses for, respectively, conjunctions and disjunctions are given by

It is easy to see that the empty conjunction is trivially true, and the empty disjunction trivially false.

Logics whose theorems are valid in every, including the empty, domain were first considered by Jaskowski 1934, Mostowski 1951, Hailperin 1953, Quine 1954, Leonard 1956, and Hintikka 1959. While Quine called such logics "inclusive" logic they are now referred to as free logic.

See also

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.

<span class="mw-page-title-main">De Morgan's laws</span> Pair of logical equivalences

In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.

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.

In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, when used together with a predicate variable, is called an existential quantifier ("x" or "∃(x)" or "(∃x)"). Existential quantification is distinct from universal quantification ("for all"), which asserts that the property or relation holds for all members of the domain. Some sources use the term existentialization to refer to existential quantification.

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.

In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers.

In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica.

In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension holds for at least the positive formulas.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic.

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.

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier. Lindström quantifiers generalize first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers. They were introduced by Per Lindström in 1966. They were later studied for their applications in logic in computer science and database query languages.

In constructive mathematics, Church's thesis is the principle stating that all total functions are computable functions.

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

Dependence logic is a logical formalism, created by Jouko Väänänen, which adds dependence atoms to the language of first-order logic. A dependence atom is an expression of the form , where are terms, and corresponds to the statement that the value of is functionally dependent on the values of .

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.

Feferman–Vaught theorem in model theory is a theorem by Solomon Feferman and Robert Lawson Vaught that shows how to reduce, in an algorithmic way, the first-order theory of a product of structures to the first-order theory of elements of the structure.

References

  1. Quine, W. V. (1951). Mathematical Logic. Harvard University Press. doi:10.4159/9780674042469. ISBN   978-0-674-04246-9.