1
vote
1answer
30 views

Relative Interpretations alla Kunen

at the moment I try to figure out some details of Kunen's "Relative Interpretation" Definition (within the 2013 Edition of his "Set Theory", p. 99 to 100): Definition If $\Lambda$ is some axioms ...
4
votes
1answer
56 views

Decision and the Uncountable Spectrum

In 2000, Hart, Hrushovski, and Laskowski classified all complete first order theories in a countable language up to their uncountable spectra. However, does this also imply that given a $any$ ...
1
vote
1answer
53 views

Are algebraic structures required to satisfy axioms?

Is it a requirement for algebraic structures, when studying universal algebra, to satisfy axioms? The reason I ask is because algebraic structures are only defined by a underlying set, a signature, ...
-1
votes
0answers
34 views

Is an o-minimal structure equivalent to a totally ordered set?

Is the notion of o-minimality synonymous to a totally ordered set? Both notions seem to emanate from Tarski although he may not have discussed o-minimality explicitly...
1
vote
2answers
62 views

An Uncountable language , A Model of $\mathbb{N}$, A Problem.

Edit 1: I messed up my original question, but Arthur Fischer answered my question anyway. Edit 2: We can actually restrict $L$ to the language in arithmetic with the prdicate $P_{\mathbb{P}}$. ...
5
votes
1answer
65 views

Is infinitary logics $\mathcal{L}_{\infty\omega}$ an abstract logic?

Infinitary logics $\mathcal{L}_{\infty\omega}$ is an extension of first-order logics such that $\bigvee\Phi \in \mathcal{L}_{\infty\omega}$ if $\Phi$ is a set of ...
6
votes
1answer
77 views

Construction of Ultrafilters

I've been doing a lot of work with ultrapowers and saturation recently. In particular, I am reading chapter 6 of Chang and Keisler as well as Keisler's paper on "Ultraproducts which are not ...
0
votes
0answers
36 views

Model-theory : questions regarding back-and-forth sets

See my previous post for the basic definitions from Jouko Väänänen, Models and Games (2011), page 54-on. See page 64 for : Definition 5.14 Suppose $\mathcal A$ and $\mathcal B$ are ...
1
vote
1answer
45 views

Model-theory : questions regarding partial isomorphism

I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and ...
7
votes
1answer
150 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
1
vote
1answer
70 views

Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$

We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...
0
votes
1answer
52 views

Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily nonequivalent structures for $L$?

Let $L$ be a set of specific symbols and $\operatorname{Form}(S)$ be the set of all first-order formulas over $L$. Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ ...
2
votes
1answer
56 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...
2
votes
1answer
103 views

Cardinalities of Collections of Models

Let $T$ be a complete theory in a countable language (with only infinite models). Recall the spectrum function: $I(\aleph_\alpha,T)=$ the number of non-isomorphic models of $T$ of cardinality ...
4
votes
1answer
46 views

A model which has only one undefinable element over a language with only a finite number of symbols

I try to solve the problem 1.3.14 in Chang and Keisler's Model theory: For each $n\in\omega$, find a model $\mathfrak{A}_n$ for $\mathcal{L}$ a language with only a finite number of symbols, which ...
6
votes
3answers
129 views

Can $(\Bbb N,\leq)$ have an $\aleph_0$-categorical theory (in a larger language)?

One of the nicer consequences of compactness is that there is no statement in first-order logic whose content "$\leq$ is a well-order". So we can show that there are countable structure $(M,\leq)$ ...
3
votes
0answers
83 views

Countable transitive $T \vDash ZFC-P$ with $\approx$ not absolute: why do we need $H(\aleph_3)$?

I am trying to solve Exercise IV.3.31 from Kunen's Foundations of Mathematics. I think I have a solution but I am confused by one of the hints. By request, here is the text of the exercise. ...
2
votes
1answer
64 views

Absolute confusion! (A question about absolute *sentences*)

I'm seriously confused about absoluteness. A formula in the language of a theory $T$ is absolute for $T$ structures if its truth value is the same in all standard transitive models of $T$ (this may ...
2
votes
0answers
97 views

How large or small can the gap in Shelah's main gap theorem be, up to consistency?

Shelah's main gap theorem in model theory says: For each first order complete theory $T$ in a countable language if $I(T,\kappa)$ denotes the number of its models of size $\kappa$ then one of ...
1
vote
2answers
52 views

Prove that ⊨ is not symmetric

Another question from a beginner: We want to prove that ⊨ is not symmetric by finidng concrete formulas φ and ψ for which we can show that φ ⊨ ψ and ψ ⊭ φ. Thank you for your help!
3
votes
1answer
59 views

Is first-order logic complete with respect to countable structures?

Question. Let $\Gamma$ denote a first-order signature, and consider a sentence $\tau$ and a set of sentences $\Sigma$ in the language generated by $\Gamma$. If every countable $\Gamma$-structure that ...
5
votes
1answer
52 views

Nonstandard models of PA with a decidable order relation.

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to ...
2
votes
0answers
70 views

Examples of Jónsson Models

Let $T$ be a complete first order theory. Suppose that $M\models T$. Then, $M$ is said to be a Jónsson Model of $T$ if for all $N$, such that $N\prec M$ and $N\models T$, we have $|N|<|M|$ (Note ...
7
votes
1answer
57 views

Every elementary submodel of $H(\aleph_1)$ is transitive

I am trying to solve the first part of Exercise II.17.30 in Kunen's Foundations of Mathematics which asks: Prove that every $A \preccurlyeq H(\aleph_1)$ is transitive. Here we are working over ...
4
votes
1answer
75 views

Ultraproducts of models of ZFC

Let $D$ be a non-principal ultrafilter over $\mathbb{N}$. Let $A_i$ for $i\in\mathbb{N}$ be (countable) models of ZFC such that $A_i\models \mathfrak{c}=\aleph_i$. Then, what is the size of the ...
4
votes
1answer
49 views

The class of finite groups (models) and that of countable groups are not elementary classes (a generalized version).

First some definitions: For a set $\Sigma$ of $\mathcal{L}$-sentences, $Mod(\Sigma)$ denotes the class of all models that satisfy $\Sigma$. For a class $\mathcal{M}$ of models, we say it is $EC$ if ...
3
votes
0answers
63 views

Models of infinite groups and 'Group-like' objects

Let $G$ be an infinite group, and for simplicity, we will assume that $G$ is also countable. Now, with $G$ in mind, we construct a new language $L_G=\{f_{a_i\_},f_{\_a_i}:a_i\in G\}$ where ...
5
votes
2answers
478 views

There is no smallest infinitely large prime

I'm reading Kunen's Foundations of Mathematics and trying to solve Exercise II.16.19, which constructs an elementary extension of the reals as an ordered field, and asks the reader to prove various ...
2
votes
1answer
47 views

How can we get rid of function symbols in model theory?

I understand the presentation of a language in logic as having relations with arities, functions with arities and constants. I understand that a constant can be thought as a function with arity $0$. ...
1
vote
1answer
70 views

What is the point of (Compactness Theorem in the) Overspill Principle?

I am trying to understand the basics of computation theory. The Overspill Principle (also at google) basically says if you are cool you can do everything Let Г be a sentence of predicate logic ...
1
vote
1answer
83 views

Existence of an automorphism of $\Bbb C$ that fixes a finite set pointwise but does not fix $\Bbb R$ setwise

I would like to construct a (ring-theoretic) automorphism of $\Bbb C$ that fixes a finite set $A$ pointwise but does not fix $\Bbb R$ setwise. Marker's Model Theory, Corollary 1.3.6 does that in this ...
1
vote
1answer
32 views

Partial order version of elementary equivalence

Elementary equivalence is an important concept in mathematical logic. Two models $\mathfrak{M}$ and $\mathfrak{N}$ of the same signature are elementarily equivalent, written $\mathfrak{M} \equiv ...
3
votes
2answers
54 views

Does having a filter which is not maximal implies the negation of Łoś theorem?

If we have a family $(\mathfrak{M}_i)_{i\in I}$ of $L$-structures, and a filter $\mathcal{F}$ over $I$, we can define the reduced product $\prod_{i\in I}\mathfrak{M }_i/\mathcal{F}$. If $\mathcal{F}$ ...
4
votes
1answer
74 views

Showing $2$ is not definable in $(\mathbb{Q},+)$.

As stated, I'm to show that $2$ is not definable in $(\mathbb{Q},+)$. I tried proving it by contradiction by showing that if $2$ were definable, then we could define $\mathbb{N}$ and multiplication ...
3
votes
1answer
74 views

Showing there does not exist a formal proof of a formula $\phi$.

My problem:Suppose $R$ is a binary predicate and use the soundness theorem to show that there does not exist a formal proof of $$ \phi =\forall y\exists xR(x,y)\rightarrow \exists x\forall yR(x,y).$$ ...
5
votes
2answers
111 views

Finite Model Theory

It seems that finite model theory is regarded (in a sense) as a computer theoretic subject. Is this the case or are there questions of interest that are of interest to mathematical logicians or more ...
3
votes
1answer
85 views

“Syntactic models” and the proof of the Completeness Theorem

In Computational Complexity by Papadimitriou (page 107), he outlines the basic idea for a proof of the completeness theorem for first-order logic - namely, that given a consistent set $\Delta$ of ...
47
votes
8answers
4k views

How is the Gödel's Completeness Theorem not a tautology?

As a physicist trying to understand the foundations of modern mathematics (in particular Model Theory) $-$ I have a hard time coping with the border between syntax and semantics. I believe a lot would ...
2
votes
1answer
41 views

Non-isomorpic uncountable dense linear orderings (a textbook example)

We know that two countable dense open orderings are isomorphic, and we know that this is generally not true for uncountable structures. Now I quote from the textbook, that is "Model-Theoretic Logics": ...
3
votes
0answers
68 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list ...
1
vote
3answers
138 views

ZFC Axioms to be extended?

Sorry if this is going to be a really loaded question. I was told several times that for virtually all theorems/corollaries/propositions of mathematics (except those cases not compatible with ZFC ...
1
vote
1answer
127 views

Definable subsets of the natural numbers using only the successor function

Consider the first-order language whose only nonlogical symbol is the unary function symbol $S$, and the structure $\mathfrak{N} = ( \mathbb{N} , S )$, where $S$ denotes the successor function. Why ...
3
votes
2answers
102 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
11
votes
2answers
230 views

Putting down axioms for some symbols. Playing with their consequences qualitatively and symbolically. Building theories. The book?

I am interested in the design and building of theories. By building theories, I mean putting down axioms of various kinds, over various fields, exploring their perhaps interesting, or probably boring, ...
0
votes
1answer
80 views

Peano's theory of arithmetic and Gödel's 1st Incompleteness Theorem

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed ...
2
votes
2answers
100 views

I would like some textbook recommendations for model theory

I am a 3rd year undergraduate math student and would like to study model theory. . I have some background with set theory, ordinals etc and also with mathematical logic. This is purely for self study ...
1
vote
1answer
85 views

Example of two finitely isomorphic structures (or $\omega$-isomorphic) that are not partially isomorphic?

One can define several maps between given structures in order to portray similarities or differences. The concept of isomorphism displays a deep structural overlapping, while for instance an ...
1
vote
1answer
56 views

A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
1
vote
1answer
58 views

Show that every existential sentence is preserved upwards

A sentence is existential if it is of the form $\exists x_1 ... \exists x_nR$ and $R$ has no further quantifiers. A sentence is preserved upwards if and only if whenever it is true in an ...
4
votes
3answers
108 views

How are models constructed?

As I understand, a model $\langle S,\sim\rangle$ of $\mathsf{ZFC}$ is a set $S$ coupled with some binary operation $\sim$, in which the axioms of $\mathsf{ZFC}$ hold (please correct me if I am wrong). ...