Ambiguity in ordered tuples

Question

I hope this question is not too elementary for math overflow… My knowledge on set theory is very sketchy so it will seem very simple to a working mathematician

It’s a subtle thing I only realized today: construction of free groups. The standard construction gets equivalence class of all words over a set X. Let X={a,b,c,(a,b)}. Now the words of X is the union of all the X^n for all natural numbers n. Consider the word ((a,b),c). Is it an ordered pair in X^2 or ordered triple in X^3? Of course it’s both, and that’s where the problem is. In constructing the map that shows the free group has the universal property, we pick elements out of each equivalence class (which are words), and then multiply the image of the letters in the words. But where exactly does ((a,b),c) get mapped to, if we want to factorize the function X -> integers defined by a,b,c->1 and (a,b)->10?

If ((a,b),c) is considered as a pair, it goes to 10. If considered as a triple, it goes to 1. So the mapping is ambiguous. This gets worse of course, since an 100-tuple is a 99-tuple, 98-tuple… and so has 100 different values it might get mapped to.

Answer 1

This has nothing to do with ordered tuples but rather with unions and disjoint unions.

You should use the disjoint union of all the $X^n$, not their union. Actually, to be quite precise, let $X$ be the set of generators. Then the carrier of the free group $F(X)$ generated by $X$ consists of the disjoint union $$F(X) = \coprod_{n \geq 0} (X + X)^n.$$ There are two copies of $X$ because we want generators as well as their inverses. The disjoint union is the coproduct in terms of category theory. Concretely, in set theory we may define $$A + B = \lbrace (0,x) \mid x \in A\rbrace \cup \lbrace (1,y) \mid y \in B\rbrace$$ and $$\coprod_{i \in I} A_i = \lbrace (i, x) \mid i \in I, x \in A_i\rbrace.$$ In your example this would mean that each word is explicitly tagged by its size.

If you use ordinary union then, as you rightly observe, there may be some overlap between $X^n$ and $X^m$ for $n \neq m$.

Let me just point out that it is a shame that students are not properly educated about the importance of disjoint unions. Very often I see mathematicians pretend that two sets are disjoint when they obviously are not, just because they feel uneasy about using a disjoint union. This question is a fine example of the ensuing confusion.

Answer 2

The usual formal definition of $X^n$, the collection of $n$-tuples over $X$, is the set of functions from $n$ to $X$, that is, the set of functions from the $n$-element set $\{0,1,\ldots,n-1\}$ ` to $X$. More generally, $B^A$ is the set of functions from $A$ to $B$.

With this definition, there is no ambiguity. In particular, your tuple $((a,b),c)$ is a 2-tuple whose first element is (a,b) and whose second element is c. Your confusion results from using a vague concatenation concept of tuple, which works fine as long as none of the elements of $X$ are themselves tuples. But in the general case, the strict definition resolves any ambiguities.

Let me point out that a similar issue arises already with $1$-tuples. The strict definittion distinguishes between the elements of $X$ and their corresponding $1$-tuples, that is, the sequences over $X$ of length $1$. Specifically, having a single object of $X$ is different than having a sequence of $1$ object from $X$. In most contexts, one can safely ignore this issue, and identify an individual symbol $a$ with the sequence having just the symbol $a$ in it. But in the cases where the generating set contains elements that are themselves sequences, as in your case, there would be ambuity in this identification as you mentioned, but it is resolved by the formal definition.

In particular, in the strict definition, the sets $X^n$ are already disjoint, and so the collection of all finite tuples is in fact already the disjoint union of them.