Proving that Every Full Prefix-Free Language is Maximal
Suppose that $A$ is a full prefix-free language, that is,
$$
\sum_{x \in A} 2^{-|x|} = 1.
$$
Assume, for the sake of contradiction, that $A$ is not maximal. Then there is a word $y$ such that $A \cup \{y\}$ is also prefix-free. According to Kraft's inequality,
$$
\sum_{x \in A \cup \{y\}} 2^{-|x|} \leq 1.
$$
However, this implies that
$$
1 \geq \sum_{x \in A} 2^{-|x|} + 2^{-|y|} = 1 + 2^{-|y|} &gt; 1,
$$
and so we reach a contradiction. This shows that $A$ is maximal.



The more interesting direction is the converse: if $A$ is maximal then $A$ is full. Let me give two proofs of this fact.

The first proof is by induction on the length of the maximal word in $A$ (note that if $A$ is maximal then it cannot be empty). If $A = \{\epsilon\}$ then $A$ is indeed full. Now suppose that $A$ contains some word of positive length. Since $A$ is prefix-free, $\epsilon \notin A$. Hence we can write
$$
A = \{ 0x : x \in A_0 \} \cup \{ 1x : x \in A_1 \},
$$
where $A_0,A_1$ are prefix-free, and have shorter maximal words. It is easy to check that $A_0,A_1$ are maximal: for example, if $A_0 \cup \{y\}$ were prefix-free, then $A \cup \{0y\}$ would be prefix-free. Applying the induction hypothesis, we see that
$$
\sum_{x \in A} 2^{-|x|} = \sum_{x \in A_0} 2^{-|0x|} + \sum_{x \in A_1} 2^{-|1x|} = \frac{1}{2} \sum_{x \in A_0} 2^{-|x|} + \frac{1}{2} \sum_{x \in A_1} 2^{-|x|} = \frac{1}{2} + \frac{1}{2} = 1.
$$

The second proof uses a probabilistic argument, though for the sake of presentation I will present it as a counting argument. Let $A$ be a prefix-free code which is not maximal, and let $n$ be the length of the maximal word in $A$. For a word $x$ of length at most $n$, let $B_n(x)$ denote all words of length $n$ of which $x$ is a prefix, and note that $|B_n(x)| = 2^{n-|x|}$. Since $A$ is prefix-free, the sets $B_n(x)$ for $x \in A$ are all disjoint. Therefore
$$
\left| \bigcup_{x \in A} B_n(x) \right| = \sum_{x \in A} |B_n(x)| = \sum_{x \in A} 2^{n-|x|} = 2^n \sum_{x \in A} 2^{-|x|} &lt; 2^n.
$$
Therefore there is some word $w$ of length $n$ which has no word in $A$ as a prefix. So $A \cup \{w\}$ is also prefix-free, and we conclude that $A$ is not maximal.



Both proofs we presented above actually show the following stronger fact: every prefix-free code is a subset of a maximal prefix-free code. Let me quickly outline how to obtain this result using both proofs.

In the first proof, we prove the claim by induction. If $A = \emptyset$ then we can extend it to $A = \{\epsilon\}$, and if $A = \{\epsilon\}$ then $A$ is already maximal. So suppose that $A = 0A_0 \cup 1A_1$. The induction hypothesis shows how to extend $A_0,A_1$ to maximal prefix-free codes $B_0,B_1$ (respectively), and then $B = 0B_0 \cup 1B_1$ is maximal.

In the second proof, we obtain a maximal prefix-free code by adding to $A$ all words in
$$
\overline{\bigcup_{x \in A} B_n(x)}.
$$

In both proofs, one way to check that the extended code is maximal is by verifying that it is full.



For extra credit, the reader can try extending the ideas above to infinite prefix-free codes, that is, prefix-free codes containing countably many words.