How to ensure uniqueness of readability of nested lists over some alphabet $S$?

Question

Here is something that has been bothering me. Let me just give an example to show what I mean. Consider the alphabet $\{a,b,c\}$. $(a,b,c)$ is a list from this alphabet. $(a,b,(a,b))$ is a nested list from this alphabet. However, here is the catch: Secretly, $c$ is actually equal to $(a,b)$. So now, there is some confusion as to whether $(a,b,c)$ is a regular list or a nested list. My question really is, given a set $S$ of symbols, how does one pass to an isomorphic copy $S'$ and work with nested lists over $S'$ rather than $S$ itself, so that confusions like that don't occur, and uniqueness of readability of nested lists is ensured? I am interested in such a set-theoretic construction of $S'$.

Answer 1

For operations on nested lists to be well-defined, you need a clear definition of what is a list and what isn't (or equivalently, what is an atomic element and what isn't). This criterion should be semantic as opposed to syntactic, so that it does not depend on how you refer to the object (e.g. as "$c$" vs. as "$(a,b)$").

In type theory and programming, we can use a sum type with a tagged union construct to establish the disjoint cases for atoms and sublists. The analogous construction in set theory is a disjoint union.

To flesh this out: we can recursively define a nested list over alphabet $S$ to be a tuple that has one of the following forms:

• $(0,a)$ where $a\in S$
• $(1,x_1,\dots,x_n)$ where each $x_i$ is a nested list over $S$.

The idea here is that we have tagged our objects to indicate whether they represent atoms or sub-lists in order to avoid any dependence on the internal structure of the elements of $S$. The shape $(a,b,(a,b))$ is represented by $(1,(0,a),(0,b),(1,(0,a),(0,b)))$, whereas the shape $(a,b,c)$ is represented by $(1,(0,a),(0,b),(0,c))$. Notice that these are different even if $c=(a,b)$, or even if $a,b,c$ happen to be nested lists themselves. The tags, not the letters, are what determine the nesting shape.