# Set Membership Cycles: The Axiom of Regularity in ZF Set Theory.

Show 40 post(s) from this thread on one page
Page 1 of 6 12345 ... Last
• July 16th 2010, 10:50 AM
Ackbeet
Set Membership Cycles: The Axiom of Regularity in ZF Set Theory.
Wow, this thread-starting business is pretty heady stuff. I've got a real-world application of the axiom of regularity (in ZF Set Theory). In an inventory database of parts, where we allow assemblies of parts, I need an algorithm to check that no-one inadvertently entered a part as part of itself in an assembly, or as a part of a part that is in the first part, etc. In other words, we can't have any membership cycles. We don't allow $A_{1}\in A_{2}\in\dots\in A_{n}\in A_{1},$ for any n.

It struck me that this problem is precisely what the axiom of regularity is trying to avoid in ZF set theory. I will quote that axiom here, as it appears in Suppes' Axiomatic Set Theory (for some reason, the ampersand AND isn't working, so I'll use the \land symbol):

$A\not=0\to(\exists x)[x\in A\,\land\,(\forall y)(y\in x\to y\not\in A)].$

So I interpret this to mean that for any nonempty set, any elements of A cannot themselves have any elements in common with A. So here's my algorithm for implementing this check in my database:

Code:

boolean checks_out = TRUE;
For each assembly A[i]:
For each immediate component part x of A[i]:
For each immediate component part y of x:
If y in A[i] Then set checks_out = FALSE;
End For
End For
End For
Return checks_out;

Let's say I run that algorithm on the following assembly data:

A consists of parts B, C, D, and E.
B in turn consists of F, G, and H.
H in turn consists of I, J, K, and A (here’s the oops).

Where would this algorithm flag the error? Well, you’d start with A. Its components are B, C, D, and E. Loop through each of those.
For B, it checks out that F, G, and H are not components of A.
For C, there are no components. Done.
For D, there are no components. Done.
For E, there are no components. Done.

The next assembly is B. Loop through its components.
For F, there are no components. Done.
For G, there are no components. Done.
For H, it checks out that I, J, K, and A are not components of B.

Here the algorithm stops, and it didn't flag the error.

So here's my question: does my algorithm really implement the check I need? Does it check to make sure the axiom of regularity is followed? Or do I need to alter it in some way? If so, how?
• July 16th 2010, 10:00 PM
Failure
Quote:

Originally Posted by Ackbeet
Wow, this thread-starting business is pretty heady stuff. I've got a real-world application of the axiom of regularity (in ZF Set Theory). In an inventory database of parts, where we allow assemblies of parts, I need an algorithm to check that no-one inadvertently entered a part as part of itself in an assembly, or as a part of a part that is in the first part, etc. In other words, we can't have any membership cycles. We don't allow $A_{1}\in A_{2}\in\dots\in A_{n}\in A_{1},$ for any n.

It struck me that this problem is precisely what the axiom of regularity is trying to avoid in ZF set theory.

But note that the axiom of regularity must not only prevent the element relation from having cycles but must also prevent it from having infinite descending chains.

Quote:

I will quote that axiom here, as it appears in Suppes' Axiomatic Set Theory (for some reason, the ampersand AND isn't working, so I'll use the \land symbol):

$A\not=0\to(\exists x)[x\in A\,\land\,(\forall y)(y\in x\to y\not\in A)].$

So I interpret this to mean that for any nonempty set, any elements of A cannot themselves have any elements in common with A.
There is a quantifier $\forall A$ here (even though it is only a quantifier in the meta-language that is being used). Thus, in combination with the other axioms of set theory, you get something more powerful than your implementation (below) provides, I think.

Quote:

So here's my algorithm for implementing this check in my database:

Code:

boolean checks_out = TRUE;
For each assembly A[i]:
For each immediate component part x of A[i]:
For each immediate component part y of x:
If y in A[i] Then set checks_out = FALSE;
End For
End For
End For
Return checks_out;

Let's say I run that algorithm on the following assembly data:

A consists of parts B, C, D, and E.
B in turn consists of F, G, and H.
H in turn consists of I, J, K, and A (here’s the oops).

Where would this algorithm flag the error? Well, you’d start with A. Its components are B, C, D, and E. Loop through each of those.
For B, it checks out that F, G, and H are not components of A.
For C, there are no components. Done.
For D, there are no components. Done.
For E, there are no components. Done.

The next assembly is B. Loop through its components.
For F, there are no components. Done.
For G, there are no components. Done.
For H, it checks out that I, J, K, and A are not components of B.

Here the algorithm stops, and it didn't flag the error.
Frankly, I'm not surprised. Another way of testing for the component relation being acyclic would be to try to topologically sort all components with respect to the "is a component of" relationship: if that works it is acyclic, otherwise it isn't.
• July 16th 2010, 10:35 PM
Matt Westwood
Quote:

Originally Posted by Ackbeet
Wow, this thread-starting business is pretty heady stuff. I've got a real-world application of the axiom of regularity (in ZF Set Theory). In an inventory database of parts, where we allow assemblies of parts, I need an algorithm to check that no-one inadvertently entered a part as part of itself in an assembly, or as a part of a part that is in the first part, etc. In other words, we can't have any membership cycles. We don't allow $A_{1}\in A_{2}\in\dots\in A_{n}\in A_{1},$ for any n.

It struck me that this problem is precisely what the axiom of regularity is trying to avoid in ZF set theory. I will quote that axiom here, as it appears in Suppes' Axiomatic Set Theory (for some reason, the ampersand AND isn't working, so I'll use the \land symbol):

$A\not=0\to(\exists x)[x\in A\,\land\,(\forall y)(y\in x\to y\not\in A)].$

So I interpret this to mean that for any nonempty set, any elements of A cannot themselves have any elements in common with A. So here's my algorithm for implementing this check in my database:

Code:

boolean checks_out = TRUE;
For each assembly A[i]:
For each immediate component part x of A[i]:
For each immediate component part y of x:
If y in A[i] Then set checks_out = FALSE;
End For
End For
End For
Return checks_out;

Let's say I run that algorithm on the following assembly data:

A consists of parts B, C, D, and E.
B in turn consists of F, G, and H.
H in turn consists of I, J, K, and A (here’s the oops).

Where would this algorithm flag the error? Well, you’d start with A. Its components are B, C, D, and E. Loop through each of those.
For B, it checks out that F, G, and H are not components of A.
For C, there are no components. Done.
For D, there are no components. Done.
For E, there are no components. Done.

The next assembly is B. Loop through its components.
For F, there are no components. Done.
For G, there are no components. Done.
For H, it checks out that I, J, K, and A are not components of B.

Here the algorithm stops, and it didn't flag the error.

So here's my question: does my algorithm really implement the check I need? Does it check to make sure the axiom of regularity is followed? Or do I need to alter it in some way? If so, how?

An approach you may want to try is to define a structure as follows, which (where I work) I called a DAGNode (Directed Acyclic Graph Node):

a) ID
b) List of IDs of Parents
c) List of Children

Then create a map of ID to DAGNode.

Define a method "Add" which adds a new ID to the map as a DAGNode, which includes a) setting up the list of children of that DAGNode and b) searching through the children of existing DAGNodes for instances of this DAGNode.

If the ID is already in the tree, ignore it. Otherwise move on to the children etc. etc.

In the end you look to see that the node you first entered has no parent.

Are you at liberty to amend the implementation of your database to include a "Used in" field, that is, to list all the assemblies that a particular item is part of? Then you would have (in your DB) an instant indication of parents and children.

Check out:
Directed acyclic graph - Wikipedia, the free encyclopedia
for the page I used as a reference for doing precisely this sort of task.

What we now have is a collection of base classes (in java) which contain the essence of a DAG (although to match the immediate business requirements we called it a "hierarchy structure") and can be used for all implementations of this pattern.

We actually rolled this new s/w out on Thursday and (apart from a couple of easily-fixed backward compatibility issues) it worked first time. And it is considerably quicker than what we had earlier. And it took a couple of days to write and debug.
• July 16th 2010, 10:38 PM
Matt Westwood
Quote:

Originally Posted by Ackbeet
Wow, this thread-starting business is pretty heady stuff. I've got a real-world application of the axiom of regularity (in ZF Set Theory). In an inventory database of parts, where we allow assemblies of parts, I need an algorithm to check that no-one inadvertently entered a part as part of itself in an assembly, or as a part of a part that is in the first part, etc. In other words, we can't have any membership cycles. We don't allow $A_{1}\in A_{2}\in\dots\in A_{n}\in A_{1},$ for any n.

It struck me that this problem is precisely what the axiom of regularity is trying to avoid in ZF set theory. I will quote that axiom here, as it appears in Suppes' Axiomatic Set Theory (for some reason, the ampersand AND isn't working, so I'll use the \land symbol):

$A\not=0\to(\exists x)[x\in A\,\land\,(\forall y)(y\in x\to y\not\in A)].$

So I interpret this to mean that for any nonempty set, any elements of A cannot themselves have any elements in common with A. So here's my algorithm for implementing this check in my database:

Code:

boolean checks_out = TRUE;
For each assembly A[i]:
For each immediate component part x of A[i]:
For each immediate component part y of x:
If y in A[i] Then set checks_out = FALSE;
End For
End For
End For
Return checks_out;

Let's say I run that algorithm on the following assembly data:

A consists of parts B, C, D, and E.
B in turn consists of F, G, and H.
H in turn consists of I, J, K, and A (here’s the oops).

Where would this algorithm flag the error? Well, you’d start with A. Its components are B, C, D, and E. Loop through each of those.
For B, it checks out that F, G, and H are not components of A.
For C, there are no components. Done.
For D, there are no components. Done.
For E, there are no components. Done.

The next assembly is B. Loop through its components.
For F, there are no components. Done.
For G, there are no components. Done.
For H, it checks out that I, J, K, and A are not components of B.

Here the algorithm stops, and it didn't flag the error.

So here's my question: does my algorithm really implement the check I need? Does it check to make sure the axiom of regularity is followed? Or do I need to alter it in some way? If so, how?

While I think about it, I recall the last chapter of "The Joy Of Sets" by Keith Devlin, in which he investigates mathematical structures in which certain of the ZF axioms are relaxed, in particular the Law of Foundation. It turns out that "set theory" then turns magically into "graph theory"!

The latter concept (a "graph") is at base level a generalization of both a set and a relation.

So maybe completely rethinking your task as an exercise in graph theory may prove fruitful.
• July 16th 2010, 10:49 PM
undefined
Fun stuff!

Quote:

Originally Posted by Ackbeet
(for some reason, the ampersand AND isn't working, so I'll use the \land symbol):

Since & is a special symbol, you need to escape it with \, as in

$A\not=0\to(\exists x)[x\in A\,\&\,(\forall y)(y\in x\to y\not\in A)].$

Quote:

Originally Posted by Ackbeet
So I interpret this to mean that for any nonempty set, any elements of A cannot themselves have any elements in common with A.

I'm hoping not to embarrass myself since my experience here is limited, but this seems problematic. Consider the standard construction of the naturals, where for example 5 = {0,1,2,3,4} and 4 = {0,1,2,3}. It's clear that 4 is an element of 5, and that 3 is an element of both 4 and 5. I believe you changed the existential quantifier into a universal one.

Quote:

Originally Posted by Ackbeet
So here's my algorithm for implementing this check in my database:

Code:

boolean checks_out = TRUE;
For each assembly A[i]:
For each immediate component part x of A[i]:
For each immediate component part y of x:
If y in A[i] Then set checks_out = FALSE;
End For
End For
End For
Return checks_out;

...

So here's my question: does my algorithm really implement the check I need? Does it check to make sure the axiom of regularity is followed? Or do I need to alter it in some way? If so, how?

The algorithm does not accomplish what you want, as your counterexample shows. I believe it is due to the existential quantifier issue mentioned above.

If the only criterion is

Quote:

Originally Posted by Ackbeet
We don't allow $A_{1}\in A_{2}\in\dots\in A_{n}\in A_{1},$ for any n.

then there is the naive approach, just recursively check all elements of $\displaystyle A_i$, and all elements of elements of $\displaystyle A_i$, etc., for each $\displaystyle A_i$, either breadth-first or depth-first (I tend to find depth-first easier to code); this has the benefit of simplicity but seems inefficient. Perhaps better is to do a massive recursion, such that when checking $\displaystyle A_i$ as described just now, if $\displaystyle A_i$ has elements, then recurse on those elements as well, and keep a boolean array handy so you don't check the same component twice. Keep a list of parent nodes that you pass along recursively, and if you come across a child component that matches an element of your list, this indicates error. When you've finished the entire tree of $\displaystyle A_i$, you proceed to another element that has not been visited (according to your boolean array), until done. This might be reasonably efficient.

Edit: I only saw Matt Westwood's second post before, because I was at the end of the page; looking at his first post, our algorithms look pretty similar.
• July 17th 2010, 09:22 AM
Ackbeet
Thanks for all the replies. Let me reply to each one of them in turn.

Reply to Failure at Post #2:

You're correct in that the AoR is intended to eliminate infinite descending chains. In the database application, however, that's a moot point, since such a chain is physically impossible.

The forall quantifier is implicit in the axiom statement (which I have quoted exactly from Suppes), and explicit in my code (For each assembly A[i]). So I don't think the problem with my code is in that quantifier. But see below for my reply to undefined.

I'm not exactly sure what the phrase "topologically sort" means. Can you give an example, please?

Reply to Matt Westwood at Post #3:

What we're likely to have in the DB (of which structure, we do have control) is a table that would look like this:

Assembly Part
stack 1 cell 1
stack 1 cell 2
...
cell 1 screen 1
cell 1 screen 2
...

I doubt that the DB currently has hooks into each row for parent assemblies. But would you really need the parent info? If you think of this set membership thing as a directed graph, then you only need to go one way in order to determine if there is a cycle.

Reply to Matt Westwood at Post #4:

I agree that, possibly, thinking about the problem as an exercise in graph theory could be very fruitful. It will not, however, answer the question of why my algorithm seems to fail, or whether my algorithm even performs the check I'm trying to do. At a deeper level, perhaps, is a nagging question in my mind: is the AoR, as quoted from Suppes, adequate to prevent cycles? Problem 1 on page 56 of Suppes is to prove that $A\in B\in C\in A$ cannot occur for any three sets $A, B, C.$ It's not entirely clear to me why the AoR prevents this from happening, if it only checks two levels.

Reply to undefined at Post #5:

I understand that the ampersand has to be escaped. I was trying to use the \and symbol, which definitely works when I'm using TextPad/MiKTeX to do regular LaTeX typing. The \and symbol is equivalent to \&, but it inserts spaces before and after, which is really nice. On this forum, however, it does something really weird, where it splits up the line and puts the latter part first or something like that. Try it, and you'll see what I mean.

I'm confused as to which quantifier you claim I changed from existential to universal. Could you please clarify?

I agree that some sort of recursive tree-traversal would work, but that doesn't answer my question of why my algorithm doesn't seem to implement a check based on the AoR. If Suppes is correct, and ZF theory is correct, then the AoR prevents cycles. If my code does not prevent cycles, then it must be that my code doesn't implement the AoR check. What I would most like to see is where exactly my code fails to do that, and especially if there's a relatively easy way to fix it so that it does perform the AoR check.

Thanks for all the replies!
• July 17th 2010, 10:35 AM
undefined
Quote:

Originally Posted by Ackbeet
I understand that the ampersand has to be escaped. I was trying to use the \and symbol, which definitely works when I'm using TextPad/MiKTeX to do regular LaTeX typing. The \and symbol is equivalent to \&, but it inserts spaces before and after, which is really nice. On this forum, however, it does something really weird, where it splits up the line and puts the latter part first or something like that. Try it, and you'll see what I mean.

Thanks, didn't know that.

Quote:

Originally Posted by Ackbeet
I'm confused as to which quantifier you claim I changed from existential to universal. Could you please clarify?

I meant you seem to have interpreted

$A\not=0\to(\exists x)[x\in A\,\land\,(\forall y)(y\in x\to y\not\in A)]$

as

$A\not=0\to(\forall x)[x\in A\to(\forall y)(y\in x\to y\not\in A)]$

(I also had to change the \land to \to, which I didn't see before.)

Actually considering the changed quantifier and due to vacuous truth, the latter statement is logically equivalent to

$(\forall A)\bigg[(\forall x)[x\in A\to(\forall y)(y\in x\to y\not\in A)]\bigg]$

Quote:

Originally Posted by Ackbeet
I agree that some sort of recursive tree-traversal would work, but that doesn't answer my question of why my algorithm doesn't seem to implement a check based on the AoR. If Suppes is correct, and ZF theory is correct, then the AoR prevents cycles. If my code does not prevent cycles, then it must be that my code doesn't implement the AoR check. What I would most like to see is where exactly my code fails to do that, and especially if there's a relatively easy way to fix it so that it does perform the AoR check.

I suspect you are right that AoR can be used to check for membership cycles, but after spending more time, I'm not sure how to do it. I'm trying to apply the technique of this example in Wikipedia. Notice how the proof didn't apply AoR to the offending set itself, but to a set constructed from that set using another axiom (axiom of pairing). So likewise I think in the situation you outlined, where

A = {B,C,D,E}
B = {F,G,H}
C = 0
D = 0
E = 0
F = 0
G = 0
H = {I,J,K,A}

and hence $\displaystyle A \in H \in B \in A$, applying AoR to the given sets won't do anything (there will be no contradiction), rather we would have to strategically construct some set or sets so that AoR when applied to that will produce a contradiction.
• July 17th 2010, 01:42 PM
undefined
Oh okay, I think this works. See this subheading in the Wikipedia article. Define

$f(n) = \begin{cases} A & ,\ n \equiv 0\ (\text{mod}\ 3) \\ B & ,\ n \equiv 1\ (\text{mod}\ 3) \\ H & ,\ n \equiv 2\ (\text{mod}\ 3) \end{cases}$

where n ranges over the non-negative integers. This f cannot exist by AoR. Now, as to turning this into an algorithm, I'm not sure there is much to do besides using the graph-theory-type algorithm(s) already mentioned.
• July 20th 2010, 06:24 AM
Ackbeet
I'm afraid I don't understand your Post #8 at all. Care to clarify?

Reply to Post #7: It seems I have translated the existential to a forall: you're right.

Have you got any idea how to construct these sets on which we can check the AoR, and thus flag the contradiction?
• July 20th 2010, 07:30 AM
undefined
Quote:

Originally Posted by Ackbeet
I'm afraid I don't understand your Post #8 at all. Care to clarify?

Reply to Post #7: It seems I have translated the existential to a forall: you're right.

Have you got any idea how to construct these sets on which we can check the AoR, and thus flag the contradiction?

Well here is what's in Wikipedia:

~~~~~~~~~~~

"Suppose, to the contrary, that there is a function, f, on the natural numbers with f(n+1) an element of f(n) for each n. Define S = {f(n): n a natural number}, the range of f, which can be seen to be a set from the axiom schema of replacement. Applying the axiom of regularity to S, let B be an element of S which is disjoint from S. By the definition of S, B must be f(k) for some natural number k. However, we are given that f(k) contains f(k+1) which is also an element of S. So f(k+1) is in the intersection of f(k) and S. This contradicts the fact that they are disjoint sets. Since our supposition led to a contradiction, there must not be any such function, f.

"The nonexistence of a set containing itself can be seen as a special case where the sequence is infinite and constant."

~~~~~~~~~~~

So I was just defining an f so that we can reduce your example to a problem that's already been solved. Just so people don't have to scroll up and down, here's your example

A = {B,C,D,E}
B = {F,G,H}
C = 0
D = 0
E = 0
F = 0
G = 0
H = {I,J,K,A}

We have $\displaystyle A \in H \in B \in A$. This is a finite membership chain, but we could just as well write $\displaystyle \dots \in A\in H \in B \in A\in H \in B \in A$. So the f I defined matches the description in Wikipedia. Then we define S = {f(n): n a natural number} and proceed accordingly. My take on it was that rather than trying to explicitly implement AoR in an algorithm, we could just recognize that any finite membership chain implies an infinite membership chain, and proceed to look for finite chains through a tree parsing algorithm.

However, the Wikipedia argument can be adapted for finite chains, although it doesn't seem to produce an efficient algorithm. Here we just let S = {A, B, H}. We can check exhaustively that there is no element X in S that is disjoint from S (which follows from the membership chain).

1) A is not disjoint from S because B in A and B in S.
2) B is not disjoint from S because H in B and H in S.
3) H is not disjoint from S because A in H and A in S.
• July 20th 2010, 07:39 AM
Ackbeet
Aha! New algorithm, then:

Let S = {all assemblies}. Loop through each assembly, and check to see if any sub-assemblies of the current assembly are also in S. If the check returns negative for all assemblies, then the database is regular. How does that work? I think that would be relatively quick to implement.
• July 20th 2010, 07:55 AM
undefined
Quote:

Originally Posted by Ackbeet
Aha! New algorithm, then:

Let S = {all assemblies}. Loop through each assembly, and check to see if any sub-assemblies of the current assembly are also in S. If the check returns negative for all assemblies, then the database is regular. How does that work? I think that would be relatively quick to implement.

I see a problem with this: Suppose you have 52 components in your inventory, labeled a through z then A through Z. Then the number of assemblies is just the cardinality of the power set of {a, ... , Z} which is $2^{52} \approx 4.5 \cdot 10^{15}$ assemblies! And the only assembly that can safely be discarded is the empty set. Unless I've misunderstood something?
• July 20th 2010, 07:59 AM
Ackbeet
You're thinking of a theoretical realm of possible assemblies. However, in our little company here, we may accumulate maybe 10 new kinds of assemblies per year. We might have as many as 30 right now. I think with that real-world constraint, which I would agree is important, my new algorithm would be fairly efficient. What do you think?
• July 20th 2010, 08:39 AM
Failure
Quote:

Originally Posted by Ackbeet
You're thinking of a theoretical realm of possible assemblies. However, in our little company here, we may accumulate maybe 10 new kinds of assemblies per year. We might have as many as 30 right now. I think with that real-world constraint, which I would agree is important, my new algorithm would be fairly efficient. What do you think?

I wonder how this problem of circularity comes about if you cumulatively build your database of assemblies: as you know, the axiom of regularity captures some of the intuition that the universe of sets is (thought to be) built "cumulatively". So if you start with an initial database (universe) of assemblies that consists only of assemblies without components (i.e. "urelelements"), and if every time you add a new assembly to your database you make sure it is built only from assemblies that are already in the database, you will never ever get a cycle. So checking for circularity would not even be necessary.
• July 20th 2010, 08:45 AM
Ackbeet
Reply to Failure at Post #14:

That would be a fantastically easy way to check on circularity, I agree. However, it's not realistic for our database. Parts are not going to be entered in anything like a linear fashion. We may get new parts from one assembly back from the manufacturer at the same time as we're using its constituent parts in a new assembly. We can't count on any particular order being followed. What's more, that sort of linearity is actually undesirable for our database, because that would impose constraints on when we could enter parts into an assembly - not good from a tracking perspective.

If we didn't have these requirements, your suggestion would be a good one. It's rather akin to the insertion sort algorithm, in my mind.
Show 40 post(s) from this thread on one page
Page 1 of 6 12345 ... Last