Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [first-order-logic]

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

First-order logic contains, in addition to all symbols and rules of , the universal $\forall$ and existential $\exists$ quantifiers. These satisfy $\neg\forall xP(x)\iff\exists x\neg P(x)$ and $\neg\exists xP(x)\iff\forall x\neg P(x)$. First-order logic is used to build up the axioms of most set theory formulations, including Zermelo–Fraenkel.

5442 questions
12
votes
1 answer

What is the operator precedence for quantifiers?

Is the term $$\forall x p(x) \rightarrow \forall x q(x)$$ equal to $$\forall x (p(x) \rightarrow \forall x q(x))$$ or $$(\forall x p(x)) \rightarrow (\forall x q(x))$$ In other words: What is the operator precedence of $\forall$ and $\exists$? Does…
Martin Thoma
  • 9,821
7
votes
2 answers

How many variables in formal logic?

Remark: I assume the equality symbol „$=$“ with its standard semantics to always be included in first-order logic. Suppose we want to formalize some first-order theory. For our first-order language, we need to fix some set of variables and some set…
Lucina
  • 555
5
votes
1 answer

Finite axiomatization in logic with equality versus without equality

Is there a theory $T$ that can be finitely axiomatized in first-order logic with equality, which can also be axiomatized in first-order logic without equality, but not finitely axiomatized in first-order logic without equality?
user107952
  • 20,508
4
votes
2 answers

Validity undecidable in first order logic

I am a little confused about the decidablity of validity of first order logic formulas. I have a textbook that seems to have 2 contradictory statements. 1)Church's theorem: The validity of a first order logic statement is undecidable. (Which I…
Murdock
  • 223
4
votes
2 answers

Injective homomorphism that isn't a strong homomorphism

I'm taking a college course about first order logics right now and the teacher emphasised the difference between a homomorphism and a strong homomorphism. He also asked us to provide a example of a injective homomorphism that isn't an embedding…
Indinellow
  • 41
4
votes
1 answer

Fragment of ZFC to prove first-order completeness theorem

If I am not mistaken PRA or an even weaker theory suffices to develop the syntactics of first-order logic (at least for finite or countable languages). To develop the semantics of first-order logic sets are assumed. I am wondering what fragment of…
Joel Adler
  • 707
  • 3
  • 8
4
votes
2 answers

Is power-associativity finitely axiomatizable?

Let the signature under consideration be $(S,*)$, which is the signature of magmas. Power-associativity can be axiomatized by an infinite set of equations. Can it also be axiomatized by a finite set of equations, or if not, a finite set of first…
user107952
  • 20,508
3
votes
1 answer

how many variables in first-order language?

The book I use deals mostly with countable first-order languages. In these there are countably many variables. Do you demand uncountably many variables in uncountable languages or do countably many variables suffice, since formulas are always…
Pi o r
  • 143
3
votes
1 answer

Prove that, for any $\Delta_0$ sentence $\sigma$, QE$\models \sigma \leftrightarrow \sigma$ is true in $\eta$

A formula $\varphi$ of $L^A$ is $\Delta _0$ if $\varphi$ belongs to the smallest set containing the atomic formulas and closed under negation, forming conditionals, and bounded quantification. Closure of $\Delta _0$ under forming conditionals means…
TooYoung
  • 135
3
votes
2 answers

Are partial orders definable in first order logic without equality?

Consider a first order language without equality, and just one relation symbol P. Is there a set of axioms(which could be either a finite or infinite set) in that language, such that all those axioms will be true iff P is a reflexive partial order?…
user107952
  • 20,508
3
votes
1 answer

Formal proof of $\exists x \forall y P(x,y) \implies \forall y \exists x P(x,y)$

Say that the variables $x,y$ of a predicate $P$ are taken from some non-empty set. It is clear that the following statement is true. How should a formal proof look? $$\exists x \forall y P(x,y) \implies \forall y \exists x P(x,y)$$
Daugmented
  • 546
3
votes
0 answers

Is this a correct translation of english to first order logic?

Working through first order logic examples and want to make sure I am translating correctly before moving on to harder resolution of first order logic Use the predicates HasBugs(x), Comments(x), HighQuality(x), QuickSolve(x), and BestPractice(x),…
RTT
  • 35
3
votes
3 answers

Need help with first order logic

I'm trying to understand first-order-logic and have this simple question. Given the following predicates: $Thing(t)$, which states that $t$ is a thing; $Word(w)$, which states that $w$ is a word; and $HurtsYouMoreThan(x,y)$, which states that $x$…
Victor
  • 111
3
votes
1 answer

Function and Predicate Symbols in First Order Logic and Thoughts for the Connection between Math and Computer Science

Some FOL systems are equipped with function symbols, while some are not. Since function symbols apply to terms without restriction, terms like "father(Adam)" are well accepted, where Adam is the first man in the world. This causes a problem: objects…
Ziqi Fan
  • 1,816
3
votes
1 answer

Proving tautologies using semantic definitions

I know how to prove tautologies with truth tables, but not with semantic definitions. How can I prove, using the semantic definitions, that the following are tautologies? \begin{gather} \bigl(\exists x\,P(x) \lor \exists x\,Q(x)\bigr) \to \exists…
user81265
  • 33
1
2 3
…
26 27