# Questions tagged [first-order-logic]

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

4,297 questions
Filter by
Sorted by
Tagged with
0answers
33 views

### Formal proof of the statement $\exists x \forall y: R(x,y) \implies \forall y \exists x: R(x, y)$

As an exercise, my textbook wants me to prove that $\exists x \forall y: R(x,y) \implies \forall y \exists x: R(x, y)$. It is easy to prove in mathematical English. Something like: Fix some $x = x_0$. ...
1answer
41 views

### how do you write the following theorem in prenex normal form?

The theorem states: «a product of two-square numbers is two-square». Two-square number is a number equal to the sum of two squares.
1answer
24 views

### Complexity of $Th(\langle \mathbb{N},= \rangle)$

I can prove that the decision problem of $Th(\langle \mathbb{N},= \rangle)$ is PSPACE-hard. However, the recursive algorithm to show it is in PSPACE would not work, since variables are unbounded and ...
0answers
34 views

### finding set of formulas of first-order logic that satisfies a infinite domains

I was wondering what is the set of formulas of first-order logic that is satisfiable only iff the size of the domain is 3? I was also wondering how we can use the above formulas to find another set of ...
0answers
37 views

### a theorem in first order logic

There is a theorem in a logic book that depicts that for every formula $A$, there exists a formula $B$ in $\mathcal L$such that $\vDash A\leftrightarrow B$ and $FV(B) \cap BV(B) = \emptyset %$ ...
0answers
18 views

1answer
37 views

0answers
40 views

### Establishing First Order Logic and basic results with PRA

I am just beginning my study of mathematical logic (I’ve worked through the first 7 chapters of Kleene’s Introduction to Metamathematics) and like many others who are studying FOL for the first time, ...
1answer
33 views

### Fitch natural deduction proof of ∀x∀y∀z((S(x,y) ∧ S(y,z)) → S(x,z)), ∀x¬S(x,x) ⊢ ∀x∀y (S(x,y) → ¬S(y,x))

I'm trying to prove this sequent but I keep getting stuck. Working with multiple variables as well as quantifiers is confusing me quite a bit. My effort so far is below - you will see that I am trying ...
1answer
50 views

### Fitch natural deduction proof of $\exists xF(x) \lor \exists xG(x) \vdash \exists x (F(x) \lor G(x))$

I'm trying to create a natural deduction proof using the openlogicproject proof checker, but I just can't get it right. I have proven this on paper but I don't know how to get this right on the ...
2answers
79 views

### Is there a difference between $\exists x(\phi(x) \rightarrow \forall y\phi(y))$ and $\exists x \phi(x) \rightarrow \forall y\phi(y)$?

Is there a difference between $\exists x(\phi(x) \rightarrow \forall y\phi(y))$ and $\exists x \phi(x) \rightarrow \forall y\phi(y)$? The first one is the Drinker's paradox, which is a true in an non-...
0answers
36 views

### How to prove this logical entailment? [closed]

LOGICAL ENTAILMENT Let Γ be a set of Relational Logic sentences, and let φ and ψ be individual Relational Logic sentences. For each of the following claims, state whether it is correct. ∀x.φ ⊨ φ (no) ...
1answer
87 views

### Checking if a set is definable in a given structure

I am trying to find out whether the integers divisible by certain numbers are definable in the structure of $\mathbb{Z}$. but I really have no clue how to even begin, I've been sitting at my desk for ...
0answers
37 views

### Is there a way to eliminate redundant clauses in first-order logic?

I'm new to mathematical logic and wondering is there a way to eliminate redundant clauses in first order logic. Here is an example of my question: given two knowledge bases each containing a first-...
0answers
45 views

### Confusion about the proof of lemma 2.16 in Mendelson logic.

This question is from "Introduction to Mathematical Logic" by Elliot Mendelson , page 89. The lemma is this: Let J be a consistent, complete scapegoat theory. Then J has a model M whose ...
1answer
30 views

### Explanation for this Limitation of 1-Order Logic Concerning Supremum

In some book I found the statement that it is not possible in the predicate calsulus to express the sentence, that every bounded nonempty subset of an ordered field has a supremum. I thought that ...
1answer
84 views

### Can we express the theory of a single topology as a multi-sorted theory?

I've heard the result before that the theory of topologies cannot be expressed as a first-order theory, but I can come up with a simple multisorted theory that seems to capture the open set ...
2answers
30 views

### Negating a certain if-then statement in English involving a quantifier

I want to negate the statement $S \equiv$ "If not all integers are composite, then there are integers that are prime". The general rule that $\neg(Q \to P) \equiv Q \wedge \neg P$ may lead ...
0answers
34 views

### How to formalise this argument for showing equivalence of Noetherian conditions?

I am having trouble with a specific direction in proving the equivalence of certain conditions for being Noetherian. Let $A$ be a commutative ring with unity. Let $I(A)$ denote the set of ideals of $A$...
1answer
82 views

### Applications of intuitionistic logic in programming

In this discussion I asked people about applications of intuitionistic logic, and one of the participants of this forum, HallaSurvivor, told me that there are applications in programming. I am a ...
2answers
31 views

1answer
49 views

### Proving that $K_2$ is a theory with equality.

This question is from "Introduction to Mathematical Logic" , page 98 , exercise 2.67 . My proof: To prove that it is a theory with equality using $2.25$ , it suffices to show that the ...
2answers
51 views

### Is there a first order formula that is satisfied by $\mathbb{N}$, but not by any other models of Peano axioms?

Is there a first order formula that is satisfied by $\mathbb{N}$, but not by any other models of Peano axioms? For example, is there a formula that expresses "there is an element that is greater ...
1answer
50 views

### Minimum set of axioms for equality

I was reading the Wikipedia article on the axioms of equality here and I was a bit surprised by the fact that 3 axioms are provided (reflexivity, substitution for functions and substitution for ...
0answers
42 views

### Is it meaningful to ask whether first-order logic is consistent?

Is it meaningful to ask whether first-order logic, as opposed to a particular theory with axioms stated using first order logic, is consistent? If we assume first-order logic as our framework, then ...
1answer
26 views

### Analyzing logical form clarification

I want to refer to Example 2.3.1 of Velleman's book "How to prove it" . It is asked to analyze the logical form of $\{x_i\; | \; i\in I\} \subseteq A$. Two possible answers are given. The ...
1answer
27 views

### Prove by induction: the string $\forall x f(x,c)$ is not an $S-$term (where $S$ is an arbitrary symbol set). Do we really need induction?

I got this question in the lecture notes Prove by induction: the string $\forall x f(x,c)$ is not an $S-$term (where $S$ is an arbitrary symbol set). Well, as far as my readings are concerned I know ...
1answer
22 views

0answers
64 views

### Proof for Condition for equality in Proposition 2.25 in Mendelson Logic.

This question is from "Introduction to Mathematical Logic, by Elliot Mendelson , forth edition , page 97 about the proof of proposition 2.25. I am having trouble understanding this proof.Here is ...
1answer
32 views

### if for every finite statement set is satisfiable by 2 then any statement set is satisfiable by 2

Let S be a statement set of first order logic. We say that it is satisfiable by 2 if one can split to 2 the set, so each set is satisfiable . Prove or disprove, if every finite is satisfiable by 2, ...