User:IssaRice/Strength of a mathematical statement

Negation

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

External links

• https://gowers.wordpress.com/2008/12/28/how-can-one-equivalent-statement-be-stronger-than-another/ (haven't read this yet)
• 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")