I am doing some homework, let me know if this makes sense:
Question
Let $F \subset \mathcal P(\mathbb N)$ be the set of all finite sets of $\mathbb N$. Construct an injection $\phi: F\rightarrow \mathbb N $. What does this say about the cardinality of $F$? Prove your claim.
Claim
The cardinality of $F$ is infinite.
Proof
Given a finite set of primes $P \in F$, where $P=\{p_0, p_1, ..., p_n\}$, then there exists a composite number $c\in \mathbb N$ such that $c = p_0\cdot p_1\cdot ... \cdot p_n$. The number $c+1$ is either prime or composite.
Case 1 - Prime
If $c+1$ is prime, then there exists another finite set $Q \subset F$ such that $Q=\{ p_0, p_1, ..., p_n, (c+1)\}$.
Case 2 - Composite
If $c+1$ is composite, then there exists a prime number $p_k \in \mathbb N$ such that $p_k$ is part of the prime factorization of $c+1$. No prime number of $P$ can increase a number by $1$ through multiplication, so $p_k$ is not an element of $P$. It follows that there exists a finite set $R \subset F$ such that $P\subset R$ and $p_k \in R$.
Implication
Because from any finite set of prime numbers there is another finite set of prime numbers, we can conclude that there are infinite possible sets of prime numbers and that the cardinality of $F$ is infinite.
Questions to reader:
Is this a valid proof? How can I include a function $\phi: F\rightarrow\mathbb N$ in this proof like the question is asking?
