MATH1081 Discrete Maths (5 Viewers)

InteGrand · Aug 17, 2016

Re: Discrete Maths Sem 2 2016

Drsoccerball said:
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 · Aug 18, 2016

Re: Discrete Maths Sem 2 2016

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

leehuan · Aug 18, 2016

Re: Discrete Maths Sem 2 2016

Drsoccerball said:
$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 · Aug 18, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
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 · Aug 18, 2016

Re: Discrete Maths Sem 2 2016

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

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

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

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

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

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

Now we need to go back.

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

$\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.

$\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.

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

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

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

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

$$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})$

Drsoccerball · Aug 18, 2016

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 · Aug 18, 2016

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

Paradoxica · Aug 18, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
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 · Aug 18, 2016

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 · Aug 25, 2016

Re: Discrete Maths Sem 2 2016

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

$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)

InteGrand · Aug 25, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
$$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

$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.)

leehuan · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

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

RenegadeMx · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

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

wouldnt this be done by induction?

leehuan · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

RenegadeMx said:
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.

RenegadeMx · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
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 · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

RenegadeMx said:
oh, anyways enjoy this section its the hardest in course

Lol thanks I knew that already

leehuan · Aug 31, 2016

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.

$$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:

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

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

$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 · Aug 31, 2016

Re: Discrete Maths Sem 2 2016

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

$\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*}$

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

leehuan · Sep 4, 2016

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.

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

$$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 · Sep 4, 2016

Re: Discrete Maths Sem 2 2016

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

MATH1081 Discrete Maths (5 Viewers)

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Heroic!

Well-Known Member

Well-Known Member

Well-Known Member

Kosovo is Serbian

Well-Known Member

Kosovo is Serbian

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 5)