In my recent question on Godel Completeness I mentioned that there was a related question I wanted to ask, but would keep separate. I have been recently studying "non-well ordered sets" and Chapter 7 of this paper is useful background. There are many mathematical questions about non-well ordered sets, but here I want to return to something I noticed in Logic.
There is a form of Godel Completeness known as "Generalised Completeness Theorem" which applies to uncountable languages. For this theorem to be proven it requires the Axiom of Choice. This is understandable, and is needed because the uncountable language needs to be ordered to construct the formulae ordering needed in proofs: $\phi_1, \phi_2, \phi_3, ...$
However I have only seen this point mentioned for uncountable languages - never as an assumption in connection with countable languages. EDIT Thus AC is invoked in proofs involving uncountable languages. But Sets (in ZF) can be "uncountable" for two distinct reasons: Let S be such a ZF set:
- S is well ordered, but has cardinality greater than $\aleph_0$
- S is not well ordered, and so again cannot be put into correspondence with $\omega$.
In the latter case giving a "size" to the set is harder. However a theorem called Hartog's theorem provides an associated ordinal - that is Hartogs(S) is an ordinal. This does not quite give us the notion of exact size like we had in ZFC, but it is a beginning. As a finite ordinal example
Hartogs$(n) = n+1$
This is what I shall mean in the Question by "low cardinality" non-well ordered sets - sets which would like to be countable but cannot be due to being non-well ordered. This idea is related to Conways "Counted - Countable" distinction mentioned in that paper (I think).
Such sets still have finite subsets (which are always well-ordered without any Choice) and examining these elements might lead one to infer that the main set was well ordered.
So why does Formal Language theory only consider "Well ordered languages?" END EDIT
My initial answer is that formal languages are often assumed built on a finite alphabet - hence all words and formulae can be lexicographically ordered without even Choice being required.
Beyond this case it all becomes more problematic. One can have an infinite alphabet. This has to be assumed well-ordered to start things off. In several of my Logic textbooks we are simply told: A is an alphabet with members - a1, a2, a3, .... So this implicitly (but not explicitly) assumes either (1) that Choice is invoked or (2) that A is an infinite well ordered set to start with. As a result all theorems (including the regular Godel Completeness) may now depend on Choice via this assumption? For those reading my related question this would seem to imply that e.g. Godel's Completeness theorem is never really independent of Choice (and not merely WKL)? In short Formal language texts are saying "Let A be a well ordered set ..."
The benefit of having a countable supply of variables could still be resolved in such a case: Let S be a "low cardinality" non-well ordered Set. Then let A = S U Nat. A is a non-well ordered alphabet, generating a non-well ordered language with (a class of) indexical terms.
The Amorphous Set construction in Answer to my previous question is an example of a non-well ordered set construction. Borrowing Conway's term one might want to distinguish between:
- Countable Languages (those with an enumerable alphabet, etc)
- Counted Languages (those which cannot be isomorphic to Nat)
I have never seen this subject discussed before, so I am looking for other comments.
EDIT: I have removed all references to Countable Choice in the first version of this question for reasons identified in comments below.