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.

  • 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.2012-05-28
  • 0
    I don't understand the question. What does it mean for a symbol to be interpreted in "the same" way in different models?2012-05-29
  • 0
    @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.2012-05-29
  • 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.2012-05-29
  • 0
    @AndréNicolas, Okay, but then what can you say about the ultraproduct? For my problem, I want to say that there exists a function on it that reverses infinite sequences, by reasoning (I presume) similar to that that gives the existence of infinitesimals. That is, how do I know what union of all my $T_n$ actually says, taken together? It's not clear to me that I get the function that I want.2012-05-29
  • 0
    @Rachel: André is referring to Łoś's theorem (http://en.wikipedia.org/wiki/Ultraproduct#.C5.81o.C5.9B.27s_theorem), which is a relatively concrete way of proving the compactness theorem. However, I do not believe it gets you the function you want. What is your theory of functions that reverse sequences?2012-05-29
  • 0
    @QiaochuYuan, If you are asking for axioms that a reversing function must satisfy, I don't have any yet. Is this what you mean? (I am familiar with ultraproducts, by the bye. An ultraproduct would be very nice.)2012-05-29
  • 0
    @Rachel: yes. Don't you need some to apply compactness to the problem of finding a function that reverses infinite sequences?2012-05-29
  • 0
    @QiaochuYuan, Yes, I just hadn't gotten that far yet. I was thinking intuitively about the models. But now I am concerned because I want to say that there exists a function with such-and-such properties, but I cannot say this directly. I think my original question has been answered, though. Thanks for the help. :^)2012-05-29
  • 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.2012-05-29
  • 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