7
$\begingroup$

Is there any formal notation for dealing with lists, rather than sets?

e.g. if I have a set $X=\{x_1,\dots,x_n\}$ and I want to add a new item to the set, say $x_{n+1}$, I can say "Let $X = X \cup \{x_{n+1}\}$" and it is clearly understood that I want to add $x_{n+1}$ to my set.

However, if $X$ is not a set but rather a list, or tuple (i.e. the elements are ordered and duplicates are allowed), is there any way of indicating that I am adding an element to the end of the list?

e.g. given $X=(x_1,\dots,x_n)$, how do I say add an element to $X$ such that $X=(x_1,\dots,x_n,x_{n+1})$? i.e. how do I formally denote appending an element to $X$?

  • 0
    Also, I purposefully didn't use the word "appending" because I thought _that_ was programming lingo :-P2011-05-05

3 Answers 3

3

What you call a list is formally known as sequence. There was a question which symbol is for sequence concatenation. Unfortunately there is no accepted answer. Symbols , (commentator actually used u2322, "frown" symbol but it's resisting my attempt to copy it) and are mentioned in comments.

According the Wikipedia article is an operator for concatenation of numbers (doesn't specify which set of numbers, probably ℕ) but doesn't say much about sequences. The same symbol is in my opinion more commonly used for parallelism so it may confuse the reader.

I haven't seen symbol before but commentators agree about it.

2

I don't think there is any standard notation.

One alternative would be to not use $(a,b)$ for ordered pairs but $a \times b$, which is the notation suggested by category theory. The $\times$ allows you to sweep lots of assocativity isomorphisms under the rug: it looks perfectly natural to write $(a \times b) \times c = a \times (b \times c) = a \times b \times c$, but not $((a,b),c) = (a,(b,c)) = (a,b,c)$.

Then if you have an $n$-tuple $x$ in $X^n$, you can write $x \times a$ for the $(n+1)$-tuple in $X^{n+1}$ obtained by appending $a$.

0

In addition to the answers mentioned above, I would like to stress that any list can be expressed as a set.

Formally, we can define a list to be a function, where the domain is a subset of the natural numbers. We can then express the function as a set of ordered pairs $(x,y)$, where $x$ is the input and $y$ is the output of the function.

Using this approach has the upshot that you retain all of the neat set notation and the reader will be familiar with the notation used in your work. On the other hand, the notation is a little (but not overwhelmingly) clunky.

As an example, if we have a list $$ of real numbers, this corresponds to a function $f:\{1,...,n\}\rightarrow\mathbb{R},$ where $f(1) = y_{1}$, etc. We could then represent this list as the set $Y =\{\hspace{3pt}(x,f(x)):x\in \{1,...,n\} \hspace{3pt}\}.$

Consequently, to append an element to $Y$, we could consider $Y\cup \{(n+1,y_{n+1})\}$

To remove the clutter from this approach, we can then slightly abuse notation by defining

$S\cup \{y_{n+1}\} = S\cup \{(n+1,y_{n+1})\}.$