0
$\begingroup$

I want to apply the proof strategies and overall scratch work diagram based framework introduced in the book "How to Prove It" in order to construct step-by-step the proof of the following theorem:

Theorem Any positive rational number has an expression as a fraction in lowest form.

Proof. First write a given positive rational number as a quotient of positive integers $\frac{m}{n}$. We know that 1 is a common divisor of $m$ and $n$. Furthermore, any common divisor is at most equal to $m$ or $n$. Thus among all common divisors there is a greatest one, which we denote by $d$. Thus we can write $$ m = dr \qquad \text{and} \qquad n = ds $$ with positive integers $r$ and $s$. Our rational number is equal to $$ \frac{m}{n} = \frac{dr}{ds} = \frac{r}{s} $$

All we have to do now is to show that the only common divisor of $r$ and $s$ is $1$. Suppose that $e$ is a common divisor which is greater than 1. Then we can write $$ r = ex \qquad \text{and} \qquad s = ey $$ with positive integers $x$ and $y$. Hence $$ m = dr = dex \qquad \text{and} \qquad n = ds = dey $$ Therefore $de$ is a common divisor for $m$ and $n$, and is greater than $d$ since $e$ is greater than $1$. This is impossible because we assumed that $d$ was the greatest common divisor of $m$ and $n$. Therefore $1$ is the only common divisor of $r$ and $s$, and our theorem is proved. $\blacksquare$

The first thing that I did was to rewrite the statement using logical connectives and quantifiers $$ \forall a: (a \in \mathbb{Q}_+) \rightarrow \exists \ r,s : (r,s \in \mathbb{Z}_+) \ \land (a = r/s) \ \land (\operatorname{gcd}(r,s) = 1). $$ making it clear that we are trying to prove a conditional statement.

So we should assume that $(a \in \mathbb{Q}_+)$ and our scratch work diagram becomes \begin{array}{c c c c c} \text{Givens} & & \qquad \qquad \qquad \qquad \qquad & & \text{Goal} \\ \hline (a \in \mathbb{Q}_+) & & & & \exists \ r,s : (r,s \in \mathbb{Z}_+) \ \land (a = r/s) \ \land (\operatorname{gcd}(r,s) = 1) \\ \end{array}

How should I proceed from here? This seems like an existence proof using a proof by contradiction at some point, and while the original proof makes sense to me, I'm having trouble factoring it in small steps using this framework.

$\endgroup$
13
  • $\begingroup$ This basic result has been proved here many times in many ways, e,g, see the linked dupe. It is not clear what you are asking, but the question is not answerable unless you precisely define "proof strategy ...framework". Rewriting everything in symbolic logic is the wrong way to go if what you ultimately seek is a better understanding of the key idea(s) of the proof. $\endgroup$ May 23, 2022 at 12:25
  • $\begingroup$ @BillDubuque, I didn't say I wanted a proof with just symbols. I'm not asking for a formal proof and nowhere in what I wrote that seems to be implied. What I'm asking for is for a proof rewriting using the techniques to approach proofs that appear in a book for beginners that I mentioned in text. The argument that the basic result has been proved here doesn't even make sense, since I even gave a proof of it myself. $\endgroup$
    – fire-bee
    May 23, 2022 at 12:35
  • 2
    $\begingroup$ I said: scratch work diagram based framework introduced in the book "How to Prove It". And in the title: using Velleman's 'given–goal diagrams' This is what I asked for, there isn't any other question here that asks for that. It doesn't seem like a duplicate to me. And it is contextualized for people that actually read the book. I'm appealing to those people, and even the title seems enough for that. Only those who know the name will click on it. $\endgroup$
    – fire-bee
    May 23, 2022 at 12:46
  • 3
    $\begingroup$ I don't understand why you think rewriting is necessary. The proof already follows the strategies in How To Prove It. The given $a\in\mathbb{Q}_+$ means $\exists m\exists n(m,n \in \mathbb{Z}_+ \wedge a = m/n)$, so the proof begins by introducing $m$ and $n$. The proof then produces positive integers r and s such that $r/s=a$ and $\text{gcd}(r,s) = 1$. The proof that $\text{gcd}(r,s)=1$ uses proof by contradiction. All of this is following the strategies in How To Prove It. $\endgroup$ May 26, 2022 at 13:16
  • 2
    $\begingroup$ Yes, I wrote How To Prove It. Theorem 6.4.5 in How To Prove It involves similar reasoning. $\endgroup$ May 29, 2022 at 22:17

1 Answer 1

0
$\begingroup$

Our goal is the universal conditional statement

$$ \forall a \; \biggl[\; a \in \mathbb{Q}_+ \; \rightarrow \; \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr)\; \biggr]$$ with no additional assumptions.

Scratch work

The starting givens-goals diagram is \begin{array}{c c c} \text{Givens} & \qquad \qquad & \text{Goal} \\ \hline & & \forall a \; \biggl[\; a \in \mathbb{Q}_+ \; \rightarrow \; \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr)\; \biggr] \end{array}

$\\[15pt]$

We introduce the new variable $a$ into the proof to stand for an arbitrary object

\begin{array}{c c c} \text{Givens} & \qquad \quad \qquad \qquad & \text{Goal} \\ \hline & & a \in \mathbb{Q}_+ \; \rightarrow \; \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr) \end{array}

$\\[15pt]$

Since our goal is a conditional statement we begin by assuming that the antecedent is true

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr) \end{array}

$\\[15pt]$

Assuming that $a \in \mathbb{Q}_+$ allows us to use the definition of positive rational number

\begin{array}{c c c} \text{Givens} & & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr) \\ \exists \ m \ \exists \ n \; \Bigl( \; m,n \in \mathbb{Z}_+ \; \land \; a = m/n \;\Bigr) & & \end{array}

$\\[15pt]$

We let $m_0, n_0$ stand for positive integers such that $a = m_0 /n_0$ (existential instantiation)

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr) \\ m_0, n_0 \in \mathbb{Z}_+ & &\\ a = m_0/n_0 & & \\ \end{array}

$\\[15pt]$

We let $d$ stand for $\operatorname{gcd}(m_0,n_0)$

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr) \\ m_0, n_0 \in \mathbb{Z}_+ & &\\ a = m_0/n_0 & & \\ d = \operatorname{gcd}(m_0,n_0) && \end{array}

$\\[15pt]$

Let produce positive integers $r,s$

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \\ m_0, n_0 \in \mathbb{Z}_+ & &\\ a = m_0/n_0 & & \\ d = \operatorname{gcd}(m_0,n_0) && \\ r = m_0/d && \\ s = n_0/d && \end{array}

$\\[15pt]$

We treat the conjunction as separate goals

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & r,s \in \mathbb{Z}_+\\ m_0, n_0 \in \mathbb{Z}_+ & & a = r/s\\ a = m_0/n_0 & & \operatorname{gcd}(r,s) = 1\\ d = \operatorname{gcd}(m_0,n_0) && \\ r = m_0/d && \\ s = n_0/d && \end{array}

$\\[15pt]$

The try to prove $\operatorname{gcd}(r,s) = 1$ by contradiction

\begin{array}{c c c} \text{Givens} & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad & \text{Goal} \\ \hline a \in \mathbb{Q}_+ & & r,s \in \mathbb{Z}_+\\ m_0, n_0 \in \mathbb{Z}_+ & & a = r/s\\ a = m_0/n_0 & & \textrm{contradiction}\\ d = \operatorname{gcd}(m_0,n_0) && \\ r = m_0/d && \\ s = n_0/d && \\ \operatorname{gcd}(r,s) \neq 1 && \end{array}

$\\[15pt]$

Form of final proof:

Let $a$ be arbitrary

$\quad$ Suppose $a \in \mathbb{Q}_+$. Let $m_0, n_0 \in \mathbb{Z}_+$ and $a = m_0 / n_0$. Let $d = \operatorname{gcd}(m_0,n_0)$ .

$\quad$$\quad$ Let $r = m_0/d$ and $s = n_0/d$.

$\quad$$\quad$$\quad$ [Proof of $r,s \in \mathbb{Z}_+$ goes here.]

$\quad$$\quad$$\quad$ [Proof of $a = r/s$ goes here.]

$\quad$$\quad$$\quad$ Suppose $\operatorname{gcd}(r,s) \neq 1$

$\quad$$\quad$$\quad$$\quad$ [Proof of contradiction goes here.]

$\quad$$\quad$$\quad$ Therefore $\operatorname{gcd}(r,s) = 1$

$\quad$$\quad$ Thus, $\exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr)$.

$\quad$ Therefore $a \in \mathbb{Q}_+ \; \rightarrow \; \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr)$.

Since $a$ was arbitrary, we can conclude that $\forall a \; \biggl[\; a \in \mathbb{Q}_+ \; \rightarrow \; \exists \ r \ \exists \ s \; \Bigl( \; r,s \in \mathbb{Z}_+ \; \land \; a = r/s \; \land \; \operatorname{gcd}(r,s) = 1 \;\Bigr)\; \biggr].$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .