1
$\begingroup$

I am reading some notes and having trouble understanding the following example:

Let $F$ be a finite set of size $q$, where $q ≥ 2$. Let $n$ be an integer, where $n ≥ 2$. For a subset $X ⊆ F^n$ of words over $F$ of length $n$, and for $k ∈ \{1, 2, . . . , n\}$, we define $X(k)$ to be the set of $k$th components of words in $X$, and we define the set desc$(X)$ of descendants of $X$ by desc$(X) = X(1) × X(2) × · · · × X(n).$

For example, if $X = \{0000, 0111, 0012\}$ then $X(1) = \{0\}, X(2) = X(3) = \{0, 1\}, X(4) = \{0, 1, 2\}$ and desc($X$) is the following set of words: $\{0000, 0100, 0010, 0110, 0001, 0101, 0011, 0111, 0002, 0102, 0012, 0112\}$.

I know that the descendants of $X$ is also defined as the set of new words that could be produced by a coalition of pirates who posses all the words in $X$. In the example above I can't see how we know $X(1) = \{0\}$ etc? Or then how we desc($X$) is the following set of words: $\{0000, 0100, 0010, 0110, 0001, 0101, 0011, 0111, 0002, 0102, 0012, 0112\}$? For example, how is it that we know that $0111$ is in the set but $1111$ is not?

$\endgroup$
  • $\begingroup$ is my answer clear? $\endgroup$ – kodlu Apr 23 '17 at 21:39
1
$\begingroup$

Note that there are two words in $F$ which disagree on the $k^{th}$ coordinate if and only if $|X(k)|>1.$

All three words in $F$ have $0$ as their first symbol so $X(1)=\{0\}.$

Thus all descendants have 0 in their first coordinate.

By definition of the direct product $\times,$ the descendants are formed by entering all elements of $X(1)$ in the first coordinate, those of $X(2)$ in the second coordinate, etc.

$\endgroup$

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.