10
$\begingroup$

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.

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

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Macuyiko
    Mar 1, 2013 at 14:16
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ (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! $\endgroup$
    – Macuyiko
    Mar 1, 2013 at 14:15
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .