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

learn more… | top users | synonyms

0
votes
1answer
9 views

Rule T in First-Order Logic

In Enderton's A Mathematical Introduction to Logic (second edition, page 118), we are given the so-called Rule T (Lemma $24C$) : If $\Gamma\vdash\alpha_1,\ldots,\Gamma\vdash\alpha_n$ and ...
0
votes
1answer
14 views

Entailment Checking Description Logic

I am reading a research paper in Description Logic. Say L be a knowledge base which consists of axioms. Then $C \sqsubseteq D$ is an axiom. Theorem: L $\vDash C \sqsubseteq D $ iff L $\vDash C ...
-1
votes
0answers
12 views

Can one decide if an inflationary FP sentence can be expressed as FO?

I'm studying for a final exam by trying to review some problems from around the internet. I don't know where to start on this one: Prove that it is undecidable whether a given inflationary fixpoint ...
1
vote
0answers
13 views

Extension of Tarski's result on the decidability of reals

Due to Tarski's result, it is well-known that the theory of reals $(\mathbb{R},+,\cdot,<,=,0,1)$ is decidable. I am working on a paper where I need an extension of this result. More precisely, I ...
0
votes
1answer
20 views

Can we program a computer to check a proof in first-order arithmetic is valid, and can we find out whether such a statement is true?

Slightly confused by this. I wish I knew what more to add, but I know it's asking something about the halting problem, and something about Godel but I cannot seem to figure it out.
0
votes
2answers
18 views

Using substitution to make an equation into a separable differentiable equation

I have the question: By making the substitution $y = t^nz$ and making a cunning choice of n, show that the following equations can be reduced to separable equations and solve them. $$\dfrac{dy}{dt} = ...
0
votes
1answer
49 views

show that a horn sentence is preserved under a direct product.

show that a horn sentence is preserved under a direct product. If $\varphi$ is a horn sentence and $\mathfrak{A}_i, i \in \text{I}$ is a model for $\varphi$ namely $\mathfrak{A}_i \vDash \varphi$ ...
1
vote
0answers
33 views

show that the theory of fields cannot be axiomatized by horn sentences

show that the theory of fields cannot be axiomatized by horn sentences im not sure how to show it, nearly everything is quantified so easily no free variables, maybe something to do with $\neg0 ...
2
votes
1answer
38 views

Proving that every submodel of DLOE is an elementary submodel

Let $A$ and $B$ be models of the theory of Dense Linear Orders without Endpoints such that $|B| \subset |A|$. I'm trying to prove that $B$ is an elementary submodel of $A$. Using Tarski-Vaught test I ...
1
vote
1answer
37 views

Left and Right hand associativity equivalent first order logic

Say we are in a first order theory, and one of our inference rules is the associative rule saying that we can infer $(A \vee B) \vee C$ from $A \vee (B \vee C)$. Using the other logical inference ...
5
votes
0answers
68 views

On proving the zero-one-law for first order logic

I'm trying to understand the proof of the zero-one-law for first order logic as provided in (Ebbinghaus-Flum, 1995). It goes as follows: Let $\tau$ be a relational signature. Let $r\in\mathbb{N}$, ...
0
votes
1answer
49 views

Question about understanding an Interpretation definition in First Order Logic

I am trying to understand a definition within First Order Logic using interpretation. Below is the specific interpretation definition We define the truth value of a formula A in an interpretation I. ...
1
vote
1answer
33 views

Every complete axiomatizable theory is decidable

Enderton (in A Mathematical Introduction to Logic) gives the following theorems: Theorem $17$F : A set of expressions is decidable iff both it and its complement (relative to the set of all ...
1
vote
2answers
31 views

Properties of the deductive closure

Let $\Phi_0$ be the set of $\cal L$-sentences. For $\Gamma\subseteq\Phi_0$, the deductive closure of $\Gamma$ is given by $$\mathsf{Cn}(\Gamma)=\left\{\phi\in\Phi_0\mid\Gamma\vdash\phi\right\}$$ ...
0
votes
3answers
44 views

Why if for all x, p(x) and for all x not p(x) is not a contradiction?

$\forall x: p(x) \equiv1$ and $\forall x: \neg p(x) \equiv 1$ is not a contradiction? I have this doubt after a logic contest, and I cant see why. My thoughs was that this is not a contradiction ...
1
vote
1answer
43 views

Mathematical Logic descending chains

I'm working on a mathematical logic question. Suppose $<$ belongs to $S$ and $\Phi \subseteq L_{0}^{S}$. Assume that for any $m \in \mathbb{N}$ there is a model $\mathfrak{A}$ of $\Phi$ such ...
2
votes
1answer
98 views

A problem in the first-order predicate calculus.

So the teacher decided to make our life harder by giving us an extra-credit problem: Use the language of the first-order predicate calculus to express that in a group $ S $ of elements with a ...
1
vote
1answer
29 views

Axiomatizability in monadic second-order logic

For my thesis in finite model theory I'm considering some basic classes of structures, and I want to show in which logical systems they can or cannot be axiomatized. I now consider the class ...
1
vote
0answers
33 views

If $\nvDash\phi$ must it be $\vDash\lnot\phi$? If $\nvDash\phi$ where $\phi$ first order sentence must it be $\vDash\lnot\phi$?

I am stucked at this problem: Determine wether the following sentences are true or false in first order logic: (1) If $\nvDash\phi$ must it be the case that $\vDash\lnot\phi$? (2) If ...
0
votes
0answers
24 views

Finite model or no models?

An FO sentence has the finite model property if either it has no model or it has at least one finite model. Show that it is undecidable if an FO sentence has the finite model property. Any hints?
0
votes
1answer
64 views

Some exercises on Models in First Order Logic [closed]

So these are some practice exercises for a Math Logic exam, I can't get a hold on how to do these. Semantically what does T = Th(N) represent? And how do I go about constructing a model A for T, ...
0
votes
1answer
69 views

Characterisation of a complete first-order theory

Let $T$ be a set of formulas of a first-order language $L$. Show that $T$ is complete if and only if there is no sentence $A$ of $L$ such that both $T \cup \{ A \}$ and $T\cup \{\neg A\}$ are ...
0
votes
0answers
19 views

Extending monadic predicate calculus

If we used currying to extend monadic predicate calculus to polyadic predicates, would validity of a formula in this predicate calculus be decidable? Why or why not? EDIT: I am led to believe that ...
1
vote
0answers
56 views

Why does a definition of multiplication in Presburger Arithmetic result in an undecidable theory?

Presburger Arithmetic is a decidable theory but if multiplication is added to it would that theory remain decidable? UPDATE: I began to write out the axioms that would distinguish Presburger ...
0
votes
0answers
40 views

Name of this rule: $a \vdash b$ and $b \vdash c$ then $a \vdash c$?

I'm trying to provide names of meta-theorems at each stage in my proof, and I forgot the name of the rule that says $a \vdash b$ and $b \vdash c$ then $a \vdash c$. Does anyone know?
1
vote
1answer
25 views

There are exactly N objects in the universe in first-order logic

For one object in the universe, the sentence would be: ∃x∀y (x=y) For two: ∃x1,x2∀y [(x1=y ∨ x2=y) ∧ (x1 ≠ x2)] But what about for N objects? The only way I can think of doing this is by using ...
0
votes
1answer
23 views

semantic tableaux - can't show sequent is valid

I have the sequent $\forall x\forall y(Rxy\to(Fx\lor Gy)), \forall x(Fx\to Gx) \vdash \forall x(Gx\lor \exists\lnot Ryy)$ I have tried several different ways, and I know all branches are supposed to ...
1
vote
3answers
142 views

Isn't the axiom of determinacy inconsistent with ZF? What am I overlooking?

I'm sure there's something I'm missing here; probably a naive confusion of mathematics with metamathematics. Regardless, I've come up with what looks to me like a proof that (first-order) ZF+AD is ...
1
vote
1answer
62 views

What does “Fixed-Point Lemma” says intuitively?

The lemma as stated in Enderton's logic says: Fixed-Point Lemma.   Given any formula $\beta$ in which only $v_1$ occurs free, we can find a sentence $\sigma$ such that $$ A_E \vdash ...
0
votes
1answer
26 views

Can First Order Logic identify that two variables are the same object?

Supposed I defined: $Px$ = $x$ is a person $Lxy$ = $x$ loves $y$ And I expressed that everyone loves someone: $$(∀x)(Px \implies (∃y)(Py ∧ Lxy))$$ However I want to formally exclude narcissists ...
0
votes
0answers
44 views

Validity of a first-order formula

How can I see (and prove) whether the given first-order formula $\varphi$ is valid or not? $\varphi = \forall x \forall y [ (r(x,y) \rightarrow (p(x) \rightarrow p(y))) \land (r(x,y) \rightarrow ...
0
votes
1answer
45 views

Bound Variable and Free Variable, A Questions and one Example?

I see a Local Contest Question as : for statement $ \forall x [ \exists y ( x<y+z) \to \exists z (x < y+z)] $ two following axiom is True: I) $ y, z$ is free and $x$ is bounded. II) ...
3
votes
1answer
62 views

What are the L-sentences that are true in an empty structure?

I am looking for an algorithm or set of rules to figure out whether a sentence (in first order logic) is true when we are dealing with an empty set as domain. Clearly, it has to be a sentence (no free ...
3
votes
2answers
133 views

Do we know if the consistency of $ \mathsf{ZFC} $ is sufficient to prove that $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) \to \mathsf{SM} $?

This is basically a sequel to this earlier post. There, I asked: If $ \mathsf{ZFC} $ is consistent, then is $ \mathsf{ZFC} \nvdash \neg \text{Con}(\mathsf{ZFC}) $, i.e., $ \neg ...
7
votes
9answers
272 views

If $4=5$, then $6=8\,$ (yes or no?)

I had an argument with a friend about the statement in the title. I asserted that if $4=5$, then $6=8$, as you can derive any conclusion from a false statement. However, he does not agree, and claims ...
0
votes
1answer
28 views

Union of a chain of consistent subsets is consistent.

In a proof of Gödel's completeness theorem via Lindenbaum's Lemma I have seen it is necesssary to prove that if we have a chain of consistent sets, ordered by the $\subseteq$ relation, the union over ...
1
vote
0answers
33 views

Show that $\Phi$ is negation complete.

Im working on a FOL exercise but i'm a little stuck here. Let $S$ be a symbol set and $\mathcal{J} = (\mathcal{U}, \beta)$ an $S$-interpretation. Further let $\Phi:=\{\varphi\in ...
0
votes
1answer
40 views

Exam preparation: logic - problems on (maximally) consistent sets

I am preparing for an exam on aspects of Logic related to propositional and first order logic. One of my revision exam questions is . I have attempted this question but I am really struggling with ...
2
votes
0answers
57 views

Dependence of axioms of Zermelo set theory

I'm reading a book about Zermelo–Fraenkel set theory, and I was told that there are a lot of dependence relation among the commonly used axiom system (in the question What axioms does ZF have, ...
1
vote
1answer
96 views

Reference request for the independence of $ \text{Con}(\mathsf{ZFC}) $.

Gödel’s Second Incompleteness Theorem says that if $ \mathsf{ZFC} $ is consistent, then $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) $, i.e., $ \text{Con}(\mathsf{ZFC}) $ is not provable in $ ...
0
votes
0answers
24 views

Derivation: Discerning difference between arithmetic expression with parenthesis versus without using abstract syntax trees

I am trying to illustrate the expression: ( 3 * 4 + 5 * 6 + 7 ) using an abstract syntax tree. I have already illustrated the expression: ( 3 * (4 + 5) * (6 + 7) ). Could someone please illustrate ...
0
votes
0answers
58 views

A provability puzzle

This is a problem I came up with on my own, and it has me stumped, so I am going to pose it as a kind of puzzle. Let $F$ be a formal proof system, recursively axiomatizable, with an acceptable ...
2
votes
1answer
76 views

How show $ S \models \forall x ( \alpha \Leftrightarrow \beta)$?

I read some notes on Logic Course. I read that we can conclude: $$ S \models \forall x ( \alpha \Leftrightarrow \beta)$$ if and only if $ S \models \forall\, x\, \alpha$ has conclusion $ S ...
0
votes
0answers
38 views

Do indiscernibles imply additional non-stardard models?

From Wikipedia Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Question: does the ...
-1
votes
1answer
40 views

first order: show that $\forall x (\phi \vee \psi) =\hspace{-.4em}|\models (\phi \vee \forall x \psi)$

first order: show that $\forall x (\phi \vee \psi) =\hspace{-.4em}|\models (\phi \vee \forall x \psi)$ if $x \notin free(\phi)$, where $=\hspace{-.4em}|\models$ denotes logically equivalent. I ...
0
votes
2answers
82 views

Why $ M\models \forall x ( \alpha \to \beta)$ Is False? [closed]

if M be a model and $\alpha$ and $ \beta$ be two formula the following is False: $ M \models \forall x ( \alpha \to \beta)$ if and only if $ M \models \forall x \alpha$ has conclusion $ M \models ...
0
votes
0answers
29 views

Let $\Phi = \{Rwt, Rzt, Rwt \wedge Rzt \rightarrow Rxt, y\equiv t\}$. Does $\mathcal{J}^{\Phi} \models Rxy$ hold?

Im working on a mathematical logic question but i'm a little stuck here. The question is the fallowing: Let $\Phi = \{Rwt, Rzt, Rwt \wedge Rzt \rightarrow Rxt, y\equiv t\}$. Does $\mathcal{J}^{\Phi} ...
2
votes
1answer
49 views

How to define “is a structure” by a first-order formula of ZFC

So, I've been trying to define a series of notions by first-order formulas in ZFC, and I'd like to know if I'm getting this right. In particular, I'd like to know if my formula for defining a ...
1
vote
1answer
34 views

How to represent a function that says “send least element to least element and next to next” using a first order formula?

Suppose that $A$ is a finite set. $<_1$ and $<_2$ are two well-orderings on $A$. Suppose that I want to find a formula that repesents the function $F$ that says " send least element in ordering ...
0
votes
1answer
28 views

Let $M,N$ be structures with relation $E$. $E^N$ and $E^M$ are equivalence relations, find sufficient and necessary condition for isomorphism

Let there be signature $S=\{E\}, n_E=2$, and let $M,N$ be S-structures. $E^N$ and $E^M$ are equivalence relations, find a sufficient and necessary condition for $M$ and $N$ being isomorphic. I ...