We prove two of the inequalities needed to obtain the following result on the ordinal values of ptykes of type 2, which are definable in Gödel'sT. LetG be a dilator satisfyingG(0)=ω, ∀x:G(x)≧x, and ∀η<Ω:G(η)<Ω, and letg be the ordinal function induced byG. Then sup{A(G)∣A ptyx of type 2 definable in Gödel'sT} = sup{x∣x is∑ 1 g -definable without parameters provably in KP(G)} =J (2 +Id) g (ω) (0) = the “Bachmann-Howard ordinal relative tog”. KP(G) is obtained from Kripke-Platek set theory (...) without urelements KP by adjoining a two-place relation symbolG and axioms expressing thatG is the graph of a total function from ordinals to ordinals.J D g is an iteration hierarchy defined relative tog by primitive recursion on dilators. (2 +Id)(ω) is the dilator $$\mathop {\sup }\limits_{n< \omega } (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n)} $$ with (2 +Id)(0)≔1 and $$(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n + 1)} : = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)^{(2 + Id)_{(n)} } $$ . The “Bachmann-Howard ordinal relative tog” is the closure ordinal of a Bachmann hierarchy of lengthε Ω + 1, which is built on an iteration ofg as initial function.For the caseG=(1+Id)·ω, KP(G) is equivalent to Jäger's theory KPu, and the “Bachmann-Howard ordinal relative tog” is the usual “Bachmann-Howard ordinal”. For the caseG=Ξ1 KP(G) can be replaced by Jäger's theory KPi, andg can be replaced by the functionλx. x +.x + is the successor admissible ofx, andΞ 1 is the sum of all recursive dilators in an arbitrary enumeration. (shrink)

A hierarchy (J D g ) D Dilator of ordinal functionsJ D g : On→On is introduced and studied. It is a hierarchy of iterations relative to some giveng:OnarOn, defined by primitive recursion on dilators. This hierarchy is related to a Bachmann hierarchy $\left( {\phi _\alpha ^g } \right)_{\alpha< \varepsilon _{\Omega {\mathbf{ }} + {\mathbf{ }}1} }$ , which is built on an iteration ofg ↑ Ω as initial function.This Bachmann hierarchy $\left( {\phi _\alpha ^g } \right)_{\alpha< \varepsilon _{\Omega {\mathbf{ (...) }} + {\mathbf{ }}1} }$ itself is shown to be explicitly definable by $$\phi _\alpha ^g (\eta ) = g^{\Omega ^\alpha \cdot (1 + \eta )} (0)$$ from a hierarchy of iterationsg α :Ω→Ω for weakly monotonicg: Ω→Ω withg(0)>0. Forg=λη. (1+η) ·ω org=λη. 1, in particular, one obtains as $\left( {\phi _\alpha ^g } \right)_{\alpha< \varepsilon _{\Omega {\mathbf{ }} + {\mathbf{ }}1} }$ Bachmann hierarchy.With every ordinalα≦ε Ω+1 a dilatorD α is associated.D α is “below” the dilator $$\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id} \right)_{(\omega )}$$ , which is defined as $$\mathop {\sup }\limits_{n< \omega } (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n)}$$ with (¯2+Id)(0):=1 and $$(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n + 1)} : = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)^{(2 + Id)_{(n)} }$$ . For weakly monotonicg:OnarOn satisfyingg(0)>0 and $g(\Omega ) \subseteqq \Omega$ , and forη<Ω andα<ε Ω+1 it is proved that. (shrink)

Nondeterministic programs occurring in recently developed programming languages define nondeterminate partial functions. Formulas (Boolean expressions) of such nondeterministic languages are interpreted by a nonempty subset of {T (true), F (false), U (undefined)}. As a semantic basis for the propositional part of a corresponding nondeterministic three-valued logic we study the notion of a truth-function over {T, F, U} which is computable by a nondeterministic evaluation procedure. The main result is that these truth-functions are precisely the functions satisfying four basic properties, called (...) -isotonic, –-isotonic, hereditarily guarded, and hereditarily guard-using, and that a function satisfies these properties iff it is explicitly definable (in a certain normal form) from if..then..else..fi, binary choice, and constants. (shrink)