In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, the spectrum of a sentence is the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s occurring as the size of a
finite model in which a given
sentence is true.
Definition
Let ''ψ'' be a sentence in
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 ...
. The ''spectrum'' of ''ψ'' is the set of natural numbers ''n'' such that there is a finite model for ''ψ'' with ''n'' elements.
If the vocabulary for ''ψ'' consists only of relational symbols, then ''ψ'' can be regarded as a sentence in
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 ...
(ESOL) quantified over the relations, over the empty vocabulary. A ''generalised spectrum'' is the set of models of a general ESOL sentence.
Examples
* The spectrum of the first-order formula
:
:
:
is
, the set of powers of a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. Indeed, with
for
and
for
, this sentence describes the set of
fields
Fields may refer to:
Music
* Fields (band), an indie rock band formed in 2006
* Fields (progressive rock band), a progressive rock band formed in 1971
* ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010)
* "Fields", a song b ...
; the
cardinality of a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
is the power of a prime number.
* The spectrum of the monadic second-order logic formula
is the set of
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
numbers. Indeed,
is a
bijection between
and
, and
and
are a partition of the universe. Hence the cardinality of the universe is even.
* The set of finite and co-finite sets is the set of spectra of first-order logic with the successor relation.
* The set of ultimately periodic sets is the set of spectra of monadic second-order logic with a unary function. It is also the set of spectra of monadic second-order logic with the successor function.
Properties
''
Fagin's theorem'' is a result in
descriptive complexity theory
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity clas ...
that states that the set of all properties expressible in 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 on ...
is precisely the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
. The theorem was proven by
Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).
Equivalence to Turing machines
As a corollary, Jones and
Selman showed that a set is a spectrum if and only if it is in the complexity class
NEXP In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^.
In terms of NTIME,
:\mathsf = \bigcup_ \mathsf(2^)
...
.
[* ]
One direction of the proof is to show that, for every first-order formula
, the problem of determining whether there is a model of the formula of
cardinality ''n'' is equivalent to the
problem of satisfying a formula of size polynomial in ''n'', which is in NP(n) and thus in NEXP of the input to the problem (the number ''n'' in binary form, which is a string of size log(''n'')).
This is done by replacing every
existential quantifier
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, w ...
in
with
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
over all the elements in the model and replacing every
universal quantifier with
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
over all the elements in the model. Now every predicate is on elements in the model, and finally every appearance of a predicate on specific elements is replaced by a new propositional variable. Equalities are replaced by their truth values according to their assignments.
For example:
For a model of cardinality 2 (i.e. ''n''= 2) is replaced by
Which is then replaced by
where
is truth,
is falsity, and
,
are propositional variables.
In this particular case, the last formula is equivalent to
, which is satisfiable.
The other direction of the proof is to show that, for every set of binary strings accepted by a non-deterministic Turing machine running in exponential time (
for input length x), there is a first-order formula
such that the set of numbers represented by these binary strings are the spectrum of
.
Jones and Selman mention that the spectrum of first-order formulas without equality is just the set of all natural numbers not smaller than some minimal cardinality.
Other properties
The set of spectra of a theory is closed under
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
intersection, addition, and multiplication. In full generality, it is not known if the set of spectra of a theory is closed by complementation; this is the so-called Asser's Problem.
See also
*
Spectrum of a theory
In model theory, a branch of mathematical logic, the spectrum of a theory
is given by the number of isomorphism classes of models in various cardinalities. More precisely,
for any complete theory ''T'' in a language we write ''I''(''T'', ''κ'' ...
References
*
*
*
*
{{Mathematical logic
Finite model theory