User:IssaRice/Strength of a mathematical statement: Difference between revisions

Revision as of 19:49, 1 October 2018

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 $\forall x W (x)$ with $W (x)$ a weak statement, negating it produces $\exists x \neg W (x)$ , where the strong $\forall x$ has become the weak $\exists x$ , and the weak $W (x)$ has become a strong $\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 $ω \in Ω$ ), 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 x P (x)$ , we are saying $P (x_{1}) \land P (x_{2}) \land \dots \land P (x_{n})$ . When we say a weak statement like $\exists x P (x)$ , we are saying $P (x_{1}) \lor P (x_{2}) \lor \dots \lor 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, $\forall x P (x)$ means we have all of $P (x_{1}), \dots, P (x_{n})$ separately, whereas with $\exists x P (x)$ we only have one long statement $P (x_{1}) \lor P (x_{2}) \lor \dots \lor P (x_{n})$ .
In causal inference, I think $X ⊥ ⊥ Y \cup W$ is stronger than $(X ⊥ ⊥ Y) \lor (X ⊥ ⊥ W)$ , even though both seem to use a single "or"-type operation. But if $Y$ and $W$ are disjoint, then I think the former is true while the latter may be false. I think this is similar to how $\forall x \in X (P (x))$ is usually stronger than $\exists x \in X (P (x))$ , unless $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 $P (x) \land P (y) \land P (z)$ . Then we can deduce $P (y)$ . So we can say $(P (x) \land P (y) \land P (z)) ⟹ P (y)$ . Let's visualize this by drawing each of $P (x), P (y), P (z)$ as points. Then if we know $P (x) \land P (y) \land P (z)$ , the set of statements we know is $A : = {P (x), P (y), P (z)}$ . The set of statements we are trying to prove is $B : = {P (y)}$ . But now notice something strange: $A$ is stronger than $B$ , but we have $B ⊊ A$ . A question might be: how do we visualize $P (x) \lor P (y) \lor P (z)$ in this scheme? My first thought was "Maybe we need three copies of the diagram, so that we have $(P (x) \land P (y) \land P (z)) ⟹ P (x)$ , $(P (x) \land P (y) \land P (z)) ⟹ P (y)$ , and $(P (x) \land P (y) \land P (z)) ⟹ P (z)$ ". But maybe a better way to think of this is that each set such as $B$ above is a microcosm. Once you're in $B$ , it's not as small as you thought! You're actually in the set ${P (y), P (y) \lor P (x), P (y) \lor P (z), P (y) \lor P (x) \lor 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 $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 $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")

@@ Line 13: / Line 13: @@
 * In causal inference, I think <math display="inline">X \perp\!\!\!\perp Y\cup W</math> is stronger than <math display="inline">(X \perp\!\!\!\perp Y) \vee (X \perp\!\!\!\perp W)</math>, even though both seem to use a single "or"-type operation. But if <math display="inline">Y</math> and <math display="inline">W</math> are disjoint, then I think the former is true while the latter may be false. I think this is similar to how <math display="inline">\forall x\in X(P(x))</math> is usually stronger than <math display="inline">\exists x\in X(P(x))</math>, unless <math display="inline">X = \emptyset</math>.
 * 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 <math display="inline">P(x) \wedge P(y) \wedge P(z)</math>. Then we can deduce <math display="inline">P(y)</math>. So we can say <math display="inline">(P(x) \wedge P(y) \wedge P(z)) \implies P(y)</math>. Let's visualize this by drawing each of <math display="inline">P(x), P(y), P(z)</math> as points. Then if we know <math display="inline">P(x) \wedge P(y) \wedge P(z)</math>, the set of statements we know is <math display="inline">A := \{P(x), P(y), P(z)\}</math>. The set of statements we are trying to prove is <math display="inline">B := \{P(y)\}</math>. But now notice something strange: <math display="inline">A</math> is stronger than <math display="inline">B</math>, but we have <math display="inline">B \subsetneq A</math>.
+* Let's say we have <math display="inline">P(x) \wedge P(y) \wedge P(z)</math>. Then we can deduce <math display="inline">P(y)</math>. So we can say <math display="inline">(P(x) \wedge P(y) \wedge P(z)) \implies P(y)</math>. Let's visualize this by drawing each of <math display="inline">P(x), P(y), P(z)</math> as points. Then if we know <math display="inline">P(x) \wedge P(y) \wedge P(z)</math>, the set of statements we know is <math display="inline">A := \{P(x), P(y), P(z)\}</math>. The set of statements we are trying to prove is <math display="inline">B := \{P(y)\}</math>. But now notice something strange: <math display="inline">A</math> is stronger than <math display="inline">B</math>, but we have <math display="inline">B \subsetneq A</math>. A question might be: how do we visualize <math display="inline">P(x) \vee P(y) \vee P(z)</math> in this scheme? My first thought was "Maybe we need three copies of the diagram, so that we have <math display="inline">(P(x) \wedge P(y) \wedge P(z)) \implies P(x)</math>, <math display="inline">(P(x) \wedge P(y) \wedge P(z)) \implies P(y)</math>, and <math display="inline">(P(x) \wedge P(y) \wedge P(z)) \implies P(z)</math>". But maybe a better way to think of this is that each set such as <math display="inline">B</math> above is a ''microcosm''. Once you're in <math display="inline">B</math>, it's not as small as you thought! You're actually in the set <math display="inline">\{P(y), P(y) \vee P(x), P(y) \vee P(z), P(y) \vee P(x) \vee P(z)\}</math>. And once you're in this microcosm/"kingdom", you can navigate to wherever you please.
+* The above vs joint distribution. Symbolically, the contrast between <math display="inline">\Pr(x,y,z)</math> (the joint distribution specifies an elementary event, which is small, whereas a marginal distribution specifies a "lumped together" event, which is large) and <math display="inline">P(x),P(y),P(z)</math> (the more statements we know, the larger the set of statements we know).
 ==External links==