Why Is Many-One Reducibility Not A Total Order?

We use the notation A \leq_m B if there’s a many-one reduction from set A to set B. When I first learned about many-one reduction, the notation \leq_m made me think \leq_m imposes a total order among subsets of \mathbb{N}, i.e. \leq_m on \mathcal{P}(\mathbb{N}) behaves like \leq on \mathbb{N}. Unfortunately, \leq_m only imposes a partial order on \mathcal{P}(\mathbb{N}). In this post, we will discuss an example of two subsets of natural numbers that are not comparable using \leq_m.

Continue reading “Why Is Many-One Reducibility Not A Total Order?”