The Logic of Choice
The paper deals with the choice construct \((choose\;x: \phi (x))\) (some element \(x\) satisfying \(\phi(x)\)), which is used in the second author's ASM (abstract state machine) programs. Two ways of adding a choice operator to first-order logic are studied. Under a fixed-choice strategy, all choices from the same set give the same result. Under the independent-choice strategy, choices from the same set \(Z\) may differ. When the set \(Z\) is empty, a default element \texttt{default} is returned. This is the approach used in ASM. The fixed-choice operator is Hilbert's epsilon operator \(\varepsilon x (\phi(x))\) [\textit{D. Hilbert} and \textit{P. Bernays}, Grundlagen der Mathematik. II. 2. Aufl., Springer, Berlin (1970; Zbl 0211.00901)], leading to the first-order logic FO+\(\varepsilon\). The independent-choice operator is denoted by \(\delta x (\phi(x))\), and FO+\(\delta\) is the corresponding first-order logic. The paper studies the epsilon operator in \S 3 and \S 4. More space is devoted to the \(\delta\) operator (\S 7 with supporting material in \S 5--\S 6). \S 8--\S 9 deal with variant independent choice operators and extensions. A FO+\(\varepsilon\) structure \((A,F)\) consists of a first-order structure \(A\) and a choice function \(F\). The term \(\varepsilon x \phi(x)\) is interpreted in \((A,F)\) as \(F(\{x\;|\;A \models \phi(x)\})\). A sentence \(\phi\) is \(\varepsilon\)-invariant if \((A,F_1) \models \phi \iff (A,F_2) \models \phi\) for any two choice functions \(F_1\) and \(F_2\). Proposition 3.2 states that a sentence \(\phi\) is equivalent to a first order (\(\varepsilon\)-free) sentence \(\psi\) iff \(\phi\) is \(\varepsilon\)-invariant. The proofrelies on the interpolation theorem, and the definability of a choice function in terms of a standard linear ordering. An example due to \textit{Martin Otto} [J. Symb. Log. 65, No. 4, 1749-1757 (2000; Zbl 0994.03028)] shows that Proposition 3.2 is false for finite structures. It is also proved that finding out whether a formula \(\phi\) is \(\varepsilon\)-invariant (even over infinite structures) is non-effective. It is shown that there exists a formula \(\phi\) of FO+\(\varepsilon\) such that the problem of deciding, given a structure \(A\) for the vocabulary of \(\phi\), whether \(\phi\) is \(\varepsilon\)-invariant over \(A\) is co-NP hard: \(\phi\) is \(\varepsilon\)-invariant on a graph \(G\) iff \(G\) has no Hamiltonian path. \S 4 deals mainly with \(\varepsilon\)-existential formulas, that is, those formulas of the form \((\exists \varepsilon)\phi\), where \(\phi\) is in FO+\(\varepsilon\). \(A \models (\exists \varepsilon)\phi\) iff \((A,F) \models \phi\) for some \(F\). By Theorems 4.1 and 4.5, \(\varepsilon\)-existential formulas are exactly the formulas equivalent to \(\Sigma_1^1\) formulas, of the form \((\exists P_1)\dots(\exists P_n) \phi\). This implies that any \(\varepsilon\)-existential formula is equivalent to another one of the form \((\exists \varepsilon) \psi\), where every \(\varepsilon\) application in \(\psi\) is of the form \(\varepsilon x (x = t_1 \lor \dots \lor x = t_j)\), \(t_i\) \(x\)-free, \(j \leq 2v+5\), and \(v\) is the number of free variables. Formalizing the independent choice strategy for FO+\(\delta\) is quite different from the standard formalization for FO. It is built on top of what the authors call nondeterministic first-order logic (NFO), a three-valued logic with the truth values \(True\), \(False\), and \(Both\). Intuitively, the interpretation of terms and formulas is blown up into a range of values rather than a single value. The function \(Rng^B(\tau)\), evaluated in a non-deterministic structure \(B\), returns this range of values, both for terms and formulas. The truth values are defined as \(True = \{{\mathtt true}\}\), \(False = \{{\mathtt false}\}\), and \(Both = \{{\mathtt true, false}\}\). \(Rng^B(\delta x \phi(x))\) is the set of elements \(x\) such that \(Rng^B(\phi(x))\) is \(Both\) or \(True\). \texttt{default} is also included if \(True \not \in Rng^B(\phi(x))\) for all elements \(x\). Theorem 7.4 states that \(Rng(t)\) is first-order expressible. Hence every term \(t\) is equivalent to one of the form \(\delta x \phi(x)\), where \(\phi(x)\) is first order. If a formula \(\phi\) has truth value \(Both\) on a structure, then there is no first-order formula with range \(Both\) on a structure. Thus not every FO+\(\delta\) formula is first-order expressible. Corollaries 7.6 and 7.7 provide sufficient conditions for a FO+\(\delta\) formula \(\phi\) to have a first-order equivalent over a class of structures \(K\): \(\phi\) has to be \(\delta\)-invariant (never has value \(Both\) on a structure in \(K\)). In FO+\(\delta\), different occurrences of a term \(s\) can evaluate to different values. In some applications, like the \(let\) constraint in ASM, one wants to have only one value for some term \(s\). This property is expressible in FO+\(\delta\). The construct \(if\;\phi\;then\;t_1\;else\;t_2\) is also definable within FO+\(\delta\). FO+\(\delta\) admits ``quantifier elimination in the sense that quantifiers can be replaced with \(\delta\): \(\exists x \phi(x) \iff ((\delta x (x \neq {\mathtt default} \land \phi(x))) \neq {\mathtt default}) \lor \phi({\mathtt default})\). Vector terms \(\delta x_1 \dots x_n\) \(\phi(x_1, \dots , x_n)\) can also be eliminated in FO+\(\delta\). Infinitary extensions are treated in \S 7. \(L^{\omega}_{\infty,\omega} + \delta\) admits infinite conjunctions and disjunctions. FO+DTC+\(\delta\) adds the deterministic transitive closure operator, and FO+IFP+\(\delta\) includes the inflationary fixed point operator. IFP and DTC were described by \textit{H. D. Ebbinghaus} and \textit{J. Flum} [Finite model theory. 2nd ed., Springer, Berlin (1999; Zbl 0932.03032)]. \S 8 and \S 9 deal with some variants of FO+\(\delta\). This includes the logic FO+W, introduced by S. Abiteboul, E. Simon and V. Vianu, where \(W\) is the witness operator: \([W\bar{y}\phi(\bar{x},\bar{y})](\bar{t})\) holds when \(\bar{t}\) is a witness for \(\phi(\bar{x},\bar{t})\).
- Epsilon-logic is more expressive than first-order logic over finite structures
- Fixed-point Logics with Nondeterministic Choice
- Choice construct and Lindström logics
- Intuitionistic ϵ‐ and τ‐calculi
- Decision procedures for elementary sublanguages of set theory VII. Validity in set theory when a choice operator is present
- On the expressiveness of choice quantification
- Interpreting HOL in the calculus of constructions
- Implicit complexity over an arbitrary structure: Quantifier alternations
- A Tailor-Made Test of Intransitive Choice
- De Groot duality and models of choice: angels, demons and nature
- Semantics and proof theory of the epsilon calculus
- Herbrand complexity and the epsilon calculus with equality
- The epsilon calculus and Herbrand complexity
- Hilbert's epsilon as an operator of indefinite committed choice
This page was built for publication: The Logic of Choice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527924)