In formal languages, alphabet is the set of all symbols used to form words in our language.

Why is the notion of "set" used in this definition, instead of some other kind of collection, e.g. class? Does this sort of thing come from purely historical reasons or is there some deeper, perhaps philosophical or logical, justification? Does this somehow relate to proving that the alphabet we are describing exists, which seems to be easier in set theory?

Also, perhaps the following few thoughts might be related to my question.

ZFC axioms are designed to replicate the intuitive properties of sets, so listing them seems like a good way to define sets. Listing them in natural language such as English and defining first-order languages and then building a first-order ZFC theory isn't a problem, or so I thought. But I didn't pay care to my reasoning since I forgot the axiom schema of replacement, which uses the concept of first-order formulas, which in turn must be described by first order languages, so natural language listing of the axioms would result in circularity.

This axiom schema isn't needed to prove the existence of alphabet usually used in first-order language of set theory.

Since we are selecting and using symbols from the alphabet, the axiom of choice, which uses the concept of a WFF too, is needed when defining a formal language. So there is still no way not to get rid of circular results when defining sets using ZFC in natural languages though.

This seems like a pretty bad result. So why not use some other collection than set to define alphabet?

  • $\begingroup$ Doesn't this problem go away if, as is invariably the case, the alphabet is finite? $\endgroup$ – Rick Decker Apr 18 '16 at 0:17
  • $\begingroup$ @RickDecker: No it does not go away. We can without loss of generality assume that the alphabet for any countable first-order theory is finite, because we can use any prefix-free encoding to encode any countably infinite recursive set of symbols using a finite alphabet. All problems remain. See my answer for some explanations why it is an intrinsic issue. There are too many details, so feel free to ask further. $\endgroup$ – user21820 Apr 18 '16 at 12:53
  • $\begingroup$ Sorry but what is a class in your context ? $\endgroup$ – Yves Daoust Apr 18 '16 at 13:01

Your underlying question has more or less come up a few times here. See this answer for my take on the inherent unavoidable circularity in mathematics.

As for your more specific questions:

  1. You cannot define "set" in ZFC, not to say "class". In a stronger system such as MK (Morse-Kelley) you have some objects in the domain called "sets", but other objects are just "not sets". In general no first-order theory that extends ZFC can define its own domain as any kind of collection whatsoever, unless it is inconsistent.

  2. In ZFC, you need the axiom of infinity otherwise you cannot even define what is a well-formed formula, not to say the set of all well-formed formulae. Of course, the axiom of infinity cannot be justified by any simpler concept. One either accepts it based on our intuitive notion of natural numbers, or one doesn't.

  3. It is not just the axiom schema of replacement that requires knowledge of well-formed formulae. All the schemas do! The comprehension axiom schema included. Indeed to define any reasonable formal system (such as ZFC), we need to work in a separate meta-system that already allows us to talk about finite strings from some fixed alphabet, otherwise we cannot define what is a valid sentence, nor can we define the inference rules. It turns out that we don't need much in most cases. Most reasonable formal systems can be defined in any meta-system that is of equivalent strength to PA (though to understand or prove that the definition 'works' we would need to work in a meta-meta-system...).

  4. Defining a formal system via syntactic rules is one thing. Defining its semantics, namely what are models of a formal system, is another thing, and requires much much more. For the latter we need a meta-system that not only knows string manipulation but also knows about collections of some sort, so that it can express the actual semantics of quantifiers.

So the bottom-line is that, no, there is no way to get around knowing finite strings or equivalently natural numbers in the meta-system. However, once you distinguish between the meta-system and the formal systems you study, then you can grasp what actually is happening. Usually we chose ZFC as our meta-system, and we can investigate the properties of various formal systems as proven in ZFC. This includes ZFC itself. We can show for example that all first-order theories (a particular category of formal systems) satisfy some interesting properties like completeness and compactness, and that every countable first-order theory with an infinite model has a model of every cardinality.

Incidentally, Godel showed any formal system $T$ that has PA as a fragment and is effective (proofs over $T$ can be deterministically checked) cannot prove 'its own consistency', in the specific sense that we can build (even with a fixed computer program) a sentence $Con(T)$ over $T$ such that it represent the correct notion as long as our meta-system already has a model of PA. More precisely, we would have $\mathbb{N} \vDash Con(T)$ iff $T$ is consistent. If PA is flawed, then all bets are off. But the widely used HTTPS (specifically RSA decryption) relies on a non-trivial theorem of PA applied to natural numbers encoded as binary strings in physical media, so it is reasonable to believe that PA is valid, and so Godel's results put serious restrictions on what any formal system can do, not just those that we have come up with so far.

Godel's incompleteness theorems partially explain why any circularity in justification is inevitable. My linked post explains more of why circularity in definition is inevitable.


It would be extremely pedantic to introduce any consideration about ZFC in the definition of an alphabet. But anyway, your formal approach seems strange to me from the very beginning "alphabet is the set of all symbols used to form words in our language". No, that is not the formal way it is defined. You rather consider the concrete category of monoids Mon (and as you know, it means you already have a faithful functor F: Mon${}\to{}$Set) and then you define the free monoid on (the alphabet) $A$. It turns out (this requires a proof) that this free monoid is the set of formal words (the usual definition) with concatenation as product and the empty word as the identity.

  • 2
    $\begingroup$ It would be extremely pedantic to mention categories when defining an alphabet. $\endgroup$ – GEdgar Apr 20 '16 at 14:03
  • $\begingroup$ @GEdgar I fully agree with your comment, of course. I never define an alphabet in this way. $\endgroup$ – J.-E. Pin Apr 20 '16 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.