January 16, 2007
We defined languages and structures in the model theoretic sense, and the notion of an embedding between structures of the same language.
We proved that the theory of the degrees is decidable by means of forcing:
- First we reduced the argument to showing that any finite partial order can be embedded in .
- Then we argued that for this it is enough to show that there is an infinite independent family of degrees, where independence means that no element of the family is reducible to the join of finitely many of the other members of the family.
- Finally, we built such a family using forcing.
January 11, 2007
We presented a general framework for forcing arguments, and gave the proof of the existence of incomparable degrees in the language of forcing.
We defined the hierarchy of formulas and defined theories, the theory of a structure, and what it means for a theory to be decidable.
We want to show that the theory of is decidable. For this, we will use the technique of forcing to show that there is an infinite set of independent degrees.
- Degree structures: local and global investigations, by R. Shore. Bulletin of Symbolic Logic 12 (3) (2006), 369-389.
January 4, 2007
There are several equivalent characterizations of the notion of being recursive in a function , namely:
- Belonging to the closure of under recursive functions and recursive operations.
- Being computable using a Turing machine with oracle .
The key tool to use this notion is the enumeration theorem.
This material should just be a generalization of notions and results studied in 117a. The following references may be useful for this part of the course:
- Mathematical Logic, part II, by R. Cori and D. Lascar. OUP (2001), 0 -19-850050-5
- Computability: An introduction to recursive function theory, by N. Cutland. Cambridge Univerity Press (1980), 0-521-294657
- Theory of recursive functions and effective computability, by H. Rogers. MIT press (1987), 0-262-68052-1
- Computability theory, by B. Cooper. CRC Press (2003), 1-58488-237-9
- Degrees of unsolvability: Local and global theory, by M. Lerman. Springer (1983), 0-387-12155-2