Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

1
vote
1answer
163 views

Sound and Complete

So I am in a introductory formal logic class, and my professor has asked us questions on our homework about "Sound and Complete rules of inference". Unfortunately, I am having a hard time finding out ...
4
votes
4answers
218 views

Why is my logical statement wrong?

"Express the following sentence symbollically, using only quantifiers for real numbers, logical connectives, the order relation < and the symbol Q having the meaning 'x is rational'" I have to ...
4
votes
1answer
151 views

The method of “Mathematical Induction” as explained in my book.

I am reading the book "A Treatise on Advanced Calculus" by Philip Franklin. I found this book in our city's central library and liked it at the first reading, am continuing this book as a reference. ...
2
votes
5answers
2k views

propositional logic , don't know the answer

Is the assertion "This statement is false" a proposition? I think that it is a proposition because this("This Statement is false") may have truth values. the statement may be true or maybe false. ...
1
vote
1answer
80 views

What is the name of this basic law of logic?

Given any logical formulas $\alpha, \beta, \gamma$. Then: $$ (\alpha \lor \beta) \land (\neg \beta \lor \gamma) \models (\alpha \lor \gamma) $$ Unlike for Modus Ponens and the chain rule, we were ...
1
vote
1answer
126 views

“Measure” of induction for cut-elimination in sequent calculus

I'm not very familiar with proof thoery, so I'm in trouble understanding different versions of the proof of the Cut-elimination Theorem for sequent calculus. In Sara Negri & Jan von Plato, ...
3
votes
2answers
71 views

Logical implication of the form $P\to P$

Two logical propositions are given. $$P:\ good\ books\ are\ not\ cheap\\ Q:\ cheap\ books\ are\ not\ good$$ Now 3 statements are given: $A:\ P \ implies\ Q\\ B:\ Q\ implies\ P\\ C:\ P\ and\ Q\ are\ ...
3
votes
2answers
906 views

How do commas and brackets affect the meaning of quantifiers?

My logic class didn't introduce us to multiple quantifiers. I've seen a few variations that seem to have distinct meanings: $$ \forall x, \forall y(...) $$ $$ \forall x \forall y(...) $$ $$ \left( ...
5
votes
4answers
238 views

What obstacles prevent three-valued logic from being used as a modal logic?

I am familiar with many of the surveys of many valued logic referenced in the SEP article on many valued logic, such as Ackermann, Rescher, Rosser and Turquette, Bolc and Borowic, and Malinowski. It ...
0
votes
2answers
232 views

Some QL Translations

So here I am again... Still stumped, with little progress made. Please help me translate the following sentences to QL. Anyone who knows everyone Alma knows knows Alma Everyone who knows everyone ...
2
votes
1answer
63 views

Difference Between First Order Logic and Conjunctive Queries

What is the difference between First Order Logic and Conjunctive Queries ? Can you for instance give an example of FO query and Conjunctive Query for the following statement? Give the all the ...
2
votes
4answers
135 views

Convincing proofs, proofs by contradiction and countability

Disclaimer: I have a (modest) background in mathematical physics, not logic, so I know very little of the latter. Although when I understood Cantor's argument for the first time (from one of Martin ...
1
vote
1answer
92 views

Translations with more than one quantifier

I've been having trouble translating statements with multiple quantifiers, and I would like some feedback and advice on my answers for the following translations. Let $Kxy$ mean x knowns y. Some know ...
0
votes
1answer
94 views

QL Translation Question

I was attempting to translate the statement "All love all.", and then check if it is a logical truth. I first want to know if my translation is correct. Let $Lxy$ mean x loves y,then $\forall x ...
4
votes
0answers
59 views

Unification in languages without function symbols or with relational terms.

In case a logic formula is mechanically constructed, obtained as the specification of an expression in an imperative programming language for example, the functional constraints could be implicit in ...
6
votes
5answers
865 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
0
votes
1answer
207 views

Countable and Uncountable sets

Is $\mathbb{N}\cup\{a\}$, for some $a\not\in\mathbb{N}$ countable or uncountable? $\mathbf{Attempt: }$ It is true that a set is countable if there exists an injective function $f : S → N$ from $S$ to ...
2
votes
1answer
340 views

Trouble understanding Lindenbaum's lemma's proof

I'm stuck on the section (b) of the proof of the Lindenbaum's lemma in Geoffrey Hunter's Metalogic (part 32.12). Can't these two derivations ($\Gamma ' \vdash_{PS} A $ and $\Gamma ' \vdash _{PS}\sim A ...
1
vote
0answers
1k views

Validity of three syllogisms with venn diagram

me and my study group are struggling with a "how to proof syllogism conclusions" approach. We got three syllogisms which look like the following: We know for a fact that syllogism #1 and #3 are ...
3
votes
2answers
137 views

How to show tautologies in FOL using truth definitions?

Anyone know how to prove these tautologies by way of truth definition? I take it that to solve a), I need to disprove a minimal counter example to the formula/sentence given? If so, how to formally ...
9
votes
3answers
714 views

Gödel's Completeness Theorem and satisfiability of a formula in first-order logic

Gödel's original proof of the Completeness Theorem for first-order logic proves it in the equivalent form : a formula $\varphi$ is satisfiable or $\varphi$ is refutable (i.e.$\vdash \lnot ...
4
votes
1answer
207 views

A couple of Natural Deduction proofs

I have two proofs that I can't figure out how to get started on. a) q ├ (p ∨ ¬p) & q b) p ∨ q, p→¬q Ⱶ (p→q)→(q ∧ ¬p) for q ├ (p ∨ ¬p) & q I only assumed that I might try to prove it ...
1
vote
1answer
51 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
1
vote
2answers
86 views

Restrictive Rules for LK System

I have a question regarding the restrictive nature of $\forall(R)$ and $\exists(L)$ rules in sequent calculus LK. I don't really understand why the restrictions exists in the first place, so why: $$ ...
1
vote
3answers
129 views

Finding equivalent formulas

The question I have on my homework is "Find a formula that contains no connective other than ¬ and v which is equivalent to ((p→q)→s)." I drew out the truth table for the given formula but have no ...
0
votes
1answer
96 views

the sum of two odd integers is even

How do I represent this statement using symbolic notation? This is my attempt at it. $$ \forall n \in \Bbb{Z}, \forall m \in \Bbb{Z}, (n = 2q + 1) \wedge (m = 2k + 1) \Longrightarrow (m + n = 2l) $$ ...
1
vote
1answer
35 views

Direct proof that $K \leq_\mathrm{T} Rec$

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ ...
1
vote
1answer
248 views

Use mathematical induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n+1) from F (n)is well defined.

Im just not sure what the question is asking me to prove, or how to prove it with induction.
12
votes
3answers
321 views

What do we call entities (like $\sum$) that bind variables?

In logic, we refer to entities like $\forall$ and $\exists$ as quantifiers, because they bind variables. However, variable-binding doesn't just occur at quantifiers. For example, the symbol $i$ ...
2
votes
1answer
140 views

Consequences of difference between “strong” and weak Church-Rosser property

An Abstract rewriting system is a set A, whose elements are usually called objects, together with a binary relation on A, traditionally denoted by $\rightarrow$. An object $x \in A$ is ...
2
votes
2answers
76 views

Resolution Proof Question

Given the implication $[(p\vee (q\wedge r) \wedge (p\to s)] \to (r\vee s)$, establish the validity of the argument using resolution. This is the answer my textbook gave: ...
1
vote
3answers
142 views

Show that “$\Gamma \models S \Rightarrow \Gamma \vdash S$” entails “if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable”

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable" I'm primarily confused with the notation being used here. In ...
0
votes
1answer
54 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
1
vote
1answer
77 views

semantic equivalence

Hi I am looking to prove that this equivalence holds using rules of semantic equivalence, or if it does not hold give an interpretation that shows it. (p⇒q)∨(r⇒q)≡p⇒(r⇒q) I get ≡implication ...
-2
votes
1answer
157 views

Every Countable Model of PA is Recursive?

I am interested in any obvious flaws in the following argument. Assume we have a countable model of Peano arithmetic in a meta-theory like ZFC. Assume this model has a set of ordered triplets, ...
1
vote
1answer
305 views

formal proof with natural deduction

Hi I am looking to prove $r\wedge q\Leftrightarrow r \vdash r\Rightarrow q$ using natural deduction I get: $r\wedge q\Leftrightarrow r$, assumption $r\vdash q$ $r$, assumption I assume that I ...
0
votes
1answer
92 views

Natural Deduction: Epsilon Rule and Its Application

I interpret the first example as, if you have a formula that belongs to all formulas in this language, then it is deductible from any formula in this language. I think my explaining might be wrong or ...
1
vote
2answers
95 views

prove formulae using natural deduction

Hello I am trying to prove this: ⊢p⇒p∧(p∨q) using natural deduction. p ⊢ p∧(p∨q) p, assumption p ⊢ (p∨q) p, assumption but dont seem to be getting anywhere. can someone please help? thank you. ...
2
votes
1answer
77 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
0
votes
1answer
77 views

Simple first order logic satisfy for every formula

I'm studing logic as autodidact and i stucking on this sentence : show that : if for every model $M$, $M \vDash \lnot \Phi$ then, for every $\Phi$, $\Phi \vDash \Psi$. What is the correct way for ...
0
votes
3answers
70 views

How did I solve this problem?

While writing a SQL query I had to solve a problem I'd never dealt with before. It was trivial, but I cannot explain the solution without drawing lines on paper or making examples with actual numbers ...
0
votes
1answer
40 views

peano axioms coherence

Can anyone help me to solve this problem : if every formula Φ that is provable in PA is such that N |= Φ then PA is consistent. What is the basic idea in this problem? Thank you Miguel
-2
votes
6answers
408 views

how do i know how many columns to put in a truth table

Oh man i am in so much trouble! I am in school for my RN and am taking all my classes online. I suck at math to begin with, and then trying to teach myself? = Trouble current problems are truth ...
0
votes
1answer
42 views

Reformulation of Theories

Philosophical questions (or even just a matter of taste) regarding some mathematical constructions can give rise to reformulations of whole theories, for example, we can develop (Non-standard) ...
1
vote
1answer
184 views

Prove $\forall x~\forall y~\forall z (x+y)+z=x+(y+z), \forall x~\forall~y\exists z~ x=y+z, \forall x~\forall z \exists y x=y+z ⊢ ∃y∀x x+y=x$

I need help using the standard rules of predicate logic with quantifiers to prove $~\forall x~\forall y~\forall z ~~(x+y)+z=x+(y+z), ~\forall x~\forall y~\exists z ~~x=y+z, ~\forall x~\forall z~ ...
3
votes
3answers
1k views

Online lectures for a first course in mathematical logic

I have a friend who is interested in learning math. I suggested that he learns mathematical logic. He has never learnt mathematical logic before, however I believe he has all the necessary ...
-1
votes
1answer
75 views

First order Logic find Model example

Can anyone help my to find a model for this first order logic sentence? 1) dog doesn't bite dog 2) alf bites brick 3) brick bites alf $\therefore$ 4) alf isn't a dog now i have to negate the 4) ...
2
votes
1answer
328 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...
3
votes
1answer
115 views

A problem about sequent calculus for classical logic

In Sara Negri & Jan von Plato, Structural Proof Theory (2001), page 51, various properties of the system G3cp of classical propositional logic are showed. Theorem 3.1.1 [page 49] proves that all ...
3
votes
1answer
201 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...