I need some help understanding the steps to take to prove subsets.


For each of the following universal statements regarding any three finite sets $X, Y$, and $Z$, determine whether it is (universally) true or not. If you say it is false (not always true), give a counter-example to show that the statement is not true in that case. If you say the statement is true, provide a proof to show it is true all the time.

My Notes: I can sort of understand the first 3 questions, but I don't understand the multiplication of sets ones. Also note before all these questions, there's (Universal quantifier of $X, Y$, and $Z$)

(solved the first 3 already by myself)

iv. $(X - Y) \times Z \subseteq (X \times Z) - (Y \times Z)$

v. $(X \times Z) - (Y \times Z) \subseteq (X - Y) \times Z$

vi. $(X - Y) \times Z = (X \times Z) - (Y \times Z)$

I really need this help someone urgently, and this is my first time trying this out.

Thank you!

  • $\begingroup$ Do you know the definition of $X \times Y$? $\endgroup$ – Ishfaaq May 17 '14 at 5:52
  • 1
    $\begingroup$ X x Y would be the Cartesian product of set X and Y right? So for example, if X = {a,b} and Y = {1,2} $X$ x $Y$ would be {(a,1),(a,2),(b,1),(b,2)} $\endgroup$ – xNinjaKittyx May 17 '14 at 5:56
  • $\begingroup$ The role of the Universal Quantifier in front of a set expression like $\forall X \forall Y(X \cap Y = Y \cap X)$ means that the formula holds for all "couples of sets $X,Y$, like in the algebraic expression : $(x+y)^2=x^2+2xy+y^2$. In order to prove it, you have to show that it hold for $X,Y$ whatever; then you can "generalize" it, i.e. cocnlude to the universally quantified version. Tho show that in does not hold, it is sufficient to find a "counterexample", i.e. a case in which the formula is false. Having found it, we are able to conclude that the "general" formula ... 1/2 $\endgroup$ – Mauro ALLEGRANZA May 17 '14 at 7:29
  • $\begingroup$ ...$\forall X \forall Y (...)$ is not true [e.g.if we find an odd number, we are licensed to conclude that "all numbers are even" is not true]. 2/2 $\endgroup$ – Mauro ALLEGRANZA May 17 '14 at 7:31

Here's some clarification rather than just giving the answer. The multiplication is the cartesian product of sets and results in ordered pairs of elements.

An element of $X\times Z$ is an ordered pair $(x,z)$ with $x\in X, z\in Z$.

An element of $Y\times Z$ is an ordered pair $(y,z)$ with $y\in Y, z\in Z$.

An element of $(X-Y)\times Z$ is an ordered pair $(a,z)$ with $a\in X, a\not\in Y, z\in Z$.

An element of $(X\times Z)-(Y\times Z)$ is an ordered pair $(b,z)$ with $(b,z) \in X\times Z, (b,z) \not\in Y\times Z$.


Correct. Then I shall do the first one for you. Suppose $ (a, b) \in (X - Y) \times Z$. That is $a \in (X - Y)$ and $b \in Z$. Then clearly $a \in X$ but not in $Y$ and $b \in Z$. Hence you must see that $(a, b) \in (X \times Z) - (Y\times Z)$. Therefore the first statement holds.

  • $\begingroup$ So then, (X x Z) would be {(a,b)} and (Y x Z) would be {(a)}, which makes (X x Z) - (Y x Z) still hold. Right? $\endgroup$ – xNinjaKittyx May 17 '14 at 6:11
  • $\begingroup$ @xNinjaKittyx - NO. What Ishfaaq has shown you is that $(a,b) \in (X×Z)$ and that $(a,b) \notin (Y×Z)$, because $a \notin Y$. Thus, because $(a,b) \notin (Y×Z)$, we cannot "subtract" it from $(X×Z)$ and we can conclude that $(a,b) \in (X×Z) - (Y×Z)$. Now enters the quantifier: because $a,b$ are whatever, we can conclude that $\forall a \forall b [(a,b) \in ((X−Y)×Z) \rightarrow (a,b) \in ((X×Z) - (Y×Z))]$. But this is the definition of set inclusion : $A \subseteq B$ iff $\forall x(x \in A \rightarrow x \in B)$. Thus, we have proved that: $(X−Y)×Z \subseteq (X×Z)-(Y×Z)$. $\endgroup$ – Mauro ALLEGRANZA May 17 '14 at 9:07
  • $\begingroup$ Both sets $(X−Y)×Z$ and $(X×Z)−(Y×Z)$ are cartesian products, i.e. sets of (ordered) couples. The first one is "made of" couples $(a,b)$ such that $a \in X-Y$ and $b \in Z$; the second one is "made of" couples $(a,b)$ which belongs to $(X×Z)$ but not to $(Y×Z)$. Thus, the elements of $(Y×Z)$ cannot be like $(a)$, which is incorrcet: we have $a$ or $(a,b)$ ... $\endgroup$ – Mauro ALLEGRANZA May 17 '14 at 9:27

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.