# $n$ out of $m$ theorems (some imply the rest)

Is there symbolism (or even a name) for groups of statements in which any fixed-number of them imply all the rest?

For example, in linear algebra, a basis is sometimes defined as a set of n-dimensional vectors which:

• Is linearly independent
• Spans the vector space
• Contains exactly n elements

However, it is then shown that any TWO of these statements being true implies the third is true. How would you write this symbolically? (other than $A \wedge B \Rightarrow C, A \wedge C \Rightarrow B, B \wedge C \Rightarrow A$, which does not scale well...)

-
Can you think of any other non-trivial examples, especially with n>2 or m>3? The case n=1 (for any m) is the well known "the following are equivalent", but other than that, I'm hard-pressed to think of many good examples of this phenomenon. – Simon Nickerson Jul 26 '10 at 11:37
I suspect that many examples of this phenomenon have m-n = 1 -- that is, that if all but one of a list of conditions holds, then all of them hold. – Michael Lugo Jul 26 '10 at 15:00

I encountered this situation when dealing with permutations; we phrased it as follows. If $\sigma$ is a permutation of $\mathbb{Z}_n$ and $d$ is a divisor of $n$, then it is impossible for precisely two of the following statements to hold for some $i,j \in \mathbb{Z}_n$:

• $i \equiv j \pmod d$,
• $\sigma(i) \equiv \sigma(j) \pmod d$ and
• $\sigma(i)-i \equiv \sigma(j)-j \pmod d$.

I suspect a modification of this would suffice in most cases.

-

Often the most obvious solution is the best solution. I would write T(s) be 1 if a statement is true and 0 if it is false. I would then call the statements A, B and C and let S={A, B, C}. Then is would write sum T(s) over S >=2 => all s are true. You can make these statement more symbolic if you really like

-
Of course, it is often best to not be formal at all and just say any 2 of the following statements imply the third – Casebash Jul 26 '10 at 10:31
I nearly fell for this trap once. The above sentence asserts, for example, that the second and third statements imply the third statement (which is pretty silly). – Douglas S. Stones Nov 7 '10 at 2:55