The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf
However,
Where does it come from that these are inclusive sets and not separate?
Or that $|P| ≤ |NP|$?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThe Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf
However,
Where does it come from that these are inclusive sets and not separate?
Or that $|P| ≤ |NP|$?
One definition of NP is "the set of languages accepted by non-deterministic Turing Machines in polynomial time."
There's a trivial transformation that lets us convert any deterministic Turing Machine into a non-deterministic one, which will have the exact same running time. Basically, you just take the same deterministic TM, rename it as non-deterministic, and don't use any non-determinism.
In short, any deterministic TM is also a non-deterministic TM (but the converse is not true).
So, suppose there's a language $L$. If we can accept $L$ in polynomial time with a deterministic TM, then we just make the trivial non-deterministic TM which runs identically, and we can now accept $L$ in polynomial time with a non-deterministic Turing Machine.
We know that $|P| = |NP|$ because both sets are infinite and countable. There are countably many Turing Machines, since each Turing Machine can be represented as an integer. There is at least one Turing Machine for each language in $NP$, and likewise, at least one Turing Machine for each language in $P$. Since both of these sets are infinite, they must be infinite countable.
P is the set of languages $L$ for which there exists a polytime function $f$ such that $$ x \in L \Longleftrightarrow f(x)=Yes. $$ NP is the set of languages $L$ for which there exists a polytime function $f$ and an integer $k$ such that $$ x \in L \Longleftrightarrow f(x,y)=Yes\text{ for some $y$ of length $|y| \leq k|x|^k$}. $$ (Here $|x|$ is the length of $x$.)
Hopefully you can now show that P$\subseteq$NP on your own.