So to translate that back into natural language, R R asks 'does the set of sets which don't contain themselves contain itself?', and the answer, 'Y N' reads, 'why not'?
How is this example special, compared to the general notion:
F = (\x -> Z (x x))
Y f = (\x -> f (x x)) (\x -> f (x x))
Y Z = F F
so, any set F that is defined in terms of how sets (functions) relate to themselves, fits into the Y combinator. Which is expected, since Y is the essence of recursion.I don't know that there's anything special about Russell's paradox in particular, to be honest. It has obvious historical importance, obviously, but I doubt that's what you're looking for.
There's something a bit remarkable about how trivial it is, I suppose. Booleans are very simple types, if you'll give me those, and then Not is the only involution!
Re:Russell's paradox and the Y combinator
by theVirginian on Tuesday June 02, 2015 @09:29PM
(#9650082)
Ahh.. thank you. We touched on this in philosophy courses but my specific courses did not cover it in depth. Thank you for explaining the notation for me.
First, we talk about characteristic functions. As noted, they are merely functions which return either 1 or 0, True or False. They represent sets by examining their argument and returning True if and only if the set they represent contains that thing.
So, if x is a characteristic function and (x x) is True, then x "contains" itself. Then N is just negation, so if N (x x) is True then x does not "contain" itself. That much is simple.
Now we form a special new characteristic function, R, defined as
When is (R x) True? Exactly when x is "contained" in R. When does that happen? When N (x x), e.g., when x does not "contain" itself.So this is a well-defined characteristic function and therefore represents what we might think is a well-defined set.
But what happens when we check (R R), i.e. to see if R contains itself?
Well, R, by definition, contains all things which are not members of themselves. If R is in R then (R R) is True, but then N (R R) is False and (R R) = False. Contradiction!
We can inline R into (R R) in order to take a look at the functional form.
and the author notes that this is the same form as the Y-combinator with its first argument specialized to N. And there we go!