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

Question:

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!

• Do you know the definition of $X \times Y$? – Ishfaaq May 17 '14 at 5:52
• 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)} – xNinjaKittyx May 17 '14 at 5:56
• 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 – Mauro ALLEGRANZA May 17 '14 at 7:29
• ...$\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 – 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.

• 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? – xNinjaKittyx May 17 '14 at 6:11
• @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)$. – Mauro ALLEGRANZA May 17 '14 at 9:07
• 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)$ ... – Mauro ALLEGRANZA May 17 '14 at 9:27