Yoneda lemma, Arithmetical hierarchy, Automata
Understand Yates index set theorem as a statement about the foursome, and relate it to the Yoneda lemma.
Study
- Find good video courses about computability.
- Write down all the examples of sets in the arithmetic hierarchy as prenex statements.
- Intuit from these examples how they express the power of their level.
- Study from Soare Chapter IV how to demonstrate that they are not less than that level.
- Think about the general form of the matrix of a prenex statement (which is quantifiers plus a matrix).
- Understand Sutner's remark that existence can be thought of as geometric projection. How does that relate to perspectives?
- Study Soare Chapter XII.
Questions
- In this context, what is a perspective?
- Consider whether there is a connection between the automata hierarchy and Bott periodicity.
- Relate the quantifiers in the sevensome/eightsome with the arithmetical hierarchy and the foursome, how four levels yield the three-cycle upon identifying the first and the last levels, the null level with consciousness of the null level.
- Express nondeterminism and determinism in terms of universal and existential quantifiers, respectively.
- Yates Index Set Theorem - consider substitution.
Arithmetical hierarchy
- The Arithmetical Hierarchy intersperse existential and universal quantifiers in the same way as the chain of perspectives intersperses human (existential) and God's (universal) perspectives.
- The application of the pumping lemma (Hopcroft & Ullman, p.57) is expressed as a dialogue with an adversary where the adversary chooses the existential quantifiers and we choose the universal quantifiers. Thus this is an example of a division of perspectives and the use of persons such as You and I.
{$(\forall L)(\exists n)(\forall z)[z \textrm{ in } L \textrm{ and } |z| \geq n \textrm{ implies that }(\exists u, v, w)(z = uvw, |uv| \leq n, |v| \geq 1 \textrm{ and } (\forall i)(uv^iw \textrm{ is in } L))]$}
Readings
Arithmetical Hierarchy
Yates Index Set Theorem
Chomsky hierarchy
Computability
C.E.M. Yates