# Re-partitioning a partitioned set using quotient sets

• Mar 29th 2011, 08:46 AM
CT2011
Re-partitioning a partitioned set using quotient sets
Hi,

I hope I've posted this in the right subforum. :)

I've been thinking about a problem for a while, but I've come to a halt. I would be really grateful for insight concerning this. So here goes.

I have a set U consisting of a finite arbitrary number of objects. Each of these objects is a 2-tuple (referred to as T1) where the first element is an arbitrary size finite set, while the second element is a new 2-tuple (referred to as T2). This new 2-tuple consists of two sets - also finite of arbitrary sizes.

The problem is:

Part 1:

I would like to partition the set U using a quotient set. Two objects of U is considered the same (and should reside in the same equivalence class) if the first element of their T1 is equal. ~ (equivalence relation) should be defined by an invariant / morphism that "checks" whether the first element of T1 for two objects is identical (equality of sets). This yields the quotient set U / ~.

Part 2:

The next step is to re-partition the quotient set U / ~ to yield a new quotient set (say V) where the equivalence classes of V are a subset of the equivalence classes of U / ~ (also considering that equivalence classes may "disappear" from U / ~). Thus, V may have fewer equivalence classes than U / ~. Specifically, the elements of each equivalence class of U / ~ should only be members of the "same" equivalence class of V if all objects' T2 tuple have disjoint sets respectively.

Since this is probably not clear just by reading, I've attached a figure illustrating things. It consists of three steps where each transistion (marked by a blue arrow) represents a partitioning.

Concerning the figure: For instance, A is an object of U. It consists of the tuple <Ax, Ay> (referred to as T1). Ax is a set of properties, whereas Ay is a new tuple (T2). T2 has two sets of objects a, b, c,... It can be assumed that all objects of U share the exact same structure.

I apology if my attempt to explain this is somewhat blurry. I is perfectly possible that another notation or structure than what I have used is possible. I have no experience in defining more complex structures than simple sets and tuples.

The initial problem (regardless of my attempt to formalise things) is a set of objects with some meta properties. Two objects are considered equal if their meta properties are the same. A new classification of objects can then be done based on if they contain the same subelements. If someone have a better mathematical structure for expressing this, you are welcome to bring it to the table.

Have a good day!
• Apr 1st 2011, 09:54 AM
Plato
I see that you have asked for this post to be moved.
I don't think its location has any thing to do with the lack of replies.
After first reading days ago, I decided not to even attempt to unravel it.
You really should post a clear simple example of what you are doing.
I am sure it is very clear to you, but I doubt it is to many others.
• Apr 1st 2011, 04:13 PM
Deveno
the trouble i see is that your attempt to refine the original partition is not an equivalence relation. for example, if A = {Ax, {1,2}, {1,3}}, then in your second partition, A is not equivalent to itself, because the sets {1,2} and {1,3} are not disjoint.

what i think you want to do is something like this: define f(S,T) = 0 if S∩T = Ø, f(S,T) = 1 if S∩T ≠Ø.

then define for A,B in [X], A~B iff f(Ay) = f(By).

that separates each equivalence class [X] into two subclasses: one subclass has only disjoint sets in the second 2-tuple, the other has "overlapping sets" (which appaently you want to discard).

another problem i see with your approach is, if you discard some of the sets, you'll lose some of your structure.

an analogy is this: we can partition the integers into their remainders modulo 4. now, perhaps we're only interested in integers equal to 1 mod 4, and 3 mod 4 (we've discarded all the even numbers, so we've "re-partitioned" by 2). that's fine, but we've lost the additive structure we had. we still have multiplication, perhaps that enough for our purposes, but maybe not.

perhaps if you give a better example of what it is you are trying to accomplish, we can give you a better way to do it.
• Apr 5th 2011, 04:07 AM
CT2011
Oh...replies, great!

Thanks guys! I understand that my question was not clear. I apologise for that.

This is absolutely something in the right direction:

f(S,T) = 0 if S∩T = Ø, f(S,T) = 1 if S∩T ≠Ø.
then define for A,B in [X], A~B iff f(Ay) = f(By).

I will start off a little more easy this time.

Question 1:

Is there any way that I can define my equivalence relation in terms of several properties including predicates? Let's say U is a multiset consisting of several sets, A, B, C, ...

Can I express the equivalence in similar terms as this?

$A \sim B \Leftrightarrow f(A) = f(B) \ and \ \forall x \forall yP(x,y) \ , \ x \in A \ \ y \in B \ A,B \in U$

That is, the objects A and B are equal iff $f$ applied on each of them give the same result and $P(x,y)$ is true for all objects in the two sets.

Question 2:

Say I have a set U consiting of A, B, C, ... where A, B, C are 2-tuples <X, Y> where X and Y are both sets. How can I address each of these subsets (X, Y) in the definition for equivalence? That is, can I do something similar:

$A \sim B \Leftrightarrow f(A.X) = f(B.X)$

Here I've used a '.' to indicate that I want to apply $f$ on the the X sets of A and B. Is this possible (with a correct notation)?

Question 3:

How can I address the elements of an equivalence class? Here I would like to build a set based on some logical properties. Can I do this (or something similar)?

$\{ y \ | \ \forall x \forall y [x] \ P(y) \wedge Q(y) \} , \ y \in [x]$

The idea here is that I would like to build a set consiting of all elements y, from all equivalence classes, where P(y) and Q(y) are both true.

Question 4 (put into practice):

I have a set U consiting of the 2-tuples A, B, C, ... Each of these 2-tuples consist of a new 2-tuple and a set. Some examples:

$
A = \langle \langle "p1", "p2", ... \rangle, \{ a, b, c \} \rangle
$

$
B = \langle \langle "p1", "p2", ... \rangle, \{ d, e, f, g \} \rangle
$

$
C = \langle \langle "p1", "p2", ... \rangle, \{ e, h \} \rangle
$

$
D = \langle \langle "p1", "p3", ... \rangle, \{ i, j \} \rangle
$

Here, I would like to partition the elements of U where elements that have equal properties ( "p1", "p2", ... ) and disjoint sets reside in the same equivalence class (in one operation). In the above examples, equivalence should be present between A and B, and A and C. Why:

- A and B do both have the same properties and disjoint sets
- A and C do both have the same properties and disjoint sets
- A and D do not have the same properties
- B and C do not have disjoint sets
- C and D do not have the same properties

How can this be expressed mathematically?

As may be evident, there are two choices for equivalence classes here. Either A and B can reside in the same class, or A and C. Is there a way to order how equivalence classes are built to ensure that elements are grouped alphapetically (starting from A). Thus, A and B should reside in the same equivalence class, while C resides in a singleton equivalence class.

To sum up, all elements of U residing in the same equivalence class must have the same properties and mutually disjoint sets. All sets and tuples are finite.
• Apr 11th 2011, 02:13 AM
CT2011
Hm...kinda interesting to know why there are no replies here. Are the questions unclear somehow or do nobody have any viable hints, comments, etc.?
• Apr 11th 2011, 12:04 PM
Deveno
it is still hard to see what you ar trying to accomplish. some quick answers, given without much in-depth thought:

1.) this appears to be a valid equivalence.

2.) a cartesian product (that is a 2-tuple (x,y) with x in X, and y in Y) comes with two "built-in" projection functions p1 and p2, given by p1(x,y) = x, p2(x,y) = y.

it is perfectly permissible for the x,y to be sets, in which case X x Y = U{x} x U{y}. there is no reason why you cannot define an equivalence by:

(x,y) ~ (x',y') iff p1(x,y) ~' p1(x',y') (here ~' is an equivalence just among the x's). in other words, you can define an equivalence amongs pairs (2-tuples) by "ignoring one of the pair".

3.) there is a canonical way to form such sets, it is called intersection.

4.) you can't do this with an equivalence, transitivity forces A,B and C to all belong to the same equivalence class. if you want to sub-divide by some kind of lexicographic ordering, you need to create another refinement.
• Apr 15th 2011, 02:37 AM
CT2011
This was strange. I posted a reply to this and now it's suddenly gone!?

Anwyay, thanks for taking the time to answer these questions. I feel I'm a step closer to a solution, which is great! Do you know about some online resources that address similar topics, as of my questions?