Model theory is the study of (classes of) mathematical structures (e.g. groups, fields, graphs, universes of set theory) using tools from mathematical logic. Objects of study in model theory are models for formal languages which are structures that give meaning to the sentences of these formal ...

learn more… | top users | synonyms

6
votes
1answer
98 views

How do inconsistent arithmetics get around Gödel incompleteness?

Gödel theorems imply that arithmetic can not be complete under recursive axiomatization and consistency assumptions. Unexpectedly, consistency can be dropped in a meaningful way by switching to a ...
2
votes
1answer
93 views

Understanding countable elementary submodels

So I'm having some trouble understanding the existence of countable elementary submodels. I have read and understand the Löwenheim–Skolem theorem, so given a model I understand how to build a ...
2
votes
1answer
76 views

Is the use of the meta-meta-theory allowed in proving an independence result?

I am wondering about the use of a meta-meta-theory in proving statements of the form "$\phi$ is independent of $\mathcal{T}$" in mathematical logic. Short question: Is using a result from the ...
0
votes
1answer
42 views

Simple proof that Automorphisms preserve definable subsets?

I've been looking all over for a proof of this result, but I haven't really found anything. Is anyone aware of a particularly simple or elegant one?
2
votes
1answer
58 views

Why isn't $\leq$ definable in $(\mathbb{R};0,+,-)$?

Are there any simple and straightforward proofs of this fact? I'm not really sure how to begin to approach the problem.
1
vote
0answers
41 views

Automorphisms and Definable subsets?

I'm trying to show that if we have a structure $\textbf{A}$ and $C\subseteq A$, with an $\mathcal{L}_C$ formula $\varphi(x)$ defining the set $S$ in $\textbf{A}$, then for any given automorphism ...
0
votes
1answer
34 views

Is logical implication examining only the syntatical component?

As my title asks, is logical implication only examining the syntatical compinent of the formal language? I am using Enderton's book on Mathematical Logic in my class and after some work I am ...
3
votes
1answer
52 views

Show the inequality $x <y$ is definable in the language $\langle \mathbb{R}; +, \times ; 0,1 \rangle $

My initial idea is that I need to find a sentence that expresses 'x is positive' and then I can say: for any $a, b$, $a>b$ iff there is a positive x s.t. $b+x=a$, but can't figure out how, any ...
3
votes
1answer
49 views

A simple proof that elementary equivalence and isomorphism coincide for finite structures?

I'm wondering if there's a straightforward proof of this result I've seen mentioned in quite a few places. If $\mathcal{L}$ is finite, of course, this is trivial since there's a single formula that ...
1
vote
1answer
54 views

First-order definition of “$f$ is continuous at $x$” using just $<$

I need to show that the set $\{ a\in \mathbb{R}\ |\ f\ \text {is continuous at a}\}$ is definable in the structure $(\mathbb{R};<,\ f)$, where $f$ is just some function ...
1
vote
1answer
35 views

Prove that this theory is incomplete

Given $\Sigma = \{\forall x \forall y \forall z(x \circ (y \circ z) = (x \circ y) \circ z), \forall x (x \circ e = x), \forall x \exists y (x \circ y = e)\}$ (eg. group theory axioms), I need to prove ...
1
vote
0answers
73 views

Prove that there exists a non-standard model of arithmetic

Specifically, I need to show there exists a structure $\mathcal{Z}'$ that is elementarily equivalent to $ \langle \mathbb{N} ; <; \cdot ; 0,1 \rangle $ (the standard model of arithmetic) but is not ...
1
vote
1answer
41 views

Relation between homogeneity and categoricity

Define a structure $\mathcal{A}$ as homogeneous if, for every two substructures $\mathcal{B}, \mathcal{C}$ of $\mathcal{A}$, if $f: B \to C$ is an isomorphism, then $f$ extends to an automorphism of ...
3
votes
1answer
62 views

Is a theory elementary iff it is categorical? [closed]

If an elementary class is the set of structures satisfying a theory, and a theory is categorical if it determines a structure up to an isomorphism, it would seem that the two concepts are related, no? ...
5
votes
0answers
58 views

bi-interpretability and automorphism groups

Let $M$ and $N$ be two first order structures, say they are countable and $\aleph_0$-categorical. Then $M$ and $N$ are bi-interpretable if and only if their automorphism groups $Aut(M)$ and $Aut(N)$ ...
2
votes
1answer
62 views

Show the only definable subsets of $ \langle \mathbb{Q} , < \rangle $are the empty set and $ \mathbb{Q} $

I'm trying to show the above, and I know it should be quite simple, but I'm struggling to get my head around how you show subsets are not definable using automorphisms- so a detailed explanation would ...
2
votes
1answer
46 views

DOP, Shelah, Clarifying the definition

I'm trying to understand Shelah's prototypical example of DOP here on page 26, item (c). It would be a very nice example if correctly understood.However, there is some strange mixture in the ...
6
votes
1answer
106 views

Integer parts isomorphic?

Let $F$ be a real closed field. It is known$^{[1]}$ that $F$ has an integer part, that is, a subring $A$ such that $\forall x \in F, \exists ! a \in A, a \leq x < a+1$. Are all integer parts over ...
1
vote
0answers
89 views

Calculus as a structure in the sense of Model theory

I am not a specialist in Logic (my field is Functional Analysis), so excuse me my ignorance. I suppose there must be texts where Calculus is presented as a structure in the sense of Model theory. I ...
0
votes
0answers
45 views

Quantifier elimination in the structure of exponential sums

We consider the language $L=\{+, -, ' , T, 0, 1\}$ Let $\text{Exp}(\mathbb{C})$ (the exponential sums) be the structure in that we interpret $L$. We define $\text{Exp}(\mathbb{C})$ as the set of ...
2
votes
2answers
56 views

Exercise 1.2.10 from Model Theory by Chang and Keisler.

I am reading Model Theory by Chang and Keisler, and I am having some trouble with exercise 1.2.10, which asks me to prove that if $\Sigma \vdash \varphi$ for all $\varphi \in \Gamma$ and $\Sigma \cup ...
1
vote
1answer
40 views

restriction map in Stone space is open

In the Stone space, how to proof that the restriction map $S_{m+n}(B)\to S_{n}(B)$ is open? Where B is subset of the model of the theory. I know that the restriction is continuous and surjective.
4
votes
1answer
136 views

Is there a countable transitive model satisfying the same set of first-order sentences as $V$? [duplicate]

This is probably a pretty simple question, but I'm tying myself in knots over it. We're all familiar with the Reflection Theorem, Lowenheim-Skolem Theorem, and Mostowski Collapse Lemma for getting ...
2
votes
1answer
46 views

Proving that every interval in an o-minimal structure is definably connected.

By an ordered structure I mean a (first order) structure $\mathcal{M}=(M,<,\ldots)$ that is totally and densely ordered by $<$. An ordered structure $\mathcal{M}$ is o-minimal if every definable ...
3
votes
1answer
68 views

Using the compactness theorem to prove Principal ideal rings nonaxiomatizable

I'm trudging through Barwise's Handbook of Mathematical Logic and came across this: Here is a good exercise. A ring $\mathfrak{R}$ is a principal ideal ring if $\mathfrak{R}$ is a model of the ...
2
votes
0answers
25 views

$R \subseteq M^I$ is $A$-invariant, then $R$ is $A$ definable in the next two infinitary logics.

Let $A \subseteq M$ and let $R \subseteq M^I$ be $A$-invariant. If $M$ is $\kappa^+$-strongly homogenous for $\kappa = |A| + |I|$, then $R$ is $A$-definable in $M$ in the infinitary logic ...
2
votes
1answer
51 views

For $\mathbb{N}$ a structure in $\mathcal{L}=\{s, 0, 1\}$, are the sum and product definable? [duplicate]

Reading about interpretability made me think about the $s$ function that somehow always bothered me in the language of PA. My question is the following Given $\mathbb{N}$ as a structure in ...
0
votes
1answer
43 views

Showing that a certain formula of second order logic with full semantic is true in all and only non-standard model of arithmetic.

Showing that a certain formula of second order logic with full semantic is true in all and only non-standard model of arithmetic. $\exists X(\exists x Xx \wedge \forall x\forall y((Xx \wedge (x=0 ...
1
vote
3answers
65 views

How it can be formally proved that a formula of First Order Logic with identity has only infinite models?

I have an irreflexive and transitive relation $R$. Then I want to prove that $\forall x \exists y (xRy)$ has only infinite models. I have an intuitive idea for which the relation $R$ cannot be ...
-1
votes
2answers
103 views

What's the difference between a model and a $\sigma$ structure?

In model theory, I haven't actually seen the word "model" defined. The only thing I've seen defined is a $\sigma$ structure for some signature $\sigma$. I read phrases like $A$ is a model of some ...
2
votes
2answers
100 views

Infinite, finite and arbitrarily large models.

How is it possible to have a sentence of First Order Logic with identity such that it has both finite and infinite models, but not arbitrarily large models? Edited: (arbitrarily large -finite- ...
0
votes
1answer
33 views

First order theories, interpretation, concrete example, proof

I read a proof that no model of a certain f.o. theory $T_1$ is definable in $(Q,<)$ and I have a problem with understanding the very end of Lemma 3.2 here. "The distance from $\alpha_i$ to ...
0
votes
2answers
53 views

Ultraproduct, axiomatizability,models,finite structures,language of one biary symbol

If we know that first order axiomatizable theories have classes of models in one binary relational symbol $R$,say, closed under ultraproducts, how can I see that finite graphs, i.e. finite models in ...
3
votes
0answers
66 views

Principia Mathematica Part VI “Quantity” vs Part IV “Relation Arithmetic”

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments: "I think relation-arithmetic important, not only as an interesting ...
3
votes
1answer
74 views

General exponential inequality?

The theory $Th_{\exp,\mathrm{fields}}$ of exponential ordered fields is the first-order theory over $\left\langle +,\cdot,0,1,<,\exp\right\rangle$ whose axioms state that the model is an ordered ...
1
vote
1answer
47 views

Automorphism for definable set [duplicate]

In $(\mathbb{R},<)$ $D_{1}:=\{(x,y)\in\mathbb{R}\times\mathbb{R}|\,x<y\} , D_{2}:=\{(x,y)\in\mathbb{R}\times\mathbb{R}|\,x=y\} , D_{3}:=\{(x,y)\in\mathbb{R}\times\mathbb{R}|\,y<x\} ...
0
votes
0answers
26 views

On gluing of sheaves (requirements, modelling and so on).

I am having a look at pages on sheaves and I came accross this nice diagram, which I somehow found appealing for my own thoughts: https://en.wikipedia.org/wiki/File:2_point_sheaf_gluing.svg I have ...
5
votes
2answers
117 views

Is there a constructive approach as a replacement of Henkin's construction?

Henkin's proof for Goedel's completeness theorem that is based on the Henkin construction using term models built by constants is not constructive. My question is whether there is any constructive ...
2
votes
1answer
89 views

List out all the definable set in given model

The problem says: List all the definable subsets of $\mathbb R^2$ in ($\mathbb R$,<) with formulas. And I found $x<y$, $y<x$ and $x=y$ are desired one. But, I want to say that any subset ...
6
votes
1answer
138 views

Is there a logic so powerful it pins down every structure up to isomorphism?

Definitions. By a structure, I mean a set equipped with some finitary operations and finitary relations. By a non-standard model of a structure $X$ with respect to a logic, I mean a model of the ...
1
vote
1answer
36 views

¿countably natural models? [closed]

¿ A set theory can have countably models models that can it be natural models, where ∈ relation in the internal model , it is, can be the real ∈ in the external model?
6
votes
0answers
155 views

Transexponential Functions

Recall that $\exp(1,x) = e^x$ and $\exp(n+1,x) = e^{\exp(n,x)}$. Recall that $f(x)$ is transexponential if $f(x)$ is eventually greater than $\exp(n,x)$ $\forall n \in \mathbb{N}$ I am looking for a ...
4
votes
3answers
110 views

The converse of Vaught's Test

I work in first order logic. I noticed that a complete theory that is satisfied by finite models can only be satisfied by models of a given fixed finite cardinality. It made me think about the ...
3
votes
2answers
101 views

Intermediate Logic Text

I have been self-studying logic and foundations of mathematics for some time. Unfortunately, I struggle to graduate to higher-level work. (I am particularly interested in model theory.) The problem is ...
11
votes
4answers
1k views

How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
6
votes
1answer
347 views

What's an example of a number that is neither rational nor irrational?

Of course in regular logic, the answer is there aren't any. But in intuitionistic logic, there might be, as seen by this answer: http://math.stackexchange.com/a/1437130/49592. My question is, as per ...
3
votes
0answers
54 views

Shepherdson's model for Open Induction

In the paper "A Non-Standard Model for a Free Variable Fragment of Number Theory", Shepherdson constructs a recursive model for a fragment of arithmetic known as "Open Induction". I would like to ...
4
votes
0answers
72 views

Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...
4
votes
1answer
62 views

Where is the (original) proof of Klaus Potthoff's Theorem about the order type of arithmetic models?

I am looking for a complete proof, respectively for the complete original proof of the following theorem, which is attributed to Klaus Potthoff: If $\mathfrak{M}$ is a nonstandard model of PA, ...
0
votes
2answers
76 views

Is the reduction correct?

Is the following formulation of the reduction correct? EDIT: Undecidability of an (positive) existential theory $T$ is proved often by reducing an other (positive) existential theory $T'$, which ...