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

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
96 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
96 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
51 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
65 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
73 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
45 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
88 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
154 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
108 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
100 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
327 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
53 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
59 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 ...
1
vote
1answer
85 views

Existential theory

We have that a formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it is of the form $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l)$$ where the formula ...
3
votes
1answer
44 views

Is there an overview of possible order types of fragments of first-order arithmetic?

I know, that there aren't many results on order types of arithmetic fragments. E.g. there are some basic results which one can find in texts of Kaye and Bovykin. But does anyone know, if there is ...
-3
votes
1answer
47 views

Let $T$ be a set of closed literals of signature $L$. Show that a) is equivalent to b). Why is this not plainly false?

Let $T$ be a set of closed literals of signature $L$. Show that a) is equivalent to b). a) Some $L$-structure is a model of $T$. b) If $\neg \phi$ is a negated atomic sentence in $T$, then $\phi$ ...
0
votes
1answer
48 views

ZFC,unprovability of existence of a countable model,Skolem construction and paradox

The well-known Skolem construction yields a countable model of ZFC,elemetarily equivalent to the universe of sets $V$.Why this construction is not a proof of existence of models of ZFC,as such proofs ...
4
votes
1answer
91 views

The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$

I am a complete newcomer to logic and I'm having trouble proving the following: The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$. Now, I know that the $<$-relation on ...
3
votes
1answer
75 views

Compactness theorem aplication

I have one problem and I m sure that can be solved by using compactness theorem but I cant solve it. Let $T$ be an $L$-theory and $\{F_i (x) \mid i\in I\}$ family of $L$-formulas. Suppose further ...
3
votes
2answers
76 views

Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$

Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$ This is from Hodges' A Shorter Model Theory. My idea is to take ...
0
votes
1answer
62 views

Sentence $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements

I'm trying to prove this result: For any natural number $n \geq 1$ there is a sentence $\phi_n$ such that $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements. My attempt: By induction ...
0
votes
1answer
34 views

Definition of prime model extension over a set

Standard definition of prime model over a set is that: $M\vDash T$ is said to be a prime model extension of a set $A$ if $A\subset M$ and any partial elementary map $A\rightarrow N$ ($N\vDash$) extend ...
2
votes
2answers
97 views

How does the Soundness Theorem follow from this lemma?

The soundness theorem is a famous theorem in logic that goes like this: If $\Gamma \vdash \phi$, then $\Gamma \vDash \phi$. It's supposed to follow readily from Lemma 3.2.3 from Moerdijk/Van ...
0
votes
1answer
38 views

Is the theory of real closed fields expanded by restricted analytic functions decidable?

Is the theory of real closed fields expanded by restricted analytic functions decidable? I have been doing a lot of reading on the subject, but I can't quite find a straight answer on this one. The ...
0
votes
1answer
72 views

Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

I'm stuck with a question: Proof that you can't express if a graph is cyclic in first-order logic. The definition of cyclic is that for every node there is a ...
0
votes
1answer
44 views

Doubt about the proof on uniqueness of saturated model

A standard proof for the fact that any 2 saturated models of the same cardinality are isomorphic can be found here But I have doubt about this. Specifically, the construction of the next partial ...
2
votes
1answer
98 views

Why are algebras classified as being of a certain type?

In Grätzer's, Universal Algebra, page 33, Grätzer defines the concept of an algebra of type $\tau$, as follows: An algebra $\mathfrak{A} = \langle A ; F \rangle$ of type $\tau$ is a pair, where ...
1
vote
0answers
37 views

How can a structure for a formal language be defined? [duplicate]

I'm learning some stuff about formal languages and structures for them. However there's this thing I don't understand. How can we ever define/specify a structure for a language, if we do not yet have ...
0
votes
0answers
73 views

“there are infinitely many” with finitely many variables

I vaguely recall reading somewhere that one cannot say "there are infinitely may" using a formula with only finitely many variables. A bit more precisely, let $\mathcal L$ be the result of extending ...
1
vote
1answer
37 views

Finite set of formulas from $L(A)$ is realized iff it is consistent with $Th(\mathfrak{A})$

Let $\mathfrak{A}$ be an $L$-structure with domain $A$. If $\Sigma$ is a finite set of formulas in $L(A)$, how can I prove that $\Sigma$ is realized in $\mathfrak{A}$ iff it is consistent with ...
3
votes
1answer
77 views

Are the hyper-reals countably transitive?

A hyper-real field is $ R^*=(R^N)_{/U}$ where $U$ is a free ultrafilter on $N$. If A and B are any countable order-isomorphic subsets of $R^*$, is there an order-automorphism of $R^*$ that maps $A$ ...
6
votes
2answers
109 views

Defining the existence of a non algebraic element in the language $L:= \{0,1,+,\cdot\}$

I raise following question after reading this post. Is it possible in the language $L:= \{0,1,+,\cdot\}$ to write sentences for which a model will necessarily contain a copy of $\mathbb Q$ and a non ...
5
votes
1answer
69 views

Can this sequence be a hyperreal number? What would be its real part?

Consider the sequence $\{a_n\} = \{\sin(n) \mid n\in \mathbb N \}$. Can this sequence be viewed as a hyperreal number? What could be its real part? Any intuition would be highly appreciated :) ...
1
vote
1answer
86 views

(Sphere Lemma) Hanf locality Lemma and locally threshold testability

I am reading the proof of Hanf's Sphere Locality lemma for (finite or infinite structures but with bounded degree), and I'm trying to understand the details of the proof! I'm confused with the ...
2
votes
1answer
64 views

Local isomorphism question in logics

The definition of a local isomorphism between structures: a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ ...
5
votes
1answer
85 views

Given any set of consistent axioms, is it always possible to find a model for these axioms in ZFC set theory?

If not, are there any conditions under which there must be a model under ZFC theory? Alternatively, is there any set of axioms for which this does hold true? If so, can we drop some of the axioms and ...