MATH1081 Discrete Maths (1 Viewer)

InteGrand · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Wait what? Now I'm confused.

I resolved my question mainly based off something like this:
$f:\mathbb{R}\to \mathbb{R}, f(x)=\frac{1}{x}\\ \text{is not a function (despite what bull high school says) because when }x=0\text{ there is no defined value for }f(0)$

I was wondering why something like this 'function' is not surjective:
$f:\mathbb{R} \to [0,\infty), f(x)=x^3$

But then I realised that it's not a function because when x<0, there are no output values.

(Edit: Or maybe I do actually. I think I might've abused the term "range")

Which thing was confusing you?

Well the second function isn't well-defined because the given "codomain" isn't really a codomain at all (a codomain should contain all the function values, but it clearly doesn't here. I.e. if f: X -> Y is a well-defined function, we should have f(x) ∈ Y for all x ∈ X, but that's not the case for your second Q., since e.g. f(-1) = (-1)^3 = -1, which is not in [0, ∞).).

leehuan · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
Which thing was confusing you?

Well the second function isn't well-defined because given "codomain" isn't really a codomain at all (a codomain should contain all the function values, but it clearly doesn't here).

Terminology. Resolved it in my mind just now.

Yeah cause they threw stuff like the first and second ones at us and they also said "a relation is a function if every element in the domain has exactly one corresponding element in the codomain". If an element in the domain didn't have a corresponding value in the codomain it fails the condition to be a function.

I think, in other words, if an element in the domain does not have a defined value in the codomain it's not a function either. The concept of "undefined" is not permitted.

leehuan · Aug 2, 2016

Re: Discrete Maths Sem 2 2016

True or false

If a function is monotone on it's domain, it is injective iff it is continuous on its entire domain.

RenegadeMx · Aug 2, 2016

Re: Discrete Maths Sem 2 2016

false, second statement doesnt always mean first will be true, tho to write it up formally...

Paradoxica · Aug 2, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
True or false

If a function is monotone on it's domain, it is injective iff it is continuous on its entire domain.

Not necessarily?

The discontinuous jump could empty out part of the domain.

Unless I don't understand the definition of injective...

¯\_(ツ)_/¯

leehuan · Aug 2, 2016

Re: Discrete Maths Sem 2 2016

Oh so replace <=> with just <= ?

(Which was what I meant. Not sure where I got iff from)

leehuan · Aug 8, 2016

Re: Discrete Maths Sem 2 2016

$$Let $f:\mathbb{Z}\times \mathbb{Z} \to \mathbb{Z}$ be the function given by $\\ f(m,n)=m^2-n^2$

$Show that $f$ is not onto.$

An easy counter case is f(m,n)=2. But how do I show that

$m^2 \neq n^2 + 2 \forall m,n \in \mathbb{Z}$

seanieg89 · Aug 8, 2016

Re: Discrete Maths Sem 2 2016

There are lots of ways. Firstly note that you can assume that m and n are non-negative without loss of generality.

You can then do it using the fact that (m-n)(m+n)=2.

An alternative approach is based on something sometimes called the discrete inequality.

If m>n, then m >= n+1 since we are working with integers. Hence...

Shadowdude · Aug 8, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
$$Let $f:\mathbb{Z}\times \mathbb{Z} \to \mathbb{Z}$ be the function given by $\\ f(m,n)=m^2-n^2$

$Show that $f$ is not onto.$

An easy counter case is f(m,n)=2. But how do I show that

$m^2 \neq n^2 + 2 \forall m,n \in \mathbb{Z}$

so i get your first line, that you want to show that no (m,n) will map to 2

use difference of two squares and the fact that 2 is a prime number, that should work

leehuan · Aug 10, 2016

Re: Discrete Maths Sem 2 2016

Very dumb question.

So I get why lcm(2²3⁵5³, 2⁵3³5²)=2⁵3⁵5³

Why is lcm(0,3) undef.?

InteGrand · Aug 10, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Very dumb question.

So I get why lcm(2²3⁵5³, 2⁵3³5²)=2⁵3⁵5³

Why is lcm(0,3) undef.?

There's some discussion about this question at this page: http://mathforum.org/library/drmath/view/62543.html .

leehuan · Aug 11, 2016

Re: Discrete Maths Sem 2 2016

Two questions please. Firstly something somewhat large.
Getting lost with the identity function, as to the identity "on what". Please clarify

$$Question: Prove that if $f:X\to Y$ and $g:Y\to Z$ are invertible, then so is $g\circ f:X\to Z$, and the inverse $g\circ f$ is $f^{-1}\circ g^{-1}$

So this is the proof that we did in class. Everything makes sense EXCEPT for the identity part which confuses me.

$$Suppose $f:X\to Y$ and $g:Y \to Z$ are invertible with inverses $\\f^{-1}: Y \to X, \quad g^{-1}:Z \to Y$

$$Then, $f^{-1}\circ g^{-1}$ satisfies the condition for being the inverse of $g\circ f$ because$\\ \begin{align*}(f^{-1}\circ g^{-1}) \circ (g \circ f)&= f^{-1} \circ (g^{-1} \circ g) \circ f \qquad \text{(associativity of composition)}\\ &= f^{-1}\circ \text{id}_Y \circ f\\ &= f^{-1}\circ f\\ &=\text{id}_X \end{align*}$

$$and:$\\ \begin{align*}(g \circ f)\circ (f^{-1}\circ g^{-1}) &= g \circ (f\circ f^{-1}) \circ g^{-1}\\ &= g\circ \text{id}_Y \circ g^{-1}\\ &= g \circ g^{-1}\\ &= \text{id}_Z\end{align*}$

My question is basically, how did they know which set to use as the subscript on the identity function?

And a somewhat smaller question (hopefully): Just regarding the inverse image of a set (under a function). Is the following statement true?

$x \in f^{-1}(S) \iff f(x) \in S$

InteGrand · Aug 11, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Two questions please. Firstly something somewhat large.
Getting lost with the identity function, as to the identity "on what". Please clarify

$$Question: Prove that if $f:X\to Y$ and $g:Y\to Z$ are invertible, then so is $g\circ f:X\to Z$, and the inverse $g\circ f$ is $f^{-1}\circ g^{-1}$

So this is the proof that we did in class. Everything makes sense EXCEPT for the identity part which confuses me.

$$Suppose $f:X\to Y$ and $g:Y \to Z$ are invertible with inverses $\\f^{-1}: Y \to X, \quad g^{-1}:Z \to Y$

$$Then, $f^{-1}\circ g^{-1}$ satisfies the condition for being the inverse of $g\circ f$ because$\\ \begin{align*}(f^{-1}\circ g^{-1}) \circ (g \circ f)&= f^{-1} \circ (g^{-1} \circ g) \circ f \qquad \text{(associativity of composition)}\\ &= f^{-1}\circ \text{id}_Y \circ f\\ &= f^{-1}\circ f\\ &=\text{id}_X \end{align*}$

$$and:$\\ \begin{align*}(g \circ f)\circ (f^{-1}\circ g^{-1}) &= g \circ (f\circ f^{-1}) \circ g^{-1}\\ &= g\circ \text{id}_Y \circ g^{-1}\\ &= g \circ g^{-1}\\ &= \text{id}_Z\end{align*}$

My question is basically, how did they know which set to use as the subscript on the identity function?

And a somewhat smaller question (hopefully): Just regarding the inverse image of a set (under a function). Is the following statement true?

$x \in f^{-1}(S) \iff f(x) \in S$

For your last Q., yes, that's true.

InteGrand · Aug 11, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Two questions please. Firstly something somewhat large.
Getting lost with the identity function, as to the identity "on what". Please clarify

$$Question: Prove that if $f:X\to Y$ and $g:Y\to Z$ are invertible, then so is $g\circ f:X\to Z$, and the inverse $g\circ f$ is $f^{-1}\circ g^{-1}$

So this is the proof that we did in class. Everything makes sense EXCEPT for the identity part which confuses me.

$$Suppose $f:X\to Y$ and $g:Y \to Z$ are invertible with inverses $\\f^{-1}: Y \to X, \quad g^{-1}:Z \to Y$

$$Then, $f^{-1}\circ g^{-1}$ satisfies the condition for being the inverse of $g\circ f$ because$\\ \begin{align*}(f^{-1}\circ g^{-1}) \circ (g \circ f)&= f^{-1} \circ (g^{-1} \circ g) \circ f \qquad \text{(associativity of composition)}\\ &= f^{-1}\circ \text{id}_Y \circ f\\ &= f^{-1}\circ f\\ &=\text{id}_X \end{align*}$

$$and:$\\ \begin{align*}(g \circ f)\circ (f^{-1}\circ g^{-1}) &= g \circ (f\circ f^{-1}) \circ g^{-1}\\ &= g\circ \text{id}_Y \circ g^{-1}\\ &= g \circ g^{-1}\\ &= \text{id}_Z\end{align*}$

My question is basically, how did they know which set to use as the subscript on the identity function?

And a somewhat smaller question (hopefully): Just regarding the inverse image of a set (under a function). Is the following statement true?

$x \in f^{-1}(S) \iff f(x) \in S$

$\noindent For a set $A$, the identity map/function on $A$ (which we can denote $\mathrm{id}_A$) is the function that has domain and codomain $A$ and just maps each element of $A$ to itself. In other words, $\mathrm{id}_A \left(x\right) = x$ for all $x \in A$.$

$\noindent Now, if $\phi$ is some function with domain $A$ and codomain $B$ say, and if $\phi$ is invertible, then it means that $\phi ^{-1} \left(\phi \left(a\right)\right) = a$ for all $a \in A$ and $\phi \left(\phi ^{-1} \left(b \right) \right) = b$ for all $b\in B$. In other words, the composite function $\phi ^{-1} \circ \phi \colon A \to A$ just maps every element $a\in A$ to $a$, which means $\phi ^{-1} \circ \phi$ is just $\mathrm{id}_A$. Similarly, $\phi \circ \phi ^{-1}\colon B\to B$ maps every element in $B$ to itself, so is just $\mathrm{id}_B$. So the reason for why it's the identity on these particular sets is due to what the domain and codomain of these composite functions are (\underline{which is just the domain of the function on the right}).$

$\noindent So for example, in your particular Q., $g^{-1} \circ g$ is $\mathrm{id}_Y$ because $g^{-1}\circ g$ has domain and codomain $Y$. (Because $g$, the right function, has domain $Y$.)$

leehuan · Aug 11, 2016

Re: Discrete Maths Sem 2 2016

Ahhh thanks

I sorta thought in that direction after I posted but got lost and needed it cleared up

leehuan · Aug 13, 2016

Re: Discrete Maths Sem 2 2016

$$Proven: $\frac{3}{k}+\frac{4}{k+1}-\frac{7}{k+2}=\frac{10k+6}{k(k+1)(k+2)}$

Please check my working. There's no solutions again

(I took out a few trivial steps to reduce reading)

$\begin{align*}\sum_{k=1}^n\frac{5k+3}{k(k+1)(k+2)}&= \frac{1}{2}\sum_{k=1}^n\left(\frac{3}{k}+\frac{4}{k+1}-\frac{7}{k+2}\right)\\ &= \frac{1}{2}\left[3\sum_{k=0}^{n-1}\frac{1}{k+1}+4\sum_{k=1}^n\frac{1}{k+1}-7\sum_{k=2}^{n+1}\frac{1}{k+1}\right]\\ &= \frac{1}{2}\left[3-\frac{3}{n+1}-\frac{7}{n+2}+\frac{7}{2}\right]\end{align*}$

InteGrand · Aug 13, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
$$Proven: $\frac{3}{k}+\frac{4}{k+1}-\frac{7}{k+2}=\frac{10k+6}{k(k+1)(k+2)}$

Please check my working. There's no solutions again
(I took out a few trivial steps to reduce reading)

$\begin{align*}\sum_{k=1}^n\frac{5k+3}{k(k+1)(k+2)}&= \frac{1}{2}\sum_{k=1}^n\left(\frac{3}{k}+\frac{4}{k+1}-\frac{7}{k+2}\right)\\ &= \frac{1}{2}\left[\sum_{k=0}^{n-1}\frac{1}{k+1}+4\sum_{k=1}^n\frac{1}{k+1}-7\sum_{k=2}^{n+1}\frac{1}{k+1}\right]\\ &= \frac{1}{2}\left[3-\frac{3}{n+1}-\frac{7}{n+2}+\frac{7}{2}\right]\end{align*}$

I think you just made a typo in the second last line (left out a 3 as a coefficient for the first sum, but I'm sure you had it in your working out on paper), but otherwise looks good. You can (and should!) test formulas like this with easy values of n, e.g. n = 1 or 2 etc.

leehuan · Aug 13, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
I think you just made a typo in the second last line (left out a 3 as a coefficient for the first sum, but I'm sure you had it in your working out on paper), but otherwise looks good. You can (and should!) test formulas like this with easy values of n, e.g. n = 1 or 2 etc.

Oh of course! Thanks

could be a handy tip for the actual test. (Too bad it's non calculator haha)

And just one more please

$$Prove that $\{ x \in \mathbb{R} | x \ge 1 \}$ is a proper subset of $\{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

$\text{Let }k \in \{ x \in \mathbb{R} | x \ge 1 \}\text{ then }\\ \begin{align*}k&\ge 1\\ \implies (k-1)&\ge 0\\ \implies (2k+5)(k-1)&\ge 0 \qquad \text{ as }k\ge 1 \implies 2k+5\ge 7 > 0\\\implies 2k^2+3k-5 &\ge 0\\ \implies 2k^2+3k &\ge 5\end{align*}$

$\therefore k \in \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}\\ \therefore \{ x \in \mathbb{R} | x \ge 1 \}\subseteq \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

$\\ \text{But }-3 \in \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}\\ \text{yet }-3 \notin \{ x \in \mathbb{R} | x \ge 1 \}\\ \therefore \{ x \in \mathbb{R} | x \ge 1 \}\subset \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

InteGrand · Aug 13, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Oh of course! Thanks could be a handy tip for the actual test. (Too bad it's non calculator haha)

And just one more please

$$Prove that $\{ x \in \mathbb{R} | x \ge 1 \}$ is a proper subset of $\{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

$\text{Let }k \in \{ x \in \mathbb{R} | x \ge 1 \}\text{ then }\\ \begin{align*}k&\ge 1\\ \implies (k-1)&\ge 0\\ \implies (2k+5)(k-1)&\ge 0 \qquad \text{ as }k\ge 1 \implies 2k+5\ge 7 > 0\\\implies 2k^2+3k-5 &\ge 0\\ \implies 2k^2+3k &\ge 5\end{align*}$

$\therefore k \in \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}\\ \therefore \{ x \in \mathbb{R} | x \ge 1 \}\subseteq \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

$\\ \text{But }-3 \in \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}\\ \text{yet }-3 \notin \{ x \in \mathbb{R} | x \ge 1 \}\\ \therefore \{ x \in \mathbb{R} | x \ge 1 \}\subset \{ x \in \mathbb{R}| 2x^2+3x \ge 5 \}$

Even without a calculator, we could test n = 1 for that sum decently easily, because then we don't need to sum up terms for the LHS, making it the easiest case to test, (just calculating the RHS would need some work, but it's still pretty easy). In general also it's a good idea to check any formulas or answers you get for maths problems by checking simple or extreme cases and seeing if they match your intuition or explicit calculation (because sometimes simple cases' answers can be explicitly calculated with relative ease, and thus compared against your general formula).

And yeah, your working is correct for that last Q.

(If you're worried about pendantic markers etc., you might want to calculate the value of the quadratic when x = -3 to explicitly show it's greater than or equal to 5.)

Drsoccerball · Aug 17, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
$$ Suppose $x\in B \subseteq U$. Then since $A\cap B = \emptyset$ (i.e. $A$ and $B$ are disjoint), $x$ is not in $A$, or in other words, $x$ is in $A^{c}$

Can you explain this part please? Not too sure what you mean. How does that mean x isn't in A ?

MATH1081 Discrete Maths (1 Viewer)

Well-Known Member

Well-Known Member

Well-Known Member

Kosovo is Serbian

-insert title here-

Well-Known Member

Well-Known Member

Well-Known Member

Cult of Personality

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

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