In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
a branching quantifier,
also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering
:
of
quantifiers for ''Q'' ∈ . It is a special case of
generalized quantifier In formal semantics, a generalized quantifier (GQ) is an expression that denotes a set of sets. This is the standard semantics assigned to quantified noun phrases. For example, the generalized quantifier ''every boy'' denotes the set of sets of ...
. In
classical logic
Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this class ...
, quantifier prefixes are linearly ordered such that the value of a variable ''y
m'' bound by a quantifier ''Q
m'' depends on the value of the variables
: ''y''
1, ..., ''y''
''m''−1
bound by quantifiers
: ''Qy''
1, ..., ''Qy''
''m''−1
preceding ''Q
m''. In a logic with (finite) partially ordered quantification this is not in general the case.
Branching quantification first appeared in a 1959 conference paper of
Leon Henkin
Leon Albert Henkin (April 19, 1921, Brooklyn, New York - November 1, 2006, Oakland, California) was an American logician, whose works played a strong role in the development of logic, particularly in the theory of types. He was an active scholar ...
. Systems of partially ordered quantification are intermediate in strength between
first-order logic
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 quantifie ...
and
second-order logic
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.
First-order logic quantifies onl ...
. They are being used as a basis for
Hintikka's and Gabriel Sandu's
independence-friendly logic
Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and in 1989) is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form (\exists v/V) and (\forall v/V), where V is a finite set of variables. ...
.
Definition and properties
The simplest Henkin quantifier
is
:
It (in fact every formula with a Henkin prefix, not just the simplest one) is equivalent to its second-order
Skolemization
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.
Every first-order formula may be converted into Skolem normal form while not changing it ...
, i.e.
:
It is also powerful enough to define the quantifier
(i.e. "there are infinitely many") defined as
:
Several things follow from this, including the nonaxiomatizability of first-order logic with
(first observed by
Ehrenfeucht), and its equivalence to the
-fragment of
second-order logic
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.
First-order logic quantifies onl ...
(
existential second-order logic
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.
First-order logic quantifies onl ...
)—the latter result published independently in 1970 by
Herbert Enderton
Herbert Bruce Enderton (April 15, 1936 – October 20, 2010) was an American mathematician. He was a Professor Emeritus of Mathematics at UCLA and a former member of the faculties of Mathematics and of Logic and the Methodology of Science at the ...
and W. Walkoe.
The following quantifiers are also definable by
.
* Rescher: "The number of ''φ''s is less than or equal to the number of ''ψ''s"
::