Deficiency of necessary conditions - MathOverflow

Deficiency of necessary conditions

2010-02-20T02:50:37Z

Motivation

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

Definition

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?

Addendum

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?

Answer by Joel David Hamkins for Deficiency of necessary conditions

2010-02-20T03:41:23Z

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

Answer by fedja for Deficiency of necessary conditions

2010-02-20T04:19:04Z

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

Answer by Gerald Edgar for Deficiency of necessary conditions

2010-02-20T13:32:24Z

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

Answer by Douglas S. Stones for Deficiency of necessary conditions

2010-02-20T23:03:45Z

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.