3 ms·

We're not talking about different things. We're talking about one very specific claim that you made: > if something exists with non-zero probability in a finit

by feoren 2y ago

We're not talking about different things. We're talking about one very specific claim that you made: > if something exists with non-zero probability in a finite set there has to be at least one example This is a false claim. See my #1 through #4 above. I strongly suspect if you carefully re-read those Erdos papers, you'll discover that he never relies on my #2 or #3 above to prove anything; only #1 and #4.

deleted 2y ago
[deleted]
bubblyworld 2y ago
If a property P holds over a sample space with positive probability (i.e. the measure of the subset of elements satisfying P is positive), this implies that there is at least one element of the sample space satisfying P. This is easy to prove - it follows formally from sigma-additivity of the measure. I think you are confusing this with the notion of taking repeated samples from a probability distribution (which is what your coin example is all about).
- feoren 2y ago
  > i.e. the measure of the subset of elements satisfying P is positive Question: do any finite sets ever have positive (nonzero) measure? If not, then your sample space is infinite and you're in #4. Haven't you just restricted our conversation only to infinite sets via this assumption? Remember that this entire discussion started because of your claim about finite sets!
  - bubblyworld 2y ago
    That depends on the measure, obviously. It's trivial to construct examples in which finite sets have positive measure - just take the uniform probability distribution over a finite set. Or for a more thematic example, the probability space of random graphs on n vertices. Or really any finite measure you like! There are also myriad examples of measures over infinite spaces in which there exist finite sets with positive measure - left as an exercise to the reader. I don't mean this to be rude, but I think you would benefit from reading an undergraduate level textbook on probability theory (or measure theory). Especially before making confident claims about people like Erdos are wielding it.
    - feoren 2y ago
      I really, really think you are misunderstanding what makes Erdős's proof work in the second example in your Wikipedia link. It really has nothing to do with measure, and relies entirely on showing that there is an infinite set of graphs that all have probability at least 1/2 to have two properties. The proof simply would not work if all of those conditions were not there (I think we're both confident that Erdős did not include superfluous conditions in his proofs!) "Measure" is not mentioned at all. I obviously don't know the intricate details of every possible measure that could be defined, but I strongly suspect that no matter what measure you pick, the following statement is utterly tautological: "If the set { x ∈ S | P(x) } has measure > 0, then there must exist some y in S s.t. P(y)". You're really just saying: if we can show that the subset of elements in S with property P contains at least one element, then S must also contain that element. Of course! It's a subset of S! It's tautological, and I don't believe Erdős threw in tautological steps in his proofs. You are misunderstanding what the proof step is. We're talking about the Second example in this link: https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikipedia.org/wiki/Probabilistic_method It's structured like this: "Let n be very large and consider a random graph G on n vertices ... we show that with positive probability, G satisfies two properties." Let me ask: how are we mathematically certain there exists a graph G that satisfies the two properties? (And we are; the proof is correct.) Which of the 4 situations are we in? Your focus on finite sets makes it sound like we're in #3: finite set, nonzero probability. And indeed the set of random graphs with n vertices is finite! But that is an important mistake. We are not relying on argument #3. Yes, the set of random graphs with n vertices is finite, but we have NOT proven that any specific G has our two properties, and we have NOT proven that any graph with n vertices has those two properties! It's entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties. You might encounter a similar proof, exactly the same up to this point, and that proof might be wrong! So why does Erdős's proof work? It relies on two things that are both necessary: (1) we're not talking about a finite set at all! We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here. Our smallest example might be of size 10^10^10^n! We don't know! We just know that if we keep going, eventually we must hit one. And, critically, (2) there is a positive lower bound on the probability, above some n (it's 1/2). That is, if the probability of a random subgraph having those two properties was some small nonzero probability that decreased as n increased, e.g. p ~ 1/n^2, then we still might never find an example! The proof could be incorrect! But it's shown that above some n, the probability is at least 1/2. Thus the whole proof works, because 1 - (1/2)^inf = 1. The sum of existence probabilities over all possible examples (infinite) is 1. QED. So in summary, this statement: > If a property P holds over a sample space with positive probability (i.e. the measure of the subset of elements satisfying P is positive), this implies that there is at least one element of the sample space satisfying P. is either false or tautological. If "positive probability" means proving that some elements in a finite sample space have a positive probability of satisfying P, you have not proven existence. You need to show that the sum of "existence probabilities" of all your examples is 1. Showing a positive probability on an infinite set does this (unless the sum of probabilities over all infinite examples somehow converges to a number < 1, e.g. if p ~ 1/n^2 above). If "positive measure" means "we've proven such a thing exists", then it's tautological. All you've said is "if you can prove something exists in a subset of S, then it also exists in S." I guarantee you Erdős did not include such unnecessary tautologies in his proofs.

by feoren 2y ago

deleted 2y ago

[deleted]

bubblyworld 2y ago

If a property P holds over a sample space with positive probability (i.e. the measure of the subset of elements satisfying P is positive), this implies that there is at least one element of the sample space satisfying P. This is easy to prove - it follows formally from sigma-additivity of the measure. I think you are confusing this with the notion of taking repeated samples from a probability distribution (which is what your coin example is all about).

feoren 2y ago
> i.e. the measure of the subset of elements satisfying P is positive Question: do any finite sets ever have positive (nonzero) measure? If not, then your sample space is infinite and you're in #4. Haven't you just restricted our conversation only to infinite sets via this assumption? Remember that this entire discussion started because of your claim about finite sets!
- bubblyworld 2y ago
  That depends on the measure, obviously. It's trivial to construct examples in which finite sets have positive measure - just take the uniform probability distribution over a finite set. Or for a more thematic example, the probability space of random graphs on n vertices. Or really any finite measure you like! There are also myriad examples of measures over infinite spaces in which there exist finite sets with positive measure - left as an exercise to the reader. I don't mean this to be rude, but I think you would benefit from reading an undergraduate level textbook on probability theory (or measure theory). Especially before making confident claims about people like Erdos are wielding it.
  - feoren 2y ago
    I really, really think you are misunderstanding what makes Erdős's proof work in the second example in your Wikipedia link. It really has nothing to do with measure, and relies entirely on showing that there is an infinite set of graphs that all have probability at least 1/2 to have two properties. The proof simply would not work if all of those conditions were not there (I think we're both confident that Erdős did not include superfluous conditions in his proofs!) "Measure" is not mentioned at all. I obviously don't know the intricate details of every possible measure that could be defined, but I strongly suspect that no matter what measure you pick, the following statement is utterly tautological: "If the set { x ∈ S | P(x) } has measure > 0, then there must exist some y in S s.t. P(y)". You're really just saying: if we can show that the subset of elements in S with property P contains at least one element, then S must also contain that element. Of course! It's a subset of S! It's tautological, and I don't believe Erdős threw in tautological steps in his proofs. You are misunderstanding what the proof step is. We're talking about the Second example in this link: https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikipedia.org/wiki/Probabilistic_method It's structured like this: "Let n be very large and consider a random graph G on n vertices ... we show that with positive probability, G satisfies two properties." Let me ask: how are we mathematically certain there exists a graph G that satisfies the two properties? (And we are; the proof is correct.) Which of the 4 situations are we in? Your focus on finite sets makes it sound like we're in #3: finite set, nonzero probability. And indeed the set of random graphs with n vertices is finite! But that is an important mistake. We are not relying on argument #3. Yes, the set of random graphs with n vertices is finite, but we have NOT proven that any specific G has our two properties, and we have NOT proven that any graph with n vertices has those two properties! It's entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties. You might encounter a similar proof, exactly the same up to this point, and that proof might be wrong! So why does Erdős's proof work? It relies on two things that are both necessary: (1) we're not talking about a finite set at all! We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here. Our smallest example might be of size 10^10^10^n! We don't know! We just know that if we keep going, eventually we must hit one. And, critically, (2) there is a positive lower bound on the probability, above some n (it's 1/2). That is, if the probability of a random subgraph having those two properties was some small nonzero probability that decreased as n increased, e.g. p ~ 1/n^2, then we still might never find an example! The proof could be incorrect! But it's shown that above some n, the probability is at least 1/2. Thus the whole proof works, because 1 - (1/2)^inf = 1. The sum of existence probabilities over all possible examples (infinite) is 1. QED. So in summary, this statement: > If a property P holds over a sample space with positive probability (i.e. the measure of the subset of elements satisfying P is positive), this implies that there is at least one element of the sample space satisfying P. is either false or tautological. If "positive probability" means proving that some elements in a finite sample space have a positive probability of satisfying P, you have not proven existence. You need to show that the sum of "existence probabilities" of all your examples is 1. Showing a positive probability on an infinite set does this (unless the sum of probabilities over all infinite examples somehow converges to a number < 1, e.g. if p ~ 1/n^2 above). If "positive measure" means "we've proven such a thing exists", then it's tautological. All you've said is "if you can prove something exists in a subset of S, then it also exists in S." I guarantee you Erdős did not include such unnecessary tautologies in his proofs.