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

How to work with a statement: “for all $x$, if $p(x)$ then $q(x)$” (contradiction and contraposition)

Proving by contradiction and contrapositive a statement of the sort "for all $x$, if $p(x)$ then $q(x)$" Question about the notation: is it equivalent to $\forall x (p(x)\to q(x))$ or $(\forall x ...
0
votes
2answers
19 views

Propositional Logic Tautology Proof

I have question about a proposition that I need to prove is a tautology: $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ I have tried negating the first large bracket, ...
2
votes
1answer
34 views

Is $\lor$ definable in intuitionistic logic?

The Wikipedia page mentions that $\{\lor,\leftrightarrow,\bot\}$ and $\{\lor,\leftrightarrow,\neg\}$ are complete sets of operators for intuitionistic logic, and also gives a few equivalences for ...
1
vote
2answers
16 views

If there exist integers m and n such that am + bn =1 and c≠± 1, then c does not divide a or c does not divide b

Prove that for all integers a, b, and c. If there exist integers m and n such that am + bn =1 and c cannot be equal to 1 or negative 1, then c does not divide a or c does not divide b. This is the ...
0
votes
1answer
11 views

How to prove that $\Gamma\vdash\forall x\psi$ if $x$ occurs free in $\Gamma$, via generalization theorem?

In Enderton's logic [page $120$], he says: Assume we wish to prove $\Gamma\vdash\phi.$ where $\phi$ is $\forall x\psi$. If $x$ does not occur free in $\Gamma$, then it will suffice to show ...
0
votes
1answer
18 views

Distinguish between substructure, submodel, elementary substructure, and elementary submodel.

I can see (although I must not really understand) the definition of these terms, but could someone please explain the difference between these concepts, and whether any one of them imply the other? ...
1
vote
1answer
25 views

Proof of ⊢ (∀xA → ∃xB) → ∃x(A → B) [on hold]

Can somebody give me the proof of ⊢ (∀xA → ∃xB) → ∃x(A → B) using sequent calculus in classical logic.
2
votes
1answer
56 views

How do I prove these biconditional statements?

I keep getting stuck when I get to (not p or q) and (p or not q) for number 3 and for number 4 I get stuck in relatively the same place. Edit: I want to prove them with using equivalence laws, not ...
5
votes
0answers
32 views

Proving that ∼(∃x) P (x), is false is equivalent to proving that (∀x )∼P (x) is true.

I found this phrase in the page 60 of the book "A Transition to Advanced Mathematics, 8th Edition, written by Smith/Eggen/St. Andre." "Proving that ∼(∃x) P (x), is false is equivalent to proving that ...
0
votes
1answer
26 views

How to calculate the cardinality of a model

I know, thanks to some clarifications received from a user of this site, the definition of a model. When evaluating the cardinality of a model by taking the interpretations of all the constants, ...
0
votes
1answer
20 views

Having some trouble understanding a question about Set Theory

I'm working on some HW and having some trouble understanding what the question is asking. The questions is as follows: ...
2
votes
1answer
34 views

How to show validity in classical logic?

Firstly, I would like to know what does it mean to be a valid expression in classical logic. Secondly, How do we show validity of a formula (in sequent calculus) such as: (∀x A → ∃xB) → ∃x(A → B) As ...
2
votes
1answer
49 views

What is finite in a finite model

I am studying some theorems of model theory in an introductory text of mathematical logic. I know that a model is a way of associating the relationary symbols of a signature $\Sigma$ to $k$-ary ...
1
vote
0answers
30 views

Difference between Hilbert program and Russel & Whitehead's Principia Mathematica

May some one explain me what is difference between Hilbert program and Russel & Whitehead's Principia Mathematica? I know both of them wanted to reduce the mathematics into a set of axioms and ...
4
votes
2answers
51 views

No proposition $\chi$ such that $\mathscr{M}\models\chi\iff\mathscr{M}$ is infinite

Let notation "$\models$" be used for the two following case: let $\mathscr{M}\models\varphi$, where $\mathscr{M}$ is an interpretation model and $\varphi$ is a proposition, mean that $\varphi$ holds ...
1
vote
0answers
31 views

Henkin Construction: Goedel completeness Theorem

I am trying to understand better the Henkin construction, 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
2answers
24 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 ...
4
votes
2answers
37 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)) ...
1
vote
1answer
17 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
2answers
31 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
29 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
23 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
19 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
1answer
48 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 ...
2
votes
2answers
13 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
31 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
19 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
23 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
30 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 ...
3
votes
2answers
51 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
40 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
26 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
46 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
26 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
16 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
44 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
93 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
20 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
56 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
26 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
47 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
26 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
60 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
34 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) ...