Proof by Contradiction

The concept of proof by contradiction refers to taking a statement and assuming the opposite is true. When assuming the opposite is true we begin to further examine the our ‘opposite’ statement and reach to a conclusion which doesn’t add up or in simple terms is absurd.

Take the case:

Statement: There are infinite number of prime numbers.

Using the concept of proof by contradiction, we will assume the opposite is true.


If an integer (2) divides an integer (6) we say that 2 divides 6 or 2|6. In a more general sense we can say that if any integer ‘a’ divides any other integer ‘b’ then a|b.

Prime numbers: it is an integer (n ≥ 2) that has exactly two positive factors (1 and itself).

eg. 2, 3, 5 …

Composite numbers: it is an integer (n ≥ 2) that has more than two positive factors.

eg. 4, 6, 8 …

Fundamental Theorem of Arithmetic: Every integer n ≥ 2 has a unique (exactly one) prime factorization.…

By | April 17th, 2017|Uncategorized|0 Comments

Proof by contradiction – part 2

So, in the last post we proved that \sqrt{2} is irrational, by trying to see what the consequences would be if it were rational. We first said that if it were rational, then we should be able to write it in a simplest form \frac{p}{q} where p and q had no common factors, and then showed that in fact this was impossible, so our original proposition was indeed true (as trying to prove otherwise gave us a contradiction).
Now we are going to look at another example, which looks very similar, but here our contradiction will be a little different to last time. The fact is that, unlike much of what you would have done at highschool, there isn’t such a roadmap to how to do things here – you have to figure out for yourself where the contradiction comes in. In these posts I will point them out for you, but in general, you need to build your intuition about where something looks a bit dodgy and a contradiction is raising its head.…

By | March 22nd, 2016|Courses, First year, MAM1000, Undergraduate|5 Comments

Proof by contradiction – part 1

Proof by contradiction may at first seem completely weird! I give you something to prove, and you seem to ignore me and try and prove that what I want you to prove is wrong!

Actually, this isn’t nearly as strange as it first seems, and it can work in contexts other than mathematics. The idea stems from the fact that a statement is either true, or false (well, if you listen to Gödel, then you have to be a bit careful, but it’s reasonable enough for now). The process is the following:

  1. You want to prove that a statement is true.
  2. You say “what would happen if the statement were actually false?”
  3. You explore the consequences of it being false.
  4. If you find that it gives you a contradiction (something which you claimed to be true, but which you now see isn’t true), then you know that in fact the original statement can’t be false…so it must be true, and you’ve proved it.
By | March 20th, 2016|Courses, First year, MAM1000, Uncategorized, Undergraduate|4 Comments

Can we find the inverse of a function which is not one-to-one? (part two)

So, in the last post we had seen that while the sin function is not one-to-one and thus doesn’t have an inverse, so long as we restrict it to a given domain, you will find that it is invertible. The domain that we found (indeed chose), was between [-\frac{\pi}{2},\frac{\pi}{2}]. It’s inverse was a function with domain [-1,1]. The name of the inverse is arcsin(x).  How can we use this to help us to solve problems?

Well, what if I asked you to solve:

 

sin(x)=\frac{1}{2}

 

You might think that because we have found the inverse of sin, that we can simply say that the solution to this is:

 

x=arcsin\frac{1}{2}

 

Well, because arcsin is itself a one-to-one function, restricted to the domain [-1,1] this will clearly give us a single number (the answer is about 0.52):

 

firstsol

Is that it then? Well, let’s look at the graph of sin(x) and see if this is the only solution to sin(x)=\frac{1}{2}:

singraphIn fact, clearly there are an infinite number of solutions to the equation sin(x)=\frac{1}{2} and we have just caught the one within the region [-\frac{pi}{2},\frac{\pi}{2}].…

By | March 16th, 2016|Courses, First year, MAM1000, Uncategorized, Undergraduate|1 Comment

Domain of a composite function – part 2

This is the second part of a post, written by Muhammad Azhar Rohiman, a first year student on MAM1000W at UCT. This post came about when he asked me a question related to domains of composite functions, and it was clear that on first learning about such topics, there are some simple misunderstandings. I suggested that he write a couple of paragraphs explaining what he had learnt, and the following is, I think, a very clear explanation of some of the ideas and pitfalls of this topic. The first part of the post is here.

 

Consider the two functions below, from which we want to find the domain of

 

(a) (f\circ g)(x).

 

(b) (g\circ f)(x).

 

(c) (f\circ f)(x).

 

(d) ( g \circ g )(x).

 

f(x) = x + \frac{1}{x}

 

g(x) = \frac{x+8}{x+2}

 

(a) The functions f(x) and g(x) cannot be defined at the values x = 0 and x = -2 respectively. Therefore, we can write this as follows: f(0) and g(-2) are not defined.…

By | March 12th, 2016|Courses, First year, MAM1000, Undergraduate|1 Comment

Arbitrary functions as the sum of odd and even functions

Let’s take a function h(x), whose domain is the real numbers. We are simply going to start by writing h(x) in a slightly strange way. We will write it as:

 

h(x)=\dfrac{h(x)+h(-x)+h(x)-h(-x)}{2}

 

This might seem an odd thing to do – we have essentially added zero to the original function (in the form h(-x)-h(-x)). However, we can see that we can split this as:

 

h(x)=\dfrac{h(x)+h(-x)}{2}+\dfrac{h(x)-h(-x)}{2}

 

It’s exactly the same thing we started with, right? But now it’s written in a peculiar way. Now let’s call the two fractions f(x) and g(x) respectively. So:

 

f(x)=\dfrac{h(x)+h(-x)}{2}

 

and

 

g(x)=\dfrac{h(x)-h(-x)}{2}

 

So our original function can be written as h(x)=f(x)+g(x). If you plug in f(x) and g(x) above you will see that we have said nothing which is not trivial in any of this. However, the interesting part comes when we look at the properties of f(x) and g(x). What is f(-x)?

 

f(-x)=\dfrac{h(-x)+h(x)}{2}=\dfrac{h(x)+h(-x)}{2}=f(x)

 

But this is just the defining property of an even function, so f(x) is even.…

By | March 10th, 2016|Courses, First year, MAM1000, Undergraduate|1 Comment

Mathematical induction with an inequality

In the tutorial sessions it was clear that one question in particular was causing problems. This is an induction proof with an inequality. The one which we will look at is the inequality:

 

2^n>n^3 for n\ge 10

 

I am going to talk you through it in more detail than would be needed for the formal proof but I want to give some intuition along the way.

 

So, we start off, as always with the base case. The base case is always the first integer for which the statement is claimed to be true. In this case it is for n=10. Let’s check for n=10. Is it true that?

 

2^{10}>10^3 ?

 

Well this is:

 

1024>1000

 

and so we should be happy with that. We’ve proved the base case. Note that you do not then need to check for n=11, or n=12. I have seen many students check a base case for n=1, and then also check for n=2 and n=3.…

By | March 9th, 2016|Courses, First year, MAM1000, Undergraduate|10 Comments

Domain of a composite function – part 1

This post was written by Muhammad Azhar Rohiman, a first year student on MAM1000W at UCT. This post came about when he asked me a question related to domains of composite functions, and it was clear that on first learning about such topics, there are some simple misunderstandings. I suggested that he write a couple of paragraphs explaining what he had learnt, and the following is, I think, a very clear explanation of some of the ideas and pitfalls of this topic.

 

Consider the two functions below, from which we want to find the domain of ( f \circ g )(x)

 

f(x) = \frac{1}{x+2}, g(x) = \frac{x}{x-3}

 

We know that f(x) and g(x) cannot be defined at the values x = -2 and x = 3 respectively. This can be written as follows: f(-2) and g(3) are not defined. The domain of a composite function will not allow any values restricted by the domain of the starting function, which is g(x).…

By | March 7th, 2016|Courses, First year, MAM1000, Undergraduate|4 Comments

Mathematical induction

One of the concepts that most students seem to struggle with the most in the first year maths course is that of mathematical induction. It feels abstract, yet when you have to prove a concrete statement, it feels like all the assumptions, and cases you look at shouldn’t have any real impact on the thing that you’re trying to prove. I will now try and prove that this is not true (though not by mathematical induction!).

 

I’m going to start with a ladder brought from a magical ladder supplier. Steps on the ladder are labeled S(1), S(2), S(3) etc. The question is, are there infinitely many steps on the ladder? Well, with the information that I’ve given you so far, you just don’t know, but the manufacturer has given a little leaflet with the it. In the leaflet it says:

“As long as your ladder has a step S(n), we hereby guarantee that it will have a step S(n+1), for any integers n”.…

By | March 6th, 2016|Courses, First year, MAM1000, Undergraduate|6 Comments