All Questions
Tagged with model-theory first-order-logic
1,031
questions
3
votes
1
answer
214
views
Is quantifying over natural numbers non first order?
I was reading here that
Note that ‘x is an infinitesimal’ is not first order, because it requires you to quantify over the naturals.
Whats's non first order about quantifying over natural numbers?
- 5,965
5
votes
1
answer
415
views
Is there a theory in which all types can be omitted?
Is there a natural example of a first order complete (consistent) theory $T$ in which every 1-type can be omitted? or is there always some isolated type? In that case, why?
Of course there are plenty ...
- 581
1
vote
1
answer
77
views
Proving that the set of sentences that are true using the symbols $+,<,=$ is the same over all ordered fields
I am interested in whether the set of formulas that one can prove true for a concrete ordered field using the symbols $+,<$ and $=$, depends on the field. In particular, I am interested in the set ...
- 5,965
-2
votes
2
answers
101
views
in definition of assigment, what's means 'except possibly a'?
in frist-order logic,
part of assignments practice represent like this
"if 𝜙is ∀𝛼𝜓, where 𝛼 is a variable, then ��vℳ 𝜙 iff for every assignment 𝑣' that agrees with 𝑣 on the values of every ...
- 33
3
votes
0
answers
62
views
Two families of isomorphic structures have isomorphic ultraproduct.
I am trying to prove the following result:
Let $(\underline{M}_i)_{i\in I}$, $(\underline{N}_i)_{i\in I}$ be two families of structures such that, for all $i\in I$, $\underline{M}_i \cong \underline{...
- 103
3
votes
1
answer
90
views
What are other examples of $\aleph_1$-categorical theories?
In model theory, $\aleph_1$-categorical (first order) theories (in a countable language) are very important, and I am studying them at the moment. However, it seems that the only examples I can find ...
- 581
1
vote
1
answer
48
views
Is the interpretation of a constant symbol an injective map?
The context
Im trying to show that the reduct to the luanguage $\frak{L}$ of any model of the complete diagram $D(\frak{M})$ of an $\frak{L}$-structure $\frak{M}$ is an elementary extension of some ...
- 535
3
votes
1
answer
62
views
Algorithm for Determining Truth of First-Order Sentences in Complex Numbers
Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
- 87
-1
votes
1
answer
90
views
Decidability in Natural Numbers with a Combined Function [closed]
It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
- 87
4
votes
1
answer
123
views
Is second-order logic a special case of two-sorted first-order logic?
As far as I understand there is no syntactical difference between a two-sorted first-order theory and a second-order theory (both allow quantification over two domains).
Semantically, the ...
user1343124
0
votes
1
answer
55
views
Proof of bijection between $S_1(R,\underline{R})$ and the set of cuts in $(R,<)$
Hi guys I am trying to solve the following exercise but without great success and I hope you can help me:
"Let $\underline{R}$ be a real closed field (RCF). Show that $S_1(R,\underline{R})$ is in ...
- 103
6
votes
1
answer
59
views
Proof that the theory of $\underline{Z}=(\mathbb{Z},s)$ has quantifier elimination.
I am pretty new to model theory so this may be a naive question, however I am having some trouble proving the following:
"Let $\underline{Z}=(\mathbb{Z},s)$, where $s$ is the successor function, ...
- 103
3
votes
1
answer
121
views
Compactness Theorem for First Order Logic
I fail to understeand how a step in this particular proof of the theorem is permitted in ZFC.
The proof I've seen starts by considering models to all finite subcollections of sentences of a collection ...
- 161
1
vote
1
answer
46
views
Axiomatization of the theory of finite structures in a signature consisting only of function symbols
The following question is inspired by this question here. In that question, the OP asked whether there is a theory $T$ in the signature of a single binary operation $\{\ast\}$, s.t. $T$ admits both ...
- 9,938
3
votes
2
answers
161
views
Theory $\mathcal{T}$ with predicate $P$ that is satisfied by countably many elements in every model of $\mathcal{T}$?
By Löwenheim-Skolem, any first-order theory with some infinite model has models of any cardinality (as far as the language cardinality allows). So, it is a common pedagogical statement that "you ...
