# Questions tagged [first-order-logic]

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

5,394 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Are these restatements of m-equivalence correct?

I am not sure if these formulations of the $m$-equivalence of two structures $\mathfrak{A}$ and $\mathfrak{B}$ are correct. Two structures $\mathfrak{A}$ and $\mathfrak{B}$ are $m$-equivalent iff for ...
• 549
14 views

• 1,003
67 views

### Question about Finite Model on Robinson Arithmetic

So I was supposed to create a finite model for Robinson Arithmetic in an exam and show that it was a finite model, but I was unable to do so. Would appreciate any help with this problem because I feel ...
• 73
1 vote
100 views

### Prove that is a tautology without using truth table [closed]

I can't find a proper formula to prove that $$(p\rightarrow q) \rightarrow ((r ∨ p) \rightarrow (r ∨ q))$$ Is a tautology; considering it's almost exclusively made up of implications. Can somebody ...
39 views

### Show that there exists a ternary operator T such that {T} is functionally complete. [closed]

I know that here exists binary operator like that: T(1,1)=0, T(1,0)=1, T(0,1)=1, T(0,0)=1. But how about ternary?
212 views

### Does independence-friendly logic have a completeness theorem?

It is a well-known (and frankly magical) property that first-order logic is strongly semantically complete (Gödels completeness theorem). Independence-friendly logic is just like first-order logic but ...
1 vote
83 views

### Which logic is most fundamental? [duplicate]

A couple of my introductory logic books appeal to modal and set-theoretic notions in building up first-order logic. (They explicitly acknowledge these connections and say, for example, that validity ...
• 47
1 vote
126 views

### Infinite statements from finite axioms

I want to know if a given finite subset of axioms of PA1 ( 1st order peano arithmetic ) can prove infinite sentences in PA1 such that those proofs need no other axioms except those in the given finite ...
96 views

### is arithmetic finitely consistent? [duplicate]

Let's take PA1( First order axioms of peano arithmetic ) for example. From godel's 2nd incompleteness theorem, PA1 can't prove its own consistency, more specifically it can't prove that the largest ...
1 vote
53 views

### Modern reference on PA degrees?

I'm currently trying to work my way around some papers from Jockush et al, and PA degrees come up frequently. I'd be interested in a modern reference/survey summarizing the main results on the subject,...
• 461
40 views

### Is $\exists x [(P(x) \vee Q(x))\rightarrow R(x)]$ logically equivalent to $\exists x [(P(x) \rightarrow R(x)) \vee (Q(x)\rightarrow R(x))]$?

Is $\exists x [(P(x) \vee Q(x))\rightarrow R(x)]$ logically equivalent to $\exists x [(P(x) \rightarrow R(x)) \vee (Q(x)\rightarrow R(x))]$? What about if I replace $\exists$ with $\forall$?
• 133
49 views

### Arithmetization of Turing machines

Refer to Turing's 1936 paper, page 248, last paragraph. I present the paragraph in verbatim below : The expression "there is a general process for determining..." has been used throughout ...
• 345
1 vote
56 views

### Defining Church numerals in higher order logic.

I'm looking for some help with Exercise 5.11. in Bacon's A Philosophical Introduction to Higher-Order Logics. Construct an explicit definition of the finite Church numerals, Num$_{\sigma}$, in higher-...
• 23
43 views

### Why in First order logic, Variables mapping is not included in Structure definition [duplicate]

Although the constants are included in Structure definition and Interpretation definition, but Varibles are included only in Interpretation definition, what is the reason for that, is there any error ...
• 17
1 vote
77 views

### Proof of Hahn-Banach theorem from Compactness theorem of FOL

Since the Compactness theorem of FOL is equivalent to the ultrafilter Lemma, which implies Hahn-Banach, the implication is clear to me. I was more just wondering if there is a nice direct proof? I saw ...
• 131
230 views

### Precise axiomatic definition for the equality "=" as a binary relation

Question: What is a simple yet precise definition for "=" as a binary relation? My try: I find two definitions for "equality relation" which seems to be contradictory. The first ...
• 766
654 views

### Finding a property that is true for every left ideal but not for right ideals

I'm trying to find (or prove that it cannot exist) a property that is true for all left ideals of a ring (with unity) but fails for some right ideal. To rephrase this more rigorously: Consider the ...
• 4,806
1 vote
60 views

### Subtleties on comprehension sets

I see that a typical definition of the cartesian product $A \times B$ is $\{ x \in \wp\wp A \cup B: \exists a \exists b (a \in A \wedge b \in B \wedge x=(a,b)) \}$. I have come up with an alternative ...
119 views

### How to say in FOL that P(f) is true and everything else with property P is false?

How to say in FOL: "francis" is "Pope" Nothing is identical to "francis" Except for "francis", is false that something is "Pope" The formula should ...
• 9
28 views

### Composing Substitution Sets in Predicate Calculus

I was reading Artificial Intelligence: Structures and Strategies for Complex Problem Solving by Luger, and composing substitution sets came up. It said this on page 67: "If S and S′ are two ...
57 views

### Understand a proof on Craig's interpolation Theorem

I am reading Hans Halvorson's The Craig Interpolation Theorem. I cannot make the following lines precise: We claim now that there is an isomorphism $j: N\mid_{L_0}\to M\mid_{L_0}$ ... So, putting the ...
• 3,935
177 views

### How restricted variables can be introduced in ZF(Zermelo-Fraenkel) set theory? [closed]

In mathematics, all variables are usually restricted - they can take values only from a certain set (for example, real variables). Let us use for restricted variables the notation $x^t$ where $x$ is a ...
• 631
58 views

### If the exponential is definable in an expansion of $\mathbb{\overline{R}},$ then it is definable without parameters

Let $\mathcal{R}$ be an expansion of $(\mathbb{R},+,\cdot,-,<,0,1)$, and suppose that the exponential map is definable. I am asked to show that it is definable without parameters using the fact ...
• 447
54 views

### complement of a property in the lambda calculus

I'm trying to demonstrate that the complement of the complement of a property is equal to the property itself using $\lambda$ notation, i.e. if $G=\lambda x(\neg Fx)$ and $R=\lambda x(\neg Gx)$, then ...
38 views

• 1,789
1 vote
24 views

### Expressivity vs existence of relational structures?

There is a lot of research into understanding expressivity of first-order logic, or formal languages in general. I am particularly interested in expressivity of graph properties. So for e.g. existence ...
• 1,789
1k views

### Confusion about Löb's theorem [duplicate]

To quote wikipedia: Löb's theorem states that in any formal system that includes PA, for any formula P, if it is provable in PA that "if P is provable in PA then P is true", then P is ...
• 743
410 views

### Is axiom of replacement nicely stateable in the language of ETCS?

ETCS has a nice category-theoretic formulation: "well-pointed topos with a natural numbers object and axiom of choice." I'm too new to topoi to really understand all of what's going on, but ...
• 125
95 views

### Why does first-order logic lack of a description like the Stone duality?

Stone Duality characterizes Boolean algebras in terms of spaces. I regard this as being done by identifying an algebra with its space of models'', and feel like the barrier for a similar thing to be ...
• 3,935
1 vote
44 views

54 views

### How to show if $\Gamma\models\bot$, then $\Gamma$ is not satisfiable?

I am struggling to show that for any set of sentences $\Gamma$, if $\Gamma\models\bot$, i.e. $\Gamma$ entails $\bot$, then $\Gamma$ is not satisfiable, i.e. for any structure $M$, $M\not\models\Gamma$....
• 383
25 views

### Can a bottom sign be omitted in a disjunction?

I have got the following statement: ∀aP(a),∀a(¬P(a)∨S(a)) ⊢∀a S(a)∨¬P(a) My proof looks like this: ∀aP(a) (premise) ∀a(¬P(a)∨S(a)) (premise) Start scope of x as substitution of a P(x) (forall ...
69 views

### Name of Simple Logical System

There's a logical system, devised by someone whose name escapes me, that consists of two moves. You begin with one line, then draw another line, and somehow this can be built to capture all sorts of ...
• 47