Options

Exercise 13 - Chapter 1

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'} \) .

  1. Show that for each \( p \in P \) there is at most one \( p' \in P \) such that \( A_p = A'_{p'} \).
  2. Show that for each \( p' \in P \) there is a \( p \in P \) such that \( A_p = A'_{p'} \) .

Previous Next

Comments

  • 1.
    edited July 23
    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).

    Comment Source: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).
  • 2.

    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'} \).
    Comment Source: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'} \\).
  • 3.
    edited August 7

    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:

    1. 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}\).
    Comment Source: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}\\).
  • 4.
    edited August 8

    I like your approach, and I think your proof is more elegant than mine (and definitely better written).

    Comment Source:I like your approach, and I think your proof is more elegant than mine (and definitely better written).
Sign In or Register to comment.