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.
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 proving that his two properties hold with probability >1/2 over the distribution of random graphs on n vertices (for sufficiently large n), you _have_ proven that there exists at least one graph of order n with those properties. This is because the intersection of any two properties of measure > 1/2 has positive measure itself (simple inclusion exclusion argument) followed by applying the "tautological" statement I gave earlier.
This is the whole point of the probabilistic method! There are a finite number of graphs of order n - I don't know why you keep claiming that his proof relies on there being infinitely many graphs, when it's clear that the entire proof takes place in that (finite) set.
> We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here.
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.
This is incorrect. We really are picking from the (finite) set of graphs of order n. Erdos picks n carefully so that his properties have the desired probability, but it is fixed!
> 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.
This is not possible - as I have said, if a property holds with positive probability there is an element of the underlying space (i.e. a particular choice of graph of order n in this case) that satisfies it. If no element of your probability space satisfies P, then the probability that P holds is 0, basically by definition! This is extremely basic stuff - the measure of the empty set is always zero.
I think you really need to learn some mathematical probability theory to get this straight - you seem to be confused about basic definitions here. My question to you - can you define a random graph on n vertices rigorously? Can you define the probability of a property of a random graph of n vertices rigorously? Until you can do that we are just talking in circles - everything I'm saying follows easily (not tautologically) from those definitions.
I feel you are applying some intuitive conception of probability, which is leading you to misinterpret key parts of the proof. Everything here can be formalised precisely using measures and probability spaces, as Erdos himself absolutely knew.
Here is a good technical introduction to the probabilistic method, which verifies everything I've written (in the same language as I've used too, namely that of measures and probability spaces, which is the standard in modern mathematics for formalising this stuff).
In particular, I quote:
> We would like to prove the existence of a combinatorial object with specified
properties. Unfortunately, an explicit construction of such a “good” object does
not seem feasible, and maybe we do not even need a specific example; we just
want to prove that something “good” exists. Then we can consider a random
object from a suitable probability space and calculate the probability that it
satisfies our conditions. If we prove that this probability is strictly positive,
then we conclude that a “good” object must exist; if all objects were “bad”,
the probability would be zero.
I also quote (emphasis mine):
> 1.1.2 Definition (Random graphs). 6 The probability space of random graphs G(n, p) is a finite probability space whose elementary events are all graphs
on a fixed set of n vertices.
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
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.