Hacker News Reader

Comment by ColinWright | Hacker News Reader

I'm a mathematician, and sometimes I need to assess the level at which I'll pitch an explanation. Although I don't do this in a setting where it's possible to set a test, as such, I do ask this question:

    An equivalence relation is reflexive, symmetric, and
    transitive.  If E is an equivalence relation, and we
    know E(x,y) but we know !E(y,z), what do we know
    about E(x,z), and why?

It seems a great filter for people who can think and reason formally, as opposed to using intuition based on their understanding of the words.

Edited in response to lmm's perfectly reasonable question. In context I would see if they just assumed they knew what I meant, or asked for clarification. If they assumed they knew what I meant, it would be interesting to see what interpretation they used. This is like FizzBuzz - it shouldn't stop with the first draft of the code - it's an opening for discussion.

View on HN

"we know not" seems like an unfairly trapped way of phrasing that question; it's not entirely clear that you mean "we know !E(y,z)" rather than "we don't know anything about E(y,z)".

I would definitely reason intuitively to solve this question, rather than formally. When I see E(x,y) I paint a picture in my head putting x and y in the same equivalence class:

    =======
    | x y |
    =======

When I see !E(y,z) I put a picture in my head where z is outside of the equivalence class of y (and x):

    =======    =====
    | x y |    | z |
    =======    =====

Hence we can conclude that !E(x,z). So while this is a nice question, I don't think it achieves your goal of testing formal as opposed to intuitive reasoning.

You know about equivalence classes and know to apply them. You can reason about partitions rather than needing to drop down the the level of logical implications (higher level abstractions for the win). If you remove the "think" part and become a little bit more assertive, your intuition becomes a proof.

You pass.

How often do you get people who apply but cannot pass that test? I always felt that CS gets a pretty large influx of people who are very fresh to programming (as isn't everyone!) but I would have thought a math fizz buzz would need to be harder to get signal.

Re: E(x,z) is false (or !E(x,z)). Otherwise we would have E(y,z) given that E(y,x), that's a contradiction.

I'm not a mathematician, but it looks to me like we know E(x,z) is false. The transitive property gives us

    E(x,y) & E(y,z) => E(x,z)

but since we know !E(y,z), we can infer !E(x,z).

(I'm not a logician, either, so I hope you'll excuse what may be imprecise phrasing on my part.)

Your result is correct but your reasoning is not sound. A & B => C and !B does not imply !C.

Well, I already admitted I'm not a logician: if A & B => C, (!A | !B) => !C looks implicit to me, and while this isn't the first time I've had my nose rubbed in the fact that it's not, I never could understand why not.

That's the same as [ A => B ] and therefore [ !A => !B ]. This can easily be shown to be an invalid inference by instantiating A and B appropriately.

  A = "It's Raining"
  B = "Water is falling from the sky"

The first is clearly true. If it's raining, then water is definitely falling from the sky. The second is clearly false. Just because water is falling from the sky, that does not necessarily mean that it's raining.

You can probably invent your own, somewhat more humorous examples.

Just because A & B get you C doesn't mean that having A and B is the only way to get to C.

So you can't conclude that because you don't have A or B you don't have C.

It's like saying "Going down the A20 and the M20 (roads in the UK) gets you to Rochester (I've no idea if it does). I've not been down the A20 or the M20, thus I'm not in Rochester." The second sentence there isn't really valid, maybe you took a different route.

When !E(y,z), then also !E(z,y) (because symmetry). Also, E(y,x).

Thus !E(x,z), because E(y,x) and E(x,z) would imply E(y,z), which is false.

x is "near" y and y is near x. y is not near z, so z is not near y, and therefore z is not near x nor is x near z.

Bad example. "Near" is not an equivalence relation. Every step you make keeps you near where you were, but you can eventually get thousands of miles away.

Reply on news.ycombinator.com