A partial analysis of modified realizability

Extract

A formalized version of Kleene realizability for intuitionistic first-order arithmetic HA was axiomatically characterized by Troelstra (see [2, 3.2]) as follows: for an arbitrary HA-sentence φ, HA ⊢ ∃x(x realizes φ) if and only if HA + ECT₀ ⊢ φ.

Many notions of realizability have been characterized in this fashion: see [2] or [3] for details. For some notions, for example extensional realizability, it is necessary to pass to an extension of HA: realizability in HA is characterized by deducibility from certain axioms in an extension of HA.

The present note is concerned with modified realizability, seen as interpretation for HA. From semantical considerations (see [4]) it follows that this interpretation can be constructed as a combination of three ingredients:

i) Kleene realizability;

ii) Kripke forcing over a 2-element linear order P;

iii) The Friedman translation [1].

This will be shown in section 2. The Friedman translation (in the way we use it) introduces a new propositional constant V; hence we move to an extension HA(V) of HA. We must then define Kleene realizability and forcing for the extended language. Now let (φ)v be the result of the Friedman translation applied to φ. We obtain, in HA, that the sentence saying that φ is modified-realizable, is equivalent to the sentence which says that the statement “(φ)v is Kleene-realizable” is forced in P (see section 2).