2019-02-04

I re-read the proof of existence of a computable infinite binary tree without any computable paths, in Stillwell’s Reverse Mathematics. I was able to follow the proof. If you remember, I was having trouble with this proof a while back. One of the errors I had made earlier is to assume that the tree nodes were integers, rather than finite binary sequences. Stillwell actually clarifies this in like the first sentence of the proof, but I still had the misconception! I must have been tired… A picture would have helped, and Stillwell does include one, but in an earlier section (that he references).

I did some searching on \Delta_0 = \Sigma_0 = \Pi_0 sets/relations versus \Delta_1 = \Sigma_1\cap \Pi_1 sets/relations. They seem to be equivalent under some definitions, but I wasn’t able to figure out when they are vs when they aren’t.

Started on the function versus algorithm page.

Advertisements