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

8
votes
1answer
179 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 ...
3
votes
5answers
866 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 ...
0
votes
1answer
145 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 ...
22
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
3k 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 ...
15
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 ...
12
votes
3answers
2k 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
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 ...
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 ...
7
votes
4answers
1k 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) ...
4
votes
6answers
2k 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. ...
6
votes
3answers
674 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 ...
18
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 ...
5
votes
2answers
833 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 ...
10
votes
3answers
889 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 ...
6
votes
2answers
1k 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 ...
4
votes
1answer
944 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 ...
6
votes
4answers
649 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 ...
5
votes
2answers
289 views

Applications of forcing in model theory

What are the major applications of (set theoretic) forcing in model theory?
3
votes
2answers
321 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
246 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
327 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 ...
0
votes
1answer
279 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 ...
7
votes
1answer
404 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}\\\ ...
7
votes
3answers
541 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
521 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 ...
5
votes
0answers
759 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). ...
3
votes
2answers
405 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 ...
1
vote
2answers
259 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 ...