I've got a set S and a function f that maps every element of S to a subset of S.

I would like to describe a constraint on f which I call the "non-circularity" constraint. Informally, imagine choosing an element x

_{0}from set S. Then compute f(x

_{0}) and choose x

_{1}to be an element of

*that*set. Now do the same thing for x

_{2}(compute f(x

_{1}) and choose x

_{2}to be one of its elements). And so on and so forth. The non-circularity constraint says that no matter what x

_{n}values you choose, you will never get back to x

_{0}. And this is true for all x

_{0}values.

*Update 12/5 10am: One of the problems with this informal description is that it isn't clear what's supposed to happen if any of the f(x*

_{n})'s is the empty set (thanks**boojum**for pointing this out). My intention is that if f(x_{n}) is the empty set, it doesn't constitute a violation of the constraint. The chain of x_{n}'s just terminates.Now here's an attempt at a formal description:

(1) Let g be a function defined as follows: g(x) is equal to the union of f(x) with all the sets g(y) such that y is a member of f(x).

(2) The non-circularity constraint says that for all x, g(x) does not contain x.

Here's my question: is my formal description mathematically sound?

The computer scientist in me says "No. If the non-circularity constraint isn't met, then the computation of g(x) won't terminate. But the non-circularity constraint is defined in terms of g(x). If anyone ever gives us an f that doesn't satisfy the constraint, we'll go into an infinite loop trying to check it."

The mathematician in me says "Relax, guy! Nobody's talking about computing anything here. We're just defining mathematical functions; we don't need to worry about infinite loops. Besides, the whole point of a constraint is that it is always satisfied, ergo g(x) is well-defined, ergo the constraint can be verified."

Then there's another little voice inside me saying "What if the set S is infinite?"

## Error

You must follow the Privacy Policy and Google Terms of use.