On the permissability of uncountable languages in constructions of FOL

Question

To me it has always been a leap in allowing uncountable languages in constructions of first-order logic. I do my best to avoid them. Unfortunately this is not always possible. I was curious if anyone could show/justify/prove that it's possible to assign a unique symbol/graphic to each real number. It would be helpful in easing my hesitance in accepting the current proof I'm reading.

Answer 1

The idea that "a language is a set of scribable symbols" is similar to the idea that "a positive real number is the length of physical object" - it gets things started nicely, but you very quickly want to discard it in favor of a purely abstract treatment.

That is: there is a distinction between "language humans can use" and "language as a mathematical object." Logic is not just a tool, but also a subject of mathematical inquiry itself. You will certainly never actually write using a language with continuum-many (or indeed infinitely many, or even Graham's-number-many) symbols, but that doesn't mean you won't study such languages.

If you prefer, you can make new names for everything: planguage, psymbol, pstructure, ... (the "p" is silent). I don't mean this dismissively - one may reasonably object to the use of the word "language" to describe something that can't be written down (similarly, I think some ultrafinitists object to the term "number" being used to describe e.g. Graham's number), and so it may be helpful at least at first to translate theorems about logic into an un-loaded terminology.

---

I think at this point it's useful to give a definition of a structure - complete with its language - as a purely mathematical object. The following definition (made inside your favorite set theory or other foundational framework - I'll use ZFC for simplicity) might help clarify things:

• A structure is a triple $(A, \Sigma, I)$ where

  • $A$ is an arbitrary set (the underlying set of the structure),

  • $\Sigma$ is some function with codomain $\mathbb{N}$ (we think of $\Sigma$ itself as the language: the symbols are the ordered pairs $\langle x, \Sigma(x)\rangle$ for $x\in dom(\Sigma)$ - note that set-theoretically speaking, $\Sigma$ itself is exactly the set of all such ordered pairs! - where the left coordinate is giving the symbol a name and the right coordinate is giving it an arity), and

  • $I$ is a map from $dom(\Sigma)$ to $\mathcal{P}(A)\cup \mathcal{P}(A^2)\cup\mathcal{P}(A^3)\cup...$ such that $\Sigma(d)=i$ implies $I(d)\in\mathcal{P}(A^i)$. ($I$ is the interpretation of the symbols in the domain of $\Sigma$, sending each symbol to a relation on $A$ of appropriate arity.)

So for example, let's say I want to look at "$\mathbb{R}$ with each real named by a unary relation symbol." One way to view this is as the structure $$(\mathbb{R}, \{\langle r, 1\rangle: r\in\mathbb{R}\}, \{\langle r, \{r\}\rangle: r\in\mathbb{R}\}\}).$$ That is:

• The underlying set is $\mathbb{R}$.

• We have one unary relation symbol for each real number.

• The interpretation of the unary relation symbol indexed by "$r$" is $\{r\}$.

(Remember that in set theory, a function is a set of ordered pairs.)

Note that each real is doing double-duty here, both as an element of the structure and as a (left coordinate of a) symbol. This is fine as long as we're careful about it, but it's also reasonable to demand that the domain of $\Sigma$ and the underlying set of the structure be disjoint, just to make things nicer. In this case, we could work instead with $$(\mathbb{R}, \{\langle \langle r, \mathbb{R}\rangle, 1\rangle: r\in\mathbb{R}\}, \{\langle \langle r, \mathbb{R}\rangle, \{r\}\rangle: r\in\mathbb{R}\}).$$ That is, each symbol's left coordinate is now itself an ordered pair of the form $\langle r,\mathbb{R}\rangle$; in any reasonable set theory, no such ordered pair is a real number, so this meets the additional requirement.

We can now define formulas, sentences, theories, satisfaction, ultraproducts, etc. for arbitrary languages (that is, functions with codomain $\mathbb{N}$) and arbitrary structures on purely mathematical grounds, and prove theorems about these. How you choose to interpret these definitions and theorems, philosophically speaking, is to a certain extent up to you. But it's important to note that they interact in nice ways with the more "concrete" objects: e.g. we can prove something about a "concrete structure" (say, the field of real numbers) by proving something about an "abstract structure" (say, an appropriate ultrapower of the field of real numbers).