Regular Languages and Model Theory 8: The Word Logic

The most exciting thing about the regular languages are their expressive equivalences to various logical languages! In this video I introduce the Word Structure (words on {a,b} with a prefix relation, an equal-length relation, and "tack an a onto the end" and "tack a b onto the end") and prove that its first order logic is expressively equivalent to the regular languages.

Finding a source for this theorem has been quite tricky. J.W. Thatcher's "Decision Problems for Multiple Successor Arithmetics" cites this as coming from a letter from Shepherdson to C. C. Elgot in 1959.

I made a video about nonstandard models of this logic previously:    • Really Long Words  , but I hope to make a more detailed video on the topic later in this series.

If you have questions or something didn't make sense to you, please let me know in the comments below.