I'm studying for an exam and I'm having trouble with one of these problems.

Use proof-by-contradiction to prove the predicate $$(A \subseteq B) \implies (A \setminus B = \{ \})$$ where A and B are sets, "$\subseteq$" denotes "subset", and "$\setminus$" denotes the set difference operator.

You can use the following hint in your proof: $$ (\exists x, P(x)) \text{ and } (\forall y, \lnot P(y)) \implies \text{False} $$

I understand that A-B = {} translates to A and (intersect) not(B) = {}. This is because if A is a subset of B, A will not share any elements with not(B), because by definition B contains A.

I understand the logic but I'm having a little trouble constructing a by-contradiction proof of it In particular I am supposed to use the hint provided, but I'm not sure I understand it. Why the exist and All statement? Could someone translate it into plain English for me?



I'm sorry, but I could use some more help. The end of the class is almost near and I'm not going to get the grade I want. In fact I'm not sure if taking this class was worth it at all, in fact this class is the main reason I'm getting on an antidepressant now. I'm terrible at this stuff and I just want it to end, so please be patient with me while I try to get past these next grueling days until the exam.

I feel like I have a by-contradiction proof, but I'm still not using the hint. Could somebody take a look and guide me in the right direction?

Exist x in A-B
=> {Definition of '-'}
Exist x in (A and not(B))
=> {A is a subset of B}
Exist x in B and not(B)
=> {x cannot exist in both B and not B}

Thank you in advance.

  • $\begingroup$ The hint means: "there is an $x$ such that $P(x)$ is true" and "for all $y$, $P(y)$ is false" are mutually exclusive. $\endgroup$
    – Arthur
    Dec 1 '14 at 23:34
  • $\begingroup$ You have showed that from the assumption "by contradiction" : $A-B \ne \emptyset$ follows: $\exists x(x \in A \land x \notin B)$. But "unwinding" the assumption: $A \subseteq B$ we have that: $\forall x(x \in A \rightarrow x \in B)$. Now the final step: $p \rightarrow q$ is equivalent to $\lnot(p \land \lnot q)$. Thus the second formula is equivalent to: $\forall x \lnot(x \in A \land x \notin B)$. Thus : (i) : $\exists x (x \in A \land x \notin B)$ and (ii) : $\forall x \lnot (x \in A \land x \notin B)$ that is the "contradictory" couple : $\exists x P(x)$ and $\forall y \lnot P(y)$. $\endgroup$ Dec 2 '14 at 8:52

I. $A\subset B$ means $\forall x\in A, x\in B.$
II.By contradiction, if $\exists y\in A-B,$ then $\exists y\in A, x\not\in B.$ And what can you say about this?
Hope this helps.

  • $\begingroup$ I added an edit, please respond. $\endgroup$ Dec 2 '14 at 0:43

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.