Proof that the square root of 2 is irrational

(N.B. this blog post is mainly directed at my undergraduate students for their first year Mathematics for Computing module!)

The square root of 2 ($\sqrt{2}$, often known as root 2) is the positive algebraic number that, when multiplied by itself, gives the number 2. Geometrically, the square root of 2 is the length of a diagonal across a square with sides of one unit of length; this follows from the Pythagorean theorem. A quick approximation for the square root of two is $\tfrac{99}{70}$ (despite having a denominator of only 70, it differs from the correct value by less than $\tfrac{1}{10000}$).

In the first few lectures we have covered the basics of logic and the propositional calculus, including the idea of reductio ad absurdum, or more specifically, proof by contradiction (indirect proof). One of the examples given in the lecture was proving that the square root of 2 is irrational using infinite descent:

Assume that $\sqrt{2}$ is rational; this means that we can represent it as the ratio of two integers:

$\dfrac{a}{b} = \sqrt{2}$

Then $\sqrt{2}$ can be written as an irreducible fraction $\tfrac{a}{b}$ such that $a$ and $b$ are coprime integers:

$\left(\dfrac{a}{b}\right)^2 = 2$

It follows that:

$\dfrac{a^2}{b^2} = 2$
$a^2 = 2b^2$

Therefore $a^2$ is even because it is equal to $2b^2$ ($2b^2$ is necessarily even because it is 2 times another whole number and even numbers are multiples of 2); it follows that $a$ must be even (as squares of odd integers are never even). Because a is even, there exists an integer $k$ that fulfils:

$a = 2k$

Substituting in $2k$ for $a$ in the earlier equation:

$2b^2 = (2k)^2$
$2b^2 = 4k^2$
$b^2 = 2k^2$

Because $2k^2$ is divisible by 2 and therefore even, and because $2k^2 = b^2$, it follows that $b^2$ is also even which means that $b$ is even. As we have shown that $a$ and $b$ are both even, this contradicts that $\tfrac{a}{b}$ is irreducible. $\square$

Because there is a contradiction, the original assumption that $\sqrt{2}$ is a rational number must be false. By the law of excluded middle, the opposite is proven: $\sqrt{2}$ is irrational.

This proof was hinted at by Aristotle, in his Analytica Priora, but it appeared first as a full proof in Euclid‘s Elements (as proposition 117 of Book X). There are a number of other methods of proving that the square root of 2 is irrational, including a simple geometric proof and proof by unique factorisation (using that fact that every integer greater than 1 has a unique factorisation into powers of primes). Check them out!

Tagged ,

2011 Royal Society MP/Scientist Pairing Scheme

I will be spending next week in the House of Commons, as part of the Royal Society‘s 2011 MP/Scientist Pairing Scheme. This scheme aims to build bridges between parliamentarians, civil servants and some of the best research scientists in the UK; participating scientists are paired with either an MP or civil servant and take part in a Week in Westminster and reciprocal visits back to the researcher’s institution. The Royal Society offers this scheme as an easy way to provide MPs with the opportunity to explore the science behind their decisions; by pairing a MP or civil servant with a leading scientist, both gain an understanding of the work behind the fundamental issues involved in each field. Since 2001, over 150 scientists have been paired with MPs and civil servants.

I’m paired with Jenny Willott, the Liberal Democrat MP for Cardiff Central, who has previously taken part in the Scheme. I’ve met with Jenny a couple of times over the past couple of months, so very much looking forward to the Week in Westminster. The scientists have a action-packed schedule, including talks from the Parliamentary Office for Science and Technology, the House of Commons and House of Lords Science and Technology Select Committees, the Parliamentary and Scientific Committee (who organise SET for BRITAIN, in which I took part in 2010) and Professor Sir John Beddington, the Government’s Chief Scientific Advisor. We will also spend time “shadowing” our MP, as well as attending PMQs on Wednesday! Overall, I hope the Scheme will give me further insight into how science policy is formed, as well as providing an opportunity for building long-term relationships to share knowledge and expertise with the Government.

(N.B. a similar scheme for the National Assembly for Wales, the Universities Pairing Scheme, has recently been announced by the Beacon for Wales)

The struggle for Libel Reform

This week saw the publication of a hugely important report on libel reform in England and Wales. The report is from the Joint Committee on the Draft Defamation Bill, which has been considering the government’s proposed bill after oral and written evidence from interested parties. The proposed new legislation will be the first wholesale reform of the libel laws of England and Wales since 1843.

But why is this important for scientists? Increasingly, individuals and companies are using England’s outdated libel laws to suppress legitimate scientific debate and discovery. I wrote a report on the Libel Reform and Science session at this year’s Science Communication Conference. The sterling work of Sense About Science‘s Keep Libel Laws out of Science campaign (as part of the wider Libel Reform campaign) has raised the profile of the libel reform movement in the UK, but there is still a long way to go.

Please read this excellent summary of the report by Stephen Curry (who has written about libel reform numerous times before), as well as the press release from the Keep Libel Laws out of Science campaign.

We should all be concerned about the current libel laws: please support the Libel Reform campaign and sign the petition.

Steve Jobs (1955-2011)

As I’m sure you are all aware from the avalanche of media attention, Steve Jobs passed away on the 5th October 2011, after stepping down from his role as CEO of Apple in August; he was 56 years old.

There have been numerous extensive obituaries for Jobs, who is widely regarded as one of the most visionary and disruptive technologists the world has seen. Whether or not you appreciate the products he designed, or the socio-technical philosophy he promulgated, it is hard to deny the impact he has had on commercial computing and how we use technology.

While much of the media focus has been on his achievements during his second spell as Apple’s CEO, I think his contributions in the late 1970s (with Steve Wozniak) and 1980s are of more significance to modern computing; for example, the Apple II, the Apple Lisa, the Macintosh, NeXT and Pixar. (N.B. if you interested in the history of modern computing, especially in the 1980s, I highly recommend Steven Levy‘s book Hackers: Heroes of the Computer Revolution)

With the notoriously outspoken free software pioneer Richard Stallman being quick to offer his opinion on Jobs’ death (which was widely regarded as being in poor taste), there have also been a number of interesting discussions critically analysing Jobs’ and Apple’s wider impact on technology and society. Nevertheless, I still think we need people who Think Different:

Reasonable people adapt themselves to the world. Unreasonable people attempt to adapt the world to themselves. All progress, therefore, depends on unreasonable people.

George Bernard Shaw (1856-1950)

Tagged , ,

Be an Optimist Prime

In light of recent encounters, I’ve decided to stick this on my office door; I also found some useful Optimus Prime quotes for the workplace.

(HT to Chris Booth and his Advice of the Day blog post from January)

Tagged

Super Mario Bros.

Yes, this actually happened — I met one of my childhood heroes at the National Media Museum in Bradford, whilst I was up there for the 2011 British Science Festival in September. Although in retrospect, this photo opportunity may have been designed for children.

I barely play any games now (although I have recently procured an Xbox 360 to play with the Kinect SDK), as I still hark back to the glory days of home gaming with the NES and SNES: I first played the original Super Mario Bros. on the NES when I was around eight years old and have played pretty much every Mario incarnation since (favourites: Super Mario Bros. and Super Mario World).

Any other Mario fans or NES/SNES aficionados out there?

The Science (Café) of Logic

Contrariwise, if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.

Through the Looking-Glass
Lewis Carroll (1832-1898)

On Tuesday night I made my second appearance on Science Café, BBC Radio Wales’ flagship weekly science and technology programme, which aims to explore the science and technology stories making the headlines and reveal the latest Welsh scientific research.

The topic of this week’s programme was logic: a two thousand year old system of reasoning and argumentation which (some) humans use every day, as well as being the foundation of computation and modern technology. I was joined on the panel by two distinguished colleagues, Professor John Tucker (Professor of Computer Science at Swansea University) and Professor Christopher Norris (Distinguished Research Professor in Philosophy at Cardiff University).

The discussion was driven by the expertise of the panel: starting from the development of “classical logic” as a formal system of the principles of inference and rational reasoning, all the way back to Aristotle and the classical trivium. Then moving into the mathematical logic of the late 19th century and early 20th century with Hilbert and his program to clarify the foundations of mathematics, how Gödel shattered Hilbert’s dream, and in particular, the significant contributions to philosophy, mathematics and logic of the Welsh-born Bertrand Russell. Logic cuts to the heart of computer science as it emerged as a discipline: Turing‘s work on the Entscheidungsproblem followed from Gödel’s work on the incompleteness theorems, with the notion of computation and general-purpose computers being of fundamental importance to the designers of the computer machinery in the 1940s. This rapidly moved on to a discussion of expressing human knowledge using logic with mathematical notation, developing “intelligent” thinking machines and the problems of artificial intelligence (especially so-called strong AI). This (briefly) touched upon my work using logic programming for real-world declarative problem-solving, particularly for provably optimal code generation and improving the efficiency of microprocessors.

In essence, the key point was made about how logic is pervasive in our modern technological society: in every piece of digital electronics and especially in software — a clear manifestation of logic. This led to an important education question: shouldn’t we be developing these important deductive reasoning, problem-solving and computational thinking skills at school? I certainly think so. Finally, in a move that may come back to haunt me in later years, I was asked to finish with a joke about logic…

The Science Café “Logic” programme is now available on iPlayer (but only for seven days after broadcast). You can also read about my week with the Science Café team in Wrexham in August 2011.