# Does there exist an infinite set of binary strings $S$ such that no element of $S$ contains any other element of $S$ as a proper substring.

A binary string $a$ (of length $n\geq0$) is a finite sequence $(a_1,\ldots,a_n)$, with $a_i\in\{0,1\}$. We write this as $a=a_1\cdots a_n$. If the length is zero we write the binary string as $\varepsilon$. The concatenation of two binary strings $a=a_1\cdots a_n$ and $b=b_1\cdots b_m$ is defined to be $ab=a_1\cdots a_n\cdot b_1\cdots b_m$.

A binary string $a$ is said to be a substring of $b$, if there exist binary strings $x,y$ such that $b=xay$. We say $a$ is a proper substring of $b$ if $a\neq b$ and $a$ is a substring of $b$.

Does there exist an infinite set $S$ of binary strings such that for all $a,b\in S$, $a$ is not a proper substring of $b$?

• what have you looked at so far ? – user451844 Jul 7 '17 at 2:22

$101,1001,10001,100001, \dots$