Questions tagged [model-theory]
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 languages. Not to be confused with mathematical modeling.
0
votes
0answers
21 views
About a topological proof of the compactness theorem
I'm trying to prove compactness theorem following this paper https://www.staff.science.uu.nl/~ooste110/syllabi/eric-poizat.pdf.
Let $\mathcal{T}$ be the set of all complete theories over a fixed ...
0
votes
1answer
18 views
if $F\subseteq K$ real closed fields, $b\in K$ algebraic over F then $b\in F$
I'm studying real closed field part in model theory. Because I'm not familiar with abstract algebra, I'm stuck with two (possibly) simple problems. Here are definitions and two problems I'm stuck with....
6
votes
0answers
23 views
First-order definability sums of squares
Let $K$ be a field. I am interested in when there can exist a first-order definition of the set
$$
\Sigma K^2 := \lbrace \sum_{i=1}^n x_i^2 \mid n \in \mathbb{N}, x_1, \ldots, x_n \in K \rbrace
$$
in $...
1
vote
0answers
40 views
Show that these two structures are isomorphic
I'm having difficulty knowing where to start with this question:
Show that:
($\mathbb{Q}(\sqrt{2})$,<)$\cong$($\mathbb{Q}$,<)
0
votes
1answer
34 views
When Does Elementary Equivalence Imply Isomorphic substructures?
I have been reading the proof for the implication that if two $L$-structures are isomorphic then they are elementary equivalent. I've been wondering under what conditions we might prove some version ...
0
votes
1answer
72 views
Definitions in metamathematics
In model theory, the satisfiability relation $ \vDash$ between a model $M= (D,f)$ and a set of formulas tells us when a formula $\varphi$ is true or not in the model ("interpretation") $M$.
This ...
1
vote
2answers
32 views
Definability of sets of a certain form in an ultraproduct
I want to look at countable ultraproducts in a concrete setting.
Specifically, for each $n\in \mathbb{N}$, let $S_n = (A_n, B_n)$ be a finite model where $B_n$ is a binary relation. Let $U$ be a ...
1
vote
1answer
71 views
An exercise in model theory about positive homomorphisms
A formula is called positive if is is built from atomic formulas
using only $\land, \lor, \exists$ and $\forall$. A homomorphism $f : M \to N$
is positive if $$ M \models \varphi(m_1, \cdots, m_n) ...
2
votes
1answer
38 views
How to show a theory which is categorical of an uncountable cardinality is totally transcendental?
I am studying Morley's theorem, which says that a complete theory which is countable and categorical in an uncountable cardinality $\kappa$ is categorical in every uncountable cardinality. In order to ...
2
votes
1answer
60 views
Is it consistent with NBG that there are two different satisfaction classes that satisfy the Tarski conditions?
So, NBG can not prove that first order set theory has a satisfication class. However, it is consistent with NBG that such a class exists. My question is if it is consistent with NBG that two such ...
2
votes
0answers
33 views
Proof that Hamiltonicity is not first-order definable
I am looking for a proof for the non-definability, in first order logic, of the exisence of a Hamiltonian cycle (or path) on a graph. It seems it can be proved using Ehrefeucht-Fraïssé games, but I ...
0
votes
0answers
27 views
Is this axiomatization of affine plane categorical?
First I'll give some definitions.
Hilbert's plane axioms of incidence: We consider a set $P$ (plane) and a family $\mathcal{L}$ (a family of lines) with axioms:
For any two distinct points $a,b$ ...
4
votes
1answer
42 views
Can there be an $S \subseteq \mathbb{R}$ closed under multiplication and addition with $|\mathbb{Q}| < |S| < |\mathbb{R}|$?
In $ZFC+\lnot CH$, is the statement that there is an $S \subseteq \mathbb{R}$ closed under multiplication and addition with $|\mathbb{Q}| < |S| < |\mathbb{R}|$ true, false, or independent?
1
vote
1answer
85 views
What is the most expressive logic?
What is the most expressive logic studied in the literature (in terms of expressing properties about a structure in the sense of model theory)?
Many people talk about second-order logic, but third-...
0
votes
1answer
76 views
Confused about truth in standard models vs non-standard models
So let's say I have a set of sentences $T$, true in my standard model $\mathfrak{A}$. I construct the consequences of $T$, $Cn(T)$. For any non-standard model $\mathfrak{B}$, it has to be the case ...
2
votes
1answer
89 views
What's the difference between predicate logic and model theory?
I studied model theory a little bit, and now that I'm reading the Wikipedia aricle on predicate logic, it seems to me that this is precisely model theory in that there is also the notion of signature (...
3
votes
1answer
44 views
Are $\mathbb{R}$+$\mathbb{R}$ and $\mathbb{R}$ isomorphic models of DLO?
I know that the theory of dense linear orders without endpoints is $\aleph_0$-categorical, and looking for two uncountable non isomorphic models of same cardinality, I found many examples, but nothing ...
3
votes
1answer
101 views
A theorem similar to Los-Tarski
A sentence is called existential if it is of the form $\exists x_1 \cdots \exists x_n \varphi(x_1, \cdots, x_n)$, where $\varphi$ is quantifier-free formula.
I wish to show (an exercise):
A theory ...
0
votes
1answer
36 views
Q: on Lemma I.5.11 proof from Tourlakis 2003
I'm unsure of the exact form of the I.H. in this case (the $\exists_x B \in Wff(M)$ rule).
I was thinking it could be $(B[x \leftarrow t])^\mathcal{J} = (B[x \leftarrow \bar i])^\mathcal{J}$, but it ...
7
votes
1answer
63 views
Can every relation be defined from “set-ary” relations?
This is an extension of this question, suggested by Noah Schweber.
Suppose I have some set of relations $(R_i)_{i\in I}$ over a set $D$: $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.
Noah defines a ...
6
votes
1answer
54 views
Can all relations be defined from symmetric relations?
I have a question about first-order structures over some set $D$. Suppose I have some set of relations $(R_i)_{i\in I}$ where $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.
I would like to know if ...
1
vote
2answers
70 views
Fields of finite characteristic are not axiomatizable.
"Prove that fields of finite characteristic are not axiomatizable by the 1st order theory."
How to prove this statement?
Characteristic is a smallest number of units such that it's sum is equal to ...
4
votes
0answers
212 views
Metamathematics and the foundations of mathematics
I have some really big doubts about what is the real starting point of all (formal) mathematics.
For example: when I search on internet or study texts about the foundations of mathematics such as ...
3
votes
1answer
66 views
prove Bézout's Theorem: few axioms, restricted language
I take Bézout's theorem to be the statement that given two different irreducible algebraic curves in two-dimensional projective space over an arbitrary field $K$, of degrees $m$ and $n$, the number of ...
0
votes
1answer
14 views
$CB(\varphi)=\alpha$ iff $\{p\in S_n (T) | \varphi\in p\wedge CB(p)\geq\alpha\}$ is nomempty finite
Cantor-Bendixson rank for a formula is defined as (in my notation) for $\varphi(x)$ in fixed $L$ and complete theory $T$,
(i)$CB(\varphi(x))\geq 0$ if $\phi$ is consistent with $T$
(ii)$CB(\varphi(x)...
1
vote
0answers
12 views
Bound on the degree of a polynomial solution to a parametrized equation
Let $K$ be a field, $F = K(T)$ a rational function field over $K$. Let $G \in F[C, X_1, \ldots, X_n]$ be a polynomial with coefficients in $F$.
We can consider the polynomial $G(c, X_1, \ldots, X_n)$ ...
0
votes
1answer
22 views
How many countable non-isomorphic models does acfp have?
I know $ACF_p$ is $k$ categorical for all uncountable $k$ but I cant find the nunber of countable non-isomorphic models of it ... I think since the number of prime numbers is countable it should be at ...
1
vote
1answer
37 views
proving $\phi$ does not isolate any complete type implies $CB(\phi)\geq 1$
I'm trying to understand the definition of a cantor-bendixson rank for a formula. It is defined as (in my notation) for $\phi(x)$ in fixed $L$ and complete theory $T$,
(i)$CB(\phi(x))\geq 0$ if $\phi$...
3
votes
1answer
80 views
First orderer logic completeness and independence: the proof that disappear?
Gödel completeness theorem for the first-order logic is in fact equivalent to BPI (every proper filter can be extended to an ultrafilter). Moreover, BPI is independent of ZF; that in particular means ...
1
vote
1answer
28 views
Marker's “Model Theory” exercise 5.5.4: indiscernibles in a $\kappa$-saturated model
I am solving exercises in Model Theory: An Introduction from David Marker. I think I have an idea, but I'd like to know if my intuition is correct. In this exercise, we work on a countable complete ...
1
vote
1answer
49 views
Can we enumerate finite sequences which have no halting continuation?
Note: this is a cross-post from CS.SE, since I haven't gotten an answer there.
I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
18
votes
2answers
907 views
Has a conjecture ever originally been decided by constructing the proof with mathematical logic?
So, one of the things that mathematical logic does is study theorems as abstract objects. There also many theorems about mathematical logic, and these theorems can have connections to other fields.
...
1
vote
0answers
36 views
Is reflexivity modally definable?
Reflexivity is not modally definable, in the sense that there is no modal formula that can specify only the reflexivity of points within a given model/frame (e.g., due to the bisimulation of a model ...
5
votes
1answer
44 views
First-Order Definability of finite structures (negative result)
I am trying to wrap my head around this proof sketch that we did in class:
Proof: Finite structures are not first-order definable
Suppose that the set $\Gamma$ of first-order sentences defines ...
1
vote
1answer
24 views
Classifying the $n$-types over $(\mathbb{Z}, S)$
Consider the structure $(\mathbb{Z}, S)$, where $S$ is the successor function. I'm trying to work out a classification of the $n$-types over it, and would appreciate some help in how to go about it.
...
0
votes
0answers
44 views
First-order definability of structures of at least $n$ elements
In class, we learned that it is possible to define structures of at least $n$ elements using the following WFF $\exists^{\geq n}$:
$$\exists x_1 \ldots x_n \bigwedge_{i \not= j} \neg (x_i = x_j)$$
...
4
votes
0answers
82 views
Does this class of models of ZFC correspond to some theory?
For some model of ZFC, $M$, we will let $Z_M(H)$ be the following 1-type over $M$:
"$H$ is a finite set."
"$S \in H$" for all $S \in M$
Then for some model $M'$ of ZFC with a distinguished element $...
5
votes
0answers
52 views
Axiomatizing a “bounded” companion to PA
There's nothing special about PA here, I'm just focusing on it since it's strong enough to ignore lots of minor technical issues around foundations. If switching to some other theory would yield a ...
0
votes
0answers
58 views
How is mathematics formulated - with models of formal systems?
How does one start doing 'Mathematics' from the ground up? My naive intuition (I don't know any logic) was that it's something like this:
1) Write down some symbols; so that we can use them for ...
1
vote
1answer
30 views
Classifying the $1$-types over $(\mathbb{Q}, <)$
Consider the $1$-types over $\mathbb{Q}$ as a dense linear order without endpoints. They are similar to cuts: for any $1$-type $p$ over $\mathbb{Q}$, we can define $L_p = \{a \in \mathbb{Q} \; | \; a &...
2
votes
1answer
26 views
If $T$ admits quantifier elimination in $\mathcal{L}$, does it admit quantifier elimination in $\mathcal{L}(c)$?
I know this is true:
If $T$ is an $\mathcal{L}$-theory and it admits quantifier elimination in $\mathcal{L}(c)=\mathcal{L}\cup\{c\}$, where $c$ is a constant symbol not in $\mathcal{L}$, then $T$ ...
2
votes
1answer
33 views
A necessary and sufficient condition for a structure to be rigid.
Is this a necessary and sufficient condition for a structure $M$ to be rigid: For all distinct $m, m'$ in the underlying set of $M$, $Th(M,m) \neq Th(M,m')$?
0
votes
0answers
34 views
Satisfication of modal formulas in ultrapower modals
I am learning from Blackburn's modal logic book, and I am attempting proving:
Proposition 2.71 Let $\prod_U M$ be an ultrapower of $M$. Then, for all modal formulas $\phi$ we have $M,w\vdash \phi$ ...
2
votes
1answer
55 views
Show that the set of real numbers is not definable in the field of complex number
Like what the title suggest, I wish to show that $\mathbb{R}$ cannot be define in $\mathbb{C}$. I want to make use of the following proposition ;
(David Marker) Fix a structure $M$, if $X \subset M$ ...
6
votes
2answers
230 views
Axiom checking as type checking?
There is a connection between type theory and logic, where types are propositions, and type checking performs the role of checking whether a proof of a proposition is correct (Curry-Howard isomorphism)...
2
votes
1answer
115 views
Vacuous truths in Superstructure approach to Nonstandard Analysis
Good evening everybody,
at the moment I'm studying non-standard analysis, specifically the superstructure approach to it. This approximately works as described in chapter 3 of http://people.dm.unipi....
0
votes
1answer
33 views
Is the structure $(\mathbb{R}, +, *)$ rigid? [duplicate]
Does the structure $(\mathbb{R}, + ,*)$ have only the trivial automorphism?
1
vote
1answer
27 views
A not-$\omega$-saturated model.
I'm new to $\omega$-saturated model and the likewise and although I'm aware of examples of $\omega$-saturated models $(\mathbb{Q},<)$, I can not really imagine a not-$\omega$-saturated model and ...
2
votes
1answer
166 views
Complete Theorem
Let $\mathcal{L}$ be a language with the constants ${a_1},{a_2}$ and the single parameter operation $F$. Looking at the set $\Gamma=\{ \psi,\chi,\eta \}\cup\{\phi_n|n\ge1\}$ where
$\psi=\forall{x}(x\...
2
votes
1answer
29 views
Elementary equivalence and finite isomorphism
It is well known, as Fraïssé's theorem, that for a finite relational signature $\sigma$ and two $\sigma$-models $\mathfrak{A}$, $\mathfrak{B}$, $\mathfrak{A}$ and $\mathfrak{B}$ are elementary ...
