discrete-math

[glossy dirge]

Thank you for the answer but english isnt my native language, and math "talk" is confusing to me, so ididnt understand that

[halcyon basin]

What's your native language? If I know it I might try to explain it differently

[glossy dirge]

serbian

Could you add few steps in your explanation? Or tell me what should i google?

[halcyon basin]

Oh then I can't sorry

[halcyon basin]

The only thing you use here is that two polynomials are equal if and only if their coefficients are equal

[glossy dirge]

I think i get it now, thanks

[halcyon basin]

You're welcome

[halcyon sand]

Could someone help me in determining Big-O notation?

[halcyon basin]

Yup

[halcyon sand]

for ex; f(x) = x^x, g(x) =x!

would this be f(x) = O(g(x))

[halcyon basin]

Well here $g(x)\underset{x \to +\infty}{=}o(f(x))$ because $\frac{g(x)}{f(x)} \underset{x \to +\infty}{\longrightarrow}0$

[vital dew]

black_couscous

[halcyon sand]

Is it when the limit approaches zero g(x) = O(f(x)

[halcyon basin]

No when it goes to 0 then it's a little o

The big O is when the quotient is bounded

Like 2x and x

The quotient is 2

Or like x^2 and 2x^2+x+1

[halcyon sand]

Ah I see.

I appreciate that man!

[halcyon basin]

My pleasure

[glossy dirge]

How do i get those 2 equations from the first one?

[halcyon basin]

Because it's a polynomial on the variable n

[glossy dirge]

I appreciate the help, but i seem to have forgotten about that. What should i google to figure this out?

[halcyon basin]

That

[glossy dirge]

Ok, thanks. I really appreciate your help

[halcyon basin]

If you want to train on that and to show an interesting result look at Pascal's inversion formula

One of the proofs uses that

[glossy dirge]

I will look up that, thanks

[halcyon basin]

You're welcome

[covert bolt]

Why is this relation set transitive?

$R={(1,2),(3,4)}$

[vital dew]

Opify

[stray reef]

does there exist a triple (a, b, c) such that (a,b) ∈ R, (b,c) ∈ R but (a,c) ∉ R?

no

therefore R is transitive

[covert bolt]

ooo

why is R also transitive?

[stray reef]

it's not just transitive, it's even an equivalence relation

[covert bolt]

yea ik it's symmetric and reflexive

but I still dont really get how its transitive tbh

[pale epoch]

its finite so you can just check every combination

[weary tiger]

finite enough you can check every combination

[covert bolt]

just to check when checking for transitivity can I ignore (3,3)?

[pale epoch]

i want to say no but it doesnt affect the transitivity of the relation

[chrome horizon]

Hello 👋 there,
I study in class 10th I want to say that how can I improve my math. My math performance is very poor.

  Ignore my English. I am not very well in english

[covert bolt]

ahh ic

[modern nova]

dance with the numbers

solved

[spark silo]

so this graph has a bridge. but can it be said that vertices 1 & 2 (the two vertices connected to the bridge) are also cut vertices?

[dawn sandal]

Lets say I have:
U = {x ∈ Z | 0<x<100}
A = {x | 2x ∈ U ^ x/2 ∈ Z}
B = {7x | x ∈ U ^ x<7}
What would be the roster notation of A and B given these set notations where Z represents an integer?
What I have tried so far:

• U is all numbers from 1-99
• A is all even numbers from 2-48
• B is multiples of 7 from 7-42

I am confused on whether or not I did A and B correctly given that one is divisor and one is multiple

[eternal thicket]

how to proof that factorial bigger than bell number for n>2?

[astral fractal]

I have to simplify this expression but again and again I arrive at this: [(q bar) or (1 or (p and q))]

Can someone please guide

[bleak agate]

Start to simplify from inside (I would start with the equivalence first)

[astral fractal]

Yeah I did that only

[bleak agate]

Describe q => p, p => q with or/and first

[elder berry]

Algebraically it might be useful to try strong induction on the recursive definition of the Bell numbers

$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$

[vital dew]

peaceGiant

[elder berry]

and then using B_k <= k!

I think it should work

[proper forge]

I think I know the answer to this problem, but I don't know how to properly explain it.

[zealous kraken]

hey guys, how do i find the expected number of recursive calls made by randomized quicksort?

[covert bolt]

is $(\neg A) nand (\neg B) \equiv \neg(\neg(A nand B) nand (A nand B))$?

[vital dew]

Opify

[covert bolt]

nand truth table

[coral parcel]

That doesn't feel true. On the left you just have "A or B" (by De Morgan's laws).

But on the right you have something involving "¬P nand P" (for P = A nand B) which is either "true nand false" or "false nand true", no matter what A and B are.

[covert bolt]

o ya

I see the issue now when I drew a venn diagram

[lusty fern]

So in proof by inductions, we assume k is true and we prove k+1. Is it possible to assume k is true and prove k-1 if the sequence is going in a negative direction?

Or is that no longer by definition a proof by induction?

Like idk if thats a thing or not, to prove k-1 step

[coral parcel]

You'd need a base case, and in the end you can then only conclude that the property is true for k less than or equal to that base case.

That is:

m is a fixed integer
Base case: Prove p(m)
Induction step: Given p(k) prove p(k-1)
Conclusion: p(k) holds for all k <= m

What this really boils down to is just the same as ordinary mathematical induction on m-k.

[ornate creek]

I am working on the mathematics for computer science course (MIT 6.042J) for my own enjoyment and I am struggling with the current problem.
I have worked on it for a while, I looked up a solution cause I've been at it for hours with no success and found the following.
From my understanding, I think it is basically saying if a,b,c,d is the smallest solution then a/2, b/2, c/2, d/2 is also a solution. Which contradicts the minimality of a,b,c,d. Am I interpreting that correctly?

[stray reef]

yes

[lusty fern]

Yeah this looks like the proof that was presented to me

[urban mantle]

What tree degree is sufficient to connect any vertex set in any n-dimensional space? What I mean: what is minimum possible degree of resulting spanning tree on any vertex set in any n-dimensional space? Is it 3? How to prove that it is 3?

Here is an example of spanning tree degree-3 connecting dots in 2d plane

And it seems to work on any set of vertices on 2d plane, but I cannot prove it working on any n-dimensional plane

[stray reef]

you can make a spanning tree of degree 2 can't you?

[urban mantle]

no

[stray reef]

just put them all in a polygonal chain

unless there's some criterion you are leaving unstated

[urban mantle]

Here is degree 2

It can theoretically do this, by finding hamiltonian path, but it is not general for spanning tree algorithm to do this

but with degree > 2 it seems to work fine

[stray reef]

it's a little unclear what your setup is

[urban mantle]

What tree degree is sufficient to connect any vertex set in any n-dimensional space?

[stray reef]

taking your statement at face value you just have a set of points

[urban mantle]

Yes. I have a set of points

[stray reef]

any two of which could potentially be joined by an edge

[urban mantle]

On n-dimensional space

I need to connect them by edges in such a way, that no one of them have degree > than some constant

[stray reef]

so what is stopping us from making a single polygonal path through all of our vertices???

you are unconcerned with edge length or anything

[steep plume]

I struggle greatly to understand the way this task is worded

[weary tiger]

A_1={1}, A_2={1, 2}, A_3={1, 2, 3}, ...
Is it what you needed?

[feral salmon]

Heyyy guys

Will the interval [1/(2n),1/n] be empty when n tends to infinity?

[little prism]

well for that you should first define what exactly you mean with a limit of sets

there arent really obvious ways to do that

[carmine veldt]

hey, can someone help me with c) please?

[livid drum]

ake any guy in NxN, and assign him to his equivalence class.... this is f.

now g is a map from NxN to Z.

How might you define a map h from the equivalence classes to Z, using g?

a natural way is to take an equivalence class, look at a representative of it, and apply g to the representative.

you'll have to check that the def is well defined (doesn't depend on the representative chosen).

see that this map satisfies all the things it claims to.

[carmine veldt]

thanks

I don't know how to define h though...

would you have an example?

[livid drum]

that's mentioned in the post 😂
think about it mate, give yourself a fair chance and you'll get through.
If it's overwhelmingly confusing, then start by strengthening your understanding incrementally.

[carmine veldt]

I'll think more about it haha, thanks
to be honest I'm not a math student, this question was for a friend who studies math but yeah can be a nice training for me as well ^^

and now I got what you meant in your post, thanks ^^

[ornate creek]

I thought that the steps I selected in the second picture should be included in the steps containing logical error because how can m be equal to 0? If we stated in the same line that F(0) = 0 is even. Also, how can we say m >= 2 if we haven't shown that F(1) is even?

[weary tiger]

I’m not understanding that step

[brave rock]

a + b + c = (a + b) + c.

that's all.

[zealous elbow]

how do i tell if a graph is simple or not without drawing it

[livid drum]

Hey Guppy, The step "then m>=0 because F(0) is even" is justified right? I mean, yes m>0, but fine whatever we can say something weaker like m>=0.

The step "Suppose m>=2 ..." is also alright.
We can suppose whatever we want! (Whether it's useful or not, ah well it's not our problem.)

Now if m>=2, we get a contradiction. Thus m<2.

But we haven't considered that case!
If we could get a contradiction with m=1, then we'd have a contradiction in all cases.

So the final step is wrong, because there is no contradiction staring at us in the face. Just the fact m<2 which leads us to the unexplored case of m=1.

[wooden moat]

I am very sure that this si not possible but I am unsure of what the reasonign would be

[coral parcel]

I can think of one.

(That is, I can think of a graph as specified, not I can think of a reason it's impossible).

[wooden moat]

what would that graph be?

[coral parcel]

Can you make a four-vertex graph with degrees 1,1,1,3?

Then find a way to add a vertex of degree 2 with minimal change to what you already have?

[ornate creek]

I see now that we can essentially write whatever we want.
How is there a contradiction if Even(m) is false when m = 2?
Are you talking about there being a contradiction that F(m - 1) and F(m - 2) being even?
Reading through it again, I think I am understanding what you were saying.
Could the proof had essentially ended at "Now, suppose m >= 2 so the definition (*) of F(m) applies."?

[livid drum]

If the proof ended there it would be incomplete.
So the flow of the proof is like this:

1. He defines the set C like he does.
2. He assume the set is nonempty, and works towards a contradiction. If he ever finds a contra, then indeed the set is empty, and he's done.
   The future steps work in the context of the assumption C is non empty.
3. C has a minimum, call it m.
4. Either m=0, m=1, or m>=2.
5. he shows m cannot be 0.
6. He then takes the case m>=2.
7. In the context of this fantasy he arrives at a contra (making some arguments about F(m-1) and F(m-2)).
   Now the correct step 8 would read "8. Therefore m=1. "

However he has written "therefore contradiction, there is no possible m", and he supposedly gets the contradiction he wanted from step 2.

This is wrong though as he forgot about the missing case m=1.

Does this make sense?
(Ive changed his proof a lot so it makes more sense for this problem).

[zealous elbow]

Prove that there is no 3-regular graph with 7 vertices.

how do i go about proving this

[stray reef]

handshake lemma

[zealous elbow]

do i need to show handshake lemma in the proof or can i just say since the degree sum is odd its impossible since i only need to prove it for that case

[stray reef]

depends on how anal your professor is

[zealous elbow]

hmm

so i could just write the handshake lemma in there and show that it doesnt work with it just in case?

[stray reef]

"By the handshake lemma, the sum of all vertices' degrees in a graph equals twice its edge count, therefore the sum of all degrees is always even, which in a 3-regular graph on 7 vertices it is not."

[ornate creek]

Yea I think I am having trouble wrapping my mind around finding the error in the “context of the fantasy”. My mind wants to just jump to “hey F(2) is odd! Let’s call it a day, not all elements are even”

But I see it now, the fact that there is no contradiction, just an unexplored m=1

[spring elk]

part b

how is the first one onto? (f(A, B) = A and B

if i have f({1}, {1, 2}) = {(1, 1)} this is not onto right? not all elements of B are paired

isnt that the result for f(a, b) = a and b?

[eager tendon]

how would i solve this..?

i thought about making a graph to maybe demonstrate it and visualize better

but i still dont quite get it lol

big O notation is used when we deal with large numbers that are all similar

if the question is, what is O(x^2) the one that seems the most similar is x^2+1000 which would be my guess

but thats as far as the depth of my answer and knowledge goes

i also know that we tend to either ignore polynomials or put them all under the same polynomial, constant multiple

in these questions lol

but again, how would i decipher the logic and solution?

first two questions

[unreal stump]

3x^3 is omega(x^2)

[eager tendon]

can you explain why?

[unreal stump]

Is this an exam/graded assignment

[eager tendon]

No, it is just exercise, regardless i wouldn't intend on cheating? lol

I'm asking for an explanation because i don't understand, i've also written down the extend of my knowledge so any help learning and understanding would be greatly appreciated

[unreal stump]

Ok,so you know what a limit is right?

[eager tendon]

No, i don't.

[unreal stump]

Ok, that's a bit problematic

So you say
a function f(x) is omega(g(x))

If there's a constant c and a cutoff n_0 such that

c g(x) < f(x) for all x > n_0

So, 3x^3 is omega(x^2) because
Well

(1) x^2 < 3x^3 for all x>(1/3)

I guess you can understand that by graphing 3x^3-x^2

And noticing how it always stays above 0 for x>1/3

[eager tendon]

Before searching myself, do you have any ressources you'd like to recommend? I'd love to try and understand and learn limits.

[unreal stump]

I learnt via school but ig Khan academy is good

[eager tendon]

shit XD well im trying to learn now through college, not going great, not that the material is to blame or anything

I thought about khan academy but it doesn't look like they offer videos of discrete math yet

[loud oyster]

Need help

[elder berry]

I wonder if in the above question they meant |f^-1 ({7})| = 5

But they probably didn't, so just find a function that has an inverse which maps 7 to 5.
This means your original function will map 5 to 7

[umbral blade]

The last 3 propositions are actually false

Does anyone know why the third proposition is false. How isn’t it a subset of that powerset?

[elder berry]

Look at what X is again. It's not a set. It is either 1 or 3.

As such, X is an element of {1, 3, 5}.
Though the question doesn't ask that, it asks if it's a subset

[loud oyster]

should all other elements except 5 also map to 7 or no?

[elder berry]

Not really necessary (given the notation you currently have), but that function would be valid as well.

[elder berry]

I'd actually encourage it because it also solves the above question that I had

[umbral blade]

The elements in {1,3} would be 1 and 3

Oh I see

1 and 3 are not in that power set

But the set of 1 and the set of 3 are in the powerset

[elder berry]

yup

[umbral blade]

Thank you

[wary scarab]

Can someone help me with this?
I need some clarification on what we have to exactly find: is it the probability that there's this sequence : wbwbw or wbw but not wbwbwbw or more than two blacks? I don't understand why the word atmost is used.

[elder berry]

The beads colored black are all next to each other, like wwbbbw.
Another way to phrase that the black beads are next to each other is

1. All black beads occur sequentially;

2. There is at most two black beads having white beads next to them.

For the given example, wwbbbw are next to the white beads, and are 2 in count

if there were more neighboring white beads, the arrangement of black beads wouldn't be sequential

[wary scarab]

Ah I see

So if N=6 and k=4, I'm asked to find the probability of this: wbbbbw configuration right?

in a cycle

[elder berry]

bbbbww or wbbbbw or wwbbbb (and the others lol)

[wary scarab]

yeah, thanks for clarifying

[carmine summit]

is there any definitive way to derive a equation from a truth table without ending up with some odd 33 logic gates

[wary scarab]

wait what else could there be?

[elder berry]

wwbbbb, bwwbbb, bbwwbb, bbbwwb, bbbbww, wbbbbw

[wary scarab]

right, thanks

[coral parcel]

Finding a minimal expression and/or circuit for a given truth function is NP-hard when the input is an arbitrary expression. But it might be different if the input is an entire truth table (because then the input itself is necessarily large when there's many variables).

[weary tiger]

Some student has asked every faculty member a question.
Let A(x,y) be x has asked y a question, F(x) be x is faculty, and S(x) be x is a student. I would build the sentence like so:

$\exists x \forall y ( F(y) \land S(x) \rightarrow A(x,y))$

[vital dew]

n/c

[weary tiger]

But this is not correct, how come?

[brave rock]

Well, let x be someone who isn't a student

then for all y, if (something false) then ...

So this is vacuously true if there is a single person who isn't a student.

I think you're misinterpreting (A & B) -> C as meaning A & (B -> C).

they're quite different!

[weary tiger]

I don't think I follow your example. If x isn't a student, then it's vacuously true, yes, but we are translating the case where such a student does exist

[brave rock]

No that's not what you've written

You're saying: There exists a person x such that, for all people y, if y is faculty and x is a student, then x has asked y a question

So in fact you have not required that x is a student: you include it in the "if ... then ..." which is incorrect

You need to say:

"There exists x such that x is a student AND (something)"

[weary tiger]

Okay, let me give you a slightly different scenario.

Some student has not asked any faculty member a question.

In this case, $\exists x \forall y (F(y) \land S(x) \rightarrow \neg A(x,y))$ is correct, right?

[brave rock]

No.

[vital dew]

n/c

[brave rock]

This suffers from the same problem.

[weary tiger]

It is correct, because that's the book answer

[brave rock]

Well unfortunately the book is incorrect

[weary tiger]

Well, rather the book answer is $\exists x (S(x) \land \forall y (F(y) \rightarrow \neg A(x,y))$

[vital dew]

n/c

[brave rock]

There we go!

This is what I'm saying

[weary tiger]

But we can move the universal quantifier outside

[brave rock]

No... no you can't

[brave rock]

I repeat this

[weary tiger]

I know they're not the same, but why can't we do that here?

[brave rock]

Hold on just a moment, I need to think through these cases

[weary tiger]

S(x) is independent of y

So, \exists x S(x) is logically equivalent to \exists x \forall y S(x)

[brave rock]

There would be issues in general moving this along if there were no such y

But I think you are in luck this time, as there being no faculty would make it trivial

However the misinterpretation above is still in play

You need to use your brackets!

[weary tiger]

Can you explain why it is a misinterpretation?

[brave rock]

A & (B -> C) is not the same as (A & B) -> C.

[weary tiger]

I know that..

[brave rock]

Yes, and that is the misinterpretation; this is what you have written

[weary tiger]

Yeah, but why is it not the latter?

[brave rock]

Because in particular we must know that x is a student!

[weary tiger]

But we do know that x is a student.. If x is not a student, we do not pass the A & B check

[brave rock]

No that doesn't mean we know that! It would be trivially satisfied if x were not a student

Let me put it this way

Let's say we're looking at a specific lecturer, I'll say Sally

and we want to say, some student has asked Sally a question

This is not the same thing as saying Exists x. S(x) -> A(x, sally)

This would be satisfied by x = Sally, where Sally is a faculty member!

You need to say: Exists x. S(x) AND A(x, Sally)

Does that make sense?

[weary tiger]

So when it is trivially satisfied, our implication would be true, but that would not be representative of the sentence 'a student asked prof Sally a question'

Since Sally is not a student

[brave rock]

That's right, so that's not the correct way to write that sentence

[brave rock]

This is how you were writing it here

[weary tiger]

So it's basically like modus ponens or something

[brave rock]

If Sally were the only faculty member, what I just replied to would be equivalent to Exists x. S(x) -> A(x, sally)

[weary tiger]

Right?

[brave rock]

Idk what you mean by that but the point is that it's just not the same thing

Idk how modus ponens comes into it.

Try rewriting your first attempt correctly

[weary tiger]

Well, modus ponens P -> Q and P, right?

Well I guess it's not quite the same so never mind

But you've been incredibly helpful

[brave rock]

Yeah I don't think it's relevant.

Glad to hear it

[weary tiger]

Thanks

[brave rock]

No worries

[river tulip]

6c + bc = what is b. and. c

[brave rock]

No way to determine that given the information you've provided

[river tulip]

lets say b =12 c is timed by 9 to figure out c so 9 x c =36

still never figured out huh

[brave rock]

Still no way to determine that given the information you've provided

[eager tendon]

Do you guys know any good recommendations, for alternative ressources on the internet, preferably video based, that talks about big o notation in the context of discrete math? I have read the book a little too much and still does not seem to get it. I have googled a bit and read around and still no luck making it click, so i am just asking for recommendations if you guys have any! Otherwise i will just proceed to google and hope it'll click eventually.

[edgy wraith]

I have a problem understanding propositional logic when there are multiple operators and the truth table involved.

A="It's cold."
B="It's snowing."
(B∨¬A)="It's snowing or it's not cold."

If B and A are true, then B∨¬A are also true? And if B is not true but A is, then is B∨¬A true too? What if B is true but not A? Then B∨¬A can't be true right? I don't get it.

[brave rock]

If B and A are true, then B∨¬A are also true?
Yes
And if B is not true but A is, then is B∨¬A true too?
No, since neither B nor ¬A are true.
What if B is true but not A?
Then since ¬A is true, we have B∨¬A is true.
Then B∨¬A can't be true right?
No as explained.

Let me talk about this in general

If P and Q are propositions, then what does it mean for P∨Q to be true?

It means that one of the following cases hold:

• P is false, Q is true
• P is true, Q is false
• Both P and Q are true.

That's it.

[edgy wraith]

P and Q both need to be false so P∨Q is false. If at least one of them is true, P∨Q is true.

[brave rock]

That's right.

[edgy wraith]

But what if Q is negated. My mind can't wrap around this

Because I feel like it changes a lot

It's really complicated for me once there is more than 1 operator

[brave rock]

¬Q is true when Q is false

that's it

So P∨¬Q is true means that at least one of P and ¬Q are true.

Is this working for you?

[edgy wraith]

So the same rules of disjunction apply?

[brave rock]

Yes, they don't change

[edgy wraith]

Both P and ¬Q need to be false so P∨¬Q is false

Rest is true

[brave rock]

That's correct

[edgy wraith]

Alright

Thanks

[brave rock]

No worries

[eager tendon]

guess thats a no, how obnoxious

[weary tiger]

Either this polynomial has degree 2 or it has degree 3 but
not both. (n = “This polynomial has degree 2,” k = “This
polynomial has degree 3”)
Can i write this equation like this: (N and K)And(not N and not K) ?

[swift urchin]

should be (N or K) and not(N and k)

[weary tiger]

oh so on second part not has to be outside of parenthesis ? is that a must ?

[swift urchin]

not really, that's how i wrote it. another way could be (not N or not K)

[weary tiger]

oh so on second parenthesis i shall just change and with or and thats it right

[swift urchin]

and in the first parantheses, it should be or, not and.

if you want to go down a rabbit hole, this is equivalent to the XOR operator

[weary tiger]

alright sirs ty

[lusty fern]

is there a formula to count odd numbers (or even) between 2 numbers a.........b?

i find undercounting a lot of times

usually by 1 or 2

[obtuse lance]

it might be easier to work out a formula for 0 or 1 to n, then use that formula to subtract off the ones from 0 to a from 0 to b

and you'll probably need to use rounding at some point in your formula

[lusty fern]

hmm

i guess u can do

b-a + 1

that'll give u the number of numbers

if the number is odd the +1

otherwise just divide by 2?

[weary tiger]

KKK

[odd compass]

I'm not sure of understanding what a biconditional does outside of the direct application of its truth table. Of what use is it?

[coral parcel]

It asserts that the two formulas have the same truth value. It is most useful together with one or more universal quantifiers, where it allows us to say "the things that have this property are exactly the same things as the ones that have that property".

(Personally I'd even say "most useful" should be "only useful", but that is a slightly spicy take).

[zealous kraken]

whats the degree of a root?

vs degree of a tree

[odd compass]

And how is this different from equivalence?

[distant glade]

they’re very similar, but equivalence is more “meta” level

[stray reef]

@zealous kraken what do you mean by "degree of a tree"

[odd compass]

what does meta mean?

[coral parcel]

Note that some logic texts use the $\equiv$ symbol instead of $\leftrightarrow$ or $\Leftrightarrow$, but with the same meaning.
Depending on what you're reading, there is not necessarily any difference between "equivalence" and "biconditional".

[vital dew]

Troposphere

[atomic igloo]

@stray reef heyo

I need some help with discrete math if you could

[stray reef]

who even are you

[atomic igloo]

someone who needs help with discrete math :(

you were the only online person on this chat and i asked everyone lmfao

[stray reef]

surely i am not the only person online in this server of thousands...

if you want help with discrete math you should post the problem(s) you need help with

[atomic igloo]

the discrete math chat lol

[stray reef]

and then whoever is able will come along

[atomic igloo]

@stray reef okie sorry for tagging you

if anyone could explain this that would be very helpful

[obtuse lance]

where's the first word you get stuck at when reading it?

[hearty hound]

how do i show that the relation is transitive?

A ∆ B is finite, B ∆ C is finite, show that A ∆ C is finite

[stray reef]

here's a hint: symmetric difference is associative and the symmetric difference of any set with itself is empty

[hearty hound]

hmm let me think

yea still stuck 😅

[stray reef]

consider $(A \mathop{\triangle} B) \mathop{\triangle} (B \mathop{\triangle} C)$

[vital dew]

Ann

[hearty hound]

i see

because it's associative then it's the same as A traingle (B triangle B) triangle C

and B triangle B is empty so it's the same as A triangle C

[stray reef]

yes there you have it

[hearty hound]

what about symmetric

[stray reef]

as in, symmetry for the relation?

[hearty hound]

yes

[stray reef]

symmetric difference is commutative, which makes this obvious

[hearty hound]

i see ok thank you so much

[raw jetty]

can someone help with cantor's diagonalization stuff? my problem is this: Use a diagonalization argument to show that the set of all infinite sequences of numbers from 0 to 9 is uncountable

[stray reef]

have you seen the diagonalization argument for the uncountability of R? or maybe that of (0,1)?

[raw jetty]

yes, i undestand for binary, but im not sure how to apply it to other numbers

[stray reef]

the crux of the argument is that, given a list of sequences, you can construct a new sequence that differs from every sequence on the list in at least one position

the fact that the terms of your sequences can now take ten values instead of two is not a hindrance, and instead just gives more wiggle room

with binary sequences you had no choice but to flip 0 to 1 and 1 to 0

but with sequences of decimal digits you can now transform them any way you like, so long as no digit is transformed into itself

[raw jetty]

so instead of writing (0,1,1,1,0,1,0,0,1) i could use any digits in any order?

[stray reef]

...you misunderstand

the crux of the argument is that, given a list of sequences, you can construct a new sequence that differs from every sequence on the list in at least one position
to do this, you form the sequence by taking the 1st number in the 1st sequence, the 2nd number in the 2nd sequence, and so on, and then changing each number to something different

how you do this change is up to you

[raw jetty]

ohhh yes i see thank you

that is the grid you are referring to there?

or just a1= a1,1 , a1,2 , a1,3...

[stray reef]

...???

[raw jetty]

just in terms of forming the sequence, i remember my teacher put all of the numbers on a grid first

something like this

[stray reef]

yeah, sure, the rows of the grid are your sequences

[raw jetty]

okay thank you!

[zealous kraken]

whats the expected number of times an element, x is compared with the pivot in randomized quicksort, I know how to find the total number of comparions but cant seem to figure this one out.

[worn inlet]

is this well ish written?

the point is to define notation for discretized functions

particularily $x_i$, the function $u(x_i) = u_i$

[vital dew]

madlor

[glossy dirge]

Is this correct?

x and y are whole numbers larger than 0

If it is i could pass my final

Anyone?

[serene mural]

could someone explain step 4? where did 2^k come from?

[elder berry]

For now ignore the thing in the brackets

you have 2^k fractions in total (do you see why?)

all of which are greater or equal to 1/2^(k+1)

[serene mural]

cause 1/2 + 1/3 till 1/2^k ?

[elder berry]

didn't really understand that

the number of numbers in 1/2^k, 1/(2^k + 1), ..., 1/2^(k+1)
is the same as
the number of numbers in 2^k, 2^k + 1, ..., 2^(k+1)

agree?

[serene mural]

yes

[elder berry]

(don't worry where this is coming from, just if it makes sense that both have the same number of terms)

right, we can write 2^(k+1) as 2^k * 2 or 2^k + 2^k

so you are looking at the sequence of 2^k, 2^k + 1, ... 2^k + 2^k

oh whoops we start from 2^k + 1

regardless, as you can see the sequence is 2^k + 1, 2^k + 2, 2^k + 3, ..., 2^k + 2^k or we go from 1 to 2^k

that's why we have 2^k numbers in total, which is the number of fractions

[serene mural]

oh so there's 2^k number between 2^k +1 and 2^(k+1)?

[elder berry]

yup!

[serene mural]

i see

[elder berry]

the same will be true for the fractions

[serene mural]

but how does that change 1/(2k^+1)...1/(2^(k+1)) to 2^k * 1/(2^(k+1))?

[elder berry]

right, what you want to do is compare each term with 1/(2^(k+1))

$\frac{1}{2^k + i} \geqslant \frac{1}{2^{k+1}}$

[vital dew]

peaceGiant

[elder berry]

any fraction on the third line will be greater than 1/2^(k+1)

[serene mural]

sorry i still don't get why

[elder berry]

do you agree that 1/(2^k + 1) >= 1/(2^(k+1))?

[serene mural]

absolutely

[elder berry]

alright, same is true for 1/(2^k + 2) >= 1/(2^(k+1))

and 1/(2^k + 3) >= 1/(2^(k+1)) and ... up to 1/(2^k + 2^k) >= 1/(2^(k+1))

good?

[serene mural]

ohh so there's 2^k numbers that's >= 1/(2^(k+1))

[elder berry]

mhm

[serene mural]

i see, thank you very much for the help

[elder berry]

np

[weary tiger]

Hey, do you remember the question from yesterday? I'm not sure if I understand the book's answer. It is ∀y(F(y) → ∃x(S(x) ∨ A(x,y)))

I understand the answer we ended up deriving, but not this one. This just says, if y is faculty, then there is a person x such that x is a student or x has asked y a question.

That doesn't seem right to me

[brave rock]

Probably meant and rather than or, which would make it a simple typo

[weary tiger]

@brave rock So you think it means S(x) and A(x,y) which then means if someone is a member of faculty, then there is another person who is a student and who has asked them a question?

[brave rock]

Yes

[zealous kraken]

hey guys whats the best place to discuss expected values, here or #probability-statistics

[brave rock]

The latter.

[floral tangle]

does anyone here have a pdf on the properties of relations with complete examples showing when is a relation reflexive, symmetric, antisymmetric, transitive, etc.? I don't easily understand formal math language since i'm not a math major

[raw jetty]

i have this, i can try and find something in more proper english if you would like as i also don't really understand formal math language

[rapid mural]

Would some examples be helpful?

[glacial flame]

I'm finding division under modulo kind of confusing; how can a fraction have the same remainder as a whole number?

[obtuse lance]

you can think of it as an extension to fractions that's consistent with multiplication in modular arithmetic

since maybe normally it doesn't make sense to think of the remainder when 1/2 is divided by 3 being 2, but since 2*2=1 mod 3, it kind of makes sense to extend it that way. Hopefully that's not too terse

[bold merlin]

Let Q be the set of binary strings of the form 1^k0^l, where k, l ∈ N with k ≤ l. I need a recursive decomposition and a generating series with respect to length for this. My thoughts was the exp. S = e U 0 U 1S00* but it doesnt lead to the correct generating series in the answers. Any tips for what I'm missing?

[glacial flame]

I'm not entirely sure where you're getting the 2*2 generally speaking; I don't understand how you would write it out for something like 5/7 or 37/59

From some wacky math I did, I came to the conclusion that 5/7 === 1 (mod 4), but I have no clue if that's right and I'm not sure of the proper way to calculate it

(these are just random numbers I'm pulling up; they have to be coprime iirc?)

[obtuse lance]

yeah, you can't have a number in the denominator unless it's coprime with the modulus

for instance, you can write 5/7=x mod 4 as 5=7x mod 4 then reduce to 1=3x mod 4, then multiply both sides by 3, 3=9x mod 4 which reduces again to 3=x mod 4 (there are other ways too)

another way you could check your answer is take 5/7 = 1 mod 4 and multiply both sides by 7, you'd get 5=7 mod 4, which reduces to 1=3 mod 4, so that's how you know you made an error

[glacial flame]

What I did was 1=3x mod4 -> 2=6x mod4 -> 2=2x mod4 -> 1=x mod4; what did I do wrong? I don't recall any rule about what you multiply by having to also be coprime

[brave rock]

2=2x mod4 -> 1=x mod4

This isn't correct

[glacial flame]

oh I guess you can't divide right

[brave rock]

Not always

but sometimes you can

[glacial flame]

oh wait this is the same division issue isn't it

[obtuse lance]

yeah

[brave rock]

In this case, 2*1 and 2*3 are both 1 mod 4.

[glacial flame]

which is why it must still be coprime

and what you did was circumvent division by getting a coeff of 1 solely from cycling

[obtuse lance]

yeah I suppose

[glacial flame]

so is division under mod basically a different operation from usual division? It feels like it represents something completely different from normal division, though I can't tell what

basically what I'm asking is, what does it mean mathematically; what does it represent?

[brave rock]

Division under modular arithmetic does not exist in general

However, multiplication always exists

[glacial flame]

is it just a cryptography thing?

[brave rock]

and if you choose the right thing to multiply by, this is the same result as dividing

So the question is, when does the right thing to multiply by exist? When the thing you want to cancel out is coprime to the thing you're modding out by

This really has very little to do with cryptography at the moment; this is just number theory

[glacial flame]

My prof said it's used a ton in cryptography

and I'm not really understanding what division under mod is actually "saying"/"representing" mathematically

[brave rock]

Yes, number theory is used in cryptography.

OK let's do another example

What is division in the real numbers? When I divide by 2, I'm just multiplying by 1/2.

Similarly when I 'divide' by 3 modulo 4, that's actually the same as multiplying by 3.

This is what I was talking about above.

[glacial flame]

yes I understand that, but it feels like the result is nonsensical; how is this useful? What can it model?

[brave rock]

It models divisibility in the integers.

This is what modular arithmetic is

[glacial flame]

in my class modulo was defined by divisibility

[brave rock]

That is it, yes.

[glacial flame]

so this doesn't make sense

[brave rock]

Bruh

[brave rock]

Literally this

[glacial flame]

divisibility was used to define mod, so how are we using mod to define divisibility? Isn't that cyclical logic?

[brave rock]

Bruh

[obtuse lance]

don't think of "1/7" like a rational number, instead they'll sometimes write it as 7^-1 to mean "what number mod m can I multiply by 7 to make 1?"

[brave rock]

It's telling you how divisibility behaves

Is that a better way to describe it for you?

[glacial flame]

so is there a related equation using divisibility that this represents? Something like 5/7 mod 4 === ... | ...?

[obtuse lance]

so 1/7 mod 4 isn't going to be the same object as 1/7 you're used to, even though it's the same symbol being used

[glacial flame]

I understand that now; I guess I'm just confused what this result represents/how you can apply it to something tangible, whether it's a word problem, etc.

[obtuse lance]

yeah, it might require a bit more machinery than what you know currently, but basically in a broad way modular arithmetic is used for solving diophantine equations, basically equations where the solutions are integers

which could be various kinds of counting problems, which is kind of a vague answer I realize

[glacial flame]

Maybe I'm just misunderstanding what you are saying; are you talking about the divisibility operator (|), or are you talking about general division?

[brave rock]

There is no division in the integers.

You cannot divide in general.

[glacial flame]

that's what I thought

[brave rock]

I am talking about divisibility.

[glacial flame]

is there some formulaic conversion between "division" under mod and an equation using only "|"?

[brave rock]

Think about it and try to write down such a conversion.

This is a good exercise

[glacial flame]

oh wait for something like a === b mod m, this is the same as m | a - b; is it related to that?

[brave rock]

Try doing the exercise

[glacial flame]

a/b === x mod m -> m | a/b - x?

[brave rock]

This notation a/b is bad.

[glacial flame]

oh wait

a/b === x mod m -> m | a - bx?

[brave rock]

Remember what I said: division doesn't happen

This is still bad

[glacial flame]

then I'm lost

[brave rock]

I can tell.

What you're looking for is a description of when ab = ac mod n implies b = c mod n.

This is called cancellation.

This is 'dividing by a'

Turn this into a statement about divisibility of integers by n and you may find it familiar.

[glacial flame]

n | a(b-c) -> n | (b-c)

I thought it could only be implied the other way though?

[brave rock]

Aiyah

This is what we discussed previously

indeed, you cannot do this for all numbers a.

[glacial flame]

Are we finding a by doing the "division" by a under the mod?

[brave rock]

You cannot 'find' a

because there will be many such a for some n

[river tulip]

yes it is possible

[brave rock]

Does this look familiar to you?

[glacial flame]

Then what is the relation between ab = ac mod n and a*b^-1 = x mod n

[glacial flame]

no?

[brave rock]

Oh well then

[brave rock]

Rewrite this as ab = x mod n

[glacial flame]

oh so we are splitting x into ac?

[river tulip]

#discrete-math message

[brave rock]

now it turns out that if I can cancel a as in the left, there is some a^-1 such that a^-1 a = 1 mod n

[glacial flame]

was I supposed to learn this? because our prof glossed over literally everything

[brave rock]

Well this is a number theory thing one learns, it's a generalisation of Euclid's lemma

if a is coprime to n and n | ab, then n | b.

Anyway as I was saying

N.b. that a^-1 is not one divided by a as a rational number

think of this ^-1 as purely symbolic for the moment

Now since we have ab = x mod n

we have a^-1ab = a^-1 x mod n

so b = a^-1 x mod n

So we've solved for b by multiplying by a^-1

Nice eh

[glacial flame]

can we kind of think of it as a similar operation as inverse matrix, in that it's not literally 1/..., rather, it's an overloaded operation?

[brave rock]

Yes.

That's a very good way of looking at it

[glacial flame]

and the relationship to divisibility would be n | a^-1*x - b?

[brave rock]

Well that's literally writing it out but sure

The relationship to divisibility is something called Bézout's lemma.

[glacial flame]

ax + by = GCD(x, y)?

[brave rock]

there exist a and b such that this holds, yes.

[glacial flame]

ye

[brave rock]

It's a good exercise to prove that Bézout's lemma for GCD(x,y)=1 is equivalent to there existing an inverse for x mod y whenever GCD(x,y)=1.

[glacial flame]

I feel like I don't know the tools to solve it because we have only learned the definitions of things, not their connections to each other nor their proofs (it was all hand-wavy, axioms, etc.)

[brave rock]

You have all the tools to solve it; it's basically just unwrapping the definition.

Just try.

[glacial flame]

Sorry I was walking home; am I proving ∀x,y in Z((GCD(x, y) = 1) -> (∃a in Z( ax = 1 mod y)))?

[river tulip]

anyone up for a challenge

[cerulean wind]

just ask

or put it in #competition-math

[chrome tree]

Hey people

I have a question regarding discrete math

I have to show that n^n is greater then or equal to n! for n=1,2,3,...

A picture of how it looks on maple.

Do i use the mathematical induction method here?

[cerulean wind]

depends on how formal you need to be

one method involves comparing n with each term of n!

[chrome tree]

And the other?

[cerulean wind]

induction

[chrome tree]

Which one would you recommend

[cerulean wind]

are you in a class which requires formal and precise mathematical proofs? if yes, then induction

if you’re allowed to be a bit more relaxed, then the former

[chrome tree]

Well I think formal is best as I can look back at it if I have to do something like this again.

[cerulean wind]

for intuition, n >= n - k for 0<= k <= n - 1

so the product n^n >= n!

that would be the “lax” proof

[chrome tree]

Ok thank you.

[coral parcel]

What are x and y here? The elements of an equivalence class should be things from W, but then {-x,y} doesn't make sense -- there's nothing you can negate and get an element of W out of.

It also looks like some of your claimed equivalence classes share some elements, but two different equivalence classes can never have an element in common.

[azure willow]

https://i.imgur.com/6CmW4Ze.png

why does this equal to 5 * 10 * 9 ?

i know you're gonna do something like 5C(2-1) * 10C(2-1) * 9C(2-1) but why is it specifically 5, 10, 9?

[coral parcel]

Once you've handed out the obligatory 3 of each fruit to each child, the surplus you actually have a choice about comprises 4 apples, 9 oranges, and 8 bananas.

The factor of 5 comes from the 4 apples, because the oldest child gets either 0, 1, 2, 3, or 4 of them, in total five different possibilities.

You could view that as a stars-and-bars problem with 4 stars and 2-1 bar.

[sweet thunder]

Can someone help me understand this first bit

I’m trying to understand why that if p|q1 then p=q

[stray reef]

gonna need to see the original question w/ all the notation therein

[stray reef]

,rccw

[stray reef]

the notation in this problem is different...

[stray reef]

this looks like a reply to a stackexchange post. please show the original stackexchange post.

[sweet thunder]

OHH 🤦🏽‍♂️I read the question that was posted on stackexchange incorrectly…I understand why p=q if p|q1. Both are listed as prime for that question.

But now I’m lost on how to go about my question since a1,a2,…an are not necessarily prime.

[stray reef]

it's the same, only that you replace q_i with a_i and don't assert equality at the base step

you don't actually need equality there anyway

the base case n=1 is trivial

if p | a_1 then p | a_1

[sweet thunder]

Oh, okay I get it. Thank you!

[frigid abyss]

does anyone know why for the inductive step f(ceil(k/2)) was used instead of f(ceil(k+1)/2)?

[agile magnet]

Why would you use ceil(k+1)/2 @frigid abyss

That isn't in the definition of f(n)

[frigid abyss]

the +n becomes (k+1), so i don't get why f(ceil(n/2) doesn't become f(ceil(k+1/2)), same thing for floor.

[agile magnet]

Oh I see

Yea looks wrong to me

[floral tangle]

I learned of a theorem that states that if the nth power of a relation R is a proper subset of the relation R itself, then that relation R is a transitive relation. n is the set of all natural numbers (i.e. from 1 onwards). but what if the 2nd power of the relation R is a proper subset of the relation R, but the 3rd power of the relation R is not a proper subset of the relation R? would the relation R be transitive since R^2 is a proper subset of R despite R^3 NOT being a proper subset of R?

[coral parcel]

First, can you construct an example of a relation with that property?

[floral tangle]

to be honest i don't know. i'm not even a math major but i find this theorem convenient for our subject in discrete structures

but when i tested this theorem in a relation that was not transitive, all powers of R were not a proper subset of R

except of course for R^1

[coral parcel]

R¹ is never a proper subset of R.

[floral tangle]

a proper subset is a subset that can be equal in magnitude to the set it is being compared to right?

isn't the "proper subset" the symbol with the line underneath the cup opening to the right?

[coral parcel]

"A is a proper subset of B" means "A is a subset of B but is not equal to B".

[floral tangle]

oh my bad. i meant subset

the theorem states that if and only if R^n is a subset of R, then R is transitive

[coral parcel]

No $\subseteq$ just means "subset". "Proper subset" is $\subsetneq$, and $\subset$ can mean either, but most often means proper subset.

[vital dew]

Troposphere

[floral tangle]

i see isee thanks

but is it possible for some power of R to be a subset of R, and that same R when raised to a different power will not be a subset of R?

[coral parcel]

If you stare at the definition of "R is transitive" and the definition of "R² is a subset of R" for a few minutes, you will find that they are different ways of expressing exactly the same condition.

If R is transitive, then R^n will be a subset of R for every n.

[floral tangle]

okay thank you

[coral parcel]

On the other hand it is possible that, for example, R³ is a subset of R, but R is still not transitive. This is for example the case if we define a relation on the integers by

n R m iff m=n+1 or m>n+2

[floral tangle]

so i can't always use the theorem to test if R is transitive? when i learned this theorem i was glad because i didn't have to scour the internet for multiple sources on how to determine if a relation is transitive. i still don't really get the pattern for determining if a relation is transitive or not

granted there is a formal definition for relation properties but i don't quite understand how formal logic works so i misinterpret some of the symbols

[floral tangle]

wait, even if that's the case, surely there is some power R^n such that R^n is not a subset of R right?

n may not be equal to 3, but there is still a value n which makes R^n not a subset of R

[coral parcel]

Yes, since "R^2 is a subset of R" means the same as "R is transitive".

If [there is a y such that xRy and yRz] then xRz.
The choices of x and z the backeted part is true for is exactly the definition of R^2 and "then xRz" says it is a subset of R.

[floral tangle]

i see, thank you. could you provide some resources from the internet for supplementary reading? if it's not a hassle

[coral parcel]

I'm afraid I'm not good at providing references.

[floral tangle]

okay i'll just ask one more question since i still don't quite understand. i am slightly new to this

[floral tangle]

but if we apply that logic in your example of "R^3 is a subset of R", can't "R^3 is a subset of R" be also interpreted as saying "R is transitive". but as you said, despite R^3 being a subset of R, R is still not transitive because of the condition you provided for the integers

[coral parcel]

No it cannot. It's a weaker condition.

It doesn't match up with the definition of "transitive" the way the R^2 claim does.

[floral tangle]

noted. thank you very much

[floral tangle]

so from what i understood, do correct me if im wrong, if i want to determine if a relation R is transitive I only need to check if R^2 is a subset of R. if R^2 is a subset of R, then R is transitive

because i plan on using this method for determining if a relation is transitive since it is easier for me to understand

[coral parcel]

Yes.

[floral tangle]

okay thank you for your time i am really grateful

[dense crane]

Hello, I have to prove this. Can anyone give me some pointers as to where to start?

[elder berry]

Showing x < y is the same as showing x-y < 0. Now start with the given inequality, move everything to one side and force x-y to appear in the inequality

||7x + 3/y - 4y - 2/x < 0 <=> (4x+3x) + (2/y + 1/y) - 4y - 2/x < 0; we split the bigger terms so we can match the coefficients with the smaller terms, to force x-y to appear||

||Rearrange, (4x - 4y) + (2/y - 2/x) < -3x - 1/y which becomes (x - y)(4 + 2/(xy)) < -3x - 1/y|| ||From here conclude that (x-y)*(positive number) < negative number only when x-y<0||

Perhaps there is a more elegant solution?

(one can loosen the upper bound as ||7y+3/x|| but it's the same argument)

[dense crane]

This actually helped a lot and is, in my opinion, quite an elegant solution. Thanks! I hadn't previously thought about splitting up the bigger terms to get x-y which was my main reason for getting stuck.

[floral tangle]

what is the weird looking "less than or equal to" symbol called? context: this is from a lesson on partial ordering, posets, and equivalence relations

[floral tangle]

a and b are elements of a poset

[coral parcel]

In LaTeX, it's $\preccurlyeq$.

[vital dew]

Troposphere

[coral parcel]

If you're asking for its meaning, in the absence of more information I'd guess it stands for the partial order on the poset.

[floral tangle]

okay thank you

[coral parcel]

7x + 3/y < 4y + 2/x
is the same as
7x + 3/y - 4y - 2/x < 0
For fixed x, the LHS is a strictly decreasing function of y, so the y's that satisfy the inequality are the ones above some threshold that depends on x. If we can show the inequality is not satisfied on the line x=y, then we're done. However for x=y, we have
7x + 3/x - 4x - 2/x = 3x + 1/x
which obviously is not negative since x is assumed positive.

[eager tendon]

How do i show that x^3 is not 7x^2 ?

Please read my argumentation. So my train of thought and what i have understood is that there is no fixed C value that will keep making x^3<=7x^2

But, how do i prove that, i guess is where im getting to. Or more eloquently put it/argue for it, because i do not think my line of thinking satisfies the full answer

[coral parcel]

You're lacking the big O in your description of the task.

[coral parcel]

When you want to argue that a thing with certain properties (here: a fixed C such that bla bla) does not exist, you can follow two strategies:

1. Assume that it does exist, and derive a contradiction.
2. Assume you find a random ting in the street; prove that it doesn't have the property.
   They're closely related, but it pays to me explicit about which one you're using when you write it down. Many people find perspective (1) easiest to think of when exploring possible proofs, but (2) generally leads to more straightforward final proofs.

So assume your adversary comes with some number C where he claims that x^3 <= 7Cx^2 for all large enough x. How can we know he's a liar without inspecting the number in detail?

[eager tendon]

My answer would be that, once x > 7(C) it would no longer reign true that x^3<=7Cx^2

[coral parcel]

Right, so there's your proof.

[eager tendon]

Okay! I'll try to implement this line of thinking, thank you very much :)!

[weak sand]

Hi, is there a way to calculate how many automorphism does a graph have?

[brave rock]

There's not really any easy way I'm afraid

These things can be very difficult in general

[heavy rain]

for a set to have a power set, the power set has to have more elements than the set we're talking about right

or am i like super missing and that made no sense?

[brave rock]

The power set of S always has more elements of S, that's true

But idk what you mean by "for a set to have a power set," as every set has a power set.

[heavy rain]

imma just open a ticket

idk

[brave rock]

I mean you can just ask but sure

[heavy rain]

okay so

the question is

Determine whether each of these sets is the power set of
a set, where a and b are distinct elements

and this is the set

{∅, {a}. {b}. {a, b}}

so the cardinility is 4 because it has 4 elements right?

[brave rock]

Yup

[heavy rain]

but the question refers to the power set

and it just says The power set of {a, b} is {∅, {a}. {b}. {a, b}} .

[brave rock]

Yes so we're trying to determine if this is the power set of some set

Yeah

[heavy rain]

but like idk what that means

[brave rock]

Do you know the definition of the power set of S

[heavy rain]

like the answer is right here and i still dont get why its the answer lmao

im not sure what that means im sorry

[brave rock]

Yeah well there's your problem

OK I will explain this

[heavy rain]

it says the power set of A is {a, b}

[brave rock]

No that's not true

In the future, you should look back and make sure you understand the definitions. I will explain what the power set is now, though.

Let A be any set.

[heavy rain]

bruh the answer is wrong?

[brave rock]

The power set of A, denoted P(A), is the set consisting of all subsets of A.

So for example:

Let A = {1,2}

the subsets of A are ∅, {1}, {2}, and {1,2}.

[heavy rain]

thats 4 subsets right

[brave rock]

Whoops typo

Yes indeed there are 4 subsets of A.

So the power set of A is P(A) = {∅, {1}, {2}, {1,2}}

Is that clear?

[heavy rain]

A = {1,2} because theres two variables?

[brave rock]

I defined A = {1,2}

there is no 'because'

I simply defined it as so.

Because, as I said, this is just an example.

[heavy rain]

okay gotcha

[brave rock]

So

[brave rock]

Do you see why this is right

[heavy rain]

okay so quick question, why is that the power set

like what makes that the power set

is that part of the example or is that definition

[brave rock]

I just defined the power set

I said so

[brave rock]

Here

This is the definition of the power set

Not for some particular set A, for any set A.

Does that make sense?

[heavy rain]

okay quick question, so if A = {a}

[brave rock]

Yup

[heavy rain]

then the power set would be {0, {a}}

[brave rock]

I assume you mean ∅ not 0, but if so then yes

[heavy rain]

yeah thats what i meant

okay i get it now

[brave rock]

Great

[heavy rain]

okay so {∅, {a}. {b}. {a, b}} is the powers set of {a,b}

[brave rock]

That's right

[heavy rain]

im so happy im gonna cry

thank you so much

[brave rock]

Woah there calm down that was like, 5 mins of work

dw about it

it's cool

[heavy rain]

bro comp sci major was the highest paying mistake ill ever make

[brave rock]

Something something math

[heavy rain]

have a blessed night my kind sir

you definitely will see me again

[brave rock]

you too

Feel free to ask whenever

[ashen gate]

i agree

[weak sand]

can somene please help find how many automorphism this graph may have? i'm going crazy

can flip it and rotate it 4x2 = 8 ways but is that it? i doubt

[obtuse lance]

you can flip the two vertices on each of the triangles

like this at the top left:

possibly more by exchanging two "arms" across the middle, but thinking some might be equivalent to some of the flipping you already have

[languid gust]

can anyone help me with a discrete math exercise

[fleet sable]

hi! struggling with this

[languid gust]

salam

[fleet sable]

salam!

[languid gust]

kifik

[odd compass]

For me, equivalence between two statements means that in all cases, they hold the same truth values. Hence my original question : I'm not sure of the nuance of the difference. I can say that two statements are equivalent because they behave similarly. But my question is of what use is the biconditional here.

[spring elk]

im confused by this example

so piA(D) means that pi(a, b) = a right?

but lets say i take the values (-2, -2) where a is -2, pi(-2, -2) will give me 9

but doesnt pi(a, b) = a for piA(D) mean that it should have been (-2, -2) = -2?

[spring elk]

nvm go tit

[weary tiger]

hello, can I prove this

using less than these 3

[coral parcel]

What does the $C^B_E$ notation mean?

[vital dew]

Troposphere

[pale epoch]

why not post your solution instead

[weary tiger]

$E \setminus B$

F

[vital dew]

Zephium

[weary tiger]

oh yes forgot to mention

A B C are all parts.. of E?

idk the word

subsets

[molten fjord]

any discrete math giga geniuses want to answer some of my questions about power sets, processors and parallel time

[pale epoch]

no, if you ask publicly anyone can help
i cant guarantee i have anything useful to say, but someone probably has

[brave rock]

It is not correct.

You implicitly use (1 + x)^k = 1 + kx but this is false.

Remember the inductive hypothesis is an inequality, not an equality.

Furthermore you end with showing kx^2 >= 0, which is true, but is not what you were asked to prove

[brave rock]

Please don't ping me. I'm not available to answer questions at all times.

[sonic path]

can someone check my work for this problem. im not very good at these types of problems and feel like i did unnecessary steps along the way

[brave rock]

Your arguments are valid but I think you've only showed that (p => q) => (not q => not p), rather than that they are equivalent, which is what the question asked

Unless I'm just mistaken there – it's likely I am as I don't recognise the rule you've applied

[spring elk]

can i get help with part 3?

part e*

i would think the inverse would just be [-1, 2] as well

why is that not thecase?

[brave rock]

for example, f(2.5) = 2 is in [-1, 2]

[spring elk]

but why can i even select 2.5

its not in range B

[brave rock]

So?

We're asking to discover f^-1(B), not B.

[spring elk]

f^(-1) is the inverse right?

so if id have f: (1, 2) then f^-1 would just be (2,1)

[brave rock]

the function f doesn't have an inverse

The notation f^-1(B) is referring to something called the preimage

it is defined as follows:

f^-1(B) = {a in A | f(a) in B}

[spring elk]

i was also confused why (i thought) it had an inverse in the first place becacuse e isnt one ot one

[spring elk]

oh

[brave rock]

Idk what you mean by e not being one-to-one. Being injective is a property of a function.

The function f : R -> R is not injective.

[spring elk]

right but we are taking a subset which could be injective

[brave rock]

No, a subset is not injective—this is exactly what I'm talking about

[spring elk]

oh

[brave rock]

Only functions can be injective. It is meaningless to say that a subset is injective

[spring elk]

thats good to know

thanks

[spring elk]

so in this example it would be {a in R | f(a) in B} ?

[brave rock]

Yes

The question is asking you to compute this set for various values of B.

[spring elk]

yeah this makes sense now thank you!

[brave rock]

No worries

[spring elk]

but in cases where the function is bijective, is the inverse function equal to the preimage?

[brave rock]

The preimage is a set; the inverse function is a function—so this is a badly-formed statement

but indeed if the function has an inverse then the preimage is the same as the usual image

We can define the image of a set A as a function as f(A) = {f(a) | a in A}

And this will coincide with the preimage appropriately when the function has an inverse

[spring elk]

how is this onto? i get that for A=P({1, 2, 3}) and B empty set this can work, but for cases where B is not empty this wouldnt work

should it not work for all cases for it to be onto?

[brave rock]

But we can choose B to be whatever we like

so it doesn't matter

[spring elk]

in this case cant we choose B ot eb whatever we like for one to one to make it true?

[brave rock]

No

[glacial flame]

If we have some sort of equation of the form 8x === 4 (mod 16), how do we know when x exists? Also, how would we find x with the correct x === _ mod n when there is a GCD > 1 throughout the equation?

[brave rock]

For the first part, x never exists since 8x is either 0 or 8 mod 16.

For the second part, I don't know what you mean by that

Please explain more

[glacial flame]

That was just a random example I made; is there a rule for how to determine it generally? I know that GCD must be 1 when x is the inverse, but I'm not sure about cases like this where it isn't the inverse.

A better example would be 8x congruent to 4 mod 12

[brave rock]

Right

[glacial flame]

which has this solution

[brave rock]

It certainly does

[glacial flame]

How do we determine the proper modulus for a general equation of this form?

[brave rock]

Well you say you know the gcd thing

[glacial flame]

yes but that's only for inverse (that's the only thing we learned)

[brave rock]

So presumably you know how to prove that there exists a solution x for ax = 1 mod b when gcd(a,b) = 1

Right?

[glacial flame]

I think we saw the proof once?

[brave rock]

OK well I want you to look back at that proof. Even better, try to prove it yourself.

Then I want you to try to generalise it to thinking about when there exists a solution x for ax = c mod b

[glacial flame]

does it use proof by contradiction where we assume gcd is > 1?

[brave rock]

You'll forgive me for not simply giving you the answer

[glacial flame]

which means we can pull a factor out

[brave rock]

Contradiction is unhelpful here.

To prove the other way, use Bézout's lemma.

[glacial flame]

is that the one where ax + by = GCD(a,b)

[spring elk]

why is that not the case? I mean why can be choose B to be whatever we like for onto but not one to one? we don't know what subset B is going to be so shouldn't it be working for all cases for it to be determined true?

[brave rock]

Check the definition of what it means to be onto and one-to-one.

I'm going to use the terms surjective and injective because I dislike the previous terminology; forgive me for that

You will see that one says "for all x, there exists y such that..."

and the other says "for all x and y ..."

The point is that in proving the first of the two, because there is a "for exists", this allows us to choose anything we like

But you cannot simply choose anything you like when proving something of the form "for all"

Review the definitions and this should become clear to you.

[spring elk]

ah alright this does make sense then. The definitions i was reading didn't phrase it that way

[viral hawk]

Could someone help with this one question, I keep getting zero

[glacial flame]

I feel like I'm doing something wrong

ax === 1 (mod b)
b | ax - 1
bc = ax - 1

ax + by = GCD(a, b)
ax + by = c, where c = GCD(a, b)
ax = c - by

bc = c - by - 1
bc + by = c - 1
b(c + y) = c - 1
b | c - 1

[brave rock]

Use words. I have no idea what steps you're taking

[glacial flame]

okay one second

[brave rock]

which way are you trying to prove this? This isn't clear.

Like this bit:

bc = ax - 1

ax + by = GCD(a, b)
No, this doesn't follow

What is y? You haven't said anything so y has no meaning

[glacial flame]

then I'm not entirely sure when to use bezout's

[brave rock]

OK that's nice. Review the proof you were given first.

Then we'll discuss where bézout comes in

[glacial flame]

the proof for inverse only existing for coprime?

or the proof for bezouts

[brave rock]

I don't expect you to prove Bézout's lemma; that would be a mostly pointless exercise here.

I want you to review the proof of this:

there exists a solution x for ax = 1 mod b if and only if gcd(a,b) = 1

[glacial flame]

ah okay

ohhhh I see what I did wrong

I was just taking random variables and assuming since they had the same name it meant the same thing 🤦‍♂️

okay I'm going to stop looking at the proof and try to do the rest myself

[brave rock]

Nice, glad you spotted that mistake

I'll be interested in seeing your solution of course

[glacial flame]

ax === 1 (mod b) [Given]
b | ax - 1 [Defintion of modulo]
bc = ax - 1, c in Z [Definition of divisibility]
1 = ax - bc [Math]

let d = GCD(a, b)
a = dl, l in Z
b = dm, m in Z

1 = dlx - dmc [Substitution]
1 = d(lx - mc) [Math]
d | 1 [Definition of Divisibility]
|d| <= |1| ^ d != 0
therefore, d = 1
GCD(a, b) = 1

This is what I came up with

I didn't use bezouts so maybe I did something wrong?

[brave rock]

Good job, this does indeed show one direction of the implication

Now show the other

[glacial flame]

oh crap

so we assumed x exists and got d = 1, so now I start with d = 1 and derive x exists?

[brave rock]

Yes

[glacial flame]

I only remember the proof we learned being a one-way proof 👀 does that mean it's wrong?

maybe he just glossed over it quickly

[brave rock]

Well it's just a proof of half of the statement I asked you to prove

It is incomplete in that way

[glacial flame]

By the way, what is it that I did in my proof which made it only a valid statement one way; did I use a rule of inference anywhere?

[brave rock]

I don't know how to answer that exactly; it's simply only a proof of one direction

If you just try to reverse it you will fail

You need additional information

[glacial flame]

then how are we supposed to know when we need to prove both ways on something like a test?

I don't think the prof tells us that

[brave rock]

I asked you to prove if and only if

That means both ways.

[glacial flame]

I thought if you don't use rules of inference then you are using laws of logic that allow every step you do to go both ways, unless one of the definitions I used is only one way?

[brave rock]

No

That's just not true

[glacial flame]

what have I been learning then 😦

[brave rock]

Okay I don't know but I did ask you to work something out

can we focus on that?

[glacial flame]

yes I'm working on it as we speak

[brave rock]

great

[glacial flame]

not 100% confident but

GCD(a, b) = 1 [Given; derive ax === 1 (mod b)]
ax + by = GCD(a, b), x and y in Z [Bezout's Lemma]
ax + by = 1 [Substitution]
by = 1 - ax [Math]
b | 1 - ax [Definition of Divisibility]
ax === 1 (mod b) [Definition of Modulo]

[brave rock]

Yup

very nice

Simple isn't it?

OK

[glacial flame]

yea that's why I wasn't confident, felt too simple

[brave rock]

Now that you're equipped with this

[glacial flame]

do it with a c both ways?

[brave rock]

Try and discover a similar condition for when ax = c mod b has an inverse solution

This will be more complicated

best of luck

[glacial flame]

I'll see you on the other side 🥲

[brave rock]

Or sorry I said inverse

I meant solution

Look to the examples you calculated as inspiration

[glacial flame]

will do

[brave rock]

8x = 4 mod 16 doesn't have a solution
8x = 8 mod 16 does
8x = 4 mod 12 does
8x = 2 mod 12 doesn't

[glacial flame]

at a glance it feels like it has to do with 8/GCD(a,c,m) being corpime with m/GCD(a,c,m)

but that's only when it behaves nicely with being able to make c go to 1

ax === c (mod b) [Given]
b | ax - c [Definition of Modulo]
bd = ax - c [Definition of Divisibility]

let g = GCD(a, b)
a = gl, l in Z
b = gm, m in Z

gmd = glx - c [Substitution]
g(lx - md) = c [Math]
g | c [Definition of Divisibility]
GCD(a, b) | c [Substitution]

[brave rock]

I like where this is going

So you've proved that if there is a solution x, then GCD(a, b) | c

That's a nice fact

[brave rock]

Seems to work for all of these too

[glacial flame]

do I now need to start with that fact and go the other way?

[brave rock]

Wanna try?

[glacial flame]

sure 🙃

Either I did something wrong, or there seems to be an extra requirement:

GCD(a,b) | c [Given; derive ax === c (mod b)]

ax + by = GCD(a,b) [Bezout's Lemma]
ax + by | c [Substitution]
(ax + by)d = c [Definition of Divisibility]
dax + dby = c [Math]
bdy = c - dax [Math]
b | c - dax [Definition of Divisibility]
dax === c (mod b) [Definition of Modulo]

On the one hand, it feels like d could become a part of x, but on the other that feels like it might be some weird contradictory behavior

[brave rock]

Yeah so you're doing that thing again where you assume things are the same because of the name

we require to show that there exists an x such that ax = c mod b

then you say x is the thing in bézout's lemma, but you don't need to assume that's true

you can choose the solution later

Fwiw, you've almost found it, you just need to point to the solution and say "them's it!"

Take a look at the last bit

[glacial flame]

so dx can be grouped?

[brave rock]

yeah exactly

And that is a solution

[glacial flame]

okay that's what I was saying here

[brave rock]

Well no it's different because the 'become part of x' thing is not right

but I think you had the right broad idea

anyway

Well done; you have solved the problem you posted here pretty much 100% by yourself, just with a small push

A solution to 8x = 4 mod 16 doesn't exist because gcd(8,16) = 8 > 4

[glacial flame]

so basically the GCD(a,b) | c

[brave rock]

Yeah, that's equivalent to there being a solution to ax = c mod b

I didn't tell you what the criterion was gonna be either, you discovered that on your own

So very well done indeed

[glacial flame]

very interesting, thanks!

And I'm just curious, would saying this be okay, or is it better to go back and change the variable names so that x is available for the end?

let y = dx
ay === c (mod b) [Substitution]
(this is what we wanted to derive; x was arb, y is arb, so it is the same form, just with different variable names)

[brave rock]

That's perfectly valid

[glacial flame]

😄

[brave rock]

I wouldn't say that x is 'arbitrary' but the name x is arbitrary, yes

[glacial flame]

I'll be honest, I learned more from this than I did from the lectures O_o

the whole class is lost

[brave rock]

One does tend to do that when doing math instead of just listening to math

[glacial flame]

It sounds like exam 1 grades were even lower than usual semesters, probably around 30-40%

Back to what we were saying about two-way proofs + using laws of logic, does that mean for something like a ^ b v b ^ c === b ^ (a v c) (just pretend this example has multiple steps using laws of logic), we would have to go both ways (even though I was taught otherwise)?

[brave rock]

If the laws of logic you used worked both ways this would be fine

They usually do not.

I mean on a practical level, if they did then everything would be equivalent, like

All men are mortal, socrates is a man, therefore socrates is mortal

It's not true that socrates being mortal implies that all men are mortal, you can't infer that from that fact alone

[glacial flame]

Oh wait I think I see the problem, what we are finding is an implication in the first place

we are assuming the existence of x

[brave rock]

That is definitely an important part of it, yes.

One reason why that proof cannot be reversed immediately.

[glacial flame]

I see. One last part of my question: how do we find x for both the inverse and the general form that had c?

[brave rock]

Do you know how we prove Bézout's lemma?

You can just say no if you don't.

[glacial flame]

no

[brave rock]

OK

[glacial flame]

does it have to do with Extendend Euclid's Alg?

[brave rock]

Yes

Great

Yeah

[glacial flame]

I remember him showing the EEA but was 100% lost

he just showed an example, didn't really explain it well

[brave rock]

Note here that if you have calculated x and y, you can calculate the solution dx

that's how we do it.

So we just use the extended Euclidean algorithm to calculate it.

OK well you should practice the EEA in your own time.

[glacial flame]

when did we calculate x and y? Or is that also part of EEA?

[brave rock]

The EEA gives you x and y.