If both sets we're comparing are well-founded (i.e., they don't contain links back to themselves), then we say they are equal iff they have the same elements. It's not hard to write a recursive function that tests this (pseudocode):
Code: Select all
if A and B are primitives: return (A==B)
if A is a set and B is a primitive, or vice-versa: return False
if A and B are sets:
for all x in A:
if not(∃y∈B: equals(x,y)): return False
else: remove x from B
if B is nonempty: return False
else: return True
But what if the sets are not well-founded? Then the above procedure will never finish, but we can still understand an intuitive notion of equality. (The following definition might not be completely rigorous, but I think you'll understand what I'm getting at here.)
- If A and B are both primitives or well-founded sets, use the above definition.
- If A is a primitive or well-founded set, and B is a non-well-founded set (or vice-versa), then A≠B.
- If A and B are both non-well-founded sets, then A=B iff it is possible to assume that A=B without contradicting (1) and (2).
So, the question is, what's the best algorithm to test for equality, without ending up in an infinite loop?