Proofs final review

number of ways of selecting + arranging objects

n!/(n-k)!

number of ways of selecting objects

n!/(n-k)!k!

binomial coefficient combinatorial definition

number of subsets of size k that can be chosen from n elements

combinatorial proof of (n k)=(n-1 k)+(n-1 k-1)

subset w/k elements either contains n or doesn’t.

subsets without n (n-1 k), subsets w/n (n-1 k-1)

add together

state the binomial theorem

(x+y)^n = sigma n from k=0 (n k)x^n-k + y^k

combinatorial proof of (n k) = 2^n

LHS = number of subsets of size k given n elements, 2 cases: element in subset or not, 2^n subsets for n elements

how Q is defined as equiv. classes

Q = {[(a, b)]: (a, b) in Z x (Z \ {0})}

prove square root x is irrational

suppose root is rational, define as p/q

isolate p², show how p is divisible by x

let p = xk

repeat for q, show how q is divisible by x

GCD(p, q) = 1 is false, root is irrational

prove root x + root y is irrational

suppose rational so =r

isolate one root, square everything

isolate other root with r on other side

side w/r is rational so root is rational

multiply to contradict given assumption

root x + root y is irrational

if a is rational and b is irrational, then a+b is irrational

assume a+b is rational, =r

isolate b, b must be rational

contradiction, a+b is irrational

if a is rational and b is irrational, then ab is irrational

assume ab is rational and a isn’t 0

isolate b, b must be rational

contradiction, ab is irrational

if a = 0, ab = 0, and ab is rational

prove principle of induction

let S = {n in N, p(n) is false}, and S isn’t empty

by WO, S has least element m

p(m) is false, p(n) for n<m is true

p(m-1) is true so p(m) is true by induction

contradiction, S is empty

prove principle of strong induction

let S = {n in N, p(n) is false}, and S isn’t empty

by WO, S has least element m

p(m) is false, p(n) for n<m is true

p(1), p(2), and p(m-1) are true so p(m) is true by strong induction

contradiction, S is empty

prove f^-1 is bijective and (f^-1)^-1 = f

define f^-1: T → S

suppose f^-1(t₁) = f^-1(t₂)

f(f^-1(t₁))=f(f^-1(t₂))

t₁=t₂ so f^-1 is injective

since f is bijective, f(s) = t so f^-1(t) = s

so f^-1 is surjective

so f^-1 is bijective

as defined, f is the inverse of f^-1

so (f^-1)^-1 = f

prove if f and g are injective then g o f is injective

suppose g o f(s1) = g o f(s2)

then g(f(s1)) = g(f(s2))

since g is injective, f(s1) = f(s2)

since f is injective, s1 = s2

so g o f is injective

prove if f and g are surjective then g o f is surjective

since g is surjective, g(t) = r

since f is surjective, f(s) = t

g o f(s) = g(f(s)) = g(t) = r

so g o f(s) = r and g o f is surjective

find and prove a formula for the inverse of g o f

candidate formula: (g o f)^-1 = f^-1 o g^-1

((f^-1 o g^-1) o (g o f))(s) = f^-1(g^-1(g(f(s))))

so = i_s

repeat using r instead of s

so f^-1 o g^-1 is the inverse of g o f

if S is a subset of T, prove the inclusion map from S to T has a left inverse, but not a right inverse

i: S → T, i(s) = s

left inverse: j o i = i_s

let j(t) =t for j:T → S

if t isn’t in S, j(t) is any element in S

if t is in S, j o i(s) = j(i(s)) = j(s) = s

we have a left inverse

right inverse: i o k = i_t

so i o k(t) = i(k(t)) = k(t) = t

but k(t) is in S and t isn’t

k(t) in S can’t be t so no right inverse

prove the inclusion map from R⁺ to R has infinite left inverses and no right inverses

i: R⁺ → R, i(x) = x

g is a left inverse if g o i = i_R+

for x>0 g(i(x)) = g(x) = x

for x<1 g(x) can be any number in R⁺

so infinite left inverses

h is a right inverse if i o h = i_R+

so i(h(y)) = h(y) = y

but h(y) is in R⁺, so y can’t be in R

so no right inverse