nLab
principle of omniscience

Principles of omniscience

Idea

In logic and foundations, a principle of omniscience is any principle of classical mathematics that is not valid in constructive mathematics. The idea behind the name (which is due to Bishop (1967)) is that, if we attempt to extend the computational interpretation of constructive mathematics to incorporate one of these principles, we would have to know something that we cannot compute. The main example is the law of excluded middle (EMEM); to apply p¬pp \vee \neg{p} computationally, we must know which of these disjuncts hold; to apply this in all situations, we would have to know everything (hence ‘omniscience’).

Bishop's principles of omniscience (stated below) may be seen as principles that extend classical logic from predicates (where EMEM may happen to be valid, even constructively, for certain predicates) to their quantifications over infinite domains (where EMEM is typically not constructively valid).

The limited principle of omniscience

The limited principle of omniscience (LPOLPO) states that the existential quantification of any decidable proposition is again decidable. That is,

(x,P(x)¬P(x))(x,P(x))¬(x,P(x)), (\forall x, P(x) \vee \neg{P(x)}) \Rightarrow (\exists x, P(x)) \vee \neg(\exists x, P(x)) ,

or equivalently

(x,P(x)¬P(x))(x,P(x))(x,¬P(x)). (\forall x, P(x) \vee \neg{P(x)}) \Rightarrow (\exists x, P(x)) \vee (\forall x, \neg{P(x)}) .

We have not stated the domain of quantification of the variable xx. If you take it to be the subsingleton corresponding to a given truth value and apply this principle to the constantly true proposition, then EMEM follows; conversely, EMEM implies LPOLPO (over any domain). However, Bishop's LPOLPO takes the domain to be the set of natural numbers, giving a weaker principle than EMEM. (It appears that a realizability topos based on infinite-time Turing machine?s validates LPOLPO but not EMEM; see Bauer (2011).)

We can also state the principle set-theoretically, with explicit reference to the domain of quantification. Given a set AA, the limited principle of omniscience for AA (LPO ALPO_A) states that, given any function ff from AA to the boolean domain {0,1}\{0,1\}, either ff is the constant map to 00 or 11 belongs to the image of ff. Then Bishop's LPOLPO is LPO LPO_{\mathbb{N}}, which applies to any infinite sequence of bits.

While LPOLPO for \mathbb{N} is a classic example of the difference between constructive and classical mathematics, LPOLPO holds for the set ¯\overline{\mathbb{N}} of extended natural numbers; this is related to the fact that ¯\overline{\mathbb{N}} may constructively be given a compact topology. See Escardó (2011) for this and much more.

The lesser limited principle of omniscience

The lesser limited principle of omniscience (LLPOLLPO) states that, if the existential quantification of the conjunction of two decidable propositions is false, then one of their separate existential quantifications is false. That is,

(x,P(x)¬P(x))(y,Q(y)¬Q(y))¬(x,P(x)y,Q(y))¬(x,P(x))¬(y,Q(y)), (\forall x, P(x) \vee \neg{P(x)}) \Rightarrow (\forall y, Q(y) \vee \neg{Q(y)}) \Rightarrow \neg(\exists x, P(x) \wedge \exists y, Q(y)) \Rightarrow \neg(\exists x, P(x)) \vee \neg(\exists y, Q(y)) ,

or equivalently

(x,P(x)¬P(x))(y,Q(y)¬Q(y))¬(x,P(x)y,Q(y))(x,¬P(x))(y,¬Q(y)). (\forall x, P(x) \vee \neg{P(x)}) \Rightarrow (\forall y, Q(y) \vee \neg{Q(y)}) \Rightarrow \neg(\exists x, P(x) \wedge \exists y, Q(y)) \Rightarrow (\forall x, \neg{P(x)}) \vee (\forall y, \neg{Q(y)}) .

If, as before, you take the domains of quantification to be subsingletons, you get de Morgan's law ¬(pq)¬p¬q\neg(p \wedge q) \Rightarrow \neg{p} \vee \neg{q} (DMDM), which is weaker than EMEM; conversely, DMDM implies LLPOLLPO (over any domain). Again, Bishop's LLPOLLPO takes the domain to be \mathbb{N}, giving a principle weaker than DMDM (and also weaker than LPO LPO_{\mathbb{N}}).

Stated set-theoretically, the lesser limited principle of omniscience for AA (LLPO ALLPO_A) states that, given functions f,g:A{0,1}f, g\colon A \to \{0,1\}, if 1imfimg1 \notin \im f \cap \im g, then 1imf1 \notin \im f or 1img1 \notin \im g. So Bishop's LLPOLLPO is LLPO LLPO_{\mathbb{N}}. Note that LLPO ALLPO_A follows from LPO ALPO_A, but not conversely.

Analytic versions

Bishop introduced the above principles of omniscience to show that certain results in pointwise analysis could not be constructive, by showing that these results implied a principle of omniscience. The principles of omniscience that appear directly in analysis are these:

  • The analytic LPO states that the set \mathbb{R} of real numbers has decidable equality (x=yx = y or xyx \neq y).
  • The analytic LLPO states that the usual order on \mathbb{R} is a total order (xyx \leq y or xyx \geq y).

The analytic (L)LPO implies the (L)LPO for natural numbers; the converses hold if we assume weak countable choice (as Bishop did). In any case, if we use the Cauchy real numbers (sequential real numbers), then the sequential analytic (L)LPO is the same as the (L)LPO for natural numbers.

(Note that we need not accept WCCWCC to see that an analytic result implies the (L)LPO and so cannot be constructively valid.)

There are various other results that are equivalent to or related to the principles of omniscience, which it might be handy to collect here. For the connection to writing real numbers as decimals (or in some other radix), see Daniel Mehkeri's answer to Feldman (2010).

Models

  • The LPO (for natural numbers) holds in any presheaf topos, and indeed in any locally connected topos (over a classical base SetSet), essentially since then 2 N2^N is a constant object.

  • The LPO for natural numbers fails in the topological topos, due to its internal continuity principle.

References

Revised on August 28, 2014 07:18:50 by Urs Schreiber (145.15.244.119)