All Questions
Tagged with model-theory logic
2,632
questions
4
votes
1
answer
141
views
(When) are recursive "definitions" definitions?
This is a "soft" question, but I'm greatly interested in canvassing opinions on it. I don't know whether there is anything like a consensus on the answer. Under what conditions (if any) are ...
- 95
3
votes
1
answer
396
views
Does Löwenheim-Skolem require Foundation in any way?
As title states, I'm curious whether Löwenheim-Skolem (in either of its upward or downward versions) necessitates some implicit use of Foundation. The usual presentation makes quite clear the reliance ...
- 512
0
votes
1
answer
74
views
Proving a simple consequence of the Compactness Theorem
I am self-learning logic, and trying to prove the following exercise using the Compactness Theorem:
Suppose $T$ is a theory for language $L$, and $\sigma$ is a sentence of $L$ such that $T \models \...
- 531
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
6
votes
1
answer
226
views
Definability of acyclic graphs
I think you should be able to encode the axioms of a directed, acyclic graph by introducing a strict partial order. Say E(a, b) represents there is an edge from a to b. We introduce a strict partial ...
- 63
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
4
votes
1
answer
87
views
Why are extensions of countable models of ZFC better behaved than extensions of arbitrary models of ZFC?
This answer hints that certain kinds of extensions are only guaranteed to exist for countable models of ZFC. Why?
One intuitive reason i can think of is that the metatheory might not have enough new ...
- 457
7
votes
1
answer
436
views
Functional completeness over a structure
The set of propositional connectives $\{\wedge,\vee\}$ is of course not functionally complete; correspondingly, the logical vocabulary $\{\forall,\exists,=,\wedge,\vee\}$ is not sufficient for ...
- 249k
2
votes
1
answer
113
views
In what sense is forcing "impossible" in $L$?
I just saw an interesting video from Hugh Woodin about Ultimate $L$. In it, he says one of the reasons $L$ is so interesting is because it not only settles many natural set theory questions, but is ...
- 8,000
2
votes
1
answer
54
views
Last Bits of Proof of the Compactness Theorem in Propositional Logic
I am reading the proof of compactness theorem for the propositional logic and the last part of the proof is left as exercise 2 of section 1.7 in the book by Enderton, A Mathematical Introduction to ...
- 15k
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
153
views
How does type theory deal with the lack of completeness, compactness, etc.?
As far as I understand, type theory (let's say Simple Type Theory or one of its extensions such as Homotopy Type Theory) is a computational view of $\omega$th-order logic.
See this question: Type ...
user1345451
1
vote
1
answer
49
views
For which cardinals $\kappa$ is the theory of a single bijection lacking cycles $\kappa$-categorical?
I'm currently stuck on Exercise 2.5.13 of David Marker's model theory text. The full statement of the exercise is as follows:
Let $\mathscr{L}$ be the language containing a single unary function ...
