How to symbolize this statement with multiple quantifiers?

Question

I need to symbolize this statement

"Any natural number $n$ can be written either in the form of $2k$ or in the form of $2k+1$ for some natural number $k$".

I tried with

$\forall n \in \Bbb N,\exists k \in \Bbb N: (n = 2k) \veebar (n = 2k+1)$

But I'm not sure this symbolization is correct

Answer 1

It's not quite accurate because it fails to rule out the possibility that one natural number can be used as a witness for "evenness" and a different integer can be used as a witness for "oddness." To be completely pedantic about it, I'd write:

$\forall n \in \Bbb N [(\exists k \in \Bbb N ~ (n = 2k)) \iff (\forall j \in \Bbb N ~ (n \neq 2j+1))]$.

This says that a number can be expressed as some multiple of $2$ if and only if it can't ever be expressed as $1$ more than a multiple of $2$. Conversely, if $n$ can be expressed as $1$ more than a multiple of $2$ (so that the right-hand side is false), then the left-hand side must also be false so $n$ can't be expressed as a multiple of $2$.

Answer 2

I'd suggest specifying that $0\in\mathbb{N}$ for this definition, otherwise the statement is incorrect. Your symbolization is fine, but it is more correct to use the exclusive or.

Answer 3

If using $\veebar$ for exclusive or, then there is a thing we have to be careful about. Here is the correct version: $$\forall n \in \mathbb N\,[(\exists k \in \mathbb N\, (n = 2k)) \veebar (\exists j \in \mathbb N\, (n = 2j+1))]$$ Here, we've got "$(\exists k \in \mathbb N\, (n = 2k))$" for "$n$ is even", "$(\exists j \in \mathbb N\, (n = 2j+1))$" for "$n$ is odd", and we're claiming that exactly one of them holds for all $n$.

It would also be correct to use $k$ twice: $$\forall n \in \mathbb N\,[(\exists k \in \mathbb N\, (n = 2k)) \veebar (\exists k \in \mathbb N\, (n = 2k+1))]$$ These instances of $k$ have completely separate scope, so there is no confusion between them. (But using $j$ for the second instance of the variable helps it be clear which variable goes with which quantifier.)

However, we cannot factor $\exists k$ out of the exclusive or. The version in the question, with $$\forall n \in \mathbb N\,[\exists k \in \mathbb N\, ((n = 2k) \veebar (n = 2k+1))],$$ does not guarantee that $n$ is exactly one of even or odd. The exclusive or merely guarantees that there's no $k$ for which both $n=2k$ and $n=2k+1$ hold. Since the existential quantifier is not unique, it's possible that there's a $k_1 \in \mathbb N$ satisfying it for which $n = 2k_1$, and also a $k_2 \in \mathbb N$ satisfying it for which $n = 2k_2 + 1$. Then, $n$ would be both even or odd, which does not satisfy the version of the statement we said in words.

We could go a bit further: $$\forall n \in \mathbb N\,[\exists!\, k \in \mathbb N\, ((n = 2k) \veebar (n = 2k+1))],$$ uses the $\exists!$ (exists uniquely) quantifier. This guarantees that $n$ is either even or odd (but not both). We can't have a $k_1$ with $n=2k_1$ and a different $k_2$ with $n=2k_2+1$, because then both $k_1$ and $k_2$ would be candidate $k$'s, and $\exists!$ claims that there is only one. We also can't have $n=2k$ and $n=2k+1$ with the same $k$, because of the $\veebar$.

However, this statement also adds a different claim: that the "witness" to $n$ being even or odd is unique. This is a true claim, but not part of the original statement.