Wikipedia:Reference desk/Archives/Mathematics/2014 June 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 17

Set of descendents of a set in ZF

Pulling a more manageable chunk off one of my previous questions, I would like to understand how the set of all descendants (by membership) of an arbitrary set can be exhibited in ZF. It seems like this should be possible, but I am running into some confusion when I try to nail it down. It seems like the only way to specify a new set that is not a simple combination of powersets etc is to write out a first-order sentence describing it, but I am uncertain how predicate symbols are attached to definitions. For instance, in order to identify the set of nth-level descendents of x, is it valid to define a property P(n,a,x) := (n=0&a=x)||EkEb(n=k+1 & a=union(b) & P(k,b,x)) ? The recursive part seems like it might be a problem, but I'm not sure. Black Carrot (talk) 22:31, 17 June 2014 (UTC)

The recursive part can be shown not to be a problem; a simple way of resolving it is as follows:

$P(n,a,x){\overset {\underset {\mathrm {def} }{}}{=}}(\exists f)({\mathcal {D}}(f)=n+1\wedge f(0)=x\wedge f(n)=a\wedge (\forall m<n)(f(m+1)=\cup f(m)))$

— Arthur Rubin (talk) 23:49, 17 June 2014 (UTC)

At least that works in vNBG; the precise use of separation and replacement to get it to work in ZF may be more complicated. — Arthur Rubin (talk) 23:57, 17 June 2014 (UTC)

I'm not sure what you mean "works in NBG". It's expressed in the first-order language of set theory, same as ZF, so whether it works or not does not depend on the theory. (Proving it works is another matter, of course.) --Trovatore (talk) 01:22, 18 June 2014 (UTC)

I don't understand that. If f is a function variable, how can we quantify over it in first order logic? And what is D? Also, I'm uncertain how the symbol < can be defined without running into the same problem. Black Carrot (talk) 14:13, 18 June 2014 (UTC)

It's quite easy to express "f is a function" in the first-order language of set theory. You just say every element of f is an ordered pair, and given any two elements of f, call them (x,y) and (z,w), if x=z, then y=w. --Trovatore (talk) 16:26, 18 June 2014 (UTC)

The difficulty I see is in proving that the "set of descendents" is a "set". In vNBG, by that theory's version of "class comprehension", it's clearly a "class".

${\mathcal {D}}(f)$ is the domain of f.

As for "<", there are two simple approaches.

1. Using the Von Neumann definition of ordinals, "<" can be replaced by "∈".
2. Alternatively, we can use any explicit representation of the natural numbers N = <N,<_N>, and replace "m < n" by "m ∈ N : m <_N n"

— Arthur Rubin (talk) 17:17, 19 June 2014 (UTC)

That's a different way of phrasing it, as whether it is a set or a class, but I think it comes down to the same thing. What reason do you see, though, to say it is a proper class? Also, the Cartesian product construction of a function will not work if we don't know whether the range is a set, which is the exact thing I want to prove. Black Carrot (talk) 22:44, 19 June 2014 (UTC)

These are just minor "programming difficulties", as it were. The transitive closure of a (wellfounded) set is easily proved to be a set. I can't be arsed to come up with the exact proof at the moment, but just note that the rank of the transitive closure is no higher than the rank of the set itself, and then figure out the details. --Trovatore (talk) 23:02, 19 June 2014 (UTC)

Or, using using theorem 4.3.1 of my mother's book(Jean E. Rubin (1967). Set Theory for the Mathematician. Holden-Day. LCCN 67-13848.) in NBGU-, rewritten changing the class function F to a proposition φ:

$(\forall x)(\exists !y)\phi (x,y)\vdash (\forall u)(\exists !f)(Func(f)\&{\mathcal {D}}(f)=\omega \&f(0)=u\&(\forall n\in \omega )(\phi (f(n),f(n+1)))$

As I don't have a basic set theory book using ZF, I'm not sure how difficult it is to prove in ZF. — Arthur Rubin (talk) 01:10, 22 June 2014 (UTC)

Hexadecimal

Just a heads-up for those who frequent this page, there is a post over at the computing reference desk pertaining to mathematics as well. It's probably best to keep the discussion centralized, so you're welcome to comment there if you feel you have something to add. Kurtis ^(talk) 23:37, 17 June 2014 (UTC)