[throwawaymath]

I don't like the phrasing the article used. The domain of the Collatz function is the set of positive natural numbers, which is countably infinite. Unless I'm misunderstanding the quote, it doesn't make sense to refer to percentages of infinite quantities.

In the formal sense of the term, "almost always" means that a property applies to all elements of an infinite set, with all exceptions comprising a subset with a smaller cardinality than the original set.

I usually see this term applied in the sense of measure theory, where the sets under study are uncountably infinite (or greater). Being that the naturals are countably infinite, the only way I can interpret this statement is that Tao has proven all but finitely many elements do not have an orbit terminating in 1 under the Collatz map.

Is that correct? If not, would someone mind clarifying the use of percentages here?

[ja3k]

You can make sense of a percentage of natural numbers with the concept of natural density: https://en.wikipedia.org/wiki/Natural_density

The natural density of a set is the limit as N goes to infinity of the proportion of the numbers up to N which are in the set.

For instance the natural density of primes, squares and cubes is 0 and the natural density of even numbers is 1/2. But all these sets are infinite so the same cardinality.

[throwawaymath]

Thank you, but your last sentence is not really correct. The concept of cardinality captures different sizes of infinity. This is why I mentioned countable and uncountable infinites upfront: a countably infinite set and an uncountably infinite set do not have the same cardinality, but both are infinite.

[Sniffnoy]

This is not correct.

I think your basic mistake here is thinking that sizes of infinite sets has to be measured by cardinality. Yes, that's one way, but usually not the most useful way; it's a very crude measure. Its only real advantage is the fact that it doesn't need any context to work. In most cases, though, more context-dependent measures of size are more appropriate.

For instance, typically, "almost everywhere" doesn't mean "except on a subset of smaller cardinality", it means "on a subset of measure 0".

It's easy to see why you might get these confused. In many of the typical cases of measure theory -- let's say R^n with Lebesgue measure for concreteness -- you're looking at a set of cardinality 2^(aleph_0), and any countable subset will have measure 0. (Indeed, any set of intermediate cardinality will also have measure 0, if such a thing exists, although famously the question of whether it does cannot be resolved.)

But you can also have subsets also of cardinality 2^(aleph_0) which nonetheless have measure 0. E.g., in R, the Cantor set has measure 0, although its cardinality is equal to that of R itself. If a certain statement was true except on the Cantor set, we'd still say it was true "almost everywhere".

(And all this is assuming we're using "almost everywhere" in the measure sense. Sometimes it's instead used to mean, except on a meagre set, which is a different notion; but that's not the usual meaning, so someone using it that way would hopefully say what they mean explicitly.)

In the case of the natural numbers, we frequently measure sizes of subsets by their natural density. The natural density of a subset S of the natural numbers is simply the limit of |S∩{1,...,n}|/n as n goes to infinity (this limit is not guaranteed to exist, of course). So when talking about the natural numbers, if we say something holds "almost everywhere", typically this means it holds except on a set of natural density 0.

(Remember, math terms are heavily overloaded!)

I hear there may be some people use "almost everywhere" when talking about the natural numbers to mean "except on a finite set", but I'd consider this use confusing; if that's what you mean, just say that.

Hope that clears things up.

Edit: It turns out that Tao is actually using the logarithmic density here, not the natural density. Oy. The importance of actually reading the paper, I guess...

[throwawaymath]

Thanks, this is a great comment! You've cleared things up for me a lot.