Questions tagged [first-order-logic]

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

Filter by
Sorted by
Tagged with
3
votes
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$. ...
0
votes
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.
0
votes
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 ...
0
votes
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 ...
0
votes
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 %$ ...
-1
votes
0answers
18 views

What would lead one to decide that “if __, then __” needs to be a function of truth values? [duplicate]

I am not asking for an intuitive explanation for the truth table $ \begin{array}{| c | c | c | c |} \hline P & Q & P \implies Q\\ \hline T & T & T\\ \hline T & F & F\\ \hline F ...
1
vote
0answers
11 views

Complexity of the sat problem for First Order Logic over an unbounded number of unary predicate and one equivalence relation

For this post, given a set $\tau_0$, a $\tau_0$-structure is a tuple $\mathfrak{S}=(S,(\overline{\sigma})_{\sigma\in\tau},\overline{R})$ where $S$ is a set, $\overline{\sigma}$ is a subset of $S$ and $...
0
votes
1answer
37 views

Existential and universal quantifiers and implication

$[p\rightarrow \forall x.P(x)]\equiv \forall x.[p\rightarrow P(x)]$ (1) $[(\forall x.P(x))\rightarrow p]\equiv \exists x[P(x)\rightarrow p]$ (2) to prove $\exists x \forall y.P(x,y)\rightarrow \...
0
votes
1answer
47 views

Universal elimination in Fitch

I've returned to tinkering with some arguments in Fitch after not having had anything to do with formal logic in a while, and I suppose I've grown rustier than I thought I had because I simply can't ...
-4
votes
0answers
14 views

How do I derive ui wrt qi in order to find the null [closed]

How do I derive ui with respect to qi to find the null: ui(qi,q-1)=(x-qi)*$\sum_{j=1}^n$qj According to the solution, I should obtain: (x-qi)-$\sum_{j=1}^n$qj=0
6
votes
1answer
103 views

Is there a formula in FOL that is only satisfiable in an infinite domain

Is it possible to construct a formula or set of formulas using only equality that are satisfiable only in an infinite domain? I have seen such formulas but they all use a relation like greater than or ...
2
votes
1answer
63 views

Compactness theorem equivalences

i have this equivalence to compactness theorem that i have problems to prove: For every first-order theory $T$, every tuple $x̄$ of distinct variables and all sets $\Phi(x̄),\Psi(x̄)$ of first-order ...
2
votes
1answer
73 views
+100

How to find the Skolem form of the following formula?

I'm confused about finding a Skolem form of the following formula: F = $(\forall x)(P(x)\rightarrow(\forall y)((\forall z)Q(z,y)\rightarrow\neg(\forall z)R(y,z)))$ So following the algorithm I've done ...
1
vote
1answer
59 views

Complexity of the pure theory of equality

The first-order pure theory of equality (Monk, Mathematical Logic, 240-242) has the equality predicate as its only (relation) symbol. Furthermore, I assume the convention in logic is that any ...
3
votes
1answer
51 views

Universal Quantification and Existential Quantification in Mathematical Reasoning

Mathematics is built within the framework of first-order logic, i.e., the classic set theory. Mathematical objects, in my opinion, are constant symbols introduced in sub-proofs from existential ...
4
votes
3answers
122 views

Is $\exists x\exists yP(x,y) \to\exists x\exists yP(y,x)$ valid?

Consider $$\exists x\exists yP(x,y) \to\exists x\exists yP(y,x).$$ Is the above statement valid? Please explain why. I thought is is valid and that I could write $\exists x\exists yP(y,x)$ as $\...
0
votes
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, ...
1
vote
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 ...
1
vote
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 ...
4
votes
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-...
-1
votes
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) ...
2
votes
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 ...
2
votes
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-...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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$...
1
vote
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 ...
2
votes
2answers
31 views

Existential Quantifier Distributivity in First Order Logic

It is well-known that the following formula holds for boolean functions involving free variables: $$\exists x,P(x)\wedge Q(x)\neq (\exists x_1,P(x_1))\wedge(\exists x_2,Q(x_2)),$$ $$\exists x,P(x) \...
8
votes
2answers
215 views

Applications of intuitionistic logic

Can anybody enlighten me about the applications of intuitionistic logic? I am familiar with this system only by G.Takeuti's book, where it is described as one of the examples of axiomatic systems of ...
2
votes
0answers
60 views

How can I rigorously justify introducing a new variable into a sentence?

I was thinking about a problem I saw on stack exchange today about linear maps, in which we were given that for some linear map, $T: \mathbb{R}^n \rightarrow \mathbb{R}^n$, we have that $\text{Im}(T) \...
0
votes
2answers
18 views

Negations of Statements

I'm currently working in topology and I was trying to prove something by the contrapositive, but I was unable to do so because I struggled to understand how I should appropriately interpret the ...
3
votes
2answers
98 views

Is the wf $B \to \forall x B$ logically valid?

So I wanted to know If $B \to \forall x B$ is logically valid. I found this Tree proof generator website where I can check If a wf is logically valid or if there is an counter-example. I putted in the ...
1
vote
1answer
86 views

On the existence of infinitesimals.

Creating the first infinitesimal by use of Compactness Theorem In this question someone tried to create the first infinitesimal using the compactness theorem, but I don't know much about compactness ...
1
vote
2answers
70 views

Is the equals operator reducable to basic logic and set theory?

Usually, an equivalence relation ($=$) is defined as having the following three properties: Reflexivity. $\forall x, x = x$ Symmetry. $\forall x, y \text{ }$ $y = x$ if and only if $y = x$ ...
1
vote
1answer
48 views

Definition of $(\exists_1x)\mathscr B(x)$

This question is from Introduction to Mathematical Logic by Elliot Mendelson , forth edition , page 99 about the definition of $(\exists_1x)\mathscr B(x)$. In the book , the definition is written like ...
1
vote
1answer
30 views

Is there any particular formulation of $Con(T)$ that makes $Con(T)$ derivable from $T$?

In the proof of Gödel's second incompleteness theorem in my textbook, it is required that we choose the formula $Drv$ to be one that satisfies certain additional properties, rather than any formula ...
1
vote
1answer
39 views

Understanding the solution to this exercise on Gödel's second incompleteness theorem

Exercise: Show that if $F$ is a closed formula and if $$\mathcal{P} \vdash \exists v_0\; Drv[ \underline{\#F},v_0]\Rightarrow F,$$ then $$\mathbb{P}\vdash F.$$ Solution: Suppose that $$\mathcal{P} \...
0
votes
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 ...
1
vote
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 ...
3
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
1answer
22 views

Interpretation of a First order language and functions that map distinct sets

I'm new to logic and I've been studying Enderton's book. From Sec. 2.2 Truth and Models we know that a structure $U$ for a first order language map each function symbol $f$ to an $n-$ary operation $f^...
1
vote
1answer
46 views

What should be my induction hypothesis for proving the unique readability of terms in first order logic?

The thing I want to prove is: If a term is one of the following then it is uniquely defined a variable a constant complex form, $f t_1 t_2 \cdots t_n$ where $f$ is a function of arity $n$ and $t_i$ ...
1
vote
1answer
29 views

Is the biconditional possible for this statement (instead of just a conditional)?

In one of the assignment of the "Introduction to Mathematical Thinking" course by professor Keith Devlin on Coursera, this statement was shown to be true: $\forall x \forall y \, [(x \leq y) ...
0
votes
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 ...
1
vote
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, ...

1
2 3 4 5
86