discrete-math

[twilit pendant]

the exam is extremely hard

i need more than 80

the degree is from 100

i think it's B+ i don't really now but i need more than 80

[pale monolith]

Well you should get started

[twilit pendant]

4 hours a day ?

[pale monolith]

No reason not to try

[twilit pendant]

possible

?

[pale monolith]

I can't determine that

[twilit pendant]

i have another 3 courses that's why it's only 4

[pale monolith]

You are the one person best suited in the world to determine whether you will be able to pass

[twilit pendant]

i'm slow to understand

[pale monolith]

Even more reason to get started rather than asking about whether it's possible on discord

[twilit pendant]

i need someone that had the same problem and passed because i feel i'm not going to pass

i'm depressed

[pale monolith]

then you should ask people who have taken the same course

highly unlikely you will find those people here

[twilit pendant]

did u had a similar situation ?

[pale monolith]

No

[twilit pendant]

😦

[pale monolith]

Well i have procrastinated before

But never to the degree i needed to learn an entire course in two weeks

[twilit pendant]

also money is a big problem i don't have enough to hire a private teacher

[coral parcel]

It's safe to say that most people in an educational situation where they need to take that course wouldn't be able to internalize all of it by self-study in 18 days -- there's a reason why the course itself runs over a longer period than that.
On the other hand, surely some would. Not many but some.

[twilit pendant]

we learn all that stuff in 12 weeks

i'm going to fail

[brave rock]

You should get in contact with pastoral support at your institution. They likely have councillors or similar support staff available.

If you need an interruption to your studies that can also probably be arranged.

There's really no point in just continuing in the same way if you don't think you're going to succeed, so tell someone who can actually help instead of this discord server.

This kind of thing happens quite often, they will know what to do if you get in contact. You're far from the first person to struggle managing their time at university.

[twilit pendant]

https://tenor.com/view/crycat-crying-cat-crying-cat-thumbs-up-thumbs-up-ok-gif-22851318

i will talk with them

[brave rock]

I'm glad to hear that

[wet glen]

Not sure if I'm on the right track for part d.

[past rivet]

Unfortunately no

You’ve assumed what you want to prove

you need to show, starting from n^2 -2n + 7 being even (and other true statements), that n is odd

[wet glen]

So I need to prove n= n^2-2n+7?

[past rivet]

Nope!

You need to show that if n is an integer, and n^2 - 2n + 7 is even, then n is odd

You can think of it as - you start with a proof that n^2 - 2n + 7 is even, and you need to turn this into a proof that n is odd

[wet glen]

Got it. Thank you

[clear radish]

hello everyone, i need help with this question cuz i just cant figure out the logic behind it. i keep getting it wrong

[errant bear]

try a smaller example, how arrangements of ABCCD have the subword DAC

[uncut raptor]

Let n, r, s, i ∈ N. Give a combinatorial proof to show that the number of pairs (A, B)
with A ⊆ Nn, B ⊆ Nn, |A| = r, |B| = s and |A ∩ B| = i equals

anyone can help me

[uncut raptor]

3! right?

oh wait 3! / 2!

since there are 2 C

[silk harbor]

how can i calculate the number of arrangements of 10 different balls in 7 different cells such that the first 3 cells have a combined number of at least 8 balls?

[solar marsh]

You can choose (i) elements from the (n) ((C)), then (r-i) from the remaining (n-i) ((D)), and finally (s-i) from the remaining (n-r) ((E)). Then (A = C \cup D) and (B = C \cup E).

[vital dew]

Kevin

[novel mauve]

I want to prove that I can fully specify a vector in an infinite dimensional vector space by only determining what is equivalent to a finite tuple of integers:

-Prove that though the vector is expressible in the infinite vector space, it must be part of a subspace of that infinite space that is finite
-Pick a convenient basis for the infinite space

Can the two lines above be taken for free/on the axiom of choice? (Assume line one is a correct proof)

-Choose a finite number of elements from the basis (Can be done by specifying integers)
-Specify the coefficents of the finite number of basis elements (Can be done by specifying integers, in my case the vector space is not on R any variant of)

-.... Importantly I claim to have shown the vector of concern can be described by a finite sized tuple of integers, despite it inhabiting an infinite dimensional space. Does that make sense? Or did I cheat somewhere, in the first two lines?

This lets me prove a further result is the reason I care.

[coral parcel]

Hmm, every single vector is in the one-dimensional subspace generated by itself ...

[little prism]

even ignoring that, you can write it as a tuple of integers after you fixed the basis I suppose. but how are you specifying what those basis vectors are in the first place. thats the same problem again

sure they exist but that doesnt tell you what they are

[coral parcel]

I think the overall goal of "fully specify a vector in an infinite vector space" as if it's a list of coordinates is essentially misguided. Using the axiom of choice we can prove that every vector space has a basis such that every vector is uniquely given by a finite-support coefficient function. But these bases are completely impossible to work with other than for theoretical arguments.
If you want to actually compute in the vector space, the only generally useful way is to go to the definition of that particular vector space to see what its elements are and how the vector space operations are defined for it.

By the way, most infinite-dimensional vector spaces are so large that a basis needs uncountably many elements, in which case you cannot point to particular basis elements by giving it an integer index.
This is true even for "innocent-looking" examples such as the space of all countably-infinite sequences of elements of a finite field.

[novel mauve]

yeah someone said that and I think I need to address

[novel mauve]

the case of a finite subspace? Then it is appropriate to index with an integer?

luckily I dont actually want to compute in this space

[coral parcel]

If whatever you need to do happens to fit within a finite-dimensional subspace, then sure.

[uncut raptor]

ye i realised it too but thank you

I also have another question when defining a function take this as example, u see how they write domain -> codomain and then below u write domain in concrete notation -> codomain concrete notation

instead of writing the x -> sqrt(x) below it

can u write it right side of it?

so like domain -> codomain : concrete domain -> concrete codomain

[uncut raptor]

can u by any chance help me with this question too

[fossil mural]

i mean notation is just a human thing, so yeah sure do whatever you want

as long as it's clear and unambiguous

[uncut raptor]

but will this be clear if I said R - > R : x -> sqrt(x)

because I always see they write it below R -> R

[fossil mural]

yeah that's fine, it's pretty easy to work out what it means

[uncut raptor]

I also sometimes see R -> R : f(x) = sqrt(x)

but I guess there are just multiple ways to do it

[fossil mural]

i mean generally it's good to be consistent with notation, so it makes sense that they just picked one way of doing it and then kept going with that

[uncut raptor]

ye that makes sense

[uncut raptor]

will u be here for long I know u are quite smart, and I am doing combinatorics proof now but I am pretty sure I will run into diffuclt questions

[fossil mural]

i have no idea how long i'm going to be here (i might end up going to sleep) but probably if i'm not here there will be other people here

[uncut raptor]

ah I see, ye it's late too for me

I guess I will ask it tmmrw then if I run into diffucult question

[uncut raptor]

are u asleep already, I actually do have a question

[fossil mural]

i am still awake

[uncut raptor]

can u by any chance help me with with the function defining

why is the second part x

because y is element of k+1 elements

[fossil mural]

probably to make the rest of whatever they're going to do with the function work

[uncut raptor]

this is the rest

but

the x doesn't makes sense to me

[fossil mural]

...is there a specific problem you have with it?

[uncut raptor]

okay well u have to give a 1 to 1 relation from set X to Y

[fossil mural]

yeah ok it looks like the reason they put it there is so that you can then infer what x was just from f(x), so that f^-1 exists

[uncut raptor]

so u gotta write y in terms of A and x

[fossil mural]

...what's "y"

[uncut raptor]

uhh what does that mean actually

this part

it says y element of B

[fossil mural]

so for instance $({1, 2, 3}, 1)$ is an element of $Y$, because $1 \in {1, 2, 3}$

[vital dew]

bee [it/its]

[fossil mural]

but $({1, 2, 3}, 4)$ isn't, because $4 \not\in {1, 2, 3}$

[vital dew]

bee [it/its]

[uncut raptor]

right

uh

[fossil mural]

(and to be clear the choice of variable letters doesn't matter, if they had written $Y = {(A, x) : A \subseteq N_n, |A| = k + 1, x \in A}$ then that's the exact same set)

[uncut raptor]

but I feel like it;'s hard to see

[vital dew]

bee [it/its]

[uncut raptor]

ye but A and x were already claimed

for set X

but uhm

so A u {x} is logical

since Au{x} has cardinality k+1 which matches with B

and is also subset of N_n

but the second part

x matches with y?

[fossil mural]

yep

because $x \in A \cup {x}$

[uncut raptor]

but y is element of D

[vital dew]

bee [it/its]

[uncut raptor]

uhh

let me think

why is that?

because x is element of N_n \ A tho

[fossil mural]

well $x \in {x}$

[vital dew]

bee [it/its]

[uncut raptor]

it says N_n \ A

[fossil mural]

yes, so x isn't in A

but it is in {x}

[uncut raptor]

but

[fossil mural]

so it is in $A \cup {x}$

[vital dew]

bee [it/its]

[uncut raptor]

oohhhh

[fossil mural]

that's the union, so it contains anything that's in either of the sets (or both, but that doesn't happen in this particular case)

[uncut raptor]

u can just say

wait

[uncut raptor]

but is it allowed to say this?

because he is only element of {x}

but not part of A

[fossil mural]

well that's how $\cup$ works

[vital dew]

bee [it/its]

[fossil mural]

${1} \cup {2} = {1, 2}$ for instance

[vital dew]

bee [it/its]

[fossil mural]

$1 \in {1} \cup {2}$ because $1 \in {1}$, and $2 \in {1} \cup {2}$ because $2 \in {2}$

[vital dew]

bee [it/its]

[fossil mural]

if we wanted to require that it's in both, then that's $\cap$, the intersection

[vital dew]

bee [it/its]

[fossil mural]

and ${1} \cap {2} = \varnothing$ because no $x$ satisfies $x \in {1}$ \textit{and} $x \in {2}$

[vital dew]

bee [it/its]

[uncut raptor]

but if u said x is element of {1} u {2}

does it mean that x can be 1 or 2?

[fossil mural]

yep

$x \in A \cup B$ iff $x \in A$ or $x \in B$

[vital dew]

bee [it/its]

[fossil mural]

that's the definition of union

[uncut raptor]

but in our case x could only be element of{x}

but he could be all the elements in A too?

say A = {1,2,3}

and x = 4

then x is element of {1,2,3,4}?

[fossil mural]

yep

[uncut raptor]

so x could be 1,2 ,3 or 4?

[fossil mural]

well it's one of those

[uncut raptor]

oh

[fossil mural]

you said that it's 4

but 4 is one of 1, 2, 3, 4

[uncut raptor]

ahhh

so it doesn't have to be all?

ahh I can just expand the set

with no problem

I can just say x is element of{x} u C

where C is just a random set

I think I got it right?

I gotta read back to my question iI forgot it

[fossil mural]

i didn't understand all of what you said but it sounds like you've got roughly the right idea?

[uncut raptor]

uhh so

I can just say x is element of {x} u C
where C is a random set doesn't matter how big or how small

since x is always contained in {x}

[fossil mural]

yes

[uncut raptor]

ahhh I see now why they chose x

it's actually the only option too

thank you alot

u just have widen my vision by alot

[uncut raptor]

is this true?

also these combinatorics proof, are u able to imagine how the sets relate to each other 1 by 1 or is it more define the sets and try to find a way to connect them. Like do u visualize it too?

I think u went to sleep gn if u did

[uncut raptor]

also how do u laern to type latex so fast, it seems realy covenient when trying to write mathemetical notation

it's way mroe readable

the reason y is being chosen is because x is element of N_n \ A. that means that y should be element of N_n \ (D\y) and that is true

[agile magnet]

the more you use it the more you internalize all the commands and such

[uncut raptor]

But where did u start learning it

[agile magnet]

Overleaf has some nice tutorials online

and then basically I started doing all my math HW in LaTeX because my handwriting sucks

and at first it took me a long time since I had to keep googling stuff

but you do it more and more and more and eventually you have to google less and less stuff

[queen mist]

So I have question about Berge theorem, does it work on unconnected graphs? As I am looking at it, if our graph is made out of 3 parts with branches 12 34 56, we don't have any augmenting path, but how can we prove that 12 34 56 is max matching and 34 56 isn't max matching

[novel mauve]

Thanks for the help unsurprisingly some of this was a red herring, although the final answer does use infinite matrices

[nocturne coral]

the approach i'm thinking is make a TM for
$N_0 = 2N_1$
and then take its complement.
But how to take the complement of TM?
like in DFA/NFA we just switch the final and non final states

[vital dew]

Pogram

[ashen bane]

https://math.stackexchange.com/questions/3949970/the-union-of-two-simple-planar-graph-have-chromatic-number-leq-12

I think its even 11 chromatic

ainit?

[weary tiger]

How many ways can a person visit 3 cities, each of them 4 times such that he starts and ends at different cities?]

[fluid ibex]

how is this discrete math?

[weary tiger]

combinatorics could be discrete math?

[fluid ibex]

hm

[weary tiger]

🤨

[fluid ibex]

aight ok

[weary tiger]

anyway reposting but can someone help me with this:

How many ways can a person visit 3 cities, each of them 4 times such that he starts and ends at different cities?]

first make a injection i guess then what?

[agile magnet]

call the cities x, y, z

does this count? x x x x y y y y z z z z?

if it does then I think this is easy

if it doesn't I'll have to think some more

[gusty swallow]

paths on a cycle graph?

[agile magnet]

Are you saying this in relation to the question above or are you asking a different question? In either case can you make yourself clearer?

[gusty swallow]

take your cities x, y, z and put edges between them {x,y},{x,z}, {y,z} creating your 3-cycle graph (or complete graph), then you're looking for paths on the graph that visit each vertex 4 times and start and stop at different cities.

it's like a hamiltonian path with repetition.

[wet glen]

Am I on the right track?

[agile magnet]

you're using x for 2 different things making this hard to read, also 5j - 1 is not always odd (consider j = 5) also I don't get how k = 5x - 1 implies x^2 + 5x - 1 is odd

also idk what you mean by "x is odd since x^2 + 5x - 1 is odd"

since for x = 2 this is false (in fact this statement you wrote is false for all even x)

Can you write what it means for an integer to be odd, the formal definition. Lets start there perhaps. And then tell me if you've heard of the term "proof by cases" before.

[wet glen]

okay so I need to redo the statement. since x^2 is even

[agile magnet]

what do you mean "x^2 is even"

since 1^2 is odd

can you please answer my questions

[wet glen]

okay so I was thinking since x^2= 2k therefore that would be even. that's what I was thinking at least.

my apologies, your questions. what I meant by" x is odd since x^2 + 5x -1". I was going off the fact that J= x^2 +5x which would be odd
and k being odd too since k= 5x-1. but I think that's a mistake now that I think about it since there has to be some factorization to go back to the original x^2+5x-1

[agile magnet]

x^2 + 5x is not always odd, take x = 2. 5x - 1 is not always odd, take x = 1

[agile magnet]

ok can you answer these please

[terse wyvern]

take the RHS modulo 2

[agile magnet]

At this stage idk if they've learned modular arithmetic

[terse wyvern]

oh

[agile magnet]

and besides more basic definitions need to be fixed

[terse wyvern]

like integers?

[agile magnet]

yea applying those basic definitions, making assumptions without justifying them, and approaching the proof in a better manner (which is what I want to point them towards if they answer the questions I've told them to answer)

[wet glen]

noted

[agile magnet]

so can u answer my questions

[agile magnet]

these ones

otherwise I'll just stop trying to help since there's no point

[wet glen]

odd integar is x=2k+1

[agile magnet]

what is k?

a natural number, an integer, a real number, a complex number, something else?

[wet glen]

k is a rational number

[agile magnet]

no, k is an integer. If k could be a rational number then something like 2*(1/3) + 1 = 5/3 would be odd, which makes no sense

so x is odd if x = 2k + 1 for some integer k, and x is even if x = 2k for some integer k.

Ok next up, do you know what "proof by cases is"?

[wet glen]

is that proof by exhaustion where you prove with the easiest element?

[agile magnet]

What do you mean easiest element?

Can you elaborate on that?

[wet glen]

well by element I mean like x or y or integer... depending on the problem and what you're trying to prove

[agile magnet]

What does easiest mean?

[wet glen]

less complicated to prove.

[agile magnet]

Ehhh that's very vague.

Ok here's the idea. There are two types of integers: even and odd

Suppose x is even, proof the claim in that case

Then suppose x is odd, prove the claim in that case

Those two possibilities cover all cases so you've proven the claim to be true for every integer

[wet glen]

okay understood.

[agile magnet]

So try that, should be a straightforward computation

If you get stuck and/or want me to check your work, ping me here

[wet glen]

thank you for the clarification

[weary tiger]

yes i think probably does

that's what i did with the bijection bit but not sure how to continue

[weary tiger]

hmm could you elaborate? never done any graph theory or whatever required to understand that

[agile magnet]

Ok if it does

Suppose you start at x and end at z

Then do you agree that you can arrange the remaining 10 letters in any order to generate a valid trip?

Then compute all such orderings

This will tell you the number of possible trips starting at x and ending at z

From there getting the total number of all possible trips should be easy

[vestal bronze]

it shouldn't count

[weary tiger]

how 10?

if he starts at x then that leaves 8 (4y's and 4 z's) for him to end at right?

[small cedar]

Can anyone help me in box plot????

Statistics

[agile magnet]

?

Start at x end at z

[weary tiger]

yeah but isn't that 8?

there's 4 y's and 4 z's

[agile magnet]

Leaves 3 x's 3 z's 4 y's

You wanna visit each city 10 times

@small cedar #❓how-to-get-help

This channel is not for stats

[small cedar]

No access

[weary tiger]

#probability-statistics

[agile magnet]

Click the channel explorer everyone has access

[small cedar]

Thanks

[agile magnet]

Anyways @weary tiger is this not correct

[weary tiger]

right but if we start at x we want to end at y or z right?

so we fix the first and last letter?

and then permute the ones in between?

[agile magnet]

I'm fixing the start and end

Yea

[weary tiger]

so you're fixing the start and end at x?

[agile magnet]

And count all permutations

No

[weary tiger]

and then total - that?

[agile magnet]

You need to start and end at different cities

[weary tiger]

oh so you want to do casework? start and end at (x,y) and start and end at (x,z)

and start and end at (y,z)

[agile magnet]

Yea yea

Because counting the possible permutations of the 10 in the middle is easy once you fix start and end

[weary tiger]

but wait why can't i start and end at x?

[agile magnet]

By symmetry you're basically done with 99% of the work once you figure out once case

[weary tiger]

and then subtract from the total

[agile magnet]

Read your message bruh you said start and end at different cities

[weary tiger]

because total would have all permutations and then start and end at x would remove all words that well start and end with x

[weary tiger]

i know 😭 but check what i wrote

[agile magnet]

I mean you can but like

[weary tiger]

total permutation - start/end at x = start end at (yz) OR start end at (xy) OR start end at (xz)

no?

[agile magnet]

Yea that's equivalent ig

[weary tiger]

isn't thatmuch faster then

you do only one case work instead of 3

[agile magnet]

Well you need to also subtract start at y end at y

Start at z end at z

[weary tiger]

oh yeah

it's equivalent amt of work then

[agile magnet]

And it's all the same because these are all symmetric cases

You just multiply at the end

Or whatever you get what I mean

It's all symmetric

[weary tiger]

wait so this way is faster cuz it's symmetric in x,y, and z?

find start/end at xx

[agile magnet]

My way is equally fast

[weary tiger]

and multiply by 3

oh yeah

that's also symmetric

[agile magnet]

Multiply by 6 vs 3

[weary tiger]

true okay

[agile magnet]

Who cares

[weary tiger]

6?

oh you mean

reverse as well?

start end at xz and start end at zx

okay sure yeah multiply by 6 okay yeah

[agile magnet]

Yes because I presume those are different

[weary tiger]

and hmm i need help with the ordering too if i'm not dumb

cuz i can't combinatorics but wait

so if i fix x at the start

[agile magnet]

We just care how many ways we arrange the 10 letters right?

In the middle?

[weary tiger]

i thought constraints kinda matter too?

[agile magnet]

What constraints

[weary tiger]

the start and end letters

[agile magnet]

We fixed those

So we know we start at x

End at z

[weary tiger]

okay so don't we like account for that or no?

[agile magnet]

So we just gotta pick what order we go in the middle

Because we already know start and end

[weary tiger]

like uh 4 ways to choose x at the start?

for the fixing?

[agile magnet]

We fixed it there's 1 way

We know we start at x

We know we end at z

[weary tiger]

yeah but there's 4 x's to choose from?

can i not choose any 4?

[agile magnet]

All that can vary is the 10 middle

x is x bruh

[weary tiger]

😭

[agile magnet]

It's the same city

[weary tiger]

right right

[agile magnet]

I visit NYC today I visit tomorrow it's the same NYC

[weary tiger]

okay okay so for xz:

you permute 3 x's, 3 z's and 4 y's

[agile magnet]

Yea

[weary tiger]

10!/(3! 3! 4!)

okay yeah

[agile magnet]

Perfect

[weary tiger]

and then multiply by 6 cuz it's all symmetric

,w calc 10!/(3! 3! 4!)

[vital dew]

Results provided by WolframAlpha

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

Requested by kizzyyyyy

[agile magnet]

I sleep now

[weary tiger]

is it that many?

i think it's like

less than 1000

[agile magnet]

idk man I trust the calculator

[weary tiger]

😭

no no

i mean

i think the answer is like less than 1000

[agile magnet]

Yes this is right for all possibilities starting at x and ending at z

[weary tiger]

multiplying by 6 makes it even bigger and iirc the answer is 800 something

[agile magnet]

Then you gotta multiply by 6

[weary tiger]

tbh not sure if that's right

[weary tiger]

right makes sense yeah

[agile magnet]

Ok then you omitted some info if you know the right answer is much smaller

Because as you stated the question we have the right answer

[weary tiger]

wait so i googled it

and found this

https://math.stackexchange.com/questions/4147277/a-bus-has-to-visit-three-cities-each-of-them-four-times-the-number-of-ways-it-c

[agile magnet]

But AAAABBBBCCCC is not a proper one.

[weary tiger]

Why not?

[agile magnet]

So what you told me above when I clarified was wrong

[weary tiger]

Yeah i saw that too

Oh

[agile magnet]

If I don't have all the info how am I supposed to help

[weary tiger]

well i guess i don't understand the question myself sorry

[agile magnet]

Imma sleep now it's 1 AM 💀

[weary tiger]

but yes np

thanks thanks

[uncut raptor]

this should be D right

[uncut raptor]

can anyone hlep me with this

[ivory hedge]

Any one knows how to prove this without induction.

I think i just need to prove this equation but I don’t know how to prove it.

[little prism]

it helps to note that those two numbers are the roots of x^2=x+1

[ivory hedge]

I know this, and I know it called the golden ratio, but yet I don’t know how to deal with it .👨🏾‍🦯

[little prism]

in particular it means that ((1+sqrt5)/2)^2 = ((1+sqrt5)/2)+1

also remember x^(k+1)=x^(k-1)*x^2

[ivory hedge]

I will try this out 👍, thank you

[empty vale]

so, i gotta solve this exercise using the chinese remainder theorem, from the first congrugence equation 15a ≡ 10 (35) i can get 15a = 10 (7) and 15a = 10 (5)

but since 15a ≡ 10 (5) <=> 3.5a ≡ 2.5 (5) i can simplify to 3a ≡ 2 (5)

from the third congrugence equation 18a ≡ 24 (30) i get 18a ≡ 24 (6) and 18a ≡ 24 (5)

where 18a ≡ 24 (5) <=> 18a ≡ 24 (5) <=> 3a ≡ 4 (5) but since i had 3a ≡ 2 (5) this means the system is incompatible right?

since 3a has two different remainders when divided by 5

[fossil mural]

it would, if 3a = 2 mod 5 was actually correct, which it isn't

a = 3 satisfies 15a = 10 mod 35, but not 3a = 2 mod 5

[empty vale]

so, what i did wrong was divide both sides by 5? i thought we could do that

or since we are dividing by 5, it is a special case?

[fossil mural]

yes, the problem is that you divided both sides by zero

you can't do that

5 = 10 mod 5 is true, but 1 = 2 mod 5 is false

15a = 10 mod 5 is the same as 0a = 0 mod 5, so it's actually satisfied by every a

(if you had 15a = 10 mod 25, then it would be valid to conclude 3a = 2 mod 5, but that isn't the situation here)

[ivory hedge]

That’s it right? Thank you🙏

[empty vale]

so, in general one can't divide the congrugence equation by some number on both sides, right?

or is there a special case for when we can do that? like if the number we are dividing by is coprime with the modulo

[fossil mural]

you can divide both sides by any number that has a multiplicative inverse

[empty vale]

because i've definetely seen the professor divide both sides by some number casually

[fossil mural]

because that's the same as just multiplying both sides by the multiplicative inverse

this is basically the same as how it works with real numbers, it wouldn't be valid to take 0*2 = 0*3 and conclude 2 = 3 because there's no 1/0 that you can multiply both sides by

but in the case of mod n, yeah the numbers with multiplicative inverses are the numbers coprime to n

[empty vale]

when you say multiplicative inverse, you mean that for x, 1/x is the inverse?

[fossil mural]

yep

it's a number that when you multiply it by x you get 1

[empty vale]

ah but then i don't worry about that since we are working only with integers

[fossil mural]

well not exactly

[empty vale]

so, i just make sure that i divide both sides by a coprime of mod n

[fossil mural]

even though it's all integers there are multiplicative inverses mod n, they just might not look how you'd expect

for instance the multiplicative inverse of 3 mod 7 is 5

because 3 * 5 = 1 mod 7

and dividing both sides of a mod 7 equation by 3, is "really" just multiplying by 5

[empty vale]

so, for your example, i can do something like 3 * 5 ≡ 1 mod 7 <-> 3 * 5 ≡ -6 mod 7
<-> 3 * 5 ≡ 3 * (-2) mod 7 <-> 5 ≡ -2 mod 7 <-> 5 ≡ 5 mod 7 <-> 0 ≡ 0 mod 7 when it should have been 1 ≡ 1 mod 7 right?

[fossil mural]

well all of those statements are true

i don't really get how you got from "5 = 5 mod 7" to either "0 = 0 mod 7" or "1 = 1 mod 7"

[empty vale]

got some theorem that says if a ≡ b (x) and c ≡ d (x) <-> a-c ≡ b-d (x) so i just subtracted 5 to both sides, still, i don't get it fully the multiplicative inverse thing with congrugence equations, gotta study more

but not i know i can divide with confidence as long as i divide by a coprime of mod n, so, thanks

[fossil mural]

alright yeah that's valid then

it would also have been valid to instead subtract 4 and get 1 = 1 mod 7

basically i don't really get what you were trying to illustrate with that example

[fossil mural]

or to divide by 5 (or multiply by 3) and get 1 = 1 mod 7 that way instead

[empty vale]

well for that example i divided by a number which was not a multiplicative inverse and everything that came out after the division was valid, right?

[fossil mural]

(or to just say "well every number is equal to itself mod anything" and skip all the steps)

[fossil mural]

well you divided by 3, which does have a multiplicative inverse

it's the same as if you multiplied by 5

also dividing by a number that doesn't have a multiplicative inverse doesn't always give the wrong answer, it's just not valid in general
"7 = 56 mod 7, therefore 1 = 8 mod 7 by dividing both sides by 7", dividing both sides by 7 isn't a valid step here but it happens to result in an answer that's true anyway

[empty vale]

hmm, yeah, since the remainder of 7 and 56 divided by 7 should be 0, not 1 like what we get on the other congrugence equation

[fossil mural]

...?

i don't get what you mean

if you take 7 and 56 just considered as integers, and divide them both by 7, you get 1 and 8, where would 0 come from

if you take 7 and 56 considered as integers mod 7, then dividing them by 7 doesn't make any sense, you're dividing zero by zero, there's no reason that the answer "should be 0" when you do that

[little prism]

yes

[empty vale]

yeah you are right, my bad

[indigo marsh]

I think you can divide all three numbers though, eg 7≡56 mod 7 implies 1≡8 mod 1

[pale monolith]

Yes

If you divide the modulo by the gcd of the modulo and the divisor then it will hold

[fluid bluff]

I just finished Chapter 1 of Discrete Mathematics with Applications by Susanna Epp (Edition 5). The book is a bit rough at times but when it slaps it slaps.

At the end of the chapter I was introduced to Graphs and it all clicked. I learned a new way to practically solve basic problems using Graphs.

[ivory hedge]

Dose any one know how to solve this question, in the book it says that S_12=904 that means my answer is wrong.

[fluid bluff]

When you're having fun with Math

[vivid osprey]

The falling factorial is defined to be the number of permutations of length $k$ from an $n$ element set, $$n^{(k)}=n(n-1)\cdots(n-k+1).$$I am faced with the following identity $$ \sum_{k=0}^n (-1)^k k^{(j)} \binom{n}{k} = \sum_{k=j}^n (-1)^k k^{(j)} \binom{n}{k}.$$ Why does the sum start from $k=j$?

[vital dew]

Philip

Philip

[lean epoch]

Hello all! I'm new here and am trying to self study discrete maths. Could anyone suggest a short book for that?

[winter yarrow]

can someone please help me understand this proof?

I don't get why would a eulerian graph imply that the sum is even

[coral parcel]

For purposes of odd or even, we can ignore differences in signs: the sum of phi(v)+phi(w) has the same parity as the sum of |phi(v)-phi(w)|.

But the sum of phi(v)+phi(w) is just the sum of all the labels weighted by the degree of each vertex.

And the degrees are always even in an Eulerian graph.

[winter yarrow]

Rightt I think I get it now

Actually nvm i thought of something that wouldn’t work because of the absolute value

Wait actually I think it would

Can’t we say that the sum phi(v)-phi(w) for all connected vertices v and w would equal 0 thus be even

[coral parcel]

Yeah, if you take care to sum each edge in the direction the Eulerian curcuit uses it in.

[winter yarrow]

Yes exactly

[winter yarrow]

One final question, the labels here are edge labels or vertex labels?

[coral parcel]

Vertex labels, sorry.

[winter yarrow]

Yes nvm it’s my bad I didn’t get it at first

Thank you so much for your answer!

[eternal idol]

My uni's real analysis course uses the injection f to prove the countability of the cartesian product of the natural numbers, but my uni's discrete maths course (and another source I've found) uses the injection g to prove this fact. Are there any reasons real analysis might choose the proof involving f over the proof involving g? Like, are there any particular advantages to using f instead of g to show countability here?

[little prism]

well g only shows injectivity which is a weaker assertion

you then need schröder bernstein to get a bijection and that theorem doesnt really give you an intuitive bijection

or well, at least I've never thought about how the bijective function that theorem constructs looks like in that case

compared to that, f is a quite natural bijection

[ashen bane]

Could somebody please check if my proof is legit?

\documentclass{article}
\usepackage{amsmath, amssymb}

\begin{document}

\section*{Question:}
(5 points) Let (G) be a connected graph and let (P) be a simple path in (G). Prove that there exists a spanning tree (T) of (G) that contains the path (P).

\section*{Answer:}

\subsection*{Proof by Induction on the Number of Cycles in the Graph}

\textbf{Base Case:} \
If there are no cycles in the graph (G), then (G) is already a tree. Since (G) is connected and (P) is a simple path in (G), (P) is already part of the tree. Thus, the base case is proven.

\textbf{Inductive Step:} \
Assume the statement is true for any connected graph with (k-1) cycles. That is, for any connected graph with (k-1) cycles and a simple path (P), there exists a spanning tree containing (P).

Now, let (G) be a connected graph with (k) cycles, and let (P) be any simple path in (G).

\textbf{Case 1: (P) is not part of any cycle:} \
Remove an edge from one of the cycles in (G). Since (G) had (k) cycles, the resulting graph (G') will have (k-1) cycles and will still be connected. By the induction hypothesis, (G') has a spanning tree that contains (P). Since (G') and (G) only differ by one edge, this tree is also a spanning tree of (G).

\textbf{Case 2: (P) is part of a cycle:} \
Select an edge (e) from the cycle that is not part of (P). Removing this edge from (G) will still keep the graph connected (since (e) was part of a cycle), resulting in a new graph (G'') with (k-1) cycles. By the induction hypothesis, (G'') has a spanning tree that includes (P). Again, this tree is a spanning tree of (G).

\textbf{Conclusion:} \
The proof is complete. By induction, for any connected graph (G) and any simple path (P) in (G), there exists a spanning tree of (G) that contains (P).

\end{document}

[vital dew]

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

[ashen bane]

I'd really appreciate it if someone could read it :3

[silent tree]

is this a valid proof?

[past rivet]

You’ve assumed what you want to prove at the start

So no

Although you can tweak this to make a valid proof

Essentially you’ve proved the reverse direction

[silent tree]

hmm

[past rivet]

You’ve proven $\frac 1x \text{ irrational } \implies x \text{ irrational }$

[vital dew]

Pseudonium

[silent tree]

i see so its invalid

because proving a converse doesnt mean that its true

right?

[past rivet]

Yep

You want to prove the other direction

[past rivet]

But this is true

[silent tree]

ahhh dang it

[silent tree]

yeah a contraposition

thanks

[silent tree]

I see

[hollow token]

hey can someone explain how thm 15 implies cor 16 i cant find the contradiction argument

[analog tinsel]

Can anyone provide a useful "strategy" for counting the number of homomorphisms between two non-cyclic groups ?
There is an exercise "How many homomorphisms exist between (Z,+) and (Q,+)?" so the integers and the rational numbers together with the standard addition.
I know the solution and I read something about generator elements but it was mainly about cyclic groups. In the solution they also talk about that it basically all depends on what element from Q the 1 in Z is mapped to. Which seemed quite similar to me.

I am not exactly great at algebra so I would really appreciate it if someone could give some useful insight on how to approach such exercises

[brave rock]

There is no general method that works every time, but yes exactly it is usually helpful to think about generators.

[coral parcel]

Generally, I'd say the standard-ish strategy would be (a) identify a good set of generators for the domain; (b) work out which conditions the elements in the codomain they map to need to satisfy in order to produce a homomorphism; (c) figure out a way to count the combinations of codomain elements that satisfy those conditions.

[brave rock]

As it happens, Z has a very nice property that makes calculating Hom(Z, G) – where G is any group – very straightforward. It may be interesting to you to try and figure out why this is the case.

[analog tinsel]

@brave rock @coral parcel big thanks to both of you for your help!

[analog tinsel]

ok I will think about it thank you !

[analog tinsel]

so do I understand it correctly that for (Z, + ) the set of generators is {0,1}?

[coral parcel]

(Z,+) is generated by the single element 1.

[brave rock]

Hold on tropo

[brave rock]

0 does not generate Z

There is more than one generator of Z, but 0 is not one of them.

1 does indeed generate Z. There is one more single element that generates Z. Can you think of what it is?

[analog tinsel]

Oh I understand, because every element has to be expressable from each generating element , correct ?

[analog tinsel]

it should be -1 right ?

[analog tinsel]

by Hom(Z,G) you mean the number of homomorphisms from Z to G ?

[fossil mural]

the set of homomorphisms from Z to G

[analog tinsel]

oh alright , thanks !

[fossil mural]

it's just that if you know what that set is like, one of the properties that's easy to deduce from that is how many there are

[analog tinsel]

could you give me a hint on what that property is ? Is it that it is abelian ? Or that it has a single generating element ?
Whats confusing me rn is that there could also be groups G where there is no homomorphism from Z to G, right ?

but that should not be a problem

[past rivet]

So, Hom(Z, G) is only being considered as a set here

I don’t think it has a group structure

At least not in general

Ok maybe it does actually but

We’re considering it as a set for now

[analog tinsel]

but the point was that Z has a very nice property ?

[past rivet]

Yes

[analog tinsel]

I dont understand what you said sorry

[past rivet]

I think I misunderstood sorry

[analog tinsel]

oh ok

[past rivet]

It is a property of Z which is nice

I thought you were saying Hom(Z, G) was abelian

[analog tinsel]

no no

[past rivet]

Ok cool

I think - think about how one specifies a group hom Z -> G

[analog tinsel]

well ok , so the neutral element 0 has to go to the neutral element of G , certainly

[past rivet]

Yep

[analog tinsel]

then the rest depends on where 1 is sent

[past rivet]

In what way?

So explicitly, suppose we have $\phi : \mathbb{Z} \to G$ a group homomorphism

[coral parcel]

I think what Boytjie was after is that (a) it has a single generating element, plus (b) it is "freely generated" by that single element.

[vital dew]

Pseudonium

[past rivet]

How exactly does $\phi$ depend on $\phi(1)$?

[vital dew]

Pseudonium

[analog tinsel]

its because $\phi(n) = \phi (\sum_{i=1}^{n} 1) = \sum_{i=1}^{n} \phi(1) = n \cdot \phi(1)$

[vital dew]

barış

[analog tinsel]

for all n in Z

[analog tinsel]

what do you mean by "freely generated" ?

[coral parcel]

This has the effect that there's a bijection between "homomorphisms Z->G" and "elements of G", which is definitely a nice property.

[past rivet]

Right, I would denote that as $\phi(n) = \phi(1)^n$

[vital dew]

Pseudonium

[past rivet]

aaa spoilers

[analog tinsel]

why to the power of n ?

[past rivet]

Just cause usually the group operation is thought of as multiplication

Addition is reserved for abelian groups

But its equivalent to what you wrote really

[analog tinsel]

oh of course, such a bijection is nice for sure

[analog tinsel]

wdym by "reversed" ?

[past rivet]

So how do you go the other way? Given an element of G, how can you define a group hom Z -> G?

[analog tinsel]

oh

reserved

sorry

[coral parcel]

There's a technical definition for "freely generated", but I'm not sure I have a way to describe it that makes natural sense at the abstraction level of this conversation.

[past rivet]

We’ve seen that given a group hom $\phi : \mathbb{Z} \to G$, we can get an element of G by evaluating $\phi(1)$

[vital dew]

Pseudonium

[past rivet]

Now we want to reverse this process

[analog tinsel]

I am not sure why ?

[past rivet]

That’s what bijection means, remember

[analog tinsel]

oh right sorry my bad

we want to find the bijection between Hom(Z,G) and G, right ?

[past rivet]

Yep

[analog tinsel]

okk give me a moment to think

[analog tinsel]

I understand, thank you

but actually

the homomorphism is not complete, is it ?

I said n in Z

but it should be n in N

[past rivet]

Wait why…?

[analog tinsel]

dont we have to consider the case were n < 0 seperately ?

[coral parcel]

In order for the recipe to work, we need the convention that g^(-n) means the inverse element of g^n.

[analog tinsel]

the sum wouldnt really work

?

[past rivet]

Yes that’s true

[fossil mural]

you're correct that your earlier argument only works for n in N, because for instance ``$\sum_{i=1}^{-5} 1$'' doesn't make much sense, but that isn't a problem with the homomorphism itself, just with your argument

[vital dew]

bee [it/its]

[analog tinsel]

I see

okk then give me a moment to think about the other direction of the bijection

[coral parcel]

(This is already built into the notation g^-1 for the inverse element in the first place).

[analog tinsel]

makes sense

[coral parcel]

As far as I can see in the conversation we already have both directions of the correspondence -- if anything is missing that'll just be lining them up nicely and putting labels on them, but all the necessary things themselves have been said already,

[analog tinsel]

so it should be that given a g in G we say phi(1) = g , then this determines the homomorphism because now for any n in Z we have phi(n) = n \cdot g , right ?

[past rivet]

Yes that’s the idea

[analog tinsel]

cool

[past rivet]

This is sometimes called the “universal property of Z”

[analog tinsel]

interesting

[past rivet]

It tells you how Z relates to all other groups G in the “universe”

Because it describes what Hom(Z, G) is

[coral parcel]

Or if you want the completely abstract nonsense,

[past rivet]

It’s just in bijection with the elements of G

[coral parcel]

"Z represents the forgetful functor".

[past rivet]

Sure yeah

[analog tinsel]

I'll take the "universe" description

lmao

[past rivet]

Would you like to hear about other free groups?

[analog tinsel]

thanks to you all for helping me out so much

[analog tinsel]

I am still not sure what a free group is but sure

I'd like to

[past rivet]

So unfortunately

It’ll be a little difficult to tell you what a free group is

But I can do something else

[analog tinsel]

I read about free monoid

[past rivet]

I can tell you what a free group “does” first

[brave rock]

Well the free group is just like the free monoid except it's a group

[past rivet]

I.e. the universal property of a free group

How it relates to other groups in the universe

So, suppose we have a set with n elements (for now, n is finite)

There’s a way to define a free group on n elements, F_n

And I can tell you what Hom(F_n, G) bijects with

[analog tinsel]

unfortunately I really only read about it, I didnt really spent time thinking bout it

[past rivet]

Namely, homomorphisms F_n -> G correspond to elements of G^n

So you pick n elements from G, in order

And you get a homomorphism F_n -> G

Conversely, every homomorphism F_n -> G uniquely picks out n elements from G, in order

So e.g. Z works as F_1

Because homomorphisms Z -> G biject with elements of G^1

Does that make sense?

[analog tinsel]

I understnad yes

[past rivet]

I haven’t showed that such an F_n actually exists

We know F_1 exists though, cause Z works

[past rivet]

So I haven’t told you what F_n “is”

I’ve just told you what it “does”, how to use it, how it relates to other groups

By telling you its universal property

[analog tinsel]

ohh

I think I see the relation somehow

[past rivet]

And indeed, you’d have to separately prove that such an F_n exists

[analog tinsel]

in the definition of a free monoid is says that a Monoid M = (N, o) is is called free over a proper subset A of N if every element n in N can be uniquely represented as a product of k elements a1 o a2 o ... o ak from A

[analog tinsel]

yes of course

[past rivet]

Would you like to hear about the general definition of free group, on a set X?

[analog tinsel]

yes

[past rivet]

Again, it’s a little tricky to say what it “is”

I mean there is an explicit construction

But proving it’s a group is not trivial

[coral parcel]

Another (quite handwavy but perhaps more vivid) to say it could be:

Suppose we have some arbitrary set S. The "free group on S" means a group that (a) contains each element of S, (a1) provides some way to combine those elements in a group operation, (b) has as many different elements other than those elements from S as possible under the condition that (c) every element of the group can be made by starting from elements of S and using the group operations (multiplication, inverses) a finite number of times.
If we make this precise it can be proved that there's exactly one group (up to isomorphism) that satisfies the conditions.

[past rivet]

So instead I’ll just tell you what it “does”

I.e. the universal property

So, given a set X, we make some group F[X]

Such that group homomorphisms F[X] -> G bijectively correspond to elements of G^X

I.e. functions X -> G

Given a group hom, you get a function

And given a function, you get a group hom

Note that elements of G^n can be viewed as functions from {1, 2, .., n} to G

[analog tinsel]

thank you , I think I understand the idea

[past rivet]

Again, I haven’t shown that such a F[X] exists

[analog tinsel]

yes

[past rivet]

It’s something you’d have to separately prove

I’ve only told you what it “does”, rather than what it “is”

[analog tinsel]

thank you very much for telling me so much about it

[past rivet]

No problem! This is the kind of maths I really like

[analog tinsel]

it is very interesting

[past rivet]

Universal properties crop up in lots and lots of different places in math

[analog tinsel]

seems a bit deeper than the "usual" math I know so far

[past rivet]

The general idea is to tell you what something “does”

How it relates to other things, how to use it

Rather than tell you what it “is” through an explicit construction

[analog tinsel]

I think I get the idea

but most likely

some month from now , when I might have read a book on algebra , I will look back on this conversation and realize how little I understood xD

but still you all helped me out a lot, thanks again for that !

[past rivet]

Always fun to see people finding category theory cool

[quasi mantle]

@ashen bane

@ashen bane בשבילך

[ashen bane]

זה מוכר לי

אבל למה צריך מכפלה

אני יכול למצוא את הפונקציה

נלכסן

[quasi mantle]

זה דיסקרטית תוכיח תזהת

[ashen bane]

לא

[foggy sentinel]

Why are math books written so convoluted and not straightforward?

One example :
"Every integer a =/ 0 has the trivial parts +-1 and +-1 since a = (+-1)(+-a). Divisors of a, which are not trivial, are called real divisors. An integer p >= 2, which has only the parts +-1 and +-p, is called a prime number. An integer >=2, which is not a prime number, is called a composite number."

Why can't they just say. It's a prime number if it's only divisible by 1 or itself. Otherwise it's a composite number.

Why in the hell do they write books in such a disgusting way? It makes it sooo hard for me to read, learn and understand what they are talking about. Is this normal practice?

[agile magnet]

Because it introduces more terminology than just prime

It introduces the terms trivial parts and real divisors as well

Also because "it's a prime number if it's only divisible by 1 or itself" is wrong since 2 is divisible by -1 and -2 for example

If you wanted to specify positive divisors then that statement would be correct

[foggy sentinel]

Yes that might be so. But how is someone who just started reading at University meant to be able to read and understand this correctly? It feels so surreal that every and all math books are written like this. It leans more towards being a book of terminology instead of a book for learning.

[agile magnet]

Nonzero chance it's a not the best written book but also reading like this is how you learn

You shouldn't be trying to read this quickly

It's densely written so it will take time to process

[quasi mantle]

@ashen bane

[ashen bane]

תעשה באינדוקציה

[quasi mantle]

לא הצלחתי

[ashen bane]

איך אתה עושה דיסקרטית? לא נגמר הסמסטר אפילו

[quasi mantle]

חבר ביקש עשרה

עזרה

לא שלי

[clever sail]

bluds are speaking cardinality

[gusty dome]

I am trying to show the set of all algebraic numbers is countable. \
Let $A_n:={x \in \mathbb R: \sum_{k=0}^n a_kx^k=0, \text{ for some }a_k \in \mathbb Z}$. My idea is to show that $A_n$ is countable. Notice $\sum_{k=0}^na_kx^k=0$ has atmost $n$ roots for a particular n tuple $(a_0, \cdots , a_n) \in \mathbb Z^{n+1}$. Thus $A_n \sim \mathbb Z^{n+1}$ (not pretty sure about it) and hence is countable as $\mathbb Z^{n+1}\sim \mathbb N$.

[vital dew]

Afzal

[gusty dome]

Does it look correct?

[cerulean wind]

i think the overall idea is correct. a better way to go about it would be to write A_n as the union of a bunch of finite sets

@gusty dome

[gusty dome]

Union of sets corresponding to each n tuple of integers?

[cerulean wind]

for each polynomial f with integer coefficients, you know that f^{-1}(0) is finite

[gusty dome]

$A_n = \bigcup_{(a_0,\cdots ,a_n)\in \mathbb Z^{n+1} \text{ with } a_n \neq 0}{x:\sum a_kx^k=0}$

[vital dew]

Afzal

[cerulean wind]

yup

[gusty dome]

Oh yes. Lemme try to formally do the proof again

[cerulean wind]

if you want more concise notation, set $P_n = {f\in\mathbb{Z}[x] : \text{deg}(f) = n}$ so that
$$A_n = \bigcup_{f \in P_n}f^{-1}(0)$$

[vital dew]

c squared

[gusty dome]

(sorry i mistakenly touched on delete)

[cerulean wind]

you know that $P_n$ is countable, since it injects into $\mathbb{Z}^{n+1}$

[vital dew]

c squared

[gusty dome]

Oh that's really concise!

[gusty dome]

Do you mean bijects?

[cerulean wind]

yes

anyways, do you see how to continue knowing that A_n is of this form?

[gusty dome]

But what about the 0 tuple?

[cerulean wind]

degree zero polynomials are constant polynomials with non-zero integer coefficients

[gusty dome]

Yes. I see how A_n is written. We are combining (taking union) of all roots of each polynomial in integer ring with degree n.

[cerulean wind]

right, but how do you show that the algebraic numbers are countable knowing that each A_n is countable

[gusty dome]

Using the fact that countable¡union of countable sets is countable so $\bigcup_{n \in \mathbb N} A_n$ is countable

[vital dew]

Afzal

[cerulean wind]

alr sweet

[gusty dome]

Thank you! I will try the polished proof!

[gusty dome]

Is it looks good? (sorry for late I was busy)

This is authors solution but I did not understand first four lines I mean from the set (stated in first line) is defined

[meager prawn]

I see how the red ones are a strong congruence, but not the other 2
In particular I don't see how it holds when taking q, q' in the left class

https://arxiv.org/pdf/2401.15384
In case it's too small (page 15)

[thorny hill]

how do i do this?

Since his retirement, Jack goes for walk Monday to Friday, for 3 hours on each
of these 5 days. On average he walks 1.5 miles every hour. Find the probability that the 3rd day
that Jack walks more than 8 miles is on Friday, the last day of walking week?

its probability but idk its confusing

[vestal bronze]

i am confused

[vestal bronze]

maybe they tell you what distribution to use, like they describe it right before the problem?

[torn totem]

https://en.wikipedia.org/wiki/Poisson_distribution

[vestal bronze]

it doesn't make sense to model it as poisson, but i have no better idea myself

[ashen bane]

can you please help me with this question

i need to calculate number of walks from s, of length n, now in their answer they defined only 3 recursive formulas

i defined 6, idk why how they defined only 3

i'd love if someone could explain it to me :3

[coral parcel]

Looks like total distance he walks is only 22½ miles, so there cannot be three days with 8 or more miles.

[odd heart]

Maybe they use the symmetry, in that you just have to count walks whose first step is towards the upper left vertex, and then multiply the result by 2?

[ashen bane]

Tbh someone from my class already helped me

i for some reason thought i should end the path in s

but it wasnt written in the question

so i got basically stupid

[forest palm]

Hi can I get help here

I got this [given (G,* ) and the subset H of G is not empty I need to show that (H,* ) satisfies all the axioms of a group except for identity element]

[brave rock]

Well this is false for most subsets H so you're going to have to add context.

[forest palm]

Its difficult to find

[brave rock]

OK so the answer is this is false.

[forest palm]

I think maybe I explained in a wrong direction the question is to give an example for a set G that satisfies the axioms to be a group and to have H as a sub set which satisfies closure inverse element and Associative property but not the identity

[brave rock]

I don't understand what you're saying. Maybe you could just post the question.

[forest palm]

"Given a set ( (G, *) ) that forms a group and a non-empty subset ( H \subset G ), provide an example where ( (H, *) ) satisfies the properties of closure, having an inverse element, and associativity, but does not satisfy the identity element property."

[vital dew]

AHM3d

[brave rock]

Hint: for any group G, there is exactly one set H that might have this property

Second hint: suppose x is an element of H. What do the closure and inverse properties together imply?

[forest palm]

I will take the hints and think about it thank you very much

[upbeat fog]

Three numbers a,b,c in that order, are in geometric sequence with common ratio r.
Given further that a,2b,c in that order, are in arithmetic sequence, determine the possible value(s) of r.

I am unaware on how to solve a question like this does anyone have a text book or video they can guide me towards so i can learn i have frantikly searching for a method or teaching but cant and ChatGPT wont teach it to me XD

[coral parcel]

Express b and c in terms of a and r. Then write down an equation stating that a, 2b, c is in arithmetic sequence.

[upbeat fog]

Ari helped me sovle that thankfully i get it now but now im stuck on another question 😭

[unique acorn]

I'm reading through Terence Tao's Analysis, and I'm currently on the set theory chapter, but I'm a little confused on his definition of generalised intersection. Here's how its defined: \
For some non empty index set $I$, a set $A_\alpha$ assigned to each $\alpha \in I$, as well as some $\beta \in I$, we can define the intersection as
$$ \bigcap_{\alpha \in I} A_\alpha \coloneq {x \in A_\beta : \forall \alpha \in I (x \in A_\alpha)} $$
I understand how the definition results in the intersection of all sets $A_\alpha$, but I dont get why you couldn't just define it to be
$$ \bigcap_{\alpha \in I} A_\alpha \coloneq {x : \forall \alpha \in I (x \in A_\alpha)} ,$$
since the fact that $x \in A_\beta$ is already built into the second part of the definition. Is there some reason why its defined the way it is?

[vital dew]

QuantumBaqel

[coral parcel]

If the index set I were empty, your second definition would be attempting to produce a set of all sets, which is not allowed.

Picking a particular A_beta to take a subset of makes clear that the whole thing can be justified as an application of the Axiom of Separation (or whatever Tao calls that axiom; it has a bunch of different names).

[unique acorn]

Oh that makes sense, thanks!

[weary tiger]

hi everyone

I need some help with my assignment just to better understand the material cause I'm self doubting myself here

[rapid kernel]

What does it mean by the 3rd rule ?

[vestal bronze]

means all clubs are diferent

[rapid kernel]

So there is no member which is in intersection of any two clubs ?

[fossil mural]

...no? where did you get that from

{A, B, C, D} and {A, B, E, F} are different clubs

they both have A and B in them, but one has C in them and the other doesn't, so they're not identical

[pastel yacht]

Did the easiest graph theory problem set but was pretty fun to do

[rapid kernel]

Okay thank you

[snow junco]

Whoops discord did not load sry for ping

[digital sinew]

if the cartesian product of 2 sets A, B is defined by the set {(a,b) such that a in A and b in B} then why is the cartesian product of A, B, C the set {(a,b,c) such that a in A and b in B and c in C} rather than {((a,b), c) such that a in A and b in B and c in C} ? or rather why is the cartesian product of 3 sets not an ordered pair containing an ordered pair but instead being an ordered triple?

[brave rock]

We simply write it like that by convention

You are right to point this out, but this is just something mathematicians do to make their lives easier.

[digital sinew]

is ((a,b),c) = (a,b,c)?

or by convention it's just a different operation?

[brave rock]

This may as well be true, yes

This is pretty much the conversion that people make

But the whole point is that mathematicians usually don't want to deal with this kind of annoying detail so we just write (a,b,c)

[digital sinew]

yes but i've always associated n-tuples with vectors so it's just confusing to me xd

[coral parcel]

All that's really important is that you can be sure that (x1,x2,x3) and (y1,y2,y3) can only be equal if x1=y1 and x2=y2 and x3=y3.
Which particular things we choose for the notation (x1,x2,x3) to mean should not matter, as long as thy satisfy this/

There are a few rare-ish contexts where we also want to be sure that, say, (x1,x2,x3) and (y1,y2) are never the same thing (such that we can put both kinds into the same set and trust we can distinguish which is which when we take them out again). When that's the case we'll need to choose something else than nested pairs for representing the triples.
It's common that not a lot of fanfare is made of this, but instead it is left to the reader to notice it, in the rare cases where the reader is particularly interested in the details for formalizing the stuff that's happening in some foundational framework.

[timber minnow]

I am working on exercise 8.5.13 and I am almost done.

I know why {y \in Y: y<= a} = {y \in Y': y <= a} = {y \in Y \cap Y': y <= a} and I know why that shows why Y \cap Y' is good.

However, I am having trouble showing that s(Y \cap Y') = min(Y' - Y) when Y'-Y is nonempty

I want to use the universal property of min, but I don't know why s(Y \ cap Y') is forced to be in Y'-Y when Y'-Y is nonempty or why s(Y \cap Y') is less than any element of Y'-Y when Y'-Y is nonempty

Any guidance would be appreciated!

[timber minnow]

https://math.stackexchange.com/questions/4045654/exercise-8-5-13-terence-taos-analysis-1

I found this post explaining it, so I now know how most of the answer to my previous question, but I am not sure about the following:

I am not sure why s(Y \cap Y') is a strict upper bound of Y'

[timber minnow]

Also y is a typo and should be y'

[timber minnow]

Also when the author says "since otherwise there is an element y'...", it looks like Y \cup Y' was assumed to be a total order.

not every element of Y\Y' being a strict upper bound of Y' means the same thing as:

There exists a y' \in Y\Y' and an element y'' \in Y' such that (not (y'' < y')). 

You can't convert the (not (y'' < y')) to a y''>= y unless Y \cup Y' is a total order

[steel portal]

maybe use proof by contradiction?

[timber minnow]

For which statement? there are multiple.

[steel portal]

if ur just looking at the upper bound here are my thoughts

but im not too sure lol

[timber minnow]

In this part, we only have not(y'>= y''). To go from not(y'>= y'') to y'' > y', we need to know Y \cup Y' is a total order

This part was also a detail left out of the original stack exchange post that I wasn't able to fill in

I only know that s(Y \cap Y') is a strict upper bound of Y \cap Y'.

The statement claims it's a strict upper bound of Y', and I don't see how that follows from it being a strict upper bound of Y \cap Y'

[ashen bane]

Show that planar graph has at least 4 nodes of degree 5 of less

[timber minnow]

Actually we know automatically that Y \cup Y' is a total order because Y is a subset of Y' and vice versa. We know the previous statement because Y-Y'=empty or Y'-Y=empty

[timber minnow]

I now realize that Y \cap Y' is Y', which proves this claim

[pastel yacht]

When doing proofs, is one allowed to make up an example to prove or disprove something?

[brave rock]

If your claim is "there exists x such that ..." then this is provable by example.

No other kind of proposition necessarily follows from an example.

N.b. "Not all things x have the property that..." is equivalent to something of the form "there exists an x such that ..."

[agile magnet]

You can prove existential claims by showing the thing exists

You can disprove universal claims by finding a counterexample

[pastel yacht]

ah thank you i understand

[stable wren]

Does anyone know of a graph algorithm which could generate the right graph from the left? The right graph is a graph which contains all possible new edges which could be added to the left graph which would keep it acyclic

[agile magnet]

There's a cycle between B_ and C_

Also do you just want a maximal way to add edges? It won't necessarily be unique

I think I have an idea but I have no confirmation if it's a correct idea.

[stable wren]

a sorry I wasn't clear enough - any single edge in the right hand graph could be added to the left hand graph while keeping the left hand graph unique

duplicate edges are allowed

each time a new edge is added on the left, the right graph will need to be recalculated

[agile magnet]

But that doesn't answer my question that the right hand graph isn't acyclic

Ohhhh wait I see

NVM NVM

I understand now

The algorithm I have in my head runs in O(n^3) time

Very brute force

[agile magnet]

Do u mean acyclic instead of unique here?

[stable wren]

currently my idea is to do a transitive closure -> transpose -> for each vertex get the list of out_edges, minus that list from the full set of all vertices. But i have no idea of the complexity of that

[stable wren]

ah yes I do, thanks

[agile magnet]

Do you know what a topological sort is?

[stable wren]

yep

[agile magnet]

Cool

Then my idea is basically test every possible edge

For each possible edge, add it, see if topological sort exists

If it does, add edge to result graph

There's gotta be a smarter way

[coral parcel]

Is the input always a tree?

[agile magnet]

It's always a directed acyclic graph

Although I guess it could be any graph since if it isn't acyclic you can't add any edges lol

[stable wren]

hmm I wonder if I take the transitive closure of the transposed graph's complement?

[agile magnet]

How does that help? I don't follow

(I've never looked at this problem before so I'm just spitballing here)

[coral parcel]

Actually what you want is the reversed complement of the transitive closure, as far as I can tell.

[stable wren]

I think that produces the result. The complement removes all which would create direct loops just by its nature, then the transitive closure fills in the remaining ones which "jump across" branches

oh yes maybe the other way round

I'll just run through an example on paper to check

sorry if my wording isn't proper, I haven't actually studied much graph theory I've just come across these problems through some electronics projects

[agile magnet]

Once I get to some paper I'll try this, I don't see it

[stable wren]

by "reversed" do you mean the transposed graph?

[coral parcel]

Uh, I suppose it could be called that too.

All the edges that are not opposite to something in the transitive closure.

[stable wren]

okay I've run through it on paper with a couple graphs and I think you are correct @coral parcel . Take the first graph, generate its transitive closure -> then the complement of that -> then the transposition/reverse of that. I might try to generate some more complex examples which I can test with code to be sure but it seems right to me

thanks so much for your help everyone!

[digital sinew]

how do you prove a is in A but b is not in C therefore (a,b) is not in A x C? formally

[agile magnet]

So you want to prove that $a \in A$ and $b \notin B \implies (a, b) \notin A \times B$. What ideas do you have? (changed $C$ to $B$ just for clarity)

[vital dew]

Spamakin🎷

[digital sinew]

yes, i don't even know how you would start which is why im asking

[agile magnet]

No ideas?

[digital sinew]

convert to set builder and try to do some stuff?

but i don't see how

[agile magnet]

Nah I think we can do something easier than that (in fact since we are dealing with single elements idk how set builder would help in a not convoluted way)

Do you know what the contrapositive of an implication is?

[digital sinew]

sure

[agile magnet]

is that "sure" a yes or a not quite?

[digital sinew]

$a \implies b \ \lnot b \implies \lnot a$

oop

[agile magnet]

yea ok

[vital dew]

someone1010

[agile magnet]

so try to prove the contrapositive

[digital sinew]

i don't have that statement though

[agile magnet]

yes you do

$(a \in A \text{ and } b \notin B) \implies (a, b) \notin A \times B$

[vital dew]

Spamakin🎷

[digital sinew]

well technically but i'm not sure how you would get that statement as this is part of a 2-col proof

i have the statements

a in A

b not in B

how would you prove (a,b) not in A x B

[agile magnet]

does it have to be 2 column in this format? Do you have to prove directly and not via contrapositive?

[digital sinew]

2 col yes

which is why im confused mostly

[agile magnet]

Damn

Ok then use the formal definition of A x B

[digital sinew]

A x B = {(a,b) | a in A and b in B}

oh wait you would just demorgans and then that's done

[agile magnet]

can u elaborate

[digital sinew]

wait maybe not?

idk

nvm i have no clue

[agile magnet]

so what would it mean for (a, b) to not be in A x B?

Lets rewrite the definition using different variables just to keep things clearer

[digital sinew]

no clue

[agile magnet]

A x B = {(x,y) | x in A and y in B}

so if (x, y) is in A x B, then x is in A and y is in B right?

just by definition

[digital sinew]

yup

[agile magnet]

this is an implication. Can you take the contrapositive of this?

this is why 2 column is fucking dumb man 😭

it would be 10x easier if you could write sentences and such rather than 2 column nonsense

[digital sinew]

thanks for the sympathy

why are these proofs so long tho, 30 step proofs lmao

[agile magnet]

I'm actually struggling myself to think how to write this in some 2 column format

even though I have the proof in my head just using sentences

which would be clearer

[digital sinew]

it seems quite easy to proof it via contradiction

but i don't think that's possible

[agile magnet]

or by contrapositive

[digital sinew]

these proofs make me wanna die

Prove that F = {(x, y) ∣ x ⋅ y ∈ Z^+} on the set Z is a transitive relation with 2 col

how tf you do cases in 2 col ?

ok you can do cases but that'll take like 100 steps

[shadow lion]

2 col proofs are definitely not how proofs should be done

[vernal marlin]

Let P(x, y) =“x has parked their car in suburb y”.
Let N(x, y) =“x is a nicer suburb than y”

rewrite the following statement:
There is a nicer suburb than all the suburbs somebody has parked in.

can someone help me with this 🥲

[coral parcel]

Do you have an attempt?

(Oh I see you also posted in #proofs-and-logic, where someone already engaged. Please don't post the same question in several different channels).

[vernal marlin]

sorry mb i forgot to remove it, didnt realsie that there was proofs and logic channel 😬

[weary tiger]

A certain neighborhood has 80 total households.

Which of the following statements individually provide(s) sufficient additional information to determine the number of households in the neighborhood that have a swimming pool or a yard, but not both.

A) 30 households have a swimming pool, 39 households have a yard only, and 11 households have neither.

B) 30 households have a swimming pool, 46 households have a yard, and 11 households have neither.

C) 7 households have both a swimming pool and a yard and 11 households have neither

Is A wrong because 80 = 30 + (39 + x) - x + 11 can't actually be solved and thus the intersection can be anything from 0<= intersection <= 30?

[coral parcel]

I'd say A is wrong because neither of the numbers you have there makes any distinction between "pool and yard" and "pool, no yard".

[weary tiger]

is that a verbal description of my equation?

basically the x's cancel out?

[coral parcel]

I meant it as "we don't even need to write down that equation".

None of those givens would change if we add a yard to a house that already has a pool, or remove the yard from a house with both.

But those changes do change the number we want to determine.

[weary tiger]

ah yeah you mean the both can be anything? cuz i can just sya something like 10 households could have a house with swimming pool and yard

and that doesn't change thd description of the sentence

that 10 could be 20 as well, for example

but then the maximum is 30, correct? cuz you can't have 31 houses with yards + swimming pool? so in a way we can bound it but we can't be certain what exactly the number is?

[coral parcel]

Right.

So we can say there's somewhere between 39 and 69 houses (inclusive) with "pool XOR yard".

[weary tiger]

sure thanks

[thorny hollow]

Does C has 19 elements?

[weary tiger]

mext?

[thorny hollow]

Yes

[weary tiger]

it’s just principle of inclusion exclusion, i can’t calculate it rn cuz im doing something, but it’s just using the formula tbh

[weary tiger]

PIE for 3 sets

[thorny hollow]

Thr answer is 92

[wintry holly]

i couldn't find a graph theory chat so ill put it in here since its the closest

so im trying to prove that if a simple graph G is 2 connected then that implies there exists two u-v paths P and Q that are internally disjoint. Its a proof by contrapositive so given that the graph has no two internally disjoint paths I'm trying to show its not two connected. My argument is basically that if there is no internally disjoint paths connecting some u and v in G then there exists some vertex I'll call x which is the last point of intersection of all u-v paths with path P which must exist because if it didn't then it would be a disconnected set. removing x disconnects the graph which means it's not 2 connected

does that make any sense

[quick jetty]

im having trouble with this

maybe somebody has some ideas for a proof?

[quick jetty]

another one

[pale monolith]

This isn't true

Take arbitrarily many empty sets

[quick jetty]

well they need to be different subsets

i translated this myself so it may be not that clear but they are supposed to be different subsets

[drifting sand]

im assuming n >= 2?

[quick jetty]

yeah

[drifting sand]

First notice $\Omega=\bigcup_{i=1}^nA_i$

[vital dew]

Sara

[drifting sand]

And that for $i\neq j$, $|A_i\cap A_j|<2$

[vital dew]

Sara

[drifting sand]

Those should help

[drifting sand]

Nvm has to be >= 3 I think

Doesnt hold for n=2

[quick jetty]

oh yeah thats right

[pseudo solar]

Hi, I am new here and hope this is allowed here, let me know if it's not. I am trying to prove that in the coin change problem, the greedy algorithm is optimal for US coin denomination of 1 cent, 5 cents, 10 cents and 25 cents. I prove it by induction but the base case seems a bit long. Want to see if anyone can give some feedback/suggestions?

[fossil mural]

wow yes that base case is indeed very long

i'm also not really convinced that you actually proved the statement?

like you've shown that this gives a way of making change, but how do you know there isn't some clever collection of coins that's faster than just taking as many 25s as you can get

this isn't true in general for arbitrary denominations - if you add a 24 cent coin to the set, then the greedy algorithm still works perfectly coins below 25, but splits 29 as 25 + 2 + 2 instead of the more efficient 24 + 5

[pseudo solar]

Yes, this algorithm doesn't work for arbitrary denomination. I am trying to prove specifically for US denominations of 1 cent, 5 cents, 10 cents and 25 cents.

[fossil mural]

well it does work in the sense that it produces change at all, as long as there's a 1 cent coin

...and that's all you've proven

the property that makes 1/5/10/25 special is that the greedy algorithm is optimal, and you haven't written anything resembling a proof of that

and my point with the 24 cent coin is that nothing you wrote actually distinguishes that case from 1/5/10/25, so if it was valid reasoning it would also prove that the greedy algorithm is optimal in a case where it actually isn't

[pseudo solar]

So I made the argument that for any amount greater than 25, I can just repeatedly take 25 cents (which is optimal) until the amount is less than 25, and when it's less than 25, I have showed in the base case that it is also optimal.
I don't understand your 24 cent coin point though. I know that for other denomination it doesn't work. I am new to this so I really appreciate you taking a look, please elaborate on why I have to consider other coins when I have restricted the problem?

[fossil mural]

which is optimal
you never proved it was optimal, you just proved that it's something you can do