Correct notation or operator to remove elements from sequence

Question

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} \rightarrow 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.

Answer 1

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}$.

Answer 2

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 ;-)

Answer 3

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.