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

learn more… | top users | synonyms

0
votes
0answers
15 views

$P \Rightarrow Q$ and Skolem Functions [on hold]

We know if $P \Rightarrow Q$ (it means be true), Predicate Q is Weaker than P. which of the following is Weaker? F1 is a Skolem Function, and F2 is a Skolem constant. 1) $\exists y \forall x ...
1
vote
1answer
29 views

Finding Interpretations for First Order Logic

I'm currently looking at first order logic and I'm having a difficult time with the following question: Now I don't want answer cause that wont really help me. What I am looking for is help, with ...
1
vote
2answers
13 views

Gradient decent using Taylor Series

I'm reading a book about Gradient methods right now, where the author is using a Taylor series to explain/derive an equation. $$ \mathbf x_a = \mathbf x - \alpha \mathbf{ \nabla f } (\mathbf x ) $$ ...
-2
votes
0answers
23 views

use logical way to calculate the least percentage [on hold]

If 70 per cent. have lost an eye, 75 per cent. an ear, 80 per cent. an arm, 85 per cent. a leg q1: what is the least percentage lost all four q2: what is the least percentage lost one of them q3 what ...
0
votes
0answers
40 views

question concerning a proof that the class of infinite structures is EC

I first sketch out the proof and then point out what bothers me: Let there be given some first-order language (which might or might not contain the twisty symbol "="). Per definitionem, a class of ...
-2
votes
1answer
63 views

Inference in First Order Logic Problem [closed]

I read one logic note by Michle Sipser from MUT. I get stuck in inference. please help me in step by step inference? By using First order logic and Resolution Rules, and Proof by contradiction from ...
2
votes
1answer
33 views

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 ...
0
votes
1answer
22 views

FO-axiomatizable class?

I came across this question while preparing for my logic exam. Can this class be (finitely) axiomatizable, where the class contains all structures $\mathfrak{A} = (A, <, f)$, and for no $a \in A$ ...
0
votes
0answers
21 views

Connection between quantifier rank and Ehrenfeucht-Fraïssé Games

"Two $\tau$-structures $\mathfrak{A}, \mathfrak{B}$ are $m$-equivalent ($\mathfrak{A} \equiv_{m} \mathfrak{B}$) when... $\mathfrak{A} \models \psi$ iff $\mathfrak{B} \models \psi $ for all ...
0
votes
2answers
28 views

Use propositional logic to solve

Argue that (∀x(P(x) ∨ ∃y P(y))) is equivalent to ∃x P(x) Can anyone please explain how to do it?
3
votes
2answers
69 views

Proving $\vdash \exists x (x=c)$ for each term $c$.

I wish to prove that $\vdash \exists x (x=c)$ for each term $c$. It seems quite obvious that this would be the case, for $c$ is such an $x$, but creating a formal proof of this is escaping me. ...
0
votes
1answer
31 views

Readings on more general/abstract notions of induction related to logic

Can someone suggest references to understand the more general/abstract concept of induction? Specifically, I am trying to justify to myself what is called induction on the "complexity of a ...
2
votes
1answer
28 views

satisfiability in a structure implies satisfiability in a substructure?

My level: I've studied mathematics and now work through Hebert Enderton's book "An introduction to mathematical logic", second edition, in my free time. Relevant pages: 135-142, specifically 140 ...
1
vote
1answer
98 views

Please help with translation of English to first order logic

In a certain work on mereology, Alfred Tarski claims that the third following statement is deducible from the previous two: The sum of a class is defined as follows: $y$ is the sum of a class ...
1
vote
2answers
28 views

Axiomatizability of finite Isomorphic Classes

If $\mathfrak{A}$ is a finite $\tau$-structure and $\tau$ is a finite signature, is the isomorphic class $K_{\mathfrak{A}} = \{\mathfrak{B} \, | \, \mathfrak{A} \cong \mathfrak{B} \}$ ...
2
votes
1answer
44 views

Finite sets defined by First Order Logic

Why is a class of, say, finite groups $(G,\circ,e)$ not axiomatizable by FO logic (we use the compactness theorem to prove this statement) but a finite linear order $(A,<)$ on the other hand can be ...
-2
votes
0answers
94 views

Absoluteness of $\forall x (x=x)$

Is there any kind of (set-theoretic) absoluteness result for the formula $\forall x (x=x)$? And what about for $\exists x (x=x)$? I know $x=x$ is absolute given that it's $\Delta_0$. Also, if I'm ...
0
votes
1answer
56 views

Proving that 0 * x = 0 using only first order logic

I cannot prove that 0 * x = 0 using only first order logic and a minimum set of axioms (preferably from ZFC). Are there any axioms to look at on the world wide web? ...
2
votes
2answers
89 views

ZFC and apples described using only fundamental axioms (complete expanded reasoning)

Let's assume that I'm adding two numbers representing my count of objects I perceive (lets say a green and a blue apple that are consider to be of the same class) and I see them as a set of two apples ...
1
vote
2answers
37 views

Proof that there exist no finite axiomatic system with Compactness Theorem

Say we would like to prove that the class of all infinite groups $(G, \circ, e)$ is not finite axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we ...
0
votes
0answers
17 views

Analogue of Herbrand Disjunction for Negative Side of the Clark Completion?

For Horn clauses there is the following result. If T is a set of Horn clauses and p is a predicate, and if p is an existential consequence of T: ...
2
votes
1answer
40 views

Doubt on recursive definition of a term in a first order language, $\mathscr L$

In his definition of a first order language $\mathscr L$ in "A Friendly Introduction to Mathematical Logic by Leary", the author says a term in $\mathscr L$ is a non-empty, $\underline ...
0
votes
0answers
31 views

Doubts: Proof of Deduction Theorem

I am reading Robert Wolf's A Tour Through Mathematical Logic and am enjoying it. But the author omits proofs for the Deduction and Generalization Theorems. I looked through Intermediate Logic by ...
1
vote
0answers
24 views

Tautologies with quanitfiers added

What is the class of formulas that are propositional tautologies with quantifiers added called? For example, something like: $$ \exists x((x=0) \vee \neg (x=0)) \qquad\text{or}\qquad \forall x \exists ...
0
votes
2answers
98 views

Is the formula $ \forall x (A(x) \to B(x)) \to ( \exists x A(X) \vee \exists x B(X)) $ logically valid [closed]

Recently I studing on logic. I try to solve some first order formula that not valid. Why the following first order formula is not logically valid? every expert would please help me? 1- $ \forall x ...
-1
votes
1answer
64 views

Undecidability of First Order Logic [closed]

friends! I read in Ebraham's Outline of Logic that first order logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. It is undecidable ...
0
votes
1answer
34 views

What does it mean for a model to have 'the less cardinal possible'?.

I've encountered this question, and I'm not sure if my interpretation is right because if it is, seems like there would be very trivial models (and there would no problem at all). Ex 1: $\{\forall x ...
1
vote
0answers
56 views

Are there axiomatizations of first order logic or set theory defined in first order logic or set theory?

There are several axiomatizations for number theory, group theory, and other theories represented in first order logic. Further, these theories are also representable in set theory such as $\sf ZFC$ ...
1
vote
1answer
43 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
3
votes
1answer
33 views

Two-place position predicate problem

I see this sentence in one Logic Note Tutorial. What arguments are involved in any situation is determined by the meaning of the predicate. Sleeping can only involve one argument, whereas placing ...
-2
votes
1answer
51 views

Logic Substitution Problem

I see this formula on Logic Text Book, I take a picture and insert it here in order to one expert help me and correct the error. t is a term and $\varphi$ is a formula. I think one of ...
1
vote
1answer
94 views

question about Herbert B. Enderton's book : A mathematical introduction to logic

I hope someone can help me. My question arises on page 114 of the second edition of the book. Here the notion of 'prime formula' is introduced to enable one to view a formula as a formula of ...
1
vote
0answers
42 views

Is “autonym” an autonym?

I believe this is set theory, but I don't really know set theory, so... An autonym is a word that refers to a property that the word itself happens to possess. For example "noun" is an autonym ...
3
votes
1answer
91 views

What would provable existence of a non-standard natural number imply about ZFC?

Assume that in ZFC we can define a set $x$ in some way and that the following are provable: $x$ is a finite ordinal, (i.e. $x\in\omega$) $x\neq0$ $x\neq1$ $x\neq2$ etc. So to say that the ...
0
votes
2answers
72 views

Logic Inference Challenge [closed]

I read some logic course recently, would you please anyone say my inference is True? $\forall x S(x) \to \exists y(R(y)) \Rightarrow \forall x \exists y(S(x) \to R(y))$.
0
votes
1answer
35 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha$

prove {$\neg(\forall x)\alpha \rightarrow \alpha$}$\vdash\space(\forall x)\alpha$ Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ...
-4
votes
1answer
157 views

Primitive Recursive Predicate Problem [closed]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
2
votes
1answer
20 views

find a sentence $\alpha$ in some language L such that

Let $K=\{k\in\mathbb N : k\mod2\not=0$ and $k\mod3\not=0\}$ find a sentence $\alpha$ in some language L such that $K=${$n\in\mathbb N :$exists a structure $M$ such that $M\models\alpha$ and ...
0
votes
1answer
33 views

A simple, yet non-superficial explanation of what “paramodulation” means in the context of automated theorem proving?

Modern automated theorem provers seem to be paramodulation-based. I only have a superficial understanding of what this means: we derive a proposition whose truth is implied from the truth of [two?] ...
1
vote
1answer
74 views

Big Questions in First Order Logic

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic, the set of logical result of $\Sigma$ is Recursively Axiomatizable. why this is false? or maybe it's true? ...
-1
votes
1answer
47 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
3
votes
1answer
31 views

Expressing infinite elements each equivalence class in First Order logic

I was going through some FO-logic ideas for my logic exam revision and came across some problems... Equivalence relations can be expressed in FO-logic by the set of axioms: $\{\forall x Rxx, \forall ...
0
votes
1answer
50 views

sentence in predicate logic

“If all politicians are showmen and no showman is sincere then some politicians are insincere.” Ans: F:= $(\forall x\,(P(x) \to ShMan(x)) \land \not \exists y\,( ShMan(y) \to Sinc(y))) \to \exists ...
2
votes
1answer
86 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
2answers
106 views

How is the law of excluded middle necessary for proofs by contradiction?

It is claimed that the law of excluded middle : $A \lor \neg A$, is a necessary principle for proving statements by contradiction (i.e. non constructively). However, in first order logic, at least, ...
0
votes
1answer
61 views

Existential introduction - required or not?

Consider a theory $T$ in first order logic, and a formula $C$. If there exist a proof of $C$, and that all formulas in $T$ and $C$, none of them contains $\exists$. The question is: does there always ...
0
votes
2answers
78 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
123 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
1
vote
2answers
46 views

implication versus conjunction correctness in FOL?

I've just started learning FOL and I'm really confused about whether to use conjunction or implications. For example, if I want to represent ...
1
vote
1answer
70 views

Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$

We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...