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
16 views

Computability of certain functions

Suppose we are working in the first-order language with equality with one relation symbol R. And suppose I have a closed formula P that describes a property R may or may not have. We can define a ...
0
votes
1answer
18 views

How to formulate this logic formula

The problem setting is very simple. Suppose we have three variables x, y and z and a constraints C/3 predicate that is satisfied by the three variables C(x,y,z), but C/3 might not be the only ...
5
votes
1answer
38 views

Why isn't there a first-order theory of well order?

Problem 1.4.1 of Model Theory by Chang and Keisler asks, Is there a theory of well order in the first-order language $\{\leq\}$? I'm pretty sure the answer is no, since well order is a property ...
-1
votes
0answers
12 views

Prove that, any formula occurring anywhere in another formula is a subformula. [on hold]

What could be the formal way of proving this definition for subformulas?
0
votes
0answers
19 views

First order logic, equivalence of queries to a database

My book says II should be equivalent to Select R.a,R.b from R,S where R.c=S.c I tried using this page http://en.wikipedia.org/wiki/First-order_logic I got this far. I understand II says for every ...
0
votes
1answer
17 views

First order logic formula for complete graph with no self loops

I wanted to translate a party scenario where everyone shakes hands with everyone else into a first order logic statement. Since no one can shake hands with themselves, there can be no self loops. I ...
0
votes
1answer
18 views

interpret first-order formula

To the following formula. As I can give structure to be true? R(x) $\longleftrightarrow $ $\forall{x}$ ¬R(x) I tried to break it down but still can not understand how I can interpret this formula ...
2
votes
0answers
15 views

Is it known if 'most' first order statements are decidable or undecidable?

If we enumerate the statements we can prove as decidable with proof or negation and enumerate the statements we can prove as undecidable, with satisfiability, forcing, or an incompleteness proof, is ...
0
votes
1answer
52 views

first-order logic

How I can make the following sentences in first order logic as a set of Horn ?. "The Martians are not informatics appreciate anything more than a computer." "The Martians informatics appreciate ...
0
votes
1answer
50 views

What is really a “complete” deductive system for first-order theories.

Given some first-order language and a set of axioms therefrom one still needs to specify a deductive system to turn it into a full-fledged first-order theory. Currently I'm under the following ...
1
vote
0answers
55 views

Is a sentence in $\Pi_1$ true given $Q \vdash \lnot\varphi$?

If $Q \vdash \lnot\varphi$ (Q is the Robinson arithmetic), and if I assume that $\varphi \in \Pi_1$; Can I say that $\varphi$ is a true sentence? My thoughts are that, given that Q is $\Sigma_1$- ...
4
votes
3answers
96 views

quantification domain of set theory formulas

Let ZFC set theory, what is the domain of quantification of a formula like $\forall x\phi(x)$? If the domain is the whole Von Neumann Hierarchy $V$ why it is not a problem that it doesn't form a set?
1
vote
3answers
84 views

Defining finite unions of intervals with algebraic endpoints on the reals

I'm currently working a bit on Enderton's logic textbook (2nd ed), and, on the second chapter, he marks the following exercise on definability with an asterisk. Let $(\mathbb{R}; +, \cdot)$ be the ...
3
votes
1answer
145 views

Problems with nesting proof predicates in first order logic.

Whenever I start nesting proof predicates, I always seems to run into these bizarre situations. I was wondering if anyone knows about this and could shed some light on it or provide me with some ...
0
votes
2answers
147 views

Can the logical equivalence of two different statements to the same proposition imply that the three of them are false?

Let$\ P_0 $be our original proposition and$\ P_1 :a<b $ and$\ P_2:a<c $ the statements that are equivalent to$\ P_0 $. Now, if it is known that$\ b<c $, then there is an interval of values ...
1
vote
2answers
26 views

Negation distribution

I just have a quick question on how negation distributes to universal quantifiers and predicted in first order logic. As show below: $$ \neg(\neg\forall x \neg p(x)$$ Does this become: $$ \forall x ...
2
votes
2answers
56 views

First order Language Universal Quantifier Distribution

I've got a quick question about Universal Quantifiers. Given the following: $$ \forall x (p(x) \vee q(x)) $$ Can we do this: $$ \forall xp(x) \vee \forall xq(x) $$. i.e can we distribute the "for ...
2
votes
1answer
38 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
15 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 ) $$ ...
0
votes
0answers
45 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
67 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
36 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
30 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
70 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
33 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
29 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
99 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
47 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 ...
0
votes
1answer
57 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
90 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
38 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
44 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
32 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 ...
0
votes
2answers
100 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
67 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
58 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
45 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
34 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
99 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
75 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
160 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) ...