Chapter 1 Flashcards
PRIME FACTORISATION THEOREM
FUNDAMENTAL THEOREM OF ARITHMETIC
Every natural number can be uniquely given as a product of prime numbers up to reordering.
Proof uses euclids lemma: if a prime p divides the product of 2 natural numbers a&in then p divides a or b.
We prove existence of prime factorisation by induction
Then uniqueness by assuming can be written in two ways and showing these are equal, by showing less than or equal to on both sides
THM 1.21 for prime p , √p..
If p is a PRIME number then √p is irrational
*infinitely many primes -> infinite irrationals
Proof by supposing it’s rational, squaring and rearranging into PRIME DECOMPOSITION FORM to consider each case (if not a factor of) for contradictions
THM 1.2.2 given any 2 rational numbers we can find infinitely many irrational
for a less than q less than b
Given any 2 RATIONAL numbers a and b with a1 -> √p >1 -> (1/√p) <1.
DEFINE q = a + (b-a)/√p
Show:
1. q is irrational by sum product rules
2. There are infinitely many of the form? Primes infinite
3. Show that a< is less than q
And b is more than q
For what N? Relating Perfect squares and..?
THM 1.2.3 if N is a natural then either it’s a PERFECT SQUARE OR √N is IRRATIONAL
Proof
Suppose N is not a a perfect square and √N is rational. √N= a +(b/c) where b/c in lowest terms.
Rearranging and squaring:
b^2 = Nc
Triangle inequality,
What’s NOT true?
|a+b|≤|a|+|b| for all a,b in ℝ reals
Not true that |a-b|≤|a|-|b|
Relating to triangle inequality,
| |a|-|b| | ≤ ???
Proof: |a| = |a-b+b|
≤|a-b| + |b| By triangle
Similarly |b|≤ |b-a| + |a|
Rearranging |b| - |a| ≤ |b-a| = |a-b|
|a| - |b| ≤ |a-b|
By definitorios of mod:
Mod( |a| - |b| ) = max { |a| - |b| , |b| - |a| }
≤ |a-b|
|a|-|b| | ≤ |a-b| for all a and b in the reals
The theorem of means
For a set of nonnegative real numbers a₁ , a₂, …, a_n then
n√ a₁•a₂•..•a_n ≤ a₁+a₂+..+a_n
————
n
(Geometric mean) ≤ (arithmetic mean)
Proof from 111 by induction
Bernoullis inequality
(1+ x) ^n ≥ 1+nx
For all n in the naturals and x> -1
Proof: By induction: Base case- for n=1 equality Hypothesis- (1+x)^p ≥ 1 +px For some p in N st p>1. (1+x)(1+x)^p ≥ (1+x)(1+px) = 1+px^2 +px+x ≥ 1+ px + x then we have that (1+x)^p+1 ≥ 1 + x(p+1) hence by induction statement true.
Cauchys inequality
If a₁ , a₂, …, a_n and b₁ , b₂, …, b_n are real numbers then
Proof:
By applying the results of the previous exercise to the quadratic function problems 6 and 7 in notes
n | n ½ n ½
| Σ a b | ≤ (Σ a_i^2) * (Σ b_i^2)
| i=1 i i| i=1. I=1
A proposition: relating to an open interval and max mins?
y=a+ε x=b-ε ----a---y-------------x------b---real numbers
| |
a+½ε b-½ε
The OPEN interval (a,b) has no maximum or minimum element
We have 0 < ε < b-a
Proof:
No Max
Suppose that max((a,b))= x. Then x= b - ε < b - (½ε) < b. So b-½ε ∈ (a,b) ( in the set) is a larger number than max x , we have a contradiction. Therefore no max.
No Min
Suppose that min((a,b))= y. Then x= a + ε > a+ (½ε) > a. So a+½ε ∈ (a,b) ( in the set) is a smaller number than min y, we have a contradiction. Therefore no min.
Completeness property for the reals
Every NON-EMPTY set of REAL numbers that is BOUNDED ABOVE has a LEAST UPPER BOUND
Proof online
We assume this for most problems, if non empty and real with bounded above..
Doesn’t hold in Q eg set for A={ q ∈ Q: q² < 2} is non empty and bounded above but sup(A) is root 2 which Isn’t in Q
What is a suprmemum? Conditions?
When does it exist?
Relating to max?
Suprememum Sup(A) If A is NON-EMPTY and BOUNDED ABOVE it's the LEAST UPPER BOUND
(Completeness property gives this)
- a real number is the superman if it’s an upper bound for the set AND its the least upper bound for any other upper bound it’s less.
Sup ( (a,b) ) = b when maximum doesn’t exist
Sup(A) = max(A) if maximum exists
A proposition: relating supremum and epsilon
If A⊂ℝ is NON-EMPTY and BOUNDED ABOVE, then given any ε>0,
there exists a∈A st a> sup(A) -ε
Proof:
Suppose for some ε>0, such an a cannot be found
I.e. For all a∈A, a ≤sup(A) -ε. But then sup(A) -ε is a least upper bound than sup(A), a contradiction.
Theorem relating set of reals A and -A supremum
THM 1.4.3 A set A ⊂ R is bounded below IFF -A is bounded above.
FURTHERMORE if A is NON-EMPTY AND BOUNDED BELOW , then it has a GREATEST LOWER BOUND and inf(A) = -sup(-A)
proof:
Clearly A is bounded below by L IFF -A is bounded ABOVE by -L. SO WE CAN SHOW THAT A LOWER BOUND FOR A IS AN UPPER BOUND FOR -A, we don’t know if greatest this is what we are proving.
If A is NON-empty and bounded below then -A is non empty and is BOUNDED ABOVE, by the completeness property sup(-A) exists. Let α = -Sup(-A). Then for all a∈A -a ≤ -α -> a ≥ α and so α is a lower bound for the set A.
We should α is the greatest lower bound. We assume there exists a β ∈R st a ≥β > α for all a∈A, i.e. A greater lower bound. Then -a ≤ -β < -α and thus -β is a smaller lower bound for -A than -α=sup(A). Contradicting. AS WE STATED..
The Archimedean property
THM1.4.4
Often used:
Often used in convergence with x=1 and for large y=1/epsilon….
Also:
Infinitesimals don’t exist on real number line as Archimedean contradiction
Let x and y be arbitrary POSITIVE reals. Then there exists a natural st nx>y
Proof: suppose it’s false. So that for POSITIVE REALS x and y:
nx ≤ y for all n in the naturals.
Then define a set S= {nx ; for n∈N}. By our assumption this is bounded above by y. Hence by the completeness property on the reals Sup(S) exists. Hence for some natural number n, nx ∈N also (n+1)x∈S. Hence nx +x ≤ Sup(S)
-> nx ≤ Sup(S) -x ≤ Sup(S). THIS WORKS FOR ANY n IN THE NATURALS. But this means Sup(S)-x is a lower upper bound than the supremum, a contradiction.
THM 1.4.5 DENSITY OF THE RATIONALS
Given any two REALS x,y with y>x there exists a RATIONAL NUMBER q st between these two.
Proof by CASES:
*Assume x>0. Hence by the Archimedean Property of the reals there exists n∈N st n(y-x) > 1. Rearranging this we have 1+ nx < ny.
Next define set S= { a∈N: a > nx}.
This is non empty because nx>0 and by the archimedean principle there exists an M∈N such that M> nx and thus M∈S.
Thus by the WELL ORDERING PRINCIPLE there exists a minimum element in S. let this be natural number p, so we have nx LESS THAN p and p-1 less than or equal to nx which rearranged to p<1+nx.
So together nx LESS THANpLESS THAN 1+ nx LESS THAN ny which by division of n gives rational p/n we require.
Root 2?Thm 1.51
PREVIOUSLY DEFINE..
There exists α∈R with α >0, st α² =2
DEFINE
(a+b)
(-----)² > ab See other
2
Proof:
PART ONE: upper bound and introducing
Define A={a ∈R: a²<2}. This is NON EMPTY as 1∈A. Hence as bounded above, by say 3, by the COMPLETENESS PROPERTY on the reals Sup(A) = α exists.
introduce β =2/α and x= (α +β )/2. For α ≉β the defined inequality gives x²> αβ =2 and so (2/x)²= 4/x² <4/2=2.
This means 2/x∈A.
PART TWO: contradictions lead to only one case.
We can have α²<2, α²> 2 or α²=2.
α²<2: then α<2/α i.e. α
Definition of modulus
Mod(a) = max{a,-a} = a if a bigger than or equal to 0 or -a if less than 0
Sum of a rational and irrational
Test: is always irrational
Product of non zero rational and irrational
Test: is always irrational
MUST BE NON ZERO
It’s not true to say: rational, irrational? Sum prods
Sum of 2 irrationals, product of 2 irrationals
Uncountable and countable sets
Z_+ = union of N and {0} is countable
R= union of Q and Q^c is uncountable
Hence Q^c is uncountable
Q intersection with Q^c is the empty set
Q is countable
All are infinite
Sum of rationale and irrational sand product learnt!
Mod{ a-b} less than or equal to?
Mod{ a-b} is NOT less than or equal to mod(a) -mod(b)
