-1

I haven't really found a solution to this confusion I currently have.

I know in certain cases, we can use "without loss of generality" to proceed in a proof. For example, to prove that "if a|b or a|c -> a|bc", we can assume without loss of generality that a|b and show that a|bc follows.

But let's say I have a theorem of the form: ∃a∈Z,∀b∈Z,(P(a)∧Q(b))

Doing a proof by contradiction, we would assume: ∀a∈Z,∃b∈Z,¬P(a)∨¬Q(b)

My question is would my proof be able to legitimately proceed this way? Assume ~P(a) Show this leads to a contradiction. Then, assuming the negation of the theorem leads to a contradiction so the original statement holds?

I have a suspicion that I can't do that, and instead the approach should be: Case 1: Assume ~P(a) Show this leads to a contradiction

Case 2: Assume ~Q(b) Show this leads to a contradiction

I appreciate any help!

slow learner
  • 11
  • 1
    Please use MathJax to typeset the formulas in your MSE posts: it's easy to use and produces output that is much easier to read than using text. As regards the mathematics, it is always valid (in classical logic) to assume the negation of what you are trying to prove (although often not very helpful). – Rob Arthan Mar 23 '24 at 21:02
  • Spliting into cases is worked, but it is slower. Usually for disjunction statement, I would like to start by $\forall a\in Z$ such that $P(a)$, then to show there exists $b\in Z$ where $\sim Q(b)$. – Angae MT Mar 23 '24 at 21:23
  • Yeah, you have to show both lead to a contradiction. Proving just $P(a)$ leads to contradiction you have proven $\exists a\in A, \forall b\in A P(a)$. You haven't proven that $Q$ must always also be true. – fleablood Mar 23 '24 at 21:39
  • "Then, assuming the negation of the theorem leads to a contradiction so the original statement holds?" Right... um, you have only proven one way the statement can be false leads to a contradiction. You have to prove the other was also leads to contradiction. Assumming $P$ is false and getting a contradiction tells us nothing about what would happen if $P$ were true and it was $Q$ that was false. – fleablood Mar 23 '24 at 21:42
  • I see now, this makes sense. Thank you for the replies everyone! Sorry about the formatting as well, will keep this in mind when asking a question again. – slow learner Mar 23 '24 at 22:03

0 Answers0