1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Clive Newstead Apr 20 '17 at 2:42
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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