How does this answer for automata and Hamming distance not lead to inconsistencies?
Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it.

The transformed automaton generally works as follows:


The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet".
The state $(q, 1)$ means "the underlying automaton is in state $q$, and we have made a single error".
From any state $(q, 0)$, we can make the "correct" transition, or make any "incorrect" transition (a transition meant for any other symbol) and change the $0$ to a $1$.
From any state $(q, 1)$, we can only make the "correct" transition. In other words, once we've made one mistake, we can't make any more!
If we reach either $(a, 0)$ or $(a, 1)$, where $a$ is an accepting state, then we accept.


Hopefully this makes sense; let me know in the comments if it doesn't.

Now the key is, this works for any base automaton. So if we want $k=2$, we can just apply this transformation once, and then apply the transformation again!

The states now look like $((q, 0), 0)$. If we reach the state $((a, 1), 1)$, then we've made exactly two errors. And once we've made exactly two errors (there are no more zeroes to turn into ones), we're not allowed to make any more errors, we have to follow the base automaton exactly.

And then you can apply the transformation again for $k=3$, and again for $k=4$, and so on, for any natural $k$. Induction! QED.

(Another way to prove it is to allow errors in every state $(q, \psi)$ as long as $\psi &lt; k$. This way doesn't involve induction, and might be a bit easier to grasp, since you have a straightforward "error counter".)