All Questions
Tagged with predicate-logic or first-order-logic
9,964 questions
1
vote
1
answer
117
views
Complexity of $Th(\langle \mathbb{Z}; + , 1 \rangle)$ same as $Th(\langle \mathbb{Z}; + \rangle)$?
I want to know a lower bound for the complexity of the decision problem for $\langle \mathbb{Z}; + \rangle$. The below paper notes that Presburger arithmetic, originally $\langle \mathbb{N}; +\rangle$,...
- 287
0
votes
1
answer
81
views
Are normal forms in first order logic unique?
This is what I know so far:
If we have a block of all quantors w.r.t various variables, we can swap it as much as we like.
In general case we can't swap exists quantor with any other quantor
...
- 14.5k
-1
votes
1
answer
41
views
Need a conclusive example that explains why QBF Prenex Transformations require closed QBF formulas [closed]
The task is to show that:
$\forall p F \to G$ is not equivalent to $\exists p(F \to G)$ where F and G are propositional formulas.
I'm aware that when applying prenex rules to a formula to transform a ...
- 9
0
votes
1
answer
69
views
Generalization rule for universal quantifier and extended language
Let L be a language of first order logic. The generalization rule for universal quantifier says that, for $\phi\in L$, $\Sigma \vdash_L \forall x\phi(x) $ iff $\Sigma\vdash_{L\cup c}\phi([c/x])$, with ...
- 1
2
votes
2
answers
263
views
Does the Axiom Schema of Separation in any sense "provide" only countably many definitions of subsets of $\mathbb{N}$?
Section 6 (pg. 24-25) of this paper contains the following excerpt (bold for emphasis added by me):
The axiom of Separation could also be called the axiom of Definable Subsets. A subset $T$ of $S$ is ...
- 2,303
-1
votes
2
answers
115
views
Proof of completeness theorem in first-order logic
I am starting to program a proof assistant in Python. The proof assistant will be based in FOL. I might be interested in proving the soundness and completeness theorem for first-order logic in my ...
- 2,615
-2
votes
0
answers
32
views
How do I turn the sentence into predicate calculus? [duplicate]
How do I write the sentence " Ana knows every one of Bob's friends" in predicate calculus?
I understand "knowing a person" and "being friends with person" can be two ...
- 7
0
votes
1
answer
83
views
Is there a complete proof system for deriving some axiom schema from others?
Say that an axiom schema is an algorithm $A$ that produces a family of first-order statements (I believe we can recursively enumerate all the algorithms that produce well-formed sentences). Given ...
- 2,615
0
votes
1
answer
149
views
Relation between Tarski's conception of truth and (implicit) Axioms
I am trying to understand the original paper of Tarski Concept of Truth in the formalized languages, as printed in his collected works.
I have read introductory texts from Shoenfield Mathematical ...
3
votes
2
answers
299
views
Do equality axioms have to be stated in the meta language first?
This question may sound silly, but there is something about the semantics in first order languages which confuses me a bit.
Im using Ebbinghaus,Flum,Thomas:Einführung in die mathematische Logik, as ...
1
vote
0
answers
45
views
Under what conditions does a proper class model establish relative consistency?
Say $\mathcal L$ is a lexicon of first-order logic with equality. $\mathcal L$ is finite and may contain constants, functions or relations.
$C(x)$ is a predicate of the language obtained from $\...
- 5,612
0
votes
0
answers
59
views
How is the formula $\forall x (P(x) \vee \neg \forall x P(x))$ equivalent to $\forall x (P(x) \vee \neg \forall y P(y))$? [duplicate]
This is regarding the "convention on variables" on page 47 of the following book: Moerdijk, Ieke; van Oosten, Jaap, Sets, Models and Proofs, Springer Undergraduate Mathematics Series. Cham: ...
- 1,630
4
votes
2
answers
144
views
Uniqueness quantification example
I have encountered a quite simple sentence, which is:
The polynomial $x^2-6x+9$ has exactly one root in $\mathbb{R}$.
If I were to write this using quantifiers it would obviously be:
$\exists!_{x \in \...
- 57
-2
votes
1
answer
99
views
Get to know: The Tarski-Vaught Test [closed]
I want to understand the Tarski-Vaught Test and how to apply it.
It is stated as follows.
Let $\mathcal{M}$ ben an $\mathcal{L}$-structure and $A\subseteq M$. Then $A$ is the base set of an elementary ...
- 49
2
votes
1
answer
112
views
Semantically "undefined" terms of non-standard length in FOL with $\omega$-nonstandard metatheory
As preliminary background, the following passage from Foundations of Set Theory by Fraenkel et. al.:
The object-language of a given theory is sometimes an artificial symbolic language...When an ...
- 2,303