Mass problems and intuitionism

Stephen G. Simpson¹

Department of Mathematics

First draft: July 25, 2007
This draft: April 28, 2008

Notre Dame Journal of Formal Logic, 49, 2008, 127-136

Pennsylvania State University

Abstract:

Let $\mathcal{P}_w$ be the lattice of Muchnik degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$. The lattice $\mathcal{P}_w$ has been studied extensively in previous publications. In this note we prove that the lattice $\mathcal{P}_w$ is not Brouwerian.

Introduction

Definition 1   Let $\omega$ denote the set of natural numbers, $\omega=\{0,1,2,\ldots\}$. Let $\omega^\omega$ denote the Baire space, $\omega^\omega=\{f\mid f:\omega\to\omega\}$. Following Medvedev [27] and Rogers [32, §13.7] we define a mass problem to be an arbitrary subset of $\omega^\omega$. For mass problems $P$ and $Q$ we say that $P$ is Medvedev reducible or strongly reducible to $Q$, abbreviated $P\le_sQ$, if there exists a partial recursive functional $\Psi$ such that $\Psi(g)\in P$ for all $g\in Q$. We say that $P$ is Muchnik reducible or weakly reducible to $Q$, abbreviated $P\le_wQ$, if for all $g\in Q$ there exists $f\in P$ such that $f$ is Turing reducible to $g$. Clearly Medvedev reducibility implies Muchnik reducibility, but the converse does not hold.

Definition 2   A Medvedev degree or degree of difficulty or strong degree is an equivalence class of mass problems under mutual Medvedev reducibility. A Muchnik degree or weak degree is an equivalence class of mass problems under mutual Muchnik reducibility. We write $\deg_s(P)=$ the Medvedev degree of $P$. We write $\deg_w(P)=$ the Muchnik degree of $P$. Let $\mathcal{D}_s$ be the set of Medvedev degrees, partially ordered by Medvedev reducibility. There is a natural embedding of the Turing degrees into $\mathcal{D}_s$ given by $\deg_T(f)\mapsto\deg_s(\{f\})$. Let $\mathcal{D}_w$ be the set of Muchnik degrees, partially ordered by Muchnik reducibility. There is a natural embedding of the Turing degrees into $\mathcal{D}_w$ given by $\deg_T(f)\mapsto\deg_w(\{f\})$. Here $\{f\}$ is the singleton set whose only element is $f$.

Definition 3   Let $L$ be a lattice. For $a,b\in L$ we define $a\Rightarrow b$ to be the unique minimum $x\in L$ such that $\sup(a,x)\ge b$. Note that $a\Rightarrow b$ may or may not exist in $L$. Following Birkhoff [8,9] (first two editions) and McKinsey/Tarski [25] we say that $L$ is Brouwerian if $a\Rightarrow b$ exists in $L$ for all $a,b\in L$ and $L$ has a top element. It is known (see Birkhoff [9, §IX.12] [10, §II.11] or McKinsey/Tarski [25] or Rasiowa/Sikorski [31, §I.12]) that if $L$ is Brouwerian then $L$ is distributive and has a bottom element and for all $a\le b$ in $L$ the sublattice

$$\{x\in L\mid a\le x\le b\}$$

is again Brouwerian.

Remark 1   Given a Brouwerian lattice $L$, we may view $L$ as a model of first-order intuitionistic propositional calculus. Namely, for $a,b\in L$ we define $a\land b=\sup(a,b)$, $a\lor b=\inf(a,b)$, $a\Rightarrow b$ as above, and $\lnot a=(a\Rightarrow 1)$ where $1$ is the top element of $L$. We may also define $a\vdash b$ if and only if $a\ge b$ in $L$. There is a completeness theorem (see Tarski [52] or McKinsey/Tarski [24,25,26] or Rasiowa/Sikorski [31, §IX.3] or Rasiowa [30, § XI.8]) saying that a first-order propositional formula is intuitionistically provable if and only if it evaluates identically to the bottom element in all Brouwerian lattices.

Remark 2   Brouwerian lattices have also been studied under other names and with other notation and terminology. A pseudo-Boolean algebra is a lattice $L$ such that the dual of $L$ is Brouwerian; see Rasiowa/Sikorski [31] and Rasiowa [30]. Pseudo-Boolean algebras are also known as Heyting algebras; see Balbes/Dwinger [2, Chapter IX], Fourman/Scott [18], and Grätzer [19]. Brouwerian lattices are also known as Brouwer algebras; see Sorbi [48,49], Sorbi/Terwijn [51], and Terwijn [53,54,55,56,57]. Remarkably, the so-called Brouwerian lattices of Birkhoff [10] (third edition) are dual to those of Birkhoff [8,9] (first two editions). We adhere to the terminology of Birkhoff [8,9].

Remark 3   It is known that $\mathcal{D}_s$ and $\mathcal{D}_w$ are Brouwerian lattices. There is a natural homomorphism of $\mathcal{D}_s$ onto $\mathcal{D}_w$ given by $\deg_s(P)\mapsto\deg_w(P)$. This homomorphism preserves the binary lattice operations $\sup$ and $\inf$ and the top and bottom elements, but it does not preserve the binary if-then operation $\Rightarrow$.

Remark 4   The relationship between mass problems and intuitionism has a considerable history. Indeed, it seems fair to say that the entire subject of mass problems originated from intuitionistic considerations. The impetus came from Kolmogorov 1932 [22,23] who informally proposed to view Heyting's intuitionistic propositional calculus [20] as a ``calculus of problems'' (``Aufgabenrechnung''). This idea amounts to what is now known as the BHK or Brouwer/Heyting/Kolmogorov interpretation of the intuitionistic propositional connectives; see Troelstra/van Dalen [59, §§1.3.1 and 1.5.3]. Elaborating Kolmogorov's idea, Medvedev 1955 [27] introduced $\mathcal{D}_s$ and noted that $\mathcal{D}_s$ is a Brouwerian lattice. Later Muchnik 1963 [28] introduced $\mathcal{D}_w$ and noted that $\mathcal{D}_w$ is a Brouwerian lattice. Some further papers in this line are Skvortsova [47], Sorbi [48,49,50], Sorbi/Terwijn [51], and Terwijn [54,53,55,56,57].

Definition 4   Let $2^\omega$ denote the Cantor space, $2^\omega=\{f\mid f:\omega\to\{0,1\}\}$. Following Simpson [40] let $\mathcal{P}_s$ be the sublattice of $\mathcal{D}_s$ consisting of the Medvedev degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$, and let $\mathcal{P}_w$ be the sublattice of $\mathcal{D}_w$ consisting of the Muchnik degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$.

Remark 5   The lattices $\mathcal{P}_s$ and $\mathcal{P}_w$ are mathematically rich and have been studied extensively. See Alfeld [1], Binns [3,4,5,6], Binns/Simpson [7], Cenzer/Hinman [11], Cole/Simpson [13], Kjos-Hanssen/Simpson [21], Simpson [34,35,37,38,39,40,41,42,43,45,44], Simpson/Slaman [46], and Terwijn [54]. It is known that $\mathcal{P}_w$ contains not only the recursively enumerable Turing degrees [42] but also many specific, natural Muchnik degrees which arise from foundationally interesting topics. Among these foundationally interesting topics are algorithmic randomness [40,42], reverse mathematics [36,40,41,43], almost everywhere domination [43], hyperarithmeticity [13], diagonal nonrecursiveness [40,42], subrecursive hierarchies [21,40], resource-bounded computational complexity [21,40], and Kolmogorov complexity [21]. Recently Simpson [44] has applied $\mathcal{P}_s$ and $\mathcal{P}_w$ to prove a new theorem in symbolic dynamics.

Remark 6   It is known that $\mathcal{P}_s$ and $\mathcal{P}_w$ are distributive lattices with top and bottom elements. Moreover, the natural lattice homomorphism of $\mathcal{D}_s$ onto $\mathcal{D}_w$ restricts to a natural lattice homomorphism of $\mathcal{P}_s$ onto $\mathcal{P}_w$ preserving top and bottom elements.

Remark 7   In view of Remarks 3, 4, 5 and 6, it is natural to ask whether $\mathcal{P}_s$ and $\mathcal{P}_w$ are Brouwerian lattices. The purpose of this note is to show that $\mathcal{P}_w$ is not a Brouwerian lattice. Letting $\mathbf{1}$ denote the top element of $\mathcal{P}_w$, we shall produce a family of Muchnik degrees $\mathbf{p}\in\mathcal{P}_w$ such that $\mathbf{p}\Rightarrow \mathbf{1}$ does not exist in $\mathcal{P}_w$. In other words, $\lnot\mathbf{p}$ does not exist in $\mathcal{P}_w$.

Remark 8   It remains open whether $\mathcal{P}_s$ is a Brouwerian lattice. Terwijn [54] has shown that the dual of $\mathcal{P}_s$ is not a Brouwerian lattice. It remains open whether the dual of $\mathcal{P}_w$ is a Brouwerian lattice.

Proof that $\mathcal{P}_w$ is not Brouwerian

In this section we prove that the lattice $\mathcal{P}_w$ is not Brouwerian.

Definition 5   For $f,g\in\omega^\omega$ we write $f\le_Tg$ to mean that $f$ is Turing reducible to $g$, i.e., $f$ is computable relative to the Turing oracle $g$. We write $g'=$ the Turing jump of $g$. In particular $0'=$ the halting problem $=$ the Turing jump of $0$. We use standard recursion-theoretic notation from Rogers [32]. We say that $f$ is majorized by $g$ if $f(n)<g(n)$ for all $n$.

We begin with four well known lemmas.

Lemma 1   Given $f\le_T0'$ we can find $g\equiv_Tf$ such that $\{g\}$ is $\Pi^0_1$.

Proof.Since $f\le_T0'$, it follows by Post's Theorem (see for instance [32, §14.5, Theorem VIII]) that $f$ is $\Delta^0_2$. From this it follows that the singleton set $\{f\}$ is $\Pi^0_2$. Let $R\subseteq\omega^\omega\times\omega\times\omega$ be a recursive predicate such that our $f$ is the unique $f\in\omega^\omega$ such that $\forall m \exists n R(f,m,n)$ holds. Let $g=f\oplus h$ where $h\in\omega^\omega$ is defined by $h(m)=$ the least $n$ such that $R(f,m,n)$ holds. It is easy to verify that $g\equiv_Tf$ and $\{g\}$ is $\Pi^0_1$.$\Box$

Lemma 2   If $\{f\}$ is $\Pi^0_1$ and $f$ is nonrecursive, then $f$ is not majorized by any recursive function.

Proof.This lemma is equivalent to, for instance, [40, Theorem 4.15].$\Box$

Lemma 3   For all nonempty $\Pi^0_1$ sets $Q\subseteq2^\omega$ we have $Q\le_w\{0'\}$.

Proof.This lemma is a restatement of the well known Kleene Basis Theorem. Namely, every nonempty $\Pi^0_1$ subset of $2^\omega$ contains an element which is $\le_T0'$. See for instance the proof of [42, Lemma 5.3].$\Box$

Lemma 4   Let $Q\subseteq2^\omega$ be nonempty $\Pi^0_1$ such that no element of $Q$ is recursive. Then we can find $g\in\omega^\omega$ such that $0<_Tg<_T0'$ and $Q\nleq _w\{g\}$.

Proof.By Lemma 3 it suffices to find $g\in\omega^\omega$ such that $0<_Tg\le_T0'$ and $Q\nleq _w\{g\}$. To construct $g$ we may proceed as in the proof of Lemma 5 below. The construction is easier than in Lemma 5, because we can ignore $f$.$\Box$

Lemma 5   Let $Q\subseteq2^\omega$ be nonempty $\Pi^0_1$. Let $f$ be such that $0<_Tf<_T0'$ and $Q\nleq _w\{f\}$. Then we can find $g\in\omega^\omega$ such that $0<_Tg<_T0'$ and $Q\nleq _w\{g\}$ and $f\oplus g\equiv_T0'$.

Proof.We adapt the technique of Posner/Robinson [29].

Let $U\subseteq\omega^{<\omega}$ be a recursive tree such that $Q=\{$paths through $U\}$. By Lemmas 1 and 2 we may safely assume that $f$ is not majorized by any recursive function.

For integers $e\in\omega$ and strings $\sigma\in\omega^{<\omega}$ we write

$$\Phi_e(\sigma)=\langle\varphi_{e,\vert\sigma\vert}^{(1),\sigma}(i)\mid i<j\rangle$$

where $j=$ the least $i$ such that either $\varphi_{e,\vert\sigma\vert}^{(1),\sigma}(i)\uparrow$ or $i\ge\vert\sigma\vert$. Note that the mapping $\Phi_e:\omega^{<\omega}\to\omega^{<\omega}$ is recursive and monotonic, i.e., $\sigma\subseteq\tau$ implies $\Phi_e(\sigma)\subseteq\Phi_e(\tau)$. Moreover, for all $g,h\in\omega^\omega$ we have $g\ge_Th$ if and only if $\exists e (\Phi_e(g)=h)$. Here we are writing

$$\Phi_e(g)=\bigcup_{n=0}^\infty\Phi_e(g\upharpoonright n) .$$

In order to prove Lemma 5, we shall inductively define an increasing sequence of strings $\tau_e\in\omega^{<\omega}$, $e=0,1,2,\ldots$. We shall then let $g=\bigcup_{e=0}^\infty\tau_e$. In presenting the construction, we shall identify strings with their Gödel numbers.

Stage $0$. Let $\tau_0=\langle\rangle=$ the empty string.

Stage $e+1$. Assume that $\tau_e$ has been defined. The definition of $\tau_{e+1}$ will be given in a finite number of substages.

Substage $0$. Let $\sigma_{e,0}=\tau_e$.

Substage $i+1$. Assume that $\sigma_{e,i}$ has been defined. Let $n_{e,i}=$ the least $n$ such that either

$(1)\qquad\exists\sigma<f(n) [ \sigma_{e,i}{{}^\smallfrown}\langle n\rangle\subseteq\sigma$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\sigma)\in U ]$

or

$(2)\qquad\lnot\exists\sigma [ \sigma_{e,i}{{}^\smallfrown}\langle n\rangle\subseteq\sigma$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\sigma)\in U ]$.

Note that $n_{e,i}$ exists, because otherwise $f(n)$ would be majorized by the recursive function $l_{e,i}(n)=$ least $\sigma$ such that $\sigma_{e,i}{{}^\smallfrown}\langle n\rangle\subseteq\sigma$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\sigma)\in U$. If (1) holds with $n=n_{e,i}$ let $\sigma_{e,i+1}=l_{e,i}(n_{e,i})$. If (2) holds with $n=n_{e,i}$ let $\tau_{e+1}=\sigma_{e,i}{{}^\smallfrown}\langle n_{e,i},0'(e)\rangle$. This completes our description of the construction.

We claim that, within each stage $e+1$, (2) holds for some $i$. Otherwise, we would have infinite increasing sequences of strings

$$\sigma_{e,0}\subset\sigma_{e,1}\subset\cdots \subset\sigma_{e,i}\subset\sigma_{e,i+1}\subset\cdots$$

and

$$\Phi_e(\sigma_{e,0})\subset\Phi_e(\sigma_{e,1})\subset\cdot... ...t\Phi_e(\sigma_{e,i})\subset\Phi(\sigma_{e,i+1})\subset\cdots$$

with $\Phi_e(\sigma_{e,i})\in U$ for all $i$. Moreover, these sequences would be recursive relative to $f$, namely $\sigma_{e,i+1}=l_{e,i}(n_{e,i})$ where $n_{e,i}=$ least $n$ such that (1) holds. Thus, letting $h=\bigcup_{i=0}^\infty\Phi_e(\sigma_{e,i})$, we would have $h\in Q$ and $h\le_Tf$. Thus $Q\le_w\{f\}$, a contradiction. This proves our claim.

From the previous claim it follows that $\tau_e$ is defined for all $e=0,1,2,\ldots$. By construction, the sequence $\langle\tau_0,\tau_1,\ldots,\tau_e,\tau_{e+1},\ldots\rangle$, is recursive relative to $0'$. Moreover, $0'$ is recursive relative to $\langle\tau_0,\tau_1,\ldots,\tau_e,\tau_{e+1},\ldots\rangle$, because for all $e$ we have $0'(e)=\tau_{e+1}(\vert\tau_{e+1}\vert-1)$.

Finally let $g=\bigcup_{e=0}^\infty\tau_e$. Clearly $g\le_T0'$.

We claim that the sequence $\langle\tau_0,\tau_1,\ldots,\tau_e,\tau_{e+1},\ldots\rangle$ is $\le_Tf\oplus g$. Namely, given $\tau_e$, we may use $f$ and $g$ as oracles to compute $\tau_{e+1}$ as follows. We begin with $\sigma_{e,0}=\tau_e$. Given $\sigma_{e,i}$ we use the oracle $g$ to compute $n_{e,i}=g(\vert\sigma_{e,i}\vert)$. Then, using the oracle $f$, we ask whether there exists $\sigma<f(n_{e,i})$ such that $\sigma_{e,i}{{}^\smallfrown}\langle n_{e,i}\rangle\subseteq\sigma$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\sigma)\in U$. If so, we compute $\sigma_{e,i+1}=$ the least such $\sigma$. If not, we use the oracle $g$ to compute $\tau_{e+1}=g\upharpoonright \vert\sigma_{e,i}\vert+2$. This proves our claim.

From the previous claim it follows that $0'\le_Tf\oplus g$. Hence $0'\equiv_Tf\oplus g$.

We claim that $Q\nleq _w\{g\}$. To see this, let $e$ be such that $\Phi_e(g)=\bigcup_{e=0}^\infty\Phi_e(\tau_e)$ is a total function. Consider what happened at stage $e+1$ of the construction. Consider the least $i$ such that (2) holds, i.e., $\tau_{e+1}=\sigma_{e,i}{{}^\smallfrown}\langle n_{e,i},0'(e)\rangle$. Since (2) holds, there does not exist $\sigma$ such that $\sigma_{e,i}{{}^\smallfrown}\langle n_{e,i}\rangle\subseteq\sigma$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\sigma)\in U$. In particular, letting $\tau$ be an initial segment of $g$ such that $\sigma_{e,i}{{}^\smallfrown}\langle n_{e,i}\rangle\subseteq\tau$ and $\Phi_e(\sigma_{e,i})\subset\Phi_e(\tau)$, we have $\Phi_e(\tau)\notin U$. Hence $\Phi_e(g)\notin Q$. This proves our claim.

From the two previous claims, it follows that $0<_Tg<_T0'$. The proof of Lemma 5 is now finished.$\Box$

Remark 9   By a similar argument we can prove the following. Let $S\subseteq\omega^\omega$ be $\Sigma^0_3$. Let $f\in\omega^\omega$ be of hyperimmune Turing degree such that $S\nleq _w\{f\}$. Let $h\in\omega^\omega$ be such that $f\oplus0'\le_Th$. Then we can find $g\in\omega^\omega$ such that $0<_Tg<_Th$ and $S\nleq _w\{g\}$ and $f\oplus g\equiv_Tg'\equiv_Tg\oplus0'\equiv_Th$.

Lemma 6   Let $P\subseteq2^\omega$ be nonempty $\Pi^0_1$. Let $S\subseteq\omega^\omega$ be $\Sigma^0_3$. Then

$$\deg_w(P\cup S)\in\mathcal{P}_w .$$

Proof.This is Simpson's Embedding Lemma. See [42, Lemma 3.3] or [45].$\Box$

We are now ready to prove our main result.

Theorem 1   $\mathcal{P}_w$ is not Brouwerian.

Proof.Let $\mathrm{PA}$ be the set of completions of Peano Arithmetic. Recall from Simpson [40] that $\deg_w(\mathrm{PA})=\mathbf{1}=$ the top element of $\mathcal{P}_w$. By Lemma 4 let $f$ be such that $0<_Tf<_T0'$ and $\mathrm{PA}\nleq _w\{f\}$. Let

$$\mathbf{p}=\deg_w(\mathrm{PA}\cup\{f\})$$

and note that $\mathbf{p}<\mathbf{1}$. By Lemmas 1 and 6 we have $\mathbf{p}\in\mathcal{P}_w$.

It is well known (see for instance [40, Remark 3.9]) that $\mathcal{D}_w$ is a complete lattice. This means that for all $\mathcal{A}\subseteq\mathcal{D}_w$ the least upper bound $\sup(\mathcal{A})$ and the greatest lower bound $\inf(\mathcal{A})$ exist in $\mathcal{D}_w$. Therefore, within $\mathcal{D}_w$, let

$$\mathbf{q}=\inf(\{\mathbf{x}\in\mathcal{P}_w\mid\sup(\mathbf{p},\mathbf{x})=\mathbf{1}\})$$

and note that $\sup(\mathbf{p},\mathbf{q})=\mathbf{1}$ in $\mathcal{D}_w$. In other words, $\mathbf{q}\ge(\mathbf{p}\Rightarrow \mathbf{1})$ in $\mathcal{D}_w$.

We claim that $\mathbf{q}\notin\mathcal{P}_w$. Otherwise, let $\mathbf{q}=\deg_w(Q)$ where $Q\subseteq2^\omega$ is nonempty $\Pi^0_1$. Since $\sup(\mathbf{p},\mathbf{q})=\mathbf{1}$, we have $\mathrm{PA}\le_w\{f\oplus h\}$ for all $h\in Q$. Since $\mathrm{PA}\nleq _w\{f\}$, it follows that $Q\nleq _w\{f\}$. By Lemma 5 let $g$ be such that $0<_Tg<_T0'$ and $Q\nleq _w\{g\}$ and $f\oplus g\equiv_T0'$. Let

$$\mathbf{q}_0=\deg_w(Q\cup\{g\})$$

and note that $\mathbf{q}_0<\mathbf{q}$. By Lemmas 1 and 6 we have $\mathbf{q}_0\in\mathcal{P}_w$. By Lemma 3 we have $\mathrm{PA}\le_w\{0'\}\equiv_w\{f\oplus g\}$, hence $\sup(\mathbf{p},\mathbf{q}_0)=\mathbf{1}$ contradicting the definition of $\mathbf{q}$. This proves our claim.

Because $\mathbf{q}\notin\mathcal{P}_w$ it follows that $\mathbf{p}\Rightarrow \mathbf{1}$ does not exist in $\mathcal{P}_w$. Thus $\mathcal{P}_w$ is not Brouwerian.$\Box$

Remark 10   The same proof shows that for all $\mathbf{q}>\mathbf{0}$ in $\mathcal{P}_w$ we can find $\mathbf{p}<\mathbf{q}$ in $\mathcal{P}_w$ such that $\mathbf{p}\Rightarrow \mathbf{q}$ does not exist in $\mathcal{P}_w$. On the other hand, we know at least a few nontrivial instances where $\mathbf{p}\Rightarrow \mathbf{q}$ exists in $\mathcal{P}_w$. For example, letting $\mathbf{r}$ be the Muchnik degree of the set of 1-random reals, Theorem 8.12 of Simpson [40] tells us that $\mathbf{r}<\mathbf{1}$ in $\mathcal{P}_w$ and $\mathbf{r}\Rightarrow \mathbf{1}$ exists in $\mathcal{P}_w$. In fact, $\mathbf{r}\Rightarrow \mathbf{1}$ in $\mathcal{P}_w$ is equal to $\mathbf{r}\Rightarrow \mathbf{1}$ in $\mathcal{D}_w$, which is equal to $\mathbf{1}$. We do not know any instances of $\mathbf{p},\mathbf{q}\in\mathcal{P}_w$ where $\mathbf{p}\Rightarrow \mathbf{q}$ exists in $\mathcal{P}_w$ and both $\mathbf{p}$ and $\mathbf{p}\Rightarrow \mathbf{q}$ are $<\mathbf{q}$ in $\mathcal{P}_w$.

Bibliography

1

Christopher Alfeld.
Non-branching degrees in the Medvedev lattice of $\Pi^0_1$ classes.
Journal of Symbolic Logic, 72:81-97, 2007.

2

Raymond Balbes and Philip Dwinger.
Distributive Lattices.
University of Missouri Press, 1974.
XIII + 294 pages.

3

Stephen Binns.
The Medvedev and Muchnik Lattices of $\Pi^0_1$ Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.

4

Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327-335, 2003.

5

Stephen Binns.
Small $\Pi^0_1$ classes.
Archive for Mathematical Logic, 45:393-410, 2006.

6

Stephen Binns.
Hyperimmunity in $2^{\mathbb{N}}$.
Notre Dame Journal of Formal Logic, 48:293-316, 2007.

7

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of $\Pi^0_1$ classes.
Archive for Mathematical Logic, 43:399-414, 2004.

8

Garrett Birkhoff.
Lattice Theory.
American Mathematical Society, 1940.
V + 155 pages.

9

Garrett Birkhoff.
Lattice Theory.
Number 25 in Colloquium Publications. American Mathematical Society, revised edition, 1948.
XIII + 283 pages.

10

Garrett Birkhoff.
Lattice Theory.
Number 25 in Colloquium Publications. American Mathematical Society, third edition, 1967.
VI + 418 pages.

11

Douglas Cenzer and Peter G. Hinman.
Density of the Medvedev lattice of $\Pi^0_1$ classes.
Archive for Mathematical Logic, 42:583-600, 2003.

12

C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors.
Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 - August 15, 2005.
Number 15 in Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2008.

13

Joshua A. Cole and Stephen G. Simpson.
Mass problems and hyperarithmeticity.
Journal of Mathematical Logic, 2008.
Preprint, 28 November 2008, 20 pages, accepted for publication 17 April 2008.

14

COMP-THY e-mail list.
http://listserv.nd.edu/archives/comp-thy.html, September 1995 to the present.

15

S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors.
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.
Number 224 in London Mathematical Society Lecture Note Series. Cambridge University Press, 1996.
VII + 347 pages.

16

FOM e-mail list.
http://www.cs.nyu.edu/mailman/listinfo/fom/.
September 1997 to the present.

17

M. P. Fourman, C. J. Mulvey, and D. S. Scott, editors.
Applications of Sheaves, Proceedings, Durham, 1977.
Number 753 in Lecture Notes in Mathematics. Springer-Verlag, 1979.
XIV + 779 pages.

18

Michael P. Fourman and Dana S. Scott.
Sheaves and logic.
In [17], pages 302-401, 1979.

19

George A. Grätzer.
General Lattice Theory.
Birkhäuser Verlag, second edition, 1998.
XIX + 663 pages.

20

Arend Heyting.
Die formalen Regeln des intuitionistischen Aussagenkalküls.
Sitzungsberichte der Preußischen Akademie der Wißenschaften, Physicalisch-mathematische Klasse, pages 42-56, 1930.

21

Bjørn Kjos-Hanssen and Stephen G. Simpson.
Mass problems and Kolmogorov complexity.
4 October 2006.
Preprint, in preparation.

22

A. Kolmogoroff.
Zur Deutung der intuitionistischen Logik.
Mathematische Zeitschrift, 35:58-65, 1932.

23

Andrei N. Kolmogorov.
On the interpretation of intuitionistic logic.
In [58], pages 151-158 and 451-466, 1991.
Translation of [22] with commentary and additional references.

24

J. C. C. McKinsey and Alfred Tarski.
The algebra of topology.
Annals of Mathematics, 45:141-191, 1944.

25

J. C. C. McKinsey and Alfred Tarski.
On closed elements in closure algebras.
Annals of Mathematics, 47:122-162, 1946.

26

J. C. C. McKinsey and Alfred Tarski.
Some theorems about the sentential calculi of Lewis and Heyting.
Journal of Symbolic Logic, 13:1-15, 1948.

27

Yuri T. Medvedev.
Degrees of difficulty of mass problems.
Doklady Akademii Nauk SSSR, n.s., 104:501-504, 1955.
In Russian.

28

Albert A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

29

David B. Posner and Robert W. Robinson.
Degrees joining to $0'$.
Journal of Symbolic Logic, 46:714-722, 1981.

30

Helena Rasiowa.
An Algebraic Approach to Non-Classical Logics.
Number 78 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1974.
XV + 403 pages.

31

Helena Rasiowa and Roman Sikorski.
The Mathematics of Metamathematics.
Number 41 in Polska Akademia Nauk, Monografie Matematyczne. Panstwowe Wydawnictwo Naukowe, 1963.
519 pages.

32

Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
XIX + 482 pages.

33

S. G. Simpson, editor.
Reverse Mathematics 2001.
Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005.
X + 401 pages.

34

Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM e-mail list [16], 13 August 1999.

35

Stephen G. Simpson.
FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes.
FOM e-mail list [16], 16 August 1999.

36

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

37

Stephen G. Simpson.
Medvedev degrees of nonempty Pi$\verb\vert^\vert$0$\verb\vert _\vert$1 subsets of 2$\verb\vert^\vert$omega.
COMP-THY e-mail list [14], 9 June 2000.

38

Stephen G. Simpson.
Mass problems.
24 May 2004.
Preprint, 24 pages, submitted for publication.

39

Stephen G. Simpson.
FOM: natural r.e. degrees.
FOM e-mail list [16], 27 February 2005.

40

Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:1-27, 2005.

41

Stephen G. Simpson.
$\Pi^0_1$ sets and models of $\mathsf{WKL}_0$.
In [33], pages 352-378, 2005.

42

Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society, 75:287-297, 2007.

43

Stephen G. Simpson.
Mass problems and almost everywhere domination.
Mathematical Logic Quarterly, 53:483-492, 2007.

44

Stephen G. Simpson.
Medvedev degrees of 2-dimensional subshifts of finite type.
Ergodic Theory and Dynamical Systems, 2008.
Preprint, 8 pages, 1 May 2007, accepted for publication.

45

Stephen G. Simpson.
Some fundamental issues concerning degrees of unsolvability.
In [12], pages 313-332, 2008.

46

Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of $\Pi^0_1$ subsets of $2^\omega$.
July 2001.
Preprint, 4 pages, in preparation, to appear.

47

Elena Z. Skvortsova.
A faithful interpretation of the intuitionistic propositional calculus by means of an initial segment of the Medvedev lattice.
Sibirskii Matematicheskii Zhurnal, 29:171-178, 1988.
In Russian.

48

Andrea Sorbi.
Some remarks on the algebraic structure of the Medvedev lattice.
Journal of Symbolic Logic, 55:831-853, 1990.

49

Andrea Sorbi.
Embedding Brouwer algebras in the Medvedev lattice.
Notre Dame Journal of Formal Logic, 32:266-275, 1991.

50

Andrea Sorbi.
The Medvedev lattice of degrees of difficulty.
In [15], pages 289-312, 1996.

51

Andrea Sorbi and Sebastiaan A. Terwijn.
Intermediate logics and factors of the Medvedev lattice.
Annals of Pure and Applied Logic, 2008.
Preprint, 22 pages, 20 June 2006, to appear.

52

Alfred Tarski.
Der Aussagenkalkül und die Topologie.
Fundamenta Mathematicae, 31:103-134, 1938.

53

Sebastiaan A. Terwijn.
Constructive logic and the Medvedev lattice.
Notre Dame Journal of Formal Logic, 47:73-82, 2006.

54

Sebastiaan A. Terwijn.
The Medvedev lattice of computably closed sets.
Archive for Mathematical Logic, 45:179-190, 2006.

55

Sebastiaan A. Terwijn.
Constructive Logic and Computational Lattices.
Habilitationsschrift, Universität Wien, 2007.
VI + 110 pages.

56

Sebastiaan A. Terwijn.
Kripke models, distributive lattices, and Medvedev degrees.
Studia Logica, 85:327-340, 2007.

57

Sebastiaan A. Terwijn.
On the structure of the Medvedev lattice.
Journal of Symbolic Logic, 73:543-558, 2008.

58

V. M. Tikhomirov, editor.
Selected Works of A. N. Kolmogorov, Volume I, Mathematics and Mechanics.
Mathematics and its Applications, Soviet Series. Kluwer Academic Publishers, 1991.
XIX + 551 pages.

59

Anne S. Troelstra and Dirk van Dalen.
Constructivism in Mathematics, an Introduction.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1988.
Volume I, XX + 342 + XIV pages.

About this document ...

Mass problems and intuitionism

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 massint

The translation was initiated by Stephen G Simpson on 2008-04-28

Footnotes

... Simpson¹

The author thanks Sebastiaan Terwijn for helpful correspondence. The author's research was partially supported by the United States National Science Foundation, grants DMS-0600823 and DMS-0652637, and by the Cada and Susan Grove Mathematics Enhancement Endowment at the Pennsylvania State University.