User:Dominus/Counting

Do we need a separate article on counting arguments?

I'm not sure. David Eppstein made this into a redirect to combinatorial proof, saying that it was a much more well-developed article. I agree that it is better developed, but I do not think it sufficiently covers the meaning of "counting argument", which appears to me to be considerably broader. As I indicated in my crummy stub, there are two similar but essentially separate meanings of "counting argument". One is combinatorial. The other is set-theoretic and concerns infinite sets. Typically, one will argue that two sets are different because one is countable and one is uncountable. Examples are the theorems that there are noncomputable numbers, undecidable languages, and noncomputable functions.

The article on combinatorial proof, quite appropriately, does not cover the set-theoretic meaning of this term. It says that a counting argument is "either of two types of proof of an identity in enumerative combinatorics".

Here are some Wikipedia uses of the term "counting argument" to mean a set-theoretic argument of the type I described:

• Counting: "Counting arguments can prove the existence of certain objects without explicitly providing an example...for instance there must exists real numbers that are not computable numbers"
• Transcendental number: "Using a counting argument one can show that there exist transcendental numbers which have bounded partial quotients and hence are not Liouville numbers." (And similarly at Liouville number.)

Here are some Wikipedia uses of the term "counting argument" for other types of counting argument that could conceivably be considered combinatoric, but which are not proofs of identities in enumerative combinatorics:

• Adelman's theorem

• Arithmetic circuit complexity: "Counting arguments tell us that there are polynomials of polynomial degree that require circuits of superpolynomial size"

• Algorithmic information theory: "A simple counting argument shows that some strings of any given length are random, and almost all strings are very close to being random"

I think that calling these proofs combinatorial is stretching a point. However, they were all called "counting arguments" by other editors.