Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
The models for the finite subsets can be entirely different from each other. One can then use Compactness, or (very slightly) more concretely, splice the models together using an ultraproduct, and get a model of the full set of axions. –  André Nicolas May 28 '12 at 23:17
    
I don't understand the question. What does it mean for a symbol to be interpreted in "the same" way in different models? –  Qiaochu Yuan May 29 '12 at 0:33
    
@QiaochuYuan, I had in mind some appropriate homomorphism involving the relevant relation or operation. E.g., since you can extend the usual order on N to the usual order on R, I would consider these the same in the right way. –  Rachel May 29 '12 at 0:44
2  
@Rachel: this is completely unnecessary. To prove that $T_n$ is consistent you just need to exhibit a model of it, and the models $M_n$ you exhibit need not have anything to do with each other (e.g. there may not exist any homomorphisms whatsoever between them). The only thing the different interpretations of a symbol need to have in common is that they need to satisfy all of the axioms you impose. –  Qiaochu Yuan May 29 '12 at 0:45
1  
@Rachel: As to your "reversing" problem, an appropriate language needs to be found. I cannot see how to build one, since from function symbols of arities $2$, $3$, $4$ and so on you seem to be wanting to construct one of infinite arity, so in trying to apply Compactness we are dealing with shifting languages. We can, in a language number-theoretic setting, use explicit encoding of the reversal of finite sequences, and then in a non-standard model there will be encodings of "reversal" of some infinite sequences. –  André Nicolas May 29 '12 at 2:53

1 Answer 1

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.

share|improve this answer
    
Why does n have to be "high enough" (and what does this mean)? I am familiar with ultraproducts and transfer. Also, what is the cofinite ultrafilter? The cofinite (Frechet) filter on N is not an ultrafilter since it doesn't contain a member of every partition of N; e.g., it doesn't contain either the odd or even naturals, which more importantly are also relative complements. I also thought that the cardinality of a set does not matter when it comes to containment in an ultrafilter. Being countable is not enough to guarantee containment for every ultrafilter. –  Rachel May 29 '12 at 1:31
    
Cofinite ultrafilter doesn’t make sense: the filter of cofinite sets isn’t an ultrafilter. If you mean simply an ultrafilter extending the cofinite filter, the term is free or non-principal ultrafilter. –  Brian M. Scott May 29 '12 at 8:29
    
@Brian : yes thanks. –  mercio May 29 '12 at 10:51
    
@mercio, Regarding the new addition, I said in my question that a function won't satisfy all $r_n$. That is not what I need. I just need every $r_n$ to be satisfiable. The problem is that I don't know how to describe a reversing function without reference to the terms of the sequences, and for this, I need a second-order axiom, which means no compactness. Also, $\mathbb{Q}$ is not a model of $T$. $T$ is non-Archimedean. And compactness does tell you about your models because it gives you axiomatizations for them. It just doesn't give you a particular construction. –  Rachel May 29 '12 at 15:53
    
@ Rachel : if you think $\mathbb Q$ is not a model of $T$, please show me a sentence in $T$ that is false in $\mathbb Q$,or check that the $T$ you wrote down is really the $T$ you are thinking about. –  mercio May 29 '12 at 16:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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