Timeline for Set-theoretic foundations for formal language theory?
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 25, 2011 at 22:51 | comment | added | Not Mike | There is a certain degree of circularity, but only on the surface. This is because no formal language can reason or express itself with any meaning. For example, as soon as you try to collect all the codes for true statements about a particular universe, you have just stepped up the consistency strength of the system you are working in. A related construction is called $0^{\sharp}$, and a quick description of it is here en.wikipedia.org/wiki/Zero_sharp . (Of course I'm blurring the fine details a bit, but this is the gist.) | |
| Jul 25, 2011 at 22:21 | answer | added | Rex Butler | timeline score: 1 | |
| Jan 18, 2010 at 16:11 | comment | added | Harry Gindi | Making waves in a cup of tea? That's the first time I've ever heard that expression before.. But I like it. | |
| Jan 18, 2010 at 15:36 | vote | accept | Anthony de Almeida Lopes | ||
| Jan 18, 2010 at 15:31 | answer | added | Mariano Suárez-Álvarez | timeline score: 7 | |
| Jan 18, 2010 at 15:22 | vote | accept | Anthony de Almeida Lopes | ||
| Jan 18, 2010 at 15:36 | |||||
| Jan 18, 2010 at 15:06 | comment | added | Anthony de Almeida Lopes | Mariano Suárez-Alvarez: I agree. It's trivial, but I'm still curious. Thank you for your suggestion. | |
| Jan 18, 2010 at 15:06 | answer | added | Neel Krishnaswami | timeline score: 5 | |
| Jan 18, 2010 at 15:03 | comment | added | Mariano Suárez-Álvarez | You can define words as maps from finite ordinals to your alphabet (which is precisely what they are!), and concatenation as the obvious map from the ordinal sum... You seem to making waves in a cup of tea :P | |
| Jan 18, 2010 at 14:56 | history | edited | Anthony de Almeida Lopes | CC BY-SA 2.5 |
added 797 characters in body
|
| Jan 18, 2010 at 14:51 | comment | added | Anthony de Almeida Lopes | @Qiaochu Yuan: It seems to me that what you're proposing is a way of generating an entire (potentially infinite) language from a grammar. I also did not ask whether or not these descriptions existed, just where I could find them. Let me update the question with a more concrete example of what I'm asking. | |
| Jan 18, 2010 at 14:40 | comment | added | Qiaochu Yuan | What's not set-theoretic about production rules? Take the set of all trees that can be formed by repeated use of the production rules and add to your formal language the set of all words that result from such trees. Both of these things are perfectly well-defined. | |
| Jan 18, 2010 at 14:29 | comment | added | Anthony de Almeida Lopes | Certainly it would be circular to a degree, however one could minimize the amount of required symbols. For example, if it could be done just with a minimal set of set-theoretic symbols, then it may provide some interesting insight. | |
| Jan 18, 2010 at 14:26 | comment | added | Harry Gindi | Isn't this bound to be circular? I mean, don't we need a formal language in the first place to define set theory? | |
| Jan 18, 2010 at 14:06 | history | asked | Anthony de Almeida Lopes | CC BY-SA 2.5 |