55.7k views
4 votes
Please answer question 5.

3. Let \( \Pi_{n} \) denote the set of all partitions on the set \( [n] \). Define a relation \( R \) on \( \Pi_{n} \) as follows: Given partitions \( p \) and \( q \) of \( [n] \), let \( (p, q) \in

User Sney
by
8.8k points

1 Answer

5 votes

Answer:

the relation \( R \) if and only if for every pair of elements \( (x) \) in \( p \ there exists a pair of elements \( (a) \) in \( q \) such that \( x \) is contained in \( a \) and \( y \) is contained in \( b \).

To prove that \( R \) is an equivalence relation we need to show that \( R \) is reflexive symmetric and transitive.

1. Reflexivity: For every partition \( p \) in \( \Pi_{n} \ every element \( x \) in \( p \) is contained in itself. Therefore \( (p) \) is in \( R \ so \( R \) is reflexive.

2. Symmetry: Let \( (p) \) be in \( R \ which means that for every pair \( (x) \) in \( p \ there exists a pair \( (a) \) in \( q \) such that \( x \) is contained in \( a \) and \( y \) is contained in \( b \). Since containment is a symmetric relation we can also say that for every pair \( (y) \) in \( p \ there exists a pair \( (b) \) in \( q \) such that \( y \) is contained in \( b \) and \( x \) is contained in \( a \). Therefore \( (q) \) is in \( R \ so \( R \) is symmetric.

3. Transitivity: Let \( (p) \) and \( (q) \) be in \( R \ which means that for any pairs \( (x) \) in \( p \) and \( (y) \) in \( r \ there exist pairs \( (a) \) in \( q \) such that \( x \) is contained in \( a \) and \( y \) is contained in \( b \ and there exists a pair \( (c) \) in \( q \) such that \( y \) is contained in \( c \) and \( z \) is contained in \( d \). Since containment is transitive (if \( x \) is contained in \( a \) and \( y \) is contained in \( b \ and \( y \) is contained in \( c \ then \( x \) is contained in \( c \ we can conclude that \( x \) is contained in \( d \). Therefore for every pair \( (x) \) in \( p \) and \( (y) \) in \( r \ there exists a pair \( (a) \) in \( q \) such that \( x \) is contained in \( a \) and \( z \) is contained in \( d \). Thus \( (p) \) is in \( R \ so \( R \) is transitive.

Since \( R \) is reflexive symmetric and transitive we can conclude that it is an equivalence relation on \( \Pi_{n} \).

User Lovesh Dongre
by
8.9k points