User:IssaRice/Strength of a mathematical statement - Revision history

IssaRice: /* External links */

2023-07-02T20:42:21Z

External links

← Older revision		Revision as of 20:42, 2 July 2023
Line 44:		Line 44:
	* https://gowers.wordpress.com/2011/09/26/basic-logic-connectives-not/ (search "strong")		* 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://gowers.wordpress.com/2011/10/02/basic-logic-relationships-between-statements-negation/ (search "strong")
			* https://math.stackexchange.com/a/3316825/35525

IssaRice: /* Strong vs subset */

2019-01-24T02:10:39Z

Strong vs subset

← Older revision		Revision as of 02:10, 24 January 2019
Line 22:		Line 22:
	* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]		* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]
	* "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." [https://www.readthesequences.com/The-Twelve-Virtues-Of-Rationality] See also [https://www.readthesequences.com/The-Virtue-Of-Narrowness]		* "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." [https://www.readthesequences.com/The-Twelve-Virtues-Of-Rationality] See also [https://www.readthesequences.com/The-Virtue-Of-Narrowness]
			* 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 [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

IssaRice: /* Strong vs subset */

2019-01-18T07:48:46Z

Strong vs subset

← Older revision		Revision as of 07:48, 18 January 2019
Line 21:		Line 21:
	* The identity <math>\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</math> (for nonempty <math>I,J</math>) also seems like part of this, where the appearance of a "union" actually makes the statement stronger.		* The identity <math>\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</math> (for nonempty <math>I,J</math>) 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]		* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]
	* "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." [https://www.readthesequences.com/The-Twelve-Virtues-Of-Rationality]		* "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." [https://www.readthesequences.com/The-Twelve-Virtues-Of-Rationality] See also [https://www.readthesequences.com/The-Virtue-Of-Narrowness]
	* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

IssaRice: /* Strong vs subset */

2019-01-18T07:45:23Z

Strong vs subset

← Older revision		Revision as of 07:45, 18 January 2019
Line 21:		Line 21:
	* The identity <math>\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</math> (for nonempty <math>I,J</math>) also seems like part of this, where the appearance of a "union" actually makes the statement stronger.		* The identity <math>\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</math> (for nonempty <math>I,J</math>) 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]		* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]
			* "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." [https://www.readthesequences.com/The-Twelve-Virtues-Of-Rationality]
	* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

IssaRice at 06:57, 21 October 2018

2018-10-21T06:57:25Z

← Older revision		Revision as of 06:57, 21 October 2018
Line 27:		Line 27:

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

	==References==		==References==
Line 34:		Line 40:
	==External links==		==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/09/26/basic-logic-connectives-not/ (search "strong")
	* https://gowers.wordpress.com/2011/10/02/basic-logic-relationships-between-statements-negation/ (search "strong")		* https://gowers.wordpress.com/2011/10/02/basic-logic-relationships-between-statements-negation/ (search "strong")

IssaRice: /* Negation */

2018-10-21T06:09:56Z

Negation

← Older revision		Revision as of 06:09, 21 October 2018
Line 1:		Line 1:
	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.		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.

	==~~Negation~~==		==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 <math display="inline">\forall x W(x)</math> with <math display="inline">W(x)</math> a weak statement, negating it produces <math display="inline">\exists x \neg W(x)</math>, where the strong <math display="inline">\forall x</math> has become the weak <math display="inline">\exists x</math>, and the weak <math display="inline">W(x)</math> has become a strong <math display="inline">\neg W(x)</math>. See Gowers's posts for more discussion on this.		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 <math display="inline">\forall x W(x)</math> with <math display="inline">W(x)</math> a weak statement, negating it produces <math display="inline">\exists x \neg W(x)</math>, where the strong <math display="inline">\forall x</math> has become the weak <math display="inline">\exists x</math>, and the weak <math display="inline">W(x)</math> has become a strong <math display="inline">\neg W(x)</math>. See Gowers's posts for more discussion on this.

IssaRice at 06:09, 21 October 2018

2018-10-21T06:09:16Z

← Older revision		Revision as of 06:09, 21 October 2018
Line 21:		Line 21:
	* The identity <math>\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</math> (for nonempty <math>I,J</math>) also seems like part of this, where the appearance of a "union" actually makes the statement stronger.		* The identity <math>\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</math> (for nonempty <math>I,J</math>) 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]		* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]
	* 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.)
	* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> 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.)

	==References==		==References==

IssaRice: /* Strong vs subset */

2018-10-21T04:46:42Z

Strong vs subset

← Older revision		Revision as of 04:46, 21 October 2018
Line 23:		Line 23:
	* 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.)		* 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.)
	* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, in subtyping, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

	==References==		==References==

IssaRice: /* Strong vs subset */

2018-10-21T04:44:56Z

Strong vs subset

← Older revision		Revision as of 04:44, 21 October 2018
Line 22:		Line 22:
	* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]		* 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." [https://www.facebook.com/satvik.beri/posts/641556838954?comment_id=641557093444&reply_comment_id=641575107344&comment_tracking=%7B%22tn%22%3A%22R%22%7D]
	* 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.)		* 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.)
	* ~~i think this~~ is ~~related, but i'm too confused to know how: https~~:~~//en.wikipedia.org/wiki/Covariance_and_contravariance_~~(computer_science)		* This is essentially [[wikipedia:Covariance and contravariance (computer_science)\|contravariance]]:
	* I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.		** I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

	==References==		==References==

IssaRice: /* Strong vs subset */

2018-10-21T04:39:55Z

Strong vs subset

← Older revision		Revision as of 04:39, 21 October 2018
Line 23:		Line 23:
	* 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.)		* 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.)
	* i think this is related, but i'm too confused to know how: https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)		* i think this is related, but i'm too confused to know how: https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)
	* I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \~~subset~~ A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>		* I think <math>P \subseteq Q</math> iff for all sets <math>A</math>, we have <math>Q \subseteq A \implies P \subseteq A</math>. Also, "the worlds where <math>Q\subseteq A</math>" is a subset of "the worlds where <math>P\subseteq A</math>" iff <math>P\subseteq Q</math>. Similarly, <math>Q\to A</math> is a subtype of <math>P\to A</math> iff <math>P</math> is a subtype of <math>Q</math>. Notice that all of these have the same "form" as the <math>Q \vdash \varphi</math> stuff from above.

	==References==		==References==