Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [first-order-logic]

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

0
votes
1answer
9 views

LPL Fitch Exercise 6.20 Help

I have the premises $A\lor B$, $A\lor C$ And the conclusion $A\lor(B\land C)$ I am told that I will need to use a subproof within a subproof. I have been trying to do this for ages and I just ...
1
vote
1answer
19 views

Conversion of formula in Prenex Normal Form

Let we have a formula $\psi = \forall x (P(x) \vee \forall y Q(y,x))$. Is the formula equivalent to $\psi' = \forall x \forall y (P(x) \vee Q(y, x))$ in Prenex Normal Form. If so, What are the rules ...
3
votes
1answer
49 views

Where could I find a discussion about “minimal sets” of axioms for ZF(C) set theory?

I know ZF is not finitely axiomatizable so a "minimal set of axioms for ZF" is actually a minimal set of metaxioms (or axiom schemata) that quantify (in natural language) over well-formed-formulas of ...
3
votes
2answers
29 views

First order logic difference bettwen using exists and for all

I am trying to write the following statements in first-order logic. I have been given the functions: DirectorOf(A, B), IsMovie(A), and Equals(A, B): 1) All movies have an director. 2) No movies were ...
0
votes
1answer
31 views

How do we know that all the equivalence classes are infinite and there are infinite equivalence classes?

I'm given this definition of an equivalence relation. Let $\phi(x)$ and $\psi(x)$ be formulas (with the same set of free variables) written in some fixed language $\ell$. We say that $\phi$ and $\...
0
votes
3answers
41 views

Prove $∃x ∈ N∀y ∈ N : x < y$ [on hold]

How can I proof this formula if it is true or false. I know that this must be false, but how can I make the proof. $$∃x ∈ N∀y ∈ N : x < y$$ Is that the right negation of the formula: $$∀x ∉ N ∃y ...
0
votes
1answer
25 views

Lindenbaum's Lemma and the axiom of choice

I have doubts about the connection between the theorem of completeness for first order logic and the axiom of choice. I did hear that AC (possibly in a weakened form) is necessary to prove Goedel ...
4
votes
1answer
51 views

Definition of nonstandard models without enumerations

To define nonstandard models of Peano arithmetic or set theory, many articles use enumerations like $x>0, x>1, \dots$ where $x$ is said to be a nonstandard natural number, ie a number that is ...
0
votes
1answer
22 views

Can any 1st-order proof be expressed with an SMT?

Is it possible to rephrase every proof which uses first-order logic into a proof which uses satisfiability modulo theories? In other words, can a program which automatically solves SMT questions solve ...
1
vote
0answers
24 views

Is the subset of FOL with no function symbols and no predicates of arity > 1 decidable?

So, FOL logic in general is undecidable, but is the fragment that excludes function symbols and predicate symbols with arity > 1 decidable? I'm guessing it's not since it does not seem possible to ...
3
votes
2answers
60 views

Why does my proof fail to show the logical equivalence of (∀x)(Fx v Gx) ⊢ (∀x)Fx v (∀x)Gx?

Apparently (∀x)(Fx v Gx) is not equivalent to (∀x)Fx v (∀x)Gx, however I seem to be able to prove it syntactically: (∀x)(Fx v Gx) ⊬ (∀x)Fx v (∀x)Gx (1) (∀x)(Fx V Gx)-----premise (2) Fa v Ga----------...
0
votes
0answers
21 views

Numeralwise expressibility in logic

I am reading Chapter 8 Section 41 of Kleene's "Introduction to metamathematics" and I have encountered notion of "numeralwise expressibility". Next is a quote from the textbook: "Let $P(x_1, ..., x_n)...
0
votes
2answers
35 views

Negation of First Order Predicate Logic Example

There are at least two people who love each other and no one else If I were to negate this, this is my thinking: It is not the case that there are at least two people who love each other and no one ...
0
votes
1answer
48 views

Weakest theory equi-consistent to ZFC

I've recently read that ZF is equi-consistent to ZFC. From what I understand, to establish this we transform a formal proof of a contradiction in ZFC into a formal proof of a contradiction in ZF. We ...
4
votes
1answer
38 views

Completeness and homomorphisms between models

Suppose that $T$ is the first-order theory of a given class of models $C$ over some signature. Suppose $M$ is an arbitrary model of $T$. Does it follow that there is always a model $M'\in C$ and ...
2
votes
1answer
40 views

Is $[[\varphi]]$ a common notation for the set of $x$ satisfying a predicate $\varphi(x)$ in a specified model?

This question is merely about notation. Let $\varphi(x)$ be a predicate, i.e. a formula of first order logic, written in a given language, and having exactly one free variable denoted by $x$. Let ...
2
votes
1answer
39 views

Confusion in determining an argument's validity?

I understand that an argument is basically an implication in the sense that: $$premise1 \land premise2 \land premise3.... \to conclusion$$ And an argument would be considered valid when such an ...
9
votes
3answers
541 views

Why does Skolemming not preserve validity?

I'm wondering what exactly is meant when people say "Skolemization preserves satisfiability but not validity". I'm having trouble wrapping my brain around it because I think of Skolemization, when ...
0
votes
1answer
26 views

logical equivalence in predicate logic

I was studying discrete mathematics, one of the basic subjects in cs department. In particular, studying the chapter "Logics", I came to have some trouble. While solving problem saying " Let $S(x)$ ...
2
votes
1answer
72 views

Impredicativity in first order logic

There have been many debates about impredicative definitions in set theory, trying to judge whether they are good or bad. I'm not sure I understand them, because first-order logic theories can be ...
0
votes
1answer
25 views

Relation between depth and lenght of a formula in First-Order Logic

I'm currently reading Mathematical Logic by Helmut Schwichtenberg, and he introduces the concepts of length and depth of formulas like this [see page 3] : Definition. The depth $dp(A)$ of a formula $...
1
vote
2answers
48 views

Negating first order logic

I am struggling to understand how to really negate in first order logic. Take the following examples: "Somebody loves everybody" Negating this would be: "It is not the case that somebody loves ...
8
votes
1answer
63 views

Semantic proofs to syntactic proofs

Given a first-order logic theory $T$ and and a formula $F$, suppose I have semantically proved that $T\vdash F$. That is, I have proved that any model $M$ of $T$ satisfies $F$ and I conclude by Gödel'...
0
votes
1answer
36 views

Cardinality of finite sets in first order set theory

How would one determine if two finite sets have the same cardinality using first order set theory? Would there be a formula for showing that $$ F(x,y) \iff |x|=|y|?$$
0
votes
1answer
38 views

Pull Existential Quantifier to front in a FO formula

Consider a First order (FO) formula $\phi = \exists^*\forall^*\exists^* \psi$ where $\psi$ is quantifier free and function free (No n-ary functions, $n \geq 1$) matrix. I am searching for a formula (...
0
votes
1answer
26 views

Which statements is necessarily true for Models in first-order logic sentence given?

This questin is asked in GATE EXAM. Consider the first-order logic sentence φ≡∃s∃t∃u∀v∀w∀x∀yψ(s,t,u,v,w,x,y) where ψ(s,t,u,v,w,x,y,) is a quantifier-free first-order logic formula using only ...
5
votes
1answer
65 views

Necessity of universal quantifier in predicate calculus

I am reading Kleene's "Introduction to Metamathematics". There in Chapter 7 Section 32 he mentions two interpretations of free variables in predicate calculus. One of them is that "For the generality ...
1
vote
2answers
41 views

Why does it matter when we do a substitution of a free variable that some L-formulas don't preserve validity?

I was following these notes and there was a section where they showed the following formula: $$ \varphi(y) = \exists x (x \ne y)$$ and if one replaces the free variable $y$ with the variable $x$: $$...
1
vote
0answers
51 views

Applications of the compactness theorem. [closed]

It's well know that the compactness theorem has many aplication in model theory, its main shows existence of nonstandars models of aritmetical and the real numbers, and not elementary of some theories ...
1
vote
2answers
47 views

How does one show that an intersection of set of propositions is provable iff each proposition is individually provable?

I was going through these notes and wanted to prove the following: if $\Sigma \vdash \varphi_i, i \in [n] \iff \Sigma \vdash \varphi_1 \land \dots \land \varphi_n$ (without completeness of ...
1
vote
1answer
32 views

How does one show that every L-tautology $\varphi$ is provable $\vdash \varphi$?

I was following these notes and I tried doing exercise (5) on page 42: If $\varphi$ is an L-tautology, then $\vdash \varphi$ (without thm 2.7.4, completeness of predicate logic) intuitively it ...
0
votes
1answer
24 views

How does one prove that evaluating an L-term returns the recursive evaluation of all L-terms?

I was trying to do exercise 1 on page 30 from some logic notes. The question was to show: $$ {t^*}^{\mathcal A}(a_1,\dots,a_n) = t^{\mathcal A}(\tau_1^{\mathcal A}(a_1,\dots,a_n),\dots,\tau_m^{\...
1
vote
0answers
59 views

Contradiction in defining a new symbol, where's the error?

The theorem states the following: Let $T$ be a theory, $F(x_1,...,x_n,w)$ be a formula containing only $x_1,...,x_n,w$ free, $f(x_1,...,x_n)$ be a new function symbol that is not in both $T$ and $P(.....
2
votes
1answer
42 views

What is “the quantifier axioms of L” and why are they true in all L-structures?

I was going through these notes for logic. They started describing the axioms for predicate logic and said the following: The quantifer axioms of L are the formulas $\varphi(t/y) \to \exists y \...
2
votes
1answer
54 views

Usefulness of Gödel's incompleteness theorem

Given a first-order language $L$ and a theory $T$ in that language (a set of formulas of $L$), if $T$ is strong enough to prove arithmetic, then Gödel's second incompleteness theorem tells us that $T$ ...
1
vote
1answer
30 views

How to prove that every type can be realized using compactness theorem?

I could not understand the proof in David Marker's book because by definition a type $p(x_{1},...,x_{n})$ should be a collection of some formulas(rather than sentences) and I don't know what does "a ...
2
votes
1answer
41 views

Well-orders on non-standard models of Peano arithmetic

The standard model of Peano's arithmetic, $\mathbb{N}$, has the useful property that the order $\leq$ is a well-order. However, being a well-order cannot be expressed in the language of first-order ...
2
votes
0answers
31 views

Metric on the space of complete theories of a countable language

If I'm not mistaken, the space $\mathcal{T}$ of all complete theories of a countable language is a compact Hausdorff space, and moreover it is second-countable, since it has as its base the sets of ...
6
votes
1answer
38 views

Understanding convergence in the space of complete theories

Let $L$ be a given language and $\mathcal{T}$ be the set of complete theories in that language. We give a topology to $\mathcal{T}$ by considering as basic open sets the sets of the form $\langle \phi ...
0
votes
0answers
29 views

Most general unifier for set of equations?

Find the MGU in the following set of expressions $bar(1,Y,X,Y),bar(X,X,1,Z),bar(1,g(Y),1,f(W))$ Attempt I do not know if you can work with the 3 functions at the same time. So I did for 2 functions ...
2
votes
2answers
126 views

“Except” in predicate logic

I have a phrase that I am trying to translate into predicate logic. The phrase is as follows: All lions except old ones roar So far I have written down that: $∀x((L(x) \land \lnot O(x)) \to R(x))$...
1
vote
3answers
57 views

Interpretation of generality introduction rule

I have been reading Kleene's "Introduction to Metamathematics" Chapter 5 Section 24 where it is stated that $A(x) \vdash \forall xA(x)$ is a deduction rule. I was wondering on the interpretation of ...
2
votes
2answers
40 views

Relation between Empty Quantifiers and False Statements.

Consider the following statement about $\mathbb{N}$. $$\alpha: \forall \ prime \ p, \exists \ prime \ p' (p'<p)$$ This is false. Now, suppose a set of objects $\psi$ is empty. Now, consider the ...
0
votes
0answers
21 views

Relational first-order logic with each variable under a unary predicate

Is there a special name and research line for the relational first-order logic (i.e. without functions, only with predicates) whose well-formed formulas are such that for each variable ...
2
votes
1answer
42 views

Ultraproducts and the compactification of Lindenbaum algebras

I'm trying to understand the relationship between ultraproducts and the compactification of Lindenbaum algebras and I wanted to check if I'm getting thing right (so far). We start with a theory $T$ ...
1
vote
2answers
122 views

Predicate Statements— Every person loves at most only one reindeer

I was given a question by my professor during lecture today, to translate into predicate logic statements, "Every human loves a reindeer, but every human loves at most only 1 reindeer", without ...
1
vote
1answer
37 views

What does it mean by “$v$ is not restricted” in the rule of Existential Elimination?

In textbook First-Order Mathematical Logic, author Angelo Margaris stated: The rule of generalization is $$\large\dfrac{P}{\forall vP}\space\space\space\space \text{ provided $v$ is not ...
-1
votes
1answer
25 views

Truth assignments of a subset of sentence symbols

I am trying to prove that truth assignments of an infinite subset of sentence symbols are uncountable. I am new to mathematical logic and I am kind of confused. I learned the compactness theorem but I'...
0
votes
2answers
23 views

Expressing given problem in first order logic

I came across this problem in a test: Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes—for instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there ...
0
votes
2answers
46 views

Generalized associative law of union

$$\Large\bigcup\limits_{k\in\bigcup\limits_{i\in I}J_i}A_k=\bigcup\limits_{i\in I}\bigg(\bigcup\limits_{k\in J_i}A_k\bigg)$$ My attempt: $\large x\in\bigcup\limits_{k\in\bigcup\limits_{i\in I}J_i}...