On The Margins

Saturday January 19, 2008

[ Mathematics ] How Many

How many non-standards models of Peano Arithmetics exist? (Hint: The Gödel construction gives you many models. One can also prove the existence of many such models using the fact that there are  many primes.)

2008-01-19 07:44:09.0 -- Comments [1] ; Permalink ; Trackback.
logic mathematics

Friday October 13, 2006

[ Mathematics ] Interactive Mathematics

The Interactive Mathematics portal could be worth a visit for children.  It seems to have used Java Applets for a good many of its puzzles and games. The problems are quite simple but they can still be fun for kids and adults, too. Take for example, the 3 jugs problem. (It would have been ideal if this puzzle had been implemented to include various number and sizes of jugs. Note that the 3 jugs version includes all the essential mathematics behind the problem.) This site is still heavier on the explanation side and lighter on interaction. If you know an "open community" of math puzzles (implemented as Java Applets or by other means), feel free to leave the URL in the comment section below.

2006-10-13 06:21:58.0 -- ; Permalink ; Trackback.

[ Mathematics ] San Jose Math Circle

A good friend of mine who works at Apple pointed me to San Jose Math Circle.  He says the Math Cricle meetings can be fun for kids who enjoy mathematics. Diverse set of topics, mostly from geometry, are presented. For example, next week, Tom Davis talks about "box packing problems".

2006-10-13 06:18:37.0 -- ; Permalink ; Trackback.

Sunday September 17, 2006

[ Mathematics ] Events, Probabilities and Information

The less probable an event is, the more information its occurrence conveys. The value of the information (or the "message") an event brings is zero when the probability is equal to one "because receiving a message that we expect with certainty gives us, in effect, no new information" (Adam Drozdek, Elements of Data Compression).  On the other hand, as the probability of an event approaches zero, the message it carries will contain more valuable information. As Dorzdek notes, "[t]his is in line with our intuition that rare events are more informative than unsurprising events."

2006-09-17 23:08:36.0 -- Comments [5] ; Permalink ; Trackback.

Thursday August 24, 2006

[ Mathematics ] Mathematicians and Confirming Correctness

Only a mathematician can turn confirming correctness into a conundrum.

To get around the conundrum, neither deduction by contradiction nor deduction by construction will help.

I'm purposefully not using "proof by contradiction" here but emphasizing the "deduction" used by mathematicians. Anything that requires for its proof a deduction must indeed be quite poor in its validity for it is far from obvious.

2006-08-24 23:16:05.0 -- Comments [2] ; Permalink ; Trackback.

Tuesday June 13, 2006

[ Mathematics ] P vs. NP

Here is a nice take on the P vs. NP problem.

2006-06-13 10:36:03.0 -- ; Permalink ; Trackback.

Monday August 01, 2005

[ Mathematics ] Information Theory

Lucent has a nice little page on the "who" and "what" of information theory, and there is a little course on information theory hosted at Cavendish Laboratory, Cambridge.

2005-08-01 21:53:20.0 -- Comments [2] ; Permalink ; Trackback.

Sunday July 31, 2005

[ Mathematics ] Space, Mechanism and Interactability

The space used to encode a problem and the machine (mechanism) used for solving it cannot transform an interactable problem to a tractable one. Instead, interactability may have its most important relationship to the logical form (or description) of the problem. This hypothesis suggests itself when one examines the description of recursively enumerable sets and the computing levels in the arithmetical hierarcy. (See Chapter 4 of Robert I. Soare's Recursively Enumerable Sets and Degrees.)

Mathematics, Digital Machines.

2005-07-31 22:39:21.0 -- Comments [0] ; Permalink ; Trackback.

Monday April 04, 2005

[ Mathematics ] Mathforum.Org, Nonlinear Dynamics and Blood

Mathforum.org has a great starting point for exploring non-linear dynamics on the web.

I thought about non-linear dynamics because we had some guests Sunday night whose son (who was also visiting us) almost died last year because of a mis-communicated antibiotic prescription to the pharmacy. This particular antibiotic has long-lasting effects and, obviously, triggers biochemical pathways, not all of which are fully mapped out. It may interest some to know that the nonlinearity of the biochemical cosmos is certainly greater than the nonlinearity of heavenly bodies (when they are taken to be point masses, of course).

I had the good fortunte of studying Biochemistry (among other subjects) in graduate school, and to me, the extent of the cosmos of biochemical pathways is truly astonishing. To explore it is not simply a matter of collecting more of the pathways and committing their relationships to some sort of database. The triggers and signals are only and will forever be partially mapped (think of the combinatorics). Given their understanding of small parts of the universe of biochemical pathways in the body, drug companies come up with new "designer" drugs. Since the cosmos of biochemical pathways is immense, the effect of these drugs on other corners of that cosmos are totally unknown. Small triggers in the wrong places can unleash deadly consequences, as it seems to have happened with our friends' son. Only six years of age, he woke up drenched in blood one night last year and had to stay in the hospital for two weeks. I will spare you the details.

So, did the Babylonians have it wrong? They used to lay their sick at the door, collect medical advice from the passersby, integrate and administer the suggestions.

Did they have it more wrong than we do today?

Mathematics, Drugs, Babylon, Medicine, Nonlinear Dynamics, Biochemistry, Administer, Children.

2005-04-04 14:15:53.0 -- Comments [0] ; Permalink ; Trackback.

Thursday March 24, 2005

[ Mathematics ] Gravitating Masses

As I was driving to work this morning, I wondered again about the subtle integral role of cultural practices which resonate with the motion of heavenly bodies, for example the start of the Persian solar year, Noruz, which celebrates spring solstice. The mathematics and numerical simulation of such motions has fascinated people for centuries. Here is a cool Java applet computing and displaying the motion of gravitating masses in the solar system and a few others. My favorites are the ones with "simple" orbits, like this one which shows bodies ending with circular orbits. The applet is hosted by CUUG, Calgary Unix Users Group. Bob Jenkins has implemented another Java applet, displaying the paths of gravitating masses. Jenkins says he has used a 9th order multi-step simulation method for his applet because lower-order methods were insufficient for his purposes. He also has a summary page for various multi-step methods, and a brief note which describes their pedigree—absolutely great stuff

TX Cam, in the constellation Camelopardalis. (National Radio Astronomy Observatory)

Mathematics, Physics, Gravitation, Noruz, Solstice.

2005-03-24 09:26:04.0 -- Comments [1] ; Permalink ; Trackback.

Friday November 05, 2004

[ Mathematics ] A Problem

Mathematics, particularly those parts of it rooted in Algebra, have a stunning, razor-sharp view of the concept of a problem:

[A] problem will be a general question to be answered, usually possessing several parameters, or free variables, whose values are left unspecified. A problem is described by giving: (1) a general description of all its parameters, and (2) a statement of what properties the answer, or solution, is required to satisfy. An instance of a problem is obtained by specifying particular values for all the problem parameters. Michael R. Garey and David S. Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness

In other words, an instance of a problem is obtained when all paramters, except the "solution" variables are bound to particular values. The "solution" variables remain free. For example, find an x such that for all y, z and w, we have P(x,y,z,w), where P is some predicate.

What mathematics offers is precision in thinking. Without basic training in it, our reasoning becomes crippled, and we fail to see what there is and what there is not.

2004-11-05 08:43:08.0 -- Comments [4] ; Permalink ; Trackback.

Tuesday October 26, 2004

[ Mathematics ] Consistency--What's Logic Got To Do With It

Frege used a 2-D notation for his logic.

Back in 1996, in a paper submitted to the annual Stanford-Berkeley graduate philosophy seminar, I wrote on the role of mathematical logic in the positivist philosophical work conducted in the twilight of the twentieth century. This afternoon, I mentioned it, in passing, to a friend, and he suggested I should discuss it on my weblog. Now, this friend of mine (who likes to remain annonymous to search engines but who is one of the leads for our most important pieces of work on web services) noted that consistency was central to his methodology. We agreed that the Cartesian model of the world still remains the dominant one in many of the socio-operational systems around us.

In the paper, I claim that an over-emphasis on consistency (I should have been more precise and should have called this an over-emphasis on the the law of excluded middle) led to a misplacement of philosophical focus prior to Heidegger. Heidegger is the one who turned the philosophical ship from questions regarding epistemology, in the positivist tradition, to those regarding metaphysics and ontology, in the modern tradition of phenomenology. (Metaphysics and ontology had generally enjoyed a far greater priority in traditional philosophical investigation.)

My point in the paper was about the emphasis placed on consistency, not necessarily a critique of it, but rather a critique of its importance (as understood by modern positivists and logicians) to philosophical dialog and to philosophy.

2004-10-26 15:35:23.0 -- ; Permalink ; Trackback.

Wednesday September 01, 2004

[ Mathematics ] The Mathematics of Elections

Should software and servers matter in breaking election ambiguities?

Well, it all depends on what sort of ambiguity we're talking about. Here, I'm certainly not talking about hanging chads. I'm talking about ambiguities that may arise because of the election method used.

Some election ambiguities require computational power, others may take you to the Supreme Court. Let's focus on the first type of ambiguity, for the moment.

The mathematics of elections is quite simple when everyone has a chance to vote only for one of the candidates, i.e. when no allowance is made for the voter to fully specify and assign his or her preferences to each and as many of the candidates as he or she wishes. In such an election, all we need to do is add the votes for each candidate. Whoever has more votes wins. No puzzling ambiguities are left.

Kenneth Arrow, the distinguished Stanford economist, who has also written the forward to the anniversary edition of Chester Barnard's classic (about which I've written earlier) has a famous theorem (Arrow's Impossibility Theorem) which effectively says there are no ideal methods for elections.

Arrow gives several criteria for "ideal" elections, the most controversial of which is the "Independence from Irrelevant Alternatives Criterion" (IIAC).

IIAC says, effectively, that removal or addition of a candidate should make no difference unless that candidate was or will be the winner (against all other candidates).

Arrow shows that it is impossible for an election method to satisfy all of his criteria. So, according to Arrow's theorem, even if voters had a chance to fully specify their preferences, it would make no difference.

The trouble is that the IIAC is not necessarily a valid criterion.

As noted in ElectionMethods.org, IIAC is too strong a criterion and near-ideal election methods do exist. The Condorcet election method is one such near-ideal election method:

The proper method of counting ranked votes is called the Condorcet election method, named after the French mathematician who conceived it a couple of centuries ago. The main idea is that each race is conceptually broken down into separate pairwise races between each possible pairing of the candidates. Each ranked ballot is then interpreted as a vote in each of those one-on-one races. If candidate A is ranked above candidate B by a particular voter, that is interpreted as a vote for A over B. If one candidates beats each of the other candidates in their one-on-one races, that candidate wins. Otherwise, the result is ambiguous and a simple procedure is used to resolve the ambiguity.

Well, it is the resolution of this ambiguity at a national (or any other large-scale) level that may require some use of computing power.

ElectionMethods.org discusses Basic Condercet (BC) and Schwartz Sequential Dropping (SSD) for resolving the ambiguity. It includes a software implementation for the SSD method for solving cyclic ambiguities.

BC method drops the weakest defeat (from the cyclic series of defeats) until there's a candidate that is unbeaten. This may cause strategy issues. Parties may have clone candidates, i.e. multiple candidates running for the same party.

The SSD method has been described in ElectionMethods.org, where links to software and other useful information can also be found.

Personally, the Beatpath Winner (BW) method appears to me to be adequate in resolving cyclicity in a Condercet voting result. It's equivalent to the SSD method of resolving ambiguities. In the BW method of resolving cyclic ambiguities, if A defeats B through a "path" (chain of defeats) and B defeats A through another path (in the cycle), the two paths (chains) are compared to see which one has the weakest defeat in its sequence of defeats. The candidate which has the strongest defeat paths (chains) against all other candidates is the winner.

Condercet method of elections seems like a very reasonable method. The reason it has not been popular in the U.S. is probably because people are very conservative and don't want surprises. Furthermore, the strategy outcomes are hard to predict. It really unleashes a marketplace for votes and makes results much more difficult to predict. Another reason could be that Condercet will be truly bad for the two-party system. Finally, with more parties having a chance, there is also the question of political stability. In the absence of political stability, economic stability may also be a rarity. So, I would expect there may issue some arguments from institutional economists against Condercet.

2004-09-01 11:56:44.0 -- Comments [5] ; Permalink ; Trackback.