SOME RAMSEY THEORY IN BOOLEAN ALGEBRA FOR COMPLEXITY CLASSES

✍ Scribed by Gregory L. McColm

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 367 KB
• Volume: 38
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19920380125

✦ Synopsis

Abstract

It is known that for two given countable sets of unary relations A and B on ω there exists an infinite set H ⫅ ω on which A and B are the same. This result can be used to generate counterexamples in expressibility theory. We examine the sharpness of this result.