I have two questions about exercise 6 of section 2.7 of Book of Proof from Hammack.
The exercise asks the reader to write the following statement in English and then to say if the statement is true or false.
$$ \exists \ n \in \mathbb{N}, \forall X \in \mathcal{P}(\mathbb{N}), \vert X \vert < n $$
My first question is whether or not I am reading this correctly.
I interpret this statement as saying "there exists a positive integer greater than the cardinality of all subsets of $\mathbb{N}$". Is that correct?
My second question, assuming my understanding of the statement is correct, is whether the statement is true or not.
My fist line of thought was that the statement is false because for any positive integer $n$ there will always be a subset of $\mathbb{N}$ with cardinality equal or larger than $n$ since the set of natural numbers is infinitely large. However, the converse reasoning seems as valid: for any subset of $\mathbb{N}$, however large it is, there will always exist a positive integer larger than this subset's cardinality. It seems to me now that we cannot really say if the statement is true or false: the statement itself is sort of paradoxical. Would this assessment be the correct answer? Am I missing something here?
Best Answer
Yes, pretty much ... but you want to be a little more explicit/concrete about exactly what subset you can always pick such that its cardinality is not smaller than $n$ for whatever number $n$ you may have picked initially. But it is easy to see what works: you can pick any infinite-sized subset, such as all even numbers ... or even just simply $\mathbb{N}$ itself ... which is also an element of $\mathcal{P}(\mathbb{N})$
First of all, you are now considering the truth of the statement:
$$ \forall X \in \mathcal{P}(\mathbb{N}), \exists \ n \in \mathbb{N}, \vert X \vert < n $$
which is a different statement. But, like the original one, this one is also false. Again, you can use any infinite-sized subset as a counterexample.