# help with sequence prefixes

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• May 21st 2011, 12:43 PM
Sneaky
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.
• May 21st 2011, 12:58 PM
emakarov
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?
• May 21st 2011, 01:08 PM
Plato
Quote:

Originally Posted by Sneaky
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.
• May 21st 2011, 03:17 PM
Sneaky
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.
• May 21st 2011, 03:23 PM
emakarov
Still have to ask the same question:
Quote:

Originally Posted by emakarov
What does it mean, by definition, for one sequence to be a subset of another?

• May 21st 2011, 03:30 PM
Sneaky
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.
• May 21st 2011, 03:31 PM
Plato
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.
• May 21st 2011, 03:44 PM
Sneaky
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?

--------------------------------------------------------------------------------------------------
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>
• May 21st 2011, 03:49 PM
emakarov
Let σ = {<1,1>} and τ = {<0,0>, <1,1>}. Then σ ⊆ τ, but σ is not a prefix of τ.

On the other hand, σ ⊆ τ iff σ is a subsequence of τ.
• May 21st 2011, 04:25 PM
Sneaky
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?
• May 21st 2011, 04:28 PM
emakarov
Sorry, by <0,0> I meant an ordered pair, which is an element of a function. I did not mean it as a sequence.
• May 21st 2011, 04:35 PM
Sneaky
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.
• May 21st 2011, 04:41 PM
emakarov
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.
• May 21st 2011, 04:51 PM
Sneaky
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?
• May 21st 2011, 05:01 PM
emakarov
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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last