The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
1
vote
0answers
32 views

Double-Substitutions in First-Order Logic

Let $\phi$ be a first-order formula, and let $\phi_t^x$ be the formula $\phi$ with term $t$ substituted for variable $x$. Exercise 6 in section 1.8 of Leary and Kristiansen’s A Friendly Introduction ...
1
vote
1answer
80 views

How to formalize this simple problem in logic?

I want to translate this problem with a simple logical expression. Say that my system only accepts tuples of strings $(s=s_1...s_n$, $t=t_1...t_n)$ where $s_i$ and $t_i \in \{0, 1, 2\}$, that are ...
0
votes
1answer
50 views

Writing a First-Order Language for a Basketball League

Here is exercise 4 in chapter 1.2 of Leary and Kristiansen's A Friendly Introduction to Mathematical Logic: You have been put in charge of drawing up the schedule for a basketball league. This ...
0
votes
0answers
30 views

Isn’t $P\rightarrow\forall xP$ the Generalisation Theorem?

The logical axioms I’m concerned with are mentioned in Wolf’s A Tour Through Mathematical Logic, Appendix A A Deductive System for First-order Logic which Wolf claims to have taken from Enderton’s ...
0
votes
0answers
20 views

How do the prenex conversion rules for conjunctions and disjunctions come from these logical axioms?

Wikipedia states the following rules: $(\forall x\phi )\land\psi$ is equivalent to $\forall x(\phi\land\psi )$ under (mild) condition ... that at least one individual exists), $(\forall x\phi )\...
1
vote
2answers
47 views

Quantifier difference notation

(1)$\exists x \in X \ ( P(x) \implies \forall y \in X P(y) )$ (2) $\exists x\in X P(x) \implies \forall y \in X P(y)$ What’s the difference? And are they both always true? It seems to me that the ...
0
votes
1answer
99 views

Is there any way to reduce standard second-order logic to first-order logic?

By saying "standard second-order logic" I am specifically ruling out Henkin semantics. It is my understanding that the approach generally taken is to map the second-order syntax to first-order ...
0
votes
1answer
86 views

Mathematical Logic (Shoenfield) : Lemma 1

Well, I am new learning about mathematical logic and I am using Mathematical Logic, Shoenfield. Now, I have a question regarding this lemma (the first lemma in that book) : Given two finite ...
0
votes
0answers
11 views

What is the formal translation of this statement?

Statement: For each $x$ in $X$, there exists a unique $y$ in $Y$ such that $(x,y)\in f$. Which is the correct translation? $\forall x\exists !y(x\in X\rightarrow (y\in Y\land (x,y)\in f)$ $\forall x(...
0
votes
1answer
72 views

How to determine the validity of statements in First Order Logic. Is there a general method?

For past few days I have been practicing problems related to validity of statements written in First-Order Logic, and I am wondering that is there an algorithm to check the validity of following types ...
1
vote
1answer
37 views

Completeness theorem: validity in some non-empty domain

The completeness theorem in my text says that if a formula $G$ is valid in the domain of natural numbers, then $G$ is provable in the predicate calculus. The corollary also says that then $G$ is ...
1
vote
1answer
51 views

How to show conservative extension without resorting to model theory?

Let $A$ be a set of wffs of first order logic, let $\varphi$ be a wff of first order logic, and let $a$ be a variable that is distinct from $a$ and that does not occur in any formula in $A\cup\{\...
0
votes
1answer
39 views

What does $\exists !x(P\rightarrow Q(x))$ translate to? A paradox?

Does it translate to $$\exists x\forall y((P\rightarrow Q(x))\land ((P\rightarrow Q(y))\rightarrow y=x)),\text{ or}$$ $$\exists x\forall y(P\rightarrow (Q(x)\land (Q(y)\rightarrow y=x)))?$$ $x$ is ...
0
votes
3answers
70 views

First-order logic and Peano Arithmetic paradox

I'm working through the Stanford Introduction to Logic course, and seem to have proved that all natural numbers are equal to zero: Ax.(x = 0). Obviously, this is ...
1
vote
1answer
55 views

Completeness of first-order logic with interpreted function symbols

A paper I'm reading asserts that "there is no sound and complete procedure for validity of first-order logic formulas of linear arithmetic with uninterpreted function symbols". By this we mean ...
0
votes
1answer
17 views

Prenex form of uniqueness quantifier

$\exists !xP(x)$ is generally defined as $$\exists x(P(x)\land\forall y(P(y)\rightarrow y=x)).$$ What is the prenex normal form of this? I think it should be $\exists x\forall y(P(x)\land (P(y)\...
0
votes
0answers
37 views

How to express “A is B” in first order logic

I would like to write "A is B" in first order logic. For example "Apple is food". Here are my guesses: $\exists x, s.t. \forall y, \mbox{food(x) & apple(y) & y} \in x.$ or simply $food(...
1
vote
3answers
49 views

Logic statements equivalence

Are the following two statements logically equivalent? Or does the second imply the first? Please explain. (1) $\forall x\in X$ $\exists$ $y\in$ Y: $P(x,y)$ (2) $x\in X$ $\iff$ $\exists y\in Y$ :$P(...
0
votes
1answer
21 views

Nonexistence of independent axiomatization of a theory in a finite language.

This is a follow up to two previous questions. I mistakenly thought that the theory of infinite sets in the language of equality had no axiomatization that was non-redundant. Now I am led to whether ...
1
vote
1answer
27 views

Does the theory of infinite sets in the language of pure equality have a non-redundant axiomatization?

This is a follow-up to a previous question. Consider the theory of infinite sets in the language of pure equality. Is there a set of axioms that axiomatize that theory where no axiom is redundant?
1
vote
2answers
193 views

Problem related to First Order Logic. Not able to approach the problem

Problem Statement: Consider the first order logic sentence: $$\mathbf \phi \equiv \exists s\exists t\exists u \forall v \forall w \forall x \forall y\; \psi(s,t,u,v,w,x,y)$$ where $\psi(s,t,u,v,w,x,y)$...
4
votes
1answer
68 views

Using compactness theorem to prove finiteness lemma

The finiteness lemma states the following: Fix an $o$-minimal structure $M$. Let $A\subseteq M^2$ be a definable subset, such that for every $x\in M$ $A_x=\{y|(x,y)\in A\}$ is finite. Then there ...
0
votes
0answers
33 views

Defining the notion of a perfect number in first order logic

Suppose I wanted to define in first order logic a predicate of natural numbers, $perfect$, where $perfect(n)$ for $n \in \mathbb{N}$ iff $n$ is a perfect number (i.e, a positive integer that is equal ...
2
votes
1answer
38 views

Is there a non-finitely axiomatizable theory in a finite language with an independent set of axioms?

Let $L$ be a finite language, and $T$ an $L$-theory that is not finitely axiomatizable. Can it ever be the case that there is a subset $S$ of $T$ with the same consequences as $T$, but such that every ...
-1
votes
1answer
58 views

Prove the following:proving formula in predicate logic

(∀y)(∀x)(¬𝑥=𝑦∨𝑥=𝑦)→(∀x)(¬𝑥=𝑥∨𝑥=𝑥) I am using Mathematical Logic by Dr. Tourlakis. My try: (∀x)(¬𝑥=𝑦∨𝑥=𝑦) ¬((∀y))(∀x)(¬𝑥=𝑦∨𝑥=𝑦) )∨(∀x)(¬𝑥=𝑦∨𝑥=𝑦) <1+A⊢B∨A> (∀y)(∀x)(¬𝑥=𝑦∨𝑥=...
0
votes
0answers
48 views

Prove or disprove a claim about sentences in first order logic

Let $A,B$ be two statements (i.e. WFFs without free variables) in first order logic. Prove or disprove: if $A$ and $B$ are satisfied in the same countable models, then $A\equiv B$. So my intuition ...
0
votes
1answer
33 views

query about first order logic [closed]

I would like to know how to convert this sentence to the first order logic There are three children called Alfred, Betty and Charles my try my try ∃x ∃y ∃z (isChild(x) ∧ isChild(y) ∧ isChild(z) ∧ ...
0
votes
0answers
29 views

Convert wff to pff ∃x[P(x)∧∀y[B(y)→L(x,y)]]

I'm doing an exercise in Mathematical Methods in Linguistics, Chapter 7, page 54. The task is to convert ∃x[P(x)∧∀y[B(y)→L(x,y)]] to its Prenex Normal Form. I followed the laws and the steps given ...
-2
votes
2answers
97 views

Confusion over what set theory is exactly

I am reading through Tao's Analysis. Tao defines all these rules for sets and they can be expressed in terms of first order logic, hence ZFC being a "first order theory." But then these "underlying" ...
0
votes
1answer
19 views

Converting to DNF. Demorgans then moved brackets. Correct/incorrect?

Disjunction normal form (DNF) consists of disjunctions of conjunctions (if I understand correctly). Ex. $(p \land q) \lor (p \land r \land s)$ I am facing this problem: $(t \implies \neg s) \land \...
0
votes
1answer
44 views

Show this sentence is not a consequence of these 3 preconditions

The sentence is: $$p=\forall x\forall e\forall u(u\in w(x,e)\leftrightarrow(u\in x \vee u=e)).$$ The preconditions are: $\forall v$ $\neg v\in \emptyset$ $\forall e\forall u(u\in w(\emptyset, e)\...
0
votes
1answer
37 views

Is my conversion of $\forall x(P(x)\rightarrow\forall yQ(y))$ to prenex normal form correct?

I convert using the following equivalences. $\forall x(P(x)\rightarrow\forall yQ(y))$ $\forall x\neg(P(x)\land\exists y\neg Q(y))$ $\forall x\neg\exists y(P(x)\land\neg Q(y))$ $\forall x\forall y(P(x)...
1
vote
0answers
13 views

What are the differences between a linear logic based planner and a first order logic based planner

Linear logic based planners and first order logic based planners must have different strengths and weaknesses. I would appreciate help in understanding what these strengths and weaknesses are and ...
0
votes
0answers
21 views

Primitive undefined notions in first-order logic

Correct me in my following understanding of why I consider the following (in bold and italics) to be primitive undefined notions. Variables stand for the mathematical objects that base the theory. ...
0
votes
0answers
18 views

Primitive notions in first-order logic

Are the following primitive notions in first-order logic? $\wedge$ and $\neg$ (if I define all other connectives in terms of these); $\exists$ (if I define $\forall$ in terms of it).
0
votes
1answer
23 views

Are these logically equivalent? [closed]

\begin{align} &\forall y(P(y)\rightarrow \forall x(Q(x)\rightarrow R(x,y)))\text{; and,}\\ &\forall x(Q(x)\rightarrow \forall y(P(y)\rightarrow R(x,y))).\\ \end{align} I think they are. But ...
0
votes
0answers
12 views

Is this a correct first-order formalisation?

Statement: $R$ is a set containing only ordered pairs. Translation: $\forall x(x\in R\rightarrow\exists a\exists b(x=\{\{ a\} ,\{ a,b\}\} )$
4
votes
1answer
47 views

A is prime over B, then A is also atomic over B

The definition of $A$ is atomic over $B$ is: Let $A$ be a model and $B \subset A$. An element $a \in A$ is atomic over $B$ if the type $\text{tp}(a/B)$ is isolated. If each element $a \in A$ is ...
0
votes
1answer
43 views

$P\rightarrow (Q\rightarrow R)$ in first-order logic

For statements $P$, $Q$, and $R$, by propositional logic, we have $P\rightarrow (Q\rightarrow R)$ propositionally equivalent to $Q\rightarrow (P\rightarrow R)$. Will it also be true (via logical ...
0
votes
1answer
62 views

How to show that these sets are equal?

Let $E$ be the set whose subsets only we’ll be talking of. Now complementation is a bijection on $\mathcal{P} (E)$. Hence the following two sets seem intuitively equal: \begin{align}& \{ x\in E: \...
1
vote
0answers
35 views

A structure interpreting a binary function symbol as average can't have $\mathbb{N}$ as its domain?

I thought about this question as a result of the following exercise in logic: Consider the following 4 formulae in first order logic: $\forall x(xx=x)$ (idempotency) $\forall x\forall y(xy=yx)$ (...
-1
votes
1answer
53 views

Showing that a knowledge base leads to empty clause

Using the resolution method, I want show that the following knowledge leads to the empty clause. $∃x (q(f(x))∧s(f(x),A))$ $∀x∀y¬∃z (p(x, y)∧s(x,z))$ $∀x (q(x)∧ ∃y s(x, y)) ⇒ (∃z (r(z)∧ p(x,z)))$ ...
1
vote
1answer
36 views

Graph planarity definability clarification in literature?

Here it says planarity is definable in first order. http://jgaa.info/accepted/recent/Brandenburg.pdf Here it says planarity testing of graphs is not a first order property. Refer https://simons....
1
vote
0answers
55 views

Expressibility of transitive closure on finite structures

Show that there is no formula of first-order logic which expresses "$(a, b)$ is in the transitive closure of $R$", even on finite structures. I know how to prove the result for infinite ...
1
vote
1answer
54 views

Are there non-linear forms of arithmetic that is logically axiomatized?

Informal idea: I'll visualize Peano arithmetic "PA" as arithmetic rising from a linear structure, we can call it in graph terms a linear directed path with a beginning and no end. The numbers are the ...
0
votes
2answers
51 views

Restrictions on Existential Introduction in first-order logic

I'm trying to understand the restrictions on Existential Introduction (EI) as defined by the Stanford introduction to logic. Three separate restrictions are mentioned: The term being replaced cannot "...
0
votes
0answers
35 views

Can ZFC be interpreted in this sole class theory about ordinals?

Informally the following theory is about classes of ordinals, so only von Neumann ordinals can be elements of classes. It has a primitive partial binary function of ordered pairing over ordinals, so ...
0
votes
1answer
53 views

Can withdrawal of the Power set axiom enable absoluteness for set size statements?

If we look to models of $\small \sf ZFC$ we can have two transitive models $N,M$ such that for some formula $\phi$ in the language of $\small \sf ZFC$ we have: $\forall \mathcal M ([\mathcal M\...
1
vote
1answer
50 views

Terminology “totally transcendental” in model theory

The following is a definition of totally transcendental (a concept in model theory): Where does the terminology "totally transcendental" come from? Does it have any connection with other notions of ...
3
votes
1answer
79 views

Intuition of Morley rank

One way to understand the Morley rank of a unary formula $\varphi(x)$ with $\text{RM}(\varphi(x)) < \omega$ is to imagine it as the height of an $\omega$-branching tree, where each node is mapped ...