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

learn more… | top users | synonyms

3
votes
1answer
42 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 ...
-4
votes
0answers
48 views

Will this happen, if this happens? [on hold]

If a monkey takes over the universe, will all monkeys on Earth die? Answer this question, yes, no, or unable to be determined. I believe that the answer to this question can NEVER be determined, ...
3
votes
2answers
113 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 ...
5
votes
9answers
198 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
26 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
25 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
32 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
46 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
92 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
19 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
54 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
69 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
30 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
36 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
79 views

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

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
26 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
46 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
33 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
27 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 ...
0
votes
0answers
32 views

Unsure of Skolemization and Negation Distribution When Converting from FOL to CNF

I am tasked with converting to CNF: ¬[∀x : P(x)] → [∃x : ¬P(x)] There are two main concerns I have in my attempt at this problem: My negation distribution, ...
1
vote
2answers
60 views

Why is the Generalization Axiom considered a Pure Axiom?

If $\varphi$ is a formula in a first order language $\mathcal{L}$ and $x$ is a variable that is not free in $\varphi$, then the following is a pure axiom $$\varphi \to \forall x\varphi$$ The ...
0
votes
2answers
32 views

how can we express finiteness as a first order property?

I don't know much about set theory but I read that in ZFC a set is finite when there are no bijections from the set to a proper subset of itself. It seems to me however that quantifying over subsets ...
0
votes
1answer
23 views

Constructing Logical Derivation

All Texans speak to anyone whom they know intimately. No Texan speaks to anyone who is not a Southerner. Therefore, Texans know only southerners intimately. (We have to use These predicates : $Tx, ...
3
votes
1answer
55 views

Why “Ann believes that Bob assumes that Ann believes that Bob’s assumption is wrong” is paradoxical?

In a paper(see here) by Adam Brandenburger and H. Jerome Keisler, they give a game-theoretic impossibility theorem akin to Russell’s Paradox: Ann believes that Bob assumes that Ann believes that ...
1
vote
1answer
81 views

direct hint to showing a formula is valid?

we know A formula is logically valid (or simply valid) if it is true in every interpretation. These formulas play a role similar to tautologies in propositional logic. which one could direct me to ...
0
votes
1answer
43 views

how we can prove that argument $P_1,P_2,…,P_n $?

I ran into a one claims on LOGIC. how can add more direction or hint to me? if we have an argument $P_1,P_2,...,P_n $ such that $ n>3$ ($p_i$ is premise) why $P_1,P_2,....,P_n,P_1$ is ...
1
vote
2answers
35 views

Maximal consistency proof for set of propositional logic with specific restriction?

I ran into struggle when I comes to one sentence on logic. Why the set of all propositional that under any valuation has value 1 is not maximal consistent ? ...
0
votes
0answers
46 views

Interpretation and truth table is enough to showing validity or a better way?

I'm so glad that find this useful site. anyway, I ran into some challenging ways to find a formula is valid. Here is two example in my note that called valid. I ran into such a problem with making ...
2
votes
1answer
67 views

RAA elimination and inference a theory ?!

Can somebody explain the why if we eliminate RAA rule in natural deduction system on propositional logic, why ~$(p \wedge $~$p)$ is not inference from the ...
0
votes
2answers
38 views

Valid Formula in First Order Logic

I am a little confused about the validity of first order logic formulas. How we can using formal notation to prove the following is VALID? $ \exists x \exists ...
-1
votes
1answer
28 views

how would you convert the following to CNF [closed]

How would you convert the following to CNF? ∃y.(g(y) ∧ ∀z.(r(z) ⇒ f(y,z)))
0
votes
1answer
18 views

Verifying logical equivalence in first order logic

I am given this definition: Let the domain of discourse $D$ be the set of all people and houses, the unary relation symbol $P$ is the set of people, and the unary relation $H$ is the set of ...
4
votes
0answers
33 views

Proving $\square(\forall v_1\neg\psi(v_1))\rightarrow\forall v_1\neg\psi(v_1)$ for a particular $\psi$.

I have a formula $\psi(v_1)$ that is equivalent in $\mathrm{PA}$ to $$\exists a\exists b\exists c\left[\neg\exists ...
1
vote
1answer
54 views

Construct a calculus which produces exactly all pairs $(S,t)$, such that $free(t)=S$.

Construct a calculus which produces exactly all pairs $(S,t)$, such that $free(t)=S$. This calculus will operate on pairs $(S,t)$, where $S$ is a set of variables and t is a term. I've got an ...
4
votes
2answers
226 views
+100

translating one sentence to FOL , an interview question is wrong !?

We ran into an Interview question, writing part 3 days ago. one of the question is as follows: (definition of A(x) and B(x)‌ is not given by OP) what is the logical interpretation of following ...
0
votes
1answer
30 views

logical sybmols and parameters distinction in FOL syntax

In Enderton's Mathematical logic, at the end of page 69, when he defines First-Order language syntax, he categorized its symbols into two groups 1) logical symbols 2) parameters. I understand that ...
0
votes
0answers
15 views

Separate terms of different orders from fractional polynomial

I have an expression: $\frac{1}{1-A}+\frac{-12A^4D^3 + 4A^4D^2 -16A^3D^2+4A^3D -6A^2D - AD}{- 12A^4D^3 + 4A^4D^2+12A^3D^3 -20A^3D^2 +4A^3D +16A^2D^2 -11A^2D +A^2 +7AD -2A + 1}$ How do I write it as ...
4
votes
2answers
62 views

Equivalent categories are elementarily equivalent: Formalization?

Equivalent categories should be elementarily equivalent in the sense of mathematical logic. How to make this precise? Here is an attempt: Let $F : \mathcal{C} \to \mathcal{D}$ be an equivalence of ...
-1
votes
0answers
24 views

Determine the correctness of that formal proof. [duplicate]

1) $a+c<b+c$……………………Hypothesis 2) $\neg(a < b)$..........................Hypothesis 3) $\forall A \forall B[\neg(A<B) ⇒(A=B ∨B<A)]$......Trichotomy law 4) $\neg(a < ...
2
votes
1answer
55 views

Non Archimedean countable models of the theory of the reals

The questions in model theory I am trying to tackle is: Show that there is a countable model of $Th(\langle \mathbb{R};+,.,-,-,1,< \rangle) $ which is non archimedean. Honestly i dont really know ...
0
votes
1answer
51 views

Determining the correctness of a formal proof

Is the following formal proof, proving $\forall A\forall B \forall C[A+C=B+C\Longrightarrow A=B]$ correct?? Proof 1) $a+c=b+c$.............................................................Hypothesis ...
0
votes
1answer
47 views

Logical Structure of a Proposition

I'm having a hard time figuring out the logical structure of the following theorem : I'm not interested in proving it, for now, i'm just trying to understand its logical structure. I don't know ...
1
vote
2answers
69 views

What exactly is necessary for the deduction theorem to hold?

Suppose we have some set of sentences S that we call axioms and a theory T that specifies our rules of inference. Then we write $$S\vdash_TD$$ to mean that the sentence D is deducible from the axioms ...
2
votes
0answers
24 views

When does renaming bound variables require a fresh variable?

Suppose that $E_1$ and $E_2$ are two $\alpha$-equivalent first-order logic formulas (or $\lambda$-terms), and let $V$ be the set of all variables (free and bound) used in $E_1$ or $E_2$. Is it ...
1
vote
3answers
35 views

Proving logical equivalences

The question is to prove $\neg (p \wedge q) \to (p \vee r)$ equivalent to $p \vee r$ So far, I got $¬[¬(p \wedge q)] \vee (p \vee r)$ - implication $(p \wedge q) \vee (p \vee r)$ - ...
0
votes
2answers
90 views

Logical Result about $(\forall y)( \exists x)F(x,y)$? [closed]

I ran into a note that extracted from TA‌ notes on Math. He says that only one of the following is logical result of $(\forall y)( \exists x)F(x,y)$. 1) $(\exists x)(\forall y)F(x,y)$ 2) $(\forall ...
0
votes
1answer
73 views

Skolem functions in the real ordered field.

I am currently reading into a bit of model theory and have come across the idea of Skolem functions, as used in the proof of the downward Lowenheim-Skolem theorem. Despite seeing their use there I ...
0
votes
0answers
64 views

Presburger arithmetic and finite model property

I'm learning about model theory and first order logic. Recently, I read about finite model property and Presburger arithmetic, and I have two questions about them: Does Presburger arithmetic has ...
2
votes
1answer
50 views

What is the idea behind “representability” in a first order theory?

I've been reading through Enderton's logic, this notion is introduced and is given special attention as it's said that they are crucial in the proof of incompletness theorems. I grasp the formal ...
0
votes
1answer
34 views

Substituting two variables in a first order logic formula (free and bounded variables)

When we are trying to substitute $x$ by $y$ in a first order logic formula, No free occurrence of $x$ must be in the scope of $y$ quantifier, because if $x$ was free then by substituting by $y$ and ...