2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yes, $F$ is infinite; can you use the injection to show an upper bound on the cardinality of $F$? $\endgroup$ Dec 4, 2016 at 3:46

0

You must log in to answer this question.

Browse other questions tagged .