I am attempting to prove only the cardinality portion of the Löwenheim-Skolem theorem. In other words, I am only trying to show that the existence of a model of every infinite cardinality, and am not trying to prove that these models are related to each other in any way.
I had an idea for how to prove this by starting with a set of primitive values that are a priori distinct from each other and then building well-formed formulas on top of them. I'd be using the set of well-formed formulas as the basis for constructing a model. That's what I tried to do here, anyway.
I'm interested in knowing
- Whether the proof attempt works
- Whether I left out any important details that can't/shouldn't be glossed over
- Whether there's a way of proving LS that's much simpler
A standard term defined somewhere in the literature will be mentioned in italics when first defined. A term that I am making up for the purposes of this question will appear in bold when first defined. I also use italics for emphasis. The presence of bold text outside of a section title unambiguously signals a nonstandard definition after this paragraph.
From Wolfram MathWorld, here is the statement of the theorem
The Löwenheim-Skolem theorem is a fundamental result in model theory which states that if a countable theory has a model, then it has a countable model. Furthermore, it has a model of every cardinal number greater than or equal to $\aleph_0$.
I am attempting to prove the following
If a theory has at least one infinite model, then it has at least one infinite model of every infinite cardinality.
I am defining a signature as follows, taken from A Shorter Model Theory by Wilfrid Hodges.
The signature of a structure $A$ is specified by giving.
$(1.5)$ the set of constants of $A$, and for each separate $n > 0$ , the set of $n$-ary relation symbols and the set of $n$-ary function symbols of $A$.
Therefore, I am defining a signature as an ordered triple.
- A set of constant symbols
- A sequence of sets of predicate symbols where the $n$th element of the sequence is the set of $n$-ary predicate symbols.
- A sequence of sets of function symbols where the $n$th element of the sequence is the set of $n$-ary function symbols.
A theory is just a countable set of sentences.
An augmented theory is an ordered pair consisting of a signature and a theory. In an augmented theory, all of the function, predicate, and constant symbols used in the theory element must be consistent with the signature element.
A model of an augmented theory is a structure that satisfies the signature portion of the augmented theory and the theory portion of the augmented theory.
Lemma 101: If $T$ is a predicate-free, constant-free augmented theory with an infinite model and $X$ is a nonempty set, then there exists a model $g(T,X)$ generated by $X$.
Intuitively, $X$ is a set of variable symbols and two elements $u, v$ of $X$ are defined to fall in the same equivalence class if $u=v$ is a theorem in $T$.
Let $W$ be the set of finite sequences of symbols constructed inductively in the following way.
Every singleton sequence of elements $x$ from $X$ is a well-formed formula by itself.
$$ x \in X \implies x \in W $$
Every function symbol can be used to create new terms.
$$ x_1 \in W \;\text{and}\; \cdots \;\text{and}\; x_n \in W \implies f(x_1, \cdots, x_n) \in W $$
Next, we define a two-place relation $\simeq$ on $W$ in the following way.
$$ \text{If $x \in X$ and $y \in X$, then $x \not\simeq y \iff x \neq y$} $$
$$ \text{If either $x$ or $y$ is not in $X$, then $ x \not\simeq y \iff \text{$x \neq y$ is satisfiable} $ } $$
In other words, distinct variable symbols are a priori not equivalent to each other. In other cases, we consider two elements equivalent if, as well-formed formulas with variable symbols, they are the same in every model of $T$. Free variables in $x=y$ are implicitly universally quantified.
Let $U$ be the set of equivalence classes on $W$.
$$ U \stackrel{\text{def}}{=\!=} \{ \{x \mathop. x \simeq w\} \mathop. w \in W \} $$
I will now construct a model $g(T, X)$ where $U$ is the domain.
$T$ has no constant or relation symbols, so we only need to say what the interpretation of the function symbols is.
Let $f$ be a function symbol of arity $n$.
Let $u_1, \cdots, u_n$ be equivalence classes within $U$.
Let $x_1, \cdots ,x_n$ be representatives of the equivalence classes named by $u_1, \cdots, u_n $.
$$ f(u_1, \cdots, u_n) = \;\text{the equivalence class that contains $f(x_1, \cdots, x_n)$} $$
In other words, we apply $f$ by picking representatives of each equivalence class arbitrarily, constructing a new element of $W$ of the form $f(\cdots)$ and then finding out what equivalence class it is in.
This completes the construction of $g(T, X)$.
Now, I use the assumption that $T$ has an infinite model.
If $T$ only has finite models or has no models at all, then the non-equivalence of all the elements of $X$ can be a contradiction. For instance, if $X$ is $\mathbb{N}$, then the theorem $\forall m \mathop. \forall n \mathop. m = n$ is contradicted.
However, since $T$ has at least one infinite model, every finite subset of $X$ is associated with at least one model. Therefore, by compactness, the whole of $X$ is associated with at least one model.
There are no theorems of $T$ that are not true in $g(T, X)$ because we added an edge to our relation $\simeq$ for every theorem of the form $t_1 = t_2$ where $t_1$ and $t_2$ are in $W$.
Therefore $g(T, X)$ is a model of $T$.
Lemma 102: If $X$ is infinite, the cardinality of $g(T, X)$ is the same as the cardinality of $X$.
The cardinality of the domain of $g(T, X)$ is bounded below by $X$.
The cardinality of the domain of $g(T, X)$ is bounded above the cardinality of the set of well-formed formulas $W$ described in the lemma 101. Since well-formed formulas have positive integer length, the cardinality of $g(T, X)$ can be expressed as follows. The notation below contains an iterated Cartesian product.
$$ |W| = \left| \bigcup_{i=1}^{\infty} \times_{j=1}^n X \right| $$
However, if $|X|$ is an infinite cardinal, then $|W|$ is equal to $|X|$.
We know that the size of the domain of $g(T, X)$ is between $|X|$ and $|W|$. Therefore
$$ |g(T, X)| = |X| $$
Lemma 103: Given an arbitrary augmented theory $T$, we can construct a new theory $T'$ that is predicate-free and constant-free. If $T'$ has an infinite model, then it can be converted to a model of $T$ without changing its cardinality.
First, we eliminate all the constant symbols.
For every constant symbol $c$, we replace it with a new function symbol $f$, together with the new axiom
$$ \forall x \mathop. \forall y \mathop. f(x) = f(y) $$
Second, we add two new unary function symbols, representing truth and falsehood. Call them $\top$ and $\bot$ and add the axioms
$$ \forall x \mathop. \forall y \mathop. \top(x) = \top(y) $$
$$ \forall x \mathop. \forall y \mathop. \bot(x) = \bot(y) $$
$$ \forall x \mathop. \top(x) \neq \bot(x) $$
Third, we eliminate all the relation symbols.
For every relation symbol $R$, replace it with a function symbol $f$ with the same arity.
Add the following axiom.
$$ \forall x_1 \cdots x_n . f(x_1, \cdots, x_n) = \top(x_1) \lor f(x_1, \cdots, x_n) = \bot(x_1) $$
In all the axioms, replace occurrences of $R(\cdots)$ with $f(\cdots) = \top(\alpha)$ where $\alpha$ is an arbitrary variable.
This completes the construction of $T'$.
In order to translate a model of $T'$ back to a model of $T$, we consider the provenance of the symbols in $T'$.
Function symbols are unchanged.
Since constants in $T$ are mapped to constant functions, map each constant symbol in $T$ to the sole element of the domain of the symbol in $T'$.
For each relation symbol in $T$, take the preimage of $\cup\,\text{Img}(\top)$ in the corresponding symbol in $T'$.
Theorem
Let $T$ be an augmented theory with an infinite model.
Let $F$ be a proper class of sets, with one set of each infinite cardinality.
From $T$, we construct $T'$ by eliminating all the constant and relation symbols as described in (103). Since $T$ has an infinite model, $T'$ has an infinite model.
For every set $S$ in $F$, $T'$ has a model $g(T', S)$ of cardinality $|S|$ by (101) and (102).
By (103), the model $g(T', S)$ can be transformed to a model of $T$ while preserving its cardinality.
Therefore, as desired, $T$ has a model of every infinite cardinality.