For questions about formal deduction of first-order logic formula or metamathematical properties of first-order logic.

learn more… | top users | synonyms

-6
votes
0answers
31 views

Logic Predicate Problem again [duplicate]

it dosent has any answer related to question on Primitive Recursive Predicate Problem if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? ...
-2
votes
0answers
23 views

Question and Recursive Predicate Problem [duplicate]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
-2
votes
0answers
21 views

primitive recursive predicate challenge [duplicate]

I see this question as a nice challenge on logic. Primitive Recursive Predicate Problem if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? ...
3
votes
1answer
74 views

What would provable existence of a non-standard natural number imply about ZFC?

Assume that in ZFC we can define a set $x$ in some way and that the following are provable: $x$ is a finite ordinal, (i.e. $x\in\omega$) $x\neq0$ $x\neq1$ $x\neq2$ etc. So to say that the ...
0
votes
2answers
62 views

Logic Inference Challenge [on hold]

I read some logic course recently, would you please anyone say my inference is True? $\forall x S(x) \to \exists y(R(y)) \Rightarrow \forall x \exists y(S(x) \to R(y))$.
0
votes
1answer
47 views

Logic Inference Problem [on hold]

I read that the inference below is false, but I think it's true. Would you explain it to me please? $\forall x \exists y(S(x)\to R(x,y)) \Rightarrow \forall x(S(x) \to \exists y R(x,y))$.
-1
votes
1answer
65 views

Logic Challenging Question

I see this statement on the book: Assuming a set $\Sigma = \{ φ_1, φ_2, \ldots \}$, for each valuation v, we have n such that $v(\varphi_n)=1$. in this case we have n, such that: $\vDash \varphi_1 ...
0
votes
1answer
35 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha$

prove {$\neg(\forall x)\alpha \rightarrow \alpha$}$\vdash\space(\forall x)\alpha$ Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ...
-5
votes
1answer
110 views

Primitive Recursive Predicate Problem [closed]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
2
votes
1answer
18 views

find a sentence $\alpha$ in some language L such that

Let $K=\{k\in\mathbb N : k\mod2\not=0$ and $k\mod3\not=0\}$ find a sentence $\alpha$ in some language L such that $K=${$n\in\mathbb N :$exists a structure $M$ such that $M\models\alpha$ and ...
0
votes
1answer
28 views

A simple, yet non-superficial explanation of what “paramodulation” means in the context of automated theorem proving?

Modern automated theorem provers seem to be paramodulation-based. I only have a superficial understanding of what this means: we derive a proposition whose truth is implied from the truth of [two?] ...
1
vote
1answer
69 views

Big Questions in First Order Logic

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic, the set of logical result of $\Sigma$ is Recursively Axiomatizable. why this is false? or maybe it's true? ...
-1
votes
1answer
44 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
3
votes
1answer
21 views

Expressing infinite elements each equivalence class in First Order logic

I was going through some FO-logic ideas for my logic exam revision and came across some problems... Equivalence relations can be expressed in FO-logic by the set of axioms: $\{\forall x Rxx, \forall ...
0
votes
1answer
42 views

sentence in predicate logic

“If all politicians are showmen and no showman is sincere then some politicians are insincere.” Ans: F:= $(\forall x\,(P(x) \to ShMan(x)) \land \not \exists y\,( ShMan(y) \to Sinc(y))) \to \exists ...
1
vote
1answer
76 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
2answers
102 views

How is the law of excluded middle necessary for proofs by contradiction?

It is claimed that the law of excluded middle : $A \lor \neg A$, is a necessary principle for proving statements by contradiction (i.e. non constructively). However, in first order logic, at least, ...
0
votes
1answer
49 views

Existential introduction - required or not?

Consider a theory $T$ in first order logic, and a formula $C$. If there exist a proof of $C$, and that all formulas in $T$ and $C$, none of them contains $\exists$. The question is: does there always ...
0
votes
2answers
68 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
122 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
1
vote
2answers
42 views

implication versus conjunction correctness in FOL?

I've just started learning FOL and I'm really confused about whether to use conjunction or implications. For example, if I want to represent ...
1
vote
1answer
67 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 ...
1
vote
1answer
39 views

Is there a proof of this statement about deductions?

Is there a proof of the following statement: you cannot prove with natural deduction theorems that are unprovable in a Hilbert-style proof system? The logic in discussion is either propositional logic ...
2
votes
2answers
44 views

Why this holds? p(X) ⊨ p(f(X))

is there somebody who could help me understand? These statements were given to me to illustrate a logical consequence: ● p(X) ⊨ p(f(X)) ● p(X) ⊨ p(f(Y)) Where p is a predicate symbol a f is a ...
0
votes
1answer
31 views

Does intuitionist logic deny diagonal argument?

Let us for example give an example of diagonal proof of uncountability of the set of real numbers $\mathbb{R}$. Would intuitionists accept this, or deny this? If they deny this argument, why would ...
5
votes
3answers
59 views

Contraposition and law of excluded middle

Does truth-equivalence of an $A \rightarrow B$ and contrapositive $\neg B \rightarrow \neg A$ rely on the law of excluded middle?
0
votes
0answers
25 views

What are all of the computable or semidecidable properties of a first order sentence?

I'm interested in features of first order theories that can be used to differentiate first order sentences from each other in hopes there might be some way of measuring what makes one sentence more ...
3
votes
1answer
38 views

Existence of theories with exactly two countable models

I read a result of Vaught(a little down the page) that says that there cannot be any first order theory which has exactly two countable models upto isomorphism. Is this not a counter example: The ...
0
votes
1answer
35 views

Disjunctive Normal Form (DNF) of a boolean combination

Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 : Suppose that $P$ is a Boolean combination of ...
1
vote
0answers
58 views

Proof of $t=s\vdash ^{v} A\leftrightarrow B$ in First order logic

First of all, I will explain my terminology\synthax. $T\vdash ^{v}\varphi $ if $M\vdash T \Rightarrow M\vdash \varphi $ (where $M\vdash \varphi $ means that for every assignment $v$ in $M$ we have ...
4
votes
1answer
84 views

Elementary equivalence versus equivalence between the total theory in model theory

In the page for elementary equivalence on wikipedia, in the introduction, they say: "If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary ...
4
votes
4answers
209 views

Why aren't there any first-order sentences which have the property of being true in all non-standard models of PA and false in the standard one?

I'd like to know where the following result comes from (that is, whether there is a more general result from which it follows or else how it can be proven): There is no first-order sentence which is ...
4
votes
4answers
97 views

Can't see the intuition behind the validity of this formula: $\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$

I know that $$\vdash_{\mathcal G}\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$$ (I have read and done a syntactic proof of this.) And therefore also $$\models \exists x(\exists yP(x,y) → ...
2
votes
1answer
23 views

Small part of loop invariant i'm not getting

Show that $y = \frac{1}{2} \cdot z \cdot (z + 1)$ is a loop invariant for the following WHILE loop: y := 0; z := 0 WHILE $\neg$(z = x) DO z := z + 1; y := y + z In other words, proof that $\{y = ...
4
votes
1answer
46 views

Hints and/or help needed for axiomatic deduction

Proof: $\forall x \forall y ((Ax \rightarrow Rxy) \rightarrow \neg Ay) \vdash \forall x (Rxx \rightarrow \neg Ax)$ Axioma schema's that can be used: 1 $(\forall x(\varphi \rightarrow \psi)) ...
1
vote
2answers
55 views

The Entscheidungsproblem (decision problem) for modal logic

The Entscheidungsproblem is identified with the decision problem for first-order logic that is, the problem of algorithmically determining whether a first-order statement is universally valid. ...
3
votes
1answer
30 views

English sentence to FOL

I was given a sentence ; All students who are doing chemistry or biology can sit for some test. According to my understanding I translated it in to first order ...
1
vote
1answer
45 views

Interesting Identities in First-Order Logic

Are there more identities of this sort (http://en.wikipedia.org/wiki/First-order_logic#Provable_identities) that are interesting/non-trivial? It seems that most further work in first-order logic is ...
2
votes
1answer
48 views

Proving the Completeness Theorem

In my lecture notes for logic, the Completeness Theorem for First Order Predicate Calculus has been introduced. In the lectures, it was stated that in order to show the Completeness Theorem holds ...
3
votes
2answers
89 views

Help needed with axiomatic deductions

Proof axiomatically: $\vdash \forall x (\neg (Ax \rightarrow Bx) \rightarrow (\neg Ax \rightarrow \neg Bx))$ You can use in your deduction as step the equivalence of $\varphi$ with ...
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
0answers
69 views

Help in understanding a “obscure” point in W.Rautenberg's textbook : A Concise Introduction to Mathematical Logic

See Wolfgang Rautenberg, A Concise Introduction to Mathematical Logic, (3rd ed - 2010). I've a problem in "decrypting" the statement and the proof of a theorem [see page 97] : Let $\mathcal L$ be ...
0
votes
0answers
14 views

Give an informal proof of (x = u Ʌ y = v) → 〈x, y〉 = 〈u, v〉 using First order logic set theory

Consider the fundamental property of ordered pairs: 〈x, y〉 = 〈u, v〉 ↔ (x = u Ʌ y = v). Notice that the character of the sentence is a biconditional. Hence, if we wanted to prove 〈x, y〉 = 〈u, v〉 ↔ (x ...
2
votes
1answer
33 views

Prove that, for any $\Delta_0$ sentence $\sigma$, QE$\models \sigma \leftrightarrow \sigma$ is true in $\eta$

A formula $\varphi$ of $L^A$ is $\Delta _0$ if $\varphi$ belongs to the smallest set containing the atomic formulas and closed under negation, forming conditionals, and bounded quantification. Closure ...
2
votes
1answer
100 views

Soundness of existential quantifier ($\exists \vdash$) in Gentzen's system

Consider Gentzen's system for first order logic with sequents $\Gamma \vdash_G \Delta$, where $\Gamma$ and $\Delta$ are finite sets of formulae. One of the rules in Gentzen is: $$(\exists\vdash) \, ...
1
vote
2answers
32 views

Not understanding universal generalisation, and proof that uses it

From $\varphi$ follows $\forall x \varphi$. E.g., universal generalizations of the formula $Rxy \wedge \exists z Sz$ can be $\forall x (Rxy \wedge \exists z Sz)$, $\forall x \forall y \forall u(Rxy ...
9
votes
1answer
141 views

Can all math results be formalized and checked by a computer?

Can all math results, that have been correctly proven so far, be formalized and checked by a computer? If so, what type of logic would need to be used there? I've heard that the first-order logic is ...
2
votes
0answers
39 views

A consistent first-order theory whose impredicative second-order variant is inconsistent

Let's assume that we have a consistent first-order theory, which was derived from a second order theory by replacing universal quantification over second order variables by axiom schemes for ...