# So if a problem is more difficult the language it represents is smaller?

I'm reading the definition of polynomial time reducible:

Let $$L_1, L_2$$ be two language. If $$L_1$$ is polynomial time reducible to $$L_2$$ then exists $$f:\{0,1\}^*$$ s.t. $$\forall x\in\{0,1\}^*$$ $$x\in L_1\iff f(x)\in L_2$$

For me this means the $$L_1$$ may be bigger (in cardinality) than $$L_2$$, but $$L_2$$ is more difficult since $$L_1$$ can be solved after reduced to $$L_2$$?

• How would define the cardinality of an infinite set being larger than another infinite set (both being countable sets)? – dkaeae Dec 31 '18 at 14:53
• You can find examples in which $L_1$ is a strict subset of $L_2$ (and vice versa). – Yuval Filmus Dec 31 '18 at 15:17

$$L_1$$ and $$L_2$$ are always countably infinite, and thus "equally big".