3
$\begingroup$

Please don't give me a complete answer to the motivation part of the question. I want to figure that part out for myself.

Motivation: As a starting example, say that a reversing function is a unary function on a set of $n$-length sequences over a nonempty set $X$ that would map $\langle x_1, x_2, x_3, x_4 \rangle$ to $\langle x_4, x_3, x_2, x_1 \rangle$ for $n=4$. I want a function that reverses infinite sequences. By this, I mean that I want to swap the values of the first and last positions with each other, swap the values of the second and second-to-last positions with each other, etc. I realize that "last position" is a tricky notion for an infinite sequence. However, I am hoping that such a function might exist by compactness, since there exist functions reversing the first $n$ positions of an infinite sequence for every $n$. More precisely, I want to define the n$^{th}$ unary reversing operation $r_n$ on a set $X^\mathbb{N}$ of infinite sequences to be the operation that maps $\langle x_1, x_2, \ldots, x_{n-1}, x_n, x_{n+1}, \ldots \rangle$ to $\langle x_n, x_{n-1}, \ldots, x_{2}, x_1, x_{n+1}, \ldots \rangle$. I can define this more precisely. This part is not my question.

Question: Wanting to use the compactness theorem for the above problem has raised a question about another compactness argument that establishes the existence of an ordered field containing infinitesimals. Define a set $T$ of first-order sentences inductively using sets $T_n$:

\begin{align} T_0 &= \text{ the axioms for an ordered field} \\ T_1 &= T_0 \cup \exists x [0 < x < 1] \\ T_2 &= T_1 \cup \exists x [0 < x < 1/2] \\ T_n &= T_{n-1} \cup \exists x [0 < x < 1/n] \\ T &= \bigcup_n^\infty T_n \end{align}

The argument is that, since there is a model of every (finite) $T_n$ (the real field will work), there is a model of (infinite) $T$ by compactness. Furthermore, the model of $T$ contains infinitesimals, i.e., positive numbers less than every $1/n$ because this is what the existence statements altogether claim.

My question is what exactly is happening with the binary order relation symbol $<$ in the existence sentences. The sentences above are all in the same language, so I presume this is the same exact symbol in each sentence. To use compactness, do the interpretations of all nonlogical symbols have to be the same across the finite subsets? This seems like too strong of a requirement, but what exactly is required? To what extent does it matter what a relation symbol or function symbol gets mapped to, e.g., does a symbol have to be mapped to isomorphic sets (perhaps on different domains)? If there are constraints, how do you specify them? Also, how do you relate the interpretations used for the finite subsets to the properties of the whole set of sentences, as was done in the claim about infinitesimals? The understanding in my example is that $<$ gets essentially the same or compatible interpretations for each $n$.

For my motivating problem, this becomes important because the $r_n$ as I have defined them above are very different functions for each $n$. They aren't extensions or supersets or related in any nice way as far as I can tell.

  • 0
    @AndréNicolas, The reversing functions are all unary operations on a set of infinite sequences. Each reversing function reverses the first $n$ terms and leaves the rest unchanged. I might start a new question about the axioms for this class of function because the two that I have so far are problematic. (The worst: for finite cases, $r(x)$ should be eventually equal to $x$ (i.e., $r(x)$ and $x$ only disagree for a finite initial segment), but this equivalence does not intuitively hold for the infinite case since the entire sequence is (potentially) changed.) Thanks for the help.2012-05-29

1 Answers 1

2

As you wrote it, your theory $T$ has a simple model, $\mathbb Q$. Indeed there is an $x$ in $\mathbb Q$ such that $0 < x <1$, for example $x=1/2$. There is also an $x$ in $\mathbb Q$ such that $0 < x < 1/10$, for example $x=1/37$, and so on, so every sentence you included in $T$ is true in $\mathbb Q$.

In order to get a theory that does what you want to do, you need to add a constant symbol in your language, say $\varepsilon$. So your langage has the functions symbols $\{0,1,\varepsilon,+,\times \}$ (a constant symbol is a function symbol of arity 0), and the predicate symbols $\{ =, < \}$. Let $T_0$ be the axioms for ordered fields and the sentence $"0 < \varepsilon"$, and $T_n = T_{n-1} \cup \{"\varepsilon \times (1+1+\ldots+1)< 1"\}$.

For any $n$, there is a model $\mathcal M_n$, of $T_n$ by taking $\mathbb Q$ with the usual interpretations for $0,1,+,\times,=,<$ and interpreting $\varepsilon$ as $1/(n+1)$. Indeed, it satisfies the axiom of an ordered field, and $1/(n+1)$ is less than $1,1/2,1/3,\ldots,1/n$. Therefore $T_n$ is consistent forall $n$.

By the compactness theorem, the theory $T = \cup T_n$ is also consistent. The compactness theorem does not tell you about any model of $T$, but it does tell you that a sentence is provable in $T$ if and only if it is provable in $T_n$ for $n$ high enough (anything provable in $T_n$ is still provable for higher $n$).

By the completeness theorem, since $T$ is consistent, $T$ has a model, which means that there is an ordered field $\mathcal M$, containing an element $\varepsilon$ such that $\varepsilon$ is smaller than any fraction of the form $1/n$, for all $n$ at the same time.

You can build a model by taking an ultraproduct of all the models of $T_n$ that we found together. The underlying set is the set of the families that pick for each $n$, an element of $\mathcal M_n$, quotiented by an ultrafilter on $\mathbb N$. Then, $0$ is the equivalence class of the family picking each $0$ in $\mathcal M_n$, that is, the sequence $(0,0,0,\ldots)$ ; and $\varepsilon$ is the equivalence class of the family picking the interpretation of $\varepsilon$ in each $\mathcal M_n$, that is, the sequence $(1/2,1/3,1/4,\ldots)$ etc.

However, in this simple case, we don't need to use all this heavy stuff, we can find such a model in nature, by using $\mathbb Q(X)$, the field of rational fractions in one variable, and by interpreting $<$ as $P(X) < Q(X) := \exists \delta > 0, \forall \varepsilon \in ]0;\delta[, P(\varepsilon) \text{ and } Q(\varepsilon) \text{ exist, and } P(\varepsilon) < Q(\varepsilon)$. Proving that this is well defined and is a model of $T$ is not very difficult.


Now as for your motivating question, you would need a language in order to express the properties you want. And even then, suppose $\phi_n(x)$ is a formula saying that $x$ reverses the first $n$ elements of an infinite sequence. Unlike in the previous example, where it is possible for a same rational $x$ to be smaller than $1/2$ and smaller that $1/3$ at the same time, here it is not possible for an $x$ to satisfy $\phi_1(x)$ and $\phi_2(x)$ at the same time.

If you add a constant symbol $f$ to the language, then there is no model in which both sentences $\phi_1(f)$ and $\phi_2(f)$ are true at the same time. So right from the start, your theory $T_2$ is going to be inconsistent.

If you find a family of properties $(\phi_1,\phi_2,\ldots)$ where you know that for any $n$, there is an object $f_n$ such that $\phi_1(f_n) \ldots \phi_n(f_n)$ are simultaneously true, then you can apply the compactness theorem. But for now, you can't find any function satisfying any two at the same time.

  • 0
    @mercio, Yes, sorry. $\mathbb{Q}$ is a model of $T$.2012-05-29