The meaning of Tautology and Contradiction in Complexity theory

Question

I recently had this question answered on stack exchange:
if X is in NP but Y is not in NP then can X be reduced to Y?

The answer proposed a counter example using an element of complexity theory I had not given much thought to, specifically it was the problem

$A = \emptyset$

that is, $A$ is the empty problem (or contradiction problem) where $\forall$ inputs $x$, $x \not\in A$

The role of $A = \emptyset$ in my answered question was that it served as problem in $NP$ that could be reduced to any other problem, including those not in $NP$, thereby giving a direct counter example to the statement: $X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$

What interests me was the implication that $A = \emptyset$ could be polynomial-time, many-one reduced to any other problem and that $A \in NP$.

This makes sense to me as these two implication seems vacuously true:

Let $B$ be any other problem such that $B \neq \emptyset$. Now $A \le^m_p B$ if $\exists$ some polynomial reduction $f$ such that $\forall$ inputs $x$, $x \in A \iff f(x) \in B$. But since $\not\exists x, x \in A$ by the definition of A then the reduction of $A$ to any $B$ would be a trivial one in that no matter what the given input $x$, the reduction $f(x)$ could simply produce a same input instance for $B$ such that $f(x) \not\in B$

$A \in NP$ since it seems clear that verifying an input to a problem that always returns false can be trivially accomplished in polynomial time in that we don't really even need to verify anything since there is no input instance to $A$ that would evaluate to true

Using the same logic as above this leads me to reason that there is a tautology problem $C$ such that $\forall$ inputs $x$, $x \in C$ and that $C \in NP$ and $C$ can be polynomial-time, many-one reduced to any other problem just like $A$

Is this true? or have I made an erroneous assumption? And what other useful properties are possessed by the contradiction and tautology problems $A$ and $C$?

Answer 1

You've actually missed an important prerequisite in your argument that $\emptyset \leq_m^p B$: You need that $B \neq \Sigma^*$ (the "tautology" problem $C$ you introduce later, where every instance is a "yes"-instance). But we do get that $\emptyset \leq_m^p B$ iff $B \neq \Sigma^*$, and with a very similar argument, that $\Sigma^* \leq_m^p B$ iff $B \neq \emptyset$.

I wouldn't really consider these useful examples. They are more annoying examples, i.e. require us to make exceptions in statements that would otherwise be true (eg, we would have liked to say "If $X \in \mathrm{P}$ and $Y$ arbitrary, then $X \leq_m^p Y$" - but we need to exclude $Y = \emptyset$ and $Y = \Sigma^*$ to make it true).