Results 1 to 8 of 8

Math Help - Enderton 3.3 Problem 5

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.3 Problem 5

    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).
    ================================================== ===========
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.3 Problem 5

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.3 Problem 5

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Enderton 3.3 Problem 5

    Quote Originally Posted by logics View Post
    p^i for i \neq 1 is no more a prime number.
    Yes, but did I claim it is?

    Quote Originally Posted by logics View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.3 Problem 5

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    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 \{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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton Problem 3.5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 5th 2012, 11:49 AM
  2. Enderton 3.5 Problem 1
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 27th 2011, 10:59 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum