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

Revision as of 19:36, 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$ .

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 12: / Line 12: @@
 * But if we're working in a proof system, <math display="inline">\forall x P(x)</math> means we have all of <math display="inline">P(x_1), \ldots, P(x_n)</math> separately, whereas with <math display="inline">\exists x P(x)</math> we only have one long statement <math>P(x_1) \vee P(x_2) \vee \cdots \vee P(x_n)</math>.
 * 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" ↔ "Q is 'more powerful' than P"!
+* 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>.
 ==External links==