Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A short preface:

I'm reading the book Godel Esher Bach: Eternal Golden Braid, it describes a system which it calls Typographic Number Theory. There is a question in the book that asks to represent a statement "b is a power of two" in terms of TNT. You will probably recognize the operations of TNT at once, so I'll not spend much time describing it, only what's relevant.

Here's the formula I came up with (and the interpretation, in case I've got the formula wrong):

$$ \forall{a}\forall{b}\exists{c}\forall{d}\exists{e}:<<(b=Scc)\land\lnot(b*d=a)>\land(a=e*SS0)> $$

The $<$ and $>$ symbols are used to delimit the logic expressions. $S$ stands for successor of, so $S0$ is 1, $SS0$ is 2 and so on. $Sx$ is a successor of $x$ whatever $x$ is.

In plain language, the formula above is meant to say: "whatever $b$ is, given it is a sum of any two $c$ and one (that is if $b$ is odd) it is not the case that it multiplied with any number $d$ can produce $a$ (does not divide $a$). Yet there have to be such number $e$ which if multiplied by two will produce $a$ ($a$ is even).

I'm not pretending to have any academic background, so please excuse me if the formulation is poor!

share|improve this question
1  
Since every integer $>1$ has a unique factorization into primes, and every prime $>2$ is odd, it follows that any number $>1$ with no odd divisors $>1$ has only $2$ in its prime factorization, thus is a power of two. –  Jaycob Coleman Sep 29 '13 at 8:14
    
Right on, Jaycob Coleman! –  Robert Lewis Sep 29 '13 at 8:18
    
That is a good answer @JaycobColeman –  Don Larynx Sep 29 '13 at 8:22
    
@JaycobColeman yay! Thanks a lot! You probably could post it as an answer so I could accept it. –  wvxvw Sep 29 '13 at 8:22
    
Why are you using $<$ and $>$ as parentheses? –  Git Gud Sep 29 '13 at 8:26

2 Answers 2

up vote 7 down vote accepted

Since every integer $>1$ has a unique factorization into primes, and every prime $>2$ is odd, it follows that any number $>1$ with no odd divisors $>1$ has only $2$ in its prime factorization, thus is a power of two.

Someone else could probably give something in more formal language and whatnot, but whatever floats your boat!

share|improve this answer

You do not state "$b$ is a power of two". In fact your statement does not have a free variable at all. Also $Scc$ is not even well-formed. On the other hand, your idea to rewrite "$b$ is a power of two" as "all divisors $>1$ of $b$ are even" is fine.

share|improve this answer
    
Yeah, thanks, I'd have to work on that. Sure $Scc$ was meant to be $S(c+c)$. –  wvxvw Sep 29 '13 at 8:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.