2

I was reading a book entitled Godel, Escher, Bach and one of its problems asks how a person can write that B is a power of 2 in its TNT language.

One solution I found online reads:

∀c:(∃d:(c⋅d=b)→(c=S0∨∃a:(c=SS0⋅a)))

So as I read this, it means:

  For all numbers c,

       if there exists D such that B/C=D

       then C = 1

            OR there exists A such that C=2a

I'm having trouble understanding why B always must be a power of 2. First, I don't understand why B and D cannot be equal, where B and D are any number, and C is equal to 1. Second, I don't understand why B cannot be a number with a factor of 2 but which is not a power of 2, where C=2a and A=some number other than a power of 2.

I'm quite confused. I think I must be missing a contradiction or I must not understand how the quantifiers work.

Campbell Hutcheson
  • 205

1 Answers1

1

The sentence says that for any $c$, if $cd=b$ for some $d$, then either $c=1$ or $c$ is even.

To say that there is a $d$ such that $cd=b$ is to say that $c$ is a divisor of $b$. So the sentence says that all divisors of $b$ other than $1$ are even. For it says that if $c$ is a divisor of $b$ and $c\ne 1$, then there is an $a$ such that $2a=c$.

If $b\gt 1$ is not a power of $2$, then some odd prime $p$ divides $b$. Taking $c=p$ contradicts the condition that $c$ is even, Thus $b$ must be a power of $2$, and every power of $2$ has this property. (Note that $1$ is a power of $2$.)

André Nicolas
  • 507,029
  • I'm confused why I don't need to do the same thing for d? Like ∀c:(∃d:(c⋅d=b)→((c=S0∨∃a:(c=SS0⋅a)) and ∃e:(d=SS0*e)). – Campbell Hutcheson Sep 09 '14 at 05:06
  • 1
    We could have written a sentence that was more symmetrical in $c$ and $d$, using universal quantifiers for both $c$ and $d$. The resulting formula would be a little longer. The author chose not to treat $c$ and $d$ symmetrically. The part $\exists d(cd=b)$ just says that $c$ is a divisor of $b$. – André Nicolas Sep 09 '14 at 05:12