Re: Enderton 3.3 Problem 5

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.

Re: Enderton 3.3 Problem 5

Quote:

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.

If a sequence number were defined $\displaystyle a=<a_0,\ldots, a_m>$ for $\displaystyle a_k \in \{0,1\}$ and $\displaystyle 0 \leq k \leq m$, I think it still holds the properties of a sequence number you mentioned. This is not the same as a sequence number in the #1 post for $\displaystyle a_k \in \mathbb{N}$ and $\displaystyle 0 \leq k \leq m$.

What am I confused with?

Thanks.

Re: Enderton 3.3 Problem 5

A sequence where all elements are 0 or 1 is a special case of a general sequence, so yes, codes of such sequences have the properties from post #2. However, to characterize only 0-1 sequences one has to stipulate in addition that if i > 0 and p^i divides n then i <= 2.

Re: Enderton 3.3 Problem 5

Quote:

Originally Posted by

**emakarov** A sequence where all elements are 0 or 1 is a special case of a general sequence, so yes, codes of such sequences have the properties from post #2. However, to characterize only 0-1 sequences one has to stipulate in addition that if i > 0 and p^i divides n then i <= 2.

$\displaystyle p^i$ for $\displaystyle i \neq 1$ is no more a prime number. So I think the definition of a set of sequence numbers you mentioned does not apply for this case.

Re: Enderton 3.3 Problem 5

Quote:

Originally Posted by

**logics** $\displaystyle p^i$ for $\displaystyle i \neq 1$ is no more a prime number.

Yes, but did I claim it is?

Quote:

Originally Posted by

**logics** So I think the definition of a set of sequence numbers you mentioned does not apply for this case.

Could you give a counterexample, i.e., a number that satisfies the following property but is not a sequence number or vice versa?

Quote:

Originally Posted by

**emakarov** 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.

Re: Enderton 3.3 Problem 5

Quote:

Originally Posted by

**emakarov** Yes, but did I claim it is?

Could you give a counterexample, i.e., a number that satisfies the following property but is not a sequence number or vice versa?

What I have not understood is that $\displaystyle p^i$ for $\displaystyle i \neq 1$ is not relevant to a prime divisor in the #2 post. So why do we have to stipulate it for 0-1 sequences as mentioned in the #4 post?

A set of 0-1 sequence numbers satisfies the definition in the #2 post, so a set of 0-1 sequence numbers are the same with a set of N-sequence numbers according to the #2 post, but it is clearly not.

What am I missing?

Thanks.

Re: Enderton 3.3 Problem 5

I am not sure I understand your difficulty. Let's say an integer n is even if n = 2k for some integer k. Each number in the set $\displaystyle \{4k\mid k\in\mathbb{Z}\}$ satisfies the property from the definition of even numbers, but this does not mean that $\displaystyle \{4k\mid k\in\mathbb{Z}\}$ is the set of even numbers. To have n = 4k for some k one has to require that n is even *and* in addition that n/2 is even.

Similarly, n is a sequence number iff there exists a number m <= n (the greatest prime divisor of n) such that for all prime p, p | n iff p <= m. Also, n is a sequence number encoding a 0-1 sequence iff in addition to the requirement above, for every prime divisor p of n, p^i | n iff i = 1 or i = 2.