1
$\begingroup$

Let $U = \{1,...,n\}$

And let $A$ and $B$ be partitions of the set $U$ such that $\bigcup A = \bigcup B = U$ and $|A|=s, |B|=t$

Let's define a relation between the sets $A$ and $B$ as follows: $B \succ A \iff \forall_{1 \leq i \leq t}, \exists_{1 \leq j \leq s}: B_i \subseteq A_j$

Now, we want to prove that $\succ$ is an antisymmetric relation. Thus, we want to prove that $\forall_{A,B},A \succ B \land B \succ A \implies A=B$

How would one prove this? I'm pretty much stuck after laying out the conditions, and I don't have a clue on what assumptions I should make that will lead me anywhere.

  • 1
    @AustinMohr: You mean: if $A\succ B$ _and_ $A\ne B$, then $B\not\succ A$, right?2012-08-04

2 Answers 2

5

First of all, for what you write to make sense, you're not picking two partitions and defining a relation between those particular two partitions. You're defining a single relation on the set of all partitions.

Second, I think you're overcomplicating things by considering a partition to be an indexed family of subsets of $U$. Indeed, if you consider the assignment of indices to be part of the partition, then what you want to prove is not true, because then the two partitions

$ A_1 = \{1\}, A_2 = \{2,3,\ldots,n\} $ and $ B_1 = \{2,3,\ldots,n\}, B_2 = \{1\} $ would satisfy $A\succ B\succ A$, but $A\ne B$.

So we need to work with partitions being unordered collections of subsets of $U$, and your relation should then be defined as $ B\succ A \quad\iff \forall b\in B\; \exists a\in A: b\subseteq a$

In order to prove that this is antisymmetic, we assume $A\succ B\succ A$ and seek to prove that $A \subseteq B$. (Then, since $A$ and $B$ were arbitrary, and we also have $B\succ A\succ B$, the same argument shows $B\subseteq A$, so $A = B$).

In order to prove this, it is crucial that $A$ and $B$ are partitions, which requires among other things that (1) any two different members of $A$ must be disjoint, and (2) the empty set is not in $A$.

Now, we're assuming that $A\succ B\succ A$. To prove $A\subseteq B$ consider any $x\in A$. One of the $\succ$s gives us $y\in B$ such that $x\subseteq y$, and the other gives $z\in A$ sucht that $x\subseteq y\subseteq z$. But because $x$ and $z$ are both in $A$, they must be either equal or disjoint. Since $x$ is non-empty and $x\subseteq z$ they can't be disjoint, so $x=z$. But then $x\subseteq y \subseteq x$, and $y$ must equal $x$. Since $y$ was in $B$, we have proved $x\in B$.

  • 0
    Just what I was looking for! Thanks!2012-08-04
0

The key to starting just about any proof is in the definition, so let's take a look:

$\forall_{A,B},A \succ B \land B \succ A \implies A=B$

We start with the quantifier; here it is $\forall_{A,B}$. So let's pick two arbitrary partitions $A$ and $B$.

Next we notice that we want to prove an implication. One proof strategy to use here is to assume the antecedant (the stuff on the left of the $\implies$) and try to prove the conclusion (the stuff on the right of the $\implies$).

Now we have reduced the problem to assuming that $A \succ B \land B \succ A$ and prove that $A = B$. How do you prove that two partitions are equal? I'll let you think about this for a little bit then come back and tell us what you come up with and where you get stuck.