2
$\begingroup$

This is a really basic question, but it is one I never really thought about until now.

Let $\mathscr{G}$ be a tree. Then every pair of vertices in $\mathscr{G}$ is connected by a unique walk.

We are asked to prove the converse which is worded as:

If any two vertices of $\mathscr{G}$ are joined by a unique walk, then $\mathscr{G}$ is a tree.

My question is whether the author means that if we can find a single pair of vertices that are joined by a unique walk in a graph (that may not be a tree), then we know $\mathscr{G}$ is a tree (which obviously is not true), or if he means something more a long the lines of "for all pairs of two vertices in $\mathscr{G}$".

Similarly, he asks us to prove:

If $\mathscr{G}$ is connected but becomes disconnected by the removal of any one edge, then $\mathscr{G}$ is a tree.

Again, in one case it is easy to find counterexamples of graphs with cycles (not trees) that can become disconnected by the removal of one of their edges, but if he wants us to prove that "if, for every edge, the removal of that edge will result in a disconnected graph, then the graph is a tree", the proof while also simple is very, very different.

I come from a more applied background and am not used to this kind of wording. Any insight would be much appreciated.

$\endgroup$
1
  • $\begingroup$ In both cases, your second interpretation is correct. $\endgroup$ Sep 30, 2013 at 2:24

3 Answers 3

9
$\begingroup$

One problem with "any" is that, in mathematical English, it can mean either "there exists" or "for all".

Some examples where "any" means "there exists":

  • A number $\lambda$ is an eigenvalue of a matrix $A$ if any nonzero vector $x$ satisfies $(A-\lambda)x = 0$.

  • $X \cap Y$ is nonempty if any element of $X$ is an element of $Y$

Some examples where "any" means "for all":

  • A set $A$ generates a group $G$ if any element $g \in G$ can be written as a product of elements of $A$.

  • A graph is connected if any two vertices are connected by a path.

The result of this is that you have to use context or prior knowledge to read a mathematical sentence with "any" in it; there is not a general algorithm that will tell you how to read English. I generally advise my own students to avoid the word "any" until they are very comfortable with mathematical English.

In the context of the question, if you state the converse as "If every pair of vertices of a graph is connected by a unique walk, then the graph is a tree", you can avoid the "any" issue altogether.

$\endgroup$
7
  • $\begingroup$ Another example: both of these are correct. "For any $a,b$, if $an + bm = 1$ then $n$ and $m$ are relatively prime". "$n$ and $m$ are relatively prime if $an + bm = 1$ for any $a,b$". In the former, "any" is universal; in the latter it is existential. $\endgroup$ Oct 9, 2013 at 11:05
  • $\begingroup$ Do you have references to support your claim that "any" is sometimes used to mean "there exists" as in your first two examples? To me, all of the examples you wrote for this sound just plain wrong and I think they should say "some" instead of "any". $\endgroup$ Oct 9, 2013 at 17:58
  • $\begingroup$ Here is another example: "If a subset of a vector space is nonempty, closed under vector addition, and closed under scalar multiplication, it is a subspace. If any of those three conditions fails, the subset is not a subspace." That is a perfectly idiomatic English statement, in which "any" means "at least one" rather than "all". $\endgroup$ Oct 9, 2013 at 21:34
  • $\begingroup$ Similarly, see the use of any in this answer: mathoverflow.net/a/25805/5442 or this question mathoverflow.net/q/61954/5442 $\endgroup$ Oct 9, 2013 at 21:40
  • $\begingroup$ Okay, I agree with your examples in the comments (I'm not sure why; maybe because the "if any" comes at the beginning of a sentence.) However, it seems to me that even someone who was very comfortable with mathematical English would not be able to determine that "any" means "some" in your eigenvalue example and "all" in your group example, because the sentence structure is essentially the same. Wouldn't one have to already know the definitions to make this determination? $\endgroup$ Oct 9, 2013 at 21:44
2
$\begingroup$

Logically, they're the same: "For any $x$, $P(x)$" is the same as "For every $x$, $P(x)$" is the same as "$\forall x$, $P(x)$." Your initial inclination is correct.


There is, however, at least to my ear, a difference in connotation and hint of proof method. "For any" emphasizes that this property holds for an arbitrary element --- in your case, an arbitrary pair of vertices on the tree. Perhaps the proof will include the choice and consideration of an arbitrary object.

Meanwhile, "For every" emphasizes somehow some sort of "uniformity" --- perhaps the proposition can be proven from the properties of this class of object without choice of an arbitrary object.

But a note of caution: These are subtle connotations, certainly not definitions set in stone! Don't take them as gospel, but rather merely as one person's coloring of the language. They are two ways of phrasing the same logical quantifier.

$\endgroup$
6
  • $\begingroup$ The part that confused me was "if any". "For any" would be much more clear. $\endgroup$ Sep 30, 2013 at 2:46
  • $\begingroup$ I suppose one other factor is that he asked that we prove these. If you are asked to prove something and disprove it, I assume it is doing it wrong. But there is of course nothing that says the converse of a theorem must hold. $\endgroup$ Sep 30, 2013 at 2:48
  • $\begingroup$ @thomasjames I tend to think of "If any two vertices are joined by a unique path ..." as "If, for any two vertices, they are joined by a unique path ...". $\endgroup$
    – Neal
    Sep 30, 2013 at 2:57
  • $\begingroup$ Thank you. I'll go forward assuming he meant this, and will just add a comment about it. $\endgroup$ Sep 30, 2013 at 3:06
  • $\begingroup$ Quine makes a case in “Methods of Logic” that ‘any’ calls for a broader scope, and ‘every’ a narrower scope. For example: “if anyone contributes, I'll be surprised,” is ‘$\forall x ( F x \to p )$’ and “if everyone contributes, I'll be surprised,” is ‘$\forall x F x \to p$’ for the domain of people; “I don't know any poem,” is ‘$\forall x \neg F x$’, and “I don't know every poem,” is ‘$\neg \forall x F x$’ for the domain of poems. $\endgroup$ Sep 30, 2013 at 3:53
0
$\begingroup$

According to the Oxford English Dictionary, "every" and "each" are both universal quantifiers, but "any" is not called a universal quantifier by the OED. Instead "any" is used to express qualitative force, i.e. emphasis. Unfortunately, careless usage has eroded these subtle distinctions.

$\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.