# Proving existence results

I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:

(i) For all x ∈ A, |x| ≤ 5.

(ii) Every DFA that decides A has more than 8 states.

To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}* that holds both of these properties?

• Yes, a given example proves that there is such an language. Does this answer your question? – John L. Feb 8 '19 at 4:47

1. Use a probabilistic argument. If you choose a uniformly random graph on $$n$$ vertices, then it will have no large clique or independent set. We don't know how to construct such graphs explicitly.
2. Use a non-constructive argument. The is an algorithm that given $$n$$, determines whether the decimal expansion of $$\pi$$ contains a block of $$n$$ zeroes. Indeed, such a program either always returns YES, or it returns whether $$n \leq N$$, where $$N$$ is the longest such stretch of zeroes. While we do not at the moment know which of the two options is correct, one of them must be correct, and so the algorithm exists.
3. Use a proof by compactness. Consider the problem of determining whether a graph can be embedded into a torus (without edge crossings). This is a minor-closed family of graphs, and we can consider the set of forbidden minors, i.e., minimal graphs (with respect to the minor relation) not embeddable into a torus. This is an antichain of graphs (with respect to the minor relation), so according to the graph minor theorem, it must be finite. Since we can test whether a graph on $$n$$ vertices has a given graph as a minor in time $$O(n^2)$$, it follows that we can determine whether a graph is embeddable in a torus in time $$O(n^2)$$. But we can't actually construct the algorithm, so we don't know the complete list of forbidden minors.