Search Results for “heyting arithmetic”

Source: Heyting arithmetic

In mathematical logic, Heyting arithmetic

H
A

{\displaystyle {\mathsf {HA}}}

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

Axiomatization

Heyting

arithmetic

Heyting

arithmetic

Theorems

= Double negations

= Excluded middle

arithmetic

Heyting

arithmetic

= Conservativity

arithmetic

Unprovable statements

Heyting

arithmetic

= Classically independent propositions

arithmetic

= Unprovable classical principles

Heyting

arithmetic

In class notation, as familiar from set theory, an arithmetic statement

Q
(
n
)

{\displaystyle Q(n)}

is expressed as

n
∈
B

{\displaystyle n\in B}

where

B
:=
{
m
∈

N

∣
Q
(
m
)
}

{\displaystyle B:=\{m\in {\mathbb {N} }\mid Q(m)\}}

. For any given predicate of negated form, i.e.

ϕ
(
n
)
:=
¬
(
n
∈
B
)

{\displaystyle \phi (n):=\neg (n\in B)}

, a logical equivalent to induction is

¬
∃
(
n
∈
B
)
.
¬
∃
(
k
∈
B
)
.
k
<
n

↔

B
=
{
}

{\displaystyle \neg \exists (n\in B).\neg \exists (k\in B).k

The insight is that among subclasses

B
⊆

N

{\displaystyle B\subseteq {\mathbb {N} }}

, the property of (provably) having no least member is equivalent to being uninhabited, i.e. to being the empty class. Taking the contrapositive results in a theorem expressing that for any non-empty subclass, it cannot consistently be ruled out that there exists a member

n
∈
B

{\displaystyle n\in B}

such that there is no member

k
∈
B

{\displaystyle k\in B}

smaller than

n

{\displaystyle n}

:

B
≠
{
}

→

¬
¬
∃
(
n
∈
B
)
.
¬
∃
(
k
∈
B
)
.
k
<
n

{\displaystyle B\neq \{\}\,\to \,\neg \neg \exists (n\in B).\neg \exists (k\in B).k

In Peano arithmetic, where double-negation elimination is always valid, this proves the least number principle in its common formulation. In the classical reading, being non-empty is equivalent to (provably) being inhabited by some least member.
A binary relation "

<

{\displaystyle <}

" that validates the strong induction schema in the above form is always also irreflexive: Considering

ϕ

c

(
n
)
:=
(
n
≠
c
)

{\displaystyle \phi _{c}(n):=(n\neq c)}

or equivalently

Q

c

(
n
)
:=
(
n
=
c
)

{\displaystyle Q_{c}(n):=(n=c)}

for some fixed number

c

{\displaystyle c}

, the above simplifies to the statement that no member

k

{\displaystyle k}

of

B
=
{
c
}

{\displaystyle B=\{c\}}

validates

k
<
c

{\displaystyle k
, which is to say

¬
(
c
<
c
)

{\displaystyle \neg (c
. (And this logical deduction did not even use any other property of the binary relation.)
More generally, if

B

{\displaystyle B}

is non-empty and the associated (classical) least number principle can be used to prove some statement of negated form (such as

¬
(
c
<
c
)

{\displaystyle \neg (c
), then one can extend this to a fully constructive proof. This is because implications

α
→
¬
β

{\displaystyle \alpha \to \neg \beta }

are always intutionistically equivalent to the formally stronger

(
¬
¬
α
)
→
¬
β

{\displaystyle (\neg \neg \alpha )\to \neg \beta }

.
But in general, over constructive logic, the weakening of the least number principle can not be lifted. The following example demonstrates this: For some proposition

P

{\displaystyle P}

(say

C

f

{\displaystyle {\mathrm {C} _{f}}}

as above), consider the predicate

Q

P

(
n
)
:=
(
n
=
0
∧
P
)
∨
(
n
=
1
)

{\displaystyle Q_{P}(n):=(n=0\land P)\lor (n=1)}

This

Q

P

{\displaystyle Q_{P}}

corresponds to a subclass

b

P

:=
{
z
∈
{
0
}
∣
P
}
∪
{
1
}

{\displaystyle b_{P}:=\{z\in \{0\}\mid P\}\cup \{1\}}

of the natural numbers. One may ask what the least member of this class may be. Any number proven or assumed to be in this class provably either equals

0

{\displaystyle 0}

or

1

{\displaystyle 1}

, i.e.

b

P

⊆
{
0
,
1
}

{\displaystyle b_{P}\subseteq \{0,1\}}

. Using decidability of equality and the disjunctive syllogism proves the equivalence

P
↔

Q

P

(
0
)

{\displaystyle P\leftrightarrow Q_{P}(0)}

. If the underlying proposition

P

{\displaystyle P}

is independent, then the predicate is undecidable in the theory. Now since

1
=
1

{\displaystyle 1=1}

, the proposition

Q

P

(
1
)

{\displaystyle Q_{P}(1)}

is trivially true and so the class is inhabited:

1
∈

b

P

{\displaystyle 1\in b_{P}}

. In particular, least number existence for this class cannot be rejected. Given a conjunction with

Q

P

(
1
)

{\displaystyle Q_{P}(1)}

is trivial, the existence claim of a least number validating

Q

P

{\displaystyle Q_{P}}

itself translates to the excluded middle statement for

P

{\displaystyle P}

. Knowledge of such a number's value in fact determines whether or not

P

{\displaystyle P}

holds. So for independent

P

{\displaystyle P}

, the least number principle instance with

Q

P

{\displaystyle Q_{P}}

is also independent of

H
A

{\displaystyle {\mathsf {HA}}}

.
In set theory notation,

P

{\displaystyle P}

is equivalent to

0
∈

b

P

{\displaystyle 0\in b_{P}}

and so

b

P

=
{
0
,
1
}

{\displaystyle b_{P}=\{0,1\}}

, while its negation is also equivalent to

b

P

=
{
1
}

{\displaystyle b_{P}=\{1\}}

. This demonstrates that elusive predicates can define elusive subsets. And so also in constructive set theory, while the standard order on the class of naturals is decidable, the naturals are not well-ordered. But strong induction principles, that constructively do not imply unrealizable existence claims, are also still available.

= Anti-classical extensions

=
In a computable context, for a predicate

M

{\displaystyle M}

, the classically trivial infinite disjunction

∀
n
.

(

M
(
n
)
∨
¬
M
(
n
)

)

{\displaystyle \forall n.{\big (}M(n)\lor \neg M(n){\big )}}

,
also written

D
e
c

M

{\displaystyle {\mathrm {Dec} }_{M}}

, can be read as a validation of the decidability of a decision problem. In class notation,

M
(
n
)

{\displaystyle M(n)}

is also written

n
∈
M

{\displaystyle n\in M}

.

H
A

{\displaystyle {\mathsf {HA}}}

proves no propositions not provable by

P
A

{\displaystyle {\mathsf {PA}}}

and so, in particular, it does not reject any theorems of the classical theory. But there are also predicates

M

{\displaystyle M}

such that the axioms

H
A

+
¬

D
e
c

M

{\displaystyle {\mathsf {HA}}+\neg {\mathrm {Dec} }_{M}}

are consistent. Again, constructively, such a negation is not equivalent to the existence of a particular numerical counter-example

t

{\displaystyle t}

to excluded middle for

M
(
t
)

{\displaystyle M(t)}

. Indeed, already minimal logic proves the double-negated excluded middle for all propositions, and so

∀
n
.
¬
¬

(

Q
(
n
)
∨
¬
Q
(
n
)

)

{\displaystyle \forall n.\neg \neg {\big (}Q(n)\lor \neg Q(n){\big )}}

, which is equivalent to

¬
∃
n
.
¬

(

Q
(
n
)
∨
¬
Q
(
n
)

)

{\displaystyle \neg \exists n.\neg {\big (}Q(n)\lor \neg Q(n){\big )}}

, for any predicate

Q

{\displaystyle Q}

.

Church's thesis

Church's rule is an admissible rule in

H
A

{\displaystyle {\mathsf {HA}}}

. Church's thesis principle

C
T

0

{\displaystyle {\mathrm {CT} _{0}}}

may be adopted in

H
A

{\displaystyle {\mathsf {HA}}}

, while

P
A

{\displaystyle {\mathsf {PA}}}

rejects it: It implies negations such as the ones just described.
Consider the principle in the form stating that all predicates that are decidable in the logic sense above are also decidable by a total computable function. To see how it is in conflict with excluded middle, one merely needs to define a predicate that is not computably decidable.
To this end, write

Δ

e

(
w
)
:=

T

1

(
e
,
e
,
w
)

{\displaystyle \Delta _{e}(w):=T_{1}(e,e,w)}

for predicates defined from Kleene's T predicate. The indices

e

{\displaystyle e}

of total computable functions fulfill

∀
x
.
∃
w
.

T

1

(
e
,
x
,
w
)

{\displaystyle \forall x.\exists w.T_{1}(e,x,w)}

. While

T

1

{\displaystyle T_{1}}

can be realized in a primitive recursive fashion, the predicate

∃
w
.

Δ

e

(
w
)

{\displaystyle \exists w.\Delta _{e}(w)}

in

e

{\displaystyle e}

, i.e. the class

H
:=
{
e
∣
∃
w
.

Δ

e

(
w
)
}

{\displaystyle H:=\{e\mid \exists w.\Delta _{e}(w)\}}

of partial computable function indices with a witness describing how they halt on the diagonal, is computably enumerable but not computable. The classical compliment

M

{\displaystyle M}

defined using

¬
∃
w
.

Δ

e

(
w
)

{\displaystyle \neg \exists w.\Delta _{e}(w)}

is not even computably enumerable, see halting problem. This provenly undecidable problem

e
∈
M

{\displaystyle e\in M}

provides a violating example. For any index

e

{\displaystyle e}

, the equivalent form

∀
w
.
¬

Δ

e

(
w
)

{\displaystyle \forall w.\neg \Delta _{e}(w)}

expresses that when the corresponding function is evaluated (at

e

{\displaystyle e}

), then all conceivable descriptions of evaluation histories (

w

{\displaystyle w}

) do not describe the evaluation at hand. Specifically, this not being decidable for functions establishes the negation of what amounts to

W
L
P
O

{\displaystyle {\mathrm {WLPO} }}

.
The formal Church's principles are associated with the recursive school, naturally. Markov's principle

M
P

D
e
c

{\displaystyle {\mathrm {MP} _{\mathrm {Dec} }}}

is commonly adopted, by that school and by constructive mathematics more broadly. In the presence of Church's principle,

M
P

D
e
c

{\displaystyle {\mathrm {MP} _{\mathrm {Dec} }}}

is equivalent to its weaker form

M
P

P
R

{\displaystyle {\mathrm {MP} _{\mathrm {PR} }}}

. The latter can generally be expressed as a single axiom, namely double-negation elimination for any

¬
¬
∃
w
.

T

1

(
e
,
x
,
w
)

{\displaystyle \neg \neg \exists w.T_{1}(e,x,w)}

. Heyting arithmetic together with both

M
P

D
e
c

{\displaystyle {\mathrm {MP} _{\mathrm {Dec} }}}

+

E
C
T

0

{\displaystyle {\mathrm {ECT} _{0}}}

prove independence of premise for decidable predicates,

I
P

0

{\displaystyle {\mathrm {IP} }_{0}}

. But they do not go together, consistently, with

I
P

{\displaystyle {\mathrm {IP} }}

.

C
T

0

{\displaystyle {\mathrm {CT} _{0}}}

also negates

D
N
S

{\displaystyle {\mathrm {DNS} }}

. The intuitionist school of L. E. J. Brouwer extends Heyting arithmetic by
a collection of principles that negate both

P
E
M

{\displaystyle {\mathrm {PEM} }}

as well as

C
T

0

{\displaystyle {\mathrm {CT} _{0}}}

.

Models

= Consistency

=
If a theory is consistent, then no proof is one of an absurdity. Kurt Gödel introduced the negative translation and proved that if Heyting arithmetic is consistent, then so is Peano arithmetic. That is to say, he reduced the consistency task for

P
A

{\displaystyle {\mathsf {PA}}}

to that of

H
A

{\displaystyle {\mathsf {HA}}}

. However, Gödel's incompleteness theorems, about the incapability of certain theories to prove their own consistency, also applies to Heyting arithmetic itself.
The standard model of the classical first-order theory

P
A

{\displaystyle {\mathsf {PA}}}

as well as any of its non-standard models is also a model for Heyting arithmetic

H
A

{\displaystyle {\mathsf {HA}}}

.

= Set theory

=
There are also constructive set theory models for full

H
A

{\displaystyle {\mathsf {HA}}}

and its intended semantics. Relatively weak set theories suffice: They shall adopt the Axiom of infinity, the Axiom schema of predicative separation to prove induction of arithmetical formulas in

ω

{\displaystyle \omega }

, as well as the existence of function spaces on finite domains for recursive definitions.
Specifically, those theories do not require

P
E
M

{\displaystyle {\mathrm {PEM} }}

, the full axiom of separation or set induction (let alone the axiom of regularity), nor general function spaces (let alone the full axiom of power set).

H
A

{\displaystyle {\mathsf {HA}}}

furthermore is bi-interpretable with a weak constructive set theory in which the class of ordinals is

ω

{\displaystyle \omega }

, so that the collection of von Neumann naturals do not exist as a set in the theory. Meta-theoretically, the domain of that theory is as big as the class of its ordinals and essentially given through the class

F
i
n

{\displaystyle {\mathrm {Fin} }}

of all sets that are in bijection with a natural

n
∈
ω

{\displaystyle n\in \omega }

. As an axiom this is called

V
=

F
i
n

{\displaystyle V={\mathrm {Fin} }}

and the other axioms are those related to set algebra and order: Union and Binary Intersection, which is tightly related to the Predicative Separation schema, Extensionality, Pairing, and the Set induction schema. This theory is then already identical with the theory given by

C
Z
F

{\displaystyle {\mathsf {CZF}}}

without Strong Infinity and with the finitude axiom added. The discussion of

H
A

{\displaystyle {\mathsf {HA}}}

in this set theory is as in model theory. And in the other direction, the set theoretical axioms are proven with respect to the primitive recursive relation

x
∈
y

⟺

∃
(
r
<

2

x

)
.
∃
(
s
<
y
)
.

(

2

x

(
2
s
+
1
)
+
r
=
y

)

{\displaystyle x\in y\iff \exists (r<2^{x}).\exists (s

That small universe of sets can be understood as the ordered collection of finite binary sequences which encode their mutual membership. For example, the

100

2

{\displaystyle 100_{2}}

'th set contains one other set and the

110101

2

{\displaystyle 110101_{2}}

'th set contains four other sets. See BIT predicate.

= Realizability

=
For some number

n

{\displaystyle \mathrm {n} }

in the metatheory, the numeral in the studied object theory is denoted by

n

_

{\displaystyle {\underline {\mathrm {n} }}}

.
In intuitionistic arithmetics, the disjunction property

D
P

{\displaystyle {\mathrm {DP} }}

is typically valid. And it is a theorem that any c.e. extension of arithmetic for which it holds also has the numerical existence property

N
E
P

{\displaystyle {\mathrm {NEP} }}

:

H
A

⊢
∃
n
.
ψ
(
n
)

⟺

exists

n

H
A

⊢
ψ
(

n

_

)

{\displaystyle {\mathsf {HA}}\vdash \exists n.\psi (n)\iff {\text{ exists }}{\mathrm {n} }{\text{ }}{\mathsf {HA}}\vdash \psi ({\underline {\mathrm {n} }})}

So these properties are metalogical equivalent in Heyting arithmetic. The existence and disjunction property in fact still holds when relativizing the existence claim by a Harrop formula

α

{\displaystyle \alpha }

, i.e. for provable

α
→
∃
n
.
ψ
(
n
)

{\displaystyle \alpha \to \exists n.\psi (n)}

.
Kleene, a student of Church, introduced important realizability models of the Heyting arithmetic.
In turn, his student Nels David Nelson established (in an extension of

H
A

{\displaystyle {\mathsf {HA}}}

) that all closed theorems of

H
A

{\displaystyle {\mathsf {HA}}}

(meaning all variables are bound) can be realized. Inference in Heyting arithmetic preserves realizability. Moreover, if

H
A

⊢
∀
n
.
∃
m
.
φ
(
n
,
m
)

{\displaystyle {\mathsf {HA}}\vdash \forall n.\exists m.\varphi (n,m)}

then there is a partial recursive function realizing

φ

{\displaystyle \varphi }

in the sense that whenever the function evaluated at

n

{\displaystyle {\mathrm {n} }}

terminates with

m

{\displaystyle {\mathrm {m} }}

, then

H
A

⊢
φ
(

n

_

,

m

_

)

{\displaystyle {\mathsf {HA}}\vdash \varphi ({\underline {\mathrm {n} }},{\underline {\mathrm {m} }})}

. This can be extended to any finite number of function arguments

n

{\displaystyle {\mathrm {n} }}

.
There are also classical theorems that are not

H
A

{\displaystyle {\mathsf {HA}}}

-provable but do have a realization.
Typed versions of realizability have been introduced by Georg Kreisel. With it he demonstrated the independence of the classically valid Markov's principle for intuitionistic theories.
See also BHK interpretation and Dialectica interpretation.
In the effective topos, already the finitely axiomizable subsystem of Heyting arithmetic with induction restricted to

Σ

1

{\displaystyle \Sigma _{1}}

is categorical. Categoricity here is reminiscent of Tennenbaum's theorem. The model validates

H
A

{\displaystyle {\mathsf {HA}}}

but not

P
A

{\displaystyle {\mathsf {PA}}}

and so completeness fails in this context.

= Type theory

=
Type theoretical realizations mirroring inference rules based logic formalizations have been implemented in various languages.

Extensions

Heyting arithmetic has been discussed with potential function symbols added for primitive recursive functions. That theory proves the Ackermann function total.
Beyond this, axiom and formalism selection always has been a debate even within the constructivist circle. Many typed extensions of

H
A

{\displaystyle {\mathsf {HA}}}

have been extensively studied in proof theory, e.g. with types of functions between numbers, and function between those, etc. The formalities naturally become more complicated, with different possible axioms governing the application of functions. The class of functions being total can be enriched this way. The theory with finite types

H
A

ω

{\displaystyle {\mathsf {HA}}^{\omega }}

when further combined with function extensionality plus an axiom of choice in

N

N

{\displaystyle {\mathbb {N} }^{\mathbb {N} }}

still proves the same arithmetic formulas as just

H
A

{\displaystyle {\mathsf {HA}}}

and has a type theoretic interpretation. However, that theory rejects Church’s thesis for

N

N

{\displaystyle {\mathbb {N} }^{\mathbb {N} }}

as well as that all functions in

N

N

→

N

{\displaystyle {\mathbb {N} }^{\mathbb {N} }\to {\mathbb {N} }}

would be continuous. But adopting, say, different extensionality rules, choice axioms, Markov's and independence principles and even the Kőnig's lemma—all together but each at specific strength or levels—one can define rather "stuffed" arithmetics that may still fail to prove excluded middle at the level of

Π

1

0

{\displaystyle \Pi _{1}^{0}}

-formulas.
Early on, also variants with intensional equality and Brouwerian choice sequence have been investigated.
Reverse mathematics studies of constructive second-order arithmetic have been performed.

History

Formal axiomatization of the theory trace back to Heyting (1930), Herbrand and Kleene.
Gödel proved the consistency result concerning

P
A

{\displaystyle {\mathsf {PA}}}

in 1933.

Related concepts

Heyting arithmetic should not be confused with Heyting algebras, which are the intuitionistic analogue of Boolean algebras.

References

Ulrich Kohlenbach (2008), Applied proof theory, Springer.
Anne S. Troelstra, ed. (1973), Metamathematical investigation of intuitionistic arithmetic and analysis, Springer, 1973.

External links

Stanford Encyclopedia of Philosophy: "Intuitionistic Number Theory" by Joan Moschovakis.
Fragments of Heyting Arithmetic by Wolfgang Burr

Axiomatization

Theorems

= Double negations

= Excluded middle

= Conservativity

Unprovable statements

= Classically independent propositions

= Unprovable classical principles

= Anti-classical extensions

Models

= Consistency

= Set theory

= Realizability

= Type theory

Extensions

History

Related concepts

See also

References

External links

Kata Kunci Pencarian:

Recent Movies

Recent Movies

Categories

Recent Movies