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)

1
vote
2answers
84 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
19 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 ...
0
votes
3answers
42 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
62 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
19 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
43 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
22 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
49 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
31 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
49 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
32 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
45 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
35 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
34 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
35 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
33 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
26 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 ...
0
votes
1answer
35 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
19 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
18 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
76 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
2answers
35 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
30 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
92 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 ...
2
votes
2answers
40 views

Logic - Logically implies question

$\forall x(A(x) \rightarrow B(x))$ logically implies $\exists x(A(x) \land B(x))$ Is the above statement true or false? I have no clue on how to start figuring this out. Can someone help me please?
3
votes
2answers
94 views

Logic - how to write $\exists !x$ without the $\exists !$ symbol [duplicate]

What is $\exists !$ equivalent to? I need to write $\exists !x \,P(x)$ without using the $\exists !$ symbol; thus, I am wondering what the $\exists !$ symbol is equivalent to.
3
votes
2answers
32 views

Difference between “necessary” and “necessary but not sufficient”?

This is from Discrete Mathematics and Its Applications: Let $p, q,$ and $r$ be the propositions: $\quad p:$ Grizzly bears have been seen in the area. $\quad q:$ Hiking is safe on the ...
0
votes
1answer
38 views

Question about mathematical logic ∀x ∈ S, ∀z ∈ S, ∃y ∈ C

∀x ∈ S, ∀z ∈ S, ∃y ∈ C,(x != z) ⇒ ¬(T(x, y) ∧ T(z, y)) I'm trying to express this in English, but I can't use the variables x or y in my sentence. Basically it means for elements x in S, and all ...
0
votes
1answer
37 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
1
vote
2answers
46 views

Proving contradiction with logical identities

We know that p → q is not equivalent to q → p. But suppose we make a proof system that has all the rules of logical identities plus the rule (“commutativity of implies”) p → q ≃ q → p. (We are using ...