I was studying for an upcoming test in college and was looking at an old test. I'm struggling to understand how to prove this problem and was hoping someone could help me out.
Prove that |P| = |N| where P is the set of primes and N is the set of natural numbers.
To show the two sets are of the same cardinality, the easiest way is to find a bijection between the two sets. I.E - a one to one correspondence.
How could we match each prime number to one natural number and vice versa? The obvious way would be to match the first prime number to the number 1, the second prime number to the number 2, etc. As J.G said, Euclid proved the are infinitely many primes, so you wouldn't run out of any along the way.
We found a bijection between the two sets, so they are of the same cardinality ($\aleph_0$).