2
votes
1answer
49 views

Proof negation in Gentzen system

I am provided with the L¬ and R¬ Gentzen rules for negation (besides “Cut” rule and some rules for ⋀ and →): $${\Gamma\vdash\Delta,\varphi\over \Gamma,\lnot\varphi\vdash \Delta}\ L\lnot \\[4ex] ...
1
vote
2answers
67 views

Show there are a pair of sentences where the first says the second is provable and the second says the first is unprovable

Given $B_1(y)$ and $B_2(y)$ in the language of arithmetic, show there are sentences $G_1$ and $G_2$ such that: $$\vdash_Q G_1 \leftrightarrow B_2(\ulcorner G_2 \urcorner)$$ $$\vdash_Q G_2 ...
0
votes
3answers
66 views

Giving Proof by counterexample

I just started learning college mathematics and one of the things I don't like is giving proofs by counterexamples. My question is how is disproving by giving counterexample is seen by advanced ...
4
votes
2answers
84 views

$2 \uparrow^n 2 = 4$ and the magnificence of $2$

I was reading up on tetration when I realized: $$2 \uparrow\uparrow 2 = 2\uparrow 2 = 2 \times 2 = 2+2 =4$$ Infact, when generally speaking: $$ 2 \uparrow^n 2 =4$$ Now, I realize that this is because ...
3
votes
0answers
68 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
0
votes
1answer
45 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
2
votes
0answers
25 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
0
votes
2answers
66 views

For all x there exists a y such that x+y=0

I know this statement is true but I am having trouble actually proving it. I know that if x=5 then y=-5. How can you prove that properly.
2
votes
2answers
61 views

Restate a logical claim using logical symbols

Proposition: Strictly between any two distinct rational numbers lies another rational number. How may I present this statement using logical symbols? My answer: $\forall x, y \in {\mathbb{Q}}. ...
2
votes
6answers
187 views

$(P\implies Q) \implies [(R ∨ P)\implies (R ∨ Q)]$ is a tautology

I'm currently trying to work on the proof for this tautology. But every time I derive the right side, I end up with a lone $R$ that will never cancel out. Like I always end up with $$(P\implies Q) ...
1
vote
1answer
34 views

On provability within minimal logic

In its most naive form my question boils down to this: when is a proposition that is provable "by contradiction" also provable "directly"? IOW, is it possible to know, a priori, that a ...
0
votes
3answers
130 views

Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...
1
vote
1answer
35 views

Negate Implication Written as a Sentence without “If …, Then …” [Chartrand P246]

P246 Theorem 10.4: Every infinite subset of a denumerable set is denumerable. P252 Theorem 10.10: Let $A \subseteq B$ be sets. If $A$ is uncountable, then $B$ is uncountable. I'm aware how ...
0
votes
1answer
47 views

Prove by Hilbert deduction: ⊢∃x(AvB)→(∃xAv∃xB); ⊢(∃xAv∃xB)→∃x(AvB)

I'd really like your help proving: 1)⊢∃x(AvB)→(∃xAv∃xB) 2)⊢(∃xAv∃xB)→∃x(AvB) Our proof system contains next Hilbert's axioms: 1.A→(B→A) 2.(A→B)→((A→(B→X))→(A→X)) 3.(A&B)→A 4.(A&B)→B ...
3
votes
3answers
148 views

Premise vs. Assumption

I have just asked about the difference between A,B and A∧B in A,B ⊢ M However, I have ...
0
votes
1answer
28 views

Defining substitution by structural recursion

For a term u, let $u{x\atop t}$ be the expression obtained from $u$ by replacing the variable $x$ by the term $t$. Define $u{x\atop t}$ by recursion on $u$. Not really sure how to start this one. ...
1
vote
3answers
108 views

How do I derive $(\forall x)(\forall y)(\exists z)(x = y \circ z)$ from these three group axioms and some previously established theorems?

I am currently self-studying Patrick Suppes' Introduction to Logic and I am stuck on exercise 5.2.4. I've successfully worked out proofs for Theorems 1 to 7, but I am having trouble coming up with a ...
0
votes
1answer
60 views

Is there a rule to justify the following logical statement?

I have to derive the following expression and reach the second one: $$\begin{gather} ( ( \forall x , Q \Rightarrow \neg P (x) ) \wedge ( \forall x, \neg Q \Rightarrow \neg P(x) ) ) \\ \iff \\ ( ...
0
votes
1answer
59 views

Models and their meaning in a proof of any formula

Behind the scenes all formula $\phi$, we must define a model, M = (F, P) over a Universe, where F = set of Functions and P = set of Predicates, on a table of free variables in $\phi$ ? Ie any $\phi$ ...
0
votes
1answer
41 views

prove two different forms of the same uniqueness theorem are logically equivalent

One may take either of the statements below as a definition of $(\exists!x)(P_x)$, where $P_x$ is a predicate concerning the set $x$. Prove that they are logically equivalent. $$ (\exists x)(P_x) ...
1
vote
2answers
90 views

How can you really be sure the contradiction didn't spring from the hypothesis?

This question may have a duplicate but I didn't find one. Given a proof by contradiction of a statement like $p \land q \implies r$. Which means (as i understand it): $p \land q \land \lnot r$ is ...
0
votes
0answers
54 views

How to prove a statement that involves max and big theta?

If we have 4 functions. a,b,c,d Considering that a is in Θ(c) and b is in Θ(d) I need to prove that (a + b) is in Θ(max{c, d }). What approach do you recommend? Do I have to prove this ...
3
votes
1answer
101 views

Type Theory (Proof tree)

Suppose $B(x)$ set $(x:A)$ is a family of sets and $D$ is a set. Prove $(\Sigma x:A)B(x) \times D \to (\Sigma x:A)(B(x) \times D)$. Using the so called Curry-Howard correspondence one may ...
2
votes
1answer
68 views

Generalized distributive laws proof feedback

I'm currently learning proofs and elementary set theory. I would like to have feedback on my proof since I'm self-studying. Are some part superfluous or unclear? My proof goes as follows: I will ...
1
vote
1answer
45 views

Prove or refute: $A_1,\ldots,A_n\vdash_{CPL} B \iff (A_1 \wedge \ldots \wedge A_n)\vdash_{CPL} B$

Need to prove or refute: $A_1, \ldots, A_n \vdash_{\rm CPL} B \iff A_1 \land\dots\land A_n \vdash_{\rm CPL} B$ Since we have $\iff$ operator, we have to deal with to directions. Let's begin from ...
2
votes
2answers
54 views

Prove or refute contingent: If A implies B is contingent, then B is too

The question is: If $A, A \to B$ are contingent, then so is $B$ $A, A \to B$ (implies) is a contingent, but how exactly to show «so is $B$»? If I'm using a truth table, how should I show that ...
0
votes
1answer
59 views

Does $(\neg R\to R)\to R$ give rise to a proof strategy?

Take for example proof by contradiction, it can be viewed as a certain deduction in logic which can be used outside of logic to prove many interesting propositions. My question is: can we use $(\neg ...
2
votes
1answer
45 views

What's the symbolic definition of the maximum value of a domain?

Lets say we have a domain S Maximum value of domain S = {S | ? ? ? ? ? ? } How could one define the possible maximum value of a set of values, symbolically?
0
votes
2answers
53 views

Question Regarding Logical Contradiction

Let's say I attempted to solve a logical statement in the form using contradiction: $\forall x \in \Bbb R, (P \implies Q)$ Negated: $\exists x \in \Bbb R, (P \land \lnot$ Q). Initially I did not ...
0
votes
1answer
30 views

Contrapositive clarification

Let's say I have this statement: ∀ real numbers x, if −x is not irrational, then x is not irrational. Which one of the following statements is equivalent to this? [because −(−x) = x], 1.∀ real ...
0
votes
1answer
104 views

Logical representation of a prime number

Is it correct to represent a prime number like this? $$\exists k \in \mathbb N,\, \exists n\in \mathbb N\, \Big((n\mid k) \land (n=k \lor n=1)\Big)$$
-2
votes
3answers
62 views

How to prove this? Mathematical Logic proofs. [duplicate]

I need to prove that If n>2 is a prime, then n is odd. I tried to prove its contrapositive... Which is that, if n is even, then n>2 is not a prime... but failed miserably. Any advice? Edit: Is ...
1
vote
0answers
55 views

Induction in the caculus of terms - Mathematical Logic

I'm studying logic from the Ebbinghaus's book "Mathematical Logic" and when I tried to solve some of the exercises doubt rises. Given a calculus C consisting of the following rules: ...
0
votes
4answers
56 views

Proof: For all real numbers $x$, If $x^2 - 5x + 4 \geq 0$, then either $x ≤ 1$ or $x ≥ 4$.

I need some help in proving the following statement: $x$, If $x^2 - 5x + 4 \geq 0$, then either $x ≤ 1$ or $x ≥ 4$. It would be greatly appreciated if someone could provide me a generic proof! I'm ...
0
votes
0answers
45 views

Formalization of the Proof of the Theorem of the Bijection of Composition of Two Mappings

I'm trying to formalize in FOL the proof of the stated theorem. Assume two mappings $f$,$g$. With a slight circularity for brevity's sake, let $B(f): \text{"f is a mapping which is bijective whose ...
0
votes
2answers
144 views

What approach should I take to establish this logical proof?

I need to design a logical math proof: Write a detailed structured proof to prove that if m and n are integers, then either 4 divides mn or else 4 does not divide n. Hint: Think about the form of ...
0
votes
3answers
79 views

Proof by cases, inequality

I have the following exercise: For all real numbers $x$, if $x^2 - 5x + 4 \ge 0$, then either $x \leq 1$ or $x \geq 4$. I need you to help me to identify the cases and explain to me how to ...
0
votes
1answer
54 views

Rooted Trees & Induction

So I am a little stumbled upon this question: A full binary tree is a rooted tree where each leaf is at the same distance from the root and each internal node has exactly two children. Inductively, a ...
2
votes
1answer
142 views

Question: Prove that a set of connectives is incomplete using structural induction

The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}. Let F be the smallest set such that: 1) Any propositional variable is ...
1
vote
1answer
56 views

Noncontradiction behind the uniqueness proof and proof by mathematical induction

I'm walking through equivalences, as it appears, between $$\exists!x:P(x)\,\,{\overset{\mathrm{?}}{\equiv}}\,\,\exists x:P(x)\wedge(P(x_1)\wedge P(x_2)\rightarrow x_1=x_2),$$ where I am not sure what ...
1
vote
1answer
58 views

Injectivity and Imdepotency implies Surjectivity

This question stem from Natural Deduction (FeedBack). The reason why I think it is justifiable to open this up as a separate question is that I am now considering other measures to show it, possibly ...
1
vote
4answers
73 views

How would I go about writing this proof in a formal way?

Let c ∈ Z: Write a detailed structured proof to prove the statement: If c^5 + 7 is even, then c is odd. I started out like this: ...
0
votes
3answers
132 views

Natural Deduction (FeedBack)

I am looking for feedback to three proofs (alternatively derivations) that I have constructed. The first is: Theorem. Injectivity does not imply surjectivity. Proof: Suppose $\{\phi\} \vdash ...
0
votes
1answer
39 views

Sequent calculus - where should I start?

I am given this formulae. $A \land B \implies C \lor D \lor E$ I want to deduce this formulae with sequent calculus. But my problem is that I dont know where to start, or which rule to take first. ...
2
votes
2answers
95 views

Rules of inference proofs

I have the following: Premise: {$p \lor q, q\rightarrow r,p \land s \rightarrow t, \lnot r, \lnot q \rightarrow u \land s$}, conclusion: $t$ I'm having a real hard understanding how to prove the ...
0
votes
1answer
196 views

Negation of double logic quantifiers

$$\forall a\forall b\ (a^{2}+4b-2=0)$$ How exactly would this be negated? would the $(a^{2}+4b-2 = 0)$ be negated twice (and as such remain the same? For example: $$\neg (\forall a\forall b\ ...
1
vote
2answers
87 views

Tautological implication

Determine whether or not $((P\land Q)\implies R)$ tautologically implies $((P\implies R)\lor (Q\implies R))$ How do I determine that $((P\land Q)\implies R)$ tautologically implies $((P\implies ...
0
votes
1answer
364 views

Induction proof for the lengths of well-formed formulas (wffs)

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible. The wffs in question are those associated with sentential/propositional logic. So, ...
1
vote
1answer
228 views

Induction on a well-formed formula (wff)

Let α be a well-formed formula (wff); let c be the number of places at which binary connective symbols (∧, ∨, →, ↔) occur in α; let s be the number of places at which sentence symbols occur in α. (For ...
0
votes
1answer
113 views

what are the Rosser Turquette axioms of Lukasiewicz 3 valued propositional logic?

I am trying to get my head around the Rosser-Turquette axiomatisation of Lukasiewicz n-valued logics, but cannot really follow it. Maybe if somebody can give me the axioms for 3 and 4 valued logic ...