Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

Math connections, Divisions, Automata, Yates index set theorem, Adjunction

Readings

• Wikipedia: Arithmetical hierarchy
• Wikipedia: Turing degree
• Wikipedia: Turing jump

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$}.