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.

Prove that $Th((\mathbb{Q},<,+,0,1))$ has uncountably many 1-types.

Prove that $Th((\mathbb{Q},+,0,1))$ has countably many 1-types.

Prove that $Th((\mathbb{Q},<,0,1))$ has five 1-types.

Prove that $Th((\mathbb{Q},<,+))$ has three 1-types and uncountably many 2-types.

($Th(\mathfrak{A})$ with $\mathfrak{A}$ a structure notates the theory of the structure, this theory is in particular complete.)

I've got this exercises and i guess i have to think about wat such a n-type in the theory says, but i don't know how to do this. Can someone help me?! Thank you :)

share|improve this question

3 Answers 3

An $n$-type for a language $\mathscr{L}$ is a maximal consistent set of formulas of $\mathscr{L}$ with $n$ free variables, so a $1$-type is a maximal consistent set of formulas of $\mathscr{L}$ with one free variable. If $\mathfrak A$ is a model for $\mathscr{L}$ with underlying set $A$, and $a\in A$, the set of all formulas $\varphi(x)$ such that $\mathfrak A\vDash\varphi(a)$ is a $1$-type, called the type of $a$ in $\mathfrak A$.

Intuitively, a $1$-type says as much as one can consistently say (in $\mathscr{L}$) about a single object, so there’s a $1$-type for each distinguishable kind of object. Look at $\operatorname{Th}(\langle\Bbb Q,<,0,1\rangle)$, for instance; what kinds of rationals are distinguishable using only the relation $<$ and the constants $0$ and $1$? Clearly the type of $0$ is unique: the formula $x=0$ by itself picks out that one rational number, and expanding it to a $1$-type isn’t going to change that. The same goes for $1$, so we’ve found two $1$-types already. There are supposed to be three more, and it’s pretty obvious what they must be: the two named rationals divide the rest of $\Bbb Q$ into three intervals, $\Bbb Q\cap(\leftarrow,0)$, $\Bbb Q\cap(0,1)$, and $\Bbb Q\cap(1,\to)$. You can say that a rational is in one of these intervals: the formulas $x<0$, $0<x\land x<1$, and $1<x$ already characterize these three types. On the other hand, there is no collection of formulas in one free variable that is satisfied by some of the negative rationals but not by others: there simply isn’t anything that you can say in this language that distinguishes one negative rational from another.

Now take a look at $\operatorname{Th}(\langle\Bbb Q,<,+\rangle)$; there are supposed to be three $1$-types and uncountably many $2$-types. Start with the $1$-types; are there any specific rationals that we can pin down in this language? There’s definitely one: the formula $x+x=x$ is satisfied only by $0$, so one of the $1$-types defines $0$. Since we have $<$, we can also say that a rational is positive or that it’s negative: the formula $$\exists y(y+y=y\land y<x)$$ is satisfied precisely by the positive rationals. But where are all those $2$-types going to come from?

Start ‘small’: try to find a countably infinite number of different $2$-types. If $m$ and $n$ are positive integers, let $\varphi_{m,n}(x,y)$ be the formula

$$\underbrace{x+\ldots+x}_m=\underbrace{y+\ldots+y}_n\;;$$

$\varphi_{m,n}(x,y)$ characterizes pairs $\langle p,q\rangle$ of rationals such that $mp=nq$, i.e., such that $\frac{p}q=\frac{n}m$. This is almost like being able to specify each rational, and it gets us $\omega$ $2$-types. There are uncountably many Dedekind cuts in $\Bbb Q$; perhaps we should try to modify the preceding idea so that instead of picking out particular rational ratios, it picks out arbitrary real ratios. Let $\psi_{m,n}(x,y)$ be the formula

$$\underbrace{x+\ldots+x}_m<\underbrace{y+\ldots+y}_n\;;$$

$\psi_{m,n}(p,q)$ says that $mp<nq$, or $\frac{p}q<\frac{n}m$, and $\psi_{n,m}(q,p)$ says that $nq<mp$, or $\frac{n}m<\frac{p}q$. Using these formulas, you can construct sets of formulas that are satisfied by a pair $\langle p,q\rangle$ of rationals if and only if the ration $\frac{p}q$ satisfies an infinite family of inequalities of the forms $\frac{p}q<\frac{n}m$ and $\frac{n}m<\frac{p}q$; do you see how you can combine that with the idea of Dedekind cuts to generate an uncountable family of $2$-types?

I’ll say nothing about the other three problems; I think that I’ve given you enough here to give you a good start on tackling them.

share|improve this answer
    
@tomasz: Depends on whom you ask. From the first edition of Chang/Keisler, p. 77: ‘By a type $\Gamma(x_1\dots x_n)$ in the variables $x_1,\dots, x_n$ we mean a maximal consistent set of formulas of $\mathscr{L}$ in these variables.’ And that’s how I learned to use the term. (From Keisler, as a matter of fact.) –  Brian M. Scott Oct 22 '12 at 16:14
    
I see. Well, I think it's more natural to call them complete types (especially since it clearly corresponds to theory/complete theory -- a theory can be seen as a $0$-type, a complete theory as a complete $0$-type). But I understand that there are some other conventions. :) –  tomasz Oct 22 '12 at 16:18
    
@tomasz: I’ve certainly no problem with your usage, which I see is also Hagen’s; it may be the OP’s too. I just hadn’t run into it (that I remember: it’s been a long time since I did any model theory.) These comments are probably a good thing, since they get the potential confusion out in the open. –  Brian M. Scott Oct 22 '12 at 16:20

Here, an $n$-type is a set of formulas with $n$ free variables such that for every finite subset of this set, there exist $n$ rational numbers making these finitely many formulas true.

Since every subset of a type is also a type and that would make producing numerous types easy,I suppose that the problem is in fact about complete types, that is maximal sets of formulas, such that ...

To get you starting: An example of a 1-type for $Th((\mathbb Q,<,+))$ would be the set of all formulas $\phi(x)$ such that $b>0\vDash \phi(b)$. For example, $$\phi(x)\equiv\forall y\colon( y+y=y\to y<x)$$ is in this type.

share|improve this answer

Some hints on how I would proceed to do these:

For the first one, notice that in the theory of $({\bf Q},0,1,+)$ defines each rational number. If you add $<$ to this, you can find a distinct type for each real number (generally, if you have a linear order $(L,<)$, then with a parameters from a subset $A\subseteq L$ you can find distinct type for each element of the Dedekind completion of $A$).

In the second case, you can notice that the theory can be seen as the theory of vector fields over $\bf Q$, with added a symbol for one nonzero vector (because multiplication by rational numbers is definable in the theory). Looking at it this way, it shouldn't be hard to see that there are types for: 0, each element in the linear span of $1$ (which is countable), and for an element linearly independent with $1$ (as would be the case with every vector space over an infinite field with a symbol for one nonzero element). Alternatively, you can notice that there's a saturated countable model (${\bf Q}^\omega$).

In the third case, notice that for countable dense linear order, there's an automorphism of it which moves any element onto any other (which is easy to see). With little effort, using that fact you should be able to show that you can move any element in $({\bf Q},0,1,<)$ onto any other as long as you don't change its relationship with $0$ and $1$, so $({\bf Q},0,1,<)$ realizes exactly $5$ one-types; and if a model realizes only finitely many types, there can't be any more.

In the fourth case for $1$-types we can do something similar: show that for any two rationals $q_1,q_2\in \bf Q$ there's an automorphism that moves $q_1$ onto $q_2$ if and only if they are both positive, both negative, or both zero. For $2$-types you can do the same thing as in the first example (you can define the set of pairs $(q_1,q_2)$ such that $q_2$ is a given rational multiple of $q_1$, and using that, for each real number $r$, you can define the type which represents the pairs $(x,y)$ where $y=r\cdot x$).

share|improve this answer

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.