Movatterモバイル変換

Question 1

1vote

1answer

111views

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$,...

Learner of math

287

asked2 days ago

Question 2

0votes

1answer

77views

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...

Clemens Bartholdy

14.5k

askedNov 25 at 10:43

Question 3

-1votes

1answer

40views

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 ...

rr06

9

askedNov 23 at 14:52

Question 4

0votes

1answer

68views

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 ...

MarcoM

1

askedNov 22 at 19:46

Question 5

2votes

2answers

262views

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 ...

NikS

2,303

askedNov 20 at 8:28

Question 6

-1votes

2answers

115views

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 ...

Pineapple Fish

2,615

askedNov 19 at 1:59

Question 7

-2votes

0answers

32views

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 ...

Mica

7

askedNov 14 at 14:25

Question 8

0votes

1answer

83views

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 ...

Pineapple Fish

2,615

askedNov 14 at 0:43

Question 9

0votes

1answer

148views

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 ...

Alexander Wagner

49

askedNov 11 at 9:41

Question 10

3votes

2answers

299views

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 ...

Alexander Wagner

49

askedNov 7 at 15:38

Question 11

1vote

0answers

45views

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 $\...

Chad K

5,592

askedNov 3 at 18:22

Question 12

0votes

0answers

57views

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: ...

The Amplitwist

1,630

askedOct 31 at 17:09

Question 13

4votes

2answers

144views

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 \...

Adamat

57

askedOct 31 at 0:24

Question 14

-2votes

1answer

98views

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 ...

Window

49

askedOct 30 at 17:20

Question 15

2votes

1answer

112views

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 ...

NikS

2,303

askedOct 22 at 1:46

Movatterモバイル変換

Stack Exchange Network

Questions tagged [first-order-logic]

Complexity of $Th(\langle \mathbb{Z}; + , 1 \rangle)$ same as $Th(\langle \mathbb{Z}; + \rangle)$?

Are normal forms in first order logic unique?

Need a conclusive example that explains why QBF Prenex Transformations require closed QBF formulas [closed]

Generalization rule for universal quantifier and extended language

Does the Axiom Schema of Separation in any sense "provide" only countably many definitions of subsets of $\mathbb{N}$?

Proof of completeness theorem in first-order logic

How do I turn the sentence into predicate calculus? [duplicate]

Is there a complete proof system for deriving some axiom schema from others?

Relation between Tarski's conception of truth and (implicit) Axioms

Do equality axioms have to be stated in the meta language first?

Under what conditions does a proper class model establish relative consistency?

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]

Uniqueness quantification example

Get to know: The Tarski-Vaught Test [closed]

Semantically "undefined" terms of non-standard length in FOL with $\omega$-nonstandard metatheory

Hot Network Questions

Subscribe to RSS