Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
PS: I hope I typed all that LaTeX up correctly. :)

share|improve this question
1  
@AustinMohr: You mean: if $A\succ B$ and $A\ne B$, then $B\not\succ A$, right? –  Henning Makholm Aug 4 '12 at 22:09

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
Just what I was looking for! Thanks! –  David D Aug 4 '12 at 22:50

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.