Hacker News new | ask | show | jobs
by thaumasiotes 1654 days ago
> Thus given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you only know that f(A ⋃ B) is constant if A ⋂ B is non-empty.

But this is wrong. Given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you do not know that f is constant, regardless of whether A ⋂ B is or isn't a non-empty set. poetically described a completely different and obviously false claim instead of the actual claim made by the false proof.

1 comments

You must not understand the notation. f(A ⋂ B) = f(A) is saying that every result of f(A ⋂ B) is equal to every result of f(A), this is trivially true if A ⋂ B is the empty set and thus tells you nothing. However if A ⋂ B is not empty, it follows from knowing f(A) is constant.

Poetically is correctly identified the exact step when the n>1 assumption is introduced. The argument is condensed but accurate.

> if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This argument is valid only if A ⋂ B ≠ ∅.

It is very clearly the assumption that "all the remaining horses" is not empty that introduces the n>1 condition. It is the non emptiness of that set that allows you to say that since f(A) is constant and f(B) is constant (and we already know that because |A|=n and |B|=n), then f(A ⋃ B) is also constant.

You've gotten confused somewhere.

> However if A ⋂ B is not empty, it follows from knowing f(A) is constant.

That f(A) is constant is supposedly a conclusion, not a premise. It is not a valid conclusion to draw from the stated premises.

> f(A ⋂ B) = f(A) is saying that every result of f(A ⋂ B) is equal to every result of f(A)

As I just responded above, interpreting the claim this way doesn't get it to make any more sense. When f(A ⋂ B) = f(A), there is no basis from which to conclude that f is constant. You have no information about whether f is or isn't constant.

This is not the claim made in the false proof, nor does it have anything to do with the claim made in the false proof. It is a creation of poetically's own mind, and it makes no sense.

> You have no information about whether f is or isn't constant

You seem to have forgotten what we are talking about. A ⋃ B is an arbitrary set of horses of size n+1, A and B are subsets of A ⋃ B, each with a single different element removed and thus of size n. We already know that f() is constant over A and over B because they are of size n and we have assumed that all sets of horses of size n have the same color (which I already pointed out in my last comment.) We also know that f() is constant over A ⋂ B becasue it is a subset of sets we already know f() is constant over. The only thing that needs to be proven is that f() is constant over the set A ⋃ B. That proof is impossible if A ⋂ B is empty. We can only assert A ⋂ B is not empty if we assume that A ⋃ B must have a size of at least 3. From assuming n+1>=3 we are able to correctly conclude that n>1 implies the inductive step is valid.