Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Closure of relations betweens sets

  1. Mar 13, 2012 #1
    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

    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
  2. jcsd
  3. Mar 17, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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:

    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?

    What is the relation that the Instance attempts to define? Does it define a binary relation? A ternary relation?
  4. Mar 19, 2012 #3
    Dear Stephen,

    Thank you very much for your reply.

    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.

    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.

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

    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:

    Relations are:

    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.
  5. Mar 19, 2012 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.)
  6. Mar 20, 2012 #5
    Dear Stephan,

    Thanks a lot for the reply.

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

    Yes, exactly.

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

    No, those kind of derivations are not required.

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

    Thank you very much
    Best regards
  7. Mar 20, 2012 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
  8. Mar 22, 2012 #7

    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
  9. Mar 24, 2012 #8

    Stephen Tashi

    User Avatar
    Science Advisor

  10. Mar 26, 2012 #9
    Dear Staphen,

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

    Kindest regards
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook