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!

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.

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.

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?



That is, the objects A and B are equal iff applied on each of them give the same result and 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:



Here I've used a '.' to indicate that I want to apply 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)?



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:






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.

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

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.

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?