Solving $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

Question

I have been solving this problem from Velleman's How to prove book:

$\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

This is my solution so far:

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

But the answer given in the book is:

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

I'm not able to understand how that answer is correct ?

Answer 1

We may add some condiderations :

(i) from an "intuitive" point of view, it is easy to convince inself that the number $n^2 + n +1$, for all $n$ is odd; thus, it must be obviously true that :

$\{ n^2+n+1 | n \in \mathbb N \} \subseteq \{ 2m+1 | m \in \mathbb N \}$.

(ii) the defining condition for set inclusion is :

$A \subseteq B$ iff for all $x$, if $x \in A$, then $x \in A$;

in our example, this is :

forl all $x$, if $\exists n (x = n^2+n+1)$, then $\exists m (x = 2m+1)$.

Note : having rewritten the defining condition in explicit form (i.e. without the set-builder "operator" $\{ n | \varphi(n) \}$), we can verify that the variables $n,m$ are bound. Thus, it does not matter what variable we use, and using the same variable in both formulae can be misleading, because there is no "link" between the two.

(iii) now we can "formalize" the above facts with a single first-order formula expressing the condition for inclusion :

$\forall x(\exists n (x = n^2+n+1) \rightarrow \exists m (x = 2m+1))$ --- (*).

We can use some logical laws to transform the last formula.

We have that :

if $x$ does not occur free in $\alpha$, then $(∃x \beta → \alpha) ↔ ∀x(\beta → \alpha)$.

Thus, applying it to (*) [$n$ is not free in $\exists m (x = 2m+1)$], we get the equivalent formula :

$\forall x \forall n ((x = n^2+n+1) \rightarrow \exists m (x = 2m+1))$.

Now we use :

if $x$ does not occur free in $\alpha$, then $(\alpha → ∃x \beta) ↔ ∃x(\alpha → \beta)$.

Applying it to the above formula [$m$ is not free in $(x = n^2+n+1)$] we have :

$\forall x \forall n \exists m ((x = n^2+n+1) \rightarrow (x = 2m+1))$

which is again equivalent to (*).

The last transformation is licensed by identity laws :

if $x = a$ and $x = b$, then $a = b$.

Applying it to : $(x = n^2+n+1) \rightarrow ((x = 2m+1) \rightarrow (n^2+n+1 = 2m+1))$ we can get the final transformation of (*) :

$\forall n \exists m (n^2+n+1 = 2m+1)$.

Answer 2

Hint: $n^2 + n + 1 = n(n+1) + 1$, and $2|n(n+1)$

Answer 3

Note the $n$ in two sets are independent. If you are confused, you may write the second set as $\{2m + 1 | m \in \mathbb{N} \}$, which refers the exactly same set as $\{2n + 1 | n \in \mathbb{N} \}$.

To show $A\subset B$, you need to show $\forall x\in A$, $x\in B$. That is, if $x$ satisfies the requirement of set $A$, then it must satisfy the requirement of being in set $B$. In your case, it's just what the solution means. Hence what you need to do is to show $2|n^2 + n$, which can be done by discussing the cases where $n$ is odd or even.

Answer 4

In order to prove that $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$, pick any $x \in \{n^2 + n + 1 | n \in \mathbb{N} \} $, we are wanted to prove that $x \in \{2n + 1 | n \in \mathbb{N} \}$.

Suppose that $x=k^2+k+1$. Then $x=k(k+1)+1$. Clearly $2|k(k+1)$, hence exists $n \Bbb N$ such that $k(k+1)=2n$, and hence $x=2n+1$.