Understanding Set Theory and the + Symbol: Solving Equations with Sets

[mikemhz]

Set Theory "+" symbol

1. X, Y and Z are sets. Does X × (Y + Z) = X × Y + X × Z?

The solution starts like so:

X × (Y + Z) = {(x,(y,0)) | x $\in$ X, y $\in$ Y}$\cup${(x,(z,1)) | x $\in$ X, z $\in$ Z}

I don't understand how the "+" symbol works. Why does it equate to this (x,(y,0)) (x,(z,1)) format? 0... 1...?

This is a frustrating early stumbling point for my discrete mathematics, "foundations of computer science" exam revision. Please help.

 

[Fredrik]

I think more people would be able to help if you define +, 0 and 1, and explain if you're talking about subsets of ℝ or something else.

 

[SammyS]

1. X, Y and Z are sets. Does X × (Y + Z) = X × Y + X × Z?

The solution starts like so:

X × (Y + Z) = {(x,(y,0)) | x $\in$ X, y $\in$ Y}$\cup${(x,(z,1)) | x $\in$ X, z $\in$ Z}

I don't understand how the "+" symbol works. Why does it equate to this (x,(y,0)) (x,(z,1)) format? 0... 1...?

This is a frustrating early stumbling point for my discrete mathematics, "foundations of computer science" exam revision. Please help.

Hello mikemhz. Welcome to PF !

[STRIKE]I suspect there's more to this problem than you have given us.

Please state the complete problem as it was given to you. As Fredrik suggested, there must be more information regarding the sets X, Y, and Z and the opperation, +, than you have stated.[/STRIKE]

Added in Edit:
I see you posted the problem seconds after I posted this.

 

[mikemhz]

So the full question is phrased like so:

Suppose X; Y and Z are sets. Does X × (Y + Z) = X × Y + X × Z?
If X, Y and Z are finite, what can we say about the cardinalities of
X × (Y + Z) and X × Y + X × Z?

I'm not looking for the solution. It's sitting here in front of me. I just don't understand the very first step. That being:

X×(Y+Z) = {(x,(y,0)) | x $\in$ X, y $\in$ Y}$\cup${(x,(z,1)) | x $\in$ X, y $\in$ Y}

X×Y+Y×Z = {((x, y),0) | x $\in$ X, y $\in$ Y}$\cup${((x,z),1) | x $\in$ X, z $\in$ Z}


These two are clearly not equal as sets because they have different
elements: for example, given x $\in$ X, y $\in$ Y , by the definition of ordered
pairs it is not the case that (x,(y, 0)) = ((x, y), 0).

I understand why these are not equal, but not where 1 and 0 come into it, or what "+" means, as it's not in the standard set theory symbol set.

EDIT: I also suspect there is a typo on the first line of the solution, surely the second half involves Z rather than Y?

 

[mikemhz]

So I just looked through the lecture slides and the "+" symbol means the sum or disjoint union.

X+Y = { (x,0) | x∈X} ∪ {(y,1) | y∈Y}

I think this is an important point to clarify because it crops up again later in the module. Still why 0 and 1?

EDIT: OK. In a moment of clarity I've realized that the digit relates to the position of the ordered pair. So in X+Y, x is in the 0 position, and y is in the 1 position.

 

[Fredrik]

*Deleted*

 

[Fredrik]

So I just looked through the lecture slides and the "+" symbol means the sum or disjoint union.

X+Y = { (x,0) | x∈X} ∪ {(y,1) | y∈Y}

I think this is an important point to clarify because it crops up again later in the module. Still why 0 and 1?

OK, I think I understand the definition. The idea is that the "disjoint union" of X and Y should be the union of two disjoint sets X' and Y' such that X can be bijectively mapped onto X' and Y can be bijectively mapped onto Y'. So we can use any set with two members to define X' and Y'. We denote the two members by 0 and 1, and define
\begin{align}
&X'=\{(x,0)|x\in X\}\\
&Y'=\{(y,1)|y\in Y\}\\
&X+Y=X'\cup Y'
\end{align}Edit: I think you should just start with a statement like "Let $w\in X\times(Y+Z)$." Then you can use the definitions to figure out something about w. You can also try the assumption $w\in X\times Y+X\times Z$, and see what that tells you about w.