1
$\begingroup$

I'm learning math and it is assumed that $ n^2 $ is even then I have to prove that $n$ is also even ( n is an integer number ).

I searched online and people were suggesting to prove the other way around which means that if you were to assume that $ n $ is odd and $ n^2 $ is odd then you proved your original one which made no sense. Can someone please elaborate on this and what is the best way to prove that ?

$\endgroup$
3
  • $\begingroup$ Do you know how to write an even number? $\endgroup$
    – Arnaldo
    Sep 20, 2017 at 21:14
  • $\begingroup$ You can write an odd number as $2k+1$ where $k$ is an integer. $\endgroup$ Sep 20, 2017 at 21:15
  • $\begingroup$ you can write an even number by n= 2m. Right? $\endgroup$
    – user481197
    Sep 20, 2017 at 21:33

3 Answers 3

17
$\begingroup$

To prove $P \implies Q$ you can prove $\sim Q \implies \sim P$ - not $Q$ implies not $P$. This is called contraposition. Both statements are equivalent. Here's how we prove the contrapositive.

Let $n = 2j +1$. Squaring gives $n^2 = 4j^2 + 4j + 1 = 2(2j^2 + 2j) +1$. Hence $n^2$ is odd.

This is easier than proving that if $n^2$ is even then $n$ is even.

$\endgroup$
7
  • 1
    $\begingroup$ oohh so i don't even need to prove n is even, but I can simply use some logic and math to prove that opposite which will automatically prove what I wanted? $\endgroup$
    – user481197
    Sep 20, 2017 at 21:31
  • $\begingroup$ This proves that indeed $n$ is even if its square is even. If we say two statements are equivalent, then they are the "same." I suggest reading on propositional logic, perhaps from a book on writing proofs, to understand this better. $\endgroup$ Sep 20, 2017 at 21:36
  • $\begingroup$ one last question, wouldn't that be the same as proving " the product of two odd numbers is odd"? because you write here m,n are integers and m=2q +1 and n = 2r +1 and then eventually ending up with 2(2qr+q+r) +1 ? is this the same prove or am i hallucinating? $\endgroup$
    – user481197
    Sep 20, 2017 at 21:40
  • $\begingroup$ Define "same." Here's a sketch: take two odd numbers and multiply. Can you write the product as $2j+1$? I won't provide details. If you want a proof verification, attempt it and pose that as another question with the "proof-verification" tag. $\endgroup$ Sep 20, 2017 at 21:43
  • $\begingroup$ sorry for not being clear, I don't have a similar question but i just wanted to make sure that I understood and while writing it down it appeared to me that what we did here is actually the same as proving what I just said above. I got lost again because of non-proving what the actual thing is but instead proving something else, where you can conclude from that it is the same. $\endgroup$
    – user481197
    Sep 20, 2017 at 21:47
14
$\begingroup$

Definitions

  1. $x\text{ is even} := \exists y[y+y=x]$ (Denote as $E(x)$)
  2. $x\text{ is odd} := \exists y[S(y+y)=x]$ (Denote as $O(x)$)

Axioms

  1. $\forall x[S(x) \ne 0]$
  2. $\forall x \forall y[S(x)=S(y) \implies x=y]$
  3. $\forall x[x+0=x]$
  4. $\forall x \forall y[x+S(y)=S(x+y)]$
  5. $[\varphi(0) \land [\forall x[\varphi(x) \implies \varphi(S(x))]]] \implies [\forall x \varphi(x)]$
  6. $\forall x[x*0=0]$
  7. $\forall x\forall y[x*S(y)=(x*y)+x]$

Part 1: Addition is commutative

Let $\varphi(y)$ denote $\forall x[y+x=x+y]$.

Let $\psi a(y)$ denote $a+y=y+a$.

01. 0+0=0+0                                         =
02. ψ0(0)                                           ψdef 01
  03. ψ0(b)                                         assumption
  04. 0+b=b+0                                       ψdef 03
  05. S(0+b)=S(b+0)                                 = 04
  06. 0+S(b)=S(b+0)                                 A4
  07. 0+S(b)=S(b)                                   A3
  08. 0+S(b)=S(b)+0                                 A3
  09. ψ0(S(b))                                      ψdef 08
10. ψ0(b)→ψ0(S(b))                                  →I 03-09
11. ∀x[ψ0(x)→ψ0(S(x))]                              ∀I 10
12. [ψ0(0)]∧[∀x[ψ0(x)→ψ0(S(x))]]                    ∧I 02 12
13. [[ψ0(0)]∧[∀x[ψ0(x)→ψ0(S(x))]]]→[∀xψ0(x)]        A5
14. ∀xψ0(x)                                         MP 12 13
15. ∀x[0+x=x+0]                                     ψdef 14
16. ϕ(0)                                            ϕdef 15
  17. ϕ(b)                                          assumption
  18. ∀x[b+x=x+b]                                   ϕdef 17
  19. 0+S(b)=S(b)+0                                 ∀E 15
  20. ψSb(0)                                        ψdef 19
    21. ψSb(a)                                      assumption
    22. S(b)+a=a+S(b)                               ψdef 21
    23. S(b)+S(a)=S(S(b)+a)                         A4
    24. S(b)+S(a)=S(a+S(b))                         para 23 22
    25. S(b)+S(a)=S(S(a+b))                         A4 24
    26. b+a=a+b                                     ∀E 18
    27. S(b)+S(a)=S(S(b+a))                         para 25 26
    28. S(b)+S(a)=S(b+S(a))                         A4 27
    29. b+S(a)=S(a)+b                               ∀E 18
    30. S(b)+S(a)=S(S(a)+b)                         para 28 29
    31. S(b)+S(a)=S(a)+S(b)                         A4 30
    32. ψSb(S(a))                                   ψdef 31
  33. ψSb(a)→ψSb(S(a))                              →I 21-32
  34. ∀x[ψSb(x)→ψSb(S(x))]                          ∀I 33
  35. [ψSb(0)]∧[∀x[ψSb(x)→ψSb(S(x))]]               ∧I 20 34
  36. [[ψSb(0)]∧[∀x[ψSb(x)→ψSb(S(x))]]]→[∀xψSb(x)]  A5
  37. ∀xψSb(x)                                      MP 36 35
  38. ϕ(S(b))                                       ϕdef 37
39. ϕ(b)→ϕ(S(b))                                    →I 17-38
40. ∀x[ϕ(x)→ϕ(S(x))]                                ∀I 39
41. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]                       ∧I 16 40
42. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]            A5
43. ∀xϕ(x)                                          MP 42 41

We shall use $P1$ to denote this.

Part 2: Addition is associative

Let $\varphi(x)$ denote $(a+b)+x=a+(b+x)$.

01. (a+b)+0=a+b                           A3
02. b+0=b                                 A3
03. (a+b)+0=a+(b+0)                       para 01 02
04. ϕ(0)                                  ϕdef 03
  05. ϕ(c)                                assumption
  06. (a+b)+c=a+(b+c)                     ϕdef 05
  07. S((a+b)+c)=S(a+(b+c))               = 06
  08. (a+b)+S(c)=S(a+(b+c))               A4 07
  09. (a+b)+S(c)=a+S(b+c)                 A4 08
  10. (a+b)+S(c)=a+(b+S(c))               A4 09
  11. ϕ(S(c))                             ϕdef 10
12. ϕ(c)→ϕ(S(c))                          →I 05-11
13. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 12
14. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 04 13
15. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
16. ∀xϕ(x)                                MP 15 14

We shall use $P2$ to denote this.

Part 3: Multiplication is left-distributive

Let $\varphi(x)$ denote $a*(b+x)=(a*b)+(a*x)$.

01. b+0=b                                 A3
02. a*(b+0)=a*b                           = 01
03. a*0=0                                 A6
04. (a*b)+0=a*b                           A3
05. (a*b)+(a*0)=a*b                       para 04 03
06. a*(b+0)=(a*b)+(a*0)                   para 02 05
07. ϕ(0)                                  ϕdef 06
  08. ϕ(c)                                assumption
  09. a*(b+c)=(a*b)+(a*c)                 ϕdef 08
  10. b+S(c)=S(b+c)                       A4
  11. a*(b+S(c))=a*S(b+c)                 = 10
  12. a*(S(b+c))=(a*(b+c))+a              A7
  13. a*(b+S(c))=(a*(b+c))+a              para 11 12
  14. a*(b+S(c))=((a*b)+(a*c))+a          para 13 09
  15. (a*b)+(a*c))+a=(a*b)+((a*c)+a)      P2
  16. a*(b+S(c))=(a*b)+((a*c)+a)          para 14 15
  17. a*S(c)=(a*c)+a                      A7
  18. a*(b+S(c))=(a*b)+(a*S(c))           para 16 17
  19. ϕ(S(c))                             ϕdef 18
20. ϕ(c)→ϕ(S(c))                          →I 08-19
21. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 20
22. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 07 21
23. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
24. ∀xϕ(x)                                MP 23 22

We shall use $P3$ to denote this.

Part 4: Every non-zero number has a predecessor

Let $\varphi(x)$ denote $x \ne 0 \implies \exists y [S(y)=x]$.

  01. 0≠0                                 assumption
  02. ⊥                                   01
  03. Ǝy[S(y)=0]                          explosion
04. 0≠0→Ǝy[S(y)=0]                        →I 01-03
05. ϕ(0)                                  ϕdef 04
  06. ϕ(a)                                assumption
  07. a≠0→Ǝy[S(y)=a]                      ϕdef 06
    08. S(a)≠0                            assumption
    09. S(a)=S(a)                         =
    10. Ǝy[S(y)=S(a)]                     ƎI 09
  10. S(a)≠0→Ǝy[S(y)=S(a)]                →I 08-10
  11. ϕ(S(a))                             ϕdef 10
12. ϕ(a)→ϕ(S(a))                          →I 06-11
13. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 12
14. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 05 13
15. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
16. ∀xϕ(x)                                MP 15 14

We shall use $P4$ to denote this.

Part 5: Every number is either odd or even

Let $\varphi(x)$ denote $[E(x) \land \neg O(x)] \lor [O(x) \land \neg E(x)]$.

01. 0+0=0                                      A3
02. Ǝy[y+y=0]                                  ƎI 01
03. E(0)                                       Edef 02
  04. O(0)                                     assumption
  05. Ǝy[S(y+y)=0]                             Odef 04
    06. S(b+b)=0                               assumption
    07. ⊥                                      A1
  08. ⊥                                        ƎE 05 06-07
09. ¬O(0)                                      ¬I 04-08
10. E(0)∧¬O(0)                                 ∧I 03 09
11. [E(0)∧¬O(0)]∨[O(0)∧¬E(0)]                  vI 10
12. ϕ(0)                                       ϕdef 11
  13. ϕ(a)                                     assumption
  14. [E(a)∧¬O(a)]∨[O(a)∧¬E(a)]                ϕdef 13
    15. E(a)∧¬O(a)                             assumption
    16. E(a)                                   ∧E 15
    17. ∃y[y+y=a]                              Edef 16
      18. b+b=a                                assumption
      19. S(b+b)=S(a)                          18
      20. ∃y[S(y+y)=S(a)]                      ∃I 19
    21. ∃y[S(y+y)=S(a)]                        ∃E 17 18-20
    22. O(S(a))                                Odef 21
      23. E(S(a))                              assumption
      24. ∃y[y+y=S(a)]                         Edef 23
        25. b+b=S(a)                           assumption
          26. b=0                              assumption
          27. 0+0=S(a)                         para 25 26
          28. 0=S(a)                           A3 27
          29. ⊥                                A1
        30. b≠0                                ¬I 26-29
        31. ∃z[S(z)=b]                         P4 30
          32. S(c)=b                           assumption
          33. S(c)+S(c)=S(a)                   para 25 32
          34. S(S(c)+c)=S(a)                   A4 33
          35. S(c)+c=a                         A2 34
          36. c+S(c)=a                         P1 35
          37. S(c+c)=a                         A4 36
          38. ∃y[S(y+y)=a]                     ∃I 37
          39. ¬O(a)                            ∧E 15
          40. ⊥                                38 39
        41. ⊥                                  ∃E 31 32-40
      42. ⊥                                    ∃E 24 25-41
    43. ¬E(S(a))                               ¬I 23-43
    44. O(S(a))∧¬E(S(a))                       ∧I 22 43
    45. [E(S(a))∧¬O(S(a))]∨[O(S(a))∧¬E(S(a))]  ∨I 44
    46. ϕ(S(a))                                ϕdef 45
  47. [E(a)∧¬O(a)]→ϕ(S(a))                     →I 15-46
    48. O(a)∧¬E(a)                             assumption
    49. O(a)                                   ∧E 48
    50. ∃y[S(y+y)=a]                           Odef 49
      51. S(b+b)=a                             assumption
      52. S(S(b+b))=S(a)                       = 51
      53. S(b+S(b))=S(a)                       A4 52
      54. S(S(b)+b)=S(a)                       P1 53
      55. S(b)+S(b)=S(a)                       A4 54
      56. ∃y[y+y=S(a)]                         ∃I 55
    57. ∃y[y+y=S(a)]                           ∃E 50 51-56
    58. E(S(a))                                Edef 57
      59. O(S(a))                              assumption
      60. ∃y[S(y+y)=S(a)]                      Odef 59
        61. S(b+b)=S(a)                        assumption
        62. b+b=a                              A2 61
        63. ∃y[y+y=a]                          ∃I 62
        64. ¬E(a)                              ∧E 48
        65. ⊥                                  63 64
      66. ⊥                                    ∃E 60 61-65
    67. ¬O(S(a))                               ¬I 59-66
    68. E(S(a))∧¬O(S(a))                       ∧I 58 67
    69. [E(S(a))∧¬O(S(a))]∨[O(S(a))∧¬E(S(a))]  ∨I 68
    70. ϕ(S(a))                                ϕdef 69
  71. [O(a)∧¬E(a)]→ϕ(S(a))                     →I 48-70
  72. ϕ(S(a))                                  ∨E 14 47 71
73. ϕ(a)→ϕ(S(a))                               →I 48-72
74. ∀x[ϕ(x)→ϕ(S(x))]                           ∀I 73
75. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]                  ∧I 12 74
76. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]       A5
77. ∀xϕ(x)                                     MP 76 75

We shall use $P5$ to denote this.

Part 6: If $n^2$ is even then $n$ is even

  01. E(n*n)                                                   assumption
  02. ∃y[y+y=n*n]                                              Edef 01
  03. [E(n)∧¬O(n)]∨[O(n)∧¬E(n)]                                P5 n
    04. E(n)∧¬O(n)                                             assumption
    05. E(n)                                                   ∧E 04
  06. [E(n)∧¬O(n)]→E(n)                                        →I 04-05
    07. O(n)∧¬E(n)                                             assumption
    08. O(n)                                                   ∧E 07
    09. ∃y[S(y+y)=n]                                           Odef 08
      10. S(b+b)=n                                             assumption
      11. S(b+b)*S(b+b)=n*n                                    = 10
      12. (S(b+b)*(b+b))+S(b+b)=n*n                            A7 11
      13. (S(b+b)*((b+0)+b))+S(b+b)=n*n                        A3 12
      14. (S(b+b)*((0+b)+b))+S(b+b)=n*n                        P1 13
      15. (S(b+b)*(((b*0)+b)+b))+S(b+b)=n*n                    A6 14
      16. (S(b+b)*((b*S(0))+b))+S(b+b)=n*n                     A7 15
      17. (S(b+b)*(b*S(S(0))))+S(b+b)=n*n                      A7 16
      18. ((S(b+b)*b)*S(S(0)))+S(b+b)=n*n                      P3 17
      19. (((S(b+b)*b)*S(0))+(S(b+b)*b))+S(b+b)=n*n            A7 18
      20. ((((S(b+b)*b)*0)+(S(b+b)*b))+(S(b+b)*b))+S(b+b)=n*n  A7 19
      21. ((0+(S(b+b)*b))+(S(b+b)*b))+S(b+b)=n*n               A6 20
      22. (((S(b+b)*b)+0)+(S(b+b)*b))+S(b+b)=n*n               P1 21
      23. ((S(b+b)*b)+(S(b+b)*b))+S(b+b)=n*n                   A3 22
      24. S(((S(b+b)*b)+(S(b+b)*b))+(b+b))=n*n                 A4 23
      25. S((((S(b+b)*b)+(S(b+b)*b))+b)+b)=n*n                 P2 24
      26. S(((S(b+b)*b)+((S(b+b)*b)+b))+b)=n*n                 P2 25
      27. S(((S(b+b)*b)+(b+(S(b+b)*b)))+b)=n*n                 P1 26
      28. S((((S(b+b)*b)+b+(S(b+b)*b)))+b)=n*n                 P2 27
      29. S((((S(b+b)*b)+b)+((S(b+b)*b))+b))=n*n               P2 28
      30. ∃y[S(c+c)=n*n]                                       ∃I 29
    31. ∃y[S(c+c)=n*n]                                         ∃E 09 10-30
    32. O(n*n)                                                 Edef 31
    33. [E(n*n)∧¬O(n*n)]∨[O(n*n)∧¬E(n*n)]                      P5 n*n
      34. E(n*n)∧¬O(n*n)                                       assumption
      35. ¬O(n*n)                                              ∧E 34
      36. ⊥                                                    31 35
    37. [E(n*n)∧¬O(n*n)]→⊥                                     →I 34-36
      38. O(n*n)∧¬E(n*n)                                       assumption
      39. ¬E(n*n)                                              ∧E 38
      40. ⊥                                                    01 39
    41. [O(n*n)∧¬E(n*n)]→⊥                                     →I 38-40
    42. ⊥                                                      ∨E 33 37 41
    43. E(n)                                                   explosion
  44. [O(n)∧¬E(n)]→E(n)                                        →I 07-43
  45. E(n)                                                     ∨E 03 06 44
46. E(n*n)→E(n)                                                →I 01-45

Conclusion

This is surprisingly provable in intuitionistic logic.

$\endgroup$
5
  • 8
    $\begingroup$ I really think this is overkill for what the OP asks. $\endgroup$ Sep 21, 2017 at 15:26
  • 4
    $\begingroup$ This is amazing. 10 outta 10 $\endgroup$ Sep 21, 2017 at 22:14
  • $\begingroup$ Please tell which language it is, so as to make better out of it. $\endgroup$
    – jiten
    Sep 16, 2020 at 21:09
  • $\begingroup$ Please don't tell me you did this by hand. $\endgroup$ Sep 28, 2020 at 13:11
  • $\begingroup$ I did this by hand. $\endgroup$
    – Kenny Lau
    Sep 28, 2020 at 13:12
2
$\begingroup$

Lemma: Let $m, n \in \Bbb Z$. If $m+n$ is even, then $m$ has the same parity as $n$.

Proof: Suppose by contradiction, without loss of generality, that $m$ and $n$ have different parities. Therefore $m = 2a$ and $n = 2b + 1$. So $2|2(a+b) + 1 \implies 2|1$, absurd. Therefore $m$ and $n$ have the same parities.

Now see that $n^2 - n = n(n-1)$, product of two consecutive numbers. So $n^2$ and $-n$ have the same parity (the product is even, analyze the remainder for each case) . Therefore $-n$ is even so $n$ is also even.

$\endgroup$
1
  • $\begingroup$ Best and unique. $\endgroup$
    – jiten
    Sep 16, 2020 at 21:06

You must log in to answer this question.