Sorting Strategies and the Last Theorem

-D26, M10, Y14-
Hello all! Although, I have this eerie feeling that some of you just pop in and stare at these in silence. Which reminds me--I should ask my TA if he has seen this blog yet.

Last week, we began to discuss sorting strategies (e.g., insertion, selection, quick, merge) and the importance of determining which strategies are more efficient than others given an algorithm. Hardware and software may change over time, but determining which sorting strategy to employ when dealing with algorithms of a certain order (by order, I mean functions that act in similar ways--all quadratic functions are of the same 'order') by comparing their 'speeds' is of chief concern.

In order to properly consider the speed of a strategies' approach to solving an algorithm, the worst case scenario is tested. Clearly, testing what happens in the best case is impractical, since all  potential obstructions and errors will eventually arise to cause even more problems in the future. Testing the average--the area most common to the typical user--can be helpful, but requires an excessive amount of work, and we all know that a virtue of a computer scientist is laziness, so this is certainly not an option.

I am not familiar with the definitions of each sorting method, but they will surely come to light in future lectures.

In addition, I have been tasked with solving a mathematical/logic problem on my own. I am unsure of the proper balance between the two, but I do have one question in mind:

It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second, into two like powers. 
[Fermat's Last Theorem, 1637]

This states that no two positive integers to the power of n can be added together to produce another positive integer to the same power of n. The first successful proof of this was finally published in 1995 by Andrew Wiles, 358 years after the theorem's discovery, and the theorem has been noted as one of the most difficult mathematical problems in the Guinness Book of World Records.

I don't expect to give a full proper proof to this, but it would certainly be fantastic practice in dealing with difficult problems.

Thank you for reading.

More Proofs

-D19, M10, Y14-
Welcome back to the nth instalment (because I am not counting how many times I have written) of blog posts concerning mathematical expressions and logic! Due to Thanksgiving, we only had two hours of class this past week, so we dealt with proofs that do not involve boolean values, disproving, cases, and delta-epsilon proofs.
Concerning non-boolean proofs, the definition of floor was utilized. In English, the definition is: for all real numbers, the floor of a real number is the same as the integer that is less than or equal to the specified real number and this integer has no other integers greater than it that are closer to the specified real number. It is the same thing as dividing any real number and only looking at the whole number value of it. In Python, this is signified by "//", so 5 // 3 would return 1.
I never thought that mixed numbers would reappear after having only used them up to grade five in elementary school.

For proving things false, it was similar to the typical idea of proving something wrong by providing a counterexample (in the case of Universal statements), but with structure.

As for proofs by cases, this is inception, but with proofs: proof-ception, where in order to prove or disprove a statement, one must prove the statement true/false for a specific category, number, and the like, and then do the same proof for the next related category. It is ironic, that in order to prove something as simple as all natural numbers squared added to themselves will be even, we must build an extensive and relatively complex proof for it, in spite of the fact that academia likes to assert that--if we truly understand something--we can reduce it to its simplest form with relative ease.
Is a fourteen line proof for a simplistic concept support this idea that understanding implies a simple explanation? I believe it disproves this implication.
Sure, it may be true in a number of skills and fields, but it most certainly does not seem to be a universally true statement.

Thanks for watching reading

Proof by Contradiction

-D11, M10, Y14-

Hello! So! Had my first midterm this past week for this class. The difficulty was in-between the short and simple class quizzes and the noticeably more challenging homework assignments, making it a fair midterm in my eyes. I am confident I did well, a few small mistakes here and there--but overall I understood how to 'read' math and use it properly,

Aside from this, we continued with proof structure and solving and proving examples. I must say, this is quite abstract knowledge: it can be a simple task to prove something true or false to yourself, but to prove it to completion, leaving absolutely no loose ends, can be a menial task.

Even the 'simple' idea of proving that there are an infinite number of prime natural numbers becomes complex when you have to prove it. Specifically, it is proven through contradiction--which simply assumes the negation of the thing (that you are trying to prove as true) is true, resulting in some fundamental impossibility--say, 1 = 2--which in turn means the assumption must have been false, thus stating the original statement was in fact true.

This proof by contradiction is very difficult when utilizing the English language, due to its ambiguity in communication--nonetheless, it is a logical argument if all sides/parties hold to the same definitions.

I am not at all firmly grounded in these proofs though. I am unable to complete the proof by contradiction for prime natural numbers at the moment. I have this vague idea that, since the negation of there being an infinite number of natural primes is, there exists a natural number n such that the last prime |P| <= n , I need to set this |P| to be n and then have |P| +1 become the new |P| in the form: m + 1 <= m  where m is a natural number. This would be the necessary contradiction to finish off the proof, but I am probably missing a step somewhere here. Anyone have an insight?

Thank you for reading.

Proof Logic and Existence

-D05, M10, Y14-
Hello again, great to see you all! Joe, Steve, how's it going Toph? Bill, Michelle, Pete, Lyra, Zuko. It would be fantastic if someone reading this was actually named above, but I digress. Last week, we learned about proofs and proof techniques as well as reviewed limits--as in delta-epsilon proofs. The concept of proofs does not intimidate me--nonetheless, I would still like to know the relevance of proofs to programming. Will we create programs that can solve mathematical proofs? This sounds beyond the depth of a first year undergraduate course, however, I could be wrong. This form of communicating truth does remind me of a more philosophical conflict: the argument that everything is subjective.
This perspective of reality has its reasoning--I personally prefer x colour, whilst you might prefer y colour--but when it is expressed mathematically, it is easy to obliterate this idea that life is subjective. For all things (x) in the Universe (U), if it exists in reality or (inclusive) abstractly (E(x)), then it is Subjective (S(x)).
Mathematically:

∀x∈U, E(x) ⇒ S(x)

As a universal statement, all that is needed to prove this statement incorrect is a single counter-example. Ironically, in stating that everything is subjective, the statement itself must be included in this definition. The statement is objective, and thus, the idea that everything is subjective nullifies its own conclusion. The statement is its own counter-example, and everyone who believes that statement needs to reconsider the purpose of their existence. This may have been a philosophical topic of existentialism, but it is still exciting to see how logic intersects these supposedly 'unrelated' fields.

Of course, as this course continues, I hope to return to this "philosophical proof" and reinterpret it entirely within the structure of a mathematical proof. The chain of results was not quite extensive when stated in English--maybe the mathematical proof will be just as brief.

I am certain that a few people would rebel against this logic, others might redefine their idea of subjectivity, and still others might raise their fists in triumph. I hope to hear some feedback.

Until next time. Thank you for reading.