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
0answers
5 views

Henkin-Konstruktion:Goedel completeness THM

I am trying to understand better the Henkin konstruktion, which consist first in an extension of the signature and then of the theory. Here are my question about this topic: -we extend the ...
1
vote
0answers
8 views

Showing that $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$ via generalization theorem

Let $P$ be a unary relation, we want to show that: If $\neg[ Px\rightarrow \forall xPx]\vdash Px$ then $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$. I want to do that via generalization ...
2
votes
2answers
24 views

Propositional Logic Help

I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables). This is what I tried: $\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) ...
0
votes
0answers
14 views

Boolean operation initiation in a Matrix application

Given a function taking input matrix $A$ and $B$. The function only returns True if $A$ and $B$ are both vectors (either coulomb or row vector.) Is the following right? if (numRow(A)!=1 and ...
1
vote
0answers
15 views

Is this theorem equivalent to “existential instantiation” rule?

In Enderton's, There is a theorem called "existential instantiation", it says: Assume that the constant symbol $c$ does not occur in $\alpha ,\beta , \Gamma$ and that: $$ ...
2
votes
1answer
21 views

If $\phi$ is a $\Sigma_2$ sentence and $H_{\kappa} \models \phi$, then $V \models \phi$?

In the title question, $\kappa$ is any infinite cardinal. It's easy to see that the result is true if $\phi$ is $\Delta_0$ or $\Sigma_1$. I first tried proving the result for $\Pi_1$, but I don't see ...
0
votes
1answer
21 views

proof detail concerning bijection between a set and its power set

Theorem: If $X$ is a set, then $X$ is not equivalent to its power set. Proof: suppose for a contradiction that $f:X\to P(X)$ is a bijection. Define $B:=\{x \in X, x\not\in f(x)\}$. Because $f$ is ...
0
votes
0answers
17 views

Do these claims imply each other?

$T$: A set of natural numbers. $C_1: 2$ is the only prime number that divides elements of $T$. $C_2 :$ If $i, j \in T$, and $i < j$, then $i$ divides $j$. For $C_1 \rightarrow C_2$, I think ...
1
vote
0answers
39 views

Prove true in natural numbers (Peano Arithmetic)

While reviewing old exercise sheets, I have found this question and am having difficulties understanding some of the logic: Let $\mathbb{N}$(natural numbers) be a model for Peano Arithmetic, that ...
1
vote
2answers
9 views

Difference between these two statements

$\forall x\in S, \forall z\in S,\exists y\in C, (x\neq z) \Rightarrow ...$ $\forall x\in S, \forall z\in S, \exists y\in C,...$ Why is there a need for $x \ne z$ in 1. Isn't it already implied that ...
0
votes
2answers
28 views

Logical equivalence: Which side is better to start to obtain the other?

How to resolve this with steps please: $$p \to (q \lor r) \equiv (p \to q) \lor (p \to r)$$ I just don't get how with less variable we can have more after or with more we can have less?
1
vote
0answers
18 views

predicate-logic - I think these claims are equivalent, can you verify please?

T is a set of natural numbers. c1: if 2 is the only prime number that divides elements of T. c2: all elements of T are equal to 2^n, where n is a natural number. I'm pretty sure c1 implies c2, ...
0
votes
2answers
19 views

Trouble with a theorem in Hunter's Metalogic

I'm a logician studian and I'm reading Hunter's Metalogic. I'm having trouble understanding and exemplifing part of a theorem in the book. It's the theorem 40.14, pp. 156-7. 40.14. Let t and u be ...
1
vote
2answers
28 views

Find logic expression for given truth table

So I was given this truth table and I need to find a logical expression for the formula to give such a result (where there can be two or three 2-place connective expressions (e.g. $A \lor B$ counts as ...
2
votes
2answers
46 views

When is $\neg(x\le 21\iff x>15)$ true?

Let $x\in\mathbb{R}$. I want to find for which $x$ the statement $$ \neg(x\le 21\iff x>15) $$ holds. I believe it is true when $x\in(-\infty,15)\cup[21,\infty)$, but I don't know how to write ...
1
vote
1answer
37 views

Simplifying Circuits

I have a question regarding simplifying a circuit of a function below that has 5 logic gates in original. f = (A + B) * (C + D) + (A + B) * (C + D)' + C = (A + B) * ((C + D) + (C + D)') + C = (A ...
3
votes
1answer
24 views

Problems in formalizing these sentences

This is the first sentence that I have to formalize: "Every student likes at least one type of cake" Let: $S(x)$ stands for 'x is a student' $C(x)$ stands for 'x is a type of cake' $L(x,y)$ ...
0
votes
2answers
43 views

Weird logic question I need help with!

The professor tells Jim: "It is necessary that you get at least a B on the final in order to pass the course". Jim gets a B. What can she conclude? a) He passed b) He can conclude nothing... I ...
2
votes
1answer
20 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
19 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{ | ...
3
votes
1answer
15 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
32 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 ...
3
votes
2answers
42 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
91 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
19 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
24 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
55 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
34 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
71 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
24 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
25 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
58 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
49 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
33 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
19 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
56 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
41 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 ...
1
vote
0answers
26 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
48 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
35 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
39 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
17 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 ...