Paul Berry (stereotype441) wrote,
Paul Berry

Set theory question

Anyone know anything about set theory? I'm having a bit of a mental block.

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 x0 from set S. Then compute f(x0) and choose x1 to be an element of that set. Now do the same thing for x2 (compute f(x1) and choose x2 to be one of its elements). And so on and so forth. The non-circularity constraint says that no matter what xn values you choose, you will never get back to x0. And this is true for all x0 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(xn)'s is the empty set (thanks boojum for pointing this out). My intention is that if f(xn) is the empty set, it doesn't constitute a violation of the constraint. The chain of xn'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?"
  • Post a new comment


    default userpic