Logical Paraodoxes

Paradoxes have always fascinated me. They take seemingly self-evident facts and use them to arrive at ridiculous, surely impossible conclusions. Paradoxes force us to re-evaluate our most basic concepts of the world. We can no longer take even the simplest premises on faith, as when faced with a paradox there is no other possible conclusion that one of our "obvious" assumptions must be wrong. And correcting these assumptions inevitably leads to a better understanding of the universe and new discoveries in mathematics.

The greatest example of this is Zeno's paradox. Zeno was a Greek philosopher in the 5th century B.C. He created several paradoxes, but I'm going to focus on the paradox Achilles and the tortoise. One day, the tortoise challenged Achilles to a race. Achilles, as you know, was a great and powerful Greek warrior. Surely he should have no problem racing a tortoise. But, knowing he is at a disadvantage, the tortoise asks for a head start of 10 meters. Achilles agrees, knowing he could recover from such a small disadvantage with ease. So, the race begins with the tortoise 10 meters ahead, inching along as tortoises do. Achilles bursts from the starting line like a locomotive. He covers the 10 meters in a few seconds. But by the time he does this, the tortoise has moved ahead, though only slightly. No matter. In a brief moment he covers that distance as well. But, in the time it took him to do this, however small, the tortoise has moved ahead still. And by the time he reaches where the tortoise is now, it will have moved ahead again. So it seems that he can never really catch the tortoise, as the tortoise will always be ahead.

This is certainly a baffling result. I mean, no one in his right mind would claim that Achilles would lose to a tortoise. But then, what went wrong? What was wrong with our reasoning? In this case, the heart of the problem lies in dealing with infinite sums. Think about it. It takes Achilles a certain amount of time to run the first 10 meters, and in that time the tortoise will have moved a little bit ahead. It takes Achilles some time to cover the second distance, some time to cover the third distance and so on. Zeno is proposing that since there an infinite amount of periods of time, the total time taken (i.e. the sum) must itself be infinite. The problem with that, as modern mathematics has shown us, that simply isn't true. It turns out that since each period of time is smaller than the previous, it is possible that the sum of all of them is finite. Though, it is not guaranteed that just because the elements of the sum are decreasing, the infinite sum will be finite. See the harmonic series, for example.

To see this in action, let's calculate how long it does take Achilles to reach the tortoise. First off, to make the math easier, let's say the tortoise was only 1 meter ahead and was traveling at 1 m/s and Achilles was traveling at 2 m/s. Achilles covers the first meter in 1/2 a second, but by that time the tortoise has moved 1/2 of a meter ahead of his previous position. Achilles will cover the next 1/2 meter in 1/4 of a second and the tortoise will move ahead 1/4 meter and so on. The periods of time it takes Achilles to cover the distances are 1/2 second, 1/4 second, 1/8 second, 1/16 second, and blah blah blah. So the total time until he passes the tortoise is 1/2 + 1/4 + 1/8... . But what does this sum up to? Let's take it bit by bit. 1/2 + 1/4 = 3/4. And 3/4 + 1/8 = 6/8 + 1/8 = 7/8. And 7/8 + 1/16 = 14/16 + 1/16 = 15/16. I'm sure you see the pattern. The denominator is always a power of two while the numerator is one less. It's obvious that this sum will not go off to infinity. In fact, the sum will never be greater than 1. But it will be getting closer and closer to 1 the more terms we add. Since we can get arbitrarily close to 1 but never exceed it, we can conclude it will take Achilles exactly 1 second to catch up to the tortoise.

And is exactly the concept known as a limit in mathematics. The understanding of limits is central to the formulation of calculus, and, as a result, everything calculus is used for. This is a rather long list, intersecting with every field of science. The solution of this paradox came with the knowledge to create the most revolutionary discovery to have ever existed. But, this is just one, of many paradoxes known today. Several of these have been explained thoroughly, but there are several more that have yet to be solved.

One of the most famous paradoxes today is known as the Liar Paradox. It's been stated in many different forms, but the simplest is probably :

This statement is false.

You can easily see something is wrong here. Is the statement true or false? If we assume it's true, it must be correct in saying that it's false, and, thus, must be false, which is a contradiction. If we assume it's false, we can see it is correct when it says it's false, and must be true, which is also a contradiction.

When I first came across this, I thought it was simple. If it can't be false, and it can't be true, why not just call it neither, or "null"? Easy, right? Then someone made the statement:

This statement is false or null.

Well, this is a problem. If the statement is false, it succumbs to the paradox as the original. And now it can't even be null because then it would actually be true. There is still a contradiction.

So, we should be cautious. We don't know if our "solutions" result in new paradoxes. These things take lots of thought.

There have been a few proposed solutions to this problem, all of which have their merits and shortcomings. I personally haven't reached a conclusion that seems completely satisfactory. None the less, investigating this paradox and paradoxes like these is always a fun experience. Who knows, one may just arrive at indisputable evidence on the inconsistency of logic. (But probably not)

Weird Fractions

I was working on Project Euler problems the other day. Since I hadn't done one in a while, I decided to look up an easy one. I chose Problem 33. Now, the problem itself wasn't difficult to solve. With a few minutes spent programming on my TI-83, I found the fractions satisfying their criteria. The fractions were 16/64, 49/98, 19/95, and 26/65. The final answer, the product of these, left me puzzled,though. Taking the product of all of these you get simply 1/100. Such a queer answer. I expected something complicated like 19/40 or maybe 23/57. But no. Just 1/100. For any critical thinker, the obvious question presents itself. Why?

The only way to know why is to look at it from a wider perspective. If you think about it, the properties of these fractions only hold for a particular base. If you interpret 16/64 in base 7 you'll find that canceling the 6's will be very, very wrong. And 15/53 certainly does not have this property in base 10 but if interpreted in base 6 the property manifests. This means that given any number for a base, there will be a set (not necessarily non-empty) of fractions with this strange property. I will refer fractions with this property in a particular base b as weird in base b. (I'm not very original.)

But now came the problem of the perspective one should take in looking at the problem. When writing out the fractions, for instance, should you reduce the fractions, or keep them in the form they were found? Should you look at cancellations with 3, 4, or 5 digits or stick to 2? What if a fraction is repeated in 2 different forms? Should you include it twice? Or maybe you should look at the products of the fractions alone, and not worry about what they are individually. In the end, I decided to output them as completely simplified fractions and to only focus on the two digit examples This was for a few reasons

1. Reducing the fractions lets me not have to write it in it's original base. I'm focusing on the actual value of the fraction and not the symbols that compose it. Thus, I can write all fractions in the familiar base 10 and not have to worry about notation for bases higher than 10. (For example, writing 15 in base 16 would force me to go past our regular digits and use new symbols. People usually start to use letters after that (making 10 = A, 11 = B...15= F...), but that would only work for up to 36, and I'd want to look at numbers higher than that).
   
2. The products themselves are too little information. Looking at the components of the products allows one to see its origins, what exactly caused the result.
3. Two digits are the simplest possible case for this kind of thing. If there is a pattern, it should be easiest to spot there.
   

Finally, we need a goal. Simply, "understanding weird fractions" seems a bit vague. The way I see it, if we're able to make an algorithm to produce weird fractions without guess-and-check, we should have a pretty good understanding of them. For a full understanding, this algorithm may even be useable for 3 or more digits.


So, going off that, in order to study this at all we need a large set of an actual example of these fractions. So, the next step is to find an algorithm that produces the weird fractions for any particular base. For a particular base k we can write a number n as the sum of a series of numbers,



where . ai is merely the i-th digit in the base k representation. For example, . Thus, we can represent the 2 digit numerators and denominators, of base k, in the form with x and y greater than or equal to 0 and less than k. And since we need a digit to cancel with either x or y should appear twice in the fraction.

We have to be careful about where we put the repeated digit as that would affect our answer. The weird fractions in base 10, 16/64, 19/95, 26/65, 49/98 all have the cancellations taking place from the right digit of the numerator to he left digit of the denominator. This means that all those fractions are of the form.



Now, it turns out that all weird fractions less than one in any base k are of this form. You can understand this by looking at the other options. For both cancellations take place on the right digit then either the numerator is equal to the denominator or the digit being cancelled is simply 0, both of which are trivial cases. When both are cancelled from the left, the same conclusions can be drawn. That only leaves the cases where the digits being canceled are across from each other diagonally. When we cancel diagonally from the top left to the bottom right however, the only weird fractions found are greater than one (actually the inverses of the weird fractions less than 1). I'll leave it as an fun little exercise to the reader to figure out why. (Meaning, I really have no idea why.)


Now, if we write the fraction as above we can form the following equation by canceling out the b's.




And then problem becomes finding the values of a, b and c that satisfy the equation for a given base k. The easiest way for me to do this was to solve for c (I could have just as easily solved for a or b ) and have the computer iterating through the possible values for a and b (0, 1, ..., k - 1), calculating the value of c at each step. If c turned out to be an integer, we will have found values that form a weird fraction. What's left is to simply calculate a/c and add that to the list of weird fractions for that base.

Using this method, I produced a table for the weird fractions (in simplified form) of every base from 2 to 100. Here are the one's up to 20.

• 2:
• 3:
• 4: 1/2
• 5:
• 6: 1/3 1/2
• 7:
• 8: 1/4 1/2
• 9: 1/3
• 10: 1/5 1/4 2/5 1/2
• 11:
• 12: 1/6 1/4 1/3 1/2
• 13:
• 14: 1/7 1/2
• 15: 1/5 2/9 3/10 1/3
• 16: 1/8 1/6 1/4 3/8 1/2
• 17:
• 18: 1/9 1/6 1/3 1/2
• 19:
• 20: 1/10 1/5 1/4 1/2

Now's the fun part. It's time to look for some patterns! If you want, try to see how many solid patterns you can find before reading on. Well, there's one very blatantly obvious pattern sticking up here. All prime numbers don't have any fractions with the weird property. The first question we ask is, well, what separates the prime numbers form all other numbers? They don't have any divisors other than 1 and itself. So, the weird fractions for a base k depend on the divisors of k. Using this as a guide a second pattern, that would normally be harder to spot, becomes easily apparent. The denominators of every weird fraction has at least 1 divisor in common with the base they are found in (not counting 1 and the number itself). This criteria would, obviously leave the prime numbers empty.

So, where does that leave us? Well, as long as we're talking about divisors there is another pattern. The inverses of all divisors of the given base can be found in that set of weird fractions for that base. This, however, does not, in general, produce all the weird fractions for a base. So, the natural thing to ask is, what's up with the fractions that aren't merely inverses of divisors?

This occurs in our very own base 10. The 2/5 and 1/4 just don't fit in with 1/5 and 1/2.Well, I haven't gotten that far yet. But, I must note that in every b's set of weird fractions, if x/y is in that set than y/xb is also in it. That is, every fraction in the set can be multiplied by another fraction (or itself) to produce 1/b. This will certainly lend insight onto where weird fractions come from, and maybe even lead to a simple algorithm for producing them without guess and check.

So, yeah, weird fractions. Cool stuff.