# Traitor tracing - determining a set of codewords

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?

• is my answer clear? – kodlu Apr 23 '17 at 21:39

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