Printable View
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.
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?
Please give definitions of the terms in this question.Quote:
Originally Posted by Sneaky
Do you mean subsequence and not subset?
I have never seen the term "prefix" in any context regarding sequences.
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.
Still have to ask the same question:
Quote:
Originally Posted by emakarov
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.
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.
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>
Let σ = {<1,1>} and τ = {<0,0>, <1,1>}. Then σ ⊆ τ, but σ is not a prefix of τ.
On the other hand, σ ⊆ τ iff σ is a subsequence of τ.
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?
Sorry, by <0,0> I meant an ordered pair, which is an element of a function. I did not mean it as a sequence.
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.
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.
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?
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.