I have a very simple question with regards to the notation of sequences. To illustrate the question, consider the following pseudo-code:

procedure fun(P):
// input $P = \langle p_0,\ldots,p_{n-1}\rangle$
if $P == \langle \rangle$ return;
for all $p_i \in P$
fun($\langle p_i,\ldots,p_{n-1}\rangle$);

That is, the variable $P$ denotes a sequence of elements, where order matters.

  1. Now the question is, can I check for an empty sequence like in the if statement ($P == \langle \rangle$)? If this is correct, do you still prefer another notation, e.g., $P == \emptyset$?

  2. Is the call fun($\langle p_i,\ldots,p_{n-1}\rangle$) correct? or should I use something like e.g., fun($P \setminus \langle p_i \rangle$)? Is the latter correct at all, i.e., can I use the set notation with sequence, but instead of curly braces used angled braces, like $P \setminus \langle p_i \rangle$?

Thank you in advance

  • $\begingroup$ Well, then how do I express that statement using sequences, as $P$ for me is a sequence not a set? I.e., how do I express $P\setminus \{p_i\}$ for sequences. $\endgroup$ – 3.14 Nov 25 '16 at 15:44
  • $\begingroup$ $P\setminus \{p_i\} $ means "set-minus": the **set** $P$ without the subset $\{p_i\}$. I don't think you mean to say that, even allowing for angled brackets instead of curly ones. Unless otherwise noted, a set is not assumed to be ordered. Take set $A = \{ 0, 1, 2, 3\} = \{2, 1, 3, 0\}$. It sounds, perhaps, that you want a partially ordered set, but then you need to designate how to compare the $p_i's$ $\endgroup$ – Namaste Nov 25 '16 at 15:52
  • $\begingroup$ What is it you want to express with $P\setminus \langle p_i \rangle$? $\endgroup$ – Namaste Nov 25 '16 at 15:53
  • $\begingroup$ With $P \setminus \langle p_i \rangle$ I want to express that I have extracted the element $p_i$ from $P$, and now $P$ has one element less (removed $p_i$). Since you're saying that my expression is incorrect, then how to correctly express it for sequences? $\endgroup$ – 3.14 Nov 25 '16 at 15:56
  • $\begingroup$ The backslash is customarily used in math to mean to identify a set, but also exclude any of its elements that share elements with the excluded set, So $A\setminus B$ excludes all elements in $A\cap B$. $\endgroup$ – Namaste Nov 25 '16 at 15:59

Somewhat awkwardly, there is a lack of universally agreed notational conventions for sequences. To circumvent this problem, I would recommend that you express a sequence as a set.

In particular, we can represent a sequence as a function, whose domain is a subset of the natural numbers. Additionally, a function is a sets of ordered pairs $(x,y)$, where $x$ is the input and $y$ is the output. By expressing a list as a set, we can apply the relevant notation for sets and would allow the reader to work with more familiar notation.

In sum, to answer both of your questions, by recasting the sequence as a set $P$, you can then make mathematically correct statements of the form $P == \emptyset$ and $P \setminus \{p_{i}\}$.


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.