Login
You're viewing the discuss.systems public feed.
  • Oct 27, 2026, 9:38 PM
    retooted Jean Abou Samra (new account)

    I hear laments that Mathstodon has more chatter on the death of math than on math these days. So here's a funny math factoid I recently learnt from jasonzeshengchen.github.io/blo . You can prove that there exist incomparable Turing degrees in three lines as follows:

    The Turing reducibility order between oracles is arithmetic, hence Borel, hence has the Baire property. As each oracle has countably many predecessors, this relation is meager by Kuratowski–Ulam, and its inverse relation is likewise meager, so it can't be total by the Baire category theorem.

    (The argument also works with measure instead of Baire category.)

    Of course, the usual proof is more or less a specialization of this, but I found it enlightening to see it written that way.

    (And yes, in spite of nominally doing research that involves computability theory, I'm still not familiar with certain things probably considered basic by computability theorists, like the computability-theoretic version of forcing, but I'm catching up.)

    💬 0🔄 3⭐ 1