User:IssaRice/Strength of a mathematical statement

In mathematics, one talks about statements being "stronger" than others, "more general" than others, a method being "more powerful" than others, etc. This page tries to point out some of the subtleties of this way of speaking.

Interaction of negation and strength

Negating a strong statement produces a weak statement, and negating a weak statement produces a strong statement. If a statement has strong and weak components, then the flip occurs at each stage. For example, in ${\textstyle \forall xW(x)}$ with ${\textstyle W(x)}$ a weak statement, negating it produces ${\textstyle \exists x\neg W(x)}$, where the strong ${\textstyle \forall x}$ has become the weak ${\textstyle \exists x}$, and the weak ${\textstyle W(x)}$ has become a strong ${\textstyle \neg W(x)}$. See Gowers's posts for more discussion on this.

Strong vs subset

A puzzle: why do we say P is stronger than Q if P is a subset of Q, but we also say that a theorem is stronger if it is more general (so bigger)?

• One reply/intuition uses something like possible world semantics, e.g. see Wei Dai's post on Aumann's agreement theorem. There is just one possible world (a single $\omega \in \Omega$), but our information state is the set of all possible worlds that we cannot distinguish, so the less we know, the more possible worlds we think we could be in.
• One visualization is to use a Venn diagram. The stronger the statement, the more our movement is restricted, as we are forced to be in more and more sets.
• When we say a strong statement like $\forall xP(x)$, we are saying $P(x_{1})\wedge P(x_{2})\wedge \cdots \wedge P(x_{n})$. When we say a weak statement like $\exists xP(x)$, we are saying $P(x_{1})\vee P(x_{2})\vee \cdots \vee P(x_{n})$. It seems like in both cases we are accumulating more and more things.
• But if we're working in a proof system, ${\textstyle \forall xP(x)}$ means we have all of ${\textstyle P(x_{1}),\ldots ,P(x_{n})}$ separately, whereas with ${\textstyle \exists xP(x)}$ we only have one long statement $P(x_{1})\vee P(x_{2})\vee \cdots \vee P(x_{n})$.
• In causal inference, I think ${\textstyle X\perp \!\!\!\perp Y\cup W}$ is stronger than ${\textstyle (X\perp \!\!\!\perp Y)\vee (X\perp \!\!\!\perp W)}$, even though both seem to use a single "or"-type operation. But if ${\textstyle Y}$ and ${\textstyle W}$ are disjoint, then I think the former is true while the latter may be false. I think this is similar to how ${\textstyle \forall x\in X(P(x))}$ is usually stronger than ${\textstyle \exists x\in X(P(x))}$, unless ${\textstyle X=\emptyset }$.
• Maybe another way to state the puzzle is this: "P is stronger than Q" ↔ "P implies Q" ↔ "Q is at least as true as P" ↔ "Q ≥ P" (as truth values T=1 and F=0) ↔ "Q is 'at least as powerful as' P"! Obviously, the last link is the problem.
• Let's say we have ${\textstyle P(x)\wedge P(y)\wedge P(z)}$. Then we can deduce ${\textstyle P(y)}$. So we can say ${\textstyle (P(x)\wedge P(y)\wedge P(z))\implies P(y)}$. Let's visualize this by drawing each of ${\textstyle P(x),P(y),P(z)}$ as points. Then if we know ${\textstyle P(x)\wedge P(y)\wedge P(z)}$, the set of statements we know is ${\textstyle A:=\{P(x),P(y),P(z)\}}$. The set of statements we are trying to prove is ${\textstyle B:=\{P(y)\}}$. But now notice something strange: ${\textstyle A}$ is stronger than ${\textstyle B}$, but we have ${\textstyle B\subsetneq A}$. A question might be: how do we visualize ${\textstyle P(x)\vee P(y)\vee P(z)}$ in this scheme? My first thought was "Maybe we need three copies of the diagram, so that we have ${\textstyle (P(x)\wedge P(y)\wedge P(z))\implies P(x)}$, ${\textstyle (P(x)\wedge P(y)\wedge P(z))\implies P(y)}$, and ${\textstyle (P(x)\wedge P(y)\wedge P(z))\implies P(z)}$". But maybe a better way to think of this is that each set such as ${\textstyle B}$ above is a microcosm. Once you're in ${\textstyle B}$, it's not as small as you thought! You're actually in the set ${\textstyle \{P(y),P(y)\vee P(x),P(y)\vee P(z),P(y)\vee P(x)\vee P(z)\}}$. And once you're in this microcosm/"kingdom", you can navigate to wherever you please. This explains why a strong statement is bigger (in this visualization): when we start out with more statements, our "kingdom" is bigger (we get more combinations of OR statements for free). So we can navigate to many other smaller sets of sentences (villages, towns, whatever).
• The above vs joint distribution. Symbolically, the contrast between ${\textstyle \Pr(x,y,z)}$ (the joint distribution specifies an elementary event, which is small, whereas a marginal distribution specifies a "lumped together" event, which is large) and ${\textstyle P(x),P(y),P(z)}$ (the more statements we know, the larger the set of statements we know).
• What do I mean by "navigate to"? Basically I mean ${\textstyle \vdash }$ from mathematical logic. If ${\textstyle A}$ and ${\textstyle B}$ are sets of sentences, then "if we have ${\textstyle A}$, we can navigate to ${\textstyle B}$" means ${\textstyle A\vdash B}$.
• Maybe a better notation would be $P\subseteq Q\iff \forall x(P(x)\implies Q(x))\iff \forall x\{\varphi :Q(x)\vdash \varphi \}\subseteq \{\varphi :P(x)\vdash \varphi \}\implies \{\varphi :Q\vdash \varphi \}\subseteq \{\varphi :P\vdash \varphi \}$
• The identity $\left(\bigcap _{\alpha \in I}A_{\alpha }\right)\cap \left(\bigcap _{\alpha \in J}A_{\alpha }\right)=\bigcap _{\alpha \in I\cup J}A_{\alpha }$ (for nonempty $I,J$) also seems like part of this, where the appearance of a "union" actually makes the statement stronger.
• Nate's comment: "the way I think of it is that there are fewer ways to write a fn with a more general type (for the same reasons there’s less you can say about that is true about all apples than about any one particular apple), so if your function is in the general type and you write it in the general type then the typechecker verifies that you didn’t accidentally depend on any specifics." [1]
• "What is true of one apple may not be true of another apple; thus more can be said about a single apple than about all the apples in the world." [2] See also [3]
• There is an analogy with markup languages that I'm not sure is completely correct but I thought interesting: there are two approaches to "unifying" or "single-source publishing" all your work. You could either work in a "super language" that uses the union of features of all markup languages you want to export to, or you could work in a "crippled language" that uses the intersection of features of all markup languages you want to export to.
• This is essentially contravariance:
  • I think $P\subseteq Q$ iff for all sets $A$, we have $Q\subseteq A\implies P\subseteq A$. Also, "the worlds where $Q\subseteq A$" is a subset of "the worlds where $P\subseteq A$" iff $P\subseteq Q$. Similarly, in subtyping, $Q\to A$ is a subtype of $P\to A$ iff $P$ is a subtype of $Q$. Notice that all of these have the same "form" as the $Q\vdash \varphi$ stuff from above.

Proving a stronger statement

• Charles Chapman Pugh: "It may seem paradoxical at first, but a specific math problem can be harder to solve than some abstract generalization of it." (Real Mathematical Analysis, p. 51.)

Strength in a more informal sense

• https://gowers.wordpress.com/2008/12/28/how-can-one-equivalent-statement-be-stronger-than-another/

In this sense, two logically equivalent statements can have a different strength, i.e. strength is not measured in the logical power of the statement.

External links

• https://gowers.wordpress.com/2011/09/26/basic-logic-connectives-not/ (search "strong")
• https://gowers.wordpress.com/2011/10/02/basic-logic-relationships-between-statements-negation/ (search "strong")
• https://math.stackexchange.com/a/3316825/35525