I think that what I wrote is implicitly agreeing with the GP that the induction argument is wrong not the base case. And I think that you attempted to refute it, but I couldn’t really understand how what you wrote would relate to either side. Do you mean that you agree that your description above was complicated, or that you agree that what I wrote is a fair description of the problem, or do you (now as opposed to before?) think that the problem was the induction step not the base case? Or are you talking about the statement that it is easy to miss the error by thinking of n as big rather than n=2? Maybe it doesn’t matter.
The argument in the article is the following: Given some function f, 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 doesn't apply to the base cases because anything is true for the empty set and any function on a one element set is trivially constant. So the minimal case where this can be applied in a non-trivial way is a set with 3 elements.
> The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c.
This is not the argument.
> This argument is valid only if A ⋂ B ≠ ∅.
No, it isn't; it isn't even valid then. Consider a function over sets of real numbers:
f([0,2]) = 5
f([1,3]) = 5
f([1,2]) = 5
f([0,3]) = 6
plus other values...
I've constructed this function so that, obviously, f(A) = f(B) = f(A ⋂ B) = 5, and A ⋂ B = [1,2] ≠ ∅, but f is not a constant function and f(A ⋃ B) is not 5. f is still a function.
We can state the proposition "in a group of N or fewer horses, all of the horses are the same color" like so:
∀G∃c∀x( (|G| ≤ N ∧ x ∈ G) → f(x) = c )
where f is the function that tells you what color a horse is, and N is a free variable.
The proof claims that if this proposition is true for the value N = k, then it is also true for the value N = k+1. This claim is correct for all k > 1, but it is not correct for k=1. The problem is that we only show the truth of the proposition for N=1.
Abstracting a little further, we can view the proposition above as the potential output of a function of N:
p(0) = ∀G∃c∀x( (|G| ≤ 0 ∧ x ∈ G) → f(x) = c )
p(1) = ∀G∃c∀x( (|G| ≤ 1 ∧ x ∈ G) → f(x) = c )
p(2) = ∀G∃c∀x( (|G| ≤ 2 ∧ x ∈ G) → f(x) = c )
p(3) = ∀G∃c∀x( (|G| ≤ 3 ∧ x ∈ G) → f(x) = c )
p(4) = ∀G∃c∀x( (|G| ≤ 4 ∧ x ∈ G) → f(x) = c )
We can now say that the proof is claiming that whenever p(k) is true, p(k+1) is also true, that this claim is correct for all k > 1, and that p(1) has been established. But p(2) has not.
> This claim is correct for all k > 1, but it is not correct for k=1. The problem is that we only show the truth of the proposition for N=1.
This is exactly what the person you are responding to was saying. They were talking about the transitive part of the inductive step that the article handwaves to with this line:
>> In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown.
the "remaining horses" is the A ⋂ B set that was mentioned and if that set is empty then know it is the same color as set A is meaningless. 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.
Given that in this case A and B are formed by removing different elements from a set of size n+1, the proof only works if n+1>=3 so that A ⋂ B can have at least one member.
> 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.
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.
> 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.
I think you just misunderstood the notation. f is a function from (say) X -> Y. But the parent talks about it as if it were a function from the power set P(X). That is, for A a subset of X, when the commenter above says that f(A) is a constant, they meant that f(A) = {c} for some c in X. This is a bit of loose usage of the standard notation f(A) := {f(a) : a in A} is commonly understood.
Obviously an arbitrary function f : P(X) -> … needn’t satisfy the properties but no one was suggesting that.
Under your interpretation, poetically's claim still does not reflect the claim from the false proof, and it is still itself obviously wrong.
(I'll assume that when you say "f(A) = {c} for some c in X", you mean "f(A) = {c} for some c in Y", since the values of f come from Y.)
So consider these definitions:
f(x) = x²
A = [0,1]
B = [-1, 1]
We can easily see that f(A) = f(B) = f(A ⋂ B) = A. But it is not true that f takes a constant value over any of those domains. (It is true that f(A ⋃ B) = f(A), but this is required by the premise f(A) = f(B).)
In your example f(A) is not a singleton. I think that the image f(A) being a singleton {c} is what was meant by “f(A) is some constant c”.
It feels to me like you are taking advantage of imprecise language to demonstrate counter-examples to statements that no one was trying to prove.
Do you actually think that 'poetically (or I) are trying to use obviously false properties of functions (specifically the properties you keep providing counter-examples to) or are just being nit-picky about language?
Usually I find much mathematical writing can be hard to read because much of the context or scope of variables, assumptions, or definitions is so implicit. But when something seems obviously wrong it is an exercise to figure out what constraint I’ve missed that makes it true.
When one first learns analysis, the statement of so many of the theorems begins “given a continuous function f” and this continues in formal writing but when people communicate more casually they usually just say function and everyone knows/figures that a continuous function is meant instead of pointing out an obvious counter-example.
In the context of this thread, it is obvious to me that the thing being talked about is when the image of a function restricted to some subset of the domain is a singleton. The reasons it is obvious to me are:
- The f(A) := {f(a) | a in A} notation is standard and implied by the choice of letters
- It is meaningless to say that the value of a function is constant—you always get the same result, so for the word to mean something, I think it is reasonable to take it as implying the restriction is a constant function, or in other words that f(A) = {c}, a singleton.
- It seemed obvious to me from the context of the article
- It seems a reasonable interpretation that changes the statements from nonsense into a reasonable description
At first I thought you just weren’t familiar with the notation, but now it seems you knew it so was it just not obvious to you that that is what was meant? Or do you actually think people were trying to prove or rely on the statements you disproved? Or that people should write more precisely and deserve to be punished with pedantry when they assume some mathematical maturity instead? I’m genuinely curious what you think is going on here because I’m struggling to fit these comments to a model of how hn commenters think and act.
> In your example f(A) is not a singleton. I think that the image f(A) being a singleton {c} is what was meant by “f(A) is some constant c”.
What? What are you quoting? Here's the full relevant text I responded to:
> The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c.
There is no claim (in the premises) that f is constant over A. There is such a claim in the conclusion, since that is a corollary of f being constant everywhere. But it's not in the premises.
So this is my model of what's happening:
- poetically has attempted to write down the claim of the false proof. He probably has a fair, if fuzzy, idea of what the proof is saying. But he doesn't know how to write it down; he has written down some things that sound kind of similar while, in the details, being mostly unrelated to the false proof. While I do believe that he broadly understands the OP, I do not believe that he understands the stuff he wrote down himself.
- You have a clear idea of what the proof is saying and you would like to read poetically as saying the same thing if at all possible. This is causing you to read things into poetically's claim that aren't there, but which would be necessary in order for him to be making sense. So it's unfair for me to use an example in which the image of A isn't a singleton, because, in the original post, the image of every set is a singleton. That the image of every set is a singleton is part of the inductive hypothesis. But in the claim attributed to the post, A is a set with no constraints on it, and f is a function with no constraints on it.
- At a wider level, poetically has described a post which contains a pretty clever false proof which is very nearly correct as instead making a claim which is so obviously incorrect that, if you believe poetically, it would make no sense to read the post.
So my initial thought process went like this:
1. Read poetically's comment. Notice that it is presented as a description of the argument in the post, but it makes no sense.
2. Leave a comment explaining how to describe the argument in the post.
This was a failure, in that poetically responded to the effect that he didn't see any difference between what he wrote and what I wrote.
In this subthread, you keep trying to provide interpretations that would cause poetically's original claim to make more sense, and I keep pointing out that the new interpretation doesn't help. In this case, the image of A being a singleton is most definitely not part of the original claim. But if I assume that it was, the adjusted claim still makes no sense. The new counterexample is:
f(x) = ⌊x⌋
A = [0.2, 0.6]
B = [0.4, 0.8]
This function is constant over A, B, and -- of necessity -- A ⋂ B. A ⋂ B is a nonempty set. But the function is not constant everywhere.
Moving back into the project of reading poetically's mind, I have to interpret his statement "This argument is valid only if A ⋂ B ≠ ∅" as an attempt to explain under what circumstances the argument he describes in the previous sentence is valid. This indicates a fairly serious error in understanding somewhere, because that argument is never valid. The observation that the intersection of A and B is or isn't empty has zero explanatory power.
(Note also that if you believe poetically was restricting himself to cases where the image of every set under consideration is a singleton, it doesn't make a lot of sense to describe for him to state his premise as "f(A) = f(B) = f(A ⋂ B)". When every image is a singleton, it's sufficient to say that "f(A) = f(B)". (And this is exactly how the false proof proceeds - it proves that f(A) = f(B) by observing that each is necessarily equal to f(A ⋂ B).) But this is fairly weak evidence; people bring up redundant information all the time.)
> At first I thought you just weren’t familiar with the notation, but now it seems you knew it so was it just not obvious to you that that is what was meant?
Yes, I'm familiar with that notation, and no, it wasn't obvious to me that that was what was meant. It still isn't, frankly. I cannot be confident about what was meant because there are no options that would make sense.
However, I will note that I don't think my response above indicates that I was familiar with the notation. You provided a definition and I used it while talking to you; I'm using "singleton" in this comment and that is a usage I was not previously familiar with.
This is incorrect. You attribute an argument to the article that it does not make.
> This argument is valid only if A ⋂ B ≠ ∅
This is vacuously true in that the argument is not valid and its validity therefore implies all propositions including that A ⋂ B ≠ ∅. Although I tend to suspect that that isn't what you meant to say. It is equally true that "This argument is valid only if A ⋂ B = ∅". It is not true that if a function f takes a constant value, you can conclude that A ⋂ B ≠ ∅ for arbitrary A and B.
