If you've read Hofstadter's Gödel, Escher, Bach, you must have come across the problem of expressing 'b is a power of 2' in Typographical Number Theory. An alternative way to say this is that every divisor of b is a multiple of 2 or equal to 1. Here's my solution:
b:~Ea:Ea':Ea'':( ((a.a')=b) AND ~(a=(a''.SS0) OR a=S0) )
It is intended to mean: no divisor of b is odd or not equal to 1. E, AND and OR are to be replaced by the appropriate signs. Is my formula OK? If not, could you tell me my mistake?
Hofstadter's TNT: b is a power of 2 - is my formula doing what it is supposed to?
-
3I spelled out the abbreviations and added links. Please take into account that others may not be as familiar with things as you are and you can save a lot of readers a lot of time by investing a little bit of time just once in spelling out abbreviations and perhaps adding links. – 2012-01-31
-
0Thank you, it seems like I have a lot to learn :) – 2012-01-31
-
0For curious readers, it appears from the Wikipedia article that "Typographical Number Theory" is just Hofstadter's cutesy name for Peano Arithmetic, expressed in standard predicate calculus. – 2012-01-31
-
2@Rashi: Nicely done! Now, can you figure out how to express that 'n is a power of 10'? (It's a shame that Hofstadter doesn't devote some time to this, as it's IMHO one of the most fundamentally important notions in Peano Arithmetic!) – 2012-01-31
-
0@StevenStadnicki Thank you for the encouragement! I'm afraid the answer will be "I can't" but I will definitely try. – 2012-01-31
-
1@Rashi It is an inordinately hard problem - even being able to do the powers of 2 is quite an accomplishment! Powers of 10 require an entirely new approach, and I believe any explicit formula must be inordinately long. A hint to get you started: look up the notion of a _pairing function_, and codes for finite sequences... – 2012-01-31
4 Answers
Your idea is sound, but the particular formula you propose $$\neg\exists a:\exists a':\exists a'':( ((a\cdot a')=b) \land \neg (a=(a''\cdot SS0) \lor a=S0) )$$ does not quite express it. The problem is that the quantifier for $a''$ has too large scope -- what your formula says is that it will prevent $b$ from being a power of two if there is some even number that is different from some factor of $b$. For example, your formula claims that $2$ itself is not a power of two, because you can make $((a\cdot a')=2) \land \neg (a=(a''\cdot SS0) \lor a=S0)$ true by setting $a=2$, $a'=1$, $a''=42$. The first part is true because $2\cdot 1$ is indeed $2$, and the second (negated) part is true because it is neither the case that $2=42\cdot SS0$ nor $2=S0$.
What you want is $$\neg\exists a:\exists a':( ((a\cdot a')=b) \land \neg (\exists a'':(a=(a''\cdot SS0)) \lor a=S0) )$$ Moving the quantifier inside one negation switches the "burden of proof" -- now it says that there isn't any number that is half of $a$, rather than there is some number that isn't half of $a$.
Or perhaps more directly expressed: $$\forall c:\Big(\exists d:( c\cdot d = b )\to \big(c=S0 \lor \exists a:(c=SS0\cdot a)\big)\Big)$$
-
0I'm not sure TNT has the $\rightarrow$, but this still lets you rephrase by substituting $\neg X\lor Y$ for $X\rightarrow Y$. – 2012-01-31
-
0Yes, I stumbled upon that second formula while I was searching the internet, trying to find out if my solution was good. I can't deny it is much more straightforward and beautiful than mine, back when I was trying to solve the problem it didn't occur to me that I could use the _if-then_ relation. As of the position of the quatnifier for _a''_, I am afraid I don't understand how it changes the formula. Could you please explain me? – 2012-01-31
-
0@ThomasAndrews Yes, TNT does have the ->. (Sorry, I have yet to learn how to insert mathematical symbols) – 2012-01-31
-
0@Rashi, I have tried to add some more explanation. – 2012-01-31
-
0Thank you very, very much :) Now I understand. – 2012-01-31
I think more elegant is to assert that every prime divisor is two
$$\forall a:\forall c:(((SSa \cdot SSc=b) \land (\neg\exists d: \exists e:SSd \cdot SSe=SSa)))\to (a=0)) $$
-
0I suppose SSa denotes (SS0+a). In that case, this may not hold true. – 2015-01-29
-
1@EzhilV: $SSa$ denotes $S(S(a))$. (One can prove $SSa=SS0+a$, but the latter is a different expression). – 2015-01-29
-
0@HenningMakholm Thanks. I was not aware of that. I could not find it in Hofstadter's book. – 2015-01-30
Henning, above, got the correct way to phrase your answer.
Another approach is to phrase it as an implication: For all $a,a'$, if $b=a\cdot a'$ then $a$ is even or one. This can then be expressed as:
$$\forall a:\forall a': \neg(b=a\cdot a') \lor (a=S0) \lor (\exists a'': a = a''\cdot SS0)$$
The advantage to this formulation is that there is one fewer negative. (You need to realize that the phrase "$X$ implies $Y$" is equivalent to $\neg X \lor Y$.)
I would express this as follows using the original notation: $$ \forall c:\forall d: \mathtt{\sim} b=(S(Sc \cdot SS0) \cdot d) $$ Or equivalently $$ \mathtt{\sim} \exists c:\exists d: b=(S(Sc \cdot SS0) \cdot d) $$ Please note that negation in the first formula applies to the whole equality and that the negation in the second formula applies to the whole formula.
From Fundamental Theorem of Arithmetic we know that power of two cannot have divisors other than two. This is exactly what we are using in the formulas above where $S(Sc \cdot SS0)$ stands for $2c+1, c>0$, i.e. any odd number greater than $1$. $Sc$ is used in $S(Sc \cdot SS0)$ in order to avoid the situation when $c=0$ and $d=b$ used in formula $S(c \cdot SS0)$ turn the equality into $b=b$ for any $b$.
These formulas detect all the powers starting from $2^0, 2^1, 2^2, \ldots$