Better Know A Theorem: Languages

01May07

I’m grouping together these two short theorems because they deal with languages.

Formal Languages

Q: What is special about the following list of primes (in base 10)?

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049.

A: Given any prime number, you can delete some of its digits to get one of the above primes. You can prove this with A Theorem That Should Be Better Known about well-quasi-ordering; see also Minimal primes by J. Shallit.

English and French Languages

Q: Do the differences between English and French really warrant the division of a country?

A: The languages are both trivial! (and hence equal.) The paper Quotients Homophones des Groupes Libres / Homophonic Quotients of Free Groups is a nicely written short proof of this humourous fact.



No Responses Yet to “Better Know A Theorem: Languages”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: