Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

True or False?

  1. Apr 29, 2006 #1
    [tex]\begin{gathered}
    \forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\
    \exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \left\{ {0,1, \ldots ,p - 1} \right\} \hfill \\
    {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}
    {q}} \right)^k } \hfill \\
    \end{gathered} [/tex]
     
  2. jcsd
  3. Apr 29, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    As stated that looks trivially false. I am assuming that your bracket is the legndre/jacobi symbol, and if so it is plus or minus 1 (or zero), the a_i are a *subset* (sets cannot have repeated elements) of {0,..p-1}, and as such just picking r large will do. The largest that sum could possibly be is 1+2+..+p-1 = (p-1)(p-2)/2
     
  4. Apr 29, 2006 #3
    i think it's true because it's limited to the existential quantifier, and thus we can find at least one sequence of a's which are subset to p-1's.

    for example, p=2 q=1 n=2 r=a0+a1*2+a2*4, and thus r is natural, and you can find a combination where {a0,a1,a2} are subset of {0,1} like a0=a1=0 a2=1, etc.
     
  5. Apr 29, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    That is assuming that that symbol means the fraction p/q. As this was a number thoery thread I assumed differently.

    In anycase, it is still false as stated, and you cannot have the set {a0,a1,a1} as a subset of {0,1} the former has 3 elements the latter has two elements. Sets cannot have repeated elements. {0,0,1} is not a set. But almost certainly that is being too picky.

    Replace it with

    [tex] a_i \in \{0,..,p-1\}[/tex]

    perhaps.
     
    Last edited: Apr 29, 2006
  6. Apr 29, 2006 #5
    isn't the set {0,0,1} equivalent to {0,1}?

    p.s
    i know that repetition doesn't affect the set itself, but i didn't know it wasn't allowed.
     
  7. Apr 29, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    To be honest I forget these days, or rather I would avoid using such ambiguous notation as to avoid having to figure out what was meant. You could well be right.
     
  8. Apr 29, 2006 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    The question doesn't make too much sense, it confuses sequences and sets, repetition of elements and the cardinality is somewhat ambiguous. But however you meant it I think this will apply:


    Pretty trivial proof that it is true for r > 2, let p = q

    [tex]r = \sum_{k=0}^n a_k[/tex]

    In other words, given an element of the natrual numbers can it be represented by a sum of smaller numbers, e.g 1 + 2 = 3, 1 + 3 = 4. All you have to do is prove that inductively, which is pretty trivial.
     
  9. Apr 29, 2006 #8
    As Matt Grime pointed out, the way it's written, it isn't true (even if it is fractions). Let p=2, q=1, r=100. Then the coefficients a(i) are either 0, 1 or 2, and 100 = a(0) + a(1)*3/2 + a(2)*9/4 cannot be satisfied. It's written as for every p, q, and r.
     
  10. Apr 29, 2006 #9
    !Zurtex, in the original post, it clearly states "p > q > 0"

    You CANNOT have p=q
    ----------------------------------
    No!--it's just the fraction...p/q :redface:!

    WHere did you get the 3/2 & 9/4 ?? If p=2 and q=1, you will have a0*(2/1) + a1*(4/1) + ... etc!

    *Daveb, if p=2 and q=1, then p/q = 2 :wink:
    And in that case, any ai is either 0 or 1.

    But...let's take your example, where p=2, q=1, and r=100.
    The sequence {a0,a1,...,an} = {0,0,1,0,0,1,1}
    as
    0(1) + 0(2) + 1(4) + 0(8) + 0(16) + 1(32) + 1(64) = 100


    Or, take the example where p=3, q=2, and r=100, in which case any ai is indeed 0,1, or 2. The sequence {a0,a1,...,an} = {1,0,2,1,0,0,2,1,2}
    as
    1(1) + 0 + 2(3/2)2 + 1(3/2)3 + 0 + 0 + 2(3/2)6 + 1(3/2)7 + 2(3/2)8 = 100


    *Just one more example: let p=7, q=4, and r=23.
    The sequence {a0,a1,...,an} = {2,5,4}
    as
    [tex]2 + 5\left( {\frac{7}{4}} \right) + 4\left( {\frac{7}{4}} \right)^2 = 23 [/tex]

    Btw, q=1 and r ≤ p are just the trivially true cases.
    No problem! I'll rewrite this less ambiguously:

    [tex]\begin{gathered}
    \forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\
    \exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}\;{\text{where }}\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\
    {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}
    {q}} \right)^k } \hfill \\
    \end{gathered} [/tex]

    Now, true or false?
     
    Last edited: Apr 30, 2006
  11. Apr 30, 2006 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Why do you insist on writing the a_i as a set?

    [tex]\exists a_i, 0\leq i \leq n, a_i \in \{0,\ldots,p-1\}[/tex]
     
  12. Apr 30, 2006 #11
    I don't. I intend to write it as a finite sequence of integers, each of which is between 0 (zero) and p-1 inclusively. Doesn't {a0,a1,...,an} denote a finite sequence?

    *If not, how would you denote a finite sequence?
     
    Last edited: Apr 30, 2006
  13. Apr 30, 2006 #12
    See the second line of his post?
     
  14. Apr 30, 2006 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    [tex] (a_i)_{i=0}^{i=n}[/tex]

    is how you more formally write sequences: round brackets with the limits marked top and bottom, though it is not usually necessary.
     
  15. Apr 30, 2006 #14
    shouldn't they be curled brackets {}?
     
  16. Apr 30, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I wouldn't have thought so. Curly braces are reserved for sets, and sets are neither ordered, nor allow repetition, unlike sequences.
     
  17. Apr 30, 2006 #16

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    [tex] \{a_i \}_{i=0}^{n}[/tex] is sometimes used to denote an ordered sequence, though not always. Sometimes <> are used. Sometimes () are used. There's no universal notation here.
     
  18. Apr 30, 2006 #17

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Sorry, I mis-read that as p > 0 and q > 0.

    Trivial Proof 2

    n = 0
    p > q > r > 0
    a0=r

    Think you can complete the rest.
     
  19. Apr 30, 2006 #18
    That's what I meant to write...oops. As Matt pointed out, {...} is generally for sets, especially since you initially wrote it as one being a subset (rather than a sequnce) of the other. The way you rewrote it now makes more sense.
     
  20. May 1, 2006 #19
    Zurtex,
    I never said r MUST be less than p!
    Again, q=1 and r<p are just the trivially true cases!

    What about q > 1 and r > p ? :bugeye:

    Apparently not, but that's what I thought! :shy:
    Alright, I'll rewrite the statement again (hopefully for the last time! unless other problems with semantics occur):

    [tex]\begin{gathered}
    \forall p,q,r \in \mathbb{N}\,{\text{ where }} \, p > q > 0, \hfill \\
    \exists \left( {a_k } \right)_{k = 0}^n \,{\text{ where }}\,\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\
    {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}
    {q}} \right)^k } \hfill \\
    \end{gathered} [/tex]

    ~Now, true or false?
     
  21. May 1, 2006 #20

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    The question is still a little ill-posed, I'm not exactly sure what you want. Is the question:

    Can you generate any natural number r for every pair (p,q)?


    Edit: made a mistake, deleted it


    Your question seemed to me to be, can you generate a pair (p,q) to satisfy any given natural number r. Which I can prove in several trivial cases, and I 've shown the other question to be false with a trivial counter example, so what do you want?!?
    I never said you said that, however it is also trivially true in the case of:

    q = anything
    and
    p > r

    With a little more work that can be broadened a little to an easy proof (almost trivial) for:

    q= anything
    and
    p > r or p = r

    Hmm, I think I may of misunderstood you though, when you say: "q=1 and r<p" are you referring to 2 different cases? It really doesn't look like it, but it is also trivially true of the case of:

    q = 1
     
    Last edited: May 1, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: True or False?
  1. Explain true of false (Replies: 1)

  2. True or false ? (Replies: 1)

Loading...