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
25 views

Implication or Bidirectional in “x is a Prime”

I have a question regarding First Order Logic. I have to express the property "x is a Prime" in First Order logic. So far I have the following solution: $\forall x\;Prime(x) \leftrightarrow \neg ...
0
votes
0answers
7 views

Why $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology?

Let $c$ be a new constant symbol in the language. Then $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology. This ...
0
votes
1answer
23 views

What is “Standardizing variables” in the procedure of converting First Order Logic to CNF?

What is meant by the step "Standardize variables" in the procedure of converting First Order Logic to CNF? The 6 all steps can be listed as, ...
0
votes
0answers
9 views

Application of Compactness theorem

Let $\frak{R}$ be the structure $\left<\mathbb{N},+, \cdot,0,1\right>.$ If $\frak{A}$ is any structure for this language and if $a,b \in |\frak{A}|,$ we say $a$ divides $b$ in $|\frak{A}|$ if ...
1
vote
1answer
29 views

Converting statements with term 'only' and 'any' to predicate logic

How to convert following statement into predicate logic? 1)"Only dogs are mammals" 2)"Any dog is a mammal" Is there a difference between "Any dog is a mammal" ...
0
votes
1answer
17 views

Confined Quantifiers - Re Expressing formula

so I'm doing some study on Confined Quantification, and I understand how it when converting to english, but I don't understand how to re express the formula? I've tried watching videos but nothing has ...
1
vote
0answers
27 views

How is a quantifier-free formula actually interpreted?

My understanding is that a quantifier-free formula in FOL is simply a formula that contains no quantifiers, just possibly free variables. How is such a formula interpreted? My understanding is that if ...
0
votes
1answer
30 views

Can I say something about the cadinality of this model?

Let $L$ be some first-order language. Suppose $A$ is existentially closed in $K$, a class of $L$-structures whose age is at most countable, and age($A$) is at most countable set . Can we say anything ...
1
vote
2answers
47 views

How does predicate logic handle contradictory statements about something that does not exist?

Let p denote ringing telephone s denote someone A denote answered ¬∃x(Px) ∀x∃y((Px⋀Sy) →Ayx) ∀x¬∃y((Px⋀Sy) →Ayx) So, There are no ringing telephones. Every ringing telephone was answered ...
0
votes
0answers
54 views

Brute-force searches for counterexamples

Gödel's completeness theorem says that for every statement in first-order predicate caluculus with equality, there is either a proof that it holds in all structures, or a counterexample --- a ...
1
vote
1answer
40 views

Expressing “Highest” in First Order Logic

I'm writing a First Order Logic sentence to express a "Highest" function. (ie. highest temperatures in a city) I'm thinking along the lines of something like this: HighestTemp returns T1 s.t. ...
3
votes
2answers
56 views

How to interpret $\exists x (\forall x \Phi (x))$?

It's clear to me what the interpretation is when we have something like: $$\exists x (\forall y \Phi(x, y))$$ or even how to interpret the formula when x or y are not variables in the expression ...
2
votes
1answer
24 views

Equivalent formula in countable structures

Question, if two sentences A & B, are such that for all countable structures M: M⊨A iff M⊨B, and A & B be thus logically eguivalent. But how?! I understand that I have to use ...
0
votes
0answers
11 views

Comparing domains in FOL?

My math background is fairly weak, so I'll try to give a common sense example that conveys what I'm asking. Suppose I have a cake and two domains that are intended to represent to cake. the first ...
0
votes
1answer
26 views

First Order Logic with a continuous domain? [closed]

The domain of first order languages is usually given as a collection of singular terms. Is it possible to have a first order language with a continuous domain? Or even could it be the case that a ...
1
vote
1answer
53 views

First Order Logic “More Than One”?

I'm trying to figure out how to express "More than one" in first order logic. What I have so far is: $$\exists S_1 \exists S_2 IsGreen(S_1) \wedge IsGreen(S_2)$$ But that definitely doesn't sound ...
1
vote
1answer
24 views

What does rule schematic mean?

While I'm studying the mathematical logic, the book says "Each rule of such a calculus either says that certain strings belong to $Z$, or else permits the passage from certain strings ...
2
votes
1answer
95 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
0
votes
1answer
28 views

First-order linear differential equation

I have this question, and the working out below is as far as I can get: $$ x \frac{dy}{dx} - y = y^2 \\ p(x) = -\frac{1}{x} \\ q(x) = \frac{y^2}{x} \\ u(x)= e^{\int -\frac{1}{x}dx} \rightarrow ...
1
vote
5answers
170 views

First Order Logic

Is it possible to represent the english sentence with numerical value in First order Logic. For example if the sentence is: Nobody has more than one mother. I am wandering who can i show the ...
1
vote
1answer
49 views

Book on the first-order modal logic

Is there a book on the metatheory for the first-order modal logic, or do I just need to take FOL as a base and use the standard translation?
1
vote
0answers
24 views

Definability of structures

Good evening, I would like to know if my proof to a problem is correct. Below are the definitions and properties that I have used, followed by the problem in concern and my proof. Thank you. Let ...
1
vote
2answers
80 views

How to determine whether a set of propositions is consistent?

Definition of consistency is: A set of formulas ⊆ WFF is consistent iff there is no A ∈ WFF such that Σ ⊢ A and Σ ⊢ (¬A). Say you have a set of propositions statements (i.e. $A \lor B \rightarrow C$, ...
1
vote
1answer
23 views

Reflexivity of equality in sequent calculus

In definition 1.3.1 of Johnstone's Sketches of an Elephant are given axioms and rules for first order logic. I recall the ones I need for the question: (a) The structural rules consist of the ...
3
votes
3answers
124 views

Trivial proof in ZFC

Let's take some theorem of ZFC, e.g.: $$(1)\: \exists x \forall y ( y \notin x) $$ We can then choose a constant, denote it by '$\varnothing$' to get the following: $$(2)\:\forall x (x\notin ...
1
vote
1answer
44 views

Prove the admissibility of $\Gamma, A \vdash_N B $, from $\Gamma \vdash_N B$

(This is an assignment) To prove: $$\frac{\Gamma \vdash_N B}{\Gamma, A \vdash_N B}$$ ($\Gamma, A = \Gamma \cup \{A\}$) I have what I think is a proof for this. I would like and be grateful for ...
1
vote
1answer
41 views

Difference Between First Order Logic and Conjunctive Queries

What is the difference between First Order Logic and Conjunctive Queries ? Can you for instance give an example of FO query and Conjunctive Query for the following statement? Give the all the ...
2
votes
2answers
90 views

How to show tautologies in FOL using truth definitions?

Anyone know how to prove these tautologies by way of truth definition? I take it that to solve a), I need to disprove a minimal counter example to the formula/sentence given? If so, how to formally ...
1
vote
1answer
42 views

Help solving a challenge - relational algebra or second order logic

I am a self-taught man and I'm posting my first question here. I'm facing a challenge I'd like to solve. Based on what I know it fits propositional calculus (hope it is). Suppose 3 people: a ...
1
vote
1answer
38 views

First-order Peano Axioms and order-completeness of $\mathbb{N}$

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo. Notation: We denote the system of first-order Peano Axioms (along with ...
4
votes
2answers
72 views

Why is $\alpha \rightarrow \forall x(\alpha)$ not generally correct in first-order logic?

Why is $\alpha \rightarrow \forall x(\alpha)$ not generally correct in first-order logic? i.e., when there are free occurrences of $x$ in $\alpha$, and, on the same point, why is the formula scheme ...
0
votes
1answer
51 views

Boolean Queries in First Order Logic

I understand first order logic and how its constructed but I have some trouble understanding how the following statement and its FO query are formed. This is from a book. ...
2
votes
2answers
27 views

Qualification of a Universal Quantification

Let us say I have a predicate, $P(n)$, and I want to say that it holds for every integer greater than $2$ (an example would be $P(n) = 2n>2+n$). Let us furthermore say that the UOD (universe of ...
2
votes
1answer
33 views

Correct Way to Write a Statement in First-Order Logic

I am teaching myself set theory. I am at a point where the set of rationals, $\mathbb{Q}$, has been defined, along with its ordering relation, $<_\mathbb{Q}$. Now, working towards a definition of a ...
2
votes
1answer
58 views

Why is better to work with first-order Peano's axioms than with second-order Peano's axioms?

In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the second-order version the operations: addition, multiplication and exponentiation ...
2
votes
1answer
78 views

Why is better to work with first-order logic than with second-order logic? [duplicate]

Why is better to work with first-order logic than with second-order logic? In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the ...
1
vote
1answer
53 views

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ...
0
votes
1answer
34 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
3
votes
4answers
113 views

When do free variables occur? Why allow them? What is the intuition behind them?

In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound. Why would one write such a formula? Why are free variables allowed? What is the intuition for allowing free variables?
3
votes
3answers
122 views

Why isn't the inductive set _the_ set of natural numbers?

ZFC's axiom of infinity states: $$\exists x (\varnothing \in x \wedge \forall y \in x (y\cup \left \{y \right \} \in x)) $$ Isn't this set $ x $ really $\mathbb{N}$? It wouldn't be $\mathbb{N}$ if x ...
2
votes
0answers
25 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
0
votes
1answer
33 views

Is there a way to treat arrays as sets?

I was doing some F.O.L. problems and I noticed that quite a lot of them could be easily solved if I could just treat a given array as a set. Example: $B(1..n)$ is a permutation of $A(1..n)$ The ...
3
votes
1answer
67 views

Defining new symbols (abbreviations) in first-order logic

In first order logic it is common (and just about necessary) to introduce new symbols which have been defined in terms of the "fundamental" symbols of a given theory. For instance, the signature of ...
1
vote
1answer
52 views

Can integers be defined in the first-order theory of the rationals?

Can integers be defined in the first-order theory of the rationals with addition, multiplication, and order?
3
votes
1answer
32 views

Are all first-order truths of real arithmetic also true of the algebraic reals?

Consider sentences in first-order logic which are true of the structure $(\mathbb R, +, \cdot, <, 0, 1)$, where the symbols have their usual meaning. Is every such sentence also true of $(\mathbb ...
0
votes
1answer
49 views

Getting auxiliary assumptions from a conclusion

In the book I'm reading they say they want to deduce $(p \rightarrow q) \rightarrow (p \rightarrow r)$ from $p \rightarrow (q \rightarrow r)$. Now, as far as I understood, $p \rightarrow (q ...
0
votes
1answer
40 views

Confusion in Conjunctive normal forms

Which of the Following is TRUE about formulae in Conjunctive Normal form? For any formula, there is a truth assignment for which at least half the clauses evaluate true. For any formula, there is a ...
1
vote
1answer
34 views

The “disjunction” of two theories

I have three first-order theories $A,B,C$ at hand such that every model of $A$ either satisfies $B$ or satisfies $C$ (or both). Presumably, none of these theories is finitely axiomatizable. I ...
7
votes
2answers
187 views

A truth definition, wrong, but where

Consider the theory ZFC of language with connectives $\neg$, $\rightarrow$, predicative symbol $\in$ and quantifier $\forall$. Assume that we are working in ZFC. Let $\mathcal{V}$ be the class of ...
0
votes
0answers
25 views

What happens if a signature of structure doesn't match the predicate symbols

I am trying to understand what will be the definition of evaluating the truth value of a totally quantified predicate in a structure for which the symbols do not fully match the predicate's symbols. ...