Given the statement: Every natural number is odd

I have to turn this statement into a mathematical proposition. I also have to write up its negation as well (where the $\neg$ doesn't show up in the final answer).

Steps I took:

$$N(x) : x \in\mathbb{N},\quad k \in\mathbb{Z}$$

$$\forall x(N(x)\rightarrow \exists k(N(k)\wedge x=2k+1))$$

Negation: $\neg \forall x(N(x)\rightarrow \exists k(N(k)\wedge x=2k+1))$

$$\Rightarrow\exists x\neg (N(x)\rightarrow \exists k(N(k)\wedge x=2k+1))$$

$$\Rightarrow\exists x (N(x)\wedge\neg \exists k(N(k)\wedge x=2k+1))$$

$$\Rightarrow\exists x (N(x)\wedge \forall k \neg (N(k)\wedge x = 2k+1))$$

$$\Rightarrow\exists x (N(x)\wedge \forall k(N(k)\rightarrow x\neq 2k+1))$$

I'm almost positive about my answer, but my problem is that I don't truly understand what I did here because I just went off or things I saw in the MIT OCW lecture notes to try and formulate this. One of the drawbacks to self studying is not being able to get something clarified when I don't understand. I am hoping that someone here can break down a few things for me here (in layman terms).

Why was $N(x)$ used? Why couldn't I just use $x\in\mathbb{N}$ ? I don't understand why I had to create a function in order to represent the $\mathbb{N}$. I would also like understand the predicate to this statement. I wrote it up that way because another example contained a similar format. I would like to know why it had to use the $\wedge$ operator.

Please break it down to me in layman terms. I'm not used to this type of math and MIT's Math for CS is my first exposure to Discrete Math. (Although I know that some people here might argue that it's barely scratching the surface of discrete math).

  • $\begingroup$ Small typo, the second right parenthesis should be erased. $\endgroup$ Nov 1 '15 at 18:38
  • $\begingroup$ @AndréNicolas Would you please be able to point out where exactly? $\endgroup$ Nov 1 '15 at 18:41
  • $\begingroup$ Second displayed formula starts with $\forall x(N(x))\to$. It should start with $\forall x(N(x)\to$. $\endgroup$ Nov 1 '15 at 18:45
  • 2
    $\begingroup$ The last step is wrong; from $¬∃k(N(k)∧x=2k+1)$ to $∀k¬(N(k)∧x=2k+1)$ to $∀k(N(k)→x≠2k+1)$. $\endgroup$ Nov 1 '15 at 18:56
  • $\begingroup$ @AndréNicolas Why put a parentheses at all then? Would you be able to explain why $N(x)$ is used represent the natural numbers? $\endgroup$ Nov 1 '15 at 19:03

It strikes me that you could just write $\forall x\in \mathbf{N} \exists k\in \mathbf{N}\cup \{0\} \hspace{0.5cm} \mbox{such that} \hspace {0.5cm} x=2k+1$

  • $\begingroup$ The problem specifically stated that I need to start by putting a $\neg$ outside of the initial statement and work it inside. $\endgroup$ Nov 1 '15 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.