“Smallest set” term in the trees set definition

Question

I often meet such kind of the definition of the set of trees, as:

The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a\in\Sigma$ and $w\in T^*$, $a(w)$ is in $T$. (http://dl.acm.org/citation.cfm?id=2101368)

One question that I can not generally understand is: how does this definition prevent from the string, say "$a)($", appear in the set $T$?

Would somebody be so kind explain me this point?

And please, if you are going to downvote this question, be so kind explain why are you doing that.

Answer 1

I think that is trivial according to the rule of how the strings are formed: $a(w)$. But if you need a formal proof then you could prove it as following using induction on the length of strings in $T$.

Assume $t \in T$ and lets call such strings "well-structured", those which do not look like "$a)($".

Base case: $t = a()$ where $a \in \Sigma$. Clearly it is well-structured.

Induction: assume that all strings in $T$ of length $n$ is well structured. Then we form a new string by taking a string $w$, a symbol $a$ from $\Sigma$ and concatenate them using parenthesis as $a(w)$ which is well-structured since $w$ is well-structured too.

Answer 2

The set of unranked $Σ$-trees, denoted by $T$, is the smallest set of strings over $Σ$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a∈Σ$ and $w∈T^∗$, $a(w)$ is in $T$.

What we have here is an inductive definition. The base case is implicit because $\epsilon \in T^*$ even if $T = \emptyset$; making is explicit, the definition is (reading $a$ as free variable):

$\qquad\begin{align*} &\ \phantom{\implies}\ a() \in T \\ w \in T^+ &\implies a(w) \in T \end{align*}$

The term "smallest set" is established, but somewhat silly, since all these sets are infinite; we mean the minimal set. Formally speaking, it's the smallest fixed point of this inductive definition; see here and here for some more on that.

As for you question, imagine this definition unfolding in an infinite process:

• $a \in T \implies a(a) \in T$.
• $a(a) \in T \implies a(a(a)) \in T$.
• ... and so on...

All you can ever do is wrap things in parentheses; thus you can never creates mismatching pairs like you propose.

A formal proof would be an induction along the inductive definition, of course!

1. Base case: all alphabet symbols have matching parentheses.
2. Inductive step: taking elements of $T$ with matching parentheses, those that are "one step larger" have matching parentheses as well.

Answer 3

You have to prove that $a)($ doesn't belong to $T$. You can start with constructing $T$, as follows. Let $T_0 = \emptyset$, and for $n \in \mathbb{N}$, define $$ T_{n+1} = \bigcup_{a \in \Sigma} \bigcup_{m \in \mathbb{N}} \{ a(t_1 \ldots t_m) : t_1,\ldots,t_m \in T_n \}. $$ I claim that $$ T = \bigcup_{n \in \mathbb{N}} T_n. $$ Indeed, you can prove by induction on $n$ that $T_n \subseteq T$. Conversely, suppose that $t_1,\ldots,t_m \in \bigcup_{n \in \mathbb{N}} T_n$. Then there exists $N$ such that $t_1,\ldots,t_m \in T_N$, and so $a(t_1\ldots t_m) \in T_{N+1} \in \bigcup_{n \in \mathbb{N}} T_n$ for all $a \in \Sigma$. This shows that $T \subseteq \bigcup_{n \in \mathbb{N}} T_n$, since the latter satisfies the conditions in the definition of $T$.

Now you can prove that $a)( \notin T$ by proving inductively that $a)( \notin T_n$ for any $n \in \mathbb{N}$. The proof is quite simple: $a)( \notin T_0$ since $T_0$ is empty, and $a)( \notin T_{n+1}$ for any $n \in \mathbb{N}$ since all strings in $T_{n+1}$ start with $b($ for some $b \in \Sigma$.

Answer 4

This use of the phrase "smallest set", or "smallest set with respect to inclusion" is generally taken to be synonymous with "the intersection of all sets satisfying this criterion" (as long as intersection preserves satisfaction of the criterion). So "smallest" here means "is a subset of every set satisfying this criterion". Consequently, no proper subset of this set can satisfy the given criterion. I.e., this set is minimal with respect to the partial ordering $\subseteq$ of sets.

Example: Let $G$ be a group and let $S$ be a subset of $G$. The normal closure of $S$ is the smallest normal subgroup of $G$ which contains $S$. Equivalently, (since we have an elementary lemma that the intersection of normal subgroups is a normal subgroup), the normal closure is the intersection of all the normal subgroups of $G$ which contain $S$. This immediately shows that any proper subgroup, normal in $G$, of the normal closure of $S$ cannot contain all of $S$, so the normal closure is smallest with respect to (set) inclusion.

Answer 5

There are sets $T$ that satisfy the condition given (for each $a \in \Sigma$ and $w \in T^*$, $a(w) \in T$) which do contain badly-structured trees like $a)($; however, there is also a set that doesn't contain any of these badly-structured trees. All of the sets that contain badly-structured trees also contain all the well-structured trees, so the set that contains only the well-structured trees is the smallest such set.