A Scary-Looking Quotient Ring …

I was preparing for my algebra final and I ran into this quotient ring constructed in \mathbb{Z}[\sqrt{-5}]:

(1 + \sqrt{-5}, 3) / (1 + \sqrt{-5})

What even is this?!

Continue reading “A Scary-Looking Quotient Ring …”

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?”