0

I was given a claim that is know to be true and must prove it using reductio ad absurdum (RAA).

The problem states:

$\textbf{M}$ is the set of students in an academic program. $\textbf{A} \subset \textbf{M}$ are the students in the program who enrolled in class A. $\textbf{B} \subset \textbf{M}$ are the students in the program who are happy. Both $\textbf{A}$ and $\textbf{B}$ are non-empty.

The following proposition is known to be true:

$a \in \textbf{B} \implies a \in \textbf{A}$

Prove this proposition using RAA.

This is what I tried initially:

Suppose $a \in \textbf{B}$ and $a \notin \textbf{A}$.

From the known proposition, it follows that $a \in \textbf{A}$.

$\therefore a \in (\textbf{A} \cap \textbf{M\\A}) = \emptyset$ for any $a \in \textbf{M}$.

$\therefore \textbf{B} = \emptyset$, but $\textbf{B} \neq \emptyset$, so the proposition must be true.

Needless to say, I am not convinced by my own attempt. Moreover, this question says that to prove something using RAA you must contradict the entire proposition, not just its right hand side. So how can I prove this using RAA?

Arturo Sbr
  • 115
  • No, this is right. Remember that the statement P AND Q is false when at least one is false. – Sean Roberson Aug 31 '21 at 18:47
  • Oh, so by negating the implication I implicitly negate the entire proposition? – Arturo Sbr Aug 31 '21 at 18:56
  • Yes. The negation of P AND Q is P AND (NOT Q). – Sean Roberson Aug 31 '21 at 18:59
  • Great. Thanks. Would you like to submit that as an answer? – Arturo Sbr Aug 31 '21 at 19:00
  • Your question is extremely unclear. What do you mean when you say the proposition is "known to be true"? Does that mean it's an assumption or does it mean it's a consequence of given properties of the sets $A$, $B$ and $M$? The latter is false: take $M = {1, 2}$, $A = {1}$ and $B = {2}$ to see why. But if it's an assumption, then it doesn't need to be proved. – Rob Arthan Aug 31 '21 at 21:02
  • "Prove X is true, knowing that X is true. Suppose X is false. But X is known to be true, so that is a contradiction. Therefore X is true. Q.E.D." This is valid, but... – Graham Kemp Sep 01 '21 at 02:17

1 Answers1

0

To prove $P \implies Q$, you can show that $P \ \& \ \sim Q$ is false. What you have done is correct - you've arrived at a contradiction!

Sean Roberson
  • 9,110
  • That justifies the superficial structure of the OP's proof. It doesn't justify what the OP actually writes. – Rob Arthan Aug 31 '21 at 20:57