0

Suppose $\mathcal{F}$ is a partition of $A$ and $\mathcal{G}$ is a partition of $B$. Let $\mathcal{F}$ $\otimes$ $\mathcal{G}$ be defined as follows: $$\mathcal{F} \otimes\mathcal{G} = \{Z \in \mathscr{P}(A\times B) \mid (\exists X)(\exists Y)(X\in \mathcal{F} \wedge Y \in \mathcal{G} \wedge Z = X \times Y)\}$$

Prove that $\mathcal{F}$ $\otimes$ $\mathcal{G}$ is a partition of $A$ $\times$ $B$.

My question is in regards to the proof of $A\times B\subseteq \bigcup\mathcal{F}\otimes \mathcal{G}$. My attempt is as follows:

Suppose $(a,b)$ $\in$ $A$ $\times$ $B$. Since $\mathcal{F}$ is a partition of $A $, $a$ $\in$ $X$ for some $X$ $\in$ $\mathcal{F}$. Similarly, $b$ $\in$ $Y$ for some $Y$ $\in$ $\mathcal{G}$ Let $Z$ = $X$ $\times$ $Y$. Suppose $(i,j)$ $\in$ Z. Then, $i$ $\in$ X $\subseteq$ A and $j$ $\in$ Y $\subseteq$ B or $(i,j)$ $\in$ $A$ $\times$ $B$. Thus, $Z$ $\subseteq$ $A$ $\times$ $B$ or Z $\in$ $\mathscr{P}$($A$ $\times$ $B$). Now it can be seen that Z $\in$ $\mathcal{F}$ $\otimes$ $\mathcal{G}$ and $A$ $\times$ $B$ $\subseteq$ $\cup$ $\mathcal{F}$ $\otimes$ $\mathcal{G}$. $\square$

Is my attempt valid? This proof differs from some other attempts I have seen online and I want to verify it.

ΑΘΩ
  • 3,930
  • You have not proved disjointness, nor have you checked that the parts are non-empty. – ancient mathematician Dec 04 '20 at 07:29
  • This question is not concerned with proving every part of the definition of a partition but only the portion I specified above. – Timmy Chyrklund Dec 04 '20 at 07:31
  • @ΑΘΩ I am not at all sure what your comment means. I am new to the concept of partitions. – Timmy Chyrklund Dec 04 '20 at 07:35
  • @ΑΘΩ This portion does make sense. I am trying to prove that $A$ $\times$ $B$ $\subseteq$ $\cup$ $\mathcal{F}$ $\otimes$ $\mathcal{G}$ – Timmy Chyrklund Dec 04 '20 at 07:37
  • @TimmyChyrklund If however you do place the union symbol in front of $\mathscr{P} \otimes \mathscr{Q}$ then that does make sense and it is precisely one of the relations that you must prove. In this case, yes indeed! – ΑΘΩ Dec 04 '20 at 08:39
  • @TimmyChyrklund You are overcomplicating the proof by needlessly introducing the objects $i$ and $j$. It is enough to argue that any ordered pair $(x, y) \in A \times B$ belongs to a cartesian product $X \times Y$ with $X \in \mathscr{P}$ (your $\mathcal{F}$) and $Y \in \mathscr{Q}$ (your $\mathcal{G}$). – ΑΘΩ Dec 04 '20 at 09:38
  • @ΑΘΩ I saw introducing (i,j) as necessary for showing that $Z$ belongs to $\mathcal{F}$ $\otimes$ $\mathcal{G}$ – Timmy Chyrklund Dec 05 '20 at 02:23
  • @TimmyChyrklund The instant $Z$ is introduced as the cartesian product $X \times Y$ with $X \in \mathscr{P}$ and $Y \in \mathscr{Q}$ it automatically qualifies as an element of $\mathscr{P} \otimes \mathscr{Q}$ by definition of this latter object. That is why no further argument is required, at all. – ΑΘΩ Dec 05 '20 at 04:10

1 Answers1

1

Let me suggest the most general version of this phenomenon. Consider a family $A$ of sets indexed by index set $I$. Agreeing to denote the set of all partitions of a given set $M$ by $\mathscr{Part}(M)$, let us consider a family $\mathscr{P} \in \displaystyle\prod_{i \in I}\mathscr{Part}(A_i)$ of partitions, which means that the component at each index $i \in I$ is a partition $\mathscr{P}_i \in \mathscr{Part}(A_i)$ on $A_i$.

We proceed to define the following set: $$\bigotimes_{i \in I}\mathscr{P}_i \colon=\left\{\prod_{i \in I}X_i\right\}_{X \in \displaystyle\prod_{i \in I}\mathscr{P}_i}$$ and seek to prove that: $$\displaystyle\bigotimes_{i \in I}\mathscr{P}_i \in \mathscr{Part}\left(\displaystyle\prod_{i \in I}A_i\right).$$

To prove this assertion, let us set $\mathscr{Q}\colon=\displaystyle\bigotimes_{i \in I}\mathscr{P}_i$ respectively $B\colon=\displaystyle\prod_{i \in I}A_i$. There are three statements we need to establish separately:

  1. Any $U \in \mathscr{Q}$ is a nonempty subset $\varnothing \neq U \subseteq B$: by definition, we have the expression $U=\displaystyle\prod_{i \in I}X_i$ for a certain family $X \in \displaystyle\prod_{i \in I}\mathscr{P}_i$. Since $\mathscr{P}_i$ is a partition of $A_i$ we infer $X_i \subseteq A_i$ for every $i \in I$ and thus $U \subseteq B$ (by virtue of the monotony of the cartesian product operation). Likewise, since $X_i \in \mathscr{P}_i$ for each $i \in I$ it follows that $X_i \neq \varnothing$ and as cartesian products of nonempty sets remain nonempty we gather that $U \neq \varnothing$.
  2. For any $U, V \in \mathscr{Q}$ we have $U \neq V \Rightarrow U\cap V=\varnothing$. Once again, let us consider expressions $U=\displaystyle\prod_{i \in I}X_i$ and $V=\displaystyle\prod_{i \in I}Y_i$, afforded by families $X, Y \in \displaystyle\prod_{i \in I}\mathscr{P}_i$. As $U \neq V$, there must exist an index $i \in I$ such that $X_i \neq Y_i$. However, since $X_i, Y_i$ are distinct members of the partition $\mathscr{P}_i$, this entails $X_i \cap Y_i=\varnothing$ and hence: $$U \cap V=\left(\prod_{i \in I}X_i\right) \cap \left(\prod_{i \in I}Y_i\right)=\prod_{i \in I}\left(X_i \cap Y_i\right)=\varnothing,$$ bearing in mind that the cartesian product of a family of sets at least one component of which is empty is itself (the product) empty.
  3. Finally, $B=\bigcup\mathscr{Q}$. Here we shall rely on the following fundamental:

Proposition. Let $J$ be a family of sets indexed by set $I$ and let furthermore $X$ be another family of sets, indexed by the disjoint union $\displaystyle\bigsqcup_{i \in I}J_i\colon=\displaystyle\bigcup_{i \in I}\left(\{i\} \times J_i\right)$. We then have the relation: $$\prod_{i \in I}\bigcup_{j \in J_i}X_{ij}=\bigcup_{k \in \prod_{i \in I}J_i}\prod_{i \in i}X_{ik_i}.$$

We apply the general proposition above to the instance of family $\mathscr{P}$ of partitions playing the role of $J$ and family $M$ -- given by $M_{iX}=X$, for any $i \in I$ and $X \in \mathscr{P}_i$ -- playing the role of $X$, in order to infer that: $$\begin{align} B&=\prod_{i \in I}A_i\\ &=\prod_{i \in I}\bigcup\mathscr{P}_i\\ &=\prod_{i \in I}\bigcup_{X \in \mathscr{P}_i}X\\ &=\bigcup_{Y \in \prod_{i \in I}\mathscr{P}_i}\prod_{i \in Y}M_{iY_i}\\ &=\bigcup_{Y \in \prod_{i \in I}\mathscr{P}_i}\prod_{i \in I}Y_i\\ &=\bigcup_{U \in \mathscr{Q}}U\\ &=\bigcup\mathscr{Q}. \end{align}$$

This concludes the argumentation and signifies the existence of a natural map: $$\begin{align} \prod_{i \in I}\mathscr{Part}(A_i) &\to \mathscr{Part}\left(\prod_{i \in I}A_i\right)\\ \mathscr{P} &\mapsto \bigotimes_{i \in I}\mathscr{P}_i. \end{align}$$

ΑΘΩ
  • 3,930