3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Could you give an example of where you've seen this word? There is a Wikipedia page relating to one possible sense of the word "witness" in mathematics, but it's hard to know without an example to what "witness" might refer in the context in which you've seen it. $\endgroup$ – Michael L. Sep 26 '17 at 2:29
  • $\begingroup$ I don't think it's being used in the strict sense mentioned in that article. $\endgroup$ – Simplicio Sep 26 '17 at 2:34
  • $\begingroup$ It is often used as a term for an input to a function that produces some desired (or undesired, as the case may be) output. I have seen it used in the context of formal verification in electronic design. $\endgroup$ – copper.hat Sep 26 '17 at 2:34
  • $\begingroup$ Common term in cryptography and primality testing. $\endgroup$ – Randall Sep 26 '17 at 3:03
2
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

One way to prove a sentence of the form "there exists an $x$ such that $\ldots$" is to produce and $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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.