News for hackers. Stuff that matters.
Re:Russell's paradox and the Y combinator by theVirginian on Tuesday June 02, 2015 @06:49PM (#9649537)
I found this description disjointed and difficult to read.
Re:Russell's paradox and the Y combinator by tel on Tuesday June 02, 2015 @07:35PM (#9649702)
It might be valuable to expand the definitions of things a bit.

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

    R x = N (x x)
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.

    (\x -> N (x x)) (\x -> N (x x))
and the author notes that this is the same form as the Y-combinator with its first argument specialized to N.

    Y f = (\x -> f (x x)) (\x -> f (x x))
    Y N = R R
And there we go!
Re:Russell's paradox and the Y combinator by jameshart on Tuesday June 02, 2015 @08:46PM (#9649957)
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'?
Re:Russell's paradox and the Y combinator by srtjstjsj on Tuesday June 02, 2015 @08:14PM (#9649858)
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.
Re:Russell's paradox and the Y combinator by tel on Tuesday June 02, 2015 @11:35PM (#9650413)
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.
Re:Russell's paradox and the Y combinator by mpu on Tuesday June 02, 2015 @07:05PM (#9649591)
I'm not a native speaker, I'm sorry you had trouble going through it. I tried to keep it short but maybe did not articulate the first paragraph and the end of the second ideally.

Hopefully, you understood the core idea.

Re:Russell's paradox and the Y combinator by mkehrt on Tuesday June 02, 2015 @07:12PM (#9649618)
I thought it was clear and concise, but I am familiar with both concepts.
Re:Russell's paradox and the Y combinator by theVirginian on Tuesday June 02, 2015 @09:26PM (#9650075)
Sorry to be negative, I did get through it but the end of the second was where I had to stop for a second.
Re:Russell's paradox and the Y combinator by triplesec on Tuesday June 02, 2015 @07:24PM (#9649666)
minor edit for you since you're not English: it's Russell's Paradox. It's amazing how much going along with accepted spelling conventions helps people like a piece, especially a short one. Good luck!
Re:Russell's paradox and the Y combinator by banachtarski on Tuesday June 02, 2015 @07:06PM (#9649593)
You were potentially not in the intended audience.