Questions tagged [model-theory]
Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models.
1,205
questions
12
votes
2
answers
6k
views
Is it possible to show that an infinite set has a countable (infinite) subset, without using the Axiom of Choice?
Let X be an infinite set.
Is it possible to show the existence of a countably infinite subset of X without using the Axiom of Choice?
- 185
1
vote
1
answer
400
views
Elementary Theory of Finite Linear QuasiOrders
It is well known that the elementary theory $Q_{fin}$ of finite quasiorders is undecidable. To be more precise, it is undecidable whether a first-order sentence built using a binary relational symbol $...
- 788
23
votes
7
answers
2k
views
Supervenience in mathematics
I'm not quite sure if this is the right place to ask, and if this is the right way to ask, but I dare.
In philosophy (of mind, e.g.) the concept of supervenience is used:
"Supervenience [is] used ...
- 9,628
10
votes
1
answer
921
views
Non-standard enlargements, $\zeta(s)$ and analytic continuation
Consider an extension of the Riemann zeta function $\zeta(s)$ where $s$ now runs over a non-standard enlargement of the complex plane.
Observe that if $s=\sigma + it$ with $\sigma>1$ real and ...
- 17.5k
12
votes
7
answers
3k
views
Use of indiscernibles in model theory
What is the main use of indiscernibles in model theory? reading through Chang and Keisler's Model Theory it seems that the main motivation for indicernibles is for getting many non-isomorphic models ...
- 659
0
votes
2
answers
3k
views
How many models are there, for a particular propositional modal logic?
Background/motivation: A model for the classical propositional calculus is a boolean function b(S) which assigns 1 or 0 to each (modal-free) sentence S according to the usual rules. I'm looking at ...
- 327
4
votes
0
answers
369
views
Sentences Preserved by Direct Products (including the Empty Product)
Consider the class of all structures for a given signature in first-order logic. Let $S_i$ be a family of structures, and $\oplus S_i$ be the direct product of the family. You can extend the notion ...
- 6,720
6
votes
1
answer
632
views
Which properties of ultrafilters on countable sets hold for filters in general?
Background/motivation: I'm investigating the construction of models for a first-order modal system (S5) as products of classical models. Since ultraproducts are all classical models and I need non-...
- 327
6
votes
7
answers
5k
views
Compactness Theorem for First Order Logic
Hi all,
I am interested in proofs without using Goedel's completeness theorem.
Does anyone have a reference to a proof of this theorem that uses Skolem Functions?
How come Enderton's (Introduction to ...
- 659
2
votes
3
answers
2k
views
Large Cardinals Imply a Model of ZFC
I've run across the statement, "The existence of a strongly inaccessible cardinal implies the consistency of ZFC" in several places (Cohen's Set Theory and the Continuum Hypothesis p. 80, for one). ...
11
votes
2
answers
2k
views
What is a good example of a complete but not model-complete theory, and why?
The standard examples of complete but not model-complete theories seem to be:
- Dense linear orders with endpoints.
- The full theory $\mathrm{Th}(\mathcal{M})$ of $\mathcal{M}$, where $\mathcal{M} = (...
- 5,440
4
votes
1
answer
153
views
Example or classification of existentially closed modules
In the language of modules, it suffices to restrict our view to positive-primitive formulas - that is to say, formulas with one existential quantifier and no negation.
And I mean existentially closed ...
- 335
3
votes
0
answers
280
views
Semantics of neural network-like structures
Background
Language (of mathematicians and most other people) has a sequential surface structure and a tree-like deep structure. So semantics usually is the semantics of such syntactical structures: ...
- 9,628
6
votes
3
answers
908
views
Metric spaces as algebraic systems
Let $(X, {\mathrm{dist}})$ be a metric space. In the paper by Kramer, Shelah, Tent and Thomas , they define an algebraic system $A(X)$ as the set $X$ with countably many binary relations $R_\alpha$, ...
user6976
10
votes
5
answers
2k
views
The use of the word "model" in Mathematical Logic vs the same word in Natural Sciences [closed]
I have always been wondering
why the term "model" is used by mathematicians (especially in mathematical logic) in a conceptually different (even opposite) way than it is used by other scientists, ...
- 22.7k
9
votes
3
answers
566
views
Statistics for Second order properties of Random graphs
Hi!
Let G(N) be the number of graphs with vertices {1, 2, ..., N} and GN(F) be the number of those of them which satisfy graph property F. There is a beautiful result by Glebskii and Fagin that limit ...
- 1,177
4
votes
1
answer
559
views
Statements that require the existence of non-standard models to hold
From the Incompleteness theorems, if ZF is consistent, one knows there are models of ZF satisfying ¬Con(ZF). These models must be non-standard (in the sense of being models whose ordinals are not well-...
- 1,475
5
votes
2
answers
2k
views
Existence of an $\omega$-nonstandard model of ZFC from compactness
I have read several times that assuming Con(ZFC), and using compactness it can be proved the existence of a model of ZFC with an ill-founded $\omega$. How is that? Any reference will be welcome.
- 1,475
6
votes
2
answers
470
views
Reconstructing a model from its definable sets
Let $\mathcal{M}$ be an infinite model of a first-order language, and for each $n$, let $\mathcal{B}_n$ be the algebra of definable sets of $n$-tuples from $|\mathcal{M}|$.
Given $\{\mathcal{B}_n\mid ...
- 7,135
18
votes
2
answers
3k
views
Universe view vs. Multiverse view of Set Theory
Here I refer to Hamkins' slides:
http://lumiere.ens.fr/~dbonnay/files/talks/hamkins.pdf
particularly, to the "Universe view simulated inside Multiverse", p. 22.
My question is: is it very unsound ...
- 1,475
13
votes
4
answers
839
views
(Finite) Classification Theory
In the context of asking about the classification of finite simple groups, the question arose: what exactly is meant by a "classification"?
Perhaps unsurprisingly, there is in fact a whole branch of ...
- 61.6k
1
vote
1
answer
356
views
Convergence of the harmonic series in larger fields
The Harmonic series is well known and its divergence was proven back in the middle ages.
I've taken an introductory course in model theory so I know a bit about RCF and some properties of it. We did ...
- 38.2k
66
votes
5
answers
6k
views
Heuristic argument that finite simple groups _ought_ to be "classifiable"?
Obviously there exists a list of the finite simple groups, but why should it be a nice list, one that you can write down?
Solomon's AMS article goes some way toward a historical / technical ...
- 61.6k
4
votes
2
answers
405
views
Is there a model theoretic realization of the concept of Arithmetical Hierachy?
The question I want to ask is close to but not exactly what stated in the title:
Fix a language $L$, it is known that a statement $\sigma$ is universal in the language if whenever $M$ satisfies $\...
- 2,744
19
votes
2
answers
978
views
Which graphs are elementarily equivalent to their own disjoint sums?
In Stefan Geschke's recent
question,
one of the solutions observed that the graph consisting of
a single infinite beaded chain, a $\mathbb{Z}$-chain where
each integer is connected to its nearest ...
- 225k
25
votes
2
answers
3k
views
Is there a known natural model of Peano Arithmetic where Goodstein's theorem fails?
(I've previously asked this question on the sister site here, but got no responses).
Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It turns out that this ...
- 6,466
0
votes
1
answer
233
views
Models for the given FOL statement
Consider the following FOL sentence:
$\phi = \exists x \forall y \exists z ((x=y) \lor (P(x,y,z) \land \lnot P(y,x,z) ) $
It can be proven that for any natural number n > 0 there exits a model of ...
14
votes
3
answers
3k
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 ...
- 16.4k
7
votes
1
answer
629
views
Model theory stressing order type of universe.
In Appendix B to their Model Theory, Chang and Keisler list some problems and conjectures that, at the time of publication, were unsolved. A few of them take imperative form, for instance:
"Develop a ...
- 1,101
3
votes
3
answers
945
views
Models within a model of set theory
Assume (M,∊M) is a model of ZF. Assume also that (n,∊n) ∊ M is a model in the sense of M and (N,∊N) is a model in the real world with the property that for all sentences σ...
- 357
45
votes
8
answers
9k
views
What is Realistic Mathematics?
This post is partially about opinions and partially about more precise mathematical questions. Most of this post is not as formal as a precise mathematical question. However, I hope that most readers ...
- 25.3k
4
votes
2
answers
225
views
Modal models as reduced products?
In model theory for standard first-order logic, one constructs a single model, a reduced product, from a collection of first-order models, together with an index set and a filter on the index set.
In ...
- 327
12
votes
2
answers
2k
views
Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition
I recently saw the proof of the independence of ZF (with allowance for multiple empty sets) and AC. The proof constructed the model based on a set theory generated by infinitely many empty sets and ...
- 15.1k
2
votes
3
answers
428
views
Undecidable completion of undecidable theory, and pairs of RCF
Given an undecidable collection of first-order sentences, is there necessarily a complete undecidable theory containing it? A direct attempt to prove it seems to require some control over the ...
- 361
10
votes
4
answers
1k
views
Complete extensions of first order logic (or language)
Lindstrom's theorem states that any extension of first order logic (FOL) more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first ...
- 1,177
6
votes
3
answers
876
views
Fraissé limit of the finite linear orderings
Hodges in his Shorter Model Theory promises to show "in what sense the finite linear orderings 'tend to' the rationals rather than, say, the ordering of the integers" (p. 160). After going through his ...
- 9,628
7
votes
2
answers
845
views
Are computable models sufficient?
What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in ...
- 1,177
14
votes
3
answers
2k
views
Intuition for Model Theoretic Proof of the Nullstellensatz
I recently read the model-theoretic proof of the Nullstellensatz using quantifier elimination (see www.msri.org/publications/books/Book39/files/marker.pdf). I'm convinced that the Nullstellensatz is ...
- 15.1k
2
votes
2
answers
735
views
Confusion about model theory notes
On p.8 of http://www.msri.org/publications/books/Book39/files/marker.pdf, the author writes $\Gamma(\bar{d})$, when $\Gamma$ is, first of all, a set of formulas (not a single one), and it is a formula ...
- 15.1k
10
votes
1
answer
367
views
Extra assumption in Hodges' lemma on the resultant of a first-order formula?
Background
I am working through a particular result in a paper of Cherlin, Shelah, and Shi, and am satisfied that it follows from basic model theory material - but I'm stuck on one point in the ...
- 354
21
votes
6
answers
2k
views
Three questions on large simple groups and model theory
Yesterday, in the short course on model theory I am currently teaching, I gave the following nice application of downward Lowenheim-Skolem which I found in W. Hodges A Shorter Model Theory:
Thm: Let $...
- 64.8k
8
votes
3
answers
1k
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 \...
- 1,475
4
votes
0
answers
305
views
To what extent MSO = WS1S, when adding relations?
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...
- 776
8
votes
2
answers
966
views
Weakest subsystems of second order arithmetic for mathematical logic
It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...
- 1,475
25
votes
3
answers
3k
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 ...
- 43.7k
5
votes
2
answers
738
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 $k$-...
- 145
10
votes
2
answers
1k
views
Cohomology Theories on The Stone Space of Complete n-types
Just a random thought here: Can cohomology theories (e.g. sheaf cohomology) on the Stone space $S_n(T)$ (the space of complete n-types) of a first-order theory $T$ tell us anything interesting (e.g. ...
- 468
32
votes
6
answers
5k
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 ...
- 19.4k
2
votes
1
answer
259
views
Relation between different definitions of types [closed]
Is there any connection between the definition of type in model theory and the definitions from type theory? Is there any explanation why the same term is used for these notions, maybe in the ...
- 141
7
votes
2
answers
3k
views
How to think like a set (or a model) theorist.
Kenneth Kunen in his “The Foundations of Mathematics” writes:
‘Set theory is the study of models of ZFC’ (p. 7)
‘Set theory is the theory of everything’ (p. 14)
With (1) Kunen is pointing to a ...
- 1,475