Differences

This shows you the differences between two versions of the page.

 intuitionistic_propositional_logic [2016/08/28 01:17]nikolaj intuitionistic_propositional_logic [2017/01/07 01:12] (current)nikolaj Both sides previous revision Previous revision 2017/01/07 01:12 nikolaj 2016/08/28 01:17 nikolaj 2016/04/13 11:20 nikolaj 2016/04/13 11:19 nikolaj 2016/04/13 11:17 nikolaj 2016/04/13 11:17 nikolaj 2016/04/13 11:16 nikolaj 2016/04/13 11:13 nikolaj 2016/04/13 11:12 nikolaj 2016/04/13 10:39 nikolaj 2016/04/13 10:39 nikolaj 2016/04/13 10:38 nikolaj 2016/04/13 10:37 nikolaj 2016/04/13 10:36 nikolaj 2016/04/13 00:23 nikolaj 2016/04/13 00:18 nikolaj 2016/04/12 17:44 nikolaj 2016/04/12 17:44 nikolaj 2016/04/12 17:43 nikolaj 2016/04/12 17:40 nikolaj 2016/04/12 17:38 nikolaj 2016/04/12 17:35 nikolaj 2016/04/12 17:34 nikolaj 2016/04/12 17:28 nikolaj 2016/04/12 17:27 nikolaj 2016/04/12 17:27 nikolaj 2016/04/12 17:25 nikolaj 2017/01/07 01:12 nikolaj 2016/08/28 01:17 nikolaj 2016/04/13 11:20 nikolaj 2016/04/13 11:19 nikolaj 2016/04/13 11:17 nikolaj 2016/04/13 11:17 nikolaj 2016/04/13 11:16 nikolaj 2016/04/13 11:13 nikolaj 2016/04/13 11:12 nikolaj 2016/04/13 10:39 nikolaj 2016/04/13 10:39 nikolaj 2016/04/13 10:38 nikolaj 2016/04/13 10:37 nikolaj 2016/04/13 10:36 nikolaj 2016/04/13 00:23 nikolaj 2016/04/13 00:18 nikolaj 2016/04/12 17:44 nikolaj 2016/04/12 17:44 nikolaj 2016/04/12 17:43 nikolaj 2016/04/12 17:40 nikolaj 2016/04/12 17:38 nikolaj 2016/04/12 17:35 nikolaj 2016/04/12 17:34 nikolaj 2016/04/12 17:28 nikolaj 2016/04/12 17:27 nikolaj 2016/04/12 17:27 nikolaj 2016/04/12 17:25 nikolaj 2016/04/12 17:24 nikolaj 2015/12/08 22:42 nikolaj 2015/12/08 13:31 nikolaj 2015/10/14 17:49 nikolaj 2015/10/13 19:10 nikolaj 2015/10/13 19:10 nikolaj 2015/10/13 19:09 nikolaj 2015/10/13 19:08 nikolaj 2015/10/13 18:40 nikolaj 2015/10/13 17:08 nikolaj 2015/10/06 16:16 nikolaj 2015/10/06 16:12 nikolaj 2015/10/06 16:11 nikolaj 2015/10/06 16:08 nikolaj 2015/10/06 15:40 nikolaj 2015/10/06 15:08 nikolaj 2014/11/11 11:11 nikolaj 2014/11/11 11:11 nikolaj 2014/03/30 18:08 nikolaj 2014/03/30 18:03 nikolaj 2014/03/27 23:01 nikolaj 2014/03/27 22:08 nikolaj 2014/03/27 22:07 nikolaj 2014/03/27 21:14 nikolaj Line 161: Line 161: If you reason about a subject that includes the statement If you reason about a subject that includes the statement >​It'​s true that today I'll eat at MacDonalds OR it's false that today I'll eat at MacDonalds >​It'​s true that today I'll eat at MacDonalds OR it's false that today I'll eat at MacDonalds - i.e. $M \lor \neg M[/​math] ​where the semantics (I should maybe say '​subject',​ as semantics is used more technically too) of [math]M[/​math] ​are "today I'll eat at MacDonalds ". + i.e. M \lor \neg M where the semantics (I should maybe say '​subject',​ as semantics is used more technically too) of M are "today I'll eat at MacDonalds ". then adoption LEM is likely what you want to do. then adoption LEM is likely what you want to do. If you reason about a subject that includes the statement If you reason about a subject that includes the statement Line 177: Line 177: - An appealing aspect of intuitionistic logic is that is has faithful semantics (in the sense of: let [math]M[/​math] ​mean that „today I'll eat at MacDonals.“) in something real, namely actions. ​ + An appealing aspect of intuitionistic logic is that is has faithful semantics (in the sense of: let M mean that „today I'll eat at MacDonals.“) in something real, namely actions. ​ https://​en.wikipedia.org/​wiki/​Brouwer%E2%80%93Heyting%E2%80%93Kolmogorov_interpretation https://​en.wikipedia.org/​wiki/​Brouwer%E2%80%93Heyting%E2%80%93Kolmogorov_interpretation Line 185: Line 185: This logic is precisely the one which you can use to describe a cooking recopy or a programming language: This logic is precisely the one which you can use to describe a cooking recopy or a programming language: - Read [math]A \land B[/​math] ​(interpretation in logic: „it’s true that A holds and it’s true that B holds“) as + Read A \land B (interpretation in logic: „it’s true that A holds and it’s true that B holds“) as >I have a proof/​reason to believe/​argument for A and I have a proof/​reason to believe/​argument B >I have a proof/​reason to believe/​argument for A and I have a proof/​reason to believe/​argument B - Read [math]A \lor B[/​math] ​in the same way. + Read A \lor B in the same way. - Read [math]A \to B[/​math] ​(in logic: „if A is true, then B is true„) as + Read A \to B (in logic: „if A is true, then B is true„) as >If I have proof/​reason to believe/​argument for A, then I can conceive a proof/​reason to believe/​argument >If I have proof/​reason to believe/​argument for A, then I can conceive a proof/​reason to believe/​argument - and [math]\neg A[/​math] ​ (in logic „A is false“) as + and \neg A (in logic „A is false“) as >If I have proof/​reason to believe/​argument for A, then something’s wrong because that’s a contradiction and doesn’t make sense >If I have proof/​reason to believe/​argument for A, then something’s wrong because that’s a contradiction and doesn’t make sense - The last connective is properly defined as [math]\neg A := A \to \bot$ + The last connective is properly defined as $\neg A := A \to \bot$ Now a statement like Now a statement like - $(A \land B) \to A$ + $(A \land B) \to A$ - is intutionistically true, because if I have a reason to believe A and one to believe B, then in particular I have a reason to believe A. Computationally,​ this „proof I just give corresponds to a function ​$f[/​math] ​of type + is intutionistically true, because if I have a reason to believe A and one to believe B, then in particular I have a reason to believe A. Computationally,​ this „proof I just give corresponds to a function ​f of type - [math](A \times B) \to A$ + $(A \times B) \to A$ i.e. i.e. - $f : (A \times B) \to A$ + $f : (A \times B) \to A$ namely namely - $f = \langle a, b\rangle \mapsto a$ + $f = \langle a, b\rangle \mapsto a$ or written differently,​ or written differently,​ - $f = p \mapsto \pi_1(p)$, + $f = p \mapsto \pi_1(p)$, - where $\pi_l[/​math] ​is the left projection operation. + where \pi_l is the left projection operation. A reason g not to believe A, i.e. A reason g not to believe A, i.e. - [math]g: \neg A[/​math] ​or [math]g: A\to \bot[/​math] ​ + g: \neg A or g: A\to \bot can be read as a function that takes an argument a and A but never terminates. g(a) is looping on your hard drive forever. can be read as a function that takes an argument a and A but never terminates. g(a) is looping on your hard drive forever. - The statement ​[math]A \to \neg ( \neg A )[/​math] ​is also true: Having a reason to believe A means that also having a reason not to believe A would already be a contradiction. + The statement ​A \to \neg ( \neg A ) is also true: Having a reason to believe A means that also having a reason not to believe A would already be a contradiction. - The computational proof [math]h : A \to ( (A \to \bot) \to \bot) [/​math] ​is simple too: + The computational proof h : A \to ( (A \to \bot) \to \bot)  is simple too: - [math]h = a \mapsto ( H \mapsto H(a) )$ + $h = a \mapsto ( H \mapsto H(a) )$ - Given an argument ‚a‘ and then a looping function ​$​H : A\to \bot$, plugging in ‚a‘ into H will trigger an unending loop - the type matches. + Given an argument ‚a‘ and then a looping function ​$H : A\to \bot$, plugging in ‚a‘ into H will trigger an unending loop - the type matches. - But $(A\to \bot) \to \bot \to A[/​math] ​is constructively not true. To logical argument is this: Merely knowing that ‚a reason to believe A is absurd‘ would be absurd - this in itself is not a constructive argument for A. + But (A\to \bot) \to \bot \to A is constructively not true. To logical argument is this: Merely knowing that ‚a reason to believe A is absurd‘ would be absurd - this in itself is not a constructive argument for A. Maybe the computational semantics is more clear here: Asking for a function of type Maybe the computational semantics is more clear here: Asking for a function of type - [math]( ( A \to \bot ) \to \bot) \to A$ + $( ( A \to \bot ) \to \bot) \to A$ - is asking for way to construct a term ‚a‘ using a functional which takes looping functions in $A \to \bot[/​math] ​as argument but never terminates. How would a terms ‚a‘ ever come from this?? It doesn’t. + is asking for way to construct a term ‚a‘ using a functional which takes looping functions in A \to \bot as argument but never terminates. How would a terms ‚a‘ ever come from this?? It doesn’t. A more complicated but not too hard example, to conclude this, would be A more complicated but not too hard example, to conclude this, would be - [math] ​( \neg A \land \neg B ) \implies \neg ( A \lor B )$ + $( \neg A \land \neg B ) \implies \neg ( A \lor B )$ >If ‚A is false‘ as well as ‚B is false‘, then neither is 'A or B'. >If ‚A is false‘ as well as ‚B is false‘, then neither is 'A or B'. or or - $​( ( A \to \bot) \times ( B \to \bot ) ) \to (A+B) \to \bot$ + $( ( A \to \bot) \times ( B \to \bot ) ) \to (A+B) \to \bot$ where + is the direct sum. where + is the direct sum. If next to the projection operators you introduce the programming concept of if-clauses now (as you have them in C++ or Phython), you’ll be able to proof this claim. If next to the projection operators you introduce the programming concept of if-clauses now (as you have them in C++ or Phython), you’ll be able to proof this claim. Line 232: Line 232: >>​7708352 >>​7708352 If by "​analysist"​ you mean a guy who's studying classical analysis, then the question has probably no answer. ​ If by "​analysist"​ you mean a guy who's studying classical analysis, then the question has probably no answer. ​ - Dropping non-constructive axioms of your theories becomes relevant, for example, whenever you got to implement stuff. As you can't even list the element of $\mathbb R$, theorems in classical analysis will be vacuous for such realization. The good news is that people have spun the spiderwebs of theories like analysis in a constructive fashion long ago, see for example all the constrictive theorems that aggregate around the unprovable intermediate value theorem + Dropping non-constructive axioms of your theories becomes relevant, for example, whenever you got to implement stuff. As you can't even list the element of $\mathbb R$, theorems in classical analysis will be vacuous for such realization. The good news is that people have spun the spiderwebs of theories like analysis in a constructive fashion long ago, see for example all the constrictive theorems that aggregate around the unprovable intermediate value theorem https://​en.wikipedia.org/​wiki/​Constructive_analysis#​Examples https://​en.wikipedia.org/​wiki/​Constructive_analysis#​Examples Line 238: Line 238: Syntetic analysis as in the pic from the book by Kock is relevant because the requirements for the theory are such that certain topoi give you internal analysis as a gift. That is you consider some topos, check if it has this and that property and then it might be implied that that topos really is about calculus/​contains a theory of calculus and you can import all the theorems you already know - I mean that's the nice feat of category theory in general. ​ Syntetic analysis as in the pic from the book by Kock is relevant because the requirements for the theory are such that certain topoi give you internal analysis as a gift. That is you consider some topos, check if it has this and that property and then it might be implied that that topos really is about calculus/​contains a theory of calculus and you can import all the theorems you already know - I mean that's the nice feat of category theory in general. ​ - The category of sets $A, B, C,...[/​math] ​(=objects) and functions ​[math]f, g ,h,...[/​math] ​(=arrows) is a topos and thus has cartesian product ​[math]A\times B[/​math] ​(=the categorical product) and function spaces ​[math]B^A[/​math] ​(=internal, setty realizations of the arrow class from [math]A[/​math] ​to [math]B$, which may be written ​$A \to B$) + The category of sets $A, B, C,...$ (=objects) and functions ​$f, g ,h,...$ (=arrows) is a topos and thus has cartesian product ​$A\times B$ (=the categorical product) and function spaces ​$B^A$ (=internal, setty realizations of the arrow class from $A$ to $B$, which may be written ​$A \to B$) A theorem of sets is that the function space A theorem of sets is that the function space - $​(A\times B) \to C$ + $(A\times B) \to C$ is isomorphic to is isomorphic to - $​(B\times A) \to C$ + $(B\times A) \to C$ as well as as well as - $​A \to C^B$ + $A \to C^B$ and and - $​B \to C^A$ + $B \to C^A$ E.g. for A=B=C the reals the first space contains E.g. for A=B=C the reals the first space contains - $​\langle a,b \rangle \mapsto \sin(a)+3b ​$ + $\langle a,b \rangle \mapsto \sin(a)+3b ​$ which you can systematically map to the function which you can systematically map to the function - $​\langle b,a \rangle \mapsto \sin(a)+3b ​$ + $\langle b,a \rangle \mapsto \sin(a)+3b ​$ in the second space, or the function in the second space, or the function - $​a \mapsto (b \mapsto \sin(a)+3b) ​$ + $a \mapsto (b \mapsto \sin(a)+3b) ​$ or or - $​b \mapsto (a \mapsto \sin(a)+3b) ​$ + $b \mapsto (a \mapsto \sin(a)+3b) ​$ The axioms of a topos have more than the sets as model, for example it provides an (intuitionistic logic), where the iso above means The axioms of a topos have more than the sets as model, for example it provides an (intuitionistic logic), where the iso above means Line 262: Line 262: Or you can take the classical identifications of the set theoretic operations as numerical operations. Forgetting what your finite sets are about, the above relation is the basic identity of numbers Or you can take the classical identifications of the set theoretic operations as numerical operations. Forgetting what your finite sets are about, the above relation is the basic identity of numbers - $​c^{a·b} = {c^a}^b ​$ + $c^{a·b} = {c^a}^b ​$ In the other direction, the relation In the other direction, the relation - $​c^{a+b} = c^a·c^b ​$ + $c^{a+b} = c^a·c^b ​$ provable in a topic, at the same time tells you for the categories of sets (where + is the disjoint/​tagged union) that the function space provable in a topic, at the same time tells you for the categories of sets (where + is the disjoint/​tagged union) that the function space - $​(A+B) \to C$ + $(A+B) \to C$ is iso (i.e. in bijection to) to is iso (i.e. in bijection to) to - $​(A\to C) \times (B\to C)$ + $(A\to C) \times (B\to C)$ In logic, In logic, „one of A or B being true already implies C“ „one of A or B being true already implies C“ Line 277: Line 277: „From A and A implies B follows B“ „From A and A implies B follows B“ being true guarantees you that the function space being true guarantees you that the function space - $(A\times B^A)\to B$ + $(A\times B^A)\to B$ isn’t empty isn’t empty Indeed, the evaluation function Indeed, the evaluation function - $​eval (a,f) := f(a)$ + $eval (a,f) := f(a)$ works no matter which sets A and B are. works no matter which sets A and B are.