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.

3,096 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
20 views

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 ...
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 ...
51 views

37 views

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 ...
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?
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)$...
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 ...
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 ...
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 ...
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)(¬𝑥=𝑦∨𝑥=...
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 ...
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) ∧ ...
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 ...
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" ...
19 views

37 views

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)... 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 ... 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. ... 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$\forallin terms of it). 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 ... 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\}\} )$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 ... 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 ... 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: \... 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)$(... 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)))$... 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.... 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 ... 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 ... 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 "... 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 ... 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\...
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 ...