Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
2answers
36 views

Definition of Semantic Entailment in First-order Theory

I cannot understand the meaning of the soundness theory in first order logic. It says that if $S$ syntactically entails $p$, then $S$ semantically entails $p$. However, $p$ don't have to be a ...
1
vote
1answer
44 views

Exercises involving Morley rank & degree

The definitions of Morley rank & degree I use are I understand these definitions, but I am having a hard time to use them concretely in exercises. For example, Let $L$ be a countable language ...
-4
votes
0answers
35 views

Logical programming

“Anyone who eats junk food or drink carbonated beverages will be a cancer victim. It is not the case that some people eat junk food but they are healthy. Every cancer victims are not healthy. Bimal is ...
1
vote
1answer
41 views

Existence of a prime model for a theory

Consider the language $\mathcal{L} = \{P, f\}$ with $P$ a unary predicate and $f$ a unary function. Let $T$ be the theory: $f$ is a bijection $\forall x \, f^nx \neq x$ for all $n$ $\forall x \, (Px \...
-1
votes
1answer
66 views

Why a language with equality in first order predicate logic has only infinite models?

I need to prove that there is no set of wff Σ of the language with equality (i.e. the language the only symbol of which is that of equality and the interpretations of this language are sets) such that:...
1
vote
1answer
47 views

The theory of (Z, s) has quantifier elimination

Let $T = \text{Th}(\mathbb{Z}, s)$ where $s$ is the successor function. I want to show quantifier elimination (QE) for $T$ and construct a concrete $\omega$-saturated model. However, I am unsure ...
0
votes
1answer
24 views

Is this formula an atomic formula?

For example, the formula $\forall x.\;P(x)\wedge∃y.\;Q(y,f(x))\vee∃z.\;R(z)$ contains the atoms $$P(x),\;Q(y,f(x)),\;R(z) $$ I'm reading definition from wikipedia but I'm somehow confused if this ...
0
votes
0answers
49 views

A theorem of Skolem

I believe the following is a theorem of Skolem. How is it proved, or where may I find a proof? Suppose $\mathscr A$ is a formula of first-order logic in which no constants or function symbols occur ...
2
votes
1answer
32 views

Are my logical translations correct?

I am reading Halmos’ Naive Set Theory. I attempt to translate the axioms of set theory as Halmos puts them in formal first-order logic containing equality and belonging. Please check if these are ...
0
votes
3answers
40 views

Mistake in $A \times B \subseteq C \times D \rightarrow A \subseteq C \wedge B \subseteq D$

I am currently going through Velleman's How to prove it and I am trying to understand exercise 12 from chapter 4.1. The exercise asks to show whether the theorem in the title is correct. It is ...
0
votes
2answers
827 views

Proof by contradiction in predicate logic

So we are given the following to prove, only by proof by contradiction $\forall x(Q(x)\to P(y)) \vDash \forall xQ(x)\to P(y)$ Now the first thing that comes to mind in predicate logic when i am on a ...
0
votes
1answer
24 views

differentiable function with only positive/negative slope impies strictly increasing/decreasing

If $f:(a,b)\rightarrow\mathbf{R}$ is differentiable and 1.$f'(x)>0$ for all x $\in (a,b)$. $\ \ $then $f$ is strictly increasing on (a,b). 2.Similarly, if $f'(x)<0$ for all x $\...
0
votes
2answers
43 views

Truth value of an open formula

I've always thought that an open formula, i.e. a formula containing free variables, has no truth value. For example, strictly speaking, I would say that for $x\in\mathbb R$, the formula "$x^2\geq0$" ...
0
votes
0answers
15 views

Can full Replacement be proved from replacement from sets of ordinals?

In a prior posting about "Ordinal Replacement", Joel David Hamkins had answered it, and his answer included the following statement: In fact, in this case, we needn't restrict $B$ to consist of ...
0
votes
3answers
62 views

Two definitions of exists unique

$\exists!x_0 \in S,P(x_0)$ Definitions: 1.$\exists x_0 \in S, P(x_0)\wedge(\forall x_1,x_2 \in S, P(x_1)\wedge P(x_2)\rightarrow x_1=x_2)$ 2.$\exists x_0 \in S, P(x_0)\wedge (\forall ...
0
votes
1answer
49 views

Lampert's supposed solution to the Entscheidungsproblem

Here: http://www2.cms.hu-berlin.de/newlogic/webMathematica/Logic/FOLDECISION2.pdf Timm Lampert claims to refute the Church-Turing theorem that first-order logic is undecidable. I'm wondering where the ...
0
votes
2answers
36 views

if $M_1,M_2$ are two structures for FOL $L$ that differ in interpretations of signs not in statement $A$, then $M_1 \vdash A$ iff $M_2 \vdash A$

Let $L$ be a first order language. Let $A$ be statement, and let $M_1,M_2$ be two structures for $L$. I want to prove that if $M_1$ and $M_2$ differ in interpretation only of signs that aren't in $A$ ...
0
votes
0answers
30 views

Infinite Conjunction vs. Compactness

How is what Quine (Methods of Logic, 1959, p. 254) called "the law of infinite conjunction" different from the compactness theorem for first order logic? The former states that if a finite or ...
3
votes
1answer
48 views

Existentially closed models of bowtie-free graphs

Setting Definition(1). $\mathcal{M} \models T$ is an existentially closed (e.c.) model of $T$ if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists ...
0
votes
1answer
16 views

FOL-Interpretation of a tableaux

Suppose I have the FOL-Formula $F := \forall x \exists y. R(x, y)$ in negation normal form. Now I want to show that $F$ is satisfiable using the tableaux calculus (TC1). By application of rules I get ...
2
votes
1answer
56 views

MGU - most general unifier for skolem functions?

I have trouble understanding MGU for functions, especially skolem functions. Is it correct that in order to find MGU for 2 functions, say f(x) and g(y) then they ...
1
vote
1answer
68 views

Ideal treatment of set theory as a meta theory for developing first-order logic

I am very familiar with the fact that when introducing model theory and the meta theorems describing a formal system, set theoretic notions are inevitably required which we include in the meta theory. ...
-2
votes
0answers
24 views

Prove that $\Gamma$ $\vdash$ $\phi$ iff. $\Gamma$ $\vdash$ $\phi_c^x$ for any constant symbol c not occuring in $\Gamma$

i have a bit problems with this, $\Gamma$ is a set of sentences in a language, and let φ be a formula in the language. can anybody help, im pretty lost
0
votes
1answer
66 views

Proof that Peano Axioms is a theory with equality (according to Mendelson book)

I'm reading Elliott Mendelson's "Introduction to Mathematical Logic". There is a statement with a proof that $S$ (Peano Arithmetic) is a first-order theory with equality. I am not sure whether I ...
-1
votes
0answers
26 views

Can this simplified arithmetical theory with a syntactically non reachable last natural be complete?

The following theory is coined in the language of arithmetic, however it differs in that the successor, addition and multiplication functions are not total functions. Also we add a new constant $L$ to ...
3
votes
1answer
81 views

Statements vs Formulas

In A Tour Through Mathematical Logic, Wolf states that Every formula of a first-order language is a statement in the sense of Section 1.2, but not conversely. In Section 1.2, Propositional Logic,...
1
vote
3answers
36 views

How to write an implication whose antecedent quantifies a variable in its consequent?

I want to write the statement $$\text{If } A^{-1} \text{ exists then } A^{-1} = \frac{\alpha-a}{\alpha^2-a^2}$$ using quantifiers. Note that $A$ and its inverse, if it exists, are taken from the set ...
2
votes
1answer
81 views

Derivative proof involving MVT and Rolle's Theorem

Suppose $f$ is a continuous and differentiable function on $[0,1]$ and $f(0) =f(1)$. Let $α∈(0,1)$. And $$∀x,y∈(0,1) ,f′(x)\neq 0\wedge f′(y)\neq 0\rightarrow f′(x) \neqαf′(y)$$ Show ...
0
votes
1answer
24 views

On rewriting the statement into predicate logic.

I'm interested in rewriting mathematical statement into predicate logic. Is the following correct? Normal Expression the following $x$ exists, such that $x \in R,x^2-1=0$ Predicate Logic ...
-1
votes
1answer
63 views

Deduction for $\exists v_1 \forall v_2 \lnot f(v_2) = v_1 \vdash \exists v_1 \exists v_2 \lnot v_2 =v_1$

I'm trying to find a deduction for $$\exists v_1 \forall v_2 \lnot f(v_2) = v_1 \vdash \exists v_1 \exists v_2 \lnot v_2 =v_1$$ with these axioms & lemma. For any function $f$ and relation $R$ ...
2
votes
2answers
54 views

Logical Axioms and Rules of Inference

In A Tour Through Mathematical Logic, Wolf mentions that These [logical axioms] usually include some or all tautologies, the usual equality axioms, and some simple laws involving quantifiers. ...
-1
votes
1answer
82 views

Resolution Principle in First Order Logic

Suppose that we are in First Order Logic and we have a set of clauses. I want to prove that a certain clause is a logical consequence of this set of clauses. Is it correct to use the Resolution ...
1
vote
0answers
31 views

Can this simple form of double extension set theory escape inconsistency?

The following theory is another way of dealing with naive comprehension. It uses the double extension principle, broadly speaking similar to what's used in Double Extension Set Theory of Andrzej ...
1
vote
0answers
55 views

Is this theory of arithmetic with a last natural that is not reachable from below complete?

This theory is a theory of arithmetic having a last natural number that is not reachable from below by syntactical recursive iteration of the successor function. So it doesn't prove all rules of ...
2
votes
1answer
47 views

Natural Deduction: Universal Introduction rule concerning free variables in Van Dalen's “Logic and Structure”

The $\forall I$ rule (forall introduction) in Dirk van Dalen's Logic and Structure (4th ed) is: $${\forall I}\, \frac{\varphi}{\forall x\, \varphi} $$ where the intended restriction is: the variable ...
0
votes
1answer
47 views

every relation in a special structure $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= |M|$.

Let $M$ be a special structure. I'm trying to proof that every relation in $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= \lambda$. By a first-order definable ...
0
votes
0answers
30 views

Is this simple class theory equi-interpretable with ZFC?

he question here is about the consistency of a rather very simply presented theory and if it is equivalent to ZFC. The theory is a first order theory of classes, so it has its primitives being ...
2
votes
1answer
44 views

Marker 4.5.36 - Showing elementary equivalence between two structures

This is a question about part b) of the question. Below I'll show the major 'results' in my attempt at the solution, as well as where I got stuck: 1. I defined a new $\mathcal{L}$-structure $\...
1
vote
2answers
58 views

Can Naive Set Comprehension survive in multi-valued logic?

If $\phi$ is a formula in which $x$ is not free, then: $(\exists x \ \forall y \ (y \in x \leftrightarrow\ \phi)) $ is an axiom. This is the inconsistent Naive comprehension axiom. Is this a ...
-2
votes
0answers
20 views

Can potential versus actual membership evade set theoretic paradoxes?

If we informally view a set as a container, and view set membership as an invitation for entry into a container. If that invitation is fulfilled, i.e. there is an instance of entry into the container, ...
0
votes
0answers
34 views

Variable subtitution in FOL formula with nested and outer quantifiers

I am given the formula: $\Psi={{\forall}}x\exists y\left(\exists z{{\forall}}xR\left(x,z,w\right)\land\exists wP\left(w,x,z\right)\right)$ for which I'm required to determine if a given simultaneous ...
3
votes
2answers
375 views

Proof of Decidability of Monadic First Order Logic

I'm looking for the proof of decidability of Monadic FOL (i.e. FOL limited to predicate symbols of arity at most one and no function symbols). In the Wikipedia page there are two references (dated ...
2
votes
2answers
43 views

What is the first order logic statement of “this field is of characteristic zero”?

I want to state that a field $F$ is of characteristic zero in logical notation to an audience without referring them to the meaning of the characteristic of a field. My first thought was the ...
0
votes
1answer
75 views

Is having models with ever increasing cardinality of the power set of $\omega$ is a theorem of ZFC?

I'll present this claim informally and try to write it formally as much as I can. Statement: every model of $\sf ZFC$ that statisfies the statement that the power set of $\omega$ is equal to a ...
0
votes
0answers
86 views

Had $\sf Con(ZFC)$ been explicitly written in first order language?

One always hear of $\sf Con(ZFC)$ and what is meant by that is an arithmetical sentence that is equivalent to $\sf ZFC \text { is consistent }$ that is written in the language of first order $\sf ZFC$....
0
votes
1answer
25 views

Conjunction vs Implication from a linguistic perspective.

I am translating some English sentences to FOL and sometimes the use of conjunction and implication confuses me, so I am trying to come up with a rule. I have given some examples: Every student doing ...
1
vote
0answers
23 views

Can we have strong theories in which all sets are Dedekindian finite?

Can we have a strong class theory in which all sets are Dedekindian finite, and that has some of its sets being Tarski infinite? By strong I mean that it can interpret $\sf ZFC$ and its extensions. ...
5
votes
2answers
54 views

Quantifiers in first-order logic

The universal $(\forall)$ and existential $(\exists)$ quantifiers are the normal quantifiers which one comes across frequently. Others like uniqueness quantifier $(\exists !)$ are also there. But in ...
0
votes
0answers
53 views

Can this extension of a fragment of Ackermann set theory survive inconsistency?

Lets work in the language of Ackermann set theory., which is first order logic with equality $``="$, class membership $``\in"$, and sub-world $``V"$, where the last is a constant symbol informally ...
0
votes
1answer
68 views

Is Reflection consistent with Resemblance?

The following theory is a class theory that combines two principles that of reflection and resemblance, informally it says that the class $V$ of all sets resembles a set $W$ that stands as a sub-world ...