Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.