Podcast
Questions and Answers
What is the main goal when using proof by contradiction?
What is the main goal when using proof by contradiction?
Which of the following best represents a constructive existence proof?
Which of the following best represents a constructive existence proof?
In the proof that √2 is irrational, what does it imply if both a and b are shown to be even?
In the proof that √2 is irrational, what does it imply if both a and b are shown to be even?
What does the expression x^y where x = √2 and y = √2 explore?
What does the expression x^y where x = √2 and y = √2 explore?
Signup and view all the answers
For a statement to be true in proof by contradiction, which of the following must occur?
For a statement to be true in proof by contradiction, which of the following must occur?
Signup and view all the answers
What is indicated by the Pythagorean triplet (3, 4, 5)?
What is indicated by the Pythagorean triplet (3, 4, 5)?
Signup and view all the answers
What characteristic defines non-constructive existence proofs?
What characteristic defines non-constructive existence proofs?
Signup and view all the answers
What conclusion can be drawn if assuming √2 is rational leads to the conclusion that both a and b are even?
What conclusion can be drawn if assuming √2 is rational leads to the conclusion that both a and b are even?
Signup and view all the answers
What is the result of the expression $x^y$ if $x = (\sqrt{2})^{\sqrt{2}}$ and $y = \sqrt{2}$?
What is the result of the expression $x^y$ if $x = (\sqrt{2})^{\sqrt{2}}$ and $y = \sqrt{2}$?
Signup and view all the answers
In the proof by cases method, what is the first step?
In the proof by cases method, what is the first step?
Signup and view all the answers
When proving that $3k^2 + k$ is even for any integer $k$, what form does $k$ take when it is even?
When proving that $3k^2 + k$ is even for any integer $k$, what form does $k$ take when it is even?
Signup and view all the answers
What is a counter example used in mathematics?
What is a counter example used in mathematics?
Signup and view all the answers
Which of the following best defines a fallacy in reasoning?
Which of the following best defines a fallacy in reasoning?
Signup and view all the answers
In the context of the proof by cases method, what must you show for each case?
In the context of the proof by cases method, what must you show for each case?
Signup and view all the answers
What condition for an integer k is explored in proving that $3k^2 + k$ is even?
What condition for an integer k is explored in proving that $3k^2 + k$ is even?
Signup and view all the answers
Which of the following serves as a counter example to the statement, 'All prime numbers are odd'?
Which of the following serves as a counter example to the statement, 'All prime numbers are odd'?
Signup and view all the answers
What is the first step in the process of Mathematical Induction?
What is the first step in the process of Mathematical Induction?
Signup and view all the answers
In the context of the argument provided, what outcome indicates a fallacy?
In the context of the argument provided, what outcome indicates a fallacy?
Signup and view all the answers
Which part of the induction process involves showing that the statement holds for the next integer?
Which part of the induction process involves showing that the statement holds for the next integer?
Signup and view all the answers
In the example proof of divisibility, what is the expression derived after substituting for P(k)?
In the example proof of divisibility, what is the expression derived after substituting for P(k)?
Signup and view all the answers
What does a truth table for a compound expression signify if it is a tautology?
What does a truth table for a compound expression signify if it is a tautology?
Signup and view all the answers
What is the purpose of assuming P(k) is true in Mathematical Induction?
What is the purpose of assuming P(k) is true in Mathematical Induction?
Signup and view all the answers
What is the representation for the compound proposition used to check consistency in the argument?
What is the representation for the compound proposition used to check consistency in the argument?
Signup and view all the answers
What conclusion can be drawn if the statement P(n) is true for n = 1 and P(k) implies P(k+1)?
What conclusion can be drawn if the statement P(n) is true for n = 1 and P(k) implies P(k+1)?
Signup and view all the answers
Flashcards
Proof by contradiction
Proof by contradiction
A method where we assume the negation of a statement is true, then show a contradiction.
Propositional statement (p)
Propositional statement (p)
A clear, declarative statement that can be true or false.
Negation (~p)
Negation (~p)
The opposite of a propositional statement, indicating it is false.
Existence Proof
Existence Proof
Signup and view all the flashcards
Constructive Existence Proof
Constructive Existence Proof
Signup and view all the flashcards
Non-constructive Existence Proof
Non-constructive Existence Proof
Signup and view all the flashcards
Example of Irrational Numbers
Example of Irrational Numbers
Signup and view all the flashcards
Pythagorean Triples
Pythagorean Triples
Signup and view all the flashcards
Validity of Arguments
Validity of Arguments
Signup and view all the flashcards
Truth Table
Truth Table
Signup and view all the flashcards
Tautology
Tautology
Signup and view all the flashcards
Mathematical Induction
Mathematical Induction
Signup and view all the flashcards
Base Case
Base Case
Signup and view all the flashcards
Assumption Step
Assumption Step
Signup and view all the flashcards
Induction Step
Induction Step
Signup and view all the flashcards
Divisibility Proof
Divisibility Proof
Signup and view all the flashcards
Irrational number
Irrational number
Signup and view all the flashcards
Proof by Cases
Proof by Cases
Signup and view all the flashcards
Mutually Exhaustive
Mutually Exhaustive
Signup and view all the flashcards
Even number
Even number
Signup and view all the flashcards
Odd number
Odd number
Signup and view all the flashcards
Counter example
Counter example
Signup and view all the flashcards
Fallacy
Fallacy
Signup and view all the flashcards
Rational number
Rational number
Signup and view all the flashcards
Study Notes
Proof by Contradiction
- A method to prove a statement by showing that assuming the opposite is true leads to a contradiction.
- Consider a statement (p).
- Assume the opposite is true (~p).
- Show that ~p leads to a false conclusion (F).
- Therefore, ~p is false, meaning p is true.
Example: Proving √2 is Irrational
- The statement (p) is: √2 is irrational.
- The negation (~p) is: √2 is rational.
- If √2 is rational, then it can be expressed as a fraction a/b, where a and b are integers with no common factors.
- Squaring both sides: 2 = a²/b²
- This implies a² is even, which means a is also even. (If a² is even, then a must be even)
- Since a is even, a can be expressed as 2k.
- Substituting 2k for a: 2b² = (2k)² = 4k²
- This simplifies to b² = 2k², which means b² is even, so b is even.
- Now both a and b are even, contradicting the initial assumption that a and b have no common factors.
- Because the assumption (~p) leads to a contradiction, it must be false.
- Therefore, the original statement (p) is true: √2 is irrational.
Constructive Existence Proof
- A proof method that finds a specific example to show a statement is true for some value within a domain.
- Example: finding integers a, b, and c where a² + b² = c² (Pythagorean triplets).
- The value of specific examples demonstrates the existence of these values.
Non-Constructive Existence Proof
- A proof showing the existence of some mathematical object without explicitly constructing it.
- Example: Showing there exist irrational numbers x and y such that x√2 + y is rational. Shows there are these numbers existing without showing explicit values.
Proof By Cases
-
A method for proving a statement by considering all possible cases and showing that the statement holds true in each case.
-
Example: Any integer k, 3k² + k is even.
-
2 cases: (k even, k odd)
-
If k is even, k can be represented as 2p. Then 3(2p)² + (2p) = 12p² + 2p = 2 (6p² + p). This is clearly even.
-
If k is odd, k = 2p + 1. Then 3(2p + 1)² + (2p + 1) = 12p² + 12p + 3 + 2p +1 = 2(6p² + 7p + 2). This is also even making the statement true.
Mathematical Induction (Weak)
- A technique to prove a statement is true for all natural numbers.
- 2 steps:
- Base case: Prove the statement is true for the first natural number.
- Inductive step: Assume the statement is true for some arbitrary number k and prove it's true for k+1.
Strong Induction
- Similar to weak induction, but in the inductive step you assume the statement is true for all numbers up to k, not just k.
Sequences
- An ordered list of elements. Terms are the elements of the sequence.
- Examples include arithmetic and geometric sequences, which have patterns.
Summations (Σ)
- The sum of sequence terms.
- Notated by the Greek capital letter Sigma.
Arithmetic Progression
- A sequence where the difference between consecutive terms is constant.
- Formula for nth term and sum of n terms are presented.
Harmonic Progression
- A sequence where the reciprocals of terms form an Arithmetic Progression, or the terms form 1/a, 1/(a+d), 1/(a+2d)
Geometric Progression (GP)
- A sequence where each term after the first is found by multiplying the previous one by a fixed, non-zero number (“common ratio”).
- Formula for the nth term and sum of n terms provided for finite GP. Also for infinite if |r| < 1.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
This quiz covers the method of proof by contradiction, focusing on the example of proving the irrationality of √2. You will learn how to assume the opposite of a statement, show that it leads to a contradiction, and conclude the original statement must be true. Test your understanding of this critical proof technique!
