5
$\begingroup$

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

  • 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.2010-07-26
  • 0
    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.2010-07-26

2 Answers 2

1

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.

2

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

  • 6
    Of course, it is often best to not be formal at all and just say any 2 of the following statements imply the third2010-07-26
  • 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).2010-11-07