Originally Posted by

**emakarov** All natural numbers are products of primes. What sets sequence numbers apart is that they are divisible by *all* prime numbers below a certain limit. So n is a sequence number iff there exists a p <= n such that all prime divisors of n are <= p and all prime numbers <= p divide n. One has to show that prime(x) and divide(x,y) are representable relations. Also, importantly, all the quantifiers involved can be bounded by n. If we are trying to decide whether n is a sequence number, we need to look only at numbers <= n to see if they divide n, if they are prime, etc. By the theorem on slide 15, formulas built using bounded quantifiers are numeralwise determined, so one only has to show that the formula *defines* the required relation.

I realize that this is somewhat complicated, so don't hesitate to ask more questions.