6

I'm a beginner and this is unfair if I try to add something to Alex Kruckman's perfect answer. But I've seen an interesting tip as an idea for the importance of this concept in general. Roughly speaking, suppose we are in the category of sets, one can hold a bijective correspondence between surjective functions on given set, say $X$, and equivalence ...


6

There are many reasons why you might care about elimination of imaginaries. Here are a few: If $T$ eliminates imaginaries, and $M\models T$, then any structure interpretable in $M$ is actually definable in $M$. For example, suppose $G$ is a definable group in $M$. This means that there is a definable set $X\subseteq M^n$ for some $n$ and a definable ...


5

You are right that $\mathcal{C}_{< \omega}$ is not axiomatisable. The usual argument using compactness goes by contradiction. It goes as follows (I'll leave it to you to fill in the details). Suppose that there is an axiomatisation $T$. Let $\phi_n$ express "every equivalence class has at least $n$ elements" (exercise: write down such a formula). Show ...


5

I cannot understand what you are asking and saying. If a sentence is only true in infinite models then it is false in every finite model, so its negation is true in every finite model. That's it. For any sentence $\sigma$ whatsoever $\operatorname{Mod}(\sigma)\in EC$... this is the definition of $EC.$ So in particular $\operatorname{Mod}(\lnot \tau)\in EC.$ ...


5

Yes, there are such models $\mathcal{M'}$ and $\mathcal{N'}$, and we may take them to be extensions of $\mathcal{M}$ and $\mathcal{N}$ respectively. Note that $a$ and $b$ being constants of the language is not really a requirement. If they were just elements of $\mathcal{M}$ and $\mathcal{N}$ with the same type, then we could add constants to the language ...


4

For your second question, a theorem or exercise down the road will be to show that if you preserve the "basic" operations/relations then you also preserve those "built up" from them. This winds up being an induction on complexity, which is a technique you'll use all the time here. Let's look at your first case. For clarity, I'm going to write "$\oplus$" for ...


4

Your summary seems accurate, with one exception: The theory of algebraically closed fields of characteristic 0 is complete. Perhaps you meant the theory of algebraically closed fields, without specifying the characteristic?


4

The logic you're referring to is called WMSO[<], or Weak Monadic Second Order Logic (with <). It is the logic where one is allowed to quantify over (monadic) second order terms (i.e., the subsets of $\mathbb{N}$), but only weakly (i.e. only the finite subsets). There are many results known about this and related logics, as Buchi found a kind of ...


3

Your argument is correct. More directly, you can just observe that any quantifier-free formula is a Boolean combination of atomic formulas, and the only atomic formulas in one variable are $x<x$ and $x=x$. Both of these are either true for all $x$ or false for all $x$, and so every quantifier-free formula in one variable is either true or false for all $...


3

There are tons of consequences of $\sigma$; indeed, $T$ is a complete theory, so for every sentence $\varphi$, either $\varphi$ or $\neg\varphi$ is in $T$. For instance, one very meaningful universal statement in $T$ is $\forall x\forall y(x=y)$. Or, for any formula $\varphi(x)$, $\forall x\forall y(\varphi(x)\leftrightarrow \varphi(y))$ is in $T$. The ...


3

There are only two general conditions (that I know of) under which automorphism-invariant implies definable (in first-order logic): (1) the trivial case when $\mathfrak{M}$ is finite, and (2) when $A$ is finite and $\mathfrak{M}$ is the unique countable model of an $\aleph_0$-categorical theory. In this case, the result is a consequence of the Ryll-...


3

One has to be a bit careful with this statement. For example, suppose $A = \{a\}$, $B = \{a,b\}$, and $c = b\notin \text{acl}(A)$. Then the formula $(x = a \lor x = b)$ witnesses that $\text{tp}(c/B)$ is algebraic, but it does not divide over $A$. But if we consider a formula isolating $\text{tp}(c/B)$ (or at least implying that $c\notin \text{acl}(A)$), ...


3

About (1): it means that for each $\varphi_i$, for $\mathscr U$-almost all $j$ you have $A_j\models \varphi_i(a_j)$. It does not at all imply that $p$ is realised by any tuple in any of the $A_j$, if that is what you were thinking. I don't think there is much more to be said, unless you have some more specific questions. About (2): as stated, no, this is ...


3

The complete theory of the structure $(\mathbb{Z}; 0,+,-,(n|)_{n\in \mathbb{Z}})$ , which is a definitional expansion of $(\mathbb{Z};+)$, has quantifier elimination. Of course, it already suffices to include the divisibility predicates $(p^k|)$ when $p$ is prime and $k>1$, since $n\mid x$ is equivalent to the conjunction of $p^k\mid x$ for each prime ...


3

For the first question, the point is that there are basic algebraic/combinatorial phenomena which can only occur in infinite structures. The simplest example is an injective non-surjective function: in the language with a unary function symbol $f$, the sentence $$[\forall x, y(x\not=y\implies f(x)\not=f(y))]\wedge[\exists x\forall y(f(y)\not=x)]$$ does have ...


2

As Chris Eagle said, your example for (1) is wrong. Removing the characteristic specification does the trick (as they observe), but there are also far simpler examples. For instance, take the empty language $\{\}$ (so only "$=$" allowed, besides the pure logical grammar) and consider the theory $$T=\{\exists x,y\forall z(x=z\vee y=z)\}.$$ This theory has ...


2

This is similar to Shaun's answer, however, it uses different software. One can generate a tree proof for the first one that closes as follows: However, for the second one the tree proof does not close allowing a countermodel to be constructed showing it is invalid: The countermodel specifies a domain with two members, $0$ and $1$. The predicate $F$ is ...


2

Note: I might be missing something since the question is tagged model-theory. Please downvote and leave comments accordingly. For every $m \in \Bbb Z$ there exists one and only one homomorphism mapping $(\Bbb N,+)$ to $(\Bbb Z,+)$ such that $\tag 1 1 \mapsto m$ It sounds like the OP's definition of a homomorphism between two ordered sets is any increasing ...


2

The proof of this has two main components: Quantifier elimination for ACVF (in an appropriate language). This allows us to understand all of the definable sets in one free variable. In particular, ACVF has a property called C-minimality, which says that all definable sets in one free variable have a certain form. The fact that NIP can be checked for ...


2

Yes, this is true, and even in simple theories (every stable theory is simple). This is already stated in this answer, but there is no proof there. So let's do that. I am not sure what definition of independence you use, but we can work with just its properties (which hold in any simple theory): Algebraic closure: for any $c$ and $A$ we have $c \overset{\...


2

Without distributivity, these axioms are extremely weak and so there are lots of ways to get strange algebras. For instance, you can start with any structure $A$ over the language $\{0,1,\wedge,\vee\}$ satisfying the identity and commutative axioms (so just any set together with two commutative operations which have identity elements!) and then consider $B=...


2

Having spent some months with a couple of (philosophy!) grad students on Shoenfield's first three chapters, I have to say that I agree with Smith's criticisms. Shoenfield is a great book, but it is extremely terse and it is sometimes hard to understand what the point of a certain proof is or why he is tackling a certain topic at that precise moment in the ...


1

When you think of $\phi(a_1,...,a_n)$ as a sentence $\psi$ in the language $\mathcal{L}(S)$, the $a_i$'s are not just arbitrary constant symbols--they are specifically the constant symbols corresponding to the elements $a_i$ of $S$. So, when you then interpret the same sentence in the structure $(\mathcal{B},f(a))_{a\in S}$, these constant symbols get ...


1

Here's another argument, working directly from the definitions of forking and dividing. So it holds in any theory (I won't assume stability or simplicity). Let $B = \text{acl}(A)$. (1) A formula $\varphi(x,d)$ divides over $A$ if and only if it divides over $B$. If $I = (d_i)_{i\in \omega}$ is a $B$-indiscernible sequence with $d_0 = d$ witnessing ...


1

In his answer, Alex Kruckman points out the excellent reference: Eklof and Fischer, The elementary theory of abelian groups. Let me just spell out what can be gleaned from this. They recover Szmielew's result that any abelian group $A$ is characterized up to elementary equivalence by the following four families of elementary invariants: The torsionfree ...


Only top voted, non community-wiki answers of a minimum length are eligible