I am having problems proving the following:
A sequence $S$ only consisting of $1$'s and $0$'s is called 'non-stuttering' if there exists no segment in $S$ that repeats three times (e.g. $00101101$ is non-stuttering, but $110010010011$ is because '$100$' is repeating three times) Suppose that for any $n \in \mathbb{N}$ there exists a sequence that is non-stuttering. Prove that there exists an infinite sequence $\hat{S}$ that is non-stuttering.
I want to prove this using König's Lemma but I am not sure how to apply it. Let $T$ be the rooted tree of all non-stuttering sequences where every node has at maximum two children ($1$ and $0$). My idea is that on every node $t_n$ there has to be a child of $t_n$ with infinitely many descendants because for every $n \in \mathbb{N}$ there excists such a sequence. But this doesn't quite add up. Because isn't there a possibility that i.e. I am looking at $t_3$ and I know there has to exist a $t_4$ somewhere. But how can I tell that it is a child of $t_3$? Couldn't it be that I chose a wrong path at $t_2$ so that I could get a non-stuttering sequence of length $3$ but not of lenght $4$?
I am quite confused at the moment and an explanation would be much appreciated!
The useful thing about Konig's lemma is exactly that it gets you out of the situation you describe. You're essentially trying to build a path (= infinite non-stuttering sequence) directly; with Konig, you can avoid this entirely.
We do this as follows. The crucial fact is:
This means that the set of finite non-stuttering sequences of $0$s and $1$s forms a tree! Now, a non-stuttering sequence of length $n$ corresponds to a node of height $n$ on this tree - given that there is such a sequence for each $n$, what does this tell you about the cardinality of $T$? (Konig's lemma then gets you the existence of a path.)
In fact, a general principle is true: if $P$ is a property of finite or infinite binary strings which is closed under initial segments - that is, if $\sigma\prec\tau$ and $\tau$ has $P$, then $\sigma$ has $P$ - then the following are equivalent:
There is a sequence of length $n$ with property $P$, for each $n\in\mathbb{N}$.
There is an infinite sequence such that each finite initial segment has property $P$.
The direction bottom-to-top is proved by "cutting off" an infinite sequence at a given length, and the top-to-bottom direction uses Konig's lemma exactly as above.
Usually we're interested in "continuous" properties - ones which hold of an infinite string iff they hold of each of its finite initial segments. Non-stuttering is a continuous property; "finite", however, isn't. Continuity in this sense can be generalized beyond the natural numbers, by consider more complicated infinite ordinals; a property of ordinal-indexed sequences is continuous if for all limit ordinals $\lambda$, a length-$\lambda$ sequence has the property iff all its strict initial segments have that property.