Title: Ramsey's Theorem does not Hold in Recursive Set Theory
Abstract: This chapter discusses Ramsey's theorem that does not hold in recursive set theory. The theorem is described, which states that there exists a recursive binary symmetric relation (R) on natural numbers (N) such that no recursively enumerable infinit subset of N is R-homogeneous. The proof of the theorem is based on the existence of two recursively enumerable sets of incomparable degrees of insolvability. The proofs of Ramsey's theorem show that there exist arithmetical R-homogeneous sets for recursive relations R. The existence of an infinite recursively enumerable R-homogeneous set implies that either S1 is recursive in S2 or S2 is recursive in S1. There exist recursively enumerable sets of incomparable degrees.
Publication Year: 1971
Publication Date: 1971-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 44
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot