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

learn more… | top users | synonyms

0
votes
1answer
40 views

The axiom systems of predicate logic

I'm writing an article about logic for absolute dummies, so I want to make everything crystal clear; now I'm going to discuss predicate logic. After Googling, I found there are mainly 2 slightly ...
0
votes
1answer
25 views

Confused by a step in the 'Rule C' proof in Mendelson's Logic Textbook

I've been working through 'Introduction to Mathematical Logic, 5th Ed' by Mendelson, and I've found a step in the proof of proposition 2.10 (Rule C) that I cannot understand. In the proof of this ...
1
vote
1answer
30 views

What is it that we are missing in defining the following in the following manner?

Recently one of my friend and I are working on a project on a certain generalization of set theory. This is the same friend of mine of whom I talked in this post. However, the basic outline of his (...
0
votes
2answers
88 views

Is there an error in this textbook about Peano Arithmetic?

I encountered this doubt in an online intro-logic open course offered by Stanford Uni. Under the section 9.4 of this textbook here: http://logic.stanford.edu/intrologic/secondary/notes/chapter_09....
1
vote
1answer
55 views

Resolution Algorithms and one Example Problems?

We have a problem in one Resolution question. There is $5$ clauses, and want to prove the $6$th clause is true. which of the following clause is need more than one times to prove $6$th clause? $t$ ...
2
votes
1answer
57 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
1
vote
1answer
35 views

Proving a formula is valid

Let a formula $A$, and a term $t$ such that $x\in FV(t)$. Show that $\varphi = A\{t/x\}\to \exists x (x=t\to A)$ is valid. So let's assume by contradiction that the formula isn't valid. Therefore ...
1
vote
1answer
28 views

Monadic signature with constant

Consider a signature $\Sigma = \{ P^1, R^1, c\}$. Where $P^1, R^1$ are unary predicates, and $c$ is a constant. Let A be a formula in FOL over $\Sigma$. Prove/Disprove: If A is satisfiable ...
2
votes
1answer
45 views

First Order Logic Double Implication [closed]

I have a Logic Assignment of First Order Logic that I have to prove an initial claim, but one of the equations is kind of confusing for me because it has double implication and quantifiers. $$\...
2
votes
2answers
47 views

Axiomatizing stacks and queues using first-order logic

In the textbook I'm using to prepare the logic exam says that first order logic may be used to implement axiomatize data structures. There is an example of that: "Stack": uses a language that ...
0
votes
1answer
26 views

First Order Logic problem using instant axiom

I was trying the following exercise of identity of VanDalen's Predicate Logic. It is as follows. $$\vDash \phi(t) \leftrightarrow \forall x(x=t \rightarrow \phi(x)), \ \ \ x \not \in FV(t)$$ It ...
1
vote
1answer
37 views

Can every decision algorithm be expressed as a first order predicate?

Suppose we have a decision algorithm over, let's say, the set of natural numbers. Can this algorithm always be expressed as a first order predicate A(x) over the natural numbers, using only the ...
1
vote
1answer
21 views

translating algorithm to preserve validity?

Let two languages $\Sigma_1 = \{R^2, P^1, =^2\}$ and $\Sigma_2 = \{c, f^1, =^2\}$. Prove or disprove: There's an algorithm (procedure that halts) which gets as an input a formula $A$ above $\Sigma_2$ ...
0
votes
0answers
110 views

Writing a set of first order clauses to define a predicate

I need some help on where to begin with the following question: We say that a list (term) represents the natural number $k$ in binary if it consists of constants 0 and 1 and the digits of the ...
0
votes
1answer
38 views

Model for first order formula

I need to find a model for the following formula: $$(\forall x \forall y \forall z.R(x,y) \wedge R(y,z) \Rightarrow R(x,z)) \wedge (\forall x\forall y.\neg R(x,y) \Leftrightarrow R(y,x))$$ So I ...
2
votes
2answers
118 views

How can logic talk about itself? [closed]

How can there exist theorems like Goedel's Completeness theorem or Incompleteness theorem? They all make some statements about logical theories, but don't we need a certain logical scheme first to be ...
0
votes
0answers
40 views

Why does every closed normal default theory have an extension?

according to Reiter every closed normal default theory has an extension. but lets say W={} and D = {BIRD(x):FLY(x)/FLY(x)}. this default theory is closed, normal and yet doesn't have an extension. ...
1
vote
1answer
118 views

How Do I Prove the 6 Letter Thesis Cδδ0δp?

There exists a 1951 paper by C. A. Meredith which proves a completeness meta-theorem for the "C, 0, δ, p" system which has as it's sole axiom Cδδ0δp under uniform substitution for propositional ...
0
votes
0answers
43 views

Looking for feedback on proof (math logic)

$\def\sD{\mathscr{D}} \def\sC{\mathscr{C}} \def\sB{\mathscr{B}} \def\Gm{\Gamma}$ This is a theorem in Mendelson's Intro. to Math. Logic (pg 66, Proposition 2.4). I try to follow his conventions. MP ...
0
votes
1answer
39 views

“logical constant” vs “logical variable”

I'm learning introduction to logic on coursera offered by Michael Genesereth with Stanford University, where the the course used the term "logical constant" to denote a proposition sentence. For ...
1
vote
2answers
38 views

precedence problem of multiple implication operators in logics

Should a→b→c be read as (a→b)→c or a→(b→c)? I used a online truth table generator (http://logic.stanford.edu/intrologic/secondary/applications/babbage.html) to test and got a→(b→c) is the ...
0
votes
0answers
22 views

Putting this formula in Prenex Normal Form

Given this well formed first order logic form: $\forall x (\mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \mathcal A_2^2(x,y)) \Rightarrow (\forall x \ \mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \forall ...
0
votes
1answer
35 views

Show for closed terms $t$ and formulas $\phi$. Given a structure $M$: $M\vDash t = \overline{t}\,^M$

Show for closed terms $t$ and formulas $\phi$. Given a structure $M$: $$ \begin{align} M&\vDash t = \overline{t}\,^M\\ M&\vDash \phi(t) \leftrightarrow \phi(\overline{t}\,^M) \end{align} $$ ...
3
votes
2answers
50 views

Can a simple (atomic) proposition be a tautology?

Definition: "A tautology is a propositional formula that is true under any truth assignment to each of the atomic propositions in the domain of propositional function." Let $p$ be a simple (or atomic)...
0
votes
2answers
44 views

Are these two sentences logically equivalent?

What i'm essentially asking is if the following statement is true: $ \forall x \exists y (R(x) \lor Q(y)) :\Leftrightarrow \exists y \forall x (R(x) \lor Q(y)) $ where $:\Leftrightarrow $ means ...
0
votes
0answers
38 views

How is this a logical truth?

I've just been reading some lecture notes and it is claimed that the following is an example of a logical truth in first order logic (classically understood): $\exists$x $\neg$ (x=x) If this were a ...
0
votes
1answer
29 views

Showing validity of a formula in first order logic [duplicate]

So I'm trying to prove the validity of this formula and I am a bit lost, not sure how to start. I know generally speaking a valid formula is one where if all the premises are true, then the conclusion ...
1
vote
2answers
49 views

What would be an example of a tautology in first-order logic involving a definite sequence of quantifiers?

This question might be silly, but while teaching a tutorial as a TA, I suddenly had the need to bring up a tautological statement in first order logic that involved the quantifiers $\forall\exists\...
0
votes
1answer
19 views

Finding equivalent statements with quantifiers

Find equivalent pairs: a. $\forall x(P(x)\land Q(x))$ b. $(\forall x(P(x))\land (\forall xQ(x))$ c. $\exists x(P(x)\land Q(x))$ d. $(\exists x(P(x))\land (\exists x Q(x))$ Are ...
1
vote
2answers
33 views

Are those statements Tautology?

a.$$\forall x\forall y \exists z (x\neq y)\rightarrow (x\neq z)$$ b. $$\neg\exists x\forall y \forall z (x=y)\rightarrow (x=z)$$ To revoke a. we need to find a case of $(x\neq z)\land (x=y)$ and ...
2
votes
1answer
90 views

understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
3
votes
2answers
31 views

Contrapositive of the statement involving “for every” and “there exists”

I have a statement (∃x.(P(x) -> (∀y.P(y)))) I am trying to formulate and understand the contrapositive of the formula. ...
2
votes
0answers
26 views

Software for solving first-order logic

Is there any class of software that can help me with the following problem in first order logic: given $\phi$ a formula with a "hole" in it (a subformula which is undetermined) and a particular set of ...
0
votes
1answer
31 views

can you help me to transform ∀x FO logical formula to it equivalent ¬∃ formula?

i have this formula ∀x ∀y (A(x,y) V A(y,x) → B(x,c1) ∧ B(y,c2) ∧ c1≠c2) to the equivalent formula that start by ¬∃x ¬∃ y ? you will find the question here ...
7
votes
1answer
88 views

Is $\pi = 3.14159…$ first-order definable in the reals?

Given first-order logic with equality and the real field $\mathbb{R} = (R, 0, 1, <, +, \cdot)$, is $\pi$ first-order definable? By first-order definable, I mean a sentence of the form $\exists x \;...
0
votes
1answer
25 views

True or falsehood of open formula under a fixed interpretation

Given the open formula: $\alpha =(\exists{{x}_{2}})({P}^{1}({x}_{1},{x}_{2}))$ And consider the interpretation $I$ where the domain is the natural numbers, and ${P}^{1}$ means equality. Is $\alpha$ ...
0
votes
1answer
26 views

Using separators as functional symbols in first order logic

Suppose we have the following definition of a term: A $term$ is: $x$, where "$x$" is a variable $c$, where "$c$" is a constant symbol $f(\tau_1,...,\tau_n)$, where "$f$" is a ...
1
vote
1answer
42 views

Citations for the proof of universality of graph classes

In Automorphisms of graphs, Peter J. Cameron mentioned following classes of graphs which are universal structures. graphs of valency k for any fixed k > 2; bipartite graphs; strongly regular graphs; ...
0
votes
2answers
48 views

Natural Deducion: assumptions can be used more than once?

Im trying to prove: $ \forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x)) \vdash \forall{x} \sim P(x,x)$ What i have: $\forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x))\;$ Premise $ \forall{y}...
1
vote
1answer
47 views

What are the different ways to get a first-order formula that express the statement“$P$ is the $n$-th prime”

I know that such a $2$-predicate formula exists since Enderton's have already constructed such a formula in his text on mathematical logic but it was not easy to remember so I wonder if there is other ...
3
votes
1answer
84 views

Precise definition of Σ00 in the arithmetical hierarchy

I encountered several different definitions for Σ00 = Π00 = Δ00 of the arithmetical hierarchy. Following are two definitions which seem to me different but I'm not sure: All first-...
0
votes
0answers
16 views

First-Order Logic ternary predicate

I want to express the meaning of the following sentence in FOL: All the GermanAthlete are exactly those Persons who play a Sport for a Country where that Country is Germany. We have a ternary ...
1
vote
1answer
70 views

Arithmetical hierarchy: Why is $\Delta_0^0\ne \Delta_1^0$?

The definitions are different from one textbook to the other, but if we take the following definitions: $\Delta_0^0$ = all the first-order arithmetic formulas with bounded quantifiers only. $\...
1
vote
2answers
59 views

Expressibility of Peano arithmetic and the Arithmetical Hierarchy

First-order Peano arithmetic has no non-logical symbols other than S, +, *, < and variables. One allows finite quantification over predicates such as: $\forall k<n: \phi(k)$ where $\phi(k)$ is a ...
6
votes
2answers
69 views

Does the following set of formulas have a finite model?

So this is the problem: Do the following 3 formulas have a finite model: 1. $\forall x \forall y (p(x,y) \Rightarrow \neg p(y,x))$ 2. $\forall x \forall y (p(x,y) \Rightarrow \exists z (p(x,z) ...
0
votes
0answers
9 views

Source proof of equivalence between relation algebra and three variable first order logic

I am reading up on relation algebra and a lot about first order logic. Being a bit of a heavy torsion on the latter one as I am not used to it. Either way I read on wikipedia that up to 3 variable ...
1
vote
1answer
183 views

Optimize nonlinear model over time period (w/ Kuhn-Tucker Conditions)

I'm working on a nonlinear model that includes a time interval of 12 months. The goal is to maximize the total net benefit (NB) over the entire time period given the constraints listed below. I've ...
2
votes
1answer
22 views

Unification of $P(x,x)$ and $P(a,b)$ [closed]

Why can we not unify $P(x,x)$ and $P(a,b)$? Don't the substitutions $a/x$ and $b/x$ provide unification?
0
votes
1answer
26 views

Proving consequence by resolution refutation

I'm having trouble figuring out my error in this exercise: the task is to prove by resolution refutation that $ p \rightarrow (q \land r)$ is a consequence of the set $\{ p \rightarrow r, (p \land r)...
1
vote
0answers
24 views

What are some methods of proving undefinability results? (Reference)

I'm trying to prove some results regarding undefinability of functions from the natural numbers in certain structures, but besides texts on elemental logic and number theory, i haven't found anything ...