Math connections, Divisions, Automata, Yates index set theorem, Adjunction
Understand how the arithmetical hierarchy relates to the foursome and sevensome.
- Study the classification of sets in the jump hierarchy as in Soare's book.
Readings
Ideas
The ways of figuring things out in mathematics include four patterns from analysis which exhibit stages in the arithmetical hierarchy:
- {$\Pi_1$} Induction {$\forall x P(x)$}
- {$\Sigma_2$} Maximum or minimum {$\forall x \exists y (P(x)\Rightarrow P(y))$}
- {$\Pi_3$} Least upper bound or greatest lower bound {$\forall x \exists y \forall z ((x \leq y) \wedge (x \leq z \Rightarrow y \leq z))$}
- {$\Sigma_4$} Limit {$\forall \delta \exists \epsilon \forall x \exists x_0 (|x-x_0|<\delta \Rightarrow |F(x)-F(x_0)|<\epsilon )$}
In general, a logical form has three parts:
- Given...
- Quantifiers...
- Statement...
Notes
- Consider what delta-epsilon statements mean in terms of the arithmetical hierarchy. There exists and x_0 such that for every epsilon there exists a delta such that for every x... It starts out most fixed (x_0) and ends most free (x).
- How do notions of variables (fixed, varying) relate to the arithmetical hierarchy?
- {$\exists ! P(x) = \exists x \forall y (P(y)\leftrightarrow y=x)$}
- {$\forall x \exists y$} defines a function {$f(x)=y$}.
- Nested quantifiers, arithmetic hierarchy. God's perspective {$\forall$}, human's perspective {$\exists$}.