Notation for a subsequence of a sequence

If we have a sequence (an ordered list)

$$ S=(s_0,s_1,...,s_n). $$

What is the notation for expressing that $S'$ is a (ordered) subsequence of $S$?

Solution 1:

Here is a handout on sequences that manages to avoid the problem by stating the definition of a subsequence and then simply stating that one is a subsequence of another each time. This, however, does not seem to be what one would like to do.

Here instead is a is another handout by Dr. Carryn Bellomo Warren at University of Nevada, Las Vegas. This uses and explains the notation that David Mitra. $$S'=(x_{n_{k}})_{n \in N} \ \ \text{for} \ n_1< n_2<n_3\cdots$$

And if you want to denote this just with the $S'$, from Structural Additive Theory, by David J. Grynkiewicz, we find the notation of defining a subsequence $S' | S$, where $S$ is a sequence. He also notes in his book that "All notation and conventions for [unordered] sequences extend naturally to ordered sequences."

Hopefully you are now convinced that this notation is relatively well used, and you should be able to find plenty more examples of this by searching online for "sequences notation". One thing to note is that oftentimes these curly brackets {} will be substituted for parentheses (), such as here, or in Mitra's comment itself.

Solution 2:

Let $k: \mathbb {N} \to \mathbb {N} $ be a strictly increasing function. Let $(x_n)_n $ be a sequence. Then the sequence $(y_n)_n $ defined by $y_n := x_{k (n)} $ is called a subsequence.

So, you can always write $(x_{k (n)})_n $ for a subsequence of the given sequence $(x_n)_n $

This notation is commonly used, and is very intuitive.

Solution 3:

For sets, we have $S'\subseteq S$. For ordered sets, it will be best to have $\subset$ with an arrow at the bottom end. The closest notation available to this in LaTeX is \hookrightarrow which looks like this $\hookrightarrow$. So we can denote $S'\hookrightarrow S$. But if this is not satisfying, then there are also ways to draw and implement your own symbols in LaTeX, using PSTricks, TikZ and so on. Just surf a bit on the Net about designing symbols for LaTeX.

I am adding my idea of the symbol, drawn in MS Paint. If you like it, you could figure out how to implement it in LaTeX.

Solution 4:

Let me give a foundational reference in support of the notation "$|$" suggested by Isaac Browne. Since you are apparently dealing with finite sequences of elements of some set $A$, every such sequence defines a word of the free monoid $A^*$. Thus subsequences are exactly the subwords as studied in [2]. Lothaire says that a word $u$ divides a word $v$ (notation $u | v$) if $u$ is a subword of $v$.

Let me just mention a key result in this area, known as Higman's lemma [1]: if the alphabet is finite, then the division ordering is a well partial order.

[1] Higman, Graham (1952), "Ordering by divisibility in abstract algebras", Proceedings of the London Mathematical Society, (3), 2 (7): 326–336.

[2] J. Sakarovitch and I. Simon, Subwords. In M. Lothaire: Combinatorics on Words, Chapter 6, Addison-Wesley, Reading, Mass. (1983), reprinted in 1997 at Cambridge University Press.