Heyting arithmetic
Encyclopedia
In mathematical logic
, Heyting arithmetic (sometimes abbreviated HA) is an axiomatization of arithmetic in accordance with the philosophy of intuitionism
. It is named after Arend Heyting
, who first proposed it.
Heyting arithmetic adopts the axioms of Peano arithmetic (PA), but uses intuitionistic logic
as its rules of inference. In particular, the law of the excluded middle does not hold in general, though the induction axiom can be used to prove many specific cases. For instance, one can prove that is a theorem (any two natural number
s are either equal to each other, or not equal to each other). In fact, since "=" is the only predicate symbol in Heyting arithmetic, it then follows that, for any quantifier-free formula p, is a theorem (where x, y, z… are the free variables in p).
Kurt Gödel
studied the relationship between Heyting arithmetic and Peano arithmetic. He used the Gödel–Gentzen negative translation
to prove in 1933 that if HA is consistent, then PA is also consistent.
Heyting arithmetic should not be confused with Heyting algebra
s, which are the intuitionistic analogue of Boolean algebras.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, Heyting arithmetic (sometimes abbreviated HA) is an axiomatization of arithmetic in accordance with the philosophy of intuitionism
Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...
. It is named after Arend Heyting
Arend Heyting
Arend Heyting was a Dutch mathematician and logician. He was a student of Luitzen Egbertus Jan Brouwer at the University of Amsterdam, and did much to put intuitionistic logic on a footing where it could become part of mathematical logic...
, who first proposed it.
Heyting arithmetic adopts the axioms of Peano arithmetic (PA), but uses intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
as its rules of inference. In particular, the law of the excluded middle does not hold in general, though the induction axiom can be used to prove many specific cases. For instance, one can prove that is a theorem (any two natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s are either equal to each other, or not equal to each other). In fact, since "=" is the only predicate symbol in Heyting arithmetic, it then follows that, for any quantifier-free formula p, is a theorem (where x, y, z… are the free variables in p).
Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
studied the relationship between Heyting arithmetic and Peano arithmetic. He used the Gödel–Gentzen negative translation
Gödel–Gentzen negative translation
In proof theory, the Gödel–Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic first-order logic. It is one of a number of double-negation translations that are of importance to the metatheory of intuitionistic logic...
to prove in 1933 that if HA is consistent, then PA is also consistent.
Heyting arithmetic should not be confused with Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
s, which are the intuitionistic analogue of Boolean algebras.
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
: "Intuitionistic Number Theory" by Joan Moschovakis.