# Correct notation or operator to remove elements from sequence

I'm currently using the following notation to denote a sequence (i.e. ordered list of elements):

$\langle x_n | x \in \mathbb{N} \rangle$

E.g. $S = \langle 1,3,5,7 \rangle$ and $S_2 = 3$

I know other notations exist, such as $\{S_k\}_{k\in\mathbb{N}}$ or $(S_k)$, but this doesn't really affect my following question.

What is the correct way to construct a new sequence from an existing sequence with some elements removed? I used to denote this as follows:

$S' = S \setminus \{1,5\} = \langle 3,7 \rangle$

But the set difference operator is not well-defined for a sequence and a set of elements. Since a sequence is commonly defined as a function $f:\mathbb{N} \mapsto E$ with $E$ the domain (set of elements which can be contained in the sequence), I was wondering if there is a better way to denote what I want to express here -- maybe there exists some operator I'm missing?

Thanks.

• Depending on what you need to represent, pseudocode might be clearer than trying to write it in math notation. – Mark S. Oct 27 at 21:16

If elements of $S$ are unique, then $S \setminus \{\ldots\}$ would be clear for me. If you define a sequence as $f : \mathbb{N} \to E$, then probably the easiest way to formally state your operation is as

$$(f \ominus g)(k) = M(0,0,k)$$ where $$M(a,b,k) = \begin{cases} M(a+1,b+1,k) &\text{if }f(a) = g(b) \\ M(a+1,b,k-1) &\text{if }f(a) \neq g(b) \land k > 0 \\ f(a) &\text{otherwise} \end{cases}$$

Note that here the you don't need $f$ to be injective, however, it is the left-most subsequence that matches $g$ that is removed.

Still, personally I would describe it using words for the sake of the reader. It is very rare that you need such a symbolic approach and keeping formalism to the necessary minimum often makes your text more approachable.

Hope that helps ;-)

• (The elements of $S$ are not necessarily unique.) Thanks -- I've made a few modifications, but your definition of $M(a,b,k)$ put me on the right track! – Macuyiko Mar 1 '13 at 14:15

I don't think there's a truly general standard notation. For the removal of single elements, I have sometimes seen the following notation:

$$(s_0, \ldots, \widehat{s_i}, \ldots, s_n),$$ meaning that the $i$-th element was removed.

The most general way would be to use sub-sequences: Define a sequence $i: \mathbb N \to \mathbb N$ that maps to the indices you want to keep, and write $s_{i_j}$.

• Thanks for the help -- I'll keep the hat notation in mind. Alas, it is more than a single element which has to be removed. – Macuyiko Mar 1 '13 at 14:16

Let $$f : \mathbb{N} \rightarrow A$$ be your original sequence and let $$K \subseteq \mathbb{N}$$ be the set of indices you want to keep. Then your new sequence $$f'$$ is

$$f' = f \circ g$$

where $$g : \mathbb{N} \rightarrow K$$ is the unique strictly increasing surjection from $$\mathbb{N}$$ to $$K$$.

$$g$$ being strictly increasing means it strictly preserves the order of indices:

$$\forall i \in \mathbb{N} : \forall j \in \mathbb{N} : i < j \rightarrow g(i) < g(j)$$

$$g$$ being surjective means every index in $$K$$ is mapped onto:

$$\forall k \in K : \exists i \in g : g(i) = k$$

These conditions together enforce uniqueness, since each index $$i \in \mathbb{N}$$ must be assigned to the smallest index $$k \in K$$ that has not been assigned to so far. If $$i$$ were assigned to an index larger than $$k$$, no index after $$i$$ could be assigned to $$k$$ due to the fact that $$g$$ is order-preserving, so $$k$$ would have to be skipped, making $$g$$ non-surjective.