It looks like you're new here. If you want to get involved, click one of these buttons!
Suppose that \(A\) is a set and
$$ \lbrace A_p \rbrace_{ p \in P } $$ and
$$ \lbrace A^\prime_{p^\prime} \rbrace_{ p^\prime \in P^\prime } $$ are two partitions of \(A\) such that for each \( p \in P \) there exists a \( p' \in P' \) with \( A_p = A'_{p'} \) .
Comments
Suppose there were another element \(p''\in P'\) such that \(A_p=A_{p''}'\). By transitivity, this would yield \(A_{p'}'=A_{p''}'\). However, each element of the index set \(P'\) must map to a different element of the partition \(\{A_q'\}_{q\in P'}\), so the above equality is in contradiction to the definition of a partition. Conclude that for every \(p\in P\) there is a unique \(p'\in P'\) associated to it.
Since the two partitions partition the same set, \(\forall p'\in P',\,\exists Q_{p'}\subseteq P\) such that \(A_{p'}'\subseteq \cup_{q\in Q_{p'}}A_q\). Let \(M_{p'}\subseteq P\) be such a subset that is minimal, i.e., there is no subset of \(M_{p'}\) such that \(A_{p'}'\subseteq\cup_{q\in M_{p'}}A_q\). By 1., for every \(q\in M_{p'}\) there is a unique \(q'\in P'\) such that \(A_q=A_{q'}'\). So, \(A_{p'}'\subseteq\cup A_{q'}'\), where the union runs over the \(q'\) that are determined by the \(q\in M_{p'}\). But since partitions consist of disjoint sets, if \(A_{p'}'\subseteq\cup A_{q'}'\), then there is a \(q''\) in the set of \(q'\)s such that \(q''=p'\). By minimality this set of \(q'\)s must be a singleton (containing just the index \(p'\)), and thus so must its preimage under the map of 1. In conclusion, for each \(p'\in P'\) there is a unique \(p\in P\) such that \(A_{p'}'=A_p\).
In fact, the maps of 1. must correspond to permutations of the elements of \(P\) (since \(P\) and \(P'\) must be related by a bijection).
1. Suppose there were another element \\(p''\in P'\\) such that \\(A_p=A_{p''}'\\). By transitivity, this would yield \\(A_{p'}'=A_{p''}'\\). However, each element of the index set \\(P'\\) must map to a different element of the partition \\(\\{A_q'\\}_{q\in P'}\\), so the above equality is in contradiction to the definition of a partition. Conclude that for every \\(p\in P\\) there is a unique \\(p'\in P'\\) associated to it. 2. Since the two partitions partition the same set, \\(\forall p'\in P',\,\exists Q_{p'}\subseteq P\\) such that \\(A_{p'}'\subseteq \cup_{q\in Q_{p'}}A_q\\). Let \\(M_{p'}\subseteq P\\) be such a subset that is minimal, i.e., there is no subset of \\(M_{p'}\\) such that \\(A_{p'}'\subseteq\cup_{q\in M_{p'}}A_q\\). By 1., for every \\(q\in M_{p'}\\) there is a unique \\(q'\in P'\\) such that \\(A_q=A_{q'}'\\). So, \\(A_{p'}'\subseteq\cup A_{q'}'\\), where the union runs over the \\(q'\\) that are determined by the \\(q\in M_{p'}\\). But since partitions consist of disjoint sets, if \\(A_{p'}'\subseteq\cup A_{q'}'\\), then there is a \\(q''\\) in the set of \\(q'\\)s such that \\(q''=p'\\). By minimality this set of \\(q'\\)s must be a singleton (containing just the index \\(p'\\)), and thus so must its preimage under the map of 1. In conclusion, for each \\(p'\in P'\\) there is a unique \\(p\in P\\) such that \\(A_{p'}'=A_p\\). In fact, the maps of 1. must correspond to permutations of the elements of \\(P\\) (since \\(P\\) and \\(P'\\) must be related by a bijection).I believe there is a typo in this problem and part 1 should read:
I believe there is a typo in this problem and part 1 should read: 1. Show that for each \\( p \in P \\) there is at most one \\( p' \in P' \\) such that \\( A_p = A'_{p'} \\).I agree with David's answer for 1., but I attacked 2. in a slightly different way and would appreciate some feedback on my approach and conclusion:
I agree with David's answer for 1., but I attacked 2. in a slightly different way and would appreciate some feedback on my approach and conclusion: 2. By 1., we know that all elements of \\(P\\) can be put in \\(1-1\\) correspondence with some subset \\(Q'\subset P'.\\) We want to show that this subset \\(Q'\\) is actually all of \\(P'\\), that for every \\(p'\in P', \; \exists p\in P\\) such that \\(A_{p'}' = A_{p}\\). Suppose that this is not true, that \\(Q'\\) is a proper subset of \\(P'\\). Then there exists at least one \\(\hat{p}'\in P' - Q'\\) so that there is no \\(p\in P\\) where \\(A_{\hat{p}'}' = A_{p}\\). But then the partition \\(\{A_{p'}'\}_{p'\in P}\\) contains at least one more set \\(A_{\hat{p}'}'\\) that does not exist in the partition \\(\{A_{p}\}_{p\in P}\\). This contradicts the assumption that both partitions partition the same set, hence there must exist some \\(p\in P\\) such that \\(A_{\hat{p}'}' = A_{p}\\). In conclusion, for all \\(p'\in P'\\) there is a unique (by the bijection established in part 1) \\(p\in P\\) such that \\(A_{p'}' = A_{p}\\).I like your approach, and I think your proof is more elegant than mine (and definitely better written).
I like your approach, and I think your proof is more elegant than mine (and definitely better written).