# 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$?

• The indices can be denoted $n_1< n_2<n_3\cdots$; so, $\{ s_{n_i}\}_{i=1}^\infty$. – David Mitra Dec 14 '11 at 9:22
• I'd write $S' \subseteq S$. – Peteris Dec 14 '11 at 11:31
• @Peteris That's subset notation. Sets are unordered so this fails the "ordered" requirement. – ApproachingDarknessFish Sep 24 '16 at 23:11
• @ApproachingDarknessFish It's definitely an abuse of notation, but there's lots of times people will use $\subset$ to denote "a subset with all the proper structure", e.g., subgroup, subring, subcategory, etc. – Duncan Ramage Dec 19 '17 at 21:51
• This Q about notation was asked here before, but I don't recall the title. – DanielWainfleet Dec 20 '17 at 3:52

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.

• The first two links don't appear to address the question I think is being asked, but the third idea is an interesting one. Using $\mid$ makes a nice connection between a subsequence and a divisor. – dbx Dec 20 '17 at 5:16

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.

• I'm sorry but this answer is missing the point. Yes, you can play games with the indices of the sequential elements but the question is: How do we use notation to indicate that one sequence is a subsequence of another? Surely there is a reasonable, and reasonably well used binary relation to say: $(x_{n_k}) \stackrel{\tiny\mbox{subsequence}}{\prec} (x_n)$. – dbx Dec 20 '17 at 17:02
• So, I indicate this notation, which is what the question asks for. How exactly does this miss the point? – user370967 Dec 20 '17 at 21:41
• The question is not: given a sequence $(a_n)$, how do I denote a subsequence of it? The question is: given two sequences, one of which is a subsequence of the other, what is the notation for that relationship? – dbx Dec 21 '17 at 0:34
• Isn't a strictly increasing function on the indices a good relationship? I think I'm indeed missing the point.. – user370967 Dec 21 '17 at 5:52
• Well, we don't have to say "$A$ is a subset of "$X$", we can use the notation $A\subseteq X$". What can we write instead of "$(a_n)$ is a subsequence of $(x_n)$"? If the answer involves an increasing function of $n$ then it's not a good solution. – dbx Dec 21 '17 at 13:34

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.

• Why do you suggest $\subset$ with an arrow under it? And unfortunately, $\hookrightarrow$ already has a job in real analysis. – dbx Dec 23 '17 at 13:14
• Yes, $\hookrightarrow$ is already used for other reasons. I have edited my answer with a picture of my suggestion. It's just the $\subset$ symbol with an added arrow-tip. The intuitive reason could be this: the $\subset$ notation just indicates inclusion. The added arrow-tip could indicate inclusion in a particular fixed order, which is essentially what we mean by an ordered subset. The idea is quite similar to that of an embedding. – VENKITESH Dec 23 '17 at 15:18
• Yes, you're right - a subsequence is essentially an embedding with respect to the sequential ordering. This is a good start! – dbx Dec 23 '17 at 19:04
• $\stackrel{\large\subset}{\rightharpoondown}$ – dbx Dec 23 '17 at 19:10
• Yeah, your symbol also does the job quite well. No need to create a new symbol. However, its a good idea to get some new symbols into LaTeX, if they are intuitive and serve some purpose in making the writing easier. – VENKITESH Dec 24 '17 at 5:03

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.

Before introducing the subsequence notation, here is a definition of a sequence that is suitable for many mathematical investigations (c.f. with this wikipedia link):

A sequence is a function whose domain is either $\{n \ge 0 \; | \; n \in \mathbb Z\}$ or $\{n \gt 0 \; | \; n \in \mathbb Z\}$.

Although sequences are a type of function, they are usually distinguished notationally from functions in that the input is written as a subscript rather than in parentheses, i.e. $a_n$ rather than $f(n)$. There are terminological differences as well: the value of a sequence at the input $1$ (or $0$ - depends on the domain) is called the "first term" (or first element) of the sequence, the value at $2$ is called the "second term", etc. Also, while a function abstracted from its input is usually denoted by a single letter, e.g. $f$, a sequence abstracted from its input is usually written by a notation such as ${\displaystyle (a_{n})_{n\in \mathbb N}}$, or just as ${\displaystyle (a_{n})}$. Here $\mathbb N$ is the domain, or 'index set', of the sequence.

Here is a definition of a subsequence (c.f. with this wikipedia link):

A subsequence of a given sequence is a sequence formed from the given sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. For instance, the sequence of positive even integers $(2, 4, 6, ...)$ is a subsequence of the positive integers $(1, 2, 3, ...)$. The positions of some elements change when other elements are deleted. However, the relative positions are preserved.

Formally, a subsequence of the sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ is any sequence of the form ${\displaystyle (a_{n_{k}})_{k\in \mathbb {N} }}$, where ${\displaystyle (n_{k})_{k\in \mathbb {N} }}$ is a strictly increasing sequence of positive integers.

Example: $S = (1/1,\, 1/2,\, 1/3,\, \dots)$ is a sequence and $S^{'} = (1/1,\, 1/4,\, 1/9,\, 1/16,\, \dots)$ is a subsequence. Do you want to get more formal?

$S = (s_1,\, s_2,\, s_3,\, \dots)$ with $s_n = 1/n$.

The strictly increasing sequence $n_k = k^2$ of numbers can be used to extract a subsequence of $S$:

${S^{'}} = {\displaystyle (s_{n_{k}})_{k\ge 1}} = (\frac{1}{k^2})_{k \ge 1} = ({s^{'}}_1, \, {s^{'}}_2, \,{s^{'}}_3, \, \dots)$ with ${s^{'}}_k = \frac{1}{k^2}$.

Many times an acceptable way of describing a subsequence setup is to simply use, say, the English language. For example,

Every subsequence of $(1/n)_{n \ge 1}$ converges to $0$.

• I'm sorry but these answers are mostly missing the point. Yes, we can say that $S'$ is a subsequence of $S$. How do we notate it? – dbx Dec 20 '17 at 17:00
• As I tried to indicate at the end of my post, and as far as I can tell, besides the ${\displaystyle (a_{n_{k}})_{k\in \mathbb {N} }}$ type claims, a notation is not necessary or really useful - doesn't pay dividends. Just state the fact when writing down the math - it is good 'good enuf'. If any theory made progress with some notation I don't know about it. Most likely it would not be useful in a real analysis course. Also, do we want to start using $S' | S$ if it can't be used in calculations? – CopyPasteIt Dec 20 '17 at 17:11
• Obviously I disagree that it wouldn't be useful. I think it would be quite useful in the context of a real analysis course, specifically! What does your final comment about "using $\mid$ in calculations" mean? – dbx Dec 20 '17 at 17:24
• A good notation is one that can be manipulated in an intuitive way leading to verifiable mathematical results. A great accomplishment in math is Leibniz's notation for calculus. Perhaps a new invention, a notation for subsequences can be found, the manipulation of which adds new insights and is useful. A notation would also be useful if it would help students understand what a subsequence is. But it is doubtful in my mind that a student with motivation/talent would need it. The concept of a subsequence would not be a roadblock to their further progress. – CopyPasteIt Dec 20 '17 at 18:00
• Yea, an just ran into this math.stackexchange.com/questions/397978/… - reading the statement in English can give you a headache! – CopyPasteIt Dec 24 '17 at 2:21

If somebody asked me to design new notation to denote that some (finite or infinite) sequences are subsequences of some other sequences I would do it in this way:

I will not go here into definition(s) of what exactly means that some sequence is a subsequence of some other sequence, because good information about that is contained in answers already posted. I will just state this notation of mine.

If some sequence $s$ is a subsequence of some sequence $r$ then I would denote that relation(ship) as $s \subseteq_o r$, where little $o$ tells us that we are dealing with ordered sets.

The fact that some (unordered) set $S$ is a subset of some other (unordered) set $R$ could then be denoted either as usual $S \subseteq R$, or like this: $S \subseteq_u R$, where little $u$ tells us that we are dealing here with ordinary (unordered) sets.

There are other facts that can be written about all of this, but they are mostly trivial so I will not write about them here and now, but will conclude this answer in a hope that you could like this approach here which is extremely simple.

• I do like this approach; what I've been using is $\subseteq$ already, so it feels natural to start with that symbol. – dbx Dec 20 '17 at 19:20

I appreciate all the effort and attention put into this question in the last week. Unfortunately, the answer seems to be "there is no such standard notation". Some interesting ideas were generated nonetheless!

Given a metric space $X$, let me for now use the notation $S(X)$ for the set of all sequences $a=(a_n)_{n\in\mathbb{N}}$ that take values in $X$. There have been some suggestions for a notation that resembles the inclusion of sets, but since the relation of being an (ordered) subsequence also introduces a partial ordering on $S(X)$, let us investigate as to whether it would be useful to emphasise this fact by using a symbol like $a\unlhd b$, $a \lesssim b$ or $a \ll b$. Let me stick with the first one.

• If $b$ converges and $a\unlhd b$, then also $a$ converges. This is feels natural, is true, but rather trivial.
• If $a$ does not converge and $a\unlhd b$, then $b$ also cannot converge. Same here, natural but trivial.
• The notation also calls for a sandwich theorem: If $a$ and $c$ converge to $x$ and $a\unlhd b\unlhd c$ , then so does $b$. Well, that's nothing new.
• The way we use subsequences most often is as follows: Assume $b$ assumes values in a compact set, then there exists a convergent $a\unlhd b$. I do like the notation here, because it suggests the following thought: If we have some control over $b$, we can make it a little smaller and get a convergent sequence.
• For a map $f\colon X \rightarrow Y$ we have that $a\unlhd b$ implies $f(a) \unlhd f(b)$, that's also trivial.

That are the first scenarios that come to my mind in which I want to think of $\unlhd$ as an ordering. However I do not think that students would really benefit from the notation, as most things I've just mentioned are rather trivial. So why introduce a new notation?

Moreover there also lies some danger in using an ordering symbol. Everything looks nice, when we write sequences as simple letteres $a$. But often we rather write $a=(a_n)_{n\in\mathbb{N}}$ and especially if we stick with $n$ all the time, the expression $$(a_n)_n \unlhd (b_n)_n$$ suggests that there is a pointwise comparison à la $a_n \le b_n$, which is at best meaningless and wrong at worst.

All in all, I don't think that introducing a new symbol would make anything clearer or easier. As has been mentioned several times in the thread before, plain English sometimes works best.