Cartesian Product

Definition. For non-empty sets $A,B,C$, the Cartesian product of $A$ with $B$ is the set of ordered pairs

For three sets, $A\times B\times C=\{(a,b,c):a\in A,\ b\in B,\ c\in C\}$ is a set of ordered triplets. In particular $A\times A=\{(a,b):a,b\in A\}$ -- this is not the same as $\{(a,a):a\in A\}$, which is only the "diagonal" of $A\times A$.

Order matters. Because the pairs are ordered, $A\times B\ne B\times A$ in general; equality $A\times B=B\times A$ forces $A=B$. The familiar $R\times R=\{(x,y):x,y\in R\}$ (written $R^2$) is the coordinate plane, and $R\times R\times R=R^3$ (written $R^3$) is ordered-triplet space.

Example. If $A=\{1,2,3\}$ and $B=\{2,4,6\}$, then

a subset of $R\times R$ with $3\times3=9$ elements.

Counting rule. $n(A\times B)=n(A)\,n(B)$ for finite $A,B$; similarly $n(A\times B\times C)=n(A)\,n(B)\,n(C)$.

Familiar subsets of $R\times R$. Graphs of ordinary curves are exactly subsets of $R\times R$: $\{(x,2x):x\in R\}$ (a line), $\{(x,x^2):x\in R\}$ (a parabola), $\{(x,\sqrt x):x\ge0\}$ and $\{(x,-\sqrt x):x\ge0\}$ (the two branches of $y^2=x$), $\{(x^2,x):x\in R\}$.

Worked examples from the book, in brief:

• Counting subsets of a set defined by a condition. For $A=\{x:x=4n+1,\ 2\le n\le5,\ n\in N\}=\{9,13,17,21\}$, $n(A)=4$ so $n(P(A))=2^4=16$.
• Language-survey cardinality. With three overlapping groups (percentages of 5000 people knowing three languages), the count "only Language A" is found via $n(A)-n(A\cap B)-n(A\cap C)+n(A\cap B\cap C)$, giving 1950 people -- confirmed independently by drawing a Venn diagram with the region percentages.
• A set-algebra identity. Statements like $((A\cup B'\cup C)\cap(A\cap B'\cap C'))\cup((A\cup B\cup C')\cap(B'\cap C'))=B'\cap C'$ are proved by using subset containments (e.g. $A\cap B'\cap C'\subseteq A\subseteq A\cup B'\cup C$) to collapse each bracket.
• Counting a "removed-element" family of subsets. If $X=\{1,\dots,10\}$, $A=\{1,2,3,4,5\}$, the subsets $B\subseteq X$ with $A-B=\{4\}$ correspond exactly to subsets $C$ of $\{6,7,8,9,10\}$ (take $B=C\cup\{1,2,3,5\}$), so there are $2^5=32$ such $B$.
• Cardinality algebra. If $n(B-A)=2n(A-B)=4n(A\cap B)$ and $n(A\cup B)=14$: setting $n(A\cap B)=k$ gives $n(A-B)=2k,\ n(B-A)=4k$, and since $n(A\cup B)=n(A-B)+n(B-A)+n(A\cap B)=7k=14$, $k=2$; then $n(A)=n(A-B)+n(A\cap B)=6$, so $n(P(A))=2^6=64$.
• Power-of-2 equation. Two sets with $m,k$ elements ($m>k$) where $2^m-2^k=112=2^4\times7$: factoring $2^k(2^{m-k}-1)=2^4\times7$ forces $k=4,\ 2^{m-k}-1=7\Rightarrow m-k=3\Rightarrow m=7$. …