0
votes
3answers
25 views

Can the proof for the following 4 cases be simplified to 2 cases?

Let $X$ and $Y$ be finite and disjoint sets. Suppose we are required to prove the following: $|X|\ge 0 \text{ and } |Y|\ge 0 \Rightarrow Q $ where $Q$ is some statement. Therefore, I know I need to ...
1
vote
1answer
34 views

Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...
0
votes
1answer
48 views

Why are the different ways to write a universal statements equivalent?

Consider the following universal statements: $\forall a \in \mathbb{R}-\{0\}, a^2 > 0$ $\{a \in \mathbb{R} - \{0\}| a^2 > 0 \} = \mathbb{R}-\{0\}$ $a\in \mathbb{R}-\{0\} \Rightarrow a^2>0$ ...
1
vote
1answer
44 views

Provide the Proof for $\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$

Provide the Proof for $$\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$$ This is all i got so far: Assume $\forall x \,\bigl( P(x) \land Q(x) ...
-2
votes
2answers
48 views

Prove or disprove, Equivalence vs Implication? [closed]

Prove or disprove, for any universal set U and predicates P and Q [ ∃x∈U, P(x) ∧ Q(x) ] ⇒ [ ∃x∈U, P(x) ∧ (∃x∈U, Q(x)) ]
2
votes
2answers
112 views

Proving the roots of a polynomial are irrational

This is a homework question so I'm just looking for some guidance. Basically we are asked to write a step by step proof in the form of assume/then statements for: $\forall x \in \mathbb{R}, ax^2 + ...
2
votes
2answers
97 views

How to prove that the law of the excluded middle is necessary?

This is a follow up question to this answer by Carl Mummert to the question whether every proof with contradiction can also be proved without contradiction. As Carl Mummert pointed out, there are ...
2
votes
2answers
44 views

Free and bound variables in “if” statements

The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion $\forall x(x>2)$ is false. In the first case ...
3
votes
1answer
61 views

Prove $\neg\exists x \neg P(x)$ is a logical consequence of $\forall x P(x)$

How would you prove that 2. is a logical consequence of 1. using a Fitch style proof? $\forall x P(x)$ $\neg\exists x \neg P(x)$
3
votes
5answers
86 views

Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...
3
votes
2answers
59 views

Is this a proof by contradiction?

Below is a proof that any group of order $p^2$ is abelian $(p$ prime of course). Let $Z \left({G}\right)$ be the center of $G$. We know $|Z(G)|>1$. $\color{blue}{\text{Suppose}} \left\vert{Z ...
1
vote
2answers
43 views

What is the proper way to prove this?

First of all, here is the question I am trying to answer for context. I can see that the statement $\forall x \in \mathbb{Z} , \exists y \in \mathbb{Z}((x\leq y ) \wedge (x+y=0)) $ negates to ...
2
votes
2answers
53 views

Logic Proof with Natural Deduction: if I assume the antecedent, do I still have to prove the consequent?

I have the unpleasent feeling that my "proof" is dead wrong. The core of my concerns is: when I have something like A -> (B -> C) and I assumed ...
1
vote
1answer
45 views

Question about Logic Proof

Assuming $P$ is a unary predicate and $Q$ is a propositional variable, I'm trying to prove the following implication: $$ (\forall x (P(x)\rightarrow Q)\rightarrow ((\forall x P(x) )\rightarrow Q) $$ ...
1
vote
3answers
110 views

Are truth tables a valid method to prove an iff statement?

I recently had a homework assignment returned to me (for a Differential Geometry course, undergrad level) in which my instructor wrote "You cannot use truth tables to prove an if and only if ...
2
votes
1answer
62 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] ...
3
votes
2answers
116 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
76 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
105 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
95 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 ...
1
vote
1answer
54 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
26 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
115 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
76 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}}. ...
3
votes
6answers
380 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
36 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
151 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
39 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
57 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
196 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
116 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
61 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
70 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
42 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
93 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
56 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
109 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
88 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
48 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
66 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 ...
1
vote
1answer
75 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
47 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
57 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
32 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
119 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
63 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
63 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
58 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
51 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 ...