0
votes
1answer
42 views

Trouble understanding case analysis (proof by cases)

I've got a discrete math test coming up, and I've been studying religiously for the past week. Proof styles still frighten me though, I find it hard to wrap my head around them. Right now I am ...
1
vote
1answer
51 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
0
votes
0answers
30 views

What's the correct logical conclusion after proving a value holds?

I had to prove that for every set $s$, the number of subsets with odd cardinalities is $2^{n-1}$. I concluded that this formula holds everytime $|s| \geq 1$ and then I used an inductive process to ...
1
vote
1answer
34 views

Is there a Fitch style system that works with some of the modal logics?

My prof taught us to use trees to prove modal logic arguments. Trees seem to provide a more efficient way to test arguments than Fitch does. However, I find that trees generally, and alethic (modal) ...
6
votes
4answers
1k views

There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2 $$ I am stuck and I would really like to see a correct proof so I can move ...
0
votes
2answers
58 views

How to prove that for all $x$ there exists some $y$ where $ (x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
2
votes
3answers
71 views

$a > b+1 \Rightarrow a>x>b$?

If I have $a,b \in \mathbb R$ such that $$a > b+1 $$ It is assured that $\exists\space x \in \mathbb Z: a>x>b$ Does this property have some special name? How can this be proved? This idea ...
0
votes
1answer
44 views

Show that | and $\downarrow$ are the only binary connectives \$ such that {$} is functionally complete.

I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks ...
1
vote
2answers
43 views

Using logical Properties to prove a tautology

So I have to prove this as a tautology. I've been stuck on this forever and am not sure where to go. I experimented and got this far, and looking for some pointers on where to take it next. (p → q) ...
1
vote
0answers
36 views

Questions on logic behind “proof by contradiction”

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post. First of all, suppose I have a proposition $P$ and from this I can imply ...
1
vote
1answer
46 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
0
votes
1answer
138 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
1
vote
3answers
75 views

Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction

I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to ...
1
vote
3answers
33 views

Show that (P→Q) ∨(Q→R) is a tautology

I don't really understand Tautologies or how to prove them, so if someone could help, that would be great!
1
vote
3answers
47 views

Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]

I literally have no idea how to start this proof. I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.
0
votes
1answer
46 views

Is it true that $\forall x,y\exists z(P(z)\wedge P(x)\wedge P(y))\sim\forall x\exists z(P(z)\wedge P(x))\wedge\forall y\exists z(P(z)\wedge P(y))$?

I am trying to prove a theorem that uses similar equivalence and I think that the expressions above are in fact equivalent. Note, that $P(\cdot)$ is just a logical expression. I explain it to myself ...
4
votes
3answers
78 views

Don't understand theorem $\exists z\in \mathbb{R}\forall x\in \mathbb{R}^+\left[\exists y\in \mathbb{R}(y-x=y/x)\leftrightarrow x\neq z\right]$.

I am reading a book on proof-writing techniques. One of the main ideas is that whenever you want to prove a statement starting with existential quantifier, you must choose a particular instance of an ...
3
votes
2answers
59 views

Can't prove easy theorem $\emptyset \in F \rightarrow \cap F = \emptyset$.

This is a problem from a book that teaches proof-writing basics. This is an exercise that assumes that I have sufficient knowledge to be able to solve the problem. But I feel stuck at this moment. ...
15
votes
10answers
2k views

Having hard time understanding proofs by contradiction.

I am reading an introductory book on mathematical proofs and I don't seem to understand the mechanics of proof by contradiction. Consider the following example. $\textbf{Theorem:}$ If $P \rightarrow ...
3
votes
2answers
83 views

Checking understanding on proving uniqueness of identity and inverse elements of a group.

Sorry for such a trivial question, but just wanted to check my understanding. When proving a statement, for example, that the inverse of a group element is unique (in elementary group theory) one ...
0
votes
3answers
41 views

How to write $a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$

How can I write the expression $$a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$$ concisely and clearly in English? A direct translation yields $a$ divides $b$ and either {$a$ and $b$ ...
4
votes
1answer
80 views

The “converse” of $P\rightarrow(Q\rightarrow R)$

As everyone know, even when reading mathematics books, a paragraph written in natural language contains much more information than just its purely logical translation. For my next tutor session, I am ...
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
40 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
56 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
46 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
75 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
117 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
159 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
51 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
66 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
99 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
65 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
44 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
68 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
53 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
122 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
69 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
117 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
81 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
111 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
142 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
70 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
27 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
216 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
80 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
828 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
39 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
182 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
45 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 ...