Class notes
Proof by contradiction Made Easy!
- Course
- MAM1000W (MAM1000W)
- Institution
- University Of Cape Town (UCT)
The documents contains all the basic aspects of proof by contradiction using the fundamental theorem of arithmetic
[Show more]
Seller
Follow
Content preview
By: Kagiso MosehlaPROOF BY CONTRADICTION
What is meant by contradiction ?
➢ It is an opposition of combined statements or ideas.
e.g. the statement says ‘Kagiso is a boy’ , using proof by
contradiction, if we want to prove that Kagiso is a boy, we have to
assume that Kagiso is a girl and proof that he’s not a girl , therefore
he’s a boy.
Let P be some statement ( P-statement)
1) We want to prove that P is true
Assume that P is false, obtain a clearly false statement which
implies that P is true
2) P, Q are statements
Prove that if P is true then Q is true
Direct way: Assume that P is true and deduce that Q is also true
Proof by contradiction: Assume that P is true and Q is false
We get a false statement, which implies that out of our
assumption that P is true and Q is false was wrong, so Q has to
be true.
Example: if x2 < 1 then x < 1
↓ ↓
P Q
We prove by contradiction :
, Assume that x2 < 1 and x ≥ 1
If x ≥ 1 then x2 ≥ 1, which contradicts to our assumption that x2 < 1
This means that our assumption that x ≥ 1 is false, therefore x < 1
PRIME NUMBERS
Let a and b be integers , a,b ≠0
We say that b is a factor of a if a is divisible by b, and we have:
b/a , this means b divides a
so there exists an integer k
such that a = bk
Example: Positive factors of 16: 1,2,4,8,16
Definition: An integer n ≥ 2 is called a prime if it has exactly two
possible factors, 1 and itself
An integer n is called a composite if it has more than two factors
NB! The number 1 is neither prime nor composite
Every integer n ≥ 2 can be written as a product of one or more prime
numbers (its prime factorization)
Example: a) prime factors of 6 ={2,3} therefore its prime
factorization 6=2×3=6
b) 10={2,5} : 2×5 = 10
c) 20={2,5} : 2×2×5 = 20
If the factors do not have to be prime numbers, then integers can be
factored in more than one way
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller KagisowaMokone. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R135,00. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
73527 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 15 years now