Page 1 of 2 12 LastLast
Results 1 to 15 of 25

Math Help - help with sequence prefixes

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    help with sequence prefixes

    Suppose sigma and tau are arbitrary sequences over some set A.
    Is it true that sigma is a subset of tau if and only if sigma is a prefix of tau?

    I want to show a counter example sigma is a prefix of tau but not a subset, but I don't understand how that is possible? If something is a prefix than its exists in the other, so it has to be a subset.

    I could show something is a subset but not a prefix, but I don't know how to show an example of a subset with sequences. I can show it for sets.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    What does it mean, by definition, for one sequence to be a subset of another? A sequence can be considered as a function from (an initial segment of) natural numbers. In this case, do you compare images of such functions, or do you compare functions themselves as sets of pairs?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,392
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by Sneaky View Post
    Suppose sigma and tau are arbitrary sequences over some set A. Is it true that sigma is a subset of tau if and only if sigma is a prefix of tau?
    Please give definitions of the terms in this question.
    Do you mean subsequence and not subset?
    I have never seen the term "prefix" in any context regarding sequences.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    From the text i have a prefix for sequences means e.x. <1,2,3> is a prefix of <1,2,3,4>.

    If a sequence is <1,2,3> then its function form is {(0,1),(1,2),(2,3)}.
    No I mean a subset not subsequence. The symbol is a 'C' with a horizontal line under.

    And I can't come up with an example of sigma being a subset of tau but not being a prefix of tau. Can I get a hint on this one?
    It seems to me that if sigma is a subset or prefix of tau, then its also prefix or subset respectively.
    Last edited by Sneaky; May 21st 2011 at 03:27 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Still have to ask the same question:
    Quote Originally Posted by emakarov View Post
    What does it mean, by definition, for one sequence to be a subset of another?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    I thought it meant, that all the elements of the function form of sequence sigma has to be in the function form of the sequence tau.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,392
    Thanks
    1476
    Awards
    1
    And I still have to ask: How are you using the word sequence?
    Please as both of our questions.
    It seems to be that we are reading meanings into your question that are not what you mean at all.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Ok let me type the whole question

    Formally, a sequence is a special kind of function, a function is a special kind of relation, and a relation is a special kind of set. Thus, ultimately a sequence is some sort of a set. Given two sequences, then, it makes perfect sense to ask whether one is a subset of the other. Is the subset relationship between sequences (viewed as sets) the same as either the sub-sequence or prefix relationship? In other words, suppose sigma and tau are arbitrary sequences over some set A.

    Is it true that sigma is a subset (C with a line under) of tau iff sigma is a prefix of tau?
    Justify your answer.


    --------------------------------------------------------------------------------------------------
    In the text (not from this question) it says sequence sigma is a prefix of sequence tau if
    1) sigma is finite and there is a sequence sigma' s.t. sigma () sigma' = tau
    or
    2) sigma is infinite sigma=tau. If sigma is a prefix of tau, but not equal, then sigma is a proper prefix of tau.

    For example <a,b,c> is a prefix (in fact a proper prefix) of <a,b,c,d>
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Let σ = {<1,1>} and τ = {<0,0>, <1,1>}. Then σ ⊆ τ, but σ is not a prefix of τ.

    On the other hand, σ ⊆ τ iff σ is a subsequence of τ.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    I don't understand, why tau is equal to a set of sequences, doesn't the question say its supposed to be a sequence itself?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Sorry, by <0,0> I meant an ordered pair, which is an element of a function. I did not mean it as a sequence.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    How can the function form of sigma be {<1,1>} (since you said 'Sorry, by <0,0> I meant an ordered pair')
    shouldn't <0,0> be in there as well? because the first element should have a 0 in the left side.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Ah, OK, if sequences as functions have to be defined on an initial segment of natural numbers (starting with 0), then being a subset implies being a prefix.

    Edit: and vice versa.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Now I am confused with your previous statement with the example, so that still shows that its a subset but not a prefix? Or does there have to be a <0,0> in sigma, which then makes the example false?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    This depends on the definition of a sequence. If the domain of a sequence is required to be {0, ..., n} for some n, then sigma is not a sequence. In any case, sigma is a subset of tau.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: July 4th 2010, 12:05 PM
  2. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  3. sequence membership and sequence builder operators
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 4th 2009, 03:16 AM
  4. Replies: 12
    Last Post: November 15th 2006, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum