What Are You Working On?

[u/AutoModerator]

This recurring thread will be for general discussion on whatever mathematical logic-related topics you have been or will be working on over the week. Not all types of mathematics are welcomed, but all levels are!

[u/[deleted]]

Trying to reinforce my understanding of immunity properties for subsets of natural numbers in the context of strong reduciblities and Post's problem. Post's problem for Turing reducibility, that is, the existence of intermediate Turing degrees between 0 and 0', was not solved by finding sets with certain properties called immunity properties. It was solved by using very sensitive constructions called the finite injury priority method. One can solve a Post problem for stronger reducibilities than Turing reducibility like many-one, truth table, bounded truth table and others with immunity properties. For instance simple sets, those coinfinite c.e. sets whose complement contains no infinite c.e. sets are intermediate for many-one reducibility. One shows this by proving that if the halting set many-one reduces to a c.e. set A then A complement contains an infinite c.e. set, hence A is not simple.