Discrete Math: Recursive Functions

Question

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?

Answer 1

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