discrete-math

[coarse sphinx]

The strange thing is that the first part of the question asks if it is reflectiv, symmetric, anti-symmetric or transitive and the second part if one can add something to make it into a equivalence relation (yes or no) and the third part is what to add. (one point for each question)

[reef thistle]

Transitive just means if xRy and yRz, then xRz

that is true

[pale epoch]

you can add nothing and make it an equivalence relation

[coarse sphinx]

The third question begins "If yes...." :)
Very hard to get 3 points.

[reef thistle]

you can add all the pairs, and it would be another trivial equivalence relation

[pale epoch]

yeah, you can always turn a relation into an equivalence relation

is this from a real exam?

the notation for S is horrible

it isn't even a set

[faint narwhal]

Jk I can't add

[coarse sphinx]

😃

[pale epoch]

was having heart attack

[coarse sphinx]

I study computer sciences at Karlstad University in Sweden and this is from an old exam earlier this year.

[pale epoch]

rip

[weary tiger]

I have a question about notation here. Suppose you have the sets A, B, and C. Let A x B x C be the cartesian product of the sets. Let A have elements a1, a2, etc B have b1, b2, etc and C have c1, c2, etc.

Why is it that A x B x C results in elements such as:

(a1, b1, c1) and not ((a1, b1), c1)?

[faint narwhal]

@weary tiger mostly convention

[weary tiger]

Are both correct? I would think they are two different things

[faint narwhal]

It's clear that there's a bijection between (A x B) x C and A x B x C in exactly the way you described

And it's a very natural bijection

So people just write the latter

It's important to note that the operation is associative

[weary tiger]

so suppose I add in D, then (A x B) x (C x D) is the same as A x B x C x D?

[faint narwhal]

So that we have that (A x B) x C is naturally bijective with A x (B xC)

Yep, because of this associative property

[weary tiger]

ah okay, thank you

Actually: https://proofwiki.org/wiki/Cartesian_Product_is_not_Associative

This seems to say they are different

[glossy adder]

they aren't the same thing but you'll have an easy bijection

[weary tiger]

It does seem to say at the bottom in a comment:

`Despite this result, the cartesian product of three sets is usually just written A×B×C and understood to be the set of all ordered triples.

That is, as the set of all elements like (a,(b,c)).

From Cardinality of Cartesian Product, we have that:

|A×(B×C)|=|(A×B)×C|
and so:

A×(B×C)∼(A×B)×C
where ∼ denotes set equivalence.

So it matters little whether A×B×C is defined as being A×(B×C) or (A×B)×C, and it is rare that one would even need to know.

When absolute rigour is required, the cartesian product of more than two sets can be defined using ordered n-tuples or, even more generally, by indexed sets.

`

[faint narwhal]

@weary tiger read the comment

At the end

Oh yeah

[weary tiger]

My book also follows the convention of what you're saying @faint narwhal so I'll just use that

[faint narwhal]

Everyone follows this convention

[weary tiger]

I think my confusion comes from a programming side where (a, (b, c)) is different from (a, b, c) because if I want to get b in the first one I index tuple[1][0] and in the second it is tuple[1]

[faint narwhal]

but you unrolling the first one gives you the second one

[weary tiger]

Is {λ} = the empty set, where λ is the empty string?

[faint narwhal]

No, that set has an element

[weary tiger]

so |{λ}| = 1

[faint narwhal]

Yep

[weary tiger]

If A = B, Then A and B are partitions of each other, right?

As long as they're not the empty set

[pale epoch]

A is not a partition of itself

unless it is empty

[weary tiger]

but A is a partition of B if A = B, right? I don't see in the set of rules that it can't be

[pale epoch]

no

this is exactly the same as saying "A is a partition of itself"

[weary tiger]

For all i, Ai ⊆ A.
For all i, Ai ≠ ∅
A1, A2, ...,An are pairwise disjoint.
A = A1 ∪ A2 ∪ ... ∪ An

Which one here is violated?

[pale epoch]

{A} is a partition of A, though

maybe that's what you meant

[weary tiger]

yes that is what I mean

I see where I went wrong

[pale epoch]

then it's fine

it's called the trivial partition sometimes

[weary tiger]

Although my by my book I think that it would be okay to word it that way

[pale epoch]

it's the only partition with just one element

[weary tiger]

Since my book states something like "A, B, C" and not {A, B, C}

[pale epoch]

"A, B, C is a partition" sounds confusing

[weary tiger]

"Do the sets A, B, and C form a partition of D?"

that's an example

[pale epoch]

that's different though

[weary tiger]

you added the is a partition thing, not me

[pale epoch]

i'm just saying that this is fine

[weary tiger]

I'm just saying it does not say "{A, B, C} forms a partition of D"

so i think it would be corrct to say "A forms a partition of A"

[pale epoch]

ok, fair enough

[dapper hound]

why would de + complement de not equal 1?

its a XNOR gate but,

[sour arrow]

Note that D'E' ≠ (DE)'

[dapper hound]

yes it would be the complement of de

so if d = 0 and e = 0 then d * e would be 0

but de complement would be 1 * 1 = 1

wouldnt it?

[sour arrow]

The complement of D OR E ≠ The complement of D OR the complement of E

If + is an OR gate here

[dapper hound]

yes + = an or gate

but when DE are stuck together like that that means multiplication and multiplication means AND

[sour arrow]

Derp lol I used the wrong word

The complement of D AND E ≠ The complement of D AND the complement of E

[dapper hound]

why do you take the complement of it after?

[sour arrow]

I'm not, you are without realizing it

[dapper hound]

this is what i am doing

i see DE with the complement sign over both of them

i plug in the original values of d and e in this case lets say o

complement of d = 1 complement of e = 1

then i do the AND

1 and 1 = true, or 1

[sour arrow]

You're right that DE + (DE)' = 1
But that's not what we have

(0*0)' = 0
0'0' = 1

[dapper hound]

why is the first one 0

0 and 0 = false, or 0 but then you complement it afterwards

which would be 1???

[sour arrow]

Wow, you're right, my bad

Bleh, I'm not hitting the right example lol. You have
DE + D'E'
Let D = 0, E = 1
01 + 0'1' = 0

[dapper hound]

that makes sense but thats just for 1 combination

just because one combination turns our false the whole thing is false?

[sour arrow]

No, but it's definitely not always true

[dapper hound]

ok i see where you're going

so because its definitely not always true we can't have it equal 1

opposed to if its was something like (D' + D)

[sour arrow]

Which is always 1 yeah

[dapper hound]

then it would definitely be 1

ok so let me clarify the reason behind it not being 1 is because theres a possibility that it could be false with another combination

and unless we know with certainty we can assume otherwise?

[sour arrow]

1 is a statement of "this is always true no matter what D and E are" which isn't the case

[dapper hound]

oh ok

so we only put 1 if its certain such as the one scenario i mentioned

[sour arrow]

You may be able to write DE + D'E' differently to better express it

[dapper hound]

thanks

[jade mountain]

is it possible to find the minimum flow from source to sink?

or did my instructor just mess up and mean to put minimum cut?

[neat eagle]

do edges have a maximum flow passing through it? or is it a different problem entirely?

if they all have upper bounds on the flow like a normal flow problem, then the min flow would be 0?

and thus he probably just had a typo

otherwise this may be a thing https://stackoverflow.com/questions/18598399/what-algorithm-should-i-use-to-find-the-minimum-flow-on-a-digraph-where-there-ar

[cerulean ore]

Guys, if A= {1,2}, B = {a,b,c}, c= {3,4} are the sets then
AxBxC = {((1,a),3), ((1,b),3)....} are the elements or

{(1,a,3), (1,b,3), (1,c,3)...} are?

[pale epoch]

by convention it is {(1,a,3), (1,b,3), (1,c,3)...}

[cerulean ore]

Why not the other one?

[pale epoch]

because it is more brackets to write down

you could also ask why not (1,(a,3)), ...

[cerulean ore]

but, (1,(a,3)) would represent it in a wrong way?

[pale epoch]

why?

[cerulean ore]

oh, that's same

[pale epoch]

it's the difference between (AxB)xC and Ax(BxC)

[cerulean ore]

So, this way: {((1,a),3), ((1,b),3)....} is wrong?

[pale epoch]

i wouldn't call it wrong

your way of writing it and the {(1,a,3), (1,b,3), (1,c,3)...} way are isomorphic

mathematicians have just decided to use the way of writing it with less brackets

because that is easier and less confusing in practice

[cerulean ore]

My teacher crossed the whole answer and gave me a 0.

[pale epoch]

hm

i would disagree with your teacher

depending on the notation you used in the rest of the answer

or was that the whole question?

[cerulean ore]

That was the whole question

find AxBxC

[pale epoch]

how did you define cartesian products in class

maybe you just didn't use the definition you were taught

but conceptually, you can do both

what you did was give (AxB)xC

[cerulean ore]

The teacher is known for his marks deduction capabilities.

I will use the notation from now on, thank you!

[pale epoch]

did you talk with your teacher already?

[cerulean ore]

Yes, he said that is a wrong way to write it.

[pale epoch]

i mean, depending on how exactly you defined cartesian products, i can understand him giving you 0 points

do you know what an isomorphism is?

[cerulean ore]

Looks same

[pale epoch]

yeah, kinda

well, your way of writing is not wrong per se, imo

it's just unconventional

you should adopt the style with less brackets, but you weren't wrong

[cerulean ore]

Sure, from now on, I will.

Which book has all this stuff?

[faint narwhal]

Yeah

Like I said

There's an obvious bijection between the two sets

But, it seems like your teacher has defined it in a certain way

And so you should follow that definition

[cerulean ore]

His definition was very simple*

[faint narwhal]

His definition specifies which one to use

[cerulean ore]

His definition as it is:
Let A and B are two non-empty sets then the cartesian product of set A and B is denoted by AxB. The set of all possible ordered pairs from set A to B.
AxB = {(x,y): x belongs A, y belongs B}

[pale epoch]

ok, but that doesn't define how to deal with the cartesian product of more than 2 sets

[cerulean ore]

exactly

[pale epoch]

if this is the only definition you have

one could argue that your answer is the correct one

because it would be the only way you could possibly deal with the cartesian product of 3 sets

[cerulean ore]

Arguing means deduction in marks in other ways (assignments, etc)

[pale epoch]

tbh if this was the only defintion given in class

and you did this

you would get full marks

[cerulean ore]

Set theory itself is harsh and a teacher like this one is cherry on top

[pale epoch]

and i would possibly deduce marks from everyone else xd

[cerulean ore]

Lol, be our professor then

[faint narwhal]

If that really is the only thing you got

Then writing A x B x C is ambigious

[stray reef]

Arguing means deduction in marks in other ways (assignments, etc)

what

[cerulean ore]

Welcome to India! ^

[stray reef]

"don't talk back or i'll dock marks"

that's just one step away from "anyone who disagrees with 2+2=5 will be shot in class"

so you're saying that a teacher can grade however the fuck he wants and the students are to just shut up and take it?
what if the teacher sees a completely valid piece of work and decides to just give it a 0 for no reason?

[cerulean ore]

You can do 2 things:

1. Ask for rechecking which only means recounting all the marks given.
2. Sue the college.

[stray reef]

recounting all the marks given? so the only thing you can ask for is for the graders to check whether they've made an arithmetic fuckup in determining your grade?

[cerulean ore]

Yes even for the final exams.

[pale epoch]

what if you ask for recounting and they count even less marks

[stray reef]

what the fuck

i mean seriously what the fuck kinda fucked up education system even IS that

[pale epoch]

i mean in theory it's the same here

[stray reef]

the students have exactly 0 say in how they're graded

[cerulean ore]

The thing is if the grader itself is fucked up then what is the use of rechecking.

[stray reef]

that's bullshit

[pale epoch]

a professor could go full "fuck you" and your last straw would be going to court

i just never met an asshole prof

[stray reef]

can you at least ask for explanations on what you got docked points for

or is it just "you just got docked another point just for asking that"

[cerulean ore]

Even after performing exceptionally good in C++, I have got 80 marks whereas those who didn't even know how to write got A+ (100)

[stray reef]

tf

[cerulean ore]

BTW, I have to go. I will try to ask him in a buttering way.

Thank you for helping!

[pale epoch]

how is india going to become a superpower by 20xx that way

[weary tiger]

lmao

superpower current_year + 1

[pale epoch]

tbh i can understand a prof marking that wrong

but if a student were to come to me with his answer

and the definition of a cartesian product like that

i would have to go "damn, he right"

or at least he did the most logical thing with the definition given

[weary tiger]

Hello, right now I'm getting into discrete maths, and I wanted to ask if there's a online resource/guide or follow up steps out there, and if not which books do u recommend?

[faint narwhal]

Really depends on what you want to learn

[weary tiger]

https://en.wikipedia.org/wiki/Discrete_mathematics so here are 17 topics, and I'm willing to get into the IT Industry focusing blockchain, ia and quantum computers

so I don't know if to study everything, or some parts

[faint narwhal]

Uh that's not what the IT industry is and I think you mean AI

But, if you want to do those things

Then you'll need to learn a lot about discrete math

[weary tiger]

Yep

So any recommendations into books or smth else?

[faint narwhal]

There's a book called applied combinators by Trotter

That's the one I read at least

[weary tiger]

Gotcha will have a look

[cerulean ore]

Can anyone suggest a good book on set theory, I am facing hard time in proofs.

[faint narwhal]

A book on set theory isn't what you're looking for

Try reading How to Prove It by Velleman

[gentle sky]

For actual set theory

Read Goldrei 👌🏽

And then Jech I guess

[weary tiger]

I hope I understand this right. Is this true to say?

"If 5 is even, then 3 is prime." This statement is true by propositional logic, right? Because the first statement is false, so whatever comes after doesn't matter and the proposition holds.

[faint narwhal]

Correct

[stray reef]

the statement is vacuously true yes

[dapper rose]

$\text{It is in \LaTeX}\iff\text{It is false}$

[vital dew]

EpicGuy4227:

[stray reef]

$2+2=4$

[vital dew]

Ann:

[weary tiger]

epic plis

[dapper rose]

I thought a good exercise would be to reason why the statement I posted is a paradox

$\text{It is in \LaTeX}\implies\text{It is false}$

[vital dew]

EpicGuy4227:

[dapper rose]

nvm i think i wrong

[weary tiger]

lmao

[cerulean ore]

How to Prove It by Velleman or goldrei classic set theory?

For someone is facing problem with the proofs^

[weary tiger]

how to prove it

[cerulean ore]

Thank you!

[cerulean ore]

First line, LHS has limits i=0 to N-1

and RHS has 1 to N

what is the method to change its limits?

[faint narwhal]

Write out each sum, you'll see that they're the same

[cerulean ore]

They might be same but, is there any technique to change the limits?

[pale epoch]

it's called an index shift, i think

[faint narwhal]

Yeah

Every i in the first sum

Becomes i-1 in the second sum

That basically keeps i the same throughout

And you're subtracting i and that's why it adds 1 to each of the products

[cerulean ore]

it adds 2 to only one product?^

[faint narwhal]

It technically does that yes

But if you look at it, because you can switch the order of multiplication

It's the same as adding 1 to each of the products

[cerulean ore]

Got it!

Thank you!

[weary tiger]

The following is a proposition, right?

∀x Q(x) ∨ P(3)

Because the x is bound and P(3) is a truth value that can be known.

[pale epoch]

what's your definition of "proposition"

[weary tiger]

A proposition is something like "The sky is purple"

or " 7 is even" or "2 is a prime number"

where as a predicate is "x is even"

[pearl carbon]

yes, it's a proposition

[weary tiger]

My problem comes with this:

Let Q(x) mean "x is a perfect square" and P(x) mean "x is prime"

Then ∀x Q(x) ∨ P(3) means what?

"For all x, x is a perfect square or 3 is prime"

Then the truth value is true? (Because 3 is prime)

oh and the domain is set of all integers

[pearl carbon]

yes, it's true

for the reason you specify

3 is prime

[weary tiger]

thank you

[ashen patrol]

anyone online?

[dense thicket]

nope, you're alone

[ashen patrol]

dang

[ashen patrol]

im going over notes for a test review and idk how to "write a formula for recursively defined functions"

the first example is:
f : all Natural numbers -> all Real numbers
f(1) = 1, f(n) = nf(n - 1)

[tropic cedar]

You mean write a closed/explicit formula?

[weary tiger]

Are quantifiers associative? For instance are these two the same:

1. $\exists x \forall yP(x,y)$

2. $\forall y \exists xP(x,y)$

[vital dew]

DeathPox:

[weary tiger]

I assume they are the same

As the bounded variables are the same

My reason for this is from this question:

Let x and y be in the domain of all real numbers. Then which of the following are true?

$$

\forall x \exists y(x + y = 0)

\exists x \forall y(x + y = 0)$$

[vital dew]

DeathPox:
Compile Error! Click the reaction for details. (You may edit your message)

[weary tiger]

The first one is obviously true to me

[pale epoch]

they are not associative

[weary tiger]

but the second one seems false

[pale epoch]

think of continuity

(if you know the epsilon delta definition of continuity)

your example works as well though so yeah

it's probably better

[weary tiger]

I think I understand. Am I right with the first being true and the second is false?

[pale epoch]

yes

you can think of it that way

in the first case the y can depend on the specific x

in the second case the x must work for all y

[weary tiger]

ah okay, thank you

[weary tiger]

I'm trying to improve my proof writing, can someone tell me if this is a good proof statement of the following:

"Among every consecutive three integers, there is a multiple of 3."

I then write:

Take some $x, x\in Z$. There is always some $n, n\in Z$ in the range $x\le n\le x+3$ such that for some $k, k\in Z, n = 3k.$

[vital dew]

DeathPox:

[weary tiger]

Is that too wordy?

I'm thinking it may be able to be reduced more and perhaps establish all my variables in the beginning? Any feedback is welcome!

[faint narwhal]

No

This is the opposite of too wordy

You literally haven't said anything at all

You didn't explain at all your last sentence

Why should that be true

You just stated it without proving it

@weary tiger

[long mica]

Can a graph be a group?Cause there exists graph automorphisms and isomorphism are only possible between groups.If a graph is a group under what operation and in what set?

[faint narwhal]

The set of automorphisms of a graph is a group @long mica

You could look into Cayley graphs of groups too

[pale epoch]

isomorphisms are only possible between groups? that's wrong

[weary tiger]

@faint narwhal That is exactly the assignment. We are just supposed to restate the statement but in a formal way.

[faint narwhal]

Yeah I guess it's fine then

[trim oak]

Ive been at this for hours now, I know it has to be simple.
I have to prove via induction that 5^n + 2 * 11^n is divisible by 3

Which would be like, 5^(k+1) + 2*11^(k+1) as the inductive step

Even just a hint would be very helpful

[trim oak]

Shit I did it I think

[weary tiger]

Im confused by this thing my book calls "definition by strong induction" of functions, and I'm just looking for clarification about the definitions my books uses from this text. Its a bit hard to follow, but I've ended up just writing it out for myself. What I'm confused about is defining the domain of h, and how the ordered n-tuple (k(0),k(1).........k(n)) is an element of it.

Domain of h is defined as the set of all functions " j " , with j having a domain of {0,1,.....p} for some p. The range of j is a subset of B. Given this definition of h, I'm confused as to how (k(0),k(1).........k(n)) is an element of its domain.

I understand the idea that ur computing all the previous values of your function to find the successive value, but im confused about what the specifics here are supposed to mean.

The book goes on to prove the theorem as well , if this helps you.

I'm familiar with the concept of the cartesian product of a set being expressed as a set of families, so it may be using that notation somehow. This would make sense with how the set {0,1,....p} is refrenced, reminds me of indexed sets.

The specifics here seem weird

wairt

IVE GOT IT

I UNDERSTAND IT

i hope no one spent time reading this

I was misunderstanding the book

anyway

[trim oak]

Did anyone else start to really struggle with induction?

I've been ok with math up till now

Kicking my ass lol a little disheartening

[stray reef]

induction can take some time to wrap your head around

at some point it just becomes another tool in your repertoire

is it the proofs you're struggling with, or the intuition? @trim oak

[trim oak]

Just the proofs :) the intuition mostly makes sense to me. I guess it is also showing some weakness in areas of my algebra etc. At least it's fun, so I don't mind hammering away at exercises.

[stray reef]

well yeah the remedy for difficulty with proofs is to do a whole bunch of induction proofs

if you want i can go over some of the proofs you've written already or give you some induction problems of my own

[trim oak]

It would be very helpful to have some more problems to solve, if you have any there! Thanks

[trim oak]

Thanks so much.

[long mica]

Is it true that if I swap the ith and jth row and than the ith column with the jth column in an adjacency matrix is the same as swapping the vertices i and j?

And is there a matrix that multiplied with the adjacency matrix swaps the ith and jth column and the ith and jth row in the adjacency matrix?

[stray reef]

swapping two rows AND two cols can't be accomplished in one matrix multiplication

however, it can be accomplished by a left-multiplication and a right-multiplication

by the matrix for row-swapping and the matrix for col-swapping respectively

[gilded monolith]

What would Y \ {∅} be equal to? Would it just be equal to Y?

[weary tiger]

that depends whether Y contains ∅ as an element

[gilded monolith]

If Y contained ∅ as an element, the resulting set would be Y but with ∅ missing

ok

[weary tiger]

yes

[gilded monolith]

I was just looking at a statement which is supposed to be "equivalent" (probably means that an "iff" is involved) to the axiom of choice. It stated that for every set X there exists a function on P(X) \ {∅} where f(A) $ \in $ A

[vital dew]

§Teotl:

[gilded monolith]

oops formatting

[stray reef]

the tex is atrocious yes

[weary tiger]

$P(X) \setminus \{\varnothing \}$

[gilded monolith]

Yeah \ is just ignored cuz its used for commands

probably

[glossy adder]

$\sm$

[vital dew]

CaptainLightning:

[trim oak]

Is this on the right path to being a correct proof

Sorry for the terrible photo I don't have a scanner :(

[vital dew]

JY1853:

[minor radish]

does anyone know any proofs for this that dont reference the binomial theorem?

[sharp mauve]

I love the probabilistic/combinatorics approach

[oak creek]

from a cursory glance, it looks like it might be proveable via induction

[sharp mauve]

Induction could probably work too yes

[proven shard]

The simple fact that

The cardinality of the powerset is 2^n

And nCk gives you the number of subsets with k elements

@minor radish

[minor radish]

Yeah that's what I was trying to prove it for

I got the cardinality of the powerset down the left-hand side and was trying to prove that it equals the right-hand side

Found that if you just multiply two cases for whether each element in the set is in our out for each element you get 2^n which was a much simpler approach

Thanks

[sharp mauve]

To create a subset of a set with n elements, you have 2 choices for each elements : either you choose it, either you don't choose it
since you do that choice n times, you have 2^n as the cardinality for the powerset

[minor radish]

Way better approach then what I was doing

Probably a bad habit but I generally stay away from induction because I've never been able to use it to derive something

You can only prove it if you think the condition exists in the first place

[naive saffron]

What are some applications of generating functions?

[sharp mauve]

The first great application is to calculate every moments for the given law

[weary tiger]

I hope I am understanding this right. I am tasked to find all non-isomorphic trees with 4 vertices.

My thought process is that in a tree with 4 vertices there should be 3 edges which means a total degree of 6.

So I think there should be only two such trees, the first one having degrees: 1,1,1,3 and the second one having degrees: 1,1,2,2.

Is this right?

[pale epoch]

yes

[trim oak]

Okay thanks @drifting arrow

[queen remnant]

is there a name for a dominating set whose complement is also a dominating set? I'm wondering about the complexity of determining the number of such sets for any given finite graph.

looks like "domatic partition of size 2" might be a name

[stray reef]

is anyone more up for a combinatorics problem than i am

i want to find the number of ways to place n points in 5 distinct boxes with no more than 3 per box

0 ≤ n ≤ 15, and the boxes are allowed to be empty

[azure lichen]

maybe the best approach would be to first find how many ways you can arrange the balls into the boxes without caring about the max (that should be straightforward enough), and then find how many arrangements have at least 4 balls in one box, which you can do by first placing 4 balls into one box (5 possibilities) and then distributing the other (n-4) balls in any arrangement (same calculation as in step one)

that will then give you X(n) - 5*X(n-4) possible arrangements, where X(n) is the number of ways to arrange n balls into 5 boxes (0 if n≤0)

@stray reef sound good?

[stray reef]

hmm

sounds good but i'm not 100% sure

[azure lichen]

I guess verify it explicitly for n=15. if it comes out as 1 it’s probably correct

I don’t personally see a flaw in my reasoning

but then that’s a problem of mine ^^

I’m also curious whether the formula would break down for n>15 or always give 0

would be quite cool if it actually still worked

I think it should still work

$X(n)$ is, according to a quick google, $\binom{n + 14}{14} = \frac{(n + 14)!}{n! 14!}$

[vital dew]

Sascha Baer:

[azure lichen]

hrm

[pale epoch]

that would give you 15 ways to arrange just 1 ball

[azure lichen]

doesn’t seem correct

[pale epoch]

this is wrong

its binomial(n+4,n) ways to arrange n balls into 5 boxes

[azure lichen]

oh, yea, I’m an idiot

[pale epoch]

it's some multiset theorem

[azure lichen]

yea yea I literally just put in the wrong values

[pale epoch]

number of multisets of cardinality 5 with elements taken from a set of cardinality n

[azure lichen]

annyoingly, it still appears wrong cause then it’d be $$\binom{n+4}{n} - 5\binom{n}{n-4}$$, which goes below zero at n=10

[vital dew]

Sascha Baer:

[azure lichen]

so I guess there is some error in the logic, too

oh, I see the issue

wait do I

no I don’t

[pale epoch]

just compute $$\sum_{\substack{a_1, ..., a_5 \leq 3 \ a_1+...+a_5=n}} \binom{n}{a_1,a_2,a_3,a_4,a_5}$$ i guess

[vital dew]

Lochverstärker:

[pale epoch]

^^

i mean it's a finite problem 🤷

[weary tiger]

Define the set A = {r, o, t, p, c} and B = {discrete, math, proof, proposition}. Define the relation R ⊆ A × B such that (letter, word) is in the relation if that letter occurs somewhere in the word.

Is my understanding of relations right here? The relation would look like:

{(r, discrete), (r,proof), (r, proposition), ..., (c, discrete)}

[stray reef]

well, the four pairs you listed are definitely in R

not sure how appropriate the ellipsis would be

but yes

[weary tiger]

well just because I don't want to write out everything

for the purpose of my question here

So a relation xRy doesn't always mean yRx, right? So in a matrix representation of a relation, just because (1,2) is true doesn't mean (2,1) is true. Is this right?

[stray reef]

yes x R y does not imply y R x

if it does, the relation is called symmetric

but in general that need not be the case

[weary tiger]

In matrix representation, what is the common orientation? Do you let the column represent the x or y?

So is (2,1) to represent row 2 column 1?

[pale epoch]

yes, row then column

although you would denote it something like $a_{i,j}$ for a matrix $A$ and not as a tupel

[vital dew]

Lochverstärker:

[pale epoch]

also to add to your first question, a binary relation on two distinct sets can't even be symmetric

(unless it is empty)

[ashen grove]

simple question what does the notation f: {0,1 }^n mean (as used in f: {0,1 }^n \rightarrow {0,1 })

like what does f:{0,1}^4 look like?

how is f: {0,1 }^n defined?

[faint narwhal]

@ashen grove Do you know what the cartesian product of sets is?

[ashen grove]

yeah like (x,y) x (1,2) = { (x,1), (x,2), (y,1), (y,2)}

[faint narwhal]

{x,y} x {1,2} = { (x,1), (x,2), (y,1), (y,2)} you mean

[ashen grove]

yes

[faint narwhal]

It's just that

[ashen grove]

so what does f: {0,1 }^4 mean? {0,1} x {0,1} x {0,1} x {0,1} ?

[faint narwhal]

{0,1}^4 is {0,1} x {0,1} x {0,1} x {0,1}

[ashen grove]

okay, great!

ty

[faint narwhal]

at least f has this as its domain

[ashen grove]

okay, that makes much more sense now

for it to be a function it'd have to take every element in this cartesian product and map it to either a 0 or a 1 correct?

[faint narwhal]

right

[ashen grove]

k

ty again

[stray reef]

{0,1}^n is the set of bitstrings n bits long
f: {0,1}^n -> {0,1} is a function from said set to {0,1}

[ashen grove]

{0,1}^2 is the set of bitstrings 2- bits long whose domain is defined by the Cartesian product: {0,1} x {0,1} = { (0,0), (0,1), (1,0), (1,1) } which is a function from this set to {0,1}, so then it would be valid to define a function f:{0,1}^2 -> {0,1}, where f is defined by: f(0,0)=0, f(0,1)=1, f(1,0)=1, f(1,1)=1

making sure this is putting what you said in words to a concrete example is correct

@stray reef

[stray reef]

sure.

[ashen grove]

k thanks!

[weary tiger]

When talking about the length of a closed walk, do you count both the starting and ending vertices when calculating length? For instance in the cycle (a,b,c,d,a), is the length of this walk 5?

[pale epoch]

is this cycle denoted by a list of edges or vertices

[weary tiger]

So if the cycle is denoted as vertices (a,b,c,d,a) vs <(a,b),(b,c),(c,d),(d,a)> then the lengths are different?

[pale epoch]

nvm, it's vertices

no, the length is whatever you define it

[weary tiger]

So if the question was "what is the length of walk of the cycle"

[pale epoch]

usually you count the number of edges

so in your example it's length 4

but nothing stops you from defining length differently

[weary tiger]

ah okay that makes more sense to go based on edges

[pale epoch]

if you deal with weighted graphs, it's usually the sum of the edge weights, so it makes sense yeah

[weary tiger]

Do graphs get heavy?

[pale epoch]

yes, very much so

you can assign weights to the edges

that's kinda how google maps works, it's just a big graph with vertices being locations and edges being streets

the weight of an edge is travel time or length or something else you care about

[weary tiger]

Ah so the weights can help decide what the best route is?

So google maps may be searching for a path with a lower weight?

[pale epoch]

exactly

that's dijkstra's algorithm

[weary tiger]

Are relations transitive and symmetric by default? So let's say you have some relation {(1,1),(2,2)}. This relation is reflexive. Is it symmetric? well if x = y and xRy then we know xRx is true, so yRx is also true, so it is symmetric? And the case of transitivity never comes up. So do we say it is not transitive? Or is it?

I hope that makes sense

[pale epoch]

they are not transitive or symmetric by default

consider (1,2), (2,3) on the set {1,2,3}

your given relation is reflexive on {1,2} but not on for example {1,2,42}

it is however symmetric and transitive

[weary tiger]

But 42 isn't in the relation

The relation only contains {(1,1),(2,2)}

[pale epoch]

yes

hence it is not reflexive on {1,2,42}

[weary tiger]

??

The relation is reflexive though

[pale epoch]

no, it depends on the underlying set

[weary tiger]

You're saying if you added some element then it would no longer be reflexive, that I do agree with

[pale epoch]

it is also a relation on the natural numbers

but certainly not reflexive there

not every element has to be in a tupel

[weary tiger]

It's just some arbitrary relation. Let's say the relation has one element (a) and also the relation {(a,a)} is the only relation

So we have a points to itself. So the relation is reflexive

Because all elements of the relation point to itself

[pale epoch]

what

[weary tiger]

I'm imagining a self loop on a

and a is the only element seen

[pale epoch]

what's (a)

[weary tiger]

a is just the name for some element in the relation

[pale epoch]

{(a,a)} is also a relation on {a,b}

but certainly not reflexive

[weary tiger]

That's fine, it may be. But we are not talking about the set {a,b}

[pale epoch]

you did not specify that

[weary tiger]

I said we are only looking at one element, a.

[pale epoch]

in your original question

you never sepcified the underlying set

[weary tiger]

Do I need to?

Okay then let me rephrase it to make more sense, this comes from a question and is how I became confused

[pale epoch]

obviously yes

you can't test reflexivity without knowing the underlying set

for symmetry and transitivity it doesn't matter

[weary tiger]

Take a set of people. Let xMy mean that x is currently married to y. Assume there is no polygamy. Is this an equivalence relation? My confusion comes from there is no transitivity here

There is never a case where xMy and yMz, it is not possible

[pale epoch]

ok

[weary tiger]

So xMz does not come up

[pale epoch]

if the case never comes up as you put it

it's trivially transitive

[weary tiger]

Okay, so it is transitive by default

[pale epoch]

because for all the cases (there are none) it's true

[weary tiger]

How can you claim it's true for all cases if there are none? Couldn't you easily say it is false for all cases (but there are none)?

[pale epoch]

notice the empty relation is transitive

[weary tiger]

ah, then that explains everything

[pale epoch]

to show it's false you need a counter example

you need one case where it is false

can you find one?

[weary tiger]

no

[pale epoch]

then it's true

[radiant bough]

assuming at least two people are married, it's not transitive

because xMy and yMx but x is not married to itself

[pale epoch]

also this, yes

[radiant bough]

(so it's also not reflexive)

you have to be careful with transitivity, because x, y, and z don't have to be distinct

so you get cases like the one above

[weary tiger]

But xMx is true

so it is reflexive and transitive

also can you then say if something is not reflexive, then it is not transitive?

[radiant bough]

what? based on the definition you gave, xMx should be false

[weary tiger]

You are always married to yourself

[radiant bough]

that's dumb lol

but fine

then yes it's transitive but you have to write down a sentence to prove it

[weary tiger]

ah okay

[radiant bough]

you can't just say "xMy and yMz never happens"

because it DOES happen, namely, if z = x

[weary tiger]

If there is no polygamy, so there is no xMy and yMz unless x=z.

Would that be sufficient?

[radiant bough]

I'd then say "and xMx is true" which verifies transitivity

[pale epoch]

people are married to themselves?

[radiant bough]

(yeah idk it's kinda a dumb thing but I guess you need it if you wanna make this an equivalence relation)

[weary tiger]

yes I belive so

[radiant bough]

also it's not true in general that transitivity implies reflexivity

[weary tiger]

Or at least, you can consider that solygamy is not ruled out

I never said that

[radiant bough]

you asked "also can you then say if something is not reflexive, then it is not transitive?"

and I answered

by saying "no"

[weary tiger]

But how could it be transitive but not reflexive?

[radiant bough]

the empty equivalence relation on a nonempty set

is transitive but not reflexive

[pale epoch]

will marry myself immediately for tax benefits

[weary tiger]

ah I see

so only true for a special case

[radiant bough]

I mean, the "proof" that transitivity and symmetry implies reflexivity is "given x in the set, find a y such that xRy. Then by symmetry we have yRx, and by transitivity we get xRx, so it is reflexive"

but the issue with that argument is obvious: if there aren't any y's with xRy then we're toast

[ashen ibex]

Please please please

I tried that multiple times and I just can't I dunno what to do anymore

Can I semd you guys an equivalence relation and a set, and can you find the quotient set?

Nvm I understood what they want lol

Weird

[pliant hemlock]

So I have some graph, with a start and end node and the objective is to find the shortest path. However instead of edge costs, I have vertex costs that are a function of the entry and exit edge.
So for example, in the path A->B->C, the cost for B would be F(AB,BC) - where F(a,b) gives the cost of the vertex given the entry and exit edge.
I am wondering how much I would have to adapt something like dijkstra's algorithm to work for this.

I don't know the exact terminology for some of the concepts, I will try to get some pictures to explain what I mean.

So, first up, an example graph:

I labelled the edges and nodes, with nodes A-G and edges 1-8

Now here I have the edges of the same graph, represented as a different graph (so each edge is now a node) The old graph is shown behind in faded colours.

finally, the different edge-edge paths in the dashed lines (separated in this image for clarity)

Does any of that make any sense? 😛

So an example path:

would have costs given by the following edges:

I think the solution is starting me in the face, but I don't know enough about graph theory to know for certain that it would be valid

To my knowledge, dijkstra's algorithm works on edge cost. However my original graph, does not have edge costs (and the vertex costs are not fixed per node but rather dependant on the edges used).
Now I can reframe the problem into a graph with edge costs (as in the example), however those edges don't actually exist in the graph they are just part of how I was thinking about the problem.

[oak creek]

quick question, so if you go from node A to B

that's free?

[pliant hemlock]

yep,

[oak creek]

only if you exit B

[pliant hemlock]

the only cost, is from 'crossing' a node, (so entering then exiting it)

[oak creek]

cant you just reword that as

you only charge for every edge except the first?

with identical edge costs for each node?

youll enter and exit a node for each step except the first

[pliant hemlock]

so I thought about doing something like that, but the edges dont have a fixed cost

[oak creek]

have costs built into the node

instead of building costs into each edge

you can just look at a list of costless edges

n use the cost built into the node

[pliant hemlock]

that's sort of what I was doing - each edge is 'free' and each node has a list of costs, one for each edge pair (although rather than storing the list of edges, I am calculating them as a function of the edges)

I will show a diagram trying to explain in a better way, wont take a sec

[oak creek]

ive seen it, but it's a little complex cause youve gotta find another way to manage how to get to the end node

[pliant hemlock]

yeah

So that image roughly describes the reason behind the problem - I have a graph of 'rooms' connected by 'doors', the doors are zero width, no cost, but the room cost depends on what path you take

so going from room B - C would have a different cost to room A - B

but solving the problem using the other type of graph means it doesn't actually have the start or end node

So there is a simplified version - the first one is what I have, the second one is one that I can run pathing algorithms on, but the second one has the start and end as an edge and not a node

I think I could make an algorithm that would solve this, but my main two concerns are overcomplicating it, and me possible missing something 😛 I tend to overcomplicate things and this problem seems to be an ideal candidate which is why I thought I would ask here in case there was something missing. I guess I will probably just have to do it the hard way and hope I didn't make any false assumptions.

I will give it a go and see what happens. Worse case scenario, it doesn't quite work and I have to go for a different data structure in my program

[analog sonnet]

The thing you're talking about all the time is called the line graph of a graph

https://en.wikipedia.org/wiki/Line_graph?wprov=sfla1

And I don't see why Dijkstra wouldn't work on a line graph

It will just tell you which edges to traverse in which order, as the vertices of the line graph are exactly the edges of your original graph

[arctic star]

@pliant hemlock how is the cost for crossing a Vertex calculated exactly?

[pliant hemlock]

@arctic star each edge has a vector X,Y and the cost is equal to the distance between those vectors

[pliant hemlock]

@analog sonnet thanks for the link, line graph is a lot more less wordy than how I was phrasing it :)
So I think I can get Dijkstra to work on the line graph without much trouble, the awkward bit will be the line graph looses the nodes from the original graph which includes the start and end. My plan so far is to temporarily add the start and end nodes to the line graph, connected to the edge-nodes it corresponds with. I think it will work, but it's not as elegant as I hoped since I didn't want to modify the original graph.
I have the original graph as a list of nodes (each with a list o edges) and a list of edges (each with the connected nodes) so I can treat it as an edge graph without any trouble, but adding the start and end nodes (to the line graph form) would either require adding a temporary edge to the base graph or perhaps storing the start and end nodes in a separate list and modify the algorithm to recognise that.

[cerulean ore]

My teacher is in full mood to ruin our academic career

She literally solved 1 out of 2 questions of PMI and she said that the chapter is completed.

[reef thistle]

What's the other question?

@cerulean ore

[cerulean ore]

One question was to prove 1+2+...+n = n(n+1)/2

another one was of divisibility of 576

When we asked her how 2 questions without any theory or just 2 questions are enough to complete a chapter, she said 2 questions are enough for practice.

[stray reef]

uh

sounds like a shitty teacher

2 questions isn't enough for anything

i mean, i can give you some of my own induction problems, if you want

but that's about all i can do to help

[cerulean ore]

That would be very much helpful!

[reef thistle]

Try proving more summation formulas on 1 variable

Yeah those are good candidates for induction

Like sum of squares 1+4+9+...

[cerulean ore]

It is very tensing that these teachers don't teach properly and also consume our useful time. Becoming a great Mathematician looks like a dream sometimes.

[reef thistle]

any past papers you have access to?

[cerulean ore]

Nope. @reef thistle

[reef thistle]

oh well

[cerulean ore]

Thank you very much, ann!

I will have to learn how to write the theory in induction first.

[reef thistle]

you are fine with that?

[cerulean ore]

With what?

[reef thistle]

"I will have to learn how to write the theory in induction first."

writing the theory in induction

whatever that means

[cerulean ore]

Like we write "Assume that results...."

[reef thistle]

like the structure of an induction proof?

[cerulean ore]

Exactly

She didn't teach us that so, going to learn that as well.

[stray reef]

i mean

that's a constant across all induction proofs

more or less

[devout willow]

That last problem from the list is pretty cool

[cerulean ore]

2^n < n!

that was a nice question

different from what I solved from the book

[weary tiger]

I have a question on an assignment but we haven't even touched graph theory in class hahaha

an idea on how to do this I would appreciate

[sour arrow]

Simple, try to apply a 3 coloring.

[weary tiger]

ok, as I said, we haven't even touched graph theory. therefore you telling me to apply a 3 coloring is meaningless

[ivory badge]

Read the question

[weary tiger]

well actually

[ivory badge]

next after that fails, try asking slightly more specific things

[weary tiger]

hang on

[ivory badge]

Defines a 3 coloring

[weary tiger]

well I can see how it would work, I just don't know how you would formally show it

[ivory badge]

For a slight clarification, a 3 coloring is where no adjacent vertices share a color and you have 3 different colors used

and to formally show it, you could go by contradiction

i.e. assume the two opposite points don't have different colors

then work with the other points to show they don't be workin

[weary tiger]

would you just define some general colors a, b, c to use

[ivory badge]

ofc

or r g b etc

or numbers

the colors don't matter

it's the coloring that's more important

[weary tiger]

ok ill just give it a shot. thanks

[ivory badge]

if you want help don't be afraid to ask, just make sure you read the question first of course

[young ferry]

Try coloring opposite corners two different colors and see if problems arise

[ivory badge]

wow its almost like i said thta

[young ferry]

Oops my b

[ivory badge]

nah it's fine

[weary tiger]

hahaha

[ivory badge]

just my dumb ass

also i fucked up saying it anyway

[young ferry]

At least we were dumb together 😍😍😍

[sour arrow]

Actually, might be easier to start with the center

The colors are forced if you do

[ivory badge]

Yeah probably

[sour arrow]

Any triangle has to have all three colors, of course

[ivory badge]

imagine having a triangle using only 2 colors

[weary tiger]

that's what i like to call a pro gamer move

well ive labelled the square in the center

[young ferry]

Those outside triangles can each go one of two ways

[weary tiger]

ooh I might have it

[sour arrow]

Indeed, the outer triangles have to be alternating. That's a problem though

[weary tiger]

oh I would also love a hint on an induction problem

[ivory badge]

Well, how about your base case?

[weary tiger]

that is what I have tried so far

hopefully that's readable

[ivory badge]

it's not the most readable but i'll manage

[weary tiger]

hahaha ok thank you

[sour arrow]

You'll want to clearly state your base case, and your inductive hypothesis. Notably, the inductive hypothesis is of the form "Assume P(n) is true, proof goes here, therefore P(n) implies P(n + 1)"

I don't see "Assume P(n) is true" anywhere. The inductive step isn't clear

[weary tiger]

fair enough. I will state that more clearly

[sour arrow]

I think the correct way to go is "Assume a given circle has such a point, then a circle with an extra 0, 1 also has such a point"

[weary tiger]

ooh, interesting

[sour arrow]

Hmm. This question is interesting, I'll think about it

[weary tiger]

I see

[faint narwhal]

take a better picture and I'll take a look

[sour arrow]

Let's say a circle has such a point. We'll throw a new 0, 1 somewhere in there.

If the 0 comes before the 1, then there's no problem. The same point works for the new circle.

If the 1 comes before the 0, then I don't know help

[weary tiger]

that's where I came to a halt as well

[ivory badge]

i mean, you can simply rotate back a point counterclockwise

that doesn't guarantee your thing, but gives you an idea hopefully

[weary tiger]

what do you mean by that?

[ivory badge]

If your point doesn't work, you could try starting back by one step

[faint narwhal]

I'm confused, can't you just start at a 0 and take the next 1 and then reduce it down to the lower case?

[ivory badge]

Yeah you almost can, but the case where you have 0 1 1 makes that slightly messier

[faint narwhal]

why is that messy

Ah hm I see

[ivory badge]

yeah you can't just pick some random 0 1 spot

but it's clear you have to start on a 0

[weary tiger]

for a circle that satisfies the property. at every point around the boundary, the number of 0s between the start and that point must be greater than or equal to the number of 1s

[ivory badge]

you're given that it has equal 1's and 0's

[weary tiger]

that's right

[sour arrow]

I'm not sure my induction works! Maybe this isn't the right angle of attack.

[weary tiger]

the quesiton does say to do induction on the number of points on the boundary

[faint narwhal]

maybe contradiction?

Assume that it doesn't have one and see if this contradicts the inductive assumption?

[weary tiger]

I've never used contradiction in induction before but can try

[ivory badge]

i mean, induction is just about showing that P(n) -> P(n+1)

(or the strong version of course)

[faint narwhal]

doing contradiction here basically amounts to showing the contrapositive

[weary tiger]

so could you assume P(n+1) doesn't hold as well as that P(n) does hold and show that creates a contradiction

[faint narwhal]

that not P(n+1) -> not P(n)

[ivory badge]

or, in other words, if it's impossible to do the rotational thing, then you can remove a 1 and a 0 and make it still remain impossible

hm, i'm not sure if it would be that you can remove a certain pair or if you can remove any pair tbh

i haven't quite formally worked it out myself

[sour arrow]

Yeah I got stuck on the logic lol

[weary tiger]

might just accept losing 2 marks tbh

[ivory badge]

in any case, i'm p sure it'd be an existential thing on removing, since it's a universal thing on adding

[weary tiger]

no big deal

[ivory badge]

There exists a pair you can remove to keep impossibility as a negation of adding any pair preserves possiblity

[sour arrow]

Ah you're right

Well that seems reasonable

This method is actually pretty neat, we're inducting downwards

[ivory badge]

anyhow, picking any n, it's clear that following your contrapositive down, you arrive at the base case P(1), which is clearly true, so your implications must be false, and they stem from your assumption that P(n+1) is impossible or whatever (i'm clearly not going down the formality hole here)
Because of this, you can induct on this backwards induction and continue it up

My argument is informal as hell and I leave it up to you to formalize it

[weary tiger]

this seems a lot more complicated than it should be at our stage. thanks for helping tho

[ivory badge]

kinda like this

induct on a sequence of inductions

this is absolutely not the most efficient means by which to do this

and I highly doubt this is how it was intended to be done

but its a method

(note it's just induction on a sequence of statements Q(n) which assert that -(-P(n+1)->-P(n)) or whatever it was)

I wouldn't recommend ever pulling this diagonal induction shit on anything really, i just think it's an interesting tool and like to use it

[weary tiger]

we have done about 1 week of induction so yeah I doubt this was an intended method hahaaha

[ivory badge]

yeah absofuckinlutely not

but i mean, induction is just P(n) -> P(n+1)

[weary tiger]

ye ye

[ivory badge]

so like, just make your P's a chain of other statements

honestly if you pull that shit the prof will probably vomit on the fuckin spot

[weary tiger]

good

jk jk

[ivory badge]

make sure to include an atrocious diagram like mine :)

[vital dew]

Darkrifts:

[naive saffron]

@ivory badge how do you create that using latex?

[ripe ferry]

tikz

probably

[ivory badge]

Tikz-cd to be precise

[naive saffron]

Ok

And can you show me the code for that specific tree? @ivory badge

[ivory badge]

No

I'm on mobile

It's not fancy anyway

[naive saffron]

ok

[sour arrow]

@weary tiger
GOT IT

Assume the 1 gets placed before the 0. There are two cases:

• The path is still good and nothing needs to be changed

• The path is now bad. That is, in the original circle, there was exactly as many 0s as 1s up to this point, and adding the extra 1 made it so there is one 1 too many.

However, this implies that on the original circle, the rest of the path maintained the rule. That is, after this point, one must have seen more 0s than 1s at any point in this circle. Therefore, on the new circle, it must be the case that starting after the newly placed 1 is a valid starting point.

[weary tiger]

👏

I am thoroughly impressed

[sour arrow]

Me too lol. That question was bugging me since we brought it up. Thanks for the awesome brain teaser

[young ferry]

You can also pick a starting point and graph (amount of 1s-amount of 0s)

[weary tiger]

I won't put that in my assignment b/c its not my work but I'm happy you solved it 😄

[young ferry]

The deepest valley in that graph is a valid starting point

No induction but it works

[sour arrow]

Oh duh you're right

Now it seems very clear that this property should exist

I can't believe the inductive proof works based on that little info

[young ferry]

Is the duh aimed at me?

[sour arrow]

Yeah, nice observation, it makes why the property should be true crystal clear

[young ferry]

If so I’m honored

Hooray!

@weary tiger your teacher has some cool practice problems, keep them coming

[queen remnant]

given a graph, is there an algorithm to actually move the vertices around such that it has the minimum crossing number, as opposed to just calculating the theoretical minimum crossing number?

[faint narwhal]

An algorithm to move around the vertices so that it has minimum crossing number must be harder than the algorithm to calculate the minimum crossing number

And by harder, I mean slower

[minor radish]

anyone have any good combinatorics practice sets with answers? i have an upcoming exam and need some more prep material since i keep making simple mistakes

[reef thistle]

If the graph is planar, then there is an algorithm.

[faint narwhal]

@reef thistle that's interesting, can you describe it?

[reef thistle]

Well, I can't

I didn't learn the algorithm, but I know it exists

[faint narwhal]

Hm okay that's interesting

[reef thistle]

http://sci-hub.tw/https://doi.org/10.1016/0020-0190(95)00020-D might be what you are interested in

[faint narwhal]

Oh yeah nice

thanks

[cerulean ore]

I am facing problems with proving inequality inductions

Getting to the right part or to the left part is difficult

[reef thistle]

Example?

[feral rapids]

Anyone know any papers/results on frequency+time vs quantization noise for a given sampling rate? The x and z axis having frequency and time while y axis having quantization noise. Instead of time, it can also be made as number of pulses of the wave.

What I can see is as the frequency starts nearing Nyquist frequency/2, if I try to take individual pulse points and try to reconstruct, I get like something with a very low amplitude and somewhat lesser frequency than what my input is supposed to be for the first pulse. this parameter keeps changing as the pulse number increases. At nyquist frequency/2, the pulses essentially align at 0 which makes it highly distoeted (since 0 value).

[feral rapids]

I'm a little confused.. because, looking at my intuition, it seems that for decent data integrity, sampling frequency should be 4x(max source frequency) and not just 2x. What am I missing here?

[cerulean ore]

@reef thistle Not any specific example but, when I see the solution I am able to understand it.

[ashen ibex]

Is there a good website/problems worksheets to practice problems? Especially things with cardinality, cantor theorems and functions?

[faint narwhal]

I'm not sure what you're looking for with practice problems?

[ashen ibex]

Like, questions from exams and solutions

Especially about functions, cardinality and cantor theorems (like proofs with those things etc )

[faint narwhal]

What do you mean by functions?

Do you mean stuff like, show that the composition of two surjective functions is surjective?

[ashen ibex]

Yeah and creating surjective/injective/both functions for certain sets

Use of cantor-schröder bernstein theorem

And proofs with these stuff

Checking the cardinality א/א_0 etc of a set, combining functions with relations etc etc

Basically everything

I look for like worksheets with solutions/websites to practice these problems etc

@faint narwhal

[faint narwhal]

This is advanced math, you're not going to find worksheets with this stuff, not websites

Your best bet is to find a textbook with these topics

[ashen ibex]

But I found websites to practice advanced problems with linear algebra

There has to be something with discrete math

There is nothing in my language literally there aren't any books, just 3 books that I could find and none of them helps

[faint narwhal]

I think another thing is that

For these topics, you don't really get problems about them

It's just kind of foundational stuff that you understand and move on

Like cantor-schroder berstein isn't something that's really "used"

[ashen ibex]

But there's an exam obviously in the end of the course

And if you wanna excel in the exam you also have to practice answering this type of questions

Btw I found something

SolutionsToFunctionsActivities.pdf

[faint narwhal]

This is stuff that's taught in like #precalculus

[ashen ibex]

Darn

[faint narwhal]

The book

How to Prove it by Velleman

has some related chapters

chapters 4,5,7 seem relevant

[ashen ibex]

Is it an online book

[faint narwhal]

No but libgen exists

[ashen ibex]

Thanks so muchhhhh

[hasty cargo]

Hmm I want to prove between any two different real numbers there exist a rational and irrational number

I said, choose two numbers a and b, assume $a>b$, and pick a $n \in \mathbb{Z}$ such that $a>b+\frac{\sqrt{2}}{n}>b$

[vital dew]

Itadakimasu!:

[reef thistle]

hmm

probably all you need to choose a n > 1/(a-b), then you can find a rational number with denominator n.

[hasty cargo]

Oh

That’s all..?

[reef thistle]

for irrational

just take a-sqrt(2), b-sqrt(2) and do the same thing

[hasty cargo]

Sorry I don’t really follow haha

[reef thistle]

rational is just that

Choose n > 1/(a-b) by Archimedean property, then (a-b)n > 1, so an > 1+bn >= floor(bn)+1 > bn

[hasty cargo]

Ohh I kinda see what you mean

[reef thistle]

(floor(bn)+1)/n is our rational

[hasty cargo]

Urr okay, I just didn't know if I was allowed to use the floor function in my proof

Because the book hadn't covered it yet

[reef thistle]

hmm

How about proof by contradiction?

Suppose there are no natural numbers in between

Can we take the least natural number bigger than bn?

[hasty cargo]

I'm not sure what that means urrr

[reef thistle]

There exists at least one integer bigger than bn

take the least one.

every set of integers (bounded below) has a least element, so you can take the least one

you need the bounded below to transform your set of integers into a set of naturals by subtracting the lower bound

[young ferry]

@hasty cargo you can create a rational number smaller than the difference between the two reals using the methods described above. Pick any integer larger than 1/(a-b) and take its reciprocal for instance

Once you have this really small rational, start adding it to itself over and over until you hit a spot between a and b

There’s no way you’ll skip a and b at the same time during this process because your rational is smaller than their difference

Then you just have a multiple of a rational which is necessarily between your two reals

[weary tiger]

I just want to say I finished my Discrete Math class with an A and I have to thank this discord a lot for helping me when I have questions on homeworks/readings!

[opal crescent]

gj

[weary tiger]

Thank you, @opal crescent

[long mica]

Is a graph a tree if and only if it has no cycle or it's only an if statement?

[reef thistle]

Well

you can have a forest

If a graph is a tree, then it has no cycles

but if a graph has no cycles, it is a forest

unless you have the connectedness condition

[pale epoch]

I'd like to point out that the sentence "An acyclic graph is called a forest, a connected forest is a tree" is a work of art itself

[cerulean ore]

Give any five partitions of set of Natural numbers

what does the question means?

[ripe ferry]

make 5 different partitions of the naturals

[dense thicket]

they ask you to divide set of natural numbers into 5 sets with empty intersection such that their sum gives N

[weary tiger]

An example with a finite set would be where the set A is {1,2,3,4,5,6,7,8,9,10}. Then any 5 partitions of A would be subsets of A where none of the subsets have any elements in common and if you take all 5 partitions and combine them you get A again

So {1,2}, {3,4}, {5,6,7}, {8}, {9,10} could be 5 partitions making up A

[pale epoch]

{{1,2}, {3,4}, {5,6,7}, {8}, {9,10}} is just a single partition of the set {1,2,3,4,5,6,7,8,9,10}

[weary tiger]

yes, exactly

[ripe ferry]

no, thats a partition into 5 sets

[pale epoch]

the elements of a partition are not called partitions

[ripe ferry]

they asked for 5 partitions

[stray reef]

there are tons upon tons upon tons of possible partitions of N

if you know what a partition is, it really isn't that hard to write out five of them

[young ferry]

Isn’t the number of partitions for a natural number in general an unsolved problem

[stray reef]

not that kind of partition

not partition into a sum

but partition of a set into a union of disjoint sets

[neat moss]

what is discrete math

[pale epoch]

the mathematical study of discrete structures

[pliant hemlock]

Is that the category graphs falls into?

[ripe ferry]

yes

[pliant hemlock]

ohh, from googling it it covers things like logic as well. Looks like an interesting branch of maths 😄

[pale epoch]

tbh it's not really it's own branch

it's a collective term for multiple subjects

[pliant hemlock]

ah, fair enough

[pliant hemlock]

Can I used Dijkstra's algorithm in the calculation of betweenness centrality? From what I understand, betweenness centrality is the measure of the number of shortest paths that pass through a given node.

From what I understand, Dijkstra's can find a shortest path between a given node and every other node. Then, I could run it for every single node in a graph to get a shortest path for every single node pair in the graph. However, I would need to be able to total up the number of times a path goes through a node. Additionally I would need to be able to find multiple same length paths between a node pair rather than just the best one. These two issues (especially the latter one) would seem to require a bit of modification to the algorithm or something, but am not sure of the best approach.

For the first issue, I could just follow every single of the shortest paths adding one to each node it goes through, which would probably work although might not be the most efficient approach. However for the second one I would need to modify Dijkstra's algorithm to not just calculate the best path, but to calculate all best paths (if there are multiple 'best' paths with the same length).

[peak crag]

@pliant hemlock this is more cs than discrete math, but for finding the shortest path between all pairs there are better solutions than running Dijkstra n times. check Floyd-Warshall or Johnson's algo

[pliant hemlock]

@peak crag Thanks, I figured it would probably be the case that it wouldn't be an optimal solution, thanks for the pointers 🙂

[minor radish]

found this problem online and was unsure of why this would be the answer

i was under the assumption the answer would be 2^n

[faint narwhal]

Why?

Just because you tried it for the first three cases doesn't count

[minor radish]

since the maximum number of parts the plane can be divided into is equal to the summation of choosing different numbers of circles from 0 <= i <= n since each part would be an intersection between those circles

and then i simplified (n choose 0) + (n choose 1) + ... + (n choose n) to 2^n

[faint narwhal]

Are you sure you can draw circles such that each different subset of circles you pick gives you a new region?

In other words,

Are you sure you can draw the circles in the plane so that they form a Venn diagram

[minor radish]

either im interpreting the question wrong or it doesnt say otherwise

as long as they can intersect they should be able to form a venn diagram

[faint narwhal]

Do it with four circles then

[minor radish]

oh shoot

i see what you mean

i hadnt considered that

[spring temple]

Hehe

[minor radish]

wait nvm

it still works

[faint narwhal]

Take a picture

[minor radish]

wait no it doesnt

im so sorry

thank you

yeah i got that same answer now

[cerulean ore]

Example 10, (b) part, how is the function one-one?

[faint narwhal]

What the fuck

Both (a) and (b) are just wrong

Is this book trolling

[cerulean ore]

And for example 11, isn't greatest integer function not one-one

[faint narwhal]

What book is this

This whole page is just riddled with errors

[naive saffron]

Wtf

That f is not onto

[cerulean ore]

This book is standard book of our college ;_;

[faint narwhal]

What's the title

[naive saffron]

Wtf

[naive saffron]

The function f:A->B is onto if for every element in f(A), there is an element a in A such that f(a) is that element

That is what the book is suggesting

I don’t even know anymore hmmmmm

[cerulean ore]

Thank you for helping!

Which book would be better to learn functions?

Example 10, part (a)

How did they prove it to be onto?

And isn't the one-one part incorrect because the question is x^3-3x

[tropic cedar]

,rotate -90

[cerulean ore]

Thank you mat! Sorry for that.

[tropic cedar]

No problem!

But never do that again

[cerulean ore]

How do we prove x^3-3x to be one-one?

And onto

[faint narwhal]

Onto kinda comes from calc

And looking at the graph

[cerulean ore]

So, either it should be strictly increasing or decreasing?

Is this the correct way to prove one-one

[tropic cedar]

But f is not one-one

[cerulean ore]

;_;

[tropic cedar]

Onto you can see looking at the limits as x approaches +inf and -inf if you already know limits

[cerulean ore]

How it is not one-one

[tropic cedar]

Oh wait, f' is actually to be corrected first

[cerulean ore]

Fuck

[tropic cedar]

It's 3x^2-1

[cerulean ore]

Yeah

So, not even onto