The Infinite Regularity Proof

In this proof, we will show that regularity is not only possible, but inevitable.

			
				1.  Let R be a regular language.
				2.  Then R is a subset of the language { w ∈ Σ* | w is in R ∪ {a}}
				3.  By definition, R = {a} ∪ (R \ {a})
				4.  By induction, R = {a, a, a, ...}
				5.  Therefore, R is regular.
			
		

Corollary: The Regularity Inevitability Theorem

By the previous proof, all languages are regular.

• More on Regularity
• Infinite Regressions