Subtree definition confusion

154 Views Asked by At

Let $A$ be a finite prefix-closed set with operation $\cdot$ (so $A$ is a semigroup, "prefix-closed" means that if $x\cdot y\in A$, then $x\in A$ as well, it is not necessarily about strings, btw).

Consider the following set, which we call the subtree with root at the node $a$:

$B|_a=\{b\mid a\cdot b\in A\}$.

My question is: does this definition imply that:

$\forall a'=a\cdot b\in A\Rightarrow b\in B|_a$?

UPD, in other words, let us consider the following example:

let $A=\{1, 1\cdot 1,1\cdot 2,1\cdot 3\}$, consider $B|_1$. Will it be necessarily $\{1,2,3\}$, or it can be $\{1,2\}$ or $\{2,3\}$?

UPD-2: I expected that the answer is yes. But in this case, how I should properly describe/define the case when $B|_1$ can be $\{1,2\}$ as well?

2

There are 2 best solutions below

0
On BEST ANSWER

As I understand it, this is partially a notation question about set builder notation. If there is no specified set which the expression of the notation is iterating over (such as the positive integers in $\{x \in \mathbb Z_{>0}: x < 10\}$) the notation is frankly ambiguous.

So supposing there is some universal set $S$, this is how I read your definition of $B|_a$.

For a fixed $a$, for all $b$ in $S$, $b \in B|_a$ if and only if $a \cdot b \in A$.

So if $A=\{1, 1\cdot 1,1\cdot 2,1\cdot 3\}$, and $S = \{1,2,3\}$, then $B|_1$ will be precisely $\{1,2,3\}$.

The other part of your question, if you wish to describe a set $B'$ such that

For a fixed $a$, if $b \in B'$ then $a \cdot b \in A$.

You are then not defining a single set but a collection of sets. The property that defines them is $B' \subseteq B|_a$.

0
On

The definition of $B|_a$ is the set $\{b \mid a \cdot b \in A\}$. This is just set-builder notation which means that if $a \cdot b \in A$, then we have $b \in B|_a$, so the answer to your question is yes.

Hence, if $A = \{1, 1 \cdot 1, 1 \cdot 2, 1 \cdot 3\}$, then $B|_1 = \{1, 2, 3\}$.