New answers tagged

1

Claim: Compact ($P$) metric space implies sequentially compact ($Q$). Proof. Assume $P\land \lnot Q$. We use $\lnot Q$ to construct an infinite sequence with no limit points. Because there are no limit points, each point in our space has an open neighbourhood containing only finitely many points of the sequence. These neighbourhoods form a cover and we use $...


2

I think you may be looking at this the wrong way. There are three distinct logical rules which are all equivalent. Each rule holds for all propositions $P$ and $Q$. Rule 1: $\neg \neg P \implies P$ This is the classic "proof by contradiction" rule. Rule 2: $(\neg P \implies \neg Q) \implies (Q \implies P)$ This is "proof by contrapositive"...


30

As you've noticed, there are (at least) three potential ways of proving an implication $p \Rightarrow q$: Assume $p$, and conclude $q$. Assume $\neg q$, and conclude $\neg p$. Assume both $p$ and $\neg q$, and derive a contradiction. If I understand you right, you're asking for a proof which is of the third kind. Moreover, you're asking for a proof which ...


9

I think you are overlooking the fact that proof by contradiction must invoke the tautology $(P\ \hbox{or}\ \neg P)$, called the law of excluded middle. To prove $P\Rightarrow Q$ by contradiction, we show that $(\neg Q\Rightarrow\neg P)$. The next step, which is where we deduce the conclusion $Q$, is where we must invoke the assumption that $P$ is "...


8

No, I suspect this situation never occurs. Here is why: If $P$ really implies $Q$, then we know logically that $\neg Q$ implies $\neg P$. Thus if you assume $\neg Q$, you will be able to deduce $\neg P$. In this way, you never "need" the assumption $P$.


4

I would like to use this as an opportunity to make an important distinction. Proof by contradiction is an argument of the form: Assume $\neg p$ Argue a contradiction under this assumption. Conclude $p$. Proof of negation is an argument of the form Assume $p$ Argue a contradiction under this assumption. Conclude $\neg p$ I learned about the difference ...


Top 50 recent answers are included