# Tagged Questions

**3**

votes

**5**answers

908 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 ...

**6**

votes

**2**answers

773 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 ...

**7**

votes

**1**answer

184 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 ...

**6**

votes

**0**answers

171 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 ...

**0**

votes

**1**answer

149 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 ...

**23**

votes

**15**answers

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 ...

**20**

votes

**6**answers

4k 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 ...

**12**

votes

**3**answers

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 ...

**15**

votes

**10**answers

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 ...

**17**

votes

**6**answers

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 ...

**24**

votes

**3**answers

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

**3**answers

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

**4**answers

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

**6**answers

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. ...

**22**

votes

**3**answers

508 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, ...

**19**

votes

**3**answers

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 ...

**6**

votes

**3**answers

707 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 ...

**5**

votes

**2**answers

841 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

**1**answer

973 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

**3**answers

929 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

**2**answers

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

**1**answer

260 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 ...

**6**

votes

**4**answers

653 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

**2**answers

319 views

### Applications of forcing in model theory

What are the major applications of (set theoretic) forcing in model theory?

**3**

votes

**2**answers

327 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

**1**answer

220 views

### A Special Pair of Formulas

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

**1**

vote

**1**answer

250 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

**1**answer

332 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

**1**answer

303 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

**3**answers

575 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

**1**answer

690 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

**1**answer

413 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}\\\
...

**5**

votes

**0**answers

834 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

**2**answers

418 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

**1**answer

134 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

**2**answers

268 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 ...