How to show these two statements are equivalent?

Question

In an example I am asked to analyse the logical form of the statement $$\{n^2 + n + 1 : n \in \mathbb{N}\} \subset \{2n + 1 : n \in \mathbb{N}\}$$

My solution is $$\forall x[\exists n\in\mathbb{N}(x = n^2 + n +1) \implies \exists n \in \mathbb{N}(x = 2n+1)] $$

I get this by re-expressing $\{n^2 + n + 1: n \in \mathbb{N}\}$ as $\{x: \exists n \in \mathbb{N} (x = n^2 +n +1)\}$ (and similarly for the other set), and then using the definition of the subset.

However the solution given by the book seems to be the much more sensible:$$\forall n \in \mathbb{N}\exists m\in \mathbb{N}(n^2+n+1=2m+1)$$

I understand the solution in the book, and if I were to write it based on the meaning of statement I think that is how I would do it. However in my own solution, I was trying to follow the precise rules for manipulating the expressions, and to express it in terms of unbounded quantifiers first.

What I can't do is show how the two statements are equivalent. When I think about the meaning, I believe my solution is correct, but I can't seem to manipulate my statement to turn it into the book's solution. I can only intuitively understand the book's solution.

My question is how to show that these two statements are equivalent? In general, I have a hard time with statements of this form; I am not sure how to show step by step the elimination of the existential quantifiers from the equality statement. Is this just a trivial step? Is there a rule of inference to go from my solution to the book's?

Answer 1

$\forall x\exists n(n\in\mathbb{N}(x = n^2 + n +1) \implies \exists n \in \mathbb{N}(x = 2n+1))$

The two "$n$"s are unrelated so for clarity we can use another symbol for it:

$\forall x\exists n(n\in\mathbb{N}(x = n^2 + n +1) \implies \exists m \in \mathbb{N}(x = 2m+1))$

As $x=n^2+n+1$ we can refer to that in the second clause.

$\forall x\exists n(n\in\mathbb{N}(x = n^2 + n +1) \implies \exists m \in \mathbb{N}(n^2 + n +1 = 2m+1))$

Now.....

Let's consider a statement of the form $\forall x\exists a(x=f(a)\implies P(f(a)))$....

In english that is: For all possible $x$ in the universe, then there exists an $a$ so that if $x$ happens to fall into a specific expression of $a$ then we can conclude something about the express of $a$ (and presumably if $x$ doesn't fall into that expression then nothing is concluded).

This is unnecessary placeholding. It is similar to saying "For every person on the planet if that person is a Scorpio, then that was born in November or October". Or "For every thing if that thing is an elephant then that thing is a mammal". Or to just make this absurd "For every physical object that is composed in part by carbon atoms if that carbon composed object is a student at Funhouse Academy that carbon composed object will enjoy a wide variety of sponsored social activities and academic pursuits"

We aren't making any observation about $x$ in general; we are only making reference to those of the form $n^2 + n + 1$. So we don't need to quantify the variable $x$. We can but it is unnecessary.

So we can say:

$\exists n(n\in\mathbb{N}(n^2 + n +1$ is something that exists $) \implies \exists m \in \mathbb{N}(n^2 + n +1 = 2m+1)$

Now we have mangled that first clause to something absurdly pointless. Of course there exists an $n$ so that $n\in \mathbb {N}$ and $n^2 +n+1$ is something. That's true for all $n \in \mathbb N$.

Instead of saying "if there exists an $n$ so that $n$ is a natural number and something that is possible for all natural numbers then SOMETHING INTERESTING" we can simply say "for all natural numbers, SOMETHING INTERESTING"

So $\forall n \in \mathbb{N}\exists m\in \mathbb{N}(n^2+n+1=2m+1)$

That's it.