MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Consider the situation: You know that every $x$ that has property $P$ must have property $Q$. $Q$ is a rather strong condition but not strong enough to fulfill $P$. What is missing?

Consider the formulas of a first-order language, a distinguished set of axioms $S$, and the formulas with exactly one free variable, factored out by provable equivalence $P(x) \sim_S Q(x)$ iff $S \vdash P(x) \leftrightarrow Q(x)$ – for short: properties.

There is a partial order on the set of properties by $[P(x)] \Rightarrow_S [Q(x)]$ iff $S\vdash P(x) \rightarrow Q(x)$ – for short: $P \Rightarrow Q$.

Let $P \Rightarrow Q$, but $Q \not\Rightarrow P$, read: $Q$ is a proper necessary condition of $P$.


A property $D(x)$ may be called a defect of $Q(x)$ with respect to $P(x)$ if

  • $D \not\Rightarrow P$
  • $Q \wedge D \Rightarrow P$

A defect $D(x)$ may be called minimal if there is no other defect $D'(x)$ with $D(x) \Rightarrow D'(x)$.

Question #1: Is the search for (minimal) defects so manifest – in the working mathematician's life – that it is performed every day without needing a proper name? And is the notion ´– thus – of no (meta-)mathematical importance?

Question #2: ... or is there already a proper – and more common – name?

Question #3: ... or is the definition above and its presuppositions flawed?


The common divisor graph on the natural numbers shares one strong property $Q$ with the Rado (= random) graph: it contains any finite graph as an induced subgraph (which I guess is a quite general necessary condition for randomness). But it's not isomorphic to the Rado graph, i.e. does not fulfill its defining property $P$. I am now interested in the "defect" of the common divisor graph: which property $D$ - as minimal as possible - prevents the common divisor graph from being truly random?

share|cite|improve this question
up vote 4 down vote accepted

Normally your "defect" is called an "additional assumption"/"extra condition"/... and the typical phrase is "the inverse implication also holds under the additional assumption that...". Yes, the search for such things is something that mathematicians do on an everyday basis trying to bridge the gap between what is necessary and what is sufficient.

The thing you should understand is that in real life it is not necessarily the first priority to have $D$ as weak as possible from the logical standpoint. What often matters much more is that $D$ is easy to verify, holds in many interesting cases, allows one to give an easy and elegant proof, etc. Actually, Joel has already brought the idea of pure logical minimality to its absurd extreme form, so I hardly need to comment more on this issue.

By the way, the assumption that $P\implies Q$ is completely unnecessary in your definition of the "defect"; it makes just as much sense without it. Indeed, the usual story is that we know something ($Q$), we want to conclude something else ($P$), we suspect that the implication $Q\implies P$ is (may be) not always true, but we want this implication not for its own sake but to figure out something about some object $X$, so we ask what other property $D$ $X$ possesses that together with $Q$ will give us $P$.

share|cite|improve this answer
Thanks! If you want to, please see my comment on Joel's answer and the concrete example in the addendum to my question. – Hans Stricker Feb 20 '10 at 13:23

First, let me mention that one must be careful when asserting that an implication fails. Taken literally, the assertion "D(x) does not imply P(x)" is logically equivalent to the assertion that D(x) is true and P(x) is false. This meaning of material implication that is used in mathematics is not the same as the natural language interpretation of if-then. For example, if the professor says to a student "It is not true that if you pass the final, then you pass the class", most people would not want the students to deduce logically that he or she will pass the final, but fail the class. But this does follow logically from the mathematical usage of material implication. So your definition of "defect" may not be what you intend.

To be sure, mathematicians are often sloppy about this. One often hears people say that such-and-such condition does not imply another condition. What they mean is that it does not necessarily imply the other condition. For example, suppose I have a function f, and someone says "its not true that if f is continuous, then f is differentiable." This statement is logically equivalent to the assertion that f is indeed continuous and not differentiable. What they meant to say, of course, was that "not every continuous function is differentiable".

In your case, you assert two implication failures: one if the definition of defect and another in the definition of minimal. When you clarify exactly what you mean more precisely, you will be led to the conclusion that the only sensible (minimal) defect is simply the assertion D(x), asserting that "either P(x) holds, or Q(x) fails". This statement does not imply P(x), except for those values of x for which Q(x) already implies P(x), and also if D(x) ∧ Q(x), then P(x) follows immediately. If D'(x) is any other statement such that D'(x) ∧ Q(x) implies P(x), then D'(x) implies that either Q(x) fails or P(x) holds, and so D'(x) implies D(x).

share|cite|improve this answer
Concerning minimality I agree: Q -> P which together with Q implies P is of course the minimal "defect", but trivially so and telling nothing about Q and P. So it should sensibly be excluded in the definition. Please see the addendum to my question. – Hans Stricker Feb 20 '10 at 13:23
If you exclude this answer, then I'm not sure you have a sensible notion, since all minimal defects will be logically equivalent to it. – Joel David Hamkins Feb 22 '10 at 1:30
As for your addendum, there are all sorts of reasons why the divisibility graph is not the random graph: for example, whenever 4 divides a number, then 2 also does; this violates the random graph property that for any two disjoint finite sets of nodes, there is a node connected to every node in the first set and none in the second. Any property that the divisibility graph has and the random graph does not prevents them being isomorphic, and the minimal such property is equivalent to the disjunction of all such properties, or just "Not isomorphic to Rado". (logically OK, but again not useful.) – Joel David Hamkins Feb 22 '10 at 1:41

A specific (and rather well-known) example exists for prime numbers. There are necessary conditions (such as Fermat's Little Theorem) which is satisfied by all primes, but sometimes satisfied by composites as well. These composites are called pseudoprimes. The property D could be considered to be non-pseudoprimality.

share|cite|improve this answer
+1, for I found this a very valuable - because concrete - hint. – Hans Stricker Feb 21 '10 at 23:20

In one field of mathematics, it's the "Tauberian condition".

share|cite|improve this answer

Your Answer


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.