Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models.

learn more… | top users | synonyms

6
votes
3answers
859 views

Tractability of forcing-invariant statements under large cardinals

It is usual to mention theorems of the kind: Th. Assume there is a proper class of Woodin cardinals, $\mathbb{P} $ is a partial order and $G \subseteq \mathbb{P}$ is V-generic, then $V \models \phi ...
3
votes
5answers
981 views

Defining 'free monoid' without Nat?

Is there a definition of what is a 'free monoid' which does not pre-suppose that the natural numbers has already been defined? The definitions that I have been able to track down all use the natural ...
7
votes
2answers
880 views

Complete theory with exactly n countable models?

For n an integer greater than 2, Can one always get a complete theory over a finite language with exactly n models (up to isomorphism)? There's a theorem that says that 2 is impossible. My ...
9
votes
0answers
236 views

“Fraïssé limits” without amalgamation

All structures are countable with countable signature. Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated ...
7
votes
1answer
194 views

Is there a forcing closure?

The main theorem of forcing says that for any c.t.m of $ZFC$ like $M$ and for all partial order $\mathbb{P}$ and $\mathbb{P}$-generic $G$ over $M$, there is a c.t.m of $ZFC$, like $N$ such that $N$ is ...
1
vote
1answer
438 views

Compactness and completeness in Gödel logic

The standard proof of the completeness theorem in first-order Gödel logic is based on a first-order countable language. I want to know that is there any proof of the completeness theorem in ...
0
votes
1answer
165 views

relatively free groups in $Var(S_3)$

Suppose $S_3$ is the symmetric group of order 6. Which elements of the variety $Var(S_3)$ are relatively free? This question is related to my previous question Relatively free algebras in a variety ...
52
votes
4answers
2k views

Is there a 0-1 law for the theory of groups?

Several months ago, Dominik asked the question Is there a 0-1 law for the theory of groups? on mathstackexchange, but although his question received attention there is still no answer. By asking the ...
24
votes
15answers
4k views

What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less ...
21
votes
6answers
5k views

What are some proofs of Godel's Theorem which are *essentially different* from the original proof?

I am looking for examples of proofs of Godel's (First) Incompleteness Theorem which are essentially different from (Rosser's improvement of) Godel's original proof. This is partly inspired by ...
14
votes
3answers
3k views

In model theory, does compactness easily imply completeness?

Recall the two following fundamental theorems of mathematical logic: Completeness Theorem: A theory T is syntactically consistent -- i.e., for no statement P can the statement "P and (not P)" be ...
16
votes
10answers
2k views

Completeness vs Compactness in logic

One standard approach to showing compactness of first-order logic is to show completeness, of which compactness is an easy corollary. I am told this approach is deprecated nowadays, as Compactness is ...
24
votes
4answers
2k views

Illustrating Edward Nelson's Worldview with Nonstandard Models of Arithmetic

Mathematician Edward Nelson is known for his extreme views on the foundations of mathematics, variously described as "ultrafintism" or "strict finitism" (Nelson's preferred term), which came into the ...
19
votes
6answers
2k views

Reasons to believe Vopenka's principle/huge cardinals are consistent

There are a number of informal heuristic arguments for the consistency of ZFC, enough that I am happy enough to believe that ZFC is consistent. This is true for even some of the more tame large ...
8
votes
4answers
2k views

Incompleteness and nonstandard models of arithmetic

The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome. Reading Peter Smith's "Gödel Without (Too Many) ...
25
votes
3answers
640 views

Is the field of constructible numbers known to be decidable?

By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
24
votes
3answers
2k views

Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. Is ...
10
votes
3answers
1k views

Is non-connectedness of graphs first order axiomatizable?

A recent question asked for graph properties that are first order axiomatizable but not finitely axiomatizable. Connectedness was mentioned in the context. Connectedness can be axiomatized in ...
10
votes
3answers
875 views

Intuitionistic Lowenheim-Skolem?

Is there a version of the Löwenheim-Skolem theorem in intuitionistic logic? I'm particularly interested in the "downward" form. The standard proof I know uses the Tarski-Vaught test for ...
4
votes
6answers
3k views

A book about model theory

I am looking for a good book about model theory. As this is obviously too vague, let me explain what I am looking for and why. First I am interested about the basics and foundations of model theory. ...
19
votes
3answers
1k views

The Closure-Complement-Intersection Problem

Background Let $A$ be a subset of a topological space $X$. An old problem asks, by applying various combinations of closure and complement operations, how many distinct subsets of $X$ can you ...
13
votes
2answers
897 views

When does Vopěnka's principle hold?

Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with ...
8
votes
2answers
2k views

Non-standard models of finite set theory

It is well known how the intended model and how the (countable) non-standard models of arithmetic look like. It's also well known how the intended model of set theory with the axiom of infinity ...
5
votes
2answers
870 views

A question about open induction

An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
4
votes
2answers
439 views

Are the types of nonstandard natural numbers within a Z-chain identical?

Hi, I was wondering how much (if anything) $\mathcal{L}_{PA}$ can express about individual nonstandard elements in a nonstandard model of PA. For instance, presumably it can say that each has ...
4
votes
1answer
1k views

Least ordinal not in a countable transitive model of ZFC

Frequently it is useful do deal with countable transitive models M of ZFC, for example in forcing constructions. The notion of being an ordinal is absolute for any transitive model, so certainly if ...
10
votes
3answers
1k views

How does categoricity interact with the underlying set theory?

Here's the setup: you have a first-order theory T, in a countable language L for simplicity. Let k be a cardinal and suppose T is k-categorical. This means that, for any two models M,N |= T of ...
5
votes
1answer
287 views

Is there any o-minimal expansion of the real field with functions of growth higher than exponential?

Let $\bar{\mathbb{R}}$ be the structure of the real field, that is $(\mathbb{R},0,1,+,-,*,<)$ . We say that a function $f$ is of growth higher than exponential if for all $N\in \mathbb{N}$ there ...
7
votes
6answers
536 views

Applications of forcing in model theory

What are the major applications of (set theoretic) forcing in model theory?
7
votes
1answer
1k views

Is the first-order theory (with =) of real numbers with addition and multiplication complete and decidable?

Due to Andreas Blass's answer to my question "Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?", i have now investigated real closed fields (RCF), because i ...
6
votes
4answers
662 views

Self-defining structures

The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed. But consider derived ...
1
vote
1answer
227 views

A Special Pair of Formulas

Consider the first order language ‎$‎‎‎\mathcal{L}=\{\in,\subseteq\}‎$ and ‎$‎‎\{\in\}$-theory ‎$\text{ZFC}$.‎ ‎Is ‎the‎re a formula ‎$‎‎\psi ‎(x,y)‎ \in \{\subseteq\}-Form‎$ ‎with ‎the ‎following ...
1
vote
1answer
254 views

Self-containing graphs

[Second try, after this question failed.] Let me sketch a notion of self-containing structures by a simple example. Consider the class $\Gamma$ of finite or countable digraphs ("graphs" for short) ...
1
vote
1answer
336 views

Riemann hypothesis for zeta function of definable sets over finite fields

Hi, Consider the zeta function of a definable set over a finite field. More precisely, let $\varphi$ be a formula in the language of fields and let $X$ be a definable subset of $F^n$ given by ...
1
vote
1answer
450 views

Completeness of Algebraically Closed Valued Fields(ACVF) Theory

One can prove Elimination of Quantifiers of ACVF finding an extension of any partial embedding of a model $K$ into a $|K|^+$ Saturated one using the language $\mathcal{L} = ( 0,1,+,*, U, \mid )$. In ...
0
votes
1answer
346 views

Recursive Non-standard Models of Modular Arithmetic? [closed]

Any algebraically closed field (ACF) is a model of Modular arithmetic (MA). (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists ...
8
votes
3answers
617 views

Categoricity in second order logic

Hi, It's shown by an easy cardinality argument that there are complete second-order theories that are not categorical (have more than one model up to isomorphism). Anyone knows of a concrete example ...
6
votes
1answer
440 views

(Finite) Models of two subtheories of Peano Arithmetic

Consider first-order theory (with identity) of Peano Artithmetic built in the language $\{S,+,\times,0\}$ and with the following set of axioms: \begin{align} \neg Sx&=0\tag{1}\\\ ...
6
votes
4answers
718 views

Example of two structures

This is probably a very trivial question, still I don't seem to find an answer. I'd like to see an example (in some language) of two countable structures $\mathcal{M}_1 $ and $ \mathcal{M}_2 $ with ...
5
votes
1answer
314 views

How do we know if Vaught's Conjecture is Absolute?

Please note that this might be some confusion on my part about the work surrounding Vaught's conjecture. First of all, Vaught Conjecture states that if a first-order complete theory $T$ in a ...
5
votes
1answer
369 views

Elementary end extension of a countable model for ZF

Theorem 2.2.18 in Chang and Kiesler uses omitting types to show that any countable model of ZF has an elementary end extension. Can we control the countable order type of such a model? for example, if ...
5
votes
0answers
905 views

Undecidability degree of some elementary theories (two equivalence relations, …)

I have a question about some results in the paper I. A. Lavrov. Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain theories (in Russian). ...
4
votes
0answers
116 views

Is the lowenheim-skolem number of nth order logic larger than the corresponding number for 2nd order logic

According to this paper, by Vaananen, the $LS$ number for $2^{nd}$ order logic is given by "the supremum of $Π_{2}$-definable ordinals", where "The Lowenheim-Skolem number $LS(L)$ of $L$ is the ...
3
votes
1answer
166 views

Number of non-isomorphic models

I had this question up on Math stackexchange: http://math.stackexchange.com/questions/1349247/number-of-non-isomorphic-models/1350763#1350763 . While it was answered partially there, I'm posting here ...
3
votes
2answers
465 views

Cantor theorem on orders

It is "a well-known theorem of Cantor", said Sierpinski (circa 1920), that every countable total order can be imbedded in the rationals, and he proceeds to demonstrate that, assuming the continuum ...
2
votes
2answers
363 views

The category of Boolean-valued models associated to a model of ZFC

This is related to my previous question here, and indirectly motivated by Andreas Blass intriguing answer therein: start from a ZF transitive model $M$, and consider the category $CBA(M)$ of ...
1
vote
1answer
146 views

How can one define the direct limit of classes?

If we have a family of classes $(\mathfrak{M}_\alpha)_{\alpha\in D}$ of $\in$-structures with $D$ being a limit ordinal or the class of ordinals, and a family ...
1
vote
2answers
287 views

Embedding of consistent subset in first order logic (finitely many variables)

I am looking at FOL with no equality, no constant, no function symbol and the unique binary predicate $\in$ with variables in arbitrary sets $V$ or $W$. Specifically we define ${\bf P}(V)$ as the free ...