I am trying to learn about proofs and one of the exercice in my book (Maths ABC) is about proof by contradiction. I think I understand the concept but I would like to have a feedback on the following proof about whether or not it is correct.

Let $A$ be the following proposition: $$[(S\cup P = P) \land (S\cap P = \emptyset)]\rightarrow(S = \emptyset)$$ Prove by contradiction that $A$ is true.

My proof:

Let assume that $[(S\cup P = P) \land (S\cap P )= \emptyset)]\rightarrow\;S\neq \emptyset$ is true.

$$(S\cup P) = \{x\mid x\in S \lor x\in P\}\land P\{x\mid x\in \emptyset\lor x\in P\}$$ hence, if $(S\cup P=P)$ we can see by symmetry that $S$ has to be equal to $\emptyset$ which is absurd and contradict our assumption.

$[(S\cup P = P)\land(S\cap P = \emptyset)]$ cannot be true if one of the two statement is false thus it is enough for us to assert that $S=\emptyset$

QEA

• You have used the fact that : if $(S \cup P) = (∅ \cup P)$, then $S=∅$. Consider $S = \{ 1 \}$ and $P = \{ 1,2,3 \}$. $S \cup P = \{ 1,2,3 \} =P$, but it is not true that $S=∅$. – Mauro ALLEGRANZA Sep 29 '14 at 16:00
• +1 to Mauro. My take by contradiction would be: If $S\not= \emptyset$, then there is $x\in S$. As $S\cup P=P$, then $x\in P$ too. So: $x\in S\cap P = \emptyset.$ Contradiction. – ir7 Sep 29 '14 at 16:05
• When typing text in formulas, please use \text{math is great} compare the difference: $math\;is\;great$ and $\text{math is great}$ – Alice Ryhl Sep 29 '14 at 16:43

The structure of the proof is wrong.

• The negation of $[(S \cup P = P) \text{ and } (S \cap P= \emptyset)] \implies (S = \emptyset)$ to prove by contradiction is $[(S \cup P = P) \text{ and } (S \cap P = \emptyset)] \text{ and } (S \ne \emptyset)$, it is not $[(S \cup P = P) \text{ and } (S \cap P = \emptyset)] \implies (S \ne \emptyset)$

• The statement $(S \cup P = P)$ does not imply $S = \emptyset$, since if $S \subseteq P$ then $(S \cup P = P)$ is true.

Now

Proof. Suppose for sake of contradiction that $[(S \cup P = P) \text{ and } (S \cap P = \emptyset)] \text{ and } (S \ne \emptyset)$. Since $S \cup P = P$, we have $S \subseteq P$. Thus $S \cap P = S \ne \emptyset$, a contradiction to the hypothesis $S \cap P = \emptyset$.

Maybe you can try prove

Let $A, B$ be sets. Show that the three statements $A \subseteq B$, $A \cup B = B$, $A \cap B = A$ are logically equivalent (any one of them implies the other two).

• I know the meaning of "Q.E.D.". What is the meaning of "Q.E.A."? – Cristhian Gz Sep 29 '14 at 16:27
• Thanks for your help! "Quod Est Absurdum" ("Which is absurd") – torr Sep 30 '14 at 2:46
• Ah! :) Enjoy your reading. Set theory is beautiful. – Cristhian Gz Sep 30 '14 at 2:51

Your proof is incorrect since $S \cup P = P$ does not imply that $S = \emptyset$. For example, if $S = \{1\}$ and $P = \{1, 2\}$, then $S \cup P = \{1\} \cup \{1, 2\} = \{1, 2\} = P$.

Assume $S \neq \emptyset$. Then there exists $x \in S$. Then $x \in S \cup P = P$, so $x \in P$. Since $x \in S$ and $x \in P$, $x \in S \cap P = \emptyset$, which is a contradiction.

I think your proof is wrong. The fact $S \cup P=P$ does not imply alone that $S$ is empty. It can be perfectly part of $P$. However together with the second condition $S\cap P=\emptyset$ they do imply that $S$ is empty.