# Discrete Math: Recursive Functions

You are given the following recursive definition defining a set of strings. 1∈S; x∈S → x11∈S. What are the 4 shortest members of the set?

What does x11∈S mean?

-
Probably the concatenation of the string $x$ with the string "11". –  Trevor Wilson Nov 7 '13 at 18:26
so would the answer be {1,111}? –  user1045845 Nov 7 '13 at 18:37
If I understand correctly, those would be the two shortest members of the set. –  Trevor Wilson Nov 7 '13 at 18:38

The definition says that the string $1$ is in the set $S$, and if $x$ is any string in $S$, then so is the string $s11$ obtained by appending $11$ to $S$. Since $1\in S$, this rule implies that $111\in S$, which in turn implies that $11111\in S$, and so on. This already shows the three shortest elements of $S$, and it’s clear what the fourth shortest element will be.
One can prove, by the way, that $S$ is precisely the set of all strings consisting of an odd number of $1$’s. The