A set of certain lists - does it exist?

Question

Define a placeholder to be either an empty list $()$ or a list $(p q)$ of two placeholders $p$ and $q$. Does it exist a set of all placeholders? Of all finite placeholders?

---

My intention with placeholders is to abstract the structure of expressions in magmas: $(a\cdot ((b\cdot c)\cdot(d\cdot e)))\mapsto (()((()())(()())))$ where the empty lists replace all terms in the expressions. The number of atoms associated with a placeholder can be defined formally as: $|p|=1$ if p is a empty list and $|p|=|p^\prime |+|p^{\prime\prime}|$ if $\;p=(p^\prime p^{\prime\prime})$.

If $M$ is a magma and $|p|=n$, $p$ defines an obvious function $M^n\to M$ and the set of all placeholders is a magma itself with the multiplication $p_1\cdot p_2= (p_1 p_2)$.

The purpose is to study questions as in A simple question about rational numbers without a simple proof?

Answer 1

Yes, there is such a set. Furthermore, it is countable, and all placeholders are "finite" in the natural sense (i.e., they have finite rank as defined below). You can use the following basic pattern of definition by recursion to make precise any such definitions. Note that, in cases with only "finite branching", like yours, the definition @ThomasAndrews gave is equivalent and simpler. For any ordinal $\alpha$, define $P_\alpha$, the set of all placeholders of rank $\leq \alpha$, by recursion: $P_\alpha$ is comprised of:

• $()$, together with
• $(pq)$, for any placeholders $p$ and $q$ of rank strictly less than $\alpha$.

A priori, the collection of all placeholders is a class, since it is the collection of all placeholders of any ordinal rank. However, we can see in this (and similar) cases, that any placeholder must have finite rank. We proceed by transfinite induction on the rank. Assume we know that, for every placeholder of rank strictly less than $\alpha$, we know that the placeholder has finite rank, and consider any placeholder of rank $\leq \alpha$. If our placeholder is $()$, then it has rank 0, and we're done. If it is $(pq)$, we know that $p$ has some finite rank $n$ and $q$ has some finite rank $m$, so $(pq)$ has rank $\max(n,m) + 1$, which is finite. Therefore every placeholder actually has finite rank. This implies that the placeholders form a set, since we only need $\cup_{\alpha < \omega} P_\alpha$ to get them all. Finally, since it is an easy induction to see that each $P_n$ is finite for $n < \omega$, we can see that the set of placeholders is countable.

Answer 2

Sure. Let $X_0=\{()\}$ and let $X_{n+1}=X_n\cup\{ (pq)\mid p,q\in X_n\}$

Then $\bigcup_{n=0}^\infty X_n$ is the set you are seeking.

The number of such expression of length $2n$ is the $n-1$st Catalan number.

Answer 3

It's defined by ordinary recursion on $\mathbb{N}$, so it does exist.

Alternatively, as pointed out by coffeemath in the comments, you may also encode a placeholder as a finite sequence of open/close brackets $(, )$, and so once again there is a set of all placeholders (defined by subset selection on the set of all finite strings of brackets).

Answer 4

If you want to handle infinite structures, there are various ways to model that, though you have to make some deliberate choices about which kind of infinity you want -- for example, are the solutions to $x=(()x)$ and $y=(()(()y))$ to count as the same or different "placeholders"? Or are you going to have multiple different solutions to $x=(()x)$?

It is possible if you are too careless to end up with proper-class many placeholders, in which case there is of course no set of them. But usually you won't need such extravagance.

One common approach would be to represent a "placeholder" with the possible paths through it, where a path is a finite sequence of words over the alphabet $\{\mathtt{car},\mathtt{cdr}\}$. A path set $A$ represents a placeholder if it satisfies these conditions:

• $A$ is non-empty.
• $A$ is closed under prefixes: If $wu\in A$, then $w\in A$ too. (In particular the empty word is in $A$).
• If $w\in A$ then either $w.\mathtt{car}$ and $w.\mathtt{cdr}$ are both in $A$, or neither of them is.

This gives what Thomas Andrews described as "possibly infinite perfect binary trees".

Thus defined, the set of possibly infinite placeholders is the (unique, up to isomorphism) final coalgebra over the signature $\{\mathtt{nil}:\sigma, \mathtt{cons}:\sigma\times\sigma\to\sigma\}$ (that is, in more category-theoretic phrasing, the $\mathbf{Set}$-endofunctor that takes $X$ to $1\uplus X\times X$).