# 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

#### Drsoccerball

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

#### leehuan

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

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

Take a break to absorb, and then we continue.

Now we need to go back.

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

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

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.

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)

• HeroicPandas

#### 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

• leehuan

#### 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 and Drsoccerball

#### leehuan

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

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

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

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

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

#### leehuan

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

Last edited:

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

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

#### 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.

Proof:

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

Last edited:
• leehuan

#### 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.

#### leehuan

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

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.