Proper Use of the Term "Witness"

Question

I was wondering what the term "witness" means in a mathematical context. I've heard and seen it used a bunch of times, but I'm still unsure of how/why the term is used or when to use it. Perhaps someone could give a few examples of when the term could be used. I would really appreciate it. Thanks.

Answer 1

In the context of logic and constructive mathematics, a "witness" is typically a specific instance of an existentially quantified formula. (This is the sense noted in the Wikipedia article cited by @MichaelLee).

For example, you might know via the fundamental theorem of arithmetic that there exists a unique prime factorization for every integer greater than one. So, in particular, you know that there is a unique prime factorization of, e.g., 8. To provide a "witness" to this claim is to provide a (in this case unique) entity which is a factorization of 8. That would be the formula $$2 \times 2 \times 2$$ The reason this is important is because constructive mathematics requires that every existential formula have a witness. It is constructively invalid to conclude that $\exists x \phi$ without first proving that some particular entity satisfies $\phi$ (i.e., without proving $\phi(t)$ for some constant term $t$).

A common situation that violates constructive principles arises when the axiom of choice is used. A common use case for the axiom of choice is to construct an infinite set from the subsets of an infinite set when no algorithmic procedure for constructing the set can be given -- the elements must be "chosen" at random. Bertrand Russell has a famous quote illustrating the idea:

The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes.

The idea being, that for shoes you can specify to always choose the left one, the right one, to alternate, etc. With socks, however, no such procedure can be specified since (at least with some socks) the left and right sock are indistinguishable. The axiom of choice ensures us that there exists sets constructed by choosing one from the infinitely many pairs of socks. We cannot, however, provide a witness for these sets because we have no way to uniquely describe one of these sets and, since the sets are infinite, we cannot simply list the elements.

By contrast, if there were only finitely many pairs of socks then we could provide a witness to the claim that there exists a set consisting of one sock from each pair. Practically this might not be possible if it's a large finite number, but in principle we could name each sock and list the socks we have constructed our set from.

Sometimes, especially outside of logical contexts, the term "witness" is used more loosely to refer to any set/entity that satisfies a given formula and thus "bears witness" to its truth. For example, definitions, axioms, or other claims are often stated in a schematic form:

A number $n$ ($n>1$) is prime if it has no positive divisors other than $1$ and itself.

An instance of this would be, e.g., $n=2$, and so you might say that two witnesses the existence of prime numbers by satisfying the definition above. This is obviously closely related to the technical sense, but there might not be explicit mention of the existential formula $2$ is a witness of.

If none of this seems familiar to you, then I agree with other commenters that more context and examples would be needed. (My cautious optimism is that the Wikipedia article presented things in a more technical manner than you're accustomed to.)

Answer 2

One way to prove a sentence of the form "there exists an $x$ such that $\ldots$" is to produce an $x$ that satisfies the criterion. That $x$ is a witness. Very simply, if somebody claims that there is an $n\in \Bbb N$ that is the square of a prime, a witness would be $4=2^2$