Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

Exercise 13 - Chapter 1

edited July 2018

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'}$$ .

• Options
1.
edited July 2018
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).
• Options
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'} \$$.
• Options
3.
edited August 2018

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}\$$.
• Options
4.
edited August 2018

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).