discrete-math

[blazing rose]

What would be the easiest way to figure out if this is true or false?

R7 means remainder when divided by 7

[meager prawn]

2^3 = 8 so R7(2^3) = R7(2^0) = 1

hence by induction, R7(2^(3n)) = R7(2^(3n-3)) = 1

Hence R7(2^1000) = R7(2^999 * 2) = R7(2^(3*333)) * R7(2) = 1*2 = 2

,w 2^1000 mod 7

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by mateo713

[meager prawn]

though in this case

the remainders modulo 7 of the powers of 2 are 1, 2, 4 (repeating as shown)

so 3 isn't a possible value

[blazing rose]

Ahh makes sense Tysm

[meager prawn]

and in this case, this is a simpler proof, since you asked for "the easiest way"

[steep ether]

great so pretty much what i thought

How do I approach this, the main approach i saw is too check each number and pair it with another number in A, then make arrows between the pairs but is there a simplier/faster way? I'm going to do both but want to practice with something faster

so like -3,-3 is a pair since mod 3 would be = 0 so i draw an arrow between

[wind peak]

$$\text{Given }f(x) = cos(x) \text{ defined for } \left{ \frac{k\pi}{6} , : , k \in \mathbb{Z} \right}$$
I have to find the equivalence classes given by the relation
$$x \sim y \Leftrightarrow f(x) = f(y)$$
and the canonical projection $$p: A \rightarrow A/\sim$$
I don't know the difference between the two. I know x and y are related if $$f(x) = f(y)$$ but I don't know how to continue from there.

[vital dew]

Aguacate

[wind peak]

Actually, even better, can someone explain to me the difference between these three things? A/∼ ; the relationship given by x ∼ y ⇐⇒ f(x) = f(y) ; and p: A → A/∼ ?

[sick grail]

the first is the set of equivalence classes, the second is uhh the relationship between them (idk how to explain this in a different way), and the third is the function that associates an element with its equivalence class

e.g. the toy case of $\bN$ and $\sim$ given by equal remainder mod 2 i.e. $x\sim y$ if both are even or both are odd\\Then $\bN/{\sim}$ is ${O, E}$ where $O = {1,3,5,\dots}$ and $E = {0,2,4,6,\dots}$ (maybe without $0$ depending on convention)\\the relation is just the relation or $(O\times O)\cup (E\times E)$ as a set\\the canonical projection is the function with $$f(x)=\begin{cases}O&x\in O\E&x\in E\end{cases}$$

[vital dew]

Edward II

[wind peak]

so then $\bN{/}\sim$ is just $\bN ?

[vital dew]

Aguacate
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[sick grail]

no, because N/~ has two elements, and N has infinitely many

those two elements of N/~ are themselves sets

[wind peak]

so its the same? its just a way of dividing the set N

[sick grail]

it is a way of dividing N i.e. a parition

no it is not the same

in the same way N and {N} are not the same (I have a drawing for this separate question wait a sec)

https://cdn.discordapp.com/attachments/359052604149465088/1167495504121315348/image.png?ex=654e55eb&is=653be0eb&hm=3221d0ef4730b0a3caf11f61934f6cdd95136c616be7ff69a60ad36ac7738afb&

if you think of the yellow box as the set N, and the things inside as the numbers, the left box is N

[wind peak]

waaaiiit

[sick grail]

the right box is {N}, the set containing the set of natural numbers, which when drawn like this is clearly something else

this is similar, except now we just have two boxes O and E i.e. odds and evens

[wind peak]

It feels strange, even though I understand what you mean

Only thing is, if we can say say that N = { {1, 3, 5, . . . } , {2, 4, 6 . . . } } and N/~ = {O,E}
Then, O = {1, 3, 5, . . . } and E = {2, 4, 6, . . . }, can't we just say that N/~ = { {2, 4, 6, . . . } , {1, 3, 5, . . . } }, and thus N = N/~ ?

[sick grail]

except we can't say that N = { {1, 3, 5, . . . } , {2, 4, 6 . . . } }

N = {1,3,5,...,2,4,6,...}

with only one set of curly brackets

[wind peak]

Oh right it would be if anything N = { {1, 3, 5, . . . } U {2, 4, 6 . . . } } right?

which is not the same thing

[sick grail]

still not quite because that's { {1,2,3,...} }

still two sets of curly brackets

N = {1, 3, 5, . . . } U {2, 4, 6 . . . } would be correct

[neon harbor]

In general, I don't think there's a faster way, but in this case you can exploit some symmetries to reduce the amount of computation. The set A has 7 elements, and thus 7*7 pairs, but I think you should be able to draw the graph by just checking 6 pairs of numbers

[cerulean gate]

hey is anyone on, I needed some help with my question

i am getting that last answer wrong

i don't understand why

[steep ether]

Cool, appreciate the help!

[steep ether]

we were slightly wrong, 2 and 1 are in the same equivelence class i just realized by reviewing but i think its correct now

[upbeat flame]

hi everyone

i need some help

using the Schroeder-Bernstein Theorem could you please guide me on how to potentially approach the question? I understand I need to find both an injective and surjective function between both sets, but I am unsure how I'd approach it. Thanks!

[brave rock]

I hope a surjection is easy to find. Hint for an injection: prime factorisation

[upbeat flame]

ohh

i see

but can you map to 1 ?

wait

I got it thank you

[vague mist]

Good evening.

The set of strictly positive natural numbers is the union of two disjoint subsets:
$ {f(1), f(2), ..., f(n), ...} \ and \ { g(1), g(2), ..., g(n) , ...} $.
Checking the conditions:
\begin{enumerate}
\item The sequences f and g are increasing
\item g(n) = f(f(n)) + 1 for all n $\geq 1$

\end{enumerate}
Questions
\begin{enumerate}
\item Calculate f(1), f(2) and f(3)
\item Find an algorithm that calculates f(n)
\end{enumerate}

I calculated f(1)=1 and g(1)=2.
But since the functions are not strictly increasing, I manage to keep f(n)=1 without too much contradiction.
I don't see if I made an error in reasoning or how to find the images.

[vital dew]

Martin

[meager prawn]

f(n) = 1 is clearly wrong because you're supposed to partition N
N is not just {1, 2}

[vague mist]

What I meant is that we can have f(2)=1, f(3)=1, and f(4)!=1.
We can have f(n)=1 up until a certain number before change.

[meager prawn]

if you just try and construct it step by step, you'll get there without much trouble just by trying to fill N up

I just gave myself the assumption f(n) >= n to hope it would get me somewhere, and it did suffice

[vague mist]

I see.
I think the exercise suggests that these two functions are unique.
So shouldn't there be a way to prove that inequality ?

And even with that, I am still blocked.
I found that f(1)=1, f(2)=3, g(1)=2 but I can't find the rest.

[meager prawn]

I think you can try to find a solution by assuming f(n) >= n.
Then g(n) > f(n).
Hence f(2) must be 3.
Then g(2) = f(3)+1 isn't any f(n)

||So we may say f(3) = 2 or f(3) = 3 for the smallest values possible
If f(3) = 2, g(2) = f(2) is contradictory, so we are reassured that f(n) >= n is probably still going to yield a solution||

||So let's say f(3) = 3 = f(2)
Then g(2) = 4, g(3) = 4 too.||

||Let's be bold and say we spot a pattern, let's claim f(4) = f(5) = 5
Then g(4) = f(5)+1 = 6 = g(5)||

||And in general, if f(2n) = f(2n+1) = 2n+1
g(2n) = 2n+2 = g(2n+1)||

||This does give a partition of N into odd/even and both f and g are increasing.
So we have found our solution.||

[vague mist]

I see.
Thank you very much.

[neon jewel]

Are there any good resources to learn modular arithmetic and congruence? Looking for any good books/videos

[brave rock]

joke answer: A Course in Arithmetic by J P Serre
Serious answer: Elementary Number Theory by G A Jones and J M Jones

[brave rock]

But for real don't use the Serre book, it's just a joke.

[faint sphinx]

What do you mean? It's arithmetic, which means it must be trivial!

[weary tiger]

Hello, I'm trying to solve a recurrence relation... Im using the characteristics roots technique.
Textbook example:
(a_n) = (7a_n-1) - (10a_n-2 ) with a_0=2 and a_1=3

rewrite: x^2 - 7x +10 = 0
(x-2)(x-5)=0

Then it says the recurrence relation must be the form:
a_n = a2^n + b5^n

I dont understand how they know which root will be paired with a or b

[opal crescent]

it doesn't matter

a and b are just placeholders for constants you'll find just after (with the initial conditions)

I could have called a , and b

@weary tiger

[weary tiger]

but isnt it true that the constants will be paired with one of the roots in a way where the pairing matters?

[livid hull]

Hi everyone!

Is there a generator tool where you can plug in a compound proposition and it'll generate the logical identities steps that show whether it is a tautology or not? Feel like it would be useful to know (for srust purpoes of course).

[opal crescent]

well you can't just exchange the constants afterwards sure

but since you haven't solved for them with the initial conditions yet, they're just arbitrary

any choice of a and b will give you a solution to the recurrence relation

[weary tiger]

ohhhhhhh i see

[opal crescent]

(just not the one with a_0 = 2 and a_1=5)

[weary tiger]

a and b are just the placeholder for the value at the specific position in the formula

basic ahh algebra

my b

thanks my friend

[twilit current]

why does A + A'B = A + B

[coral parcel]

Determining just whether a given proposition is a tautology or not is essentially the SAT problem, which is NP-complete

There are SAT solvers out there which perform pretty well on many actually occurring problem instances (even though their running time is exponential in the worst case). They'll give you a counterexample if the formula is not a tautology, but I wouldn't expect them to produce human-friendly proofs if it isn't. (Perhaps I'm wrong about that, though).

[keen cave]

for this, can I index shift for it to become

this?

or is it not allowed to do things in parenthesis only outside

[twilit current]

nah

i asked a simple question

help me

[twilit current]

is this answer for me

from my skim reading i saw too many big words for me to actually read it

[weary tiger]

yes

[keen cave]

but I thought only outside

how can it be inside

[keen cave]

you can try using distributive laws

then simplify and see urself

[coral parcel]

Sorry no, it was for @livid hull, but somehow I lost the reply marking while typing.

[keen cave]

A or not A AND A or B

A or (not)A is always True

so therefore T AND A OR B

is just A or B

aka A + B

[twilit current]

wait

u just said A or (not)A is always true

[keen cave]

yea

[weary tiger]

at least for this case you can see that these sums are equal

[twilit current]

so its True AND B

which is just b

i dont see why its A or B

where u bringing that extra a from

[coral parcel]

Try working out a truth table?

[keen cave]

fr I tried doing both ways when n = 2 I got 41 by fully distributing, and doing one by one. and I got 50 when using the 2nd method

I probably did it wrong

[keen cave]

TRUE and A or B

(True) AND (A OR B)

anything true with and is just itself

[weary tiger]

also if you override k := k + 3 then the first sum will become the second sum

[keen cave]

rn i am drawing on a trackpad

[keen cave]

Ohhh I see

Okay thank you. I see that it is correct

[twilit current]

okay so like algebra u it was A + (A '. B) u expanded the bracket to (A + A') + (A+B) then first bracket is always 1 so it becomes 1 . (a+b)

and 1 and'd with anything is always anything

[keen cave]

exactly, I used distributive rule

[twilit current]

that makes sense but

i want to know

why the + changed to andhere

[keen cave]

to and?

which line

1st 2nd 3rd or 4th

[keen cave]

oh you mean in general?

[twilit current]

the arrow wasnt there

mb

now it is

wait

nvm

it was always and

why was it and

[keen cave]

yeah

[twilit current]

not or

[keen cave]

because you distribute

[twilit current]

oh yeah

i forgot

it works like that

[keen cave]

yeah lol it takes some time getting used to

[twilit current]

okay thank u for epxlaining

[fringe gyro]

Which of these relations are equivalence relations? Explain which of the equivalence relation definition’s properties are possessed by the relation (if any) and which are not (again, if any).
(a) {(a,a),(a,d),(b,d),(c,c),(c,d),(d,a),(d,b),(d,c),(d,d)} on {a,b,c,d}
(b) {(e, f ) | e and f have the same color fur} on the domain of ‘puppies.’

for a i said its not an equivalence relation because its not reflexive or transitive

but i am confused by the wording for the set in part b

could anyone please help me, it would be greatly apreciatied!

[weary tiger]

you don't need a set like in a), you can just check if relation is reflexive, symmetric and transitive

for example, relation is reflexive because any puppy "e" has the same fur color as himself

[astral forge]

Anybody?

[weary tiger]

i guess answer is 1, 2, 4 because any undirected planar graph has less than n*(n-1)/2 = 14196 edges. to conradict 3rd you can just take a polygon with 169 vertices and it's a planar graph

[astral forge]

yes. the answer is 1. I didn't know about this formula

Is there specific name of it?

How you derived this formula? Or what topic exactly do I need to read?

[weary tiger]

it's C(2, n), or amount of different pairs of n, which is obviously maximum amount of edges

[astral forge]

I did't get you. This part -> C(2, n),

[weary tiger]

it's binomial coefficient https://en.wikipedia.org/wiki/Binomial_coefficient

[astral forge]

How is it relevant here? Why given 169 vertices of planar graph becomes 14196?

[weary tiger]

14196 is the maximum of edges in this graph, as in the question

[faint sphinx]

You can think about it this way. You've got a simple connected graph on n vertices, which means that each vertex can have at most n-1 edges incident to it. Thus, we get an upper bound of sum_{k=1}^n (n-1) = n*(n-1) for the degrees. By the handshaking lemma, #{edges} = (sum of degrees)/2, so there are at most n*(n-1)/2 edges.
To see that this upper bound is achieved (that is, there is no better upper bound), consider the complete graph on n vertices.

[ornate coral]

But is there any stronger upper bound? I am just wondering how would one go about finding the actual strongest upper bound(kind of like the supremum of the set containing the possible number of edges in a planar graph having 169 vertices)?

[haughty garden]

I think we're forgetting that such a graph is planar with n >= 3

it turns out that there's a stronger bound on the number of edges

namely, |E| <= 3n - 6

[faint sphinx]

Oh shoot planar

[fringe gyro]

would the answer be yes, its equivalent since it meets the reflexive, symetric, and transitive requirement?

[ornate coral]

Yes.

[royal canyon]

When an implication is said to be true, do we typically mean the case where both antecedent and conclusion are true and thus the implication true? Or should we also consider the vacuous truth cases when the antecedent is false

[astral forge]

okayyy

[keen cave]

np!

[vast basin]

always consider both

[fringe gyro]

Are these functions from Z to R? If the answer is ‘No,’ explain why.
I am confused by these problems, could someone point me in the right direction, thank you!

[little prism]

can you plug every integer into these expressions? is the result always a real number?

[hushed wagon]

(a , b) -> (2 ^ a * 2 * 3 ^ b)

[terse quarry]

hello

can someone explain what's the difference between mapping and relation?

briefly

[tight hound]

A relation from a set X to a set Y is any subset of the Cartesian product of X and Y. A mapping(or function) from X to Y is a relation R from X to Y such that for every a ∈ X, there exists exactly one b ∈ Y such that (a,b) ∈ R.

[true token]

s7a s7aa

[true token]

so a function is a specefic type of relations ,

studying sets-functions then relations is a bit weird

[charred prism]

Is there some way i can adapt this corollary for inequalities x_1 + x_2 + ... + x_n <= r with restrictions such as x_a >= b? I know i can use a summation when x has no restriction but i'm unsure how to do it with restrictions on x

[haughty garden]

define y_a = x_a - b >= 0

[last flicker]

For sure! Introduce a new variable y_a=x_a-b, so that y_a>=0

[charred prism]

will this catch all the solutions? even when there are different restrictions on each x_a?

[snow sleet]

yes. Let me give the following explanation.

The corollary is counting the number of ways to distribute r indentical balls into n distinct boxes. (boxes can be empty hence the corollary is about nonnegative integer solutions (x_1,x_2,...,x_n)). So let's talk about your idea. Suppose for each i in {1,2,3,...,n}, we require x_i be at least a_i. Then x_i-a_i is an integer at least 0 (assuming a_i is an integer for each i in {1,2,3,...,n}). Now to put this into physical terms we can count such distributions with this restriction on boxes by filling up each of the boxes to their required minimum ball count. That is distribute a_1+a_2+...+a_n balls from the r total balls such that each box has reached it's minimum count requirement. Then you just have r-(a_1+a_2+...+a_n) balls to distribute into boxes that now can be viewed as integers that can be 0 or positive. So invoking the corollary, we find the number of such distributions is given by C[(n-1)+r-(a_1+a_2+...+a_n) , r-(a_1+a_2+...+a_n)]. Make sense?

as you can see, if a_1+a_2+...+a_n>r then at least one a_i is an unrealistic minimum requirement for the corresponding x_i.

feel free to tag me if it doesn't make sense

[charred prism]

yeah thank you i understand

[fringe turret]

In "if p, then q" I know that when p is false, q can be anything and will render to true. That is "F -> T = T" or "F -> F = T". This is also called vacuously true. My question is why only true, why not false?

[snow sleet]

p->q is defined to be false exactly when p^~q occurs. To put it into perspective. Suppose the conditional statement is "If I live in New York, then I live in the U.S." Suppose now that I don't live in New York. Is the statement in quotes now redered false? No. It's a hypothetical "if".

the statement says if I live in New York, then I am guarateed to live in the U.S. So if I don't live in New York this statement doesn't apply to me but it's still true nonetheless

does that make sense @fringe turret ?

[fringe turret]

Suppose now that I don't live in New York. Is the statement in quotes now redered false? No. It's a hypothetical "if".
No, it will render true because you do live somewhere which is not in NY

[snow sleet]

if it said "I live in New York....", then me not living in New york would make be false. It's all about the "if". If I take out that "if", then I'm left with "I live in New York..."

[fringe turret]

Also lets say you dont live in Texas, then it is still in USA therefore it will render the statement true.

The definition makes sense in light of this example. However, I didn't understand the politicians example from the book which is equivalent to, "If I win the elections, then I will cut tax percentage."

[snow sleet]

If the politician doesn't win the elections, then based on the content of p in p->q, the politician will not cut tax percentage as they will not have the power to do so. So really it's "I cut the tax percentage if and only if I win the election.". But because we are concerned with the structure of p->q and not actually the content (in the realm of mathematics), ~p doesn't imply ~q unless it is also given to us that q-> p.

[fringe turret]

~p doesn't imply ~q unless it is also given to us that q-> p.
That will happen if they are biconditionals, right? That is p <--> q

Also, do you think true/false in this context becomes convoluted. Specially for the one coming from boolean algebra background or comp sci? Wouldnt it be more intuitive to "it doesn't disprove the statement" instead of "true"?

[snow sleet]

yes if we are given both p->q and q-> p, then we have p<->q

[snow sleet]

it not disproving means it is true, right? in the context of boolean algebra. If not 0, then 1.

or if not F, then T

whichever u use T,F or 1,0

[sonic blaze]

Hi everyone

How should I prove this rigorously ?

Im thinking I can write like this
State that the subcycles (or whatever they are called) are pairwise disjoint so i we prove this property for some subcycle we can generalize for the whole formula

Then prove (i1 … ik) ^-1 = (ik … i1)
So that means prove that (i1 … ik) * (ik … ik) = epsilion

[meager prawn]

The "caution" property holds if the inverses commute, since in general (xy)^-1 = y^-1 x^-1
Then yes just prove that the inverse of a cycle is the cycle in reverse order

[silk void]

what is improved dijkstra's algorithm

i cannot find any good video of this topic

[coral parcel]

Doesn't sound like a standard name.

[silk void]

what is it then?

[coral parcel]

Ask the person who used the term what they meant by it.

[silk void]

🙂

it is a topic in topic in graph theory

[cosmic moss]

which rule should it be?

[haughty garden]

I suppose you’re referring to Dijkstra with Fibonacci heaps

[sonic blaze]

… so here i just need to prove that the inverse is the reverse order?

[meager prawn]

Depends on what you can take for granted and what you can just say.
But either way you need to argue for the general formula one way or another

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by cedric_

[native berry]

If anyone can help me with this id really appreciate it

[haughty garden]

We count the number of committees of k >= 1 people with a chairperson in two ways.

LHS: Firstly, choose any subset of k people to be in the committee. Then out of these people, we choose one person to be the chairperson. This is done in k * C(n, k). The sum tells us that the size of the committee can be made arbitrarily.

RHS: Alternatively, we can first pick the chairperson and then out of the remaining (n - 1) people, we choose any subset of people to form the rest of the committee. This counts exactly what the LHS counts because choosing the subset of people gives us an arbitrarily sized committee

[native berry]

Thank you! I was able to make sense of this problem

I do have another question @haughty garden . What is the approach of this?

I understand this to be a stars and bars problem

[haughty garden]

You basically want to find the number of nonnegative solutions of x_1 + x_2 + ... + x_r = n such that x_i >= m_i for each i = 1, 2, ..., r

Set y_i = x_i - m_i >= 0 such that

n = x_1 + x_2 + ... + x_r = (y_1 + m_1) + (y_2 + m_2) + ... + (y_r + m_r)
=> y_1 + y_2 + ... + y_r = n - (m_1 + ... + m_r)

[twilit sundial]

i'm thinking it's 10*9^3*[something]/5 but not sure what that last "something" would be

[haughty garden]

For a cycle graph on 5 vertices, it is not possible to have a proper colouring with 1 or 2 colours; 1 is obvious, 2 can be shown with the pigeonhole principle. For three to five colours, think of it as "arrangement in a circle such that no two people (vertices) in the same group (colours) are adjacent"

[twilit sundial]

i know the definitions and everything, i'm just getting a bit hung up on how to color the last vertex

[twilit sundial]

or are you suggesting to do casework on the chromatic number?

[haughty garden]

you can take cases based on the number of colours

e.g. if there is a colouring with three colours, how many such colourings can you have?

[twilit sundial]

yea that seems like the easier approach

less of a headache to characterize such a coloring

[haughty garden]

you can also just focus on the colourings themselves since you can say "well, there are C(10, 3) ways to choose the three colours; now describe the number of ways to colour the graph with these colours"

[twilit sundial]

it's gonna look smth like

CABAB

or a permutation thereof

[haughty garden]

yea pretty much

[twilit sundial]

yea

[haughty garden]

should hopefully be an easier task now

[twilit sundial]

yea thanks

[snow sleet]

Let me refer you to this convo. (see next thing I reply too).

[snow sleet]

here^

Another person asked about pretty much the same thing

[astral forge]

Anybody? I understood how 1 and 4 are correct options but not how option 2 is incorrect while 3 is correct.

[vestal bronze]

@astral forge in option 2, you have to go 1→3 not 1→2

the options say what rule to use

[astral forge]

Yeah right In DFS we have to explore one vertex to the core then move to the other vertex. Understood

Why option 3 is correct?

In option 1 and 3, by using BFS suppose we reach at vertex 5

so we can mark vertices 6 and 7 as visited in any order?

[vestal bronze]

yes

the only way to do BFS wrong here is if you go to 3 too fast

you don;t prioritize smaller numbers, they said random order

[astral forge]

@vestal bronze

[astral forge]

Right. Because in question random order is mentioned, we do not prioritise 6 over 7 or 7 over 6?

[vestal bronze]

yes

[astral forge]

Cool

thanks for helping.

[real tiger]

Hiya,
Can I use

f ∶ R→R where f(x)=x^2+1
Let a, b ∈R show a ≠ b when f(a) = f(b)

as a formula for a proof for a 'not injective' function ?

Then use an example such as
a = -5, b =5, f(-5) = f(5) = 26

[hushed wagon]

you mean finding distance of any vertices from source even in graphs which has negative weights on their edges?

[olive pine]

Can someone explain whats happening in the parts in red box. i really dont understand this stuff

[wooden remnant]

Hi folks, new guy here. Can anyone explain for a not-at-all-a-math-guy the logic behind modding negative numbers? I understand that 15 mod 10 = 5 - 10 goes into 15 once, with 5 left over. But for example "-33 mod 10" = 7, and I don't quite get where that comes from. I'm taking a discrete class and it's in the textbook, and unfortunately my professor responded to my question with a section from a different textbook... I've historically been bad at math so doubling up on texts isn't really working.

[brave rock]

You're thinking of modular arithmetic in a less useful way

Do not think of "mod" as an operation that gives you the remainder of a number when divided by another. Think of mod as a relationship between numbers. So we would write -33 = -23 mod 10, for example.

N.b. I am not saying -33 = (-23 mod 10). Some people write this in a way that changes the equality sign rather than writing something on the end, so they might write:

$-33 \equiv_{10} -23$

[vital dew]

jan Pojeki

[brave rock]

Now as for remainders, which is what you're actually talking about, we have an important result:

[wooden remnant]

(thank you)

[brave rock]

Let $m$ be a positive integer. Then for any integer $n$, there exists a unique pair of integers: the quotient $q$ and a remainder $r$ such that $n = qm + r$ and, crucually, $0 \leq r < m$.

[vital dew]

jan Pojeki

[brave rock]

When you're talking about "-33 mod 10" you are really asking "what is the remainder of -33 upon division by 10"

Now the way we do this is by noting that q=4 works. -33 = -4*10 + 7.

So r = 7 is the remainder.

[wooden remnant]

aha! That last bit works for me

Almost.. So -22 mod 9 = 5, in that -9*2= 18, and then it's a difference of 5 to get to -22?

My head wants it to be -5, eg (-9*2)-5 = -22

[brave rock]

Well that's wrong. Reread what I wrote here.

[wooden remnant]

Right, the second part is wrong (with the -5) but am I right ont he first part?

"-22 mod 9 = 5, in that -9*2= 18, and then it's a difference of 5 to get to -22?"

or is that wrong too? (appreciate the patience, haha)

[brave rock]

Now it is true that -22 = -4 mod 9 but remember again that mod is a relationship between numbers, not an operation.

Typo.

[brave rock]

I have already described in precise terms here ^ what property the remainder satisfies. If you are looking for the remainder of -22 on division by 9 you know what to look for.

And it's certainly not -5.

[wooden remnant]

Aha! So it would be -9*3, and the remainder is +5

[brave rock]

In fact you made an arithmetic error previously: I will update my messages to reflect that

But yes the remainder is 5

[wooden remnant]

All good, I think I am at least on the right track. If I have to solve "why does -22 mod 9 = 5" on a test I think I will at least (somewhat) get it. I appreciate the help!

*Thank you!

[latent epoch]

Hello guys

I have a question if i have a partial order relation lets say if a divides b , a is in relation with b , and my set A is ( 2 , 3 , 4 , 7 ,8, 12 , 24, 35 ) , how can i determine the height and the width and why the concept of chains and antichains are related to this ?

i did something like this

(forgot to put an arrow from 12 to 24

[coral parcel]

Basically you'll have to draw a (Hasse) diagram for the relation and find the them visually.
"Height" and "width" are defined in terms of chains and antichains, of course, but those concepts have nothing in particular to do with the divides relation.
It's just a compact way for the exercise author to specify a finite partial order when he doesn't care about what exactly the elements of the finite set are. That way one doesn't need to list all the pairs in the relation explicitly, and every finite partial order is isomorphic to the restriction of "divides" to some set of naturals.

So the exercise is not really about divisibility just a "check you've understood the definitions of height and width, etc".

[latent epoch]

Thank you for your response, but i may not have explained myself well. In this particular exercice i was asked to determine the height and width of this Hasse diagram, and I would like to know how to do that. I understand that informally, it's possible to estimate these values by visual inspection for example, in this particular case the height i think is 3. However, I believe the formal way to justify these results is through partitions of chains and antichains, something like that and I am not confortable with those concepts, because i dont understand them well, so i was wondering if you could explain to me how to determine the height and width with the chains and antichains

I think i did that in class but at the time i didnt understand the resoltuion , maybe i am just saying a bunch of nonse things

[coral parcel]

I'm assuming that "height" is defined to mean the length of the longest chain and "width" is defined to be size of the largest antichain. (But I'll admit that is mostly guesswork from my side ... it sounds like definitions those words would be more or less natural for).

There's not really any formal systematic method you're supposed to discover, when it's just a "check you've understood the definitions" question.
As long as everything is finite, in principle you could write down all of the subsets one by one and ask "is this a chain? If so, is it larger than the longest chain I've seen so far? Is it an antichain? If so, is it larger than the largest antichain I've seen so far?" But it would be silly to actually do that, when it's easy to see it by eye instead.
(There are much faster algorithms one might program at least for longest chains -- not quite sure about widest antichains -- but having the best algorithm is not the point of an exercise like this).

[latent epoch]

Ok ty so much!!!

[pastel coral]

Let's say we have $(\mathbb{Z}_4,+)$ and $(\mathbb{Z}6,+)$. If we calculate the direct product of those, would it result in a group isomorphic with $(\mathbb{Z}{24},+)$?

The direct product would be a group of 24 elements right? So i'd say yes, but I don't know if this is right.
Could anyone elaborate?

[vital dew]

cedric_

[brave rock]

No, it wouldn't be Z/24, because 4 and 6 are not coprime.

See: chinese remainder theorem

[pastel coral]

Ah, so if the moduli were coprime then it would've been an isomorphism?

[brave rock]

Yes

[pastel coral]

Also, two groups are isomorphic if there's a bijection between the groups, right?
So why in this case it's not an isomophis?

[brave rock]

No, what you say is wrong.

Two groups are isomorphic if there is an isomorphism between the groups, not merely a bijection

If what you said were true then there would only be one group isomorphism class per cardinality.

[pastel coral]

alright, gotcha

[loud heron]

how do I do this Q

[coral parcel]

The multiple choice parts are just a matter of understanding the long prose description.
Actually solving the last one depends on which methods for linear programming you've learned. You can either just wing it by drawing the constraints into an x/y coordinate system and finding the corner with the largest profit visually, or you may be expected to follow some more systematic arrangement you've been taught.

[ancient ermine]

How do you do e?

[coral parcel]

Hmm, if I had (n choose r) x^r and wanted to get (n choose r) r^2, I'd try something like differentiating with respect to x, then multiplying by x, then those two operations once more, and finally setting x to 1.

[ancient ermine]

$n(1+x)^{n-1}=\sum_{r=0}^n\binom{n}{r}xr^{x-1}$

[vital dew]

CoshamGames

[ancient ermine]

This was my first line

[coral parcel]

Huh. I don't see how you get an x to end up in the exponent.

[ancient ermine]

I thought we changed the 2 to x

I honestly am struggling a lot with this topic since I've not been shown any worked examples in class

[coral parcel]

Perhaps try to start over. If you start with the binomial theorem $$ (1+x)^n = \sum_{r=0}^n \binom{n}{r} x^r $$ and then first differentiate each side with respect to $x$ and then multiply each side with $x$, what do you get?

[vital dew]

Troposphere

[ancient ermine]

Okay so I believe it'd be $n(1+x)^{n-1}=\sum_{r=0}^n\binom{n}{r}x^{r-1}$

[vital dew]

CoshamGames

[ancient ermine]

Then multiply by x

so

[coral parcel]

You differentiated wrong on the right-hand side.

(or at least forgot a factor).

[ancient ermine]

oops

hold on sorry let me go back

$n(1+x)^{n-1}=\sum_{r=0}^n\binom{n}{r}rx^{r-1}$

[vital dew]

CoshamGames

[ancient ermine]

Then multiply by x so

$xn(1+x)^{n-1}=\sum_{r=0}^n\binom{n}{r}rx^{r}$

[vital dew]

CoshamGames

[coral parcel]

Yes. So the net effect of this little dance was to give you a factor of r in each term on the RHS.

But you want to have r² there, so the natural next thing to do is ...?

[ancient ermine]

Diff again ?

[coral parcel]

Yes!

[ancient ermine]

$xn(1+x)^{n-2}(n-1)+n(1+x)^{n-1}=\sum_{r=0}^n\binom{n}{r}r^{2}x^{r-1}$

[vital dew]

CoshamGames

[ancient ermine]

I think?

[coral parcel]

Something thereabouts, but I haven't checked the LHS very closely. And now you'll have what you want on the RHS if you set x=1.

[ancient ermine]

$n(2)^{n-2}(n-1)+n(2)^{n-1}=\sum_{r=0}^n\binom{n}{r}r^{2}1^{r-1}$

[vital dew]

CoshamGames

[ancient ermine]

$n(2)^{n-2}(n-1)+n(2)^{n-1}=\sum_{r=0}^n\binom{n}{r}2r$

wait

ignore me

[coral parcel]

Wait what? r^2 is not the same as 2r.

[ancient ermine]

i just diffed for no reason ignore that XD

$n(2)^{n-2}(n-1)+n(2)^{n-1}=\sum_{r=0}^n\binom{n}{r}r^2$

[vital dew]

CoshamGames

[ancient ermine]

I believe that is now correct

[coral parcel]

Looks good. You can simplify the LHS a bit by pulling 2^(n-2) outside a parenthesis, but that's just polishing.

[ancient ermine]

How would that look?

[coral parcel]

Note that n·2^(n-1) is 2n·2^(n-2), so there's a common factor of n·2^(n-2).

[ancient ermine]

hmm

Would this be the final answer minus the simplifying in this case ?

[coral parcel]

Well, for that particular value of "final", I can't say no.

[ancient ermine]

XD Thank you 🙂

May I ask you a quick question with my workings of a previous Q same stature...

Qb on this

I was told earlier in a help channel it was correct but it feels too simple

[coral parcel]

Yeah, that's all there is to that.

[ancient ermine]

Oh cool 😄

[ancient ermine]

Thank you so much! You're a huge help 🙂 I doubt you remember it but you helped me last year with some questions I was really struggling on when I was revising for my end of year exams so that's the second time you've helped me through something I've needed help with ahaha

Well last year I mean like April/May time

[coral parcel]

Glad to be of help.

[ancient ermine]

Sorry to call back I’ve just realised under the summation r=1 not 0 does that effect the final answer ?

[coral parcel]

No, because r^2 is 0 for r=0, so it doesn't matter whether you include that term in the summation or not.

[twilit sundial]

my gut tells me i need to show this graph is tripartite but not too sure on the specific details?

i know that by pigeonhole any given student must know students from both other schools

or maybe it'll be like

"show it has too many edges to not have a cycle"? i'll try that first

[coral parcel]

Of course it is tripartite, but that's just by definition of the graph.

[twilit sundial]

ye

might need to show that it is 3-colorable but not 2-colorable?

[coral parcel]

A priori some of the students could know roughly equally many students from each of the neighboring schools. Others may have more lopsided sets of acquaintances.
Consider a student with a maximally lopsided distribution of acquantiances. Argue that such a student must be part of a triangle.

[twilit sundial]

yea that's the approach i'm taking rn

so the extreme case would be like

student from school #1 knows n students from school #2 and 1 student from school #3

the student from school #3 must know someone from school #2 by pigeonhole, and the result follows?

[coral parcel]

Yes, if we can find someone with an n/1 social split.

[twilit sundial]

ahhh and showing that it exists is just pigeonhole again?

is it?

hmm

[coral parcel]

Not exactly, I'd say, but I suppose it can be phrased that way.

[twilit sundial]

yea i realized it's not as simple as i initally thought

hmm

[coral parcel]

What I had in mind was:
Suppose the most lopsided student is Bob, at school B. He knows k students from school A and n+1-k from school C, where (without loss of generality) k <= n+1-k.
Because Bob is most lopsided, everybody in town knows at least k students from each of the two other schools (because otherwise they would be more lopsided than Bob).

[twilit sundial]

that might be where the tripartite stuff comes back in? show that if there wasn't such a split there would be too many edges coming out of one of the parts?

[coral parcel]

I don't think "tripartite" in and of itself is particularly helpful here (but it's possible that you can construct an argument where the word occurs ...)

[twilit sundial]

ye

[coral parcel]

Alice is one of the k students at A that Bob knows. How many C students does she know?

[twilit sundial]

hmm

at least k?

[coral parcel]

Yes.

So the total number of students at C who know either Alice or Bob is ...

[twilit sundial]

n+1-[students knowing both]?

[coral parcel]

Yeah. But there are only n students at C in total.

[twilit sundial]

so there must be at least one student knowing both?

[coral parcel]

Indeed.

[twilit sundial]

aight

how do we connect this back to the k=1 case?

[coral parcel]

We don't need to -- we've found a triangle already.

The other way to phrase essentially the same argument would be "infinite descent":
Start by picking a completely random student, Charles at C. He knows j students at A and n+1-j students at B. One of those A students is Adam. Either Charles and Adam have a common acquaintance at B (in which case we're done), or Adam knows fewer than j students at B. In the latter case we've found some one who has fewer acquaintances at the next school clockwise than Charles has, and we can then continue the same argument starting with Adam instead of Charles.
If we keep following the links C -> A -> B -> C -> A -> ..., we'll either find a triangle eventually, or find an unending sequence of students with ever fewer clockwise aquaintances. But the latter is obviously impossible, so there must be a triangle for the process to end with.

[twilit sundial]

hmm aight

still trying to get used to these proof methods lmao

[twilit sundial]

reading back, this doesn't require k=1?

[coral parcel]

I don't think it does.

Bob doesn't need to be the most lopsided person who could possibly exist, just the most lopsided person who is actually present.

[twilit sundial]

oh aight

[twilit sundial]

and the gist of this is that eventually we must find an overlap?

i think the overall proof makes sense to me now, thanks

[fast forge]

Can someone help me understand how to convert a logical formula in disjunctive normal form to conjunctive normal form?

I was told to use the distributiviity law $A\lor (B\land C) \equiv (A\lor B)\land (A\lor C)$

[vital dew]

Parallax Error

[fast forge]

While I undertand how to apply this when dealing with 2 terms connected with a conjunction, I'm unsure how to do it when dealing with three terms. Can someone help with this one DNF example by converting it to CNF?

$(\lnot a\land b\land\lnot c)\lor(a\land b\land c)$

[vital dew]

Parallax Error

[fast forge]

Nevermind figured it out by taking b common

[fringe turret]

I got this comment on stackexchange. Without explaining with example, this seems somewhat satisfying reasoning for the truth table 😅

imagine if we defined it that way. Then p → q is equivalent to p ∧ q, and so would be a redundant symbol

[snow sleet]

Lol. It make sense because if we say p->q is true only when both p and q are true. Then that is precisely what p^ q is. But this would mean p and q commute and so p-> q would be the same as q-> p. Obviously true that if ur in New York then ur in the US. However the commutativity would imply if ur in the US, then ur in New York…which isn’t true in all cases…u could live in Texas for example

[twilit current]

does this actually check out

like is factoring a out leave 1 in its position

and can u even factor out a in that expression

a + ab'

?

[cerulean radish]

Yeah, a = a * 1 and then you use distributivity

Alternatively you could of course say a + ab' = a(a + b') because a is also equal to a * a

But the former is clearly better

[twilit current]

how did he factor out a from a + ab' tho

if u factored out a would it be a( a + b')

wait

nvm

yeah that makes sense lol

[astral forge]

I tried alot but not able to read loops. somebody help like how to easily understand a given loop.

[terse quarry]

can someone explain why is the laste red note true ?

orange*

[scarlet hawk]

do you understand the difference between into and onto

[chrome sand]

guys

Why is the Image of A under f f(A) = [0,1]

given that A is [-1, 1]

[terse quarry]

i'm not native

whats written above in that paragraph i understood it

but the orange one no

[scarlet hawk]

In an Onto function, no elements in the range are left unmapped. Each element in the range is associated with at least one element in the domain. In an Into function, at least one element in the range is left unmapped.

[brave rock]

This conversation is happening in #proofs-and-logic btw, you might not want to miss that.

[earnest prairie]

what else should it be?
all numbers in [-1; 1] are mapped to some number in [0; 1] under f

[static bone]

Hello

What’s the difference between the Cartesian Product and power sets? I’m struggling to understand it

[coral parcel]

The elements of a cartesian product are ordered pairs.
The elements of a power set are subsets.

[nocturne grove]

A = {1,2}
B = {3,4}
A X B = {(1,3),(1,4),(2,3),(2,4)}
P(A) = {{}, {1},{2},{1,2}}

[static bone]

Thank you so much for the super simple explanation

[blazing dragon]

A boolean function of n arguments f(x_1,...,x_n) is given. Two players (A and B) are playing. The players take turns making moves. The auxiliary value m is used for the move, initially equal to 0, in addition, initially all values of variables are not defined. The move is as follows. The player either increases m by 2 or decreases it by 1. After this action, the value of m must satisfy the inequality 1≤m≤n. Then, if the value of x_m is not defined, then the player assigns a value to the variable x_m at his discretion. If the value of x_m is defined, then it changes to the opposite. The game ends when all the values are determined. If the value of the function f on the resulting set of variables is 1, then A wins, otherwise B wins. Analyze the game for n from the segment [2, 9] if f(x_1, ..., x_n) = x_1 xor x_2 xor ... xor x_n. I don't really understand what "analyze the game" means, what should i do?

[coral parcel]

Figure out which player has a winning strategy and what it is.

[blazing dragon]

A winning strategy is a strategy that allows a player to win regardless of the actions of the second? Or did you mean something else

[coral parcel]

Yes, that's what a winning strategy is.

For this game it also seems possible that the game never ends, which presumably counts as a draw.

[blazing dragon]

Why? Can you please explain this?

[coral parcel]

The players could make choices such that m takes the values 2, 1, 3, 2, 1, 3, 2, 1 ... and x_4 never gets defined, so the stopping condition is neve reached.

[blazing dragon]

So, for n >= 4 there is no winning strategy for both of them?

[coral parcel]

I'm not saying that -- just that they can collaborate on making the game last forever.

[plucky wedge]

if anyone wants to take the time to help me understanding what this question is trying to say and give me some hints would be appreciated

I was confused on where that n^2+1+2 is coming from in the middle of the inequality

[plucky wedge]

I think I see now

[tawny iris]

a

[viral pine]

Given an undirected graph with unique edge weights

1. the MST is unique, and
2. the MST must contain the cheapest edge

Both are true?

[haughty garden]

Yes

1. certainly is true and you can prove this by contradiction

2. is true by virtue of 1) and applying any MST algorithm

You can also prove it directly

[vernal vigil]

Whats the answer?

[little prism]

how many edges would that graph have?

[twilit dragon]

I wanted to ask that in proving the conditional statement that "if G prime is k+1 colourable then G is a k-colourable graph for all values of k"
Can we take a step that "Let G be a G prime without a vertex"
Since the graph is no isolated, removing a vertex removes at least one edge, removing one colourable vertex
Therefore making it k-colourable
is this a valid proof?
Kindly ping when you have gone through my proof

[vernal vigil]

Idfk dude

Wtf is k-colourable

[hallow perch]

I think we can answer with the property that if graph G is a tree, then V = E + 1, here 6 = E +1 so we expect 5 edges otherwise if we have more we'll have a cycle and if we have less it won't be connected. we also know that the sum of the degrees of each vertex is 2E because each edge is counted twice, which in this case means 1 + 2 + 2 + 3 + 4 + 4 = 2E which means 16 = 2E which means E = 8. that's too many edges so it can't be a tree.

[static bone]

Hi. When doing relations with sets, can the letter in between be any letter?

[brave rock]

Yes

[static bone]

Ok thank you.

[plain pulsar]

Suppose that n is an even integer greater than 0. How many bitstrings of length n have more 1’s than 0’s? Your answer need not be in closed form.
i got 2^(n-1) - binom{n}{n/2}?
right?

[loud heron]

i kind of forgot how to do this

[twilit dragon]

Its not a tree

[twilit dragon]

graph colouring

[weary blade]

what am i doing wrong to not get an answer of 2?

[weary tiger]

what happens to the 2nd negative x!yz

[weary blade]

they get combined

remember the + is an OR

A or A = A
A + A = A

[weary tiger]

thank u ^^

[weary blade]

wait i just realized 2^4 = 16 and 16 mod 7 = 2

is that right?

[opaque escarp]

how would i do this

what is the process?

[errant bear]

by plugging in q=1/3 lol

[opaque escarp]

so f(x) = 1/3

im a little sped not gonna lie

oooooooooooo

i think i got it

This was the work I did, clearly wrong, the answer was -1/9, what did I do wrong?

nvm i think i get it

Once I get to here, what do I do

[obtuse lance]

that is what they proved

[craggy fern]

can someone explain to me why i got this wrong im confused

[obtuse lance]

looks like you got it wrong because you didn't answer it

[craggy fern]

its hard to tell but i chose the second option

[obtuse lance]

yeah it's vaguely lighter color haha

[craggy fern]

my custom canvas fricked it up but yeah

[obtuse lance]

looks right to me

[craggy fern]

i think whats throwing me off is that the function is mapping integers to integers, i emailed my professor about it and apparently its incorrect

[obtuse lance]

probably they meant to change it to be R->R instead of Z->Z

[obtuse lance]

I say that cause why ceiling the answer of an integer?

[craggy fern]

yeah it makes no sense to me because the ceiling on an integer is just the integer

of*

[obtuse lance]

yep

[craggy fern]

my professor responded to my email saying this "Mathew think about the fact that function is mapping from integer set to integer set.." im not sure how thats supposed to help me

[obtuse lance]

your prof is confused

(x^3-y^3)/(x-y) = x^2+xy+y^2 = 0 has no solutions because z^2+z+1 is irreducible over R

so it's injective

it's clearly not surjective because there are integers that aren't perfect cubes

[astral forge]

Anybody?

[coral parcel]

It's also injective because it's strictly increasing.

[coral parcel]

All you need to record is (a) who won at the end, (b) which three of the five games did they win.

[astral forge]

Okays. Let me try

[loud heron]

do I just add the workers for each box and then multiply it by 500?

[golden urchin]

How do you do this?

[bright drift]

is anyone here good with modular multiplicative inverse? i get most of it but i'm not getting one specific part

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[vocal ruin]

just to confirm

B doesn't contain a hamiltonian circuit right?

cause of the vertex N with only one degree

[runic plover]

theres 15 spanning trees that can be made from a cycle with 15 nodes, but only 1 thats isomorphic to all the others, right?

[plucky wedge]

Having trouble showing P(1) is true

I get 10 on the right

oh for the left is it 1^2 + (2(1) + 1)^2?

oh 1^2 is from 0

I thought it was just from 1, I get it now

[coral parcel]

Each of the 15 spanning trees is isomorphic to the others.

What you can say is that there's only one isomorphism class of spanning trees.

[runic plover]

aight thanks

[runic plover]

could i also say the set of non isomorphic spanningn trees has cardinality of 1

[modest swan]

could someone give me an idea on how to start approaching this

[frozen mason]

Im not sure if you're aware of this theorem that states that if and a & b are both not zero and if d = (a,b), then d is the least element in the set of all positive integers of the form ax+by.

So we can prove your proposiiton via contradiction and using the above fact

[cerulean radish]

Alternatively you could write down the definition of gcd and look for what about it is implied from ua + vb = 1

[frozen mason]

Im trying to find a formula for this sequence defined recursively as such $R_n = R_{n - 1} + n$ with $n \geq 1$ hence $R_n - R_{n-1} = n$ I want to know if I can set substitute $n$ for $n+1$ an hence get $R_{n+1}- R_n = n+1$ instead, is this valid, moreover is this the excpeted thing to do?

[vital dew]

jayz

[cerulean radish]

Isn't it clearly the sum of first n integers though or something like that

[frozen mason]

$R_0 = 1$ BTW

[vital dew]

jayz

[weary tiger]

Yes you are allowed to do that.
The sequence you are referring to is the sequence of triangular numbers

[frozen mason]

Ok gotcha thanks

[weary tiger]

Then this gives a sequence of triangular numbers shifted by 1

The sequence of triangular numbers starts with 0 if we define R_0 = 0

[frozen mason]

Oh ok, Im trying to find the closed form of the sequence by finding its generating function e.t.c will I run in into any problems if i attempt to do this, when I shifted the sequence by 1??

[blazing axle]

looks like you can say (2k + 1)^2 is just 4k^2 + 4k + 1 and you can find the sum for each term, if you know the formula for sum of squares and sum of n natural numbers

then you can also expand the other side if you want, and compare the coefficients after getting the denominator on borh sides to be the same

[weary tiger]

Well the generating function will not be the same like you have for triangular numbers if you go by R_0 = 1. If f(x) is a generating function of some sequence A and g(x) is a generating function of sequence B, then f(x) + g(x) is the generating function for the sequence A+B. This will apply here

[frozen mason]

I have a power series of the form 1 + x + 2x^2+3x^3+........ I want to write as a quotient instead how would i do that

[weary tiger]

Well what is the resulting series when you differentiate the geometric series 1 + x + x² + ...?

[frozen mason]

1/(1-x)^2 right?

[weary tiger]

Sorry I made a mistake

Also write it in terms of series

[frozen mason]

but I do know that these specific series is 1/(1-x)^2

[weary tiger]

Take derivative of each term wrt x

[frozen mason]

oh then we would have 1 + 2x + 3x^2 +....

[weary tiger]

Yes

Now multiply this series with x

[frozen mason]

x + 2x^2 + 3x^3 +...

[weary tiger]

Add 1

So your generating function for this sequence will be $1 + x\frac{d}{dx}\left(\frac{1}{1-x}\right)$

[vital dew]

𝓘 .

[frozen mason]

wait isnt 1 + x + x^2 +..... = 1/(1-x)^2?

[weary tiger]

1/(1-x)

[frozen mason]

right thanks

[vernal vigil]

Anyone know how to incorporate graph theory into OOP?

[uncut bear]

Object orientated programming?

[lone python]

Gm guys i need a lil help in this question .. prove that
If x is smaller then y then √x is smaller then √y

[errant bear]

assume otherwise

[errant bear]

least open ended question

what do you mean by "graph theory"

[coral parcel]

"The set of non isomorphic spanning trees" does not make sense. Being isomorphic or not is not something a graph is in itself; it's a relation two graphs may have to each other.

[runic plover]

shucks, alright

[grave sail]

3. Let f be a function from X to Y . For A ⊆ X, let also f(A) denote the
   set f(A) = {f(a) | a ∈ A}. Prove that f is one-to-one if and only if
   f(A ∩ B) = f(A) ∩ f(B)
   for any subsets A, B ⊆ X. -----------I'm a bit confused on how to approach this, i'd appreciate a small hint to help get me started please 🙂

[keen cave]

guys

\

is this basically saying that since n^2 is proven to be less than 2^n

we would need to know if 2n+1 is less than 2^n since n^2 is being added with 2n+1 and if both are less, then that means the addition of 2^n + 2^n would be greater?

[silk void]

no no i got it now...

[urban berry]

im not sure i understand what you mean?

[keen cave]

well the base case is n^2 < 2^n and it's proven that for 5 2^n is less

but if we do (n+1)^2 that would simplify to n^2 + 2n+1

and we already know n^2 is less than 2^n through the base case

[urban berry]

yup

[keen cave]

for n >= 5

but since we are also adding one to 2^n+1

it becomes 2^n * 2^n does that mean we have to compare one of the 2^n's with n^2 (which we already did) and the other with 2^n again to make sure that they add up to less than 2^n+1?

sorry it's kinda hard for me to grasp so this is the best I could say

[urban berry]

how about

i say what i see

and you tell me where it gets confusing?

[keen cave]

alright thank you

[urban berry]

sorry reading it all like this is a bit much lul

[keen cave]

lol all good

[urban berry]

ok so our predicate\claim is that n^2 < 2^n for all n >= 5

base case is the smallest n so when n = 5

[keen cave]

yes

[urban berry]

small computation so it holds

now our IH is basically the predicate written again

usually its written with a dummy variable k but i guess they used n again here

[keen cave]

IH means inductive hypothesis?

[urban berry]

yup

[keen cave]

oh okay

[urban berry]

so we have that

[keen cave]

ah they do that so students don't make mistakes

or get confused

[urban berry]

n^2 < 2^n for some n >= 5

we have that for n

for induction we want to show that n+1 follows

like dominoes

so

they simply replace n with n + 1

[keen cave]

also quick question, how can we know n+2 would hold, or n+ 3 etc

just from n+1

I always wondered this

[urban berry]

great question

from n we go to n + 1

to get n+2 we need to get to n+1 then n+2

in more advance proofs youll learn about recursion, structural induiction, even strong induction

but thats not important for now (if u want to see how it works think of fib sequence)

ok so

(n+1)^2 = n^2 + 2n + 1

[keen cave]

oh okay so you're basically saying that, I can just think if n+1 satisfies condition, it works for all n +...?

in simple terms I guess

sorry haha

[urban berry]

yes

[keen cave]

okay thanks

[urban berry]

cause if u manually were to compute it you could go for all natural nums

ok so

[keen cave]

oh okay

[urban berry]

here let me write this out to make it a bit neater

one momment

[keen cave]

cause n could be n+1, then we can prove n+1 with n+1 +1, and n+ 2 with n+ 2 + 1 etc since it would hold until infinity

maybe i'm overcomplicating it though

[urban berry]

,rotate

[urban berry]

notice the inequalties on the left

i basically added them

and notice what happens when we simplify

we get exactly the case of n+1

i took our induction hypothesis

and if it holds that 2n+1 < 2n well then i can combine my IH to get (n^2) + 2n + 1 < (2^n) + 2^n

and next we can see that the person does exactly that, they prove that 2n+1 < 2^n

they really coulda formatted their proof better

so they use induction again to prove 2n+ 1 < 2^n

[keen cave]

I know this goes without saying but, if they prove 2n+1 < 2^n AND n^2 < 2^n for each base case of n = 5, would that mean 2n+1 + n^2 < 2^n + 2^n?

[urban berry]

for that specific case then yes

but not for all naturals

[keen cave]

but wouldn't it be for all naturals if they just proved n+1 case

since you can get to any natural just by adding 1

[urban berry]

do u meant less than in the last line? u said =

[keen cave]

sorry i meant less than yes

[urban berry]

but if its so straight forward the surely you can prove it?

https://tenor.com/view/peace-gif-21666350

the beauty of discrete math my friend :))

[keen cave]

oof

[urban berry]

cause heres the thing with induction

lets say we had a room full of people

and i said to you

[keen cave]

okay

[urban berry]

wukong, prove to me that each person has brown hair

then u grab the first person and say this person has brown hair

i agree

then we remove that person from the room

ok great thats a base case

but what if the room was infitely large?

how can i know that u are right?

and you have better things to do in your life then to show me each person has brown hair

[keen cave]

then we take another person and say he has brown hair, but then everyone else could have black hair

[urban berry]

exactly

so showing the base case although trivial

[keen cave]

yeah

[urban berry]

is not enough to say for all natural numbers

[keen cave]

even if it's the base case + 1

[urban berry]

yes exactly, we would be there for ever doing the + 1 case

[keen cave]

cause I was taught

if we prove n + 1 would prove everything

[urban berry]

yeah the case of n+1

that would prove it

but in this case if ur saying 5 is true

so suerly 6 is true

that dosent work

[keen cave]

ohh I see

[urban berry]

but if u show me n is true

and n+1 follows

[keen cave]

this only works for 5

[urban berry]

then that works

yes

[keen cave]

ohh okay

all numbers with 5

n = 5 sorry

[urban berry]

sorry i think i misunderstood this as "i proved the base case so it must hold for everything after"

[keen cave]

oh all good

I am just confused on this

n >= 5

shouldn't they say for all n = 5

[urban berry]

show me the whole line real quick

[keen cave]

alright

[urban berry]

no, in this its defining n

in his base case he does n = 5

[keen cave]

I think it's because the theorem says for all n >= 5

[urban berry]

after that its, suppose n >= 5

[keen cave]

at the top

[urban berry]

for induction its usually for all n >= <SOME NATURAL>

[keen cave]

I think cause that is the smallest, but over here out n is also part of the incrementation

[urban berry]

and yes in the theorem u aim to prove for naturals >= 5

[keen cave]

so we are adding + 1 not only to n^2 and 2^n

but also to the value as well

so it holds for all

since we are proving n^2 and 2^n WITH adding n

for 1 case

[urban berry]

no no not + 1 to n^2

[keen cave]

I guess we would be testing 6

[urban berry]

rather (n+1)^2

[keen cave]

ah that's what I meant

like (n+1)^2

[urban berry]

the whole idea with induction is

predocate (theorem in ur case)

base case for the smallest value possible (5 in ur case)

induction hypothesis (assuming for all n>= <UR DOMAIN> in ur case its >= 5)

then induction step i.e case of (n+1)

usually everything before induction step is straight forward

induction step is where you need to get clever

and show that the case of n+1 holds

how do u know what the case of n+1 is?

wherever u see n

plug in n+1

and that should give u a idea of where to END

[keen cave]

these are my notes though:
for induction we make n the lowest number it applies to
we try to do n+1 to prove the next statements are true (for all n values)
We try to make it into a base case form or a form that alligns with the base case (like if we are trying to prove if something is a multiple of 21 we would want to make something like 21 * (equation)

So in this case we are not only proving when n = 5, but also 6, 7, etc

[urban berry]

yes

[keen cave]

ahh okay

[urban berry]

let me find u something

[keen cave]

but what did you mean by we can't do n+ 1

we can't prove everything with n + 1

[urban berry]

i think i thought u ment by just adding one to n and showing that hold

like 5 holds now add one do computation now 6 holds

and keep doing that

[keen cave]

ohhh you meant like physically

doing it one by one

proving each one

[urban berry]

thats my misunderstanding my bad

yes

[keen cave]

ohh no worries haha

[urban berry]

thats what i ment by the hair example

[keen cave]

I applied the hair example to proving n+ 1 and somehow that worked as well lol

but I guess that's wrong way of thinking on my part

[urban berry]

here is something my prof wrote for us when we did induction

here is a better example to see how it works

[keen cave]

ohh Isee

[urban berry]

rmbr proofs are a piece of writing, make them neat and nice to read

[urban berry]

no offence to this person

but if it was a book

i would not read their book

[urban berry]

this book is much nicer

[keen cave]

no offense at all this class is structured horribly

the rating for this class is 40% out of 100%

[urban berry]

it carries the reader very nicely the entire time, no ambiguity

[keen cave]

and grade averages are low too

basically a weed out at my uni

[urban berry]

yeah i had to do discrete math twice too

big learning curve

[keen cave]

fr

[urban berry]

yup same

but i enjoy it now

way more than calc

[keen cave]

I will make sure to read it but after this one quicker question

[urban berry]

which is what i always post in the help channels

[keen cave]

for this one n isn't changing the actual value here

just the equation itself

cause 21 always stays 21

doesn't increase

but in the other one, n = 5, was increasing with the functiion itself?

[keen cave]

also I never thought i'd hear these words 😱

I felt like calc was soo simple compared to this

[urban berry]

i think uve helped me with calc in the help channels lmao

[keen cave]

loool maybe

[urban berry]

nah idk calc seems like memorization to me

[keen cave]

I love that, all the rules etc

[urban berry]

proofs is more logical more interesting

[keen cave]

ah I see

maybe it's just new to me

[urban berry]

yes cause u want to show that

4^n+1 + 5^2n-1

is always divisible by 21

so 21 remains

[keen cave]

true

[urban berry]

cause we dont need to show 2*21 divides something

thats the same as 21 divides something

what we want to show is that ur 4^n mess is always divisible by 21 no matter how big n gets

[keen cave]

ahh I see

true

and we prove that "no matter how big n gets" with n + 1

right

[urban berry]

yes

[keen cave]

cause just that would suffice

[urban berry]

u want to show n holds

[keen cave]

gotchaa this is making sense now

[urban berry]

so does n + 1

[urban berry]

im glad to hear

[keen cave]

quick question though sorry for all the questions 😅 you are very kind

[urban berry]

these two images tho

reviiew these before you go forward

this prof was amazing and id die by his notes 😂

[urban berry]

yeah go ahead

[keen cave]

In the other problem n is not increasing with the function right, it could be n^2 <= 2^n with n = 6 or actually when we add n+1 does n^2 increase with n = 5? I think I am confusing myself now actually....

[urban berry]

lets be careful here

[keen cave]

sorry i edited it to make more sense

[urban berry]

in proofs the most important things is definitions

we want to take a question and unfold it into its most basic english

[keen cave]

I guess my question is is n^2 the same as the n in n = 5

[urban berry]

u said function, we never worked with functions yet

only inequalties

[keen cave]

oh true

I forgot about that

[urban berry]

yes

youll notice in the notes i sent u

my prof usses k

usually in the inductive step people use a dummy var k

and say since k imples k + 1

[keen cave]

oh so as n increases so does n^2 n = 6 would become (n+1)^2

[urban berry]

then n imples n + 1

[keen cave]

I will make sure to read them

[urban berry]

yeah i think so if i understood this right

[keen cave]

n = 7 would be (n+2)^2?

[urban berry]

good luck, it takes a bit to wrap your head around but just go slowly and youll get it

[keen cave]

just to make sure

[urban berry]

yes, but you dont need to show that

all you need to show is n+1

[keen cave]

my question is

how come my prof didn't use n = 6 in the definition for n+1

when proving n+1

[urban berry]

because then how do i know ur n holds for n = 6 ?

u showed me n = 5

now ur saying assuming it holds for n = 6

[keen cave]

but I thought n was increasing with n+1

[urban berry]

it is but we start at something we know

then jump to the next case

we know 5

we jump to n+1

[keen cave]

ohh we are proving using the base case of 5

so we don't need 6

[urban berry]

exactly

[keen cave]

I seee

[urban berry]

think of it as a number line

i can cross off 5

u showed me 5 in ur base case

now in ur induction step

u say imagine n is equal to 5

or its greater then 5

insert logical steps

so n+1 holds

and like that you covered all natural numbers

and now i belive u

[keen cave]

true because we have to break down the n+1 into fragments of the base case, using the base number n = 5

and prove using those

we can't just say n+1 for n= 6 cause that would be back at square 1 we need to prove n+2 now but it wouldn't even work cause we have to use the smallest number anyways

[urban berry]

read this

[keen cave]

true so the base case is like the foundation

is what I got from that

the foundation of the ladder

ladder is the induction

[urban berry]

yes

base case is the most simple

basic math

you show that its true and you can go to the next step

both have to exist

you cant have on with out the other

most importantly this

show that k >= n_0

so in ur case n_0 = 5

so show that 5 -> 6 -> 7 -> 8 ....

[keen cave]

true

[urban berry]

other wise we woulda had 5, 6-> 7 -> 8 ...

which dosent work since i dont know if 5 implies 6

in regards to you asing why we had n >= 5 and not n = 6 ^^

[keen cave]

ah okay

all the notation, I've studied, for all, and there exists, element of, etc but still not too comfortable with it haha

[urban berry]

for all is upside dow a

there exists backwards E

takes a while but itll become basic english

i actually strictly write in that notation now

[keen cave]

Yeah still confused on certain cases though, because if you want to say "every german owns a car" forall x( if they are german (G(X) -> C(X))

then they own a car )

but you can't use AND

isntead of ->

because that would indicate that every german owns a car

or wait lol

this would be AND

[urban berry]

ah logic

think of python logic if u program

[keen cave]

yeah that part of discrete math sucked

I am glad I got out alivel ol

[urban berry]

man i miss discrete math

[keen cave]

woudl this be G(X) ^ C(X)?

I thought it would be

[urban berry]

much rather do it over calc 2

[keen cave]

really!?!?

I love calc 2 lol

a little less calc 3

[urban berry]

honestly its to late for me to understand

what that unit called

[keen cave]

ahh all good

[urban berry]

maybe i can dig thru my profs notes

[keen cave]

the ^ is AND operator

[urban berry]

oh

[keen cave]

but it's all good I know it's late

[urban berry]

and needs everything to b true

[keen cave]

yeah

so that would mean every human owns a car

which is false

if the domain of discourse is all humans

so we need G(X) -> C(X)

[urban berry]

uhh

thats implication

best way to think of it is

if you pass your discrete math class ill give u 15 bucks

u fail -> i dont give u 15 bucks (f -> f = true)
u fail -> i give u 15 bucks (f->t = true)
u pass -> i give u 15 bucks (t->t = true)
u pass -> i dont give u 15 bucks (t->f = false)

[keen cave]

but I think

for these problems we have to assume

the conclusion is true

and

idk it's weird I learned it a month ago

but I know for regular predicate implication T-> T = T F with anything is true

T -> F = false

but for these problems

it's like

we assume conclusion is true somehow?

nvm that's for comparing implications of universal statements

two universal

[urban berry]

yeah logic is funny

[keen cave]

but anyways bro thank u for the guidance with proofs 🙏

[urban berry]

theres book of proofs by richard hammock

free on his site

its good

[keen cave]

bro I know this is sad

but I never wanna see a proof again

or this class lol

[urban berry]

haha lol, r u cs?

[keen cave]

SE but we have same math requirements

and I have mandentory physics

[urban berry]

yeah tough luck budy it dosent go away XD

[keen cave]

in software engineering?

I have linear algebra next 😭

[urban berry]

i got to uoft and to get into cs we need to get atleast a 73 in discrete math

[urban berry]

yeah i have that next sem to

[keen cave]

oof we will suffer together haha