Enderton 3.3 Problem 5

**logics** · December 18th 2011, 04:35 AM

Show that the set of sequence numbers is representable (catalog item 10).

================================================== ==========

Necessary definitions for this problem are shown in the below link, especially, slide 21 and 22.

http://cs.nyu.edu/courses/fall03/G22...c/lec11_h4.pdf

The way how to encode a finite sequence of numbers into a single number is defined as

$<a_{0}, \ldots, a_{m}> = p_{0}^{a_0+1}\ldots p_m^{a_m+1}=\prod_{i \leq m}p_i^{a_i+1}$ , where $p_a$ is the $(a+1)$ st prime(e.g., $p_0=2, p_1=3, p_2 = 5, p_3= 7, p_4=11, \ldots$ ).
================================================== ===========

**emakarov** · December 18th 2011, 10:24 AM

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.

**logics** · December 19th 2011, 04:23 AM

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 $a=<a_0,\ldots, a_m>$ for $a_k \in \{0,1\}$ and $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 $a_k \in \mathbb{N}$ and $0 \leq k \leq m$ .

What am I confused with?

Thanks.

**emakarov** · December 19th 2011, 04:35 AM

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.

**logics** · December 19th 2011, 05:12 AM

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.

$p^i$ for $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.

**emakarov** · December 19th 2011, 05:52 AM

Originally Posted by logics

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

Yes, but did I claim it is?

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?

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.

**logics** · December 19th 2011, 07:17 AM

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 $p^i$ for $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.

**emakarov** · December 19th 2011, 07:34 AM

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 $\{4k\mid k\in\mathbb{Z}\}$ satisfies the property from the definition of even numbers, but this does not mean that $\{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.

Thread: Enderton 3.3 Problem 5

LinkBack

Thread Tools

Display

Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Re: Enderton 3.3 Problem 5

Similar Math Help Forum Discussions

Enderton Problem 3.5

Enderton 3.5 Problem 1

Enderton 3.3 Problem 8

Enderton 3.1 problem 1 (p.193)

Enderton 3.1 Problem 6 (p. 193)

Search Tags