5 ms·

Yes, I did indeed mean finite. I was referring to the probabilistic method in combinatorics (https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikip

Yes, I did indeed mean finite. I was referring to the probabilistic method in combinatorics (https://en.wikipedia.org/wiki/Probabilistic_method https://en.wikipedia.org/wiki/Probabilistic_method). It's a non-constructive technique for proving existence theorems. Of course, this kind of thing works for infinite sets too, but there are some subtleties when it comes to sets of measure zero that kind of obscure the point.

feoren 2y ago
> Yes, I did indeed mean finite. Then you're wrong. I gave you a counterexample to your statement, which you have ignored. If you care about being correct on this, you should ruminate on my comments, because what you are currently saying is wrong. > Probabilistic method Neither example on that Wikipedia page shows proving the existence of something from a finite set because it's probability is non-zero. The first example is actually showing that if the probability is zero from a finite set then there can be no examples. It's an example of #4 below. The critical point is "The number of monochromatic r-subgraphs... is a non-negative integer, hence it must be 0 (if strictly less than 1)." It's the inverse of your statement (and the contrapositive of mine, hence it has the same truth value): "if the probability of something existing in a finite set is 0, there must be no examples". That's very different! The second example is from an infinite set. It's an example of #1 below The key sentence is: "For sufficiently large n, the probability that a graph has both properties is positive". We're given g and k as parameters to the problem, and we show that there exists some n, above which the probability of a random graph having the property we want is greater than 0. It is NOT proven that the graph we're looking for has exactly n vertices! It's only proven that random graphs of at least n nodes have a positive probability to have the property. The reason the proof works is because there are infinite numbers larger than n! It shows that there are infinite graphs that have non-zero probability to have the property we're looking for, and therefore at least one must actually exist. Here's a list. Your incorrect claim is counter to #3. 1. Infinite set, nonzero probability: we know at least one example must exist. 2. Infinite set, zero probability: not sure! It could be zero, or any subset of smaller cardinality or measure zero. 3. Finite set, nonzero probability: not sure! It could be zero! My coin flip example shows this. 4. Finite set, zero probability: we know no examples can exist.
- bubblyworld 2y ago
  Look, I'm not going to argue about this because we're talking about completely different things. Read up on the probabilistic method if you're genuinely interested in what I wrote - Paul Erdos has some famous papers on it.
  - 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!
        2y ago

feoren 2y ago

> Yes, I did indeed mean finite. Then you're wrong. I gave you a counterexample to your statement, which you have ignored. If you care about being correct on this, you should ruminate on my comments, because what you are currently saying is wrong. > Probabilistic method Neither example on that Wikipedia page shows proving the existence of something from a finite set because it's probability is non-zero. The first example is actually showing that if the probability is zero from a finite set then there can be no examples. It's an example of #4 below. The critical point is "The number of monochromatic r-subgraphs... is a non-negative integer, hence it must be 0 (if strictly less than 1)." It's the inverse of your statement (and the contrapositive of mine, hence it has the same truth value): "if the probability of something existing in a finite set is 0, there must be no examples". That's very different! The second example is from an infinite set. It's an example of #1 below The key sentence is: "For sufficiently large n, the probability that a graph has both properties is positive". We're given g and k as parameters to the problem, and we show that there exists some n, above which the probability of a random graph having the property we want is greater than 0. It is NOT proven that the graph we're looking for has exactly n vertices! It's only proven that random graphs of at least n nodes have a positive probability to have the property. The reason the proof works is because there are infinite numbers larger than n! It shows that there are infinite graphs that have non-zero probability to have the property we're looking for, and therefore at least one must actually exist. Here's a list. Your incorrect claim is counter to #3. 1. Infinite set, nonzero probability: we know at least one example must exist. 2. Infinite set, zero probability: not sure! It could be zero, or any subset of smaller cardinality or measure zero. 3. Finite set, nonzero probability: not sure! It could be zero! My coin flip example shows this. 4. Finite set, zero probability: we know no examples can exist.

bubblyworld 2y ago
Look, I'm not going to argue about this because we're talking about completely different things. Read up on the probabilistic method if you're genuinely interested in what I wrote - Paul Erdos has some famous papers on it.
- 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!
      - 2y ago