とりあえず有限長の語の集合が無限集合になりうることくらいは理解してくれ。
証明が無限を扱うことと、証明長が有限なことは全然別の話。
プログラムにしても同様。