Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
0answers
4 views

Prove $ \vdash \alpha \to \alpha $ in minimal logic of Hilbert

$ \vdash \alpha \to \alpha $ I'm trying to find a way solving this statement using minimal logic of Hilbert which have only two axiom's K & S and one only rule the modus pones (MP) : ...
2
votes
1answer
13 views

Proving a variable true through rules of inference

Question: Use rules of inference to show that if $(p → q) ∧ (q → p),\; t ∨ q,\; t ∨ p,\; (p ∧ q) → t$, then $t$ is true. Work So Far: $$\text{1. }(p \implies q) \land (q \implies p)\text{ | ...
2
votes
1answer
6 views

Boolean Algebra: Converting $xy'z + wxy'z' + wxy + w'x'y'z' + w'x'yz' = w'x'z' + xy'z + wx$

Notation w,x,y,z are all just primary statements "+" is the OR logical operator what looks like two or more statements being multiplied is actually the AND operator The complement or prime ...
0
votes
1answer
23 views

Predicate Logic Question: Implications/Operations on the Empty Set

Suppose T is a set of Natural numbers. C1: $2$ is the only prime number that divides elements of $T$ C2: $T$ is the set of all natural numbers that satisfy the quadratic equation $x^2+x+1=0$. I'm ...
2
votes
2answers
38 views

What is the modus ponens of a tautology?

In the statement $P$ and $Q$, please show that $\; (P \land (P \Rightarrow Q))\Rightarrow Q \;$ is a tauntology. The state the $\;(P \land (P \Rightarrow Q))\Rightarrow Q\;$ in words. I know I need ...
1
vote
2answers
88 views

Prove $x' \neq x$ using Peano axioms

I am looking at Edmund Landau, Foundation of analysis and do not agree with is proof of Theorem 2 part 2. I put the pages here for easy reference (http://pbrd.co/1y89p7b and http://pbrd.co/1y89A2s). ...
0
votes
1answer
18 views

Satisfiability of the resolvent

What would be a way to prove the following statement: S = {$C_1$, $C_2$} and C is the resolvent of $C_1$, $C_2$. By resolvent I mean the result of the resolution operation. The theorem: if S is ...
0
votes
1answer
21 views

Please help with understanding a logic definition: Subformula

Alright, so I am reading "Computability and Logic" by Boolos and Jeffrey, specifically I'm on chapter 9 "A Precis of First-Order Logic: Syntax. There has been more than a handful of definitions in ...
1
vote
3answers
53 views

Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

I was working my way through some Propositional Logic and had the following doubt : Why is this true : ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ ...
3
votes
1answer
32 views

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$?

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$? In "Mathematical Introduction to Logic, Enderton" This is an ...
0
votes
1answer
68 views

In Whitehead & Russell's PM, what makes anything true or false?

It seems that truth and falsehood are fundamental to meanings and types. A proposition is defined as anything that is true or that is false. PM defines truth as "consisting in the fact that there is ...
0
votes
1answer
22 views

$p\to\neg q, q \vdash \neg p$- natural deduction

I have the following proposition: $$p\to\neg q, q\vdash \neg p$$ Using the following formulas on propositions is easy enough: $$\frac{\psi \qquad \psi\to\varphi}{\varphi}\quad \to_e$$ ...
0
votes
1answer
45 views

prove $( \lnot \lnot p \Rightarrow p) \Rightarrow (((p \Rightarrow q ) \Rightarrow p ) \Rightarrow p )$ with intuitionistic natural deduction

I'm trying to prove this statement with intuitionistic natural deduction using inference rules like this example : this is the statement I'm trying to solve : $$( \lnot \lnot p \Rightarrow p) ...
2
votes
1answer
24 views

$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$ - Natural deduction- elimination with $\neg$ operator

I have the following proposition: $$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$$ The only part I have trouble with is the : $$p \to (q\vee\neg r)$$ Clearly the first step is to eliminate $q$ or $\neg ...
2
votes
0answers
52 views

Vague predicates in standard predicate logic [on hold]

I'm trying to work out if a sentence of the form: 'Bob is larger than Maureen and almost as large as Chris' can be adequately formalised in predicate logic. One could just write: ...
2
votes
3answers
46 views

What is the correct form of De Morgan's Law in logic?

According to wikipedia (link), Morgan's Law is: $$¬ (P \wedge Q) \Rightarrow (¬P) \vee (¬Q)$$ But if you scroll down to 8.2.2 on this page (link), it says that Morgan's Law works as follow: $$¬ (P ...
0
votes
1answer
32 views

Prove tautology without truth using a truth table. [duplicate]

I am struggling to prove, without using truth tables, that the statement is a tautology. [(p→q)∧(q→r)]→(p→r) My work so far... ¬[(¬p∨q)∧(¬q∨r)]∨(¬p∨r) ...
-1
votes
0answers
18 views

Prove that Boolean algebra P(S) is isomorphic with the product. [on hold]

Could you help me with this please? From the begining to the end?
-1
votes
0answers
51 views

How to prove if ∀y(∃x(sx = y) ∧ ∃x(sy = x)) is logically valid [on hold]

I first tried to prove whether this statement is logically true or not, by negation and then attempted to substitute. However I can't get a clear answer and am now quite puzzled. Could someone please ...
-1
votes
1answer
28 views

Proof that the formula $((p\to q)\land (q\to r)\land p)\to r$ is a tautology [duplicate]

Write down the assumptions in a form of clauses and give a resolution proof that the formula is a tautology. $((p\to q)\land (q\to r)\land p)\to r$ I got information that i need to use here ...
0
votes
1answer
18 views

Query to get all employees that report to themselves.

I have two predicates: $Employee/1$ and $ReportsTo/2$ and let's say we have two constants: $Patrick/0:$ and $Octo/0:$ The predicate $ReportsTo/2$ takes two Employees, one reports to the other. It ...
0
votes
1answer
35 views

Question about $p \implies q$ predicate logic

$T$: a set of natural numbers. $S_1$: $2$ is the only prime number that divides elements of $T$. $S_2: T = \{16, 8, 528\}.$ I'm trying to figure out which statements imply each other, i.e., does ...
0
votes
0answers
20 views

Truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ : What should my next step be?

I am working on a truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ This is what I have done so far: My next step would be to do the disjunction from the first two ...
1
vote
1answer
47 views

Theory of definitions

I am reading "Introduction to Logic" by P Suppes at the moment. In the Chapter 8 - Theory of definitions of it, I 've some confusion, actually about the Conditional Definition. The brief explanation ...
2
votes
1answer
45 views

Couple of questions from Takeuti's Proof Theory book

I am reading Gaisi Takeuti's Proof Theory (Second Edition, Dover), and I have a couple of questions: I) Right after the first (1.1.) definition, the author says that "In any case it is essential that ...
-1
votes
0answers
36 views

Relations commuting with logical equivalence.

I'm looking for theorems of the form, 'Relation X commutes with logical equivalence', where X is NOT uniform substitution. What's the best place to find such theorems?
0
votes
0answers
33 views

What does it mean? [on hold]

I tried to do this but i dont know what it's exactly mean. Please help me someone i have exam soon!
1
vote
2answers
35 views

Negating the Sentence with 'because'

I have to negate the sentence "They pushed us into a big white room and I began to blink because the light hurt my eyes." My main issue is I'm unsure how the word 'because' can be negated. If P="I ...
2
votes
1answer
36 views

Is the $\varphi \to \varphi$ axiom in Hilbert calculus redundant?

When I see the Hilbert calculus in logic, I sometimes notice that $T \vdash \varphi \to \varphi$ is listed as an axiom and sometimes not. Is there some reason? Could I get it somehow from the other ...
0
votes
2answers
35 views

Negate definition of limit [on hold]

The definition for $\lim \limits_{x\to a} f(x) = L$ is the following: For all real numbers $\varepsilon > 0$, there is a real number $\delta > 0$ such that for all real numbers $x$ if $a−\delta ...
3
votes
1answer
15 views

Find X so that $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is contradiction

I have to find X so that this $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is a contradiction. Then I also have to find out whether or not I can find an X is a tautology. What's the most ...
0
votes
1answer
28 views

how to prove $ B = ( \beta \Rightarrow \gamma) \Rightarrow (\alpha \Rightarrow \beta)\Rightarrow \alpha\Rightarrow \gamma $ using natural deduction

I tried to follow a similar question solving another statement using natural deduction but it still seems hard to understand every time I get a different solution I can't figure out a methodology to ...
2
votes
1answer
43 views

Prove $\forall z\left(\left(\exists xA\rightarrow A_{x}[z]\right)\rightarrow B\right)\vDash B$

I'm doing some self-exercises on mathematical logic by myself and have come across this question which I can't seem to prove: Let $A$ be a formula with a single free variable $x$. Let $B$ be a ...
1
vote
1answer
37 views

Negation of uniform continuity

The definition of uniform continuity is: Given any $\varepsilon>0\ \exists\delta>0\ \forall x\in I \ \forall y\in I\ \left(\text{if }|x-y|<\delta\text{ then }\ ...
0
votes
0answers
20 views

EC,PC elementary class,pseudolementary class,omitting types

What are the typical examples of PC (pseudoelementary class) with and without omitting types, which are not elementary with and without the omitting types, respectively?
0
votes
0answers
19 views

Contrapositive/contradiction of statement with quantifiers

In general how does one formulate a proof by controposition or contradiction for the following general form: $\forall x\exists ! y (P(x)\wedge Q(y) \rightarrow R(x,y))$ Or more specifically: $\forall ...
4
votes
4answers
79 views

Show that $(p \to q) \lor (q \to p)$ is a tautology

i tried to prove that $(p \to q) \lor (q \to p)$ is tautology i used p and not-q as conditions. (Premises 1 and 5) I managed to get to a solution but I'm not sure if it's right. can you please check ...
0
votes
3answers
2 views

Logical Arguments: Why is this Multiple Argument Invalid?

In my understanding, an argument is valid when it is the case that if the premises are true, then the conclusion must be true. I have been given the following argument that if n is both a multiple of ...
0
votes
2answers
36 views

How can i get a tautology truth table from using 3 variables?

I am looking to use the variables p, q and r to create a truth table which concludes to a tautology.
0
votes
1answer
38 views

Proving an “OR” statement

If one wants to proof $P\vee Q$, is it sufficient to proof $\lnot P \rightarrow Q$? Because it makes intuitively more sense to me that $P\vee Q$ would be logically equivalent with $(\lnot P ...
0
votes
0answers
18 views

How do I prove double negation elimination in a propositional logic axiom system?

Here are my axioms: $X \rightarrow (Y \rightarrow X)$ $(X \rightarrow (Y \rightarrow Z)) \rightarrow ((X \rightarrow Y) \rightarrow (X \rightarrow Z))$ $(\lnot Y \rightarrow \lnot X) \rightarrow ...
-1
votes
0answers
32 views

Double Negation in Propositional Logic [on hold]

Given only modus ponens and the following axioms: $$ (@>(\$>@) \\ (@>(\$>\#))>((@>\$)>(@>\#)) \\ (\sim\$>\sim@)>((\sim\$>@)>\$) \\ $$ How do I show $P$ given ...
0
votes
0answers
24 views

Logic - Is it safe to state the following?

say that ∀x∃y in all possible integers (negative integers, 0 and positive integers) is x*y = x is it safe to say that ∃y∀x is also true. If not can someone explain why its not true. The way I'm ...
3
votes
1answer
81 views

How is induction justified in intuitionistic logic?

This question might be extremely naïve for which I apologise in advance. The induction principle can be stated as: If $A ⊂ ℕ$ such that $1 ∈ A$, and $ν(A) ⊂ A$ (where $ν\colon ℕ → ℕ$ is ...
1
vote
1answer
31 views

Computational tree logic satisfiability.

In the model I pasted above where $S_0$ and $S_1$ are starting states, is the $EXp$ formula satisfiable? $$M,s\vDash EXp$$ Does it have to be satisfiable for all the starting states given the $M$, ...
0
votes
3answers
93 views

If $A\rightarrow B$ and $ C \rightarrow B,$ does $(A \land C )\rightarrow B$ [on hold]

If A implies B and C implies B, do A and C together imply B? I need a clarification regarding this question.
0
votes
1answer
31 views

How to transcribe the following statement into a predicate wff?

There was a disagreement in my college class regarding what the following statement would be in a predicate wff format: It is always a sunny day only if it is a rainy day. Where D(x) is "x is a ...
-1
votes
0answers
75 views

What is a Horn Clause? [on hold]

I am not an expert in Mathematics :) thus if someone can let me know What is a Horn Clause in layman's terms? I know it is used in First order Logic but I am unable to understand what is it and how to ...
0
votes
1answer
59 views

A version of Zorn's lemma

The version of Zorn's lemma that I have found more often is Zorn's Lemma (1) If every chain belonging to the partially ordered set $S$ has an upper bound in $S$ then $S$ contains a maximal ...
2
votes
2answers
63 views

Principle of explosion: Other arguments?

I've come across a proof-theoretic argument for explosion on Wikipedia, which is as follows: $A \ \ \wedge\sim A$ $A$ $ \sim A$ $ A \lor B$ $B$ $(A \ \ \wedge \sim A) \implies B$ I've thought of ...