tag:blogger.com,1999:blog-1682681146250196022017-06-24T20:35:41.845-04:00math, etc.(programming, logic, philosophy, and pizza)Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-168268114625019602.post-41845833282288686182013-05-28T20:27:00.000-04:002013-05-29T00:00:22.670-04:00A personal favorite of mine<div style="text-align: center;"><span style="background-color: white;">"since feeling is first</span></div><span style="background-color: white;"></span><br /><div style="text-align: center;"><span style="background-color: white;">who pays any attention</span></div><span style="background-color: white;"></span><br /><div style="text-align: center;"><span style="background-color: white;">to the syntax of things</span></div><span style="background-color: white;"></span><div style="text-align: center;"><span style="background-color: white;">will never wholly kiss you;</span></div><span style="background-color: white;"><div style="text-align: center;">wholly to be a fool</div><div style="text-align: center;">while Spring is in the world</div><div style="text-align: center;"><br /></div><div style="text-align: center;">my blood approves,</div><div style="text-align: center;">and kisses are a better fate</div><div style="text-align: center;">than wisdom</div><div style="text-align: center;">lady i swear by all flowers. Don't cry</div><div style="text-align: center;">—the best gesture of my brain is less than</div><div style="text-align: center;">your eyelids' flutter which says</div><div style="text-align: center;"><br /></div><div style="text-align: center;">we are for each other: then</div><div style="text-align: center;">laugh, leaning back in my arms</div><div style="text-align: center;">for life's not a paragraph</div><div style="text-align: center;"><br /></div><div style="text-align: center;">And death i think is no parenthesis"</div></span><br /><div style="text-align: center;"><br /></div><div style="text-align: center;">--- e. e. cummings</div><div><br /></div><div><br /></div><div><span style="color: red;"><b>Life is more than the form of its syntax</b></span>.</div>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-73835856178899186742012-01-12T22:23:00.001-05:002012-01-12T23:33:52.397-05:00Self-Description in MathematicsThe <a href="http://en.wikipedia.org/wiki/Foundations_of_mathematics">foundations of mathematics</a> is a strange, strange place - and not only because of philosophical disagreements on <a href="http://en.wikipedia.org/wiki/Constructivism_(mathematics)">constructivism</a>, <a href="http://katzdm.blogspot.com/2011/12/logic-and-godels-incompleteness.html">incompleteness</a> of logical systems, and <a href="http://en.wikipedia.org/wiki/Naive_set_theory">set-theoretic paradoxes</a> (although all of that is indeed weird). No, one of the strangest things about mathematics is its uncanny ability to describe <i>itself</i>.<br /><div><br /></div><div>Ideally, we like to think of the flow of mathematics almost as a <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">directed acyclic graph</a>: The <a href="http://en.wikipedia.org/wiki/Propositional_calculus">propositional calculus</a> extends to <a href="http://en.wikipedia.org/wiki/Predicate_logic">predicate logic</a>; <a href="http://en.wikipedia.org/wiki/Axiomatic_set_theory#Axiomatic_set_theory">set theory</a> builds on predicate logic; <a href="http://en.wikipedia.org/wiki/Order_theory">order theory</a>, <a href="http://en.wikipedia.org/wiki/Abstract_algebra">algebra</a>, and <a href="http://en.wikipedia.org/wiki/Topology">topology</a> build on set theory; <a href="http://en.wikipedia.org/wiki/Mathematical_analysis">analysis</a> builds on all of these. Where things get weird, however, is when things move <i>backwards</i> through this hierarchy. This can perhaps be seen no more clearly than in order theory, and in particular, <a href="http://en.wikipedia.org/wiki/Lattice_theory">lattice theory</a>.</div><div><br /></div><div>The following relationship exists:</div><div><ul><li>A lattice can be described as:</li><ul><li>A partial order in which each pair of elements has a unique <a href="http://en.wikipedia.org/wiki/Lattice_theory">infimum</a> and <a href="http://en.wikipedia.org/wiki/Supremum">supremum</a>.</li><li>An algebraic structure which consists of a set together with two operations, "<latex>\wedge</latex>" and "<latex>\vee</latex>" such that the operations obey laws of <a href="http://en.wikipedia.org/wiki/Associative_property">associativity</a>, <a href="http://en.wikipedia.org/wiki/Commutative_property">commutativity</a>, <a href="http://en.wikipedia.org/wiki/Idempotence">idempotence</a>, and <a href="http://en.wikipedia.org/wiki/Absorption_laws">absorption</a>.</li></ul><li>Algebraic structures are defined in terms of sets, the axioms of which are defined in terms of predicate and propositional logic.</li><li>Propositional logic, with its AND and OR operations, form a <a href="http://en.wikipedia.org/wiki/Distributive_lattice">distributive lattice</a> (specifically a <a href="http://en.wikipedia.org/wiki/Boolean_algebra">Boolean algebra</a>).</li></ul><div>So in other words, algebra and lattices are defined with the help of propositional calculus, lattices can be defined in terms of algebra, and propositional calculus can be defined in terms of algebraic lattices. It is amazing to me how mathematics is continually able to so gracefully "turn around" and, in a sense, define itself. Such self-reference has in <a href="http://en.wikipedia.org/wiki/Russel%27s_paradox">some cases</a> resulted in major philosophical difficulties, but in others, such as this one, all appears to work fine. How is it though that mathematics is able to adequately define structures more fundamental than those doing the defining? I personally believe that this exact phenomenon is symptom of mathematics being not a fundamental deductive science which guides the universe, but a careful, consistent, and beautiful language whose precision grants it power far-reaching enough even to predict events which have not yet come to pass (solar eclipses, weather patterns, etc). Interesting stuff, eh?</div><ul><ul></ul></ul></div>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-5140133774432649632012-01-11T14:23:00.000-05:002012-01-11T14:23:39.654-05:00Interesting note on the history of symbolic logicVery short blurb...While reading through a chapter of Stephen Kleene's "Mathematical Logic", I came across an interesting fact. The symbol in mathematical logical for "inclusive or" (<a href="http://en.wikipedia.org/wiki/Nonexclusive_disjunction">nonexclusive disjunction</a>) is traditionally expressed as "<latex>\vee</latex>" - that much I knew. What I <i>didn't</i> know is that this symbol is descendant from the Latin word for "inclusive or": <i><b>v</b>el</i>. Pretty cool stuff.Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-2043536281059125842012-01-07T00:30:00.005-05:002012-01-07T17:20:18.489-05:00The C++ Object ModelI've got a bunch of books lying around that I've never had a chance to thoroughly read through; every once in a while, I pick one up and read a chapter. Sometimes, like with "General Lattice Theory" by George Grätzer, I try to sprint through a chapter or two just to get a general introductory feel for a subject that I have not yet had much exposure to - after all, one cannot really hope to fully come to terms with an abstract subject matter without dedicating a reasonable amount of time to reading it and tirelessly working through some exercises. I feel that it's good to survey areas of science and engineering with which one has little familiarity, if only to receive a first taste for the material, to have something to contemplate and internalize for a few days, and most importantly, to humble oneself.<br><br>Two years ago, I acquired "Inside the C++ Object Model" by Stanley Lippman. The book is a little dated (it was published in 1996), but it remains fairly relevant nonetheless. Back in 2009, the book was more than a little beyond my ability to take in, but I have since then have had much experience with C++ and many of its bizarre features: Multiple inheritance, virtual base classes, pointers-to-member-functions, etc. Thoroughly exhausted with abstract mathematics (at least for a few days), I found myself wanting something a bit more concrete and decided to try my hand reading the book once more.<br><br>I have so far read only through the first chapter out of seven, but it has certainly been a pleasure. The book elucidates the truth behind several misconceptions about C++ and is ruthlessly, but necessarily, precise in its description of C++'s memory model for object-oriented programming. Lippman even takes the time to discuss the pros and cons behind alternative memory models which could achieve similar goals, and rationalizes why C++'s model is the way that it is.<br><br>C++ is something of an anomaly as a programming language. It's a systems language (yes it is, Steven!). It's an object-oriented language. It's a high-level language. It's a low-level language. It's procedural. It's generic. Hell, thanks to template-metaprogramming, it can even be functional! And yet every one of these adjectives comes with a caveat.<br><br><a href="http://katzdm.blogspot.com/2012/01/c-object-model.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-71534442762397349382012-01-05T16:42:00.000-05:002012-03-19T15:54:29.453-04:00Classification of Algebraic Structures (Reference)Below is an incomplete list of common algebraic structures together with a short definition. I've come to realize that I would've loved to have something like this when I was learning it all, so I figured I'd write one for others. I'll update this as I continue to learn. This list is by no means exhaustive, and I'm sure that others have probably done similar things elsewhere with greater success. This is simply partly for my own records and partly for those interested who might not otherwise have the motivation to find such a list on their own.<br><a href="http://katzdm.blogspot.com/2012/01/classification-of-algebraic-structures.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-90056516967163596962012-01-04T20:33:00.002-05:002012-01-07T17:23:37.675-05:00An Interesting View of DifferentiationI've never studied any <a href="http://en.wikipedia.org/wiki/Functional_analysis">functional analysis</a> (my background in traditional <a href="http://en.wikipedia.org/wiki/Mathematical_analysis">analysis</a> is not yet nearly strong enough), but I do find the topic quite interesting. It's partly due to its place at the convergence of <a href="http://en.wikipedia.org/wiki/Linear_algebra">Linear Algebra</a> and Analysis. It's partly because I love the notion of <a href="http://en.wikipedia.org/wiki/Function_space">function spaces</a>. It's partly because it plays a central role in some areas of physics which I find quite interesting. And it's partly (probably mostly) because it just seems so <i>exotic</i> that I can't help but be attracted to it.<br><br>Despite having never studied function spaces properly, I occasionally run into them in my readings. Today in particular, I was reading about <a href="http://en.wikipedia.org/wiki/Inner_product_space">inner product spaces</a>. I eventually came across the topic of <a href="http://en.wikipedia.org/wiki/Inner_product_space">Hilbert Spaces</a>, which are inner product spaces which are also <a href="http://en.wikipedia.org/wiki/Complete_metric_space">complete metric spaces</a> with respect to the <a href="http://en.wikipedia.org/wiki/Metric_(mathematics)">metric</a> induced by the <a href="http://en.wikipedia.org/wiki/Normed_vector_space">norm</a> implicit in the inner product. One way or another, this got me thinking about <a href="http://en.wikipedia.org/wiki/Differentiation_(mathematics)">derivatives</a> from a viewpoint very different from that usually presented in an undergraduate calculus course.<br><a href="http://katzdm.blogspot.com/2012/01/interesting-view-of-differentiation.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-19829518803695730192012-01-02T18:56:00.004-05:002012-01-07T17:24:48.008-05:00Implications of Godel's Theorems on a Physical "Theory of Everything"<div><i>Disclaimer: I'm no expert on physics. If I've mischaracterized anything in this article, please let me know so I can correct it.</i></div><div><br></div>I've been on something of a logic binge lately. For the past several days, I've had <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Godel's Incompleteness Theorems</a>, <a href="http://en.wikipedia.org/wiki/Paraconsistent_logic">Paraconsistent Logic</a>, and more floating through my head. I've always been interested as to what the Incompleteness Theorems mean for the notion of a physical <a href="http://en.wikipedia.org/wiki/Theory_of_everything">Theory of Everything</a>. After writing <a href="http://katzdm.blogspot.com/2011/12/logic-and-godels-incompleteness.html">my recent post</a> on the subject, I feel that I have a much more solid understanding of the Theorems now than I ever have before, thus I feel somewhat confident in revisiting this idea with a fresh perspective. I'm a bit tired, so I'll keep things pretty simple.<br><div><br></div><div>Godel's Theorems consider the inherent limitations of axiomatic systems, and the goal of a Theory of Everything certainly fits under this category. Theoretical physicists have for many years searched for a minimal set of all-guiding universal laws which underlie all physical phenomena. So far, this quest has met little success. According to the Incompleteness Theorems, there are two obvious possibilities: Either the axioms of the universe are incomplete or they are inconsistent - presumably, they are not both.<br><br></div><a href="http://katzdm.blogspot.com/2012/01/implications-of-godels-theorems-on.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-12114569202065808822012-01-01T17:37:00.000-05:002012-01-07T17:26:08.200-05:00Philosophical Digression on Paraconsistent LogicWhile reading about <a href="http://en.wikipedia.org/wiki/Godel%27s_incompleteness_theorems">Godel's Incompleteness Theorems</a> before writing <a href="http://katzdm.blogspot.com/2011/12/logic-and-godels-incompleteness.html">my post</a> on it, I encountered a strange idea: The notion of "<a href="http://en.wikipedia.org/wiki/Paraconsistent_logic">paraconsistent logic</a>". As I explain in my Godel post, the <a href="http://en.wikipedia.org/wiki/Principle_of_explosion">Principle of Explosion</a> states that "from a contradiction, all else follows"; if a formal theory is capable of expressing a contradiction, then both a statement <i>and</i> its negation can be used for proofs. This often leads to <i>all</i> statements being true in a theory. Such a theory is termed <b>inconsistent</b>.<br><br>But certainly not <i>all</i> contradictions lead to the principle of explosion! If I simultaneously believe, for instance, that an apple is both green and red, this will not lead me to the contradiction that a number can be both odd and even. Therefore, the Principle of Explosion applies only within the scope of what objects the contradiction speaks of (directly or indirectly). The study of <b>paraconsistent logic</b> considers the implications of having rigorous logic theories in which <i>some</i> contradictions are possible.<br><a href="http://katzdm.blogspot.com/2012/01/philosophical-digression-on.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-61956108597718149362011-12-29T20:44:00.000-05:002012-01-08T00:10:33.018-05:00Logic and Godel's Incompleteness Theorems<span style="font-family: inherit;">I've always been fascinated by the work of <span style="background-color: white; line-height: 19px;"><a href="http://en.wikipedia.org/wiki/Kurt_G%C3%B6del">Kurt Gödel</a>. It has always seemed to me that few human beings have ever successfully probed so deeply into the nature of the Universe. </span></span>G<span style="background-color: white; line-height: 19px;">ödel was among the foremost logicians of the early twentieth century movement of analytic philosophy and is most famous for his wide-reaching results, the <a href="http://en.wikipedia.org/wiki/Completeness_theorem">Completeness Theorem</a> and the <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Incompleteness Theorems</a>. </span><span style="line-height: 19px;">In particular, I will focus this post on the Incompleteness Theorems and attempt to explain their profound results, without diminishing their full power (and scope of applicability), in a manner accessible to those less familiar with formal logical reasoning. First, a little bit of history.</span><br><span style="line-height: 19px;"><br></span><br><span style="line-height: 19px;">Although in some ways, the roots of the Incompleteness Theorems can be traced back to the beginnings of mathematics, the relevant history begins in the nineteenth century with logicians such as <a href="http://en.wikipedia.org/wiki/Augustus_de_morgan">Augustus De Morgan</a>, <a href="http://en.wikipedia.org/wiki/George_boole">George Boole</a>, and <a href="http://en.wikipedia.org/wiki/Charles_Sanders_Pierce">Charles Sanders Pierce</a> who gave birth to the notion of rigorous, <a href="http://en.wikipedia.org/wiki/Formal_logic">formal logic</a> in the modern sense. <a href="http://en.wikipedia.org/wiki/Grassmann">Herman Grassmann</a>, father of <a href="http://en.wikipedia.org/wiki/Linear_algebra">Linear Algebra</a>, showed that many properties of arithmetic can be reduced to the operations of succession and induction, which spurred the work of such illustrious scientists as <a href="http://en.wikipedia.org/wiki/Peano">Giuseppe Peano</a> and <a href="http://en.wikipedia.org/wiki/Gottlob_frege">Gottlob Frege</a>. Somewhat separately, <a href="http://en.wikipedia.org/wiki/Georg_cantor">Georg Cantor</a> developed the <a href="http://en.wikipedia.org/wiki/Naive_set_theory">theory of sets</a> while working in <a href="http://en.wikipedia.org/wiki/Topology">Topology</a>. All of this increase in rigor and precision, all of this focus on reducing mathematics to bare logic, led <a href="http://en.wikipedia.org/wiki/David_hilbert">David Hilbert</a>, one of the most prominent mathematicians of the early twentieth century, to in 1920 begin a program of research (now remembered as simply <a href="http://en.wikipedia.org/wiki/Hilbert%27s_program">"Hilbert's Program"</a>), the aim of which was to uncover a minimal set of complete, consistent logical axioms, from which all of mathematics could be derived - no small task indeed. The mathematicians of the philosophical school of <a href="http://en.wikipedia.org/wiki/Formalism_(mathematics)">Formalism</a> championed this noble pursuit, and for the next several years, mathematicians around the world chased this holiest of holy grails of science. G</span><span style="background-color: white; line-height: 19px;">ö</span><span style="line-height: 19px;">del's Incompleteness Theorems, proven by Kurt G</span><span style="background-color: white; line-height: 19px;">ödel, completely dismantled Hilbert's Program by showing that its intended goals were impossible to achieve.</span><br><a href="http://katzdm.blogspot.com/2011/12/logic-and-godels-incompleteness.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-84557781268330521272011-12-29T18:41:00.001-05:002011-12-29T18:41:08.008-05:00Interesting Note on the Development of Set TheoryI was reading Walter Rudin's "Principles of Mathematical Analysis" and came across the notion of a perfect set.<br /><br />"[A subset] <i>E</i> is <i>perfect</i> if <i>E</i> is closed and if every point of <i>E</i> is a limit point of <i>E</i>."<br /><br />Of course, this also implies that, since a set in a topological space is closed if and only if it contains all of its limit points, <i>E</i> is exactly equivalent to the set of its limit points. I found this rather interesting, so I searched Wikipedia for an article on "perfect sets" and was redirected to the article on "<a href="http://en.wikipedia.org/wiki/Perfect_set">Derived sets</a>".<br /><br />The article informed me that the <i>derived set</i> of a subset of a topological space is the set of its limit points (thus a perfect set is one equal to its own derived set). While I found this interesting, what I really found fascinating was a brief one-line note:<br /><br />"The concept was first introduced by Georg Cantor in 1872 and he developed set theory in large part to study the derived sets on the real line."<br /><br />I had always known that Cantor studied topology prior to developing set theory, but I had never been able to find the crucial link that led Cantor to develop the general theory of sets. Well, there you go. I love science history.Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-76884792490820911282011-12-28T20:05:00.002-05:002012-01-08T00:08:05.016-05:00Beyond the Cardinality of the RealsI feel that when studying mathematics (besides set theory), one typically encounters three types of sets.<br /><br /><ol><li>Finite sets</li><li><a href="http://en.wikipedia.org/wiki/Countable">Countably infinite</a> sets</li><li>Uncountable sets <a href="http://en.wikipedia.org/wiki/Bijection">bijective</a> to the reals</li></ol><div>But very rarely does one see any mention to cardinalities greater than <a href="http://en.wikipedia.org/wiki/Cardinality_of_the_continuum">that of the continuum</a>. I recently made a <a href="http://math.stackexchange.com/questions/93991/what-is-known-about-the-power-set-of-the-real-number-line/">post</a> on the Mathematics StackExchange website asking whether anybody could think of a useful mathematical object whose cardinality is greater than that of the continuum and what properties it might have. Although the members of that website shared some great insight, no really good examples were provided.</div><div><br /></div><div>I thought of one myself. If we take the uncountable Cartesian product of the set of real numbers:</div><latex>S = \prod\limits_{i \in \mathbb{R}}(\mathbb{R})</latex><br/>Then we can consider<i> S</i> to be the set of all <a href="http://katzdm.blogspot.com/2011/12/transfinite-sequences_25.html">transfinite sequences</a> from <i>R</i> into itself - in other words, the space of all functions on the real numbers. Since the cardinality of <i>S</i> is the cardinality of the continuum raised to itself, we have the following:<br /><latex>|S| = |\mathbb{R^{R}}| = B_{2}</latex><br/>(where <i>B</i> is a <a href="http://katzdm.blogspot.com/2011/12/aleph-numbers-vs-beth-numbers.html">Beth number</a>)<br />Thus the space of all functions on the real numbers is more numerous than the continuum, and we have our desired object. Though I have not studied <a href="http://en.wikipedia.org/wiki/Functional_analysis">functional analysis</a> (yet), I understand that such <a href="http://en.wikipedia.org/wiki/Function_space">function spaces</a> are of great importance to the subject. Pretty cool stuff.Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-79868272002313061972011-12-28T18:16:00.003-05:002012-01-07T17:28:24.690-05:00Useful Trick for Debugging Memory Leaks in C++ CodeThe summer of 2010 was fucking awesome. I was living on campus at my university, taking two classes (neither of which started before 6:00pm), and lived with my friends in the house of a fraternity that we didn't belong to. I was waking up at 7:00am every day to run and had obscene amounts of free time.<br><br>I was also building a 2D video game engine from scratch in my spare time. I didn't have any serious intentions for the project, but it was something to do and was a great learning experience. From that project, I learned how critical impeccable code organization is, I learned tricks such as using pointers to class member functions, and I had a blast doing it.<br><br>Somewhere along the line, I was reading about C++'s ability to overload the <span style="font-family: 'Courier New', Courier, monospace;">new</span> and <span style="font-family: 'Courier New', Courier, monospace;">delete</span> operators, and in the process came up with a great, simple trick for detecting memory leaks. By overloading the memory allocation operators to keep track of the total amount of memory allocated by the program at any given time, one need only check, at the conclusion of the program, how much memory remains allocated. If the value is anything greater than 0, you've got memory leaking.<br><a href="http://katzdm.blogspot.com/2011/12/useful-trick-for-debugging-memory-leaks.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com7tag:blogger.com,1999:blog-168268114625019602.post-1445305062088215792011-12-28T02:29:00.000-05:002011-12-28T12:16:52.751-05:00"Transfinite" vs "Infinite"Ask a third grader how large the set of alllll the numbers are and he'll cry out "infinity!"<br />Ask a set theorist and he'll very likely say "transfinite". <a href="http://en.wikipedia.org/wiki/Transfinite">Transfinite</a>? Really asshole? Come on...<br /><br />So why are the cardinalities of infinite sets referred to as "<b>transfinite cardinals</b>"? It turns out that the reason is somewhat historical. <a href="http://en.wikipedia.org/wiki/Georg_cantor">Georg Cantor</a>, the man responsible for placing set theory at the very foundation of all modern mathematics (and, therefore, science) was a deeply religious man who adhered to the idea that the one true god was the only "absolutely infinite" construct which could exist in the Universe; He is beyond any concept, whether it be a set or a world or a galaxy. This led Cantor to coin the term "transfinite" to describe the notion of a quantity which is not finite, but which is not the absolute infinity which he believed could only describe God - it is somewhere in between. It is the naturals; it is the reals; it is every subsequent <a href="http://en.wikipedia.org/wiki/Power_set">power set</a> of these sets, etc.<br /><br />At first glance, the matter seems trivial at best and childish at worst, especially to those deeply skeptical of religion. But one must be careful to look at the perspective of the time: <a href="http://en.wikipedia.org/wiki/Cantor%27s_theorem">Cantor's Theorem</a>, which directly implies that <i>there are an infinite amount of successively larger infinities</i>, was exotic. More than exotic. Ludicrous. Insane. Heretical to the omnipresence, omnipotence, and omniscience of God. A challenge - a <b><i>provably correct</i></b> challenge! - to the very fabric of how human beings understand the notion of abstract quantity, and, by extension, mathematics, science, philosophy, ontology, and the Universe as a whole. I find it reasonable that Cantor would draw a distinction between the hierarchy of infinities and the "absolute infinity" which he believed to be only attainable by God.<br /><br />Even if the notion of God is removed, however, the question remains relevant. What is the "largest" object which can be constructed while remaining logically consistent with the rest of mathematics? Does such a construction exist? If so, should "less numerous" infinities, such as the cardinality of the natural numbers, still be titled "infinite"? Should an infinite set be one which always contains more elements, or should it be defined as a set which contains <i>all</i> elements? Can such a set exist? Can an infinite set exist <i>at all</i> in the physical world beyond the abstract universe of mathematical thought?<br /><br />Answers are sought to many of these questions within the domain of <a href="http://en.wikipedia.org/wiki/Large_cardinals">large cardinal theory</a>, and although they admittedly rarely come into practical consideration in any remotely applicable area of mathematics, it is nonetheless instructive to consider them, if only to feel a bit humble and to realize just how fucked up and confused the foundations of mathematics and science remain.Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-9259030490604241282011-12-28T01:39:00.001-05:002012-01-07T17:30:13.393-05:00Concepts and Axioms in C++C++11, the most recently published standard for the world's <a href="http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html">third most popular</a> programming language, is admittedly a little bit of a disappointment to me. For years, one of the <i>big</i> features that were supposed to be added to the standard was <b>concepts</b>. Suppose I'm writing a function in C++ for a binary search tree.<br><br><span style="font-family: 'Courier New', Courier, monospace;"><b>class</b> bst_node</span><br><span style="font-family: 'Courier New', Courier, monospace;"><b>{</b></span><br><span style="font-family: 'Courier New', Courier, monospace;"> <b>int</b> value;</span><br><span style="font-family: 'Courier New', Courier, monospace;"> ...</span><br><span style="font-family: 'Courier New', Courier, monospace;"><b>};</b></span><br><span style="font-family: 'Courier New', Courier, monospace;"><b><br></b></span><br><span style="font-family: inherit;">But what if I want to have a binary tree which can hold a </span><span style="font-family: 'Courier New', Courier, monospace;">bool</span><span style="font-family: inherit;"> instead? Need I re-code the whole class? Need I make some complicated hierarchy of inheritance? Need I use the dreaded C </span><span style="font-family: 'Courier New', Courier, monospace;">void*</span><span style="font-family: inherit;"> type? </span><span style="font-family: inherit;">Templates to the rescue!</span><br><a href="http://katzdm.blogspot.com/2011/12/concepts-and-axioms-in-c.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-71452377210596275582011-12-27T02:27:00.001-05:002012-01-08T00:00:50.760-05:00Aleph Numbers vs. Beth Numbers<div><i>Note: Since the Google Chart API does not seem to support the Hebrew "<a href="http://en.wikipedia.org/wiki/Bet_(letter)">Beth</a>" character, I will instead use the letter "B" where that character would ordinarily appear.</i></div><br><div><br></div>The difference between <a href="http://en.wikipedia.org/wiki/Aleph_number">Aleph Numbers</a> and <a href="http://en.wikipedia.org/wiki/Beth_number">Beth Numbers</a> is not one that I ever understood. From what I could tell, <br><latex>\aleph_{i}=B_{i}</latex><br>and that was that. Both represent cardinalities of infinite sets. The first such number of each system is the countable infinity, the size of the natural numbers. So what's the difference?<br><div><br>Well, that depends whether you subscribe to belief in the <a href="http://en.wikipedia.org/wiki/Continuum_hypothesis">Continuum Hypothesis</a>, and I am sincere in calling it a belief. The Continuum Hypothesis is the somewhat unresolved statement that there can be no set whose cardinality is strictly greater than the cardinality of the natural numbers and strictly less than the cardinality of the real numbers. The work of <a href="http://en.wikipedia.org/wiki/Kurt_G%C3%B6del">Kurt G</a><span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><a href="http://en.wikipedia.org/wiki/Kurt_G%C3%B6del">ödel</a> and <a href="http://en.wikipedia.org/wiki/Paul_Cohen_(mathematician)">Paul Cohen</a> in the 1900s proved that the Continuum Hypothesis cannot be decided - that is, cannot be proven or disproven - within the usual formulation of axiomatic set theory used in mathematics, <a href="http://en.wikipedia.org/wiki/Zfc">Zermelo-Fraenkel Set Theory</a> (regardless of whether one includes the <a href="http://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of Choice</a>).</span><br><span style="background-color: white; line-height: 19px; text-align: -webkit-auto;"><br></span><br></div><a href="http://katzdm.blogspot.com/2011/12/aleph-numbers-vs-beth-numbers.html#more">Read more »</a>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-42033921803200910612011-12-26T01:29:00.000-05:002012-01-07T23:56:07.182-05:00Transfinite SequencesSequence - Given a set <i>X</i>, a sequence is an ordered list of elements of <i>X</i> {x1, x2, x3, ...}. If the number of elements of the sequence is finite, the sequence is referred to as a "finite" sequence. A sequence can also be infinite.<br /><div><br /></div><div>More formally, a sequence is, strictly speaking, a function from some subset of the natural numbers <i>N</i> into some set <i>X</i>:</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span><br /><latex>f:M \rightarrow X,\ M \subseteq \mathbb{N}</div></latex><div><i style="white-space: pre;"><br /></i></div><div>But wait a moment! What if we want for our function to range over a number of values which is greater than that in <i>N</i>? What if we want an <i>uncountable</i> sequence of numbers? What would that even mean?!</div><div><br /></div><div>It turns out that mathematics <i>does</i> in fact give the machinery needed to handle this, although one must dig into set theory to find it. The notion of <b>Transfinite Sequences</b> allows for a sequence to be constructed whose length is that of <i>any </i>ordinal on <i>any</i> well-ordered set. If we accept the <a href="http://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of Choice</a>, then the Well Ordering Theorem holds (or visa versa; the axiom and the theorem are in fact logically equivalent) and we can produce a so-called "transfinite sequence" on <i>any</i> set, including the reals. The notions of <b>Transfinite Induction</b> and <b>Transfinite Recursion</b> also help to properly extend their respective notions which are classically limited to sets of countable order. Pretty cool stuff if you think about exactly what a sequence really is. Also sheds some light on just how extreme the consequences of the Axiom of Choice really are. On a side-note, I have only just begun reading on the topic of transfinite sequences today, so if something in this post is inaccurate, please feel free to correct me.</div>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0tag:blogger.com,1999:blog-168268114625019602.post-22638012215854118922011-12-25T20:33:00.000-05:002011-12-27T09:41:06.960-05:00Introduction<span>Hi. My name's Dan. I'm a student at Stevens Institute of Technology with a profound curiosity for the rigorous sciences: Logic, Mathematics, and Computer Science (and a slowly but surely incubating interest in Physics). I've never been much of a blogger before, but I've figured that I'll give it a try.</span><div><span><br /></span></div><div><span>My intention is to use this blog as a sort of journal to record fascinating things that I learn, whether they be about set theory, C++, topology, automata theory, the history of twentieth century mathematics, Haskell, or whatever else piques my interest. I'll start things off by making a few posts about what I've been reading about over Winter break these past few days. The length of posts will certainly vary, and I'll try to make them accessible to those unfamiliar with the technical material (though in some cases I make no promises).</span></div><div><span><br /></span></div><div><span>Also...Merry Christmas.</span></div>Daniel Katzhttps://plus.google.com/111024983721064942993noreply@blogger.com0