1
$\begingroup$

Does anyone here know about Conway's On numbers and games? Because I can't figure out what he does here on p18. It feels a bit like he's using the statement we want to prove

I will type the proof below:

Theorem 5. We have $y\geq z$ iff $x+y\geq x+z$.

Proof. If $x+y\geq x+z$, we cannot have

$$x+y^R\leq x+z\quad\text{or}\quad x+y\leq x+z^L$$

and so by induction we cannot have $y^R\leq z$ or $y\leq z^L$ so that $y\geq z$.

Now supposing $x+y\ngeq x+z$ we must have one of

$$x^R+y\leq x+z,\quad x+y^R\leq x+z,\quad x+y\leq x^L+z,\quad x+y\leq x+z^L,$$

and if we further suppose $y\geq z$, we deduce one of

\begin{equation} \tag{$*$}\label{star} x^R+y\leq x+y,\quad x+y^R\leq x+y,\quad x+z\leq x^L+z,\quad x+z\leq x+z^L, \end{equation}

All of which imply contradictions by cancellation.

I think I don't understand the step \eqref{star} correctly, because I think it would require the theorem itself, but that may be wrong.

$\endgroup$
6
  • $\begingroup$ It's much better if you actually type out the formulae into the question, rather than providing an ephemeral link to an image. $\endgroup$
    – Apollo
    Commented Aug 16, 2022 at 15:43
  • 4
    $\begingroup$ As far as the question goes, I think he's just doing a typical inductive argument by contradiction - choose a least putative counter-example (so that all subgames satisfy the induction hypothesis) and show it leads to a contradiction. $\endgroup$
    – Apollo
    Commented Aug 16, 2022 at 15:47
  • $\begingroup$ I edited the question to make it more readable and clear what I don't understand $\endgroup$ Commented Aug 16, 2022 at 16:25
  • $\begingroup$ Thanks. A typical argument by contradiction in (structural) induction goes: suppose that the proposition does not hold. Then take a least counter-example X. In our case, this means all elements of X do satisfy the proposition. Then prove that this implies a contradiction, hence the proposition holds for X, and as X was a least counterexample, the proposition must hold generally. Here, he is proving $x+y\ngeq x+z$ implies $y\ngeq z$ (the converse direction) by contradiction. $\endgroup$
    – Apollo
    Commented Aug 16, 2022 at 18:02
  • $\begingroup$ I think I understand the structure of the proof, but to get from the first four inequalities to the latter four, I can't see an easy way without using the theorem itself. I do understand the rest though. $\endgroup$ Commented Aug 16, 2022 at 18:45

0

You must log in to answer this question.

Browse other questions tagged .