# Tuple-builder notation

For some function $f : \mathbb{N} \to S$, is there a concise (and preferably established) way to build tuples from sets $A\subset \mathbb{N}$ of the values they map to in $S$? The exact order of the tuple doesn't really matter, as long as it preserves some ordering.

An example is in place. Let $A = \{1, 5, 6\}$, I'm looking for a way to express the $|A|$-tuple $(f(1), f(5), f(6))$. The tuple $(f(5), f(6), f(1))$ is equally acceptable, but the (multi)set $\{f(1), f(5), f(6)\}$ would not do.

If we see tuples as nested ordered pairs $(a_1, a_2, \cdots, a_n) \equiv (a_1, (a_2, \cdots, a_n))$ with $(a_i)\equiv (a_i, \emptyset)$, I'm essentially looking for notation for the function:

$$g(f, A) = \left\{\begin{array}{ll} \emptyset & \text{if } A = \emptyset, \\ (f(\min A), g(A \setminus \min A)) & \text{else}. \end{array}\right.$$

I'm tempted to use notation parallel to the set-builder, i.e., $(f(x) : x \in A)$ but that doesn't really convey that the ordering matter.

Edit to clarify the order requirement: The order of the tuple doesn't matter at all, but it matters that it is ordered. In other words, for $f : \mathbb{N} \to S$ and $h : \mathbb{N} \to S$, I want the following property of the notation:

$$(f(x) : x \in A) = (h(x) : x \in A) \iff \forall x \in A, f(x) = h(x).$$

Obviously, this property holds for any ordering as long as it only depends on $A$. But it doesn't really feel that $(f(x) : x \in A)$ conveys that.

• I'm confused by your question: you say $(f(5), f(6), f(1))$ is just as acceptable as $(f(1), f(5), f(6))$, but later you say that $(f(x) : x \in A)$ is not sufficient because it doesn't convey ordering. Can you clarify? – Clive Newstead Apr 20 '17 at 2:42

Given $A \subseteq \mathbb{N}$, define $\ell_n(A) \in \mathbb{N}$ for $n < |A|$ inductively by $$\ell_0(A) = \mathrm{min}(A) \quad \text{and} \quad \ell_n(A) = \mathrm{min} \Big(A \setminus \{ \ell_0(A), \dots, \ell_{n-1}(A) \}\Big) \text{ for all } 0 < n < a$$ Thus the sequence $(\ell_n(A) \mid n < |A|)$ lists the elements of $A$ in increasing order.

Given a function $f : \mathbb{N} \to S$ and a subset $A \subseteq \mathbb{N}$, the sequence you seek is therefore $$\big( f(\ell_n(A)) \mid n < |A| \big)$$

Note that this definition is valid even when $A$ is empty, in which case it produces the empty sequence, and when $A$ is infinite, in which case it produces an infinite sequence of elements of $S$.

Normally, for a general index set $A$, we encode $A$-indexed tuples as functions with domain $A$.

For example, (the encoding of) an $A$-indexed tuple of elements of $S$ would then be the same thing as be a function $A \to S$. In your example, the tuple you're looking for is encoded as the restriction $f|_A$.

It is not uncommon to use sequence notation for tuples; e.g. you might write the tuple as $\{ f(a) \}_{a \in A}$ to refer to the entire $A$-indexed sequence.

Note this is often even done with $n$-tuples, taking the index set to be $\{0, 1, \ldots, n-1\}$ (or $\{1, 2, \ldots, n \}$ if $1$-up indexing is preferred)

Also note that the index set isn't required to be a subset of integers, ordered, or even countable.

If $A$ is countable (but not finite), then we can order its elements and form a sequence (whose elements are not repeated), i.e., there exists a bijection $\varphi: \mathbb{N} \to A$.

An "infinite tuple" is essentially a same as a sequence (i.e. a function $T$ whose domain is $\mathbb{N}$) so we can define it by simply composing $\varphi$ and $f$:

$$T(n) = f(\varphi(n)).$$