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

$\endgroup$
  • $\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 at 21: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$
  • $\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 '13 at 14:15
3
$\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$
  • $\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 '13 at 14:16
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.