Samiksha Jaiswal (Editor)

Systems of Logic Based on Ordinals

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.

The thesis is an exploration of formal mathematical systems after Gödel's theorem. Gödel showed for that any formal system S powerful enough to represent arithmetic, there is a theorem G which is true but the system is unable to prove. G could be added as an additional axiom to the system in place of a proof. However this would create a new system S' with its own unprovable true theorem G', and so on. Turing's thesis considers iterating the process to infinity, creating a system with an infinite set of axioms.

The thesis was completed at Princeton under Alonzo Church and was a classic work in mathematics which introduced the concept of ordinal logic.

Martin Davis states that although Turing's use of a computing oracle is not a major focus of the dissertation, it has proven to be highly influential in theoretical computer science, e.g. in the polynomial time hierarchy.

References

Systems of Logic Based on Ordinals Wikipedia