7.4 Constructive Versus Non-Constructive Proofs

Class: CSE 16 Subject: computer-science Date: 2024-11-13 Teacher: Prof. Musacchio

Proving Non-Conditional Statements

Non-Constructive Proof

• non-constructive proofs prove an example exists without actually giving it.

Example

• Proposition There exist irrational numbers $x,y$ for which $xy$ is rational.
  • Proof. Let x = \sqrt2^\sqrt2 and $y=\sqrt{2}$. We know $y$ is irrational, but it is not clear whether $x$ is rational or irrational. On one hand, if $x$ is irrational, then we have an irrational number to an irrational power that is rational: x^y = {(\sqrt2^\sqrt2)}^\sqrt2 = \sqrt2^{\sqrt2\sqrt2} = \sqrt2^2 = 2
  • On the other hand, if $x$ is rational, then y^y = \sqrt2^\sqrt2 = x is rational. Either way, we have an irrational number to an irrational power that is rational.

Constructive Proof

• constructive proofs display an explicit example that proves the theorem

Example

• Proposition There exist irrational numbers $x,y$ for which $xy$ is rational.
  • Proof. Let $x=\sqrt{2}$ and $y=lo{g}_{2}9$. Then: $x^y={\sqrt{2}}^{lo{g}_{2}9}={\sqrt{2}}^{lo{g}_2{3}^2}=({\sqrt{2}}^2{)}^{2lo{g}_{2}3}=({\sqrt{2}}^2{)}^{lo{g}_{2}3}=s^{log{2}_3}=3$
• As 3 is rational, we have shown that $xy=3$ is rational. We know that $x=\sqrt{2}$ is irrational. The proof will be complete if we can show that $y=lo{g}_{2}9$ is irrational.
• Suppose for the sake of contradiction that $log{2}_9$ is rational, so there are positive integers $a$ and $b$ for which $ab=log{2}_9$.
• This means $2^{a|b}=9$, so $(2^{a|b}{)}^b=9b$, which reduces to $2a=9b$. But $2a$ is even, while $9b$ is odd (because it is the product of the odd number 9 with itself $b$ times).
• This is a contradiction; the proof is complete.