Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like clarification on a set theory question I have.

The question reads:

Suppose $X$, $Y$ and $Z$ are sets: Does $X \times (Y +Z)=(X\times Y)+(X\times Z)$ (Where $\times$ is the cartesian product operator)?

Now, the answer is already given as:

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

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

I can see that by the rule of ordered pairs, these 2 sets are different. What I don't understand is where the union comes from and moreover the appearance of 0 & 1 in both of these sets? I believe it may be as simple as being unable to find clarification for what the '+' operator means, but any help with this is appreciated.

Many thanks.

share|improve this question
2  
Per this wiki page, + in Set Theory means disjoint union. en.wikipedia.org/wiki/List_of_mathematical_symbols –  anorton Dec 18 '12 at 21:33
add comment

3 Answers

up vote 5 down vote accepted

The notation $X+Y$ comes from cardinal arithmetic, which in turn comes from finite arithmetics.

We know that if $X\cap Y=\varnothing$ and $|X|=n$ and $|Y|=k$ then $|X\cup Y|=|X|+|Y|=n+k$. So in order to ensure that $X$ and $Y$ are disjoint we define the following: $$X+Y=X\times\{0\}\cup Y\times\{1\}$$

Now it holds that $|X+Y|=|X|+|Y|$.

The statement in your question essentially asks whether $+,\times$ obey the same distributive laws as we know them from finite arithmetics. The answer is often no in the strict equality sense, but it is yes when we pass from sets to their cardinals.

share|improve this answer
add comment

$X+Y$ is the disjoint union of $X$ and $Y$, and is often denoted $X \sqcup Y$. The way this is usually formalised is to define $$X + Y = X \times \{ 0 \} \cup Y \times \{ 1 \}$$ and then we can embed $X \hookrightarrow X+Y$ by $x \mapsto (x,0)$ and $Y \hookrightarrow X+Y$ by $y \mapsto (y,1)$. But this is just a formalisation and could be done in many other ways.

Side-note: Often you see $+$ used instead of $\sqcup$ in the context of category theory, where $+$ denotes the coproduct. In the category $\mathbf{Set}$ of sets and functions, the coproduct is (some formalisation of) the direct sum. This generalises to other categories and a lot of the results carry across. The reason why I mention category theory is that, although $X \times (Y + Z)$ and $X \times Y + X \times Z$ aren't equal, they are naturally isomorphic in the category $\mathbf{Set}$ and indeed any category in which these coproducts exist.

share|improve this answer
add comment

Apparently, your "$+$" is disjoint union (in contrast to the usual union $\cup$). In order to make arbitrary sets $A, B$ disjoint, they are replaced with $A\times\{0\}$ and $B\times \{1\}$ before taking union, i.e. $$\tag1A+B=A\times\{0\}\cup B\times \{1\}$$

Note that in general $A+B\ne B+A$, $(A+B)+C\ne A+(B+C)$ and also the distributive property from your question does not hold in a strict sense. However, there are obvious and natural bijections between these sets that should be equal, e.g. $$\tag2A+B\to B+A, ((a,0),(b,1))\mapsto (b,0),(a,1))$$ and $$\tag3A\times (B+C)\to A\times B+A\times C, (a,(x,k))\mapsto ((a,x),k)$$

Note that the choice of $0$ and $1$ in $(1)$ used to enforce disjointness is somewhat arbitrary and the bijectins in $(2)$, $(3)$ are in a manner of speaking in fact the identity if you just close your eyes just enough to avoid seeing this arbitrariness.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.