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.

  • $\begingroup$ What is $T^*$? Closure of $T$ or another tree? $\endgroup$ – fade2black Jul 22 '17 at 17:34
  • $\begingroup$ I have just given the definition from the paper. I think $T^*$ is a set of all possible unranked trees $\endgroup$ – Andrey Lebedev Jul 22 '17 at 17:56
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 22 '17 at 21:11
  • $\begingroup$ I daresay that we have the Kleene star here. Every node can have arbitrarily many children. $\endgroup$ – Raphael Jul 22 '17 at 21:11

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.

  • $\begingroup$ What about "smallest-ness" of this set? I assumed that we deal with some power set of set of strings over the alphabet $\Sigma$... $\endgroup$ – Andrey Lebedev Jul 22 '17 at 18:01

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.
  • $\begingroup$ Thank you @Raphael. I was baffled by this smallest set and considered the set of strings over $\Sigma$ as set of all possible strings (because mathematically smallest set implies operation with supersets). I could not realise that it is simply inductive description. So if there wouldn't be this term smallest, everything would be much clear. $\endgroup$ – Andrey Lebedev Jul 22 '17 at 21:43
  • $\begingroup$ @AndreyLebedev $T = \Sigma$ would be small(est), but it wouldn't satisfy the condition that if $w \in T^*$ then $a(w) \in T$. $\endgroup$ – Raphael Jul 23 '17 at 10:20

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

  • $\begingroup$ What about "smallest-ness" of this set? I assumed that we deal with some power set of set of strings over the alphabet $\Sigma$... $\endgroup$ – Andrey Lebedev Jul 22 '17 at 18:02
  • $\begingroup$ just want to thank you for your answer. It happens sometimes that one doesn't see obvious things. I was baffled by the "smallest set" term in the definition, while it appears all very simple. $\endgroup$ – Andrey Lebedev Jul 23 '17 at 10:27
  • $\begingroup$ The "smallest set" is the intersection of all sets satisfying the condition. $\endgroup$ – Yuval Filmus Jul 23 '17 at 17:27

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.

  • $\begingroup$ I fully agree with you!!! I was thinking about it too, but since I didn't understand what "the smallest" is meant precisely by the OP, I didn't make any assumptions or guesses to avoid confusions and misinterpretations. $\endgroup$ – fade2black Jul 23 '17 at 3:57

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.


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.