1
$\begingroup$

I have some confusion regarding a proof – not in its contents per se, but more in the logical structure. Here's the scenario:

enter image description here

enter image description here

Upon observation, it's apparent that the author aims to establish the uniqueness of the natural number $k$. To achieve this, the author employs a proof by contradiction. Initially, two natural numbers, $t$ and $r$, are assumed to satisfy certain properties. However, this alone doesn't seem sufficient to reach a contradiction. Subsequently, the author assumes $t \leq r$, perhaps by applying the law of trichotomy. Then, using a specific exercise (which I won't include here since it is irrelevant to the discussion), a contradiction is derived, allowing the author to conclude that $t=r$.

My confusion stems from the fact that there are two initial assumptions:

(1) There exist $t, r \in \mathbb{N}$ such that ...

(2) $t \leq r$

Upon reaching a contradiction, wouldn't it imply that either the negation of (1) or (2) is true? How does the author justify concluding that $t=r$?

$\endgroup$
3
  • $\begingroup$ Yes there are those two initial assumptions. But there would be a contradiction if $t<r$. Therefore $t=r$ $\endgroup$
    – J. W. Tanner
    Commented Feb 1 at 2:30
  • $\begingroup$ Shouldn't it be better to say 'WLOG, assume that $t<r$', and thus obtaining that either $t=r$ or $t>r$, but if we assume $t>r$ a contradiction is obtained, thus giving us that $t=r$? $\endgroup$
    – J. J. Gonzalez
    Commented Feb 1 at 3:21
  • $\begingroup$ There is a loss of generality if we assume $t<r$; what if $t=r?\;$ But there's no loss of generality if we assume $t\le r$, because that even covers the case $t\gt r$ by switching $r$ and $t$. And a contradiction is obtained when $t\lt r$, so we conclude that $t=r$ $\endgroup$
    – J. W. Tanner
    Commented Feb 1 at 3:35

1 Answer 1

Reset to default
2
$\begingroup$

From my comments:

Yes, there are the two initial assumptions that (1) there are $t,r\in\mathbb N$

and (2) without loss of generality (i.e., WLOG) $\color{blue}{t\le r}$.

(Note that there would be a loss of generality if we assume that $t\lt r$; what if $t=r?\;$

But there's no loss of generality if we assume that $t\lt r$ or $t=r$,

because that even covers the (third) case $t>r$ by switching $r$ and $t$.)

But there would be a contradiction if $\color{blue}{t\lt r}.\;$ Therefore, $\color{blue}{t=r}.$

$\endgroup$
3
  • $\begingroup$ Hi Tanner. I think I understand somewhat. Since boh $t$ and $r$ are natural numbers, then by the Law of Trichotomy we have three possibilities, either $t<r$, $t=r$, $r<t$. The first two cases are considered since for the last one it is only a matter of switching those numbers off. $\endgroup$
    – J. J. Gonzalez
    Commented Feb 2 at 13:22
  • $\begingroup$ It is as if the three cases were considered at the same time in (2). Hence, when a contradiction is produced it would mean that either (1) or (2) are false, but if (2) were false then it would contradict the Law of trichotomy since (2) considers the three cases, and hence the negation of (1) is true which give us the result we want. Is this interpretation correct? $\endgroup$
    – J. J. Gonzalez
    Commented Feb 2 at 13:29
  • $\begingroup$ Your first comment is correct. WLOG we consider the two cases $t<r$ and $t=r.$. But $t<r$ leads to a contradiction, so we conclude that $t=r$ $\endgroup$
    – J. W. Tanner
    Commented Feb 2 at 13:41

You must log in to answer this question.

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