Hideous Humpback FreakSoftware and Powerlifting
http://hideoushumpbackfreak.com/
http://www.rssboard.org/rss-specificationBlogEngine.NET 3.1.0.1en-UShttp://hideoushumpbackfreak.com/opml.axdhttp://www.dotnetblogengine.net/syndication.axdDale AlleshouseHideous Humpback Freak0.0000000.000000Diagonalization?<div id="AdnTop"><div class="AdnTopLeft" style="float:left"></div><div class="AdnTopRight" style="float:right"></div><div style="clear:both"></div></div><p>The goal of this article is to provide laymen with a conceptual understanding of diagonalization. Those interested in a deep dive full of mathematical jargon will be sorely disappointed. However, this piece is the perfect resource for a general understanding of the topic devoid of the more arcane details. Unlike the majority of my writing, this is not directly applicable to the daily responsibilities of software professionals. It is purely an endeavor to satisfy intellectual curiosity. <h4>Why?</h4> <p>The impetus for this writing comes from a colleague who contacted me after reading my blog series on Set Theory (<a href="http://hideoushumpbackfreak.com/post/2017/02/05/Just-Enough-Set-Theory-Set-Theory-Defined-(Part-1-of-3)">Set Theory Defined</a>, <a href="http://hideoushumpbackfreak.com/post/2017/02/19/Just-Enough-Set-Theory-Set-Operations-(Part-2-of-3)">Set Operations</a>, <a href="http://hideoushumpbackfreak.com/post/2017/02/22/Just-Enough-Set-Theory-When-Sets-Collide-(Part-3-of-3)">When Sets Collide</a>). The posts made pithy mention of Cantor’s diagonalization proof with implications on infinite cardinality. My friend’s search for a concise explanation proved to be unfruitful. The conversation naturally progressed toward Alan Turing’s seminal paper: <i>On Computable Numbers,</i> which also employs a diagonalization proof. Cantor and Turing both played a major part in shaping computer science. Therefore, although it is not likely that the majority of software professionals will ever employ diagonalization, it’s a crucial part of computing history. <h4>What Are We Trying to Prove?</h4> <p>Diagonalization is a mathematical proof demonstrating that there are certain numbers that cannot be enumerated. Stated differently, there are numbers that cannot be listed sequentially. Consider all the numbers on the number line as shown in <i>Figure One – Number Line</i>.</p> <p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=4-1.png"><img title="4-1" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="4-1" src="http://hideoushumpbackfreak.com/image.axd?picture=4-1_thumb.png" width="404" height="106"></a></p> <p>First consider the set of positive whole numbers including zero. These are known as <i>natural</i> or <i>counting</i> numbers and are denoted as `\mathbb{N}`. Most kindergarten curriculum teaches how to enumerate this set: starting with zero add one to the current number to get the next number ad infinitum. <p>Adding negative numbers to `\mathbb{N}` produces the set of integers denoted by `\mathbb{Z}`. Again, this set is also easy to enumerate by simply listing it as follows: `0, 1, -1, 2, -2, 3, -3, …`. <p>Now consider expanding on `\mathbb{Z}` by adding fractions to create the set of rational number denoted as `\mathbb{Q}`. The term rational signifies that a number can be expressed as a ratio such as `1/2` or `23/345`. These numbers fit between the whole number on the number line and there is an infinite amount of fractional numbers between each set of natural numbers. That is to say, regardless of the location of two rationals on the number line, it’s always possible to find another number between them. With some ingenuity, these numbers can also be enumerated in several different ways. Enumerating rational numbers, while fascinating, is beyond the scope of this post. The reader is encouraged to either just accept my word as fact or do research. <a href="http://www.cs.utexas.edu/users/sandip/acl2-09/presentations/rationals-talk.pdf">Here</a> is a good place to start. <p>Although it seems as if we’ve run out room on the number line, that isn’t actually the fact. There is another class of number that has been baffling mathematicians throughout the ages: irrational. It’s a bit perplexing, but irrationals fit between rationals on the number line (no matter how many times I think about that, it amazes me). Grade school curriculum typically introduces the concept with renowned numbers such as `\pi` or `e`. These are numbers that cannot be expressed as a ratio. The decimal representation consists of an infinite series of digits with no repeating pattern. Any calculations involving irrationals are approximations because it’s impossible to express them in a finite context. Adding these to `\mathbb{Q}` produces the set of real numbers denoted as `\mathbb{R}`. Irrational numbers are the target of our inquisition. <p>As a matter of note, the set of irrational numbers can be further divided into the sets of algebraic and transcendental numbers. Algebraic numbers can in fact be enumerated. However, this is a bit of minutia that isn’t really necessary for understanding diagonalization. Once again, the curious reader is encouraged to rely on Google for further inquiry. <p>The question is, how is it possible to prove that irrational numbers are not enumerable. With an understand of the problem, we can turn our attention to the solution which is diagonalization. <h4>Reductio Ad Absurdum</h4> <p>Diagonalization is a type of proof known as reductio ad absurdum which is Latin for reduction to absurdity. It is common amongst mathematicians and philosophers alike. The premise is to first assume a proposition is true and then disprove it via deductive reasoning thus reducing it to an absurd conclusion. <p>One popular example of a reductio ad absurdum proof is that there is no smallest fractional number. Assume there is such a number: it can be divided by two to create a smaller number. Therefore, the original assumption is absurd. Another illustration is an alibi. First assume the suspect committed the crime. If the accused is known to be at a different location when the crime took place, it’s absurd to assume that they were also at the scene of the crime. <h4>Diagonalization</h4> <p>Having addressed all the introductory trivialities, it’s time to get to the point. The diagonalization proof is as follows. First assume that it is possible to enumerate all irrational numbers. If this is true, it should be impossible to devise a number that is not included in this list. Examine <i>Figure Two – Diagonalization</i> and stretch the mind to imagine that this is in fact the list of all irrational numbers: the list is infinitely long and each number expands on endlessly. Next, draw a diagonal line down the center of the list and write down the resulting infinite number. In this case, the number is `0.13579135…`. Next add 1 to each digit expect in the case of nine which becomes a zero. This results is the number `0.24680246…`. Is this number contained in the list? It’s obviously not the first number because the first digit does not match. The same holds true for the second number because the second digit has to be different. Continue this line of logic for every number and it’s obvious that the devised number is not in the list. The reader should take a few minutes to let that sink in.</p> <p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=4-2_2.png"><img title="4-2" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="4-2" src="http://hideoushumpbackfreak.com/image.axd?picture=4-2_thumb_2.png" width="404" height="410"></a></p> <p>Keep in mind, this is purely a thought experiment. Obviously, <i>Figure Two – Diagonalization</i> is not an infinite list and each number is not truly irrational. It’s impossible to construct such a list in a finite context. However, the line of logic holds true. <p>It is common to wonder why diagonalization does not apply to `\mathbb{Q}`. The concise answer is that those numbers have finite digits and irrationals do not. <h4>Implications</h4> <p>Accepting that the diagonalization proof is valid, it has some profound implications. At first glance, it’s difficult to understand how the fact that it’s impossible to enumerate irrational numbers has bearing on the world in any way. However, many people have derived some amazing conclusions. <a href="https://en.wikipedia.org/wiki/Cantor's_diagonal_argument">Cantor</a> showed that there are in fact multiple infinities. <a href="https://en.wikipedia.org/wiki/Turing's_proof">Turing</a> used diagonalization to prove the limits of computability. It’s even been employed by philosophers to prove that there are an insufficient number of proofs to prove all the truths in the universe. More concisely, some truths are unproveable. The implications lead down an exceedingly dark and deep rabbit hole. <h4>Conclusion</h4> <p>Diagonalization is a reductio ad absurdum proof that demonstrates the impossibility of enumerating irrational numbers. It is relatively easy for non-mathematicians to understand. While only tangentially related to software engineering, it’s a fascinating concept that sheds light on the foundations of computing and indeed the world. <p>As always, thank you for taking the time to read this article. Please feel free to contact me with any questions or concerns. <div id="AdnBottom"><div class="AdnBottomLeft" style="float:left"></div><div class="AdnBottomRight" style="float:right"></div><div style="clear:both"></div></div>
http://hideoushumpbackfreak.com/post/2017/02/24/Diagonalization
dalealleshouse@gmail.comhttp://hideoushumpbackfreak.com/post/2017/02/24/Diagonalization#commenthttp://hideoushumpbackfreak.com/post.aspx?id=96503e93-490e-4255-bdec-be949c9365b0Fri, 24 Feb 2017 18:49:33 +0000SoftwareMathSetTheoryComputerSciencedalealleshousehttp://hideoushumpbackfreak.com/pingback.axdhttp://hideoushumpbackfreak.com/post.aspx?id=96503e93-490e-4255-bdec-be949c9365b02http://hideoushumpbackfreak.com/trackback.axd?id=96503e93-490e-4255-bdec-be949c9365b0http://hideoushumpbackfreak.com/post/2017/02/24/Diagonalization#commenthttp://hideoushumpbackfreak.com/syndication.axd?post=96503e93-490e-4255-bdec-be949c9365b0Just Enough Set Theory – When Sets Collide (Part 3 of 3)<div id="AdnTop"><div class="AdnTopLeft" style="float:left"></div><div class="AdnTopRight" style="float:right"></div><div style="clear:both"></div></div><p>Welcome to the final installment of this three-part series on set theory. The first piece, <a href="http://hideoushumpbackfreak.com/post/2017/02/05/Just-Enough-Set-Theory-Set-Theory-Defined-(Part-1-of-3)">Set Theory Defined</a>, detailed requisite foundational knowledge. The second article, <a href="http://hideoushumpbackfreak.com/post/2017/02/19/Just-Enough-Set-Theory-Set-Operations-(Part-2-of-3)">Set Operations</a>, outlined some beneficial set algorithms. This post develops the concepts laid out in the first two; therefore, it is highly recommended that readers begin there. <p>Individual sets have many useful properties; however, preforming operations on multiple sets provides even greater utility. This piece outlines four such operations. Each operation provides a concise means for addressing common programming problems that virtually all software professionals encounter. There is a brief description of each from a mathematical perspective followed by JavaScript (ES6) code excerpts demonstrating how to apply theory to real world scenarios. <p><b>NOTE</b>: All code samples are written in ES6 and are therefore not likely to execute directly in a browser. The best option is to use Node or transpile the excerpts using either <a href="https://babeljs.io/">Babel</a> or <a href="https://www.typescriptlang.org/">TypeScript</a>. The working code is available on <a href="https://github.com/dalealleshouse/settheory">GitHub</a> along with execution instructions. <h4>Union</h4> <p>The union of two sets is a set containing the distinct elements from both sets. `\cup` is the mathematical symbol for a union and the union of sets `A` and `B` is denoted as `A \cup B`. An expanded way of representing the union relationship is `\{x| x \in A \vee x \in B\}`, which means every element contained in `A` OR (`\vee`) `B`. <i>Figure One – Union</i> depicts two sets with three elements each. The union is a set with five elements because one item, three, is shared and union returns distinct values. The Venn diagram shows the relationship graphically.</p> <p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure3-1.png"><img title="figure3-1" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure3-1" src="http://hideoushumpbackfreak.com/image.axd?picture=figure3-1_thumb.png" width="404" height="405"></a></p> <p>Generating the union of two sets is quite easy in ES6 as the code below illustrates.</p><pre class="brush: js;">const A = new Set([1, 2, 3]);
const B = new Set([3, 4, 5]);
const union = new Set([...A, ...B]);
// union = [1,2,3,4,5];</pre>
<p>The astute reader will notice that there’s some legerdemain afoot. The code above uses the ES6 Set data structure instead of standard JavaScript arrays. Set holds only unique elements by ignoring add operations for new values that match existing ones. The algorithm is as easy as concatenating the two sets without the concern of distinct elements. If the code was using standard arrays, there would have to be logic to remove duplicated items. Luckily, converting between sets and arrays is virtually effortless. </p><pre class="brush: js;">const setDataStructure = new Set([1, 2, 3]);
const arrayDataStrcture = Array.from(setDataStructure);</pre>
<p>The problem with the code above is that it’s a rare requirement to union sets containing primitive values. Software engineering is seldom that straightforward. A more realistic scenario is calculating the union between two sets of complex objects where equality becomes problematic. Unlike primitive variables, objects with identical values are not equal because they compare by reference. This abrogates the Set trick from earlier. Suppose the requirement is to compute all bug reports currently in process across two teams and it’s possible that both teams are working on the same bugs simultaneously. The code below demonstrates a solution by first concatenating the two sets and then removing duplicates using the filter method introduced in the last article. Notice the only equality check is via the Id. Obviously, this won’t work for every scenario and depending on the size of the sets and performance requirements it is possible to write generic deep equality methods (or use a library like underscore).</p><pre class="brush: js;">const teamABugs = [
{ id: 1, name: "Screen Explodes" },
{ id: 2, name: "Keyboard Burts into Flames" },
{ id: 3, name: "Submit button off by 1 pixel" }];
const teamBBugs = [
{ id: 5, name: "Randomly Dials Russian Hackers" },
{ id: 6, name: "Publishes CC info to the www" },
{ id: 3, name: "Submit button off by 1 pixel" }];
const union = [...teamABugs, ...teamBBugs]
.filter((x, index, array) => array.findIndex(y => y.id == x.id) == index);</pre>
<h4>Intersection</h4>
<p>The intersection of two sets is a set containing distinct shared elements. `A \cap B` is the mathematical representation of a union and the expanded notation is `\{x|x \in A \wedge x \in B \}`. Stated differently, the intersection of set `A` AND (`\wedge`) `B` is every element contained in `A` AND `B`. <i>Figure Two – Intersection</i> depicts the relationship showing the union of `A` and `B` to be a singleton set containing only the number three. Once again, the Venn diagram portrays the relationship.</p>
<p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure3-2.png"><img title="figure3-2" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure3-2" src="http://hideoushumpbackfreak.com/image.axd?picture=figure3-2_thumb.png" width="404" height="405"></a></p>
<p>Much like union, finding the intersection of two sets using the Set data structure and primitive types is easy. The code below shows how it’s a matter of using the filter method to check to see if an item is also stored in the other set.</p><pre class="brush: js;">const A = new Set([1, 2, 3]);
const B = new Set([3, 4, 5]);
const intersect = [...A].filter(x => B.has(x));
// intersect = [3];</pre>
<p>The code above is a bit fanciful. Consider instead a role protected resource. Possessing any one of many roles allows users to access said resource. Users each have a set of associated roles. There are a few different ways to achieve this, but finding the intersection between the user’s roles and the resource’s required roles is the most manageable. See the code below.</p><pre class="brush: js;">const resourceRoles = [
{ id: 1, name: "Administrator" },
{ id: 2, name: "Super User" }];
const user = { id: 314, name: "Edsger Dijkstra", roles: [
{ id: 1, name: "Administrator" },
{ id: 2, name: "User" }] }
const hasAccess = resourceRoles
.filter(x => user.roles.find(y => y.name == x.name)).length > 0;</pre>
<p>All of the caveats about equality described in the Union section also apply here. It’s something programmers need to be cognizant of.
<h4>Difference</h4>
<p>The difference of two sets is sometimes known as the relative complement; both nomenclatures are interchangeable. The concept is simple, the difference is a set made up of the items that are left over after removing the intersection of another set. Otherwise stated, all of the items in set `B` that do not exist in set `A`. Mathematically, this is represented as `\{x|x \in B \wedge x \notin A\}` or the shortened version which is `B\\A`. <i>Figure Three – Difference</i> shows the difference between `B` and `A` to be a set containing four and five. Just as above, there is a representative Venn diagram.</p>
<p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure3-3.png"><img title="figure3-3" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure3-3" src="http://hideoushumpbackfreak.com/image.axd?picture=figure3-3_thumb.png" width="404" height="405"></a></p>
<p>As an aside, there is also an absolute compliment which is somewhat similar; however, it is outside the scope of this article.
<p>Finding the difference of sets is almost identical to finding the intersection as the code below demonstrates. The only variation is that the predicate passed to the filter method is negated.</p><pre class="brush: js;">const A = new Set([1, 2, 3]);
const B = new Set([3, 4, 5]);
const difference = [...B].filter(x => !A.has(x));
// difference = [4,5];</pre>
<p>Again, a more realistic example is in order. Image that there is a set of actions that must be completed and a set of actions a user has completed. Finding the difference is an easy way to determine if all required actions are complete.</p><pre class="brush: js;">const requiredActions = [
{ id: 1, name: "Electronic Signing" },
{ id: 2, name: "Submission Form" },
{ id: 3, name: "Payment" }];
const userActions = [
{ id: 1, name: "Electronic Signing" },
{ id: 2, name: "Submission Form" }];
const complete = requiredActions
.filter(x => !userActions.find(y => y.name == x.name)).length === 0;
// complete = false
</pre>
<h4>Cartesian Product</h4>
<p>The Cartesian product of two sets is a set of ordered pairs that contain all possible combinations of elements in the two sets. The mathematical representation is `A \times B`. The expanded notation is `\{(a,b)|a \in A \wedge b \in B\}` which means an ordered pair consisting of every element in `A` AND (`\wedge`) every element in `B`. <i>Figure Four – Cartesian Product</i> demonstrates the concept. As a matter of importance, unlike standard products, the Cartesian product is not commutative. Stated mathematically, `A \times B \ne B \times A`. Switching the order of statement will change the order of the pairs.</p>
<p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure3-4.png"><img title="figure3-4" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure3-4" src="http://hideoushumpbackfreak.com/image.axd?picture=figure3-4_thumb.png" width="404" height="381"></a></p>
<p>The Cartesian product is useful for combinatorics problems. A common example is simulating a deck of cards. Instead of specifying all the cards explicitly in code, it’s easier to define the suits and values as two separate sets and then take the Cartesian product to get the entire deck. See the code below.</p><pre class="brush: js;">const suits = ['Diamond', 'Spade', 'Heart', 'Club'];
const values = ['Ace', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'Jack', 'Queen', 'King'];
const cards = suits.reduce((acc, x) => [...acc, ...values.map(y => [x, y])], []);
// Alternatively, it’s possible to return the ordered pair as an object instead of an array
// const cards = suits.reduce((acc, x) => [...acc, ...values.map(y => { return { suit: x, value: y } })], []);</pre>
<p>This code should be starting to look familiar because all the samples make heavy use of the map, reduce, and filter methods. Using ES6, these methods have great utility for mimicking mathematical set operations. Because the code above is similar to previous examples, it doesn’t require further explanation.
<h4>Why Stop at Two?</h4>
<p>Up to this point, all the exhibited set operations employ two sets. However, this is for the sake of brevity. Each operations can act on as many sets as required. For instance, `A \cup B \cup C` is perfectly valid as is `A \times B \times C`. The enthused reader should solidify his/her learning by expanding each code sample to use additional sets.
<h4>Real World Applications</h4>
<p>This series demonstrated how set theory is applied to data structures and demonstrated some novel uses for set operations in order create efficient algorithms. However, this is only a meager representation of all the many and varied applications for software engineering. Relational databases make heavy use of set theory for defining data structure and constructing data queries. In fact, SQL is essentially a set notation. There are several instances in language theory and design where strings are realized as sets and set operations are performed on them. Another prolific use is in computer graphics where points on a plane are treated as sets. The list of applications is considerable. It’s a body of knowledge that no software professional should forsake.
<h4>Conclusion</h4>
<p>Thus concludes this three-part series on set theory. Hopefully, the reader has gained a high-level understanding as well as enough practical knowledge to apply the learning forthwith. The first article outlined the basics and introduced the concept of set mapping. Empty sets, cardinality, subsets, summation, and power sets were introduced in the second piece. Finally, this post presented operations involving more than one set including unions, intersections, differences, and Cartesian products. The method was to first introduce the ideas mathematically and then demonstrate how to apply them using ES6. These concepts should not be considered optional for software professionals because set theory is ubiquitous in computer science.
<p>As always, thank you for reading and please feel free to contact me with questions. I’m also happy to create more in depth posts upon request.</p><a style="display: none" href="http://www.codeproject.com/script/Articles/BlogFeedList.aspx?amid=608087" rel="tag">CodeProject</a><div id="AdnBottom"><div class="AdnBottomLeft" style="float:left"></div><div class="AdnBottomRight" style="float:right"></div><div style="clear:both"></div></div>
http://hideoushumpbackfreak.com/post/2017/02/22/Just-Enough-Set-Theory-When-Sets-Collide-(Part-3-of-3)
dalealleshouse@gmail.comhttp://hideoushumpbackfreak.com/post/2017/02/22/Just-Enough-Set-Theory-When-Sets-Collide-(Part-3-of-3)#commenthttp://hideoushumpbackfreak.com/post.aspx?id=fde79f15-1887-41db-9e70-d77b64aa7b18Wed, 22 Feb 2017 17:51:37 +0000SoftwareComputerScienceMathSetTheorydalealleshousehttp://hideoushumpbackfreak.com/pingback.axdhttp://hideoushumpbackfreak.com/post.aspx?id=fde79f15-1887-41db-9e70-d77b64aa7b182http://hideoushumpbackfreak.com/trackback.axd?id=fde79f15-1887-41db-9e70-d77b64aa7b18http://hideoushumpbackfreak.com/post/2017/02/22/Just-Enough-Set-Theory-When-Sets-Collide-(Part-3-of-3)#commenthttp://hideoushumpbackfreak.com/syndication.axd?post=fde79f15-1887-41db-9e70-d77b64aa7b18Just Enough Set Theory – Set Operations (Part 2 of 3)<div id="AdnTop"><div class="AdnTopLeft" style="float:left"></div><div class="AdnTopRight" style="float:right"></div><div style="clear:both"></div></div><p>Welcome to the second installment of this three-part series on set theory. The first piece, <a href="http://hideoushumpbackfreak.com/post/2017/02/05/Just-Enough-Set-Theory-Set-Theory-Defined-(Part-1-of-3)">Set Theory Defined</a> (recently updated with code samples), detailed requisite foundational knowledge. It is highly recommended that readers begin there if they haven’t already. <p>The first piece in this series introduced sets and exhibited how ES6 arrays are analogous to them. It also depicted how to transform, or map, a set into a related set. This post expands on set theory by probing into set operations. <p><b>NOTE</b>: All code samples are written in ES6 and are therefore not likely to execute directly in a browser. The best option is to use Node or transpile the excerpts using either <a href="https://babeljs.io/">Babel</a> or <a href="https://www.typescriptlang.org/">TypeScript</a>. The working code is available on <a href="https://github.com/dalealleshouse/settheory">GitHub</a> along with execution instructions. <h3>Empty Sets</h3> <p>Empty sets are a rather mundane topic, but nonetheless worth mentioning. As the name implies, they are simply sets that have no elements. They are also commonly referred to as null sets. Mathematically, empty sets are represented as either `\emptyset` or `{}`. The concept relates to empty arrays in software. <h3>Cardinality</h3> <p>The term cardinality sounds impressive; however, it’s simply the number of elements in a set. The mathematical representation of a set with three elements is as depicted in <i>Figure One – Cardinality</i>. </p> <p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure2-1.png"><img title="figure2-1" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure2-1" src="http://hideoushumpbackfreak.com/image.axd?picture=figure2-1_thumb.png" width="362" height="177"></a></p> <p>In JavaScript, the cardinality of an array is its length. See the code below. </p><pre class="brush: js;">const someSet = [1, 2, 3, 4, 5];
const cardinality = someSet.length;
// cardinality = 5</pre>
<p>
<h3>Subsets</h3>
<p>Subsets are relatively easy to explain, yet have far reaching implications. A subset is a portion of a larger set. For instance, consider the set of all animals (`A` ). The set of all dogs (`D` ) is a subset of the animal set because although every animal is not a dog, every dog is an animal. The mathematical notation for subsets is as follows: `D\subseteqA`. Another way of mathematically expressing the subset relationship is `\forall x(x\inD->x\inA)`. That looks absurd, but the premise is that for any (`\forall`) element (`x`) in `D` , it is implied (`->`) that the element (`x`) also exists in `A`.</p>
<p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure2-2.png"><img title="figure2-2" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure2-2" src="http://hideoushumpbackfreak.com/image.axd?picture=figure2-2_thumb.png" width="362" height="175"></a></p>
<p>Subsets are often taught with Venn Diagrams. See <i>Figure Three – Venn Diagrams</i> for an example. Admittedly, this account of subsets is a bit prosaic. However, the final post in this series relies heavily on the concept so it bears belaboring the point. </p>
<p align="center"><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure2-3.png"><img title="figure2-3" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; padding-top: 0px; padding-left: 0px; display: inline; padding-right: 0px; border-top-width: 0px" border="0" alt="figure2-3" src="http://hideoushumpbackfreak.com/image.axd?picture=figure2-3_thumb.png" width="457" height="396"></a></p>
<p>ES6 has a built-in filter method on the array object that enables easy access to subsets. Filter takes a predicate as an argument. Recall from the first article that a predicate is a function that takes a single argument and returns a Boolean response. The filter method applies the predicate to each item in a set and creates a new set that includes the items where the predicate returned true. See the code below. </p><pre class="brush: js;">const animals = [
{name: "Tom", type: "Cat"},
{name: "Jerry", type: "Mouse"},
{name: "Pluto", type: "Dog"},
{name: "Scooby Doo", type: "Dog"}];
const dogs = animals.filter(a => a.type == "Dog");
// dogs = [{name: "Pluto", type: "Dog"}, {name: "Scooby Doo", type: "Dog"}]</pre>
<p>
<h3>Summation</h3>
<p>The term summation is a bit misleading because it implies simply adding elements together, however it’s a more powerful concept. Summation applies a function to each element of a set reducing it to a single value. `\sum_{x \in S}f(x)` is the mathematical notation representing the algorithm where `S` can be any set and `f(x)` can be any function. Consider <i>Figure Four – Summation</i>. Given the set `A`, each element in the set is multiplied by two and added together. </p>
<p><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure2-4.png"><img title="figure2-4" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; float: none; padding-top: 0px; padding-left: 0px; margin-left: auto; display: block; padding-right: 0px; border-top-width: 0px; margin-right: auto" border="0" alt="figure2-4" src="http://hideoushumpbackfreak.com/image.axd?picture=figure2-4_thumb.png" width="492" height="320"></a></p>
<p>ES6’s reduce method of the array object is comparable to summation. Aptly named, reduce applies a function to each member of a set reducing it to a single value. It accepts two arguments: a function and an optional starting value. The function accepts an accumulated value and the current item. The state of the accumulated value after all items are processed is the final return value. The code below is the same process detailed in <i>Figure Four – Summation</i>. </p><pre class="brush: js;">const someSet = [1, 2, 3];
const sum = someSet.reduce((acc, x) => acc + x * 2, 0);
// sum = 12</pre>
<p>Reduce is useful for many operations beyond mathematical functions. The code below utilizes it to extract email addresses from a set of users. </p><pre class="brush: js;">const users = [
{id: 1, email: "email@email.com"},
{id: 2, email: "email2@email2.com"},
{id: 3, email: "email3@email.com"}];
const emails = users.map(u => u.email).reduce((acc, x) => `${acc};${x}`);
// emails = "email@email.com;email2@email2.com;email3@email.com"</pre>
<p>
<p>This above doesn’t do the reduce method proper justice because its efficacy is virtually endless. There are many more options that are outside the scope of this feature. The reader is highly encouraged to find more information on <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce">Mozilla’s excellent JavaScript reference</a>.
<h3>Power Set</h3>
<p>Power sets are something every programmer has to deal with at some point in his/her career, even if they can’t formally identify them by name. In mathematical parlance, power sets are denoted as `P(A)`. A power set is the set of all subsets including the empty set and itself: more succinctly, all possible set combinations. A power set always contains `2^n` elements where `n` is the cardinality of the original set (`|P(A)|=2^(|A|)`).
<p>Power sets are difficult to conceptualize without an example. <i>Figure Five – Power Set</i> depicts a set with three elements. The power set is all possible combinations of the three elements. The result is a set with a cardinality of eight (`2^3`). </p>
<p><a href="http://hideoushumpbackfreak.com/image.axd?picture=figure2-5.png"><img title="figure2-5" style="border-left-width: 0px; border-right-width: 0px; background-image: none; border-bottom-width: 0px; float: none; padding-top: 0px; padding-left: 0px; margin-left: auto; display: block; padding-right: 0px; border-top-width: 0px; margin-right: auto" border="0" alt="figure2-5" src="http://hideoushumpbackfreak.com/image.axd?picture=figure2-5_thumb.png" width="502" height="182"></a></p>
<p>Unfortunately, there isn’t an innate JavaScript method for creating power sets. However, that’s an easy problem to overcome given some ingenuity. See the code below. </p><pre class="brush: js;">const someSet = [0, 1, 2];
const powerSet = someSet.reduce((acc, x) => [...acc, ...acc.map(y => [x, ...y])], [[]]);
// powerSet = [[], [0], [1], [1,0], [2], [2,0], [2,1], [2,1,0]]</pre>
<p>
<p>The code above is a bit intimidating at first glance so it merits additional explanation. The power set always contains an empty set, so the second argument to the reduce method is a set that contains nothing but that. This is the starting value. When the function acts on the first item in the set, the value of acc is [[]] and the value of x is 0. The result of concatenating the current item to each item in acc is concatenated on to the value of acc making it [[], [0]]. The same algorithm is applied to each item in the set. This is difficult to envisage, so the code below details essentially what happens upon invocation. </p><pre class="brush: js;">const ps = (acc, x) => [...acc, ...acc.map(y => [x, ...y])];
// First element
let acc = ps([[]], 0);
// acc = [[], [0]]
// Second element
acc = ps(acc, 1);
// acc = [[], [0], [1], [1,0]]
// Third element
acc = ps(acc, 2);
// acc = [[], [0], [1], [1, 0], [2], [2, 0], [2, 1], [2, 1, 0]]</pre>
<p>
<p>The reader is highly encouraged to review this section multiple times until the concept solidifies.
<h3>Conclusion</h3>The post outlined a few useful set operations. ES6 uses the reduce method to apply the concept of summation to sets. A power set is a set of all possible set combinations. Although there is no built in ES6 functionality for this, it’s an easy algorithm to create. Make sure to come back for the final post entitled <i>When Sets Collide</i>. It is by far the most useful in the series covering set operations that act on multiple individual sets. <a style="display: none" href="http://www.codeproject.com/script/Articles/BlogFeedList.aspx?amid=608087" rel="tag">CodeProject</a><div id="AdnBottom"><div class="AdnBottomLeft" style="float:left"></div><div class="AdnBottomRight" style="float:right"></div><div style="clear:both"></div></div>
http://hideoushumpbackfreak.com/post/2017/02/19/Just-Enough-Set-Theory-Set-Operations-(Part-2-of-3)
dalealleshouse@gmail.comhttp://hideoushumpbackfreak.com/post/2017/02/19/Just-Enough-Set-Theory-Set-Operations-(Part-2-of-3)#commenthttp://hideoushumpbackfreak.com/post.aspx?id=6703d923-73e3-447a-be11-8053e649d1d6Sun, 19 Feb 2017 15:35:44 +0000SoftwareComputerScienceMathSetTheorydalealleshousehttp://hideoushumpbackfreak.com/pingback.axdhttp://hideoushumpbackfreak.com/post.aspx?id=6703d923-73e3-447a-be11-8053e649d1d62http://hideoushumpbackfreak.com/trackback.axd?id=6703d923-73e3-447a-be11-8053e649d1d6http://hideoushumpbackfreak.com/post/2017/02/19/Just-Enough-Set-Theory-Set-Operations-(Part-2-of-3)#commenthttp://hideoushumpbackfreak.com/syndication.axd?post=6703d923-73e3-447a-be11-8053e649d1d6