2
$\begingroup$

Prove that $A \ne B$ is equivalent to the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$.

Given:

P: $A \ne B$ is equivalent

Q: the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$.

Definition 3.1.8 states that we let $A$ and $B$ be sets. Then $A$ equals $B$, written $A=B$, when both $A \subseteq B$ and $B \subseteq A$. Thus the symbols $A$ and $B$ denote the same set; the negation of $A=B$ is written simply as $A \neq B$.

The logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$ suggests that some $x$ belongs to set $A$, and not set $B$, or some $x$ belongs to set $B$, and not set $A$.

The elements of $A$ may differ from those of $B$. Also, $B$ may not have the same elements as $A$:

$A$ is not the same set as $B$.

Therefore, $A \neq B$.

$A \neq B$ suggests that $A$ and $B$ are different sets. Hence, some $x$ values belong to set $A$, and not set $B$, or some values belong to set $B$, and not set $A$.

As a result, $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$.

Did I do this right or am I missing something?

$\endgroup$
  • $\begingroup$ Suggestion: add at the beginning "Let be two sets...". Releted: en.wikipedia.org/wiki/Axiom_of_extensionality. $\endgroup$ – Martín-Blas Pérez Pinilla Jan 31 '14 at 8:04
  • $\begingroup$ @Martín-BlasPérezPinilla Invoking ZFC for this sort of elementary stuff seems overkill. Her class is unlikely to cover the ZF axioms. $\endgroup$ – Newb Jan 31 '14 at 8:11
  • $\begingroup$ True, but knowing more things never kills. :-) $\endgroup$ – Martín-Blas Pérez Pinilla Jan 31 '14 at 8:13
  • $\begingroup$ yes this is from an Intro to Advanced Mathematics class. So if there's fancy stuff from any grad school course, I'm not going to understand immediately. $\endgroup$ – usukidoll Jan 31 '14 at 8:13
  • $\begingroup$ @usukidoll My apologies; I've changed the gender pronoun. And yeah, the stuff Martin was mentioning was more advanced (though certainly not at the graduate level) and will not be covered in an introductory course like the one you seem to be taking (judging by your questions). $\endgroup$ – Newb Jan 31 '14 at 8:16
1
$\begingroup$

I think your reasoning is correct, if a bit messy. Here's how I would do it:

$A\neq B$ is equivalent to $\neg (A=B)$ which is equivalent to $\neg((A\subseteq B)\wedge(B\subseteq A))$. This is of course equivalent to $\neg(A\subseteq B) \vee \neg(B\subseteq A)$ by deMorgans rule.

Now take a look at the statement $\neg(A\subseteq B)$. Since $A\subseteq B$ is defined by $\forall x: (x\in A \Rightarrow x\in B)$, its negation is therefore $\exists x: (x\in A \wedge x\notin B)$. Now that you know that $$\neg(A\subseteq B)$$ is equivalent to $$\exists x: (x\in A \wedge x\notin B),$$

plug this into the statement $$\neg(A\subseteq B) \vee \neg(B\subseteq A)$$ which you know is equivalent to $A\neq B$ and you will have your result.

$\endgroup$
  • $\begingroup$ ah yes of course the set version of De Morgans Law. I forgot about that. $\endgroup$ – usukidoll Jan 31 '14 at 8:11
  • $\begingroup$ Actually, what I uset was not the set version of the law. If you look closely, I just hat two statements, statement $a$ which was $A\subseteq B$ and statement $b$ which was $B\subseteq A$. Then I used De Morgan's law to prove equivalence between the statements $\neg(a\wedge b)$ and $\neg a \vee \neg b$. $\endgroup$ – 5xum Jan 31 '14 at 8:17
1
$\begingroup$

You added some unnecessary stuff; the essentials of your proof are in this statement:

The logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$ suggests that some x belongs to set A, and not set B or some x belongs to set B, and not set A.

A may not have the same values in B. Also, B may not have the same values in A.

A is not the same set as B. Therefore, $A \neq B$

Unfortunately, this is insufficient from a formal point of view.

I would suggest this, if you're trying to be formally correct:

We know A = B iff $A \subseteq B$ and $B \subseteq A$. We may write $A = B \Leftrightarrow (A \subseteq B) \land (B \subseteq A)$. Then taking negations of both gives us: $\lnot (A = B) \equiv A \neq B \Leftrightarrow \lnot (A \subseteq B) \lor \lnot (B \subseteq A)$, the right side by DeMorgan's Law. It is then easy to show that $\lnot (A \subseteq B) $ is equivalent to $(\exists x)(x \ in A, x \notin B)$, and the other, similar case. (You actually have to show this.) Then you are done. (You may also want to explain that you can just take negations of both sides of the $\Leftrightarrow$ statement because you can divide the iff into its two directions and then just apply the contrapositive law to each.)

$\endgroup$
1
$\begingroup$

Starting with Newb's suggestion :

$A = B \quad$ iff $\quad \forall x [(x \in A \rightarrow x \in B) \land (x \in B \rightarrow x \in A)]$

So, $A \neq B$ becomes, using property of $\forall$ :

$\lnot [\forall x (...) \land \forall x (...)]$ i.e. $\exists x \lnot (...) \lor \exists x \lnot (...)$

using againg properties of quantifiers and De Morgan.

Again, using De Morgan "inside" the parentheses, and the definition of $(p \rightarrow q)$ as $(\lnot p \lor q)$, we have :

$\exists x (\lnot \lnot x \in A \lor \lnot x \in B) \lor \exists x (\lnot \lnot x \in B \lor \lnot x \in A)$

$\exists x (x \in A \lor x \notin B) \lor \exists x (x \in B \lor x \notin A)$.

$\endgroup$
0
$\begingroup$

Your analysis looks fine.

Also you may try using contradiction to prove this.

$\endgroup$
0
$\begingroup$

Just to provide a different perspective, here is how I would do this: start with the most complex side, and use the laws of predicate logic to simplify in the direction of the simpler side.

We can calculate as follows: \begin{align} & \langle \exists x :: x \in A \land x \not\in B \rangle \;\lor\; \langle \exists x :: x \in B \land x \notin A \rangle \\ \equiv & \qquad \text{"$\;\exists\;$ distributes over $\;\lor\;$"} \\ & \langle \exists x :: (x \in A \land x \not\in B) \;\lor\; (x \in B \land x \not\in A) \rangle \\ \equiv & \qquad \text{"DeMorgan -- suggested by the negative shape of our goal"} \\ & \lnot \langle \forall x :: (x \not\in A \lor x \in B) \;\land\; (x \not\in B \lor x \in A) \rangle \\ \equiv & \qquad \text{"$\;\lnot P \lor Q\;$ is one way to write $\;P \Rightarrow Q\;$, twice"} \\ & \lnot \langle \forall x :: (x \in A \Rightarrow x \in B) \;\land\; (x \in B \Rightarrow x \in A) \rangle \\ \equiv & \qquad \text{"equivalence is double implication"} \\ & \lnot \langle \forall x :: x \in A \;\equiv\; x \in B \rangle \\ \equiv & \qquad \text{"definition of equality on sets, i.e., set extensionality"} \\ & A \not= B \\ \end{align}

$\endgroup$
  • $\begingroup$ I wish I knew how to do it through this method, but I wasn't taught that which sucks because it looks easier than what I'm doing...I'm just going through definitions. $\endgroup$ – usukidoll Feb 4 '14 at 0:45

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.