# MATH1081 Discrete Maths (1 Viewer)

#### InteGrand

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

Can you explain this part please? Not too sure what you mean. How does that mean x isn't in A ?
Since x is an element of B, and there is no element that is simultaneously in both A and B (since A intersection B is empty), x can't be in A.

(I.e. If x were in A, it'd be an element in both A and B, but this is impossible.)

#### Drsoccerball

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Prove that a function has an inverse iff it is is bijective$

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Prove that a function has an inverse iff it is is bijective$
Are you challenging everyone lol

Cause we actually proved this in the lecture

#### Drsoccerball

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

Are you challenging everyone lol

Cause we actually proved this in the lecture
I don't quite understand what happened so I want to see how integrand would solve it

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white The way he proved it was by considering each implication separately.\\ Let f:X\to Y be a function.$

$\bg_white First, suppose f is invertible, We need to show that it is therefore bijective.\\ To prove f is bijective, we must prove it is injective and surjective.$

\bg_white Since f is invertible, there exists some function f^{-1} that will satisfy\\\begin{align*}f^{-1}(f(x))&=x\\ f(f^{-1}(y))&=y \end{align*}

Take a break to absorb, and then we continue.

$\bg_white To prove that f is injective, suppose f(x_1)=f(x_2)\\ Then, by throwing the inverse on top of it\\ f^{-1}(f(x_1))=f^{-1}f(x_2))\\ which, by the definition of an inverse as shown above, implies x_1=x_2\\ So indeed f(x_1)=f(x_2)\implies x_1=x_2 satisfying the criteria to be injective.$

$\bg_white To prove that f is surjective, we need every y \in Y to satisfy y=f(x)\\ But we already know that y=f(f^{-1}(y))\\ So pick our x=f^{-1}y and we satisfy the criteria to be injective.$

$\bg_white Since f is both injective and surjective, it is bijective and thus the forward implication is satisfied.$

Now we need to go back.

$\bg_white Instead, suppose f is bijective. That is, it is both injective and surjective.$

$\bg_white \because f is surjective, y is f of some defined element x \in X\\ i.e. y=f(x) holds for all y, for a certain value(s) of x \in X\\$

This is just using the definition of surjection. For each output in the codomain there has to be an input in the domain.

$\bg_white \because f is injective, we have f(x_1)=f(x_2) \implies x_1=x_2\\ Hence, if the output y is the same, it came from one unique input x.\\ Hence, that value of y from above must've came from one and ONLY one x in the domain.$

So we affirm that there's a one-to-one correspondence between those values of y.

$\bg_white Thus, DEFINE x=f^{-1}(y) to be what satisfies f(x)=f(f^{-1}(y))=y$

$\bg_white Then, because one side is already done, we just need to verify that f^{-1}(f(x))=x\\ else we can't say it is the inverse.$

$\bg_white But this is true, because x is the one unique element that ensures f(x)=f(x)\\ Which is a bit of a redundancy, however it's enforcing because maintaining that f is injective, NO other element of the domain X will satisfy f(x_1)=f(x)\\ i.e. if you undo the process, you will get back to where you started. Not elsewhere.$

Which concludes the proof we were given.

Now whilst I'm here I have a question (again)

I can play around with divisibility but I don't know how to reintroduce GCD.

$\bg_white Prove that if d=\gcd (a,b), then \gcd \left(\frac{a}{d},\frac{b}{d}\right)=1$

$\bg_white I can show that 1=k\left(\frac{a}{d}\right) and 1=l\left(\frac{b}{d}\right) by just using the definition of divisibility but how does that help.\\ (note: k, l \in \mathbb{Z})$

Last edited:

#### Drsoccerball

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

d = k*a
d = l*b

1 = k*a/d

1 = l*b/d

thus gcd = 1 (not sure if actual proof lel)

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

Yeah how does 1 = k(a/d) and 1 = l(b/d) imply GCD(a/d,b/d)=1

##### -insert title here-
Re: Discrete Maths Sem 2 2016

Yeah how does 1 = k(a/d) and 1 = l(b/d) imply GCD(a/d,b/d)=1
Make substitutions.

GCD(a,b) = d <=> a = αd, b = βd (since d was supposedly the GCD, then it is necessarily true that α and β are coprime, otherwise, a contradiction would occur in the definition)

Then since α and β are coprime, GCD(a/d,b/d) = GCD(α,β) = 1

#### HeroicPandas

##### Heroic!
Re: Discrete Maths Sem 2 2016

Another method: if gcd(a, b) = d, then by Bézout's identity, there exists integers x and y such that ax + by = d. Dividing through by d yields (a/d)x + (b/d)y = 1 because d cannot be 0. Then reverse Bézout's identity to conclude that gcd(a/d, b/d) = 1.

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Consider the Poset (\{2,4,6,9,12,27,36,54,60,72 \}, \mid)$

Part a) asked for a Hasse diagram but that's a bit hard to type up. So I'll just write down which lines I had going to what

2->4
2->6
4->12
6->12
6->54
9->27
9->36
12->36
12->60
27->54
36->72

$\bg_white g) Find the least upper bound of \{2,9\}, if it exists.\\ i) Find the greatest lower bound of \{60,72\} if it exists.$

So I've forgotten how to do this properly. My answer was no for g) and 12 for i) (same as back of the book), but it was more out of intuition than proper reasoning. Can someone please explain why they are the correct answers to jog my memory?

(Or rather what is LUB/GLB v.s. the set of upper bounds/lower bounds for a subset)

Last edited:

#### InteGrand

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Consider the Poset (\{2,4,6,9,12,27,36,54,60,72 \}, \mid)$

Part a) asked for a Hasse diagram but that's a bit hard to type up. So I'll just write down which lines I had going to what

2->4
2->6
4->12
6->12
6->54
9->27
9->36
12->36
12->60
27->54
36->72

$\bg_white g) Find the least upper bound of \{2,9\}, if it exists.\\ i) Find the greatest lower bound of \{60,72\} if it exists.$

So I've forgotten how to do this properly. My answer was no for g) and 12 for i) (same as back of the book), but it was more out of intuition than proper reasoning. Can someone please explain why they are the correct answers to jog my memory?

(Or rather what is LUB/GLB v.s. the set of upper bounds/lower bounds for a subset)
g) The upper bounds of {2, 9} are by definition numbers in the poset that are multiples of both 2 and 9. These are: 36, 54, 72. So U := {36, 54, 72} is the set of upper bounds of {2, 9} here.

If there is to be a least upper bound of {2, 9}, by definition it must be a u in {36, 54, 72} such that u | v for any upper bound v. But clearly there is no such u (i.e. no element of U will divide all the elements in U). Hence there is no least upper bound.

i) The set of lower bounds of {60, 72} is by definition the set of all elements in the poset that divide both 60 and 72. This is L = {2, 4, 6, 12}. By definition, the GLB is the element m in L such that m is divisible by k for all k in L (if such an element m exists).

Clearly here, such an element does exist, namely 12. So this is the GLB we are after.

(Note that if a GLB or LUB exists, it is unique. You can easily show this as an exercise.)

Last edited:

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Prove that \left(1+\frac{1}{n}\right)^n<3\qquad (n \in \mathbb{Z}^+)$

Last edited:

##### Kosovo is Serbian
Re: Discrete Maths Sem 2 2016

$\bg_white Prove that \left(1+\frac{1}{n}\right)^n<3\qquad (n \in \mathbb{Z}^+)$
wouldnt this be done by induction?

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

wouldnt this be done by induction?
It's like the sixth question of the topic. Induction shouldn't come in so early lol.

I forgot to say: The question said to use the binomial theorem and appropriate inequalities.

##### Kosovo is Serbian
Re: Discrete Maths Sem 2 2016

It's like the sixth question of the topic. Induction shouldn't come in so early lol.

I forgot to say: The question said to use the binomial theorem and appropriate inequalities.
oh, anyways enjoy this section its the hardest in course

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

oh, anyways enjoy this section its the hardest in course
Lol thanks I knew that already

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

I also tried going about this question by the contrapositive but I'm not sure if I did it right.

$\bg_white Consider the following statement concerning a positive integer x\ge 2\\ If x is not divisible by any positive integer n satisfying 2 \le n \le \sqrt{x}, then x is a prime number.$

Proof:

$\bg_white Consider the contrapositive: If x is composite, then x is divisible by any positive integer n satisfying 2\le n \le \sqrt{x}$

$\bg_white Suppose x is composite. Then, \\ x=ab where a, b \in \mathbb Z, \quad 1 < a, b < x$

$\bg_white a and b are not both greater than \sqrt{x} as otherwise ab>x, which is a contradiction.\\ \therefore \exists a, b s.t. a\le \sqrt{x} or b\le \sqrt{x}\implies ab=x$

Therefore take either a=n or b=n and hence the contrapositive is true, hence so must the original statement be.

#### InteGrand

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white \noindent When n=1, LHS = (1 +1)^1 = 2 < 3. For n>1, we have that$

\bg_white \begin{align*}\left(1+\frac{1}{n}\right)^n &= \sum _{k=0}^{n} \binom{n}{k}\frac{1}{n^k} \\ &= \sum _{k=0}^{n} \frac{n(n-1)\ldots (n-(k-1))}{k!\cdot n^k} \\ &< \sum _{k=0}^{n} \frac{1}{k!}.\end{align*}

$\bg_white \noindent Try comparing this to a geometric series to show this sum is less than 3.$

Last edited:

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

They give me this basic idea to construct my proof and I don't know how to use it.

$\bg_white Prove that if n is a non-negative integer, then 11 is a factor of 2^{4n+3}+3\cdot 5^n$

$\bg_white Basic idea: if 2^{4n+3}=11k-3\times 5^n, then 2^{4n+7}=11(16k-3\cdot 5^n)-3\cdot 5^{n+1}$

#### leehuan

##### Well-Known Member
Re: Discrete Maths Sem 2 2016

$\bg_white Prove that a rational number can be expressed as a real number whose decimal expansion is terminating or (eventually) repeating.$

I managed to get through the converse, because the question was an iff question, but I'm not too sure how to approach it from this direction.