3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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=∅$. $\endgroup$ – Mauro ALLEGRANZA Sep 29 '14 at 16:00
  • 2
    $\begingroup$ +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. $\endgroup$ – ir7 Sep 29 '14 at 16:05
  • 1
    $\begingroup$ When typing text in formulas, please use \text{math is great} compare the difference: $math\;is\;great$ and $\text{math is great}$ $\endgroup$ – Alice Ryhl Sep 29 '14 at 16:43
3
$\begingroup$

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).

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.