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

`function equals(A,B):`

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?