The span of a set of binary strings S is the set of strings which can be formed by \oplus ing some of them together. In other words, \operatorname{span}(S)=\left\{\bigoplus_{s \in T} s: T \subseteq S\right\}. Let \operatorname{dim}(S)=\log _{2}(|\operatorname{span}(S)|)
Show that, if t \in \operatorname{span}(S), then \operatorname{dim}(S \cup\{t\})=\operatorname{dim}(S); otherwise, if t \notin \operatorname{span}(S), then \operatorname{dim}(S \cup\{t\})= \operatorname{dim}(S)+1. Also show that, if S contains enough packets for Bob to decode all her original messages, then \operatorname{dim}(S)=n.