Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer
6  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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