Closure of relations betweens sets

[user88]

Hi all!

I am searching for an algorithm (most likely already present in the literature) that could solve the following problem:

Instance: Properties of sets of elements and relations between sets of elements
Question: Find the closure of the properties and relations

Possible properties of a set of elements S:
1. S=∅
2. S≠∅

Possible relations between sets S, T:
1. S⊆T
2. S∩T=∅
3. S=T
4. S≠T

Example.
Instance: {S∩T=∅, S⊆R, R⊆T}
Solution: Closure C = {S∩T=∅, S⊆R, R⊆T, S⊆T, S=∅}

Hope the formulation of the question is clear enough.. If not I am happy to try to make it more precise. The solution could probably be somehow extracted from the Venn's diagram, but exact algorithm I have not yet found.

So if anybody came across such an algorithm and could write your suggestions here I would very much appreciate it.

Thanks in any case

 

[Stephen Tashi]

Let's see, according the Wikipedia article on "closure", the closure of a binary relation R on the set SxT with respect to a property P is the smallest relation (i.e. the smallest as a set) that contains R (as a subset) and satisifies property P.

Since P can be any property, it would surprise me if there was any elegant algorithm for solving this problem in general.

As to the exmaple, trying to translate the object oriented programming jargon:

Possible properties of a set of elements S:
1. S=∅
2. S≠∅

Is this simply a statement of two possible cases for the set S or does it refer somehow to a property of the relation?

What is the property with respect to which, we are trying to compute the closure?

Example.
Instance: {S∩T=∅, S⊆R, R⊆T}
Solution: Closure C = {S∩T=∅, S⊆R, R⊆T, S⊆T, S=∅}

What is the relation that the Instance attempts to define? Does it define a binary relation? A ternary relation?

 

[user88]

Dear Stephen,

Thank you very much for your reply.

Let's see, according the Wikipedia article on "closure", the closure of a binary relation R on the set SxT with respect to a property P is the smallest relation (i.e. the smallest as a set) that contains R (as a subset) and satisifies property P.

The problem is that I am not sure whether the procedure that I described is called "finding the closure". Otherwise there would have not been any problems in finding the suitable information in the literature regarding this topic. Maybe in the literature the process that I mean here is called "finding the extension" or something else. It is my fault that I have not mentioned the "notion uncertainty" in the previous post.

Since P can be any property, it would surprise me if there was any elegant algorithm for solving this problem in general.

The number of possible properties P of a set is fixed here as well as the number of possible relations between sets.

Properties of a set can be thought of as unary predicates. We have the following properties:
-emptyness(S)=true iff S=∅;
-nonemptyness(S)=true iff S≠∅.

Obviously property emptyness is equivalent to negation of nonemptyness.

Relations between the sets can be thought of as binary predicates.
We have the following binary relations:
-empty_intersection(S,T)=true iff S∩T=∅;
-inclusion(S,T)=true iff S⊆T;
-equality(S,T)=true iff S=T;
-inequality(S,T)=true iff S≠T;

Equality is equivalent to negation of inequality.

So the number of properties of a set as well as relations between sets is fixed.

As to the exmaple, trying to translate the object oriented programming jargon:

Possible properties of a set of elements S:
1. S=∅
2. S≠∅

Is this simply a statement of two possible cases for a set S or does it refer somehow to a property of the relation?

These statements relate to two possible cases for a set S: either it is empty or not.

What is the property with respect to which, we are trying to compute the closure?

The properties and relations with respect to which, we are trying to compute the closure
have already been mentioned above in this post.
So properties are:
-emptyness(S)
-nonemptyness(S)

Relations are:
-empty_intersection(S,T)
-inclusion(S,T)
-equality(S,T)
-inequality(S,T)

What is the relation that the Instance attempts to define? Does it define a binary relation? A ternary relation?

The Instance has information about all properties of the sets S and T and relation between these sets.
In our example the instance states that:
1. empty_intersection (S,T) is true (S∩T=∅), i.e. S does not intersect with T
2. inclusion(S,R) is true (S⊆R), i.e. S is included in R
3. inclusion(R,T) is true (R⊆T), i.e. R is included in T

Intuitively what I mean by computing closure is the derivation of all the information that is possible to derive from the data described in the instance. However, as I have already mentioned this process could be called in the literature but something else.
So in our example, knowing that S is included in R and R is included in T gives us that
S is included in T (this bit is definitely called computing the transitive closure but it is only part of the problem considered).
Moreover, it is given that intersection of S and T is empty, which together with S⊆T means that S is empty. We can not get anymore information from the data stated in Instance, hence we have computed the "closure".

So maybe if there does not exist any algorithms in the context of set theory, it could be the case that an algorithm that solves a similar problems exists in some logic (like some sort of restricted variant of first order logic maybe)?

If it is still not clear what the question is, I would be happy to try to make things clearer.

Any further help will be very much appreciated.
Thanks again.

 

[Stephen Tashi]

Intuitively what I mean by computing closure is the derivation of all the information that is possible to derive from the data described in the instance. However, as I have already mentioned this process could be called in the literature but something else.

Let me see if I understand what that means.

Would the input to this function be relations between specific sets? For example suppose we have the input [itex] S \subset R [/itex] . Would this refer to two specific sets [itex] S [/itex] and [itex] R [/itex] instead of referring to the general concept of the subset relation among all pairs of sets?

Would the output of this function be (in some sense) all the binary relations that hold among pairs of sets mentioned in the input? Or do you want the output to include statements involving more than one pair of sets ( like [itex] S \subset T \cup W [/itex]) ? If so, it would be like a list of all the theorems in set theory that you could prove from the given input.

The experts in symbolic logic may have a name for the concept of "all theorems that can be derived from a given set of statements", at least all the theorems that can be derived under certain restrictions. I don't know what that name is. The trouble with saying "all true statement that can be proven" is that if you can prove statement A and statement B then the statement "A or B" is also provable, so you need a way restricting the list of proven statements so they don't include "trivial" things. For example, suppose the inputs are [itex] S \subset T [/itex] , [itex] V \subset W [/itex] . Do you want [itex] S \cup V \subset T \cup W [/itex] in the output?

[I'm having trouble with my LaTex expressions running into my text. I'll research this new problem and fix it if I can. In the meantime, I hope you can read the post.)

 

[user88]

Dear Stephan,

Thanks a lot for the reply.

Let me see if I understand what that means.

Would the input to this function be relations between specific sets? For example suppose we have the input [itex] S \subset R [/itex] . Would this refer to two specific sets [itex] S [/itex] and [itex] R [/itex] instead of referring to the general concept of the subset relation among all pairs of sets?

This will exactly refer to two specific sets S and R, more precisely to inclusion relation between these two specific sets.

Would the output of this function be (in some sense) all the binary relations that hold among pairs of sets mentioned in the input?

Yes, exactly.

Or do you want the output to include statements involving more than one pair of sets ( like [itex] S \subset T \cup W [/itex]) ? If so, it would be like a list of all the theorems in set theory that you could prove from the given input.

No, this is not needed. I only need all pairwise relations of sets that can be derived from the input.

The experts in symbolic logic may have a name for the concept of "all theorems that can be derived from a given set of statements", at least all the theorems that can be derived under certain restrictions. I don't know what that name is. The trouble with saying "all true statement that can be proven" is that if you can prove statement A and statement B then the statement "A or B" is also provable, so you need a way restricting the list of proven statements so they don't include "trivial" things. For example, suppose the inputs are [itex] S \subset T [/itex] , [itex] V \subset W [/itex] . Do you want [itex] S \cup V \subset T \cup W [/itex] in the output?

No, those kind of derivations are not required.

[I'm having trouble with my LaTex expressions running into my text. I'll research this new problem and fix it if I can. In the meantime, I hope you can read the post.)

Latex worked perfectly fine for you, I can read it without any problems. All symbols look nice.

Thank you very much
Best regards

 

[Stephen Tashi]

I think I understand the question now. I'd put it this way.

We have a array A[] that represent a finite vector A1,A2,...of sets. Adopt the convention that A[0] represents the null set. The properties of the other sets are inputs to our algorithm. Perhaps this array merely holds a string or symbol that represents the name of the set. So A[0] = "[itex] \emptyset[/itex]" and the other symbols are inputs "specified by the user".

We have a two dimensional array Equals[][] which contains input data about whether set A is equal to set A[j]. We can use the code: 0 = false, 1 = true, 2 = unknown. (This array would take care of specifying which sets are known to be null or not-null, as well as which sets were known to be equal or not equal to each other.)


We have an array Subset[][] that tells us initial information about whether set A is a subset of A[j], again using the entries 0,1,2

I don't know whether you want to deal with a ProperSubset[][] array.

We have an array Intersects[][] which tells whether the intersection of A and A[j] is not-null. It also has entries 0,1,2.

The problem is take the input data and revise the arrays Equals, Subset, and Intersects so that we replace all the 2's in them with either 0 or 1 whenever it is possible to prove by the axioms of set theory that they must have one of those definite values.

I haven't seen this problem solved. It's interesting enough that I suspect people have worked on it. I don't know good terminology for searching the topic. I'll think more about this.

 

[user88]

I think I understand the question now. I'd put it this way.

We have a array A[] that represent a finite vector A1,A2,...of sets. Adopt the convention that A[0] represents the null set. The properties of the other sets are inputs to our algorithm. Perhaps this array merely holds a string or symbol that represents the name of the set. So A[0] = "[itex] \emptyset[/itex]" and the other symbols are inputs "specified by the user".

We have a two dimensional array Equals[][] which contains input data about whether set A is equal to set A[j]. We can use the code: 0 = false, 1 = true, 2 = unknown. (This array would take care of specifying which sets are known to be null or not-null, as well as which sets were known to be equal or not equal to each other.)


We have an array Subset[][] that tells us initial information about whether set A is a subset of A[j], again using the entries 0,1,2

I don't know whether you want to deal with a ProperSubset[][] array.

We have an array Intersects[][] which tells whether the intersection of A and A[j] is not-null. It also has entries 0,1,2.

The problem is take the input data and revise the arrays Equals, Subset, and Intersects so that we replace all the 2's in them with either 0 or 1 whenever it is possible to prove by the axioms of set theory that they must have one of those definite values.

I haven't seen this problem solved. It's interesting enough that I suspect people have worked on it. I don't know good terminology for searching the topic. I'll think more about this.

Thank you very much, Stephan.

Yes, that is exactly what is meant.
There is certainly a relation with solving equations in boolean algebra.
So I guess in this area there should be something.
It is not that important to develop the new algorithm rather then to find something that has already been done in the literature.

Thanks again
All the best

 

[Stephen Tashi]

So far, the only thing I found by searching is several different listings for the "Set Reasoning Facility" , such as this PDF: http://www.google.com/url?sa=t&rct=...-qiBBQ&usg=AFQjCNFaDAtK9pgIzM653bbiJF6yeZvISg

If you have academic connections, you might email one of the authors, if they are still around.

 

[user88]

Dear Staphen,

Thank you very much for your help. This is very useful.

Kindest regards