discrete-math

[sonic shadow]

So indeed, our sequence does have a nice generating function, but this function has an actual input in SOME neighborhood

So on, and so forth

i remember using gen. functions to count shit, it felt like black magic

it still actlly is

I frogot how to count w this shi 😂

[compact yacht]

It seems to me :v

[rapid kernel]

If in order theory, if I let X={1,2,3}, then S= { {1}, {2} } has 2 maximal elements ( S under set inclusion order), right ?

And if I define the set inclusion order on P(X) then S has many upper bound and none of them belongs to S, right?

[grand totem]

Correct, yes

[storm pumice]

did no one ever encounter this?

[vital dew]

Results provided by WolframAlpha

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

Requested by bee2660

Results provided by WolframAlpha

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

Requested by bee2660

[storm pumice]

you cannot multiply with the 2

2|E| says that every vertex is encountered two times and in handshaking lemma you divide it by two to get rid of one encounter

it's still 8

2 |E| = 8 and |E| = 4

E is the quantity of edges (?) sorry I have this course in german so the english jargon is completely unknown to me

No, dw

did you have the chromatic number tho?

in class I mean

[fossil mural]

...ok actually yeah you're right, the chromatic number is 3

hang on no it isn't

it's 2

[stray reef]

no

well

[fossil mural]

or is this the wrong graph

[stray reef]

that's an invalid coloring

[fossil mural]

wait hang on yeah that's not valid

[stray reef]

but its cn is 2

cause it's a tree

all trees are 2 colorable

[fossil mural]

there

[storm pumice]

With the question being " is it colorable with max 4 colors" does it mean that four is an upper bound and therefore the term is actually correct? But if x(G) =. 4 then the term is incorrect 4 <= 3

yo i got it

thank yall tho

[odd heart]

"Being colorable with 4 colors" means that 4 colors are enough, but doesn't mean you can't color it using fewer colors, so every 2-colorable graph is also 100-colorable.

Meanwhile the chromatic number is the optimal number of colors, so the smallest n such that the graph is n-colorable

[storm pumice]

yes, but that's not the question and gets me 0p

[odd heart]

I didn't really read the history 😅 just commented on the distinction between n-colorability and chromatic number.

[storm pumice]

If the chromatic number is the optimal amount of color and smallest n, does that mean that if the chromatic number is bigger than the max. color, it is wrong? Or can I say that because it is colorable with 3 colors it can also be colorable with 2? …that seems flawed tho. Im asking because I wanted to use the term I send in yesterday to proof that (1,1,2,2) is colorable with max 2 colors but cn turned out to be 3. (the graph is obviously colorable with max 2 colors)

[odd heart]

If the graph is colorable with 2 colors, then its chromatic number can't be 3

It can be 2 at most

The chromatic number is the smallest number of colors that suffices to color the vertices of the graph.

[odd heart]

This graph is 2-colorable; it is also 3-colorable, but its chromatic number is 2.

Because it can be colored with 2 colors, and not fewer.

I'm not familiar with this inequality, but I read is as saying the chromatic number is at most the right side.

So if the right side is slightly over 3, then the chromatic number is at most 3, and the graph is 3-colorable, but it might be colorable using fewer colors still

As is the case with the tree

[storm pumice]

given this it also works for (1,1,2,2) x(g) <= 3 if it is at most 3 it can be also 2

[odd heart]

Precisely

Heck, it could even be 1

Although a graph with chromatic number 1 is a sad one

But either way, the inequality only gives you a range for what the chromatic number is.

[storm pumice]

I see... but other than proving it by drawing an example I would have to prove any other inequality in an exam

thank you so much tho, it definitely clicked now

[odd heart]

Well, if you want to find the chromatic number exactly, one inequality probably won't be enough, yeah. I don't do graph theory very often so I don't know all the tools.

Comedy option, find the chromatic polynomial, for which there's a precise algorithm, and then find the smallest natural number for which the polynomial is nonzero

For a small graph that's fairly doable

Although gets very unwieldy very quickly

[storm pumice]

to get this right: this proves that it is max. colorable with max 4 colors because the cn is at most 3. In graph (1,1,2,2) it is also proven because if the cn is at most 3 it can be also less which fulfils the limitation of max 2 colors (?)

[storm pumice]

maybe fairly doable but also not worth the 1p at all might even lose all my hair in the process

[odd heart]

If the CN is at most 3, then the graph is colorable using 3 colors. This also means that it is colorable using 4 colors, 5 colors and so on.

What all of this tells you nothing about, is whether the graph is colorable using 2 colors.

[storm pumice]

welp

so I can only prove the second one by drawing or your crazy idea?

[odd heart]

Well, if you explicitly show a 2-coloring of a graph, then you've proven it's 2-colorable.

[storm pumice]

duh

but it's weird that it doesn't work with the inequality

I appreciate your help, thank you!!!

[static briar]

Can anyone explain how 100x = 140mod33 implies x = 8mod33

[obtuse magnet]

100x=100x-3(33)x=100x-99x=x mod 33

And 140=140-33(3)=140-99=41=41-33=8 mod 33

So x=8 mod 33

The key is that a=b mod n and c=d mod n implies a+c=b+d mod n and ac=bd mod n

And everything I said follows from that and the fact that 33=0 mod 33

[ocean socket]

is this an adequate definition of total ordering in first order logic?

$\forall x,y \in S ((x < y) \oplus (x > y))$

[vital dew]

Jonas!

[ocean socket]

Or strict total ordering i suppose my book is rly old i think it might be wilding

[tame bronze]

x^2 isn't one-to-one (injective) or onto (surjective) right?

[solar marsh]

Where can I find a proof that Menger's theorem implies Dilworth's theorem?

[little prism]

depends on the domain and codomain

[tame bronze]

domain are integers and codomain is all positive integers
Z > N

The solution in the textbook says it is x^2 + 1, I'm wondering why it isn't just x^2

[little prism]

!original

[lofty cloud]

Please show the original problem, exactly as it was stated to you, with the entire original context. A picture or screenshot is best. If the original problem is not in English, then post it anyway! The additional context might still be helpful. Do your best to provide a translation.

[little prism]

often 0 isnt included in N, depends on the book

[tame bronze]

for d)

[little prism]

well if f(x)=x^2, then f(0)=0 isnt in the set of positive integers

[tame bronze]

oh so 0 isn't considered positive then

[little prism]

yeah

[tame bronze]

ok thank you

that makes more sense now

[little prism]

if you want to include 0 you would say non-negative

[ocean socket]

does partial ordering work for general equivalence relations =, or is it the one we all know and love? im thinking specifically of the antisymmetry requirement using it. and if so, does that mean that Zorns lemma is only true on sets which have a specific defined equivalence relation?

[brave rock]

Any equivalence relation can be made to be equality. We simply take the set of equivalence classes.

We need equality for a partial ordering; one that doesn't have this property is only a preorder.

However the relation a <= b and b <= a is an equivalence relation, and once we take the set of equivalence classes, the <= relation descends to become a partial order on these classes.

[ocean socket]

so can i use two different definitions of =, where they are both different equivalence relations and it will still work or?

[brave rock]

There is only one equality.

I don't know what you mean by this.

As I have said, if you do not have antisymmetry, you are not working with a partial order but rather a preorder.

[north swan]

how to start set theory

[brave rock]

Read a book

[weary tiger]

What is discrete maths?

Never heard of it before

[brave rock]

Discrete mathematics is a common title for a course where students first encounter important concepts such as sets, functions, and relations, and often where they first encounter proofs.

[sudden torrent]

Graph theory for example

There's this famous problem called the 7 bridges of Konigsberg (now Kaliningrad in Russia)

Where this mathematician called Euler wanted to know if it was possible to cross all 7 bridges without crossing one of them twice

Combinatorics is also part of discrete maths

So are recurrence relations, like if I have next term = 2 * previous term + 3 * this term, so you need the previous terms to calculate the next term

Number theory, for example the Chinese Remainder Theorem

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

And lastly, there are some connections with polynomials and calculus, for instance generating functions (a way to write a list of numbers or probabilities by storing them as the coefficients of a polynomial)

It's a completely separate area of maths to the maths you are learning in high school

[weary tiger]

Interesting

I will take a look for any maths I see on this channel

[sudden torrent]

Cool

[brave rock]

It's called a turnstile and it has a few meanings: https://en.wikipedia.org/wiki/Turnstile_(symbol)

[near kiln]

Is there an easier way to establish validity for these? Like, am I looking at this in a different way? (Not my answer, btw.) I am really confused, like I easily missed out on a rule.

[brave rock]

Ask your teacher or look in your textbook/notes

[left shadow]

does anyone know warshalls algorithm for finding transitive closure

In an iteration of warshall's algorithm, can a path that needs to be made already exist?

On W1, i found a path that has v2 as its only interior, which is v4, v2, v1 . However, the (v4, v1) edge already exists. Is this fine or have i done something wrong?

[true venture]

Say I have two partitions of the same number m.
Ex. m=8 , with the two partitions being (4,2,2) and (2,2,2,2).
We can see that (4,2,2) can be made by adding terms of (2,2,2,2) using each only once.
Ex. if (1,7) and (2,2,2,2) were chosen you cannot do this.
Is there a name for this kind of relationship between two partitions?

[polar heart]

any hints for c?

I have already answered a and b

[polar heart]

I've seen the proof using G** ~ G, but I can't find the proof of the fact G** ~ G that I understand.

[rapid kernel]

If I have a family of sets which is finite, then can I say it always has a maximal element ?

[stray reef]

maximal in what sense

[north swan]

which

[stray reef]

which part(s) do you need help with?

[misty storm]

hi can someone help with this question:
Prove using induction that, for each integer n ≥ 1, 5 + 5^2 + 5^3 + · · · + 5^n = (5^(n+1) − 5)/4.

[cerulean radish]

!status

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[misty storm]

2

i am at the part where we prove the LHS is same as RHS

[cerulean radish]

That's the entire question though, did you mean the inductive step?

[misty storm]

oh yes

5 + 5^2 + 5^3 + ... + 5^k + 5^k+1 = (5^(k+2)-5)/4

[cerulean radish]

Right, so it's assumed that
[ 5 + 5^2 + 5^3 + \dots + 5^n = \frac{5^{n+1}-5}4 ]
And we want to show that
[ 5 + 5^2 + 5^3 + \dots + 5^n + 5^{n+1} = \frac{5^{n+2}-5}4 ]

[misty storm]

this step

[vital dew]

A Lonely Bean

[misty storm]

yes this step

then i sub in the 5^n

which we already found

from assumption

[cerulean radish]

You mean you rewrote the sum
[ 5 + 5^2 + 5^3 + \dots + 5^n + 5^{n+1} ]
as
[ \frac{5^{n+1}-5}4 + 5^{n+1} ]
?

[misty storm]

yes yess

[vital dew]

A Lonely Bean

[misty storm]

yess

[cerulean radish]

Have you tried simplifying the latter?

[misty storm]

yeah but idk what to simplify

hold on let me try something

[cerulean radish]

Make common denominators

[misty storm]

like this?

oh i forgot to write it as 4 x 5^k+1

but yeah

[cerulean radish]

Right, write $4\cdot5^{k+1}$ instead of $45^{k+1}$ though

[vital dew]

A Lonely Bean

[cerulean radish]

That's it, yeah

[misty storm]

oh? how does that prove the LHS is same as RHS

[cerulean radish]

Can you simplify $5^{k+1}+4\cdot5^{k+1}$?

[vital dew]

A Lonely Bean

[misty storm]

yeah it becomes 6 . 5^k+1

oh wait

5.5^k+1

[cerulean radish]

Right, it becomes $5 \cdot 5^{k+1}$

[misty storm]

omg i get it now

[vital dew]

A Lonely Bean

[misty storm]

thank you!

theres this other question

i don't even know how to begin this one

[cerulean radish]

The base case should be trivial; For inductive step, to avoid too much algebra, I would rewrite $u_{n+1}$ as $u_n + 2\frac{u_n}{u_n+1}$, your goal is to then show that
[ u_n + 2\frac{u_n}{u_n+1} < 2n + 2 ]
Given that
[ u_n < 2n ]
You already know that $u_n < 2n$, so it is sufficient to show that
[ 2\frac{u_n}{u_n+1} < 2 ]

[vital dew]

A Lonely Bean

[misty storm]

could you elaborate on how you rewrote u n+1 ?

[cerulean radish]

The first step there would be
[ \frac{u_n^2 + 3u_n}{u_n+1} = \frac{u_n^2 + u_n + 2u_n}{u_n+1} ]
Can you see what's next?

[vital dew]

A Lonely Bean

[misty storm]

hmmm

not too sure

[cerulean radish]

Can you anyhow factor $u_n^2+u_n$?

[vital dew]

A Lonely Bean

[misty storm]

oh un(un+1)

oohh i see it now

thank you so much!

[true iris]

Hi i someone can help me with these exercice Un is equivalent to sqrt(2/n) On note means=We note , Montre que=Show That, Justifer que=Justify this , En utilisant la relation définissant un, montrer que=Using the relation defining Un, show that ,
Deduce a simple equivalent of vn

[stray reef]

@true iris est-ce que la question nous dit autre chose de la suite (u_n) sauf qu'elle est équivalente à sqrt(2/n) ?

par exemple la relation mentionnée sous la lettre (e)

[true iris]

ah oui je pas fait gaffe c'est la suite d'un exo

un est décroissant

[stray reef]

hmm

ok

alors on sait que u_n ~ sqrt(2/n)

sais-tu la définition de la notation o-minuscule ?

[true iris]

oui

un=sqrt(2/n)+o(sqrt(2/n))

[stray reef]

non c'est pas la définition de l'o-minuscule

[true iris]

se quand sa tend vers 0

sa veut dire que c'est négligable

[stray reef]

non

[true iris]

ah oe ?

[stray reef]

pour deux suites $(a_n), (b_n)$ telles que $(b_n)$ contient un nombre fini de termes égaux à zéro (pour simplicité), on dit que $a_n = o(b_n)$ si $\lim_{n \to \infty} \frac{a_n}{b_n} = 0$.

[vital dew]

Ann

[stray reef]

pk pa ékrir tou lé mo an fonétik ?!

(désolée, j'ai un peu de difficulté avec ton orthographe ...)

[true iris]

désolé même mes prof on du mal

[stray reef]

tes profs sont-ils des francophones natifs ?

[true iris]

Je sais pas mais moi non

[stray reef]

ok

alors

pour vérifier que v_n = o(sqrt(1/n)) il faut juste calculer la limite de v_n/sqrt(1/n)

évidemment quand n tend vers +∞

[true iris]

un-sqrt(2/n)=0 ?

[stray reef]

non

cette égalité n'est pas vérifiée pour tout n ∈ N

on sait même pas si jamais elle est vraie

[true iris]

ah

[stray reef]

ne confonds pas la notion d'égalité avec la notion de tendence

[true iris]

en peut écrire les équivalent avec des petit o

[stray reef]

u_n - sqrt(2/n) est o(sqrt(2/n)), d'où découle qu'elle tend vers 0, mais la tendence vers 0 ne te suffira pas

il faut utiliser le petit o au lieu de l'affaibler

en effet "tend vers 0" est synonyme à o(1)

[true iris]

pourquoi à o(1)

un=sqrt(2/n)+o(sqrt(2/n)) ce que j'ai écris ici n'est pas faux ?

[stray reef]

ok im gonna switch to english bc i think this isn't getting across in french

you said "u_n - sqrt(2/n) = 0?"

i told you that there's a difference between "equals" and "approaches" (or rather, i told you not to confuse the two)

then i said the following:

u_n - sqrt(2/n) is o(sqrt(2/n)). it is true that u_n - sqrt(2/n) approaches 0, but this won't be enough -- you need to use the original little-o notation insteead of weakening it

saying a sequence approaches 0 is synonymous with saying it is o(1).

o(sqrt(2/n)) is a strict subset of o(1) as classes of sequences.

[true iris]

what do you mean by "u_ n - sqrt(2/n) is o(sqrt(2/n))" mean that u_ n- sqrt(2/n)=o(sqrt(2/n))?

[true iris]

I understand what you are saying in French, it's not that I don't understand and I'm studying in France

[stray reef]

yes but the equals sign is a slight abuse of notation

[meager prawn]

which is also extremely standard

[true iris]

donc une flèche jors u_n - sqrt(2/n) flèche o(sqrt(2/n))

[stray reef]

jors ?

[meager prawn]

no

[true iris]

just 0

[meager prawn]

$\to$ denotes limits

[vital dew]

Bezier

[stray reef]

@meager prawn do you mind taking over

i am not sure how to continue

[meager prawn]

Sure, if he comes back

[true iris]

I'm here it's I just don't understand

[meager prawn]

T'en étais où ?

[true iris]

la question 1

[meager prawn]

c'est quoi la définition d'un équivalent ?

[true iris]

quand un/vn tend vers 1

[meager prawn]

Non

[true iris]

en n +infini

[meager prawn]

T'aura du mal à définir l'équivalence à la suite nulle avec ça

[true iris]

vn différent de la suite nulle

[meager prawn]

Non

La définition utilise un o
C'est pour ça que je la veux

Pour te dire "c'est juste la définition" (+ un détail)

[true iris]

un-vn=o(vn)

[meager prawn]

Voilà

Donc par définition, vn = o(sqrt(2/n))

[true iris]

oui

donc sa c'est bon ? un=sqrt(2/n)+o(sqrt(2/n))

[meager prawn]

Est-ce que ça répond à q1 ?

[true iris]

si

juste pour savoir

[meager prawn]

Car o(sqrt(2/n)) = o(sqrt(1/n))

C'était le (+ un détail)

[true iris]

okay

car un-sqrt(2/n)=o(sqrt(2/n))

[meager prawn]

T'écris pas 0/1 par contre

[true iris]

pourquoi

[meager prawn]

le justifierais-tu en disant un - sqrt(2/n) -> 0 et sqrt(1/n) -> 1 ?

[true iris]

par croissance comparé

et quotient de limite

[meager prawn]

"vas-y enfonce toi"

[true iris]

https://tenor.com/view/kermit-falling-building-fall-woodz-gif-24715383

[meager prawn]

T'es sensé remarquer que la réponse attendue est "ah non", soit par l'intonation, soit car le 2e argument est clairement faux

[true iris]

1/infini sa tend vers 0 ah non

[meager prawn]

Donc sqrt(1/n) -> 1 est absurde

[true iris]

oui

[meager prawn]

Donc que je te propose ça comme argument c'est que j'attends un non

[meager prawn]

Donc t'écris pas ça

[true iris]

je me suis mélangé la tête

[meager prawn]

Tu dis que o(sqrt(2/n)) = o(sqrt(1/n)) er voilà
Ou bien tu le redémontre si c'est pas un acquis mais t'écris pas ça

[true iris]

no c'est bon sa arrive de se tromper

[meager prawn]

On est bon pour q1 ?

[true iris]

o(1)

[tame bronze]

I have a question about big-O notation, and how to solve those questions

For 8c, I understand the answer up to "Formally we can write...", how did they get the 3? Did they just choose any random number and decided to use 3?

I understand how they got n = 0, I understand how they got k = 1, but no idea how they came up with C = 3

[meager prawn]

x^4 + x^2 + 1 <= x^4 + x^4 + x^4 = 3 x^4, as x >= 1

And x^4+1 >= x^4 for the denominator

[tame bronze]

Thank you, but if that's the case, shouldn't 7c also be C = 3? The answer key states it as C = 2

x^4 + x^2 + 1 <= x^4 + x^4 + x^4 = 3 x^4, as x >= 1
x^3+1 >= x^4 for the denominator (?) i believe

which would be 3/1, but C = 2, why is this

[meager prawn]

2x(x^3+1) = x^4 + x^4 + 2 >= x^4 + x^2 + 1
So they used the +1 in the numerator to argue C=2 is enough and we don't need C=3

[true iris]

c'est bon pour la 2 en a juste multiplier des 2 coté grâce au relation de transitivité

[meager prawn]

Oui c'est juste une réécriture

[true iris]

pour la 3 c'est celle que j'ai vraiment rien compris du tout

[meager prawn]

Je fais juste redescendre la question

un² = (vn+sqrt(2/n))² = vn² + 2vn sqrt(2/n) + 2/n

conclus

[tame bronze]

you're saying this?

[meager prawn]

Yes

[tame bronze]

Where did you get the 2x from

[meager prawn]

divide by x^3+1
It's the inequality you're looking for

[tame bronze]

are you able to explain it a different way I don't really get it sorry

[meager prawn]

$\frac{x^4+x^2+1}{x^3+1} \leq 2x \Leftrightarrow 2x(x^3+1) \geq x^4+x^2+1$

[vital dew]

Bezier

[tame bronze]

$\frac{x^4+x^2+1}{x^4+1}$

[vital dew]

nogo

[tame bronze]

why is this one so different then

[meager prawn]

Try it and see why it doesn't work

[true iris]

c'est sa ?

[meager prawn]

en ignorant la 2e ligne qui m'a l'air ignoble
Tu peux pas juste dire que ça tend vers 0 donc c'est pas dans l'équivalent
Sinon 1/n = 1/n + o(1/n^2), or 1/n -> donc 1/n = o(1/n^2) serait un raisonnement valide

[tame bronze]

could you explain how you would go about doing 7c after finding n = 1

[meager prawn]

you don't need to notice C=2 works
You can just say C=3 works by doing the same (simpler) thing as in 8)c)

[tame bronze]

oh yeah true more than 1 C and K can work ok thank you

[fickle bluff]

can ayone help me out

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[gritty garnet]

|B| means cardinality

no?

its the number of combination of subsets from A that have size 2 ( two elements)

[lyric quartz]

I got an exercise that wants me to show that the quotients $(A \times B)/\sim$ and $A/\sim_A \times B/\sim_B$ are isomorphic, where $\sim$ is the trivial equivalence relation of $\sim_A$ and $\sim_B$.
Now it is not hard to construct two functions and show they are inverses of each other, but this exercise wants you to use the universal properties of quotients and products. But I am not really sure what way to go

[vital dew]

WanderingLethe

WanderingLethe

WanderingLethe

WanderingLethe

[analog tinsel]

Hey everyone.
I already posed this question in a help channel but unfortunately didnt receive an answer, so I am reposting it here. Would appreciate your help a lot!

I dont understand the solution to this exercise :
Show that if a graph G is planar and contains at least 4 vertices in total then it contains at least 4 vertices that have at most degree 5 each.
The solution says :
Suppose not. Then there exists a minimal counterexample. Let G be that. The minimal degree in G is 3. Then 2|E| = Sum over all degrees >= 3+3+3 + (|V|-3)*6 which is a contradiction to the edge upper bound on planar graphs.

My question: why is the minimal degree of a counterexample 3 ?

[quiet eagle]

I don't believe I can help much, but isn't the formulation "it contains at least 4 vertices..." flawed, as e.g. the Graph with a single vertex is planar too?

[analog tinsel]

correct, my bad, the condition is of course that G is a graph with at least 4 vertices

thank you

[grand totem]

Is it not hard to construct two functions going either way? Going out of the quotient into the product is easy by the universal property of each, the other way around is kind of tricky though. In any case you may either choose this unbiased approach, or show that the quotient is also a product (or vice versa that the product is also a quotient)

[tame bronze]

does this result make sense? since the answer key has k = 0 instead of k = 1, but I'm not sure why k = 1 wouldn't work, unless it does too

[lyric quartz]

Well I know how to construct them, not that many abstractions, just work to write it out.

Yeah I get why there is a morphism to the product, by the universal of the product. But when I construct the function from the product to the quotient, how do I prove it is unique?

Oh the picture is gone, let me re upload

[grand totem]

What would that uniqueness give you? If you're trying to show that they're isomorphic by actually giving an isomorphism then the uniqueness proof will only enter the picture after you've constructed a map in both directions and then you compose them and show appeal to uniquess of product and quotient to conclude that they must be the identity

[lyric quartz]

I don't have the definiton of f and g, just that the lower squares commute, how would I use that?

If i show there exists a unique morphism from the product to the quotient such that the top square commutes, that would make the quotient a universal of the product and thus isomorphic to the product.

[grand totem]

Ok I think I get what you're trying to do (showing that the quotient is also a product) but in that case you don't want to show that there exists a unique arrow from the product into the quotient, but rather from any span A/~ <-- Q --> B/~

The way you phrased it I thought you were going the "unbiased" approach of constructing two maps from product to quotient and vice versa

[lyric quartz]

Well since their are unique morphisms from any Span to the product it suffices to show there is a unique morphism from the product to the quotient and then just precompose it with the unique morphism to the product, right?

I haven't yet read about spans, but is that just a category C_{A,B}?

[grand totem]

That isn't standard notation but probably yes

[quiet eagle]

I'm not sure what definition you use, but you can try it with this:
$$x^3\in \mathcal{O}(\frac{x^3}{2}) \Longleftrightarrow \exists c,x_0\in \mathbb{R}\ \forall x\geq x_0 : \ \ x^3\leq c\frac{x^3}{2}$$

[vital dew]

Sciencenjoyer

[grand totem]

Taking a step back for a second since I have some trouble following, what exactly is your plan on how you want to show that the two are isomorphic?
Am I right in the assumption that your plan is to show that the quotient is also a product of A/~ and B/~

By showing that (equipped with proper projections) it satisfies the universal property of the product, and hence is isomorphic to the product since products are unique

[grand totem]

And f,g here are the projections you're equipping (A x B)/~ with?

[lyric quartz]

By the universal property of $(A \times B)/\sim$ there exists a unique morphism $f$ such that the lower left square commutes. So I only know it exists, I don't have the definiton

[vital dew]

WanderingLethe

[lyric quartz]

(because there exists a function A \times B \to A/\sim_A)

That is correct right? The exercise hints to use that fact

[grand totem]

The composite A x B -> A -> A/~ respects the ~ defined on A x B so it lifts to a map (A x B)/~ -> A/~ yes

Now show that A/~ <-f- (A x B)/~ -g-> B/~ satisfies the universal property of the product

This is where things get awkward since we're now talking about maps into the quotient (whereas the universal property of the quotient speaks of maps out of the quotient)

[lyric quartz]

Right, I was working on a solution that was going out of the quotient, almost at the end I am thinking oh wait it needs to go in...

[grand totem]

(This is also where the "constructing two maps and showing they compose to the identities"-approach becomes tricky)

One map is nice because it goes out of the quotient and into the product, both directions matching the respective universal properties

The other direction also works but (it's not like the theorem is false) but it's not as nice

[lyric quartz]

So I am looking at something like this, right?

[grand totem]

Yeah, I'd try proving uniqueness first since that's slightly easier

[lyric quartz]

I'm a little lost, how would I prove the uniqueness of sigma?

And if I do that, wouldn't that finish the proof?

[grand totem]

I'm a bit confused now (looking at the proposed definition of sigma), does the author still identify the elements of the quotient with equivalence classes?

(I would have expected them to work only up to iso with the quotient via the universal property, not giving any explicit construction)

[lyric quartz]

Oh that part is just mine...

Only thing stated in the question is $(a_1, b_1) \sim (a_2, b_2) \Longleftrightarrow a_1 \sim_A a_2 \wedge b_1 \sim_B b_2$

[vital dew]

WanderingLethe

[grand totem]

It's a good idea not to think of the quotient as equivalence classes, especially if they're already talking about universal properties and such

[lyric quartz]

Right, otherwise I would just construct an isomorphism between equivalence classes. But now I am even more confused, what should I do then? 😛

I dont see how any universal construction would give me a unqiue sigma

And wouldn't I need to use this definition of ~ somewhere in the proof? #discrete-math message

[grand totem]

Now the universal property won't get you very far here though but for a set A and an equivalence relation ~ on A, the following are equivalent for a structure (Q, [-] : A -> Q)

• [-] is surjective and a ~ a' iff [a] = [a']
• if a ~ a' then [a] = [a'] and for any other (B, f : A -> B) for which a ~ a' implies f(a) = f(a') there is a unique h : Q -> B such that h . [-] = f (that's the universal property)

[grand totem]

That was already necessary to get your f and g

[lyric quartz]

Why is that? Isn't that just as the image where A := A \times B and Z := A/\sim_A?

[grand totem]

Yes but you need to show that \varphi (which is the composite of A x B --> A followed by A --> A/~) is such that (a, b) ~ (a', b') implies \varphi(a, b) = \varphi(a', b')

And that requires you to use the definition of (a, b) ~ (a', b')

[lyric quartz]

Oh sorry, of course... I need to prove equivalent element have the same image

In my reasoning it was just a coslice, not a quotient...

(note to self: what are the arrows in the universal construction!)

[grand totem]

A hint for uniqueness would be: Suppose you had σ, σ' such that the diagram communtes, we prove that σ = σ' by proving that σ(z) = σ'(z) for every z in Z.
Now σ(z) and σ'(z) are both elements of (A x B)/~ so there are (a, b) and (a', b') such that σ(z) = [(a, b)] and σ'(z) = [(a', b')]. So it suffices to show that [(a, b)] = [(a', b')], but that is equivalent to (a, b) ~ (a', b'), which is in turn equivalent to a ~ a' and b ~ b'.
The fact that both σ and σ' make the left triangle commute will give you a ~ a' and the right one will give you b ~ b'

[lyric quartz]

Oh, right, ok, that reasoning I get, but I am still trying to understand your other reasoning.

Thank you so much Neverbloom, I am going to take a break and see if I can than grasp it. I got so confused by having the quotient as a coslice, didn't get where that f was coming from.

[grand totem]

You're welcome, I also confused myself a couple of times during this lol

[lyric quartz]

The book hasn't said anything about functors yet. But is $-/{\sim_-}$ a functor which lifts $\pi_A$ to $f$?

[vital dew]

WanderingLethe

WanderingLethe

[grand totem]

Good question, if you define a category C whose objects are sets together with an equivalence relation, then taking quotients is indeed a functor from C to the category of sets. And even better: If you also define another functor from C to Set which simply forgets about the equivalence relation then the assignment that assigns to every (A,~) the map [-] : A --> A/~ is a natural transformation from the latter functor to the first.

The last part is nice because even in elementary mathematics classes some people call [-] something like the "natural projection" without really meaning anything precise with it

But that shows that [-] is actually natural in a precise sense

[lyric quartz]

Right the book calls it "canonical projection"

[grand totem]

This is similar to how A x B --> A and A x B --> B are natural in a precise sense

Them being natural transformations from the product functor to the respective projection functor C x C --> C

[lyric quartz]

Ah ha, well I will read this again when the book talks about natural transformations. But I heard Awodey say that CT was invented to construct natural transformations

But just lectures don't give you insight without doing exercises

Thanks again Neverbloom! I need a break now to process it in my head😊

[weak pumice]

b,c,d

[tame bronze]

Question:

Answer:

[vital dew]

nogo

[errant bear]

plug in n=1

(and 2 and 3)

[wraith pelican]

Does #3 here

imply this?

I don't feel like that would be the case

[fossil mural]

...what symbol is that? $x \not\in X \land Y$?

[wraith pelican]

sorry

[vital dew]

bee [it/its]

[wraith pelican]

it's intersection

[fossil mural]

ah

then no

[wraith pelican]

ok

I didn't think so

[fossil mural]

$1 \not\in {1} \cap {2}$, but ``$1 \not\in {1}$ and $1 \not\in {2}$'' is false

[vital dew]

bee [it/its]

[fossil mural]

(because {1} \cap {2} = empty set)

[wraith pelican]

right

I'm having trouble getting started on this proof.

[fossil mural]

generally the first step is to look at the elements

so you want to prove that for every $x$, $x \in (A \cap B)^c$ iff $x \in A^c \cup B^c$

[vital dew]

bee [it/its]

[wraith pelican]

I've got this so far

but I don't know what I can conclude after x (not in) A union B

[fossil mural]

that's intersection, not union

[wraith pelican]

sorry

intersection is what I'm looking for

n

[fossil mural]

so that's the same as, not (x \in A and x \in B)

[wraith pelican]

what?

[fossil mural]

$x \not\in A \cap B$ iff ``$x \in A$ and $x \in B$'' is false

[vital dew]

bee [it/its]

[fossil mural]

because $x \not\in A \cap B$ is the negation of $x \in A \cap B$ which is the same as $x \in A$ and $x \in B$

[vital dew]

bee [it/its]

[wraith pelican]

?

[fossil mural]

yep

[wraith pelican]

I'm sorry

oh ok

so

how is that not the same as this?

I accept that it's not but I don't know why

[fossil mural]

well what if $x \in A$ is true and $x \in B$ is false

[vital dew]

bee [it/its]

[fossil mural]

then $x \not\in A$ and $x \not\in B$'' is false, but $x \in A$ and $x \in B$'' is also false

[vital dew]

bee [it/its]

[wraith pelican]

ok

[fossil mural]

in fact, not ($x \in A$ and $x \in B$) is the same as $x \not\in A$ or $x \not\in B$

[vital dew]

bee [it/its]

[wraith pelican]

that's what I was looking for

sorry I couldn't articulate the question

and that makes sense, logically

Am I close?

I hope that's readable enough, sorry

[fossil mural]

yep that looks good

[wraith pelican]

excellent, thank you!

And this for the second half?

[fossil mural]

yep

[wraith pelican]

nice. thx

[fickle bluff]

1

[stray reef]

@weak pumice do you still need help with your thing?

i'd prefer a shorter delay than 11 hours

[tardy finch]

can someone lmk how I can improve on this

or if its coherent enough

[stray reef]

second paragraph could be rewritten to be clearer/more explicit. and to actually include an assumption that warrants the wlog disclaimer!

you said in the first paragraph that every node will have either 3 neighbors or 3 non-neighbors

so i would say

"Without loss of generality, let x be a vertex with at least 3 neighbors. Call 3 of these neighbors a, b and c. If any two of them are adjacent, then them and x form a triangle in G. Otherwise, a, b and c form a triangle in G-complement."

idk how valuable the pictures are

and idk what the 6-node ones are for

[viral crown]

the pictures are pretty ig

but also icbw but is the second four vertex graph complement wrong

[stray reef]

yeah looks to be

[visual nymph]

Hey guys

[vital dew]

Bancie

[visual nymph]

Let me rewrite

Is it true guys ?

$\displaystyle \bigcap_{i=1}^{\infty} A_i = \overline{\overline {\bigcap_{i=1}^{\infty} Ai}} = X \backslash \bigg( \overline{\bigcap_{i=1}^{\infty} Ai} \bigg) = X \backslash \bigg( \bigcup_{i=1}^{\infty} \overline{A_i} \bigg)$

[vital dew]

Bancie

[tardy finch]

The only two graphs on 6 vertices that who have a subgraph isomorphic to k3 AND their complement has a subgraph isomorphic to k3 as well

[visual nymph]

Help me plss

[tardy finch]

NOOOO

I SEE IT

damn

Actually

I see what you mean but technically it’s still the right complement

It’s isomorphic to it right

All you have to do is switch the bottom left with the bottom right

[tardy finch]

This is better I spent a lot yapping

I added the graphs cuz I thought it would be good visual aid idk
It helped me think about what I was doing

[short ridge]

can you use height of tree for structural induction?

[grand totem]

you can induct on the height of a tree, yes. whether i would then call that structural induction, i'm not so sure

[short ridge]

yeah i can’t find a good answer for wether it’s structural induction or not

i know it works

i did it on my exam and lost like 60% of points on the problem for not doing structural induction lol

whatever

[lyric quartz]

Hey Neverbloom, I also found a solution online in which a morphism A/~ -> A was formed from the universal property of quotients by the identity on A. But that feels wrong since the identity does not map equivalent elements to the same image.

[grand totem]

Yeah that doesn't work unless ~ happens to be strict equality

[grand totem]

Defining the height of a tree in the first place requires structural recursion, which in turn implies structural induction, so it's not far off. That is quite the detour from a direct proof that simply inducts on the structure of the tree, but quite harsh to deduct over half the points for that lol

[lyric quartz]

There doesn't seem to be any other solutions online 😦

[grand totem]

There are usually two ways to define maps from some arbitrary set X into a quotient A/~
The simple case would be that you already have some function f : X --> A laying around, then [-] . f : X --> A --> A/~ is a good candidate

I'm assuming that's what the author of the solution you found online tried

In terms of the exercise that would boil down to constructing a map Z --> A x B, so they realized they'd need two maps Z --> A and Z --> B to appeal to the universal property of the product

[lyric quartz]

Right

[grand totem]

But we only have maps Z --> A/~ and Z --> B/~ respectively

Now if you wanted to have an easy way out there is one shotgun solution to go from A/~ to A (and hence from Z all the way to A)

Since [-] : A --> A/~ is surjective it has a right-inverse by the axiom of choice

That is way overkill here though

[lyric quartz]

So in my diagram from yesterday, I have a lot of epimorphisms, can I use that in the proof?

Or split epimorphisms

[grand totem]

I'd suggest a different solution: Another way to define a map from some set X into a quotient A/~ would be to first define a relation r between X and A and show that

• whenever x r a and a ~ a' then x r a',
• for every x there is an a such that x r a,
• if x r a and x r a' then a ~ a'.
  The first point is exactly what is needed to lift the relation r to a relation R between X and A/~ and the latter two points will then tell you that R is functional (hence there is a function from X to A/~ whose graph is exactly R)

[lyric quartz]

Ah ok

[timber elm]

How will you design a bijection from Z union (0,1)->(0,1)?

[visual nymph]

Countably additive property:

$\displaystyle \mu \bigg( \bigcup_{n=1}^{\infty} A_n \bigg) = \sum_{n=1}^{\infty} \mu (A_n)$

Can you guys explain why

$\displaystyle \mu \bigg( \bigcup_{n=1}^{\infty} A_n \bigg) = \sum_{n=1}^{\infty} a_n \mu_n \bigg( \bigcup_{n=1}^{\infty} A_n \bigg)$

Where $a_n$ is a string of real number.

[vital dew]

Bancie

[fickle bluff]

please help me out with this one

[errant bear]

what do you not understand/need help with specifically

[stray reef]

what is mu_n? where did you see this?

[visual nymph]

#1221867346377969664 message

I wrote it there @stray reef

[chilly dew]

double ping of doom

[past spear]

Hi everyone, I have such questions
given a1 < a2 < a3 < a4 < a5 < a6
and b1 < b2 < b3 sorted arrays
the problem is sort all elements doing no more than 7 checkings, where each time we can check ai > bj where i = 1,2,3,4,5,6 and j = 1,2,3

[stray reef]

@past spear i'd try to think of the problem this way: the b_j must occupy 3 of the 7 blank spaces in this chain:

_ < a1 < _ < a2 < _ < a3 < _ < a4 < _ < a5 < _ < a6 < _

ok some kind of bullshit is going on with discord's formatting

[fossil mural]

_ < a1 < _ < a2 < _ < a3 < _ < a4 < _ < a5 < _ < a6 < _

[stray reef]

^ that

btw when you say we can check a_i > b_j

does this mean we can ONLY be told a_i > b_j or a_i ≤ b_j?

like, do we get one of >, =, < as comparison output or are we not allowed to distinguish ≤ from <

[tawny orchid]

can anoyone give me combinatorial interpretation of ( x + y ) ^ 3

[stray reef]

what is meant by "combinatorial interpretation"?

[tawny orchid]

like we have a set of 3 elements , x + y to the three is all the possible combinations of choosing elements from a set of three where each element has x color varients etc

like a combinatorial argument

[calm chasm]

I'm sort of not sure how to start this. Unless you can rewrite S as it's power set.

The power set of S would be {empty set, x} if I start with letting x be an arbitrary element of S

[compact yacht]

You can start by taking $x \in S$

[vital dew]

Leu

[compact yacht]

then how can you relate $x$ and $2^{S}$?

[vital dew]

Leu

[calm chasm]

x would be in the power set right?

Wait would x be an element or a subset of the power set

[compact yacht]

{x} would be in the power set

[calm chasm]

So it's just an element of the power set

Right

[compact yacht]

the power set 2^S of a set S is the set whose elements are the subssets of S

so {x}, the singleton set, is element of 2^S but x is not

[calm chasm]

So x is a element of S and a subset of 2^S is {x}?

[compact yacht]

x is element of S
{x} is a subset of S
{x} is an element of 2^S

[calm chasm]

Okay

[compact yacht]

It's like S is a bag with stuff, {x} is a bag with one of the stuff in S, 2^S is a set with all possible ways you can fill a bag with stuff of S (including adding nothing to the bag, which is the empty set)

[calm chasm]

Yes yes

Okay

That was a good analogy

[calm chasm]

So would I just use definitions to relate them?

[calm chasm]

Basically following this

Then since S is a subset of T, the same should follow.

[compact yacht]

yes

[compact yacht]

exactly

[tawny orchid]

@compact yacht can u help me with combinatorics?

[compact yacht]

I can try, I'm not very good

[grand totem]

Another neat way to prove the <= direction is to notice that any set is a subset of itself, in particular S ⊆ S. But that means that S ∈ 2^S, so if 2^S ⊆ 2^T then...

[true condor]

Can I get help with this? Is this option right?

[runic island]

is there an intro to number theory channel here?

[snow sleet]

what is ur combinatorics question?

enumerative combinatorics is a forte of mine

[snow sleet]

yes it's called "elementary-number-theory"

[true condor]

.close

[agile magnet]

#elementary-number-theory

[agile magnet]

what do you think?

i.e. what have you tried?

[true condor]

I got help from one of my friends but thanks for checkin up

[zealous oracle]

can some help me with this #combinatorial-structures message

[tawny orchid]

are you still here?

it was about pell numbers

Give the combinatorial proof for p(n+m) = p(m-1)p(n) + p(m)p(n+1)

if we consider a tiling of 1xn board by dominos whos weight is 1 and squares whos weight is 2 , Let Sn be tjhe sum of the weights of the tiling , give then tjhe weight of a tiling is the product of the weights of the tiles and the weight of the empty tiling is 1

[zealous oracle]

current progress on problem iupdate #combinatorial-structures message

please let me know your thoughts on it

also am i right in saying that if sequence is important than i would use the fundamental principle of multpication whereas if it is not important i will use fundamental principle of addition

[fossil blaze]

R is transitive, if (R o R) ⊆ R where R o R is composite relation.
is this true?

[grand totem]

Yes, one can even strengthen this statement to an iff, i.e. R is transitive iff R \circ R \subseteq R

[hidden totem]

no, this is not right, or it is misleading

there are many cases where problems do fall into this pattern but the serious danger is that many problems do not follow this pattern

think of principle of addition as the combining of different cases

think of principle of multiplication as each choice combined with another choice, you have to make both choices

I'm actually working on a math video on this topic as we speak, i wish i could finish it right now and send it over lol

[vital dew]

Kapa

[tawny orchid]

anyone fimiliar with this?

[tawny orchid]

n must be odd

[weary tiger]

Off-topic but what is that big pillar thing?

[tawny orchid]

the product symbol

its just like the sum , but the terms multiply

[weary tiger]

Ahh I see

Looks interesting

Gonna try it out in a few years hopefully

[tawny orchid]

hopefully , they will become easy to grasp by time

[lyric quartz]

Can someone help me conceptualise the fibred coproduct or pushout of Set?

In HoTT I kind of get it, it's a type with points selected by the two functions and a path between each such pairs of points.

Similar to fibred products, i thought it has to be a subset of the coproduct, the disjoint union. But then the diagram will never commute. So is it then a normal union? That didn't make much sense either cause the codomain of the fixed function then would have to be subsets of another common set and then you will end up with an equaliser, not a fibred coproduct.

[grand totem]

We shouldn't expect it to be a subobject of the coproduct, but a quotient object of the coproduct.

In set we get the pushout of a diagram A <-f- X -g-> B as the quotient of the coproduct of A and B by the equivalence generated by identifying f(x) and g(x)

[lyric quartz]

Ah so instead of generating paths, we create an equivalence relation on elements

[tidal mortar]

hi discrete ppl

woould someone perchance like to perchance help me w something perchance

[compact yacht]

perchance

[tidal mortar]

im having trouble determing the max/min

i dont rlyl understand hasse

[compact yacht]

what is the ordering?

[tidal mortar]

one sec

partial

brb

[stray reef]

"partial" doesn't really tell us anything

by what rule are elements of B supposed to be compared

the lexicographic order is linear so i would have thought something else

but also the order you wrote isn't lexicographic

[tidal mortar]

yall

😭

[stray reef]

well you should post the entire problem from the outset so we don't have to pull it out of you

anyway you need to recall the definition of largest (a.k.a. maximum) and the definition of maximal, and likewise for smallest and minimal

[tidal mortar]

damn

pls dont be mean i literally will cry

i forgot that they were related

that's my bad

[tidal mortar]

ok thank u for this but i was told that there were multiple maximals/mins

and i tried drawing the hasse ]

but ya

[stray reef]

was i?

[stray reef]

ok, can you show your hasse diagram

[tidal mortar]

ok sorry maybe i misread tone

😭

[tidal mortar]

sure one sec

[stray reef]

uhh hold on

that's not B at all

a, b, c, d, x, y and z are not elements of B

the elements of B are those specific 3-length strings

[tidal mortar]

ohh ok

would it be max "zxy zyx" and min "aab"?

[stray reef]

dca is also minimal

[tidal mortar]

so max would be zxy, zyx and min aab, dca?

like no other ones would be min or max?

[stray reef]

please don't abbreviate "minimal" and "maximal" like that

but yes

[tidal mortar]

ok sorry 😭

[odd heart]

Ann says that, because "the maximum" and "a maximal element" are not the same thing

So if you just say "max", it's unclear what you mean

And in particular it's unclear to the other person whether you're aware of the difference

[lyric quartz]

Thanks again Neverbloom. It's pretty cool that from this construction you get an quotient. While for the standard quotient you actually needed to specify the condition of the morphism

[tidal mortar]

i see i see, thank u guys!

[fiery patio]

What is discrete math?

[frosty lily]

does anybody know a linear congruence calculator which writes down each step in a step by step tutorial?

[tidal mortar]

math that makes up rules as we go

[livid hull]

Is this vacuous reasoning ?

p = 5 is an odd number
q = Kevin is cute

p -> q

[lyric quartz]

No, what is vacuous?

[livid hull]

Like the fact that the empty set is a subset of any set?

[compact yacht]

no because p is true

[grim oxide]

that's not vacuous

[compact yacht]

can't you prove it if you take as an axiom that there is an empty set which has no element?

[fossil mural]

that's a weird thing to take as an axiom because like, i would take that as the definition of the empty set

[compact yacht]

I mean in a set theoretical manner

[fossil mural]

i don't know how you would consider the empty set not in a set theoretical manner? like, it's a set

unless you mean "set theory" as in specifically theories like ZF

in which case i would still take "the empty set has no elements" as the definition of the empty set

[compact yacht]

yes that's what I mean

you need to have somehow that there is a set with no element

[fossil mural]

you might want an axiom that asserts that a set with that property exists, but asserting separately that "the empty set" exists and then that it has that property raises the question of what else "the empty set" could mean

[compact yacht]

and supposing you have this

I'm asking if you can't proof from that that the empty set is a subset of every set

[fossil mural]

you can

[compact yacht]

that's the point

[compact yacht]

that's what I meant...

[weary tiger]

What is so discrete about maths?

Ahh I see what's so discrete about maths....

Looks interesting though.

[fossil blaze]

do we have a shortcut or something to do this question?

I know how to do this, but for my case steps doesnt matter. So I am wondering if there is a way that I can solve this as fast as possible

[vestal bronze]

i don;t understand the question, it's impossible that a set is a powerset of any set

it's just necessarily zero

[fossil mural]

...what

[vestal bronze]

oh maybe it's any like "at least one"

[odd heart]

That's not true at all, there are quite a few sets which are powersets of other sets

[vestal bronze]

but not all at the same time

i read any as all

[odd heart]

I agree that a set can be a powerset of at most one other set, yes

[stray reef]

feels overpedantic in this specific circumstance and context.

[vestal bronze]

i didn;t understand it

it's overconfident, "my confusion is worth broadcasting", not overpedantic

[vestal bronze]

i can't think of a general algorithm, in this case you just decide if it's a powerset, 5 times

[fossil mural]

4...?

there are 5 elements and 32 subsets, how are you making 4 decisions

[vestal bronze]

number 1 has 0 elements, not a powerset
number 2 has 1 element. maybe it's apowerset, is the element empty? yes, it's a powerset
number 3 has 1 element, it's not empty, not a powerset
number 4 has 2 elements, and yeah should be like that, it's a powerset
number 5 is like number 3

[fossil mural]

it asks how many subsets of X are power sets, not how many elements

[vestal bronze]

you;re right

then we can examine subsets of sizes 1 ,2 and 4

one for 1
and 4 for 2

no

empty set + 1 element set, of which there's 3, so three for 2

then for 4 it's empty, plus 2-element, plus both pieces of the 2-element

there's one like that yes

[fossil mural]

quicker way: ||the power set of Y is a subset of X iff all subsets of Y are elements of X. so we're counting elements of X such that all subsets of that element are in X||

[vestal bronze]

i think it's the same speed in this cirumstance and other cases too

but it's a proper algorithm on the other hand

[fossil blaze]

actually i am more worried about making mistakes and consuming a lot of time for problems like this especially when these arent mcq's
but thanks a lot

[glass garden]

im unable to find a book that defines a predicate formally

is predicate just a loosely defined word used everywhere without being defined?

i looked in enderton's set theory and others

(im aware of what it means, im just looking for a book that rigorously defines some of the trivial concepts used in set theory

[lyric quartz]

A predicate is a statement with free variables

[lyric quartz]

You can also look at dependent types from type theory. https://ncatlab.org/nlab/show/dependent+type

[steady arrow]

can the upper bound of any chain in a partially ordered set be the empty set itself? like is it ever possible? and if not why?

[steady arrow]

lets say i define my relation to be that a is less than b if and only if b has a lower cardinality than a, then if i have two sets, in my partial order, the empty set and {1} then that would mean that if {{},{1}} is a chain. its upper bound is ø, which would give an upper bound of the empty set.

[left shadow]

The name of a variable in this example is a string of between 1 and 65,535 characters, inclusive, where each character can be an uppercase or a lowercase letter, a dollar sign, an underscore, or a digit, except that the first character must not be a digit. Determine the number of different variable names.

My answer: 54 choices for the first character, and 64 for the 65,534 next characters. So the number of different variable names is 54 * 64^(65534

However the correct answer is somehow 54(64^(65535)-1)/63

can someone explain this answer?

[meager prawn]

You counted those of length 65535
But you also need to count the shorter ones

||That gives a geometric series, and you get the announced result using the geometric sum formula||

[left shadow]

I see, is there another way to get the result? My prof doesnt want us using series for this problem

[meager prawn]

You can always prove it by induction, up to n=65535
Technically there's no series but that's a bit cheesy

Trying to find a nicer solution right now

[left shadow]

Thanks. He wants us to use the multiplication rule, sum rule, division rule, and inclusion-exclusion to solve this

Im not sure if thats possible though

[meager prawn]

Inclusion-exclusion is a big fat ugly sum but you can't use geometric sums?

[left shadow]

No because calc 2 isnt a prereq for the class and hes pretty stingy about it :/

[left shadow]

How would this be done to arrive at the result?

[meager prawn]

idk

Afaik geometric sums is borderline HS material depending on the country/school

[viral crown]

it is deadass hs material

[meager prawn]

Depends on the country

[left shadow]

yeah ik, pretty sure 90% of the class has taken calc 2 as well

[tribal wasp]

Any tips on figuring out bijective functions?

I don’t struggle too much with the actually proving surjectivity and infectivity but it’s hard to figure out the function I need to use.

[stray reef]

would need to go into more detail as to why B is uncountable, i think.

well, ok, you're trying to do that

@tribal wasp did you have it proved in class that any interval is uncountably infinite

[jolly ledge]

I have no idea how this links to linalg

[stray reef]

you can construct a vector space over F_2 here

[jolly ledge]

hmmmmm...

soooooo 1 if the prime is a factor of the number and 0 otherwise

oh....

linearly independent subset...

wow

that's neat, thanks

[trail gust]

can someone please show me how is this true

[viral crown]

im not gonna do it but have you considered expanding the (p+q)^(n-2) term w the binomial thm

[haughty garden]

Instead of tackling the sum right away, try and think about how this relates to the (p + q)^n expansion that you get from the binomial theorem; there’s a lot of similarities that you can then play around with to get the left hand expression

[trail gust]

thanks, i will try it

[fresh hull]

does the method of undetermined coefficients of differential equations work for recurrence relations as well?

[near kiln]

Any clue how to get the enrolled in all three if its not given? I have a formula it works on one specific question but in this case, its not

[fossil mural]

well it depends on what other information you're given

if you take the information there but just say that 3 students are enrolled in all three courses instead, then it's still all consistent and you just end up with a different number for how many students took any course

[rapid kernel]

In Zorn's Lemma A partially ordered non-empty set in which every chain is bounded above has a maximal element, so is it necessary that if A is chain and A has an upper bound then for applying Zorn's Lemma we need to show that that upper bound must belong to A ?

[odd heart]

The statement "in which every chain is bounded above" means that the bound must belong to A, yes.

[rapid kernel]

And same for maximal, right?

[odd heart]

Yes, generally all the elements under consideration must belong to the set.

And the maximal element provided by Zorn's Lemma will also belong to the set

[compact yacht]

Just to make sure that is clear

What you said is the case if A itself is a chain but if you take a chain S in A, then the upper bound must only be in A not in S

[odd heart]

YEs

The upper bound of the chain doesn't have to belong to the chain

(although since it is greater than every elements of the chain, you can add it to the chain without breaking anything)

[rapid kernel]

?

[odd heart]

The upper bound of S doesn't have to be an element of S

But it must be an element of A

Set A = [0,1] (with the standard ordering), S = (0,1). Then S is a chain in A, and 1 is its upper bound

This is perfectly fine

[rapid kernel]

Okay, thank you ❤️

[odd heart]

And just to expand, 2 doesn't work as an upper bound, since it's not an element of A

So even if we can "embed" A in some larger space where we'd have more ways to bound things, we're not allow to use that in Zorn's lemma

Only elements of A "exist" for us

For example A = (0,1) wouldn't satisty the assumptions of Zorn's Lemma

Since not every chain in A would have an upper bound in A

(and indeed A doesn't have a maximal element)

[rapid kernel]

But for A=(0,1) itself chain but it's upper bound does not belong to A

[compact yacht]

A is the chain he is talking about

[rapid kernel]

I don't understand if A is a chain then its upper bound belongs to A or not ?

[compact yacht]

The theorem says

If P is a partially ordered set such that every chain S in P has an upper bound s in P then P has at least one maximal element

[rapid kernel]

Yes

[compact yacht]

1 - if A is chain then A is a chain in A
2 - If there is no upper bound for A in A, then there is a chain in A with no upper bound in A

in that case you can't apply zorn lemma

Btw that's precisely what he said

in other words of course

[rapid kernel]

So for applying Zorn's Lemma on A, it's one of the upper bound must be in A, right?

If A=[0,1] then we can apply Zorn's Lemma but if A=(0,1) then we can not apply Zorn's lemma ?

[compact yacht]

Yes if A is chain and we want to apply Zorn's Lemma then A must have an upper bound in A, that's why we can't apply it in (0, 1) with the standard ordering

[odd heart]

Oh yes, I messed up, very sorry

I mean, my examples were correct, but the notation was conflicting with the original one

Just to reiterate, the upper bound of the chain doesn't have to belong to the chain.

It might, it might not, doesn't matter

But it must belong to the partially ordered set P in which we are working

[rapid kernel]

Okay thank you

[odd heart]

And then there will be some maximal element in P, i.e. one that isn't dominated by any other element of P

(there might be a lot of such elements or just the one, we don't know that from Zorn's lemma alone)

[rapid kernel]

But in general if P is partial set and A is subset of P then is it necessary that maximal element of A lies in A , I think yes

[odd heart]

The phrase "maximal element of A" implies that it belongs to A, yes

As opposed to something like "upper bound of A", which might not be in A

[rapid kernel]

And a finite subset always has maximal element, right?

[odd heart]

Yep

[rapid kernel]

Okay thank you

[surreal lantern]

Dang you're smart

[odd heart]

I am!

[surreal lantern]

I'm in 8th grade and doing calculus ab right now, got any tips to become like you?

[gritty breach]

does the condition of this theorem strictly require all w(e) > w(d) for T to be the unique MST?

[odd heart]

It really just comes down to "read books, do exercises, learn things"

[surreal lantern]

Ok

[fringe turret]

Is it ok to call hash functions surjective? Because for all the inputs of domain there exists some element from range, and two inputs can have same output (hash collision)?

This questions says it is not proven for SHA256, but I have seen instances of hash collisions in md5
https://stackoverflow.com/questions/2658601/do-cryptographic-hash-functions-reach-each-possible-values-i-e-are-they-surje

[fossil mural]

all hash functions have collisions, which means they are not injective

this is just an easy argument by pigeonhole: there are more possible inputs to a hash function than outputs, because the output has fixed size and the input can be as long as you want

a function is surjective if for every output there is some input that gives that output

so for instance if you want SHA256 to output 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824, you can give it the input hello

[fringe turret]

Yeah, I thought the same. But better to ask experts 😄 . Btw is there any mathematical proof of this?

[fossil mural]

but if you want it to output 3fc7e015d1af0f601b067dddc80efee7d8bbc7e976bf82d6e92136ed3c8d4622, we don't know if that's a possible output of SHA256, there might not be any string that that's the hash of

if it isn't then SHA256 is not surjective

[fringe turret]

Yes because only bijective and injective functions are invertible.

[tired reef]

Can someone answer f(x) a + b =

[little prism]

thats imprecise. bijective functions are invertible, injective functions are left invertible and surjective functions are right invertible

[fringe turret]

Yes, left invertible. I read on wiki

idk exactly what it means (will learn about it)

If all the functions are invertable then what about hash functions?

Am I missing some important point here?

[little prism]

left invertible means that if you are given some output then you can produce the exact input you used to get it. and there is only one such input

so you can "undo" the function

you can hopefully see the connection to injective

right invertibility means that for any output you want you can generate an input. tho there might be several inputs

[little prism]

wdym all functions are invertible

well hash functions definitely arent left invertible but they might be right invertible. we dont know

its really just injective/surjective but rephrased

[fringe turret]

I see, "we don't know" thing. Yeah for now I can get that point. Will need more information why we can't find invertable function. Also if we would have found invertible function of hash function then there is no point of cryptography lol

[little prism]

we can find invertible functions. of course we can

I dont see what this has to do with the point of cryptography

[fringe turret]

No it doesn't

[little prism]

if we were able to invert a function then it wouldnt be useful as a hash function

[stray reef]

<@&268886789983436800> low effort troll

[fathom ravine]

On the left you have the question and on the right my solution, any ideas what I did wrong? This seems really easy but I cannot get the right answer

[little prism]

definitely the wrong channel

[tribal wasp]

Yea we did, sorry I just checked this.

[rapid kernel]

Is it correct?

[cerulean radish]

What does the upward arrow mean?

[rapid kernel]

NAND operator

[cerulean radish]

Then yes

[rapid kernel]

Okay, thank you

[hard citrus]

University combinatorics - how to better understand when we're choosing with/without returning elemets or with/without an order?
I'm having a hard time just discerning from the question which one it is and I'm thinking I'm missing some key words that just pass over my head, or some logic.

[rotund mauve]

How do I answer number 1?

The book only gave us the definition of B^A, I have no idea how to visualize it

[lyric quartz]

Write the exponentials as function graphs

[tardy finch]

How do you get a set to the power of a set?

is that something else

[lyric quartz]

And since 2 is isomorphic to B, as noted in def 2.34, it should be similar to B^A

And if you also write down the power set of A, you will probably see more similarities

[lyric quartz]

Look at the definition you posted. For now just see it as notation for the set of functions from A to B

And if you are done with the exercise, you can count the number of functions and maybe see way the notation is B^A

[tardy finch]

what are these questions like?

[tardy finch]

so is that notation for sets of functions?

[lyric quartz]

Yes

[tardy finch]

cool cool

Oh my god

I didn’t even see the definition

💀

My fault

[hard citrus]

idk there isnt just one of those that's the problem, i usually have the most problems identifing when its with returning objects and without order

$\binom{n+k-1}{k-1}$

[vital dew]

horizon2.0

[tardy finch]

I assume u meant like word problems

[hard citrus]

oh yes, sorry forgot to mention

[lyric quartz]

For finite groups the order equals 1 + m + 2k, where 1 is the identity element, m are the number of element with order 2 and 2k are the number of elements with order > 2.

Is there anything more to say about the relation between m and k? For example there are 2 groups of order 4, one with 3 elements of order 2 and one with m = 1 and k = 1. But for a group of order 3 the only possibility is m = 0 and k =1.

And for finite groups of an even order m has to be > 0, but can it take any odd value between 1 and |G| - 1 or are there limitations?

[lyric quartz]

Oh wait a second, the order of elements has to divide the order of the group, so that would mean there isn't any element of order 2 in a group of odd order.

I think, I haven't read about it in the book yet.

[brave rock]

Indeed. A finite group is of even order iff it has an element of even order, moreover

[lyric quartz]

Thank you

[mental hull]

Is the answer 318? Logic here #geometry-and-trigonometry message

Wait no my logic doesn’t work

Fuck

[twilit sundial]

at least three vertices

[mental hull]

Yes, I know

[twilit sundial]

yea

[mental hull]

I tried to account for that already

But 5 is impossible so I only have to consider 3 and 4

Ok I think there’s 12 4 cases

I think I got that

Is that correct?

If so I think it’s 324

Seems right?

Wait no that overcounts

44 I think

Wait wait no that undercounts

50

Ok I actually think it’s 50

Wait no it is 44

Fuck this is hard

[fossil blaze]

Is it always true that a lattice is distributive if there are no diamond (M3) or Pentagon (N5) lattice present in it?

[fossil blaze]

Also one more question: I read that in a lattice L, if each element has atmost complement, then L is a distributive lattice.
But isnt the statement wrong with this diagram?

[marble crater]

pretty far over still

I think the best way is some basic casework

[mental hull]

Yeah I got help in a help channel

I was close but undercounted the amount i overcounted

[static briar]

Could someon explain to me how to simplify the last part of this congruence

[frozen blaze]

hello what is the d+(a) for if someone could please explain

[haughty garden]

It looks like it means the set of positive divisors of a

[mental hull]

Is the answer 36? Since there’s 6 vertices that don’t share a common face with any other vertices, so (6*12) but each diagonal would be counted twice, so you divide by 2 to get 36

[valid linden]

Hiw do yall learn discrete i havr a zybook at uni is that enough

[pine torrent]

Yep

36

[pine torrent]

Uni lecture slides... And a lot of googling for me

[tranquil quarry]

Hi everyone
I'm stuck in both problems hope someone can give me an insight on how to start

[stray reef]

do you know the pigeonhole principle?

[tranquil quarry]

yes I know it but I can't apply it correctly

[stray reef]

for 2a, you want to carve up the 8×9 rectangle into 6 pieces -- that way, you will be guaranteed a pair of points that fall in the same piece

think about how you could make said pieces so that you get the desired distance ≤ 5 thing

[tranquil quarry]

oh now I see it

for number 3 I tired to divide the the set S into a group of sets where each set contains the numbers that aren't relatively prime

then apply the pigeonhole principle

[stray reef]

where the each set contains the number that aren't relatively prime
what does this mean

[tranquil quarry]

I mean that every set contain the numbers that aren't relatively prime, and their union is S

[stray reef]

it sounds like you're thinking of "relatively prime" as a unary property and not a binary one

[tranquil quarry]

in some sense yes, Mmm... no I'm wrong

I guess I found the right solution to problem 3

[stray reef]

there's no "in some sense" about it

relative primality is a property of pairs of numbers and not of individual numbers

[tranquil quarry]

well now I know I was wrong, but what I mean was the sets {2,4,6,8,....}, {3,6,9,...}, etc I used to wrong words

[left shadow]

A professor writes 40 discrete mathematics true/false questions. Of the statements in these questions, 17 are true. If the questions can be positioned in any order, how many different answer keys are possible?

I thought the answer would be P(40, 17) * P(40, 23) because the order of questions in the answer key matters. And since 17 are true and 23 are false, these are independent choosing, hence the multiplication rule.However the answer is C(40, 17). Can someone explain this?

[pale monolith]

there are 40 answers on the answer key

17 of these have to be true

there are C(40,17) ways of picking 17 things out of the 40 there are

[stray reef]

the answer key contains only the answers not the questions

[open remnant]

Reconsider if the order really matters. In the test, of course questions in different orders lead to different tests. But in the answer sheet, all you are doing in distributing 17 TRUE labels and 23 FALSE labels among 40 different "boxes"

Which are the numbers that represent each question

[stray reef]

so it is just a sequence of forty T/F values in which 17 are T's and the rest F's

[left shadow]

If order doesnt matter, C(40, 17) makes sense to me. i just dont get how order doesnt matter here because answers in an answer key are labeled #1, #2, etc and each one corressponds to a specific number in the questions. You cant just switch #1 and #2 in the answer key ?

But if order did matter, would my answer be correct?

[open remnant]

Order of the questions themselves does not matter, that is:
Imagine question #1 is about combinatorics and it is TRUE
and question #2 is about geometry, also TRUE

Swapping questions 1 and 2 on the test make absolutely no difference on the answer sheet. In that sense, the order does not matter

Therefore, you are not assigning TRUE or FALSE to the questions themselves, but just to the order they appeared in test, that is, labels (1, 2, ... 39, 40)

[tepid pawn]

Can someone help me understand p(p(R^2))? I understand that p(R^2) is mind boggling cause it’s basically every possible 2d image or text. But I just can’t wrap my head around what p(p(R^2)) would be like.

[tepid pawn]

Ok I thought about it more, if p(r^2) could be thought of as a list of every possible 2d image, would p(p(r^2)) be a list of all the possible combinations of 2d images put together?

[little prism]

basically, yes

[fossil mural]

You cant just switch #1 and #2 in the answer key ?
exactly. that's why order doesn't matter

i think maybe "order doesn't matter" doesn't quite capture it. C(40, 17) is if the order isn't part of what's being counted

there's only one way to write the question numbers, so it's the same effect as if you didn't have them there at all and just wrote "T F F T F T F F F T T T F F T T F F F T F T T F F T T F F F F F F F T T T T F F" as the answer key

and that's also the same as if you allow the question numbers to be in any order, but then declare that it doesn't matter what order they're in

if "2. true 1. false" is the same answer key as "1. false 2. true", then that is "order doesn't matter"

[late kernel]

Can someone help me understand warshall algorithm for finding the transitive closure of a relation?

[fossil mural]

in this case there is also "only one" way to write the question numbers, because you declare that every way of writing the question numbers is the same

[fossil mural]

is there a specific thing you're confused about?

[late kernel]

How to find subsequent matrices after the relation matrix?

[meager prawn]

sounds way too expensive to be worthwhile to me

there's plenty of great books available online

[brave rock]

I did a google search: https://www.google.com/search?q=discrete+mathematics+with+applications+type%3Apdf

You may find the results interesting

[late kernel]

Discrete mathematical structures by kolman is a good choice to start with

[hard citrus]

is this correct?
the number of solutions over the naturals for $x_1 +x_2 +x_3 = 17$ when for all $i, 2\leq x_i \leq 7$ is 15?

[vital dew]

horizon2.0

[stray reef]

15? sounds low to me at a glance.

nevermind, checks out.

[hard citrus]

I've first adjusted the lower limit to include 0 ($x_1'+x_2'+x_3' = 11$) and then found the complement: meaning i'm taking 3 y's, $5 \leq y_i$ such that $y_1'+x_2+x_3 = 5$ (it's the same for all 3) and then $y_1'+y_2+x_3 = -1$ so i can ignore this and the next (when all are y) and i end up with $\binom{13}{11} - \binom{3}{1} \cdot \binom{7}{5} = 78 - 63 = 15$

[vital dew]

horizon2.0

[stray reef]

yeah, same here.

[hard citrus]

alright thanks!

[weary tiger]

There’s a n*n board, the leftmost bottom of the board is labeled (0,0), the rightmost top is labeled (n,n), find all possible ways to move from (0,0) to (n,n) by only moving one square right or one square up at a time, without crossing the (0,0) to (n,n) diagonal.

[weary tiger]

I see

[vestal bronze]

i don't

[mental hull]

What exactly would count as a different “way” in this context?

[stray reef]

seating arrangements modulo 90° rotations

[mental hull]

Yeah but what about flipping across the vertical and horizontal axis? Or the diagonals? Are those not also valid symmetries in this context

[stray reef]

no

imagine yourself seated at the table

you can tell who is to your left and to your right

[mental hull]

Ok, just making sure

[lone burrow]

Hi I was wondering if anyone has a clue at how to approach question b)

i want to link the generating function and the generating function with the fibonacci numbers but idk how to

[terse wyvern]

evaluate $A_k(x)$ at a point

[vital dew]

treesarentreal.com

[storm prism]

what is the general approach to prove if a function is surjective or injective?

[terse wyvern]

a function is injective if you can show that if two things get mapped to the same point then they must be the same

a function is surjective if you can show that every item in the codomain has a corresponding item in the domain that gets mapped to it

[storm prism]

ah okay, thank you

[tawny orchid]

Where did $(\phi_{0.5})^3 = 0.5$ come from?

[vital dew]

Kapa

[tawny orchid]

Never mind guys it was from the previous example

[compact star]

is this a good spot to hangout?

[near kiln]

This is an example from our prof, Isn't the compliment of B must include the entire book except B

[stray reef]

yes, it should also include the big outside part

your prof claimed her drawing to represent $\overline{B}$ when it is actually $(A \cup C) \setminus B$

[vital dew]

Ann

[near kiln]

I see, thanks

@stray reef what do you call these, when set has like squared in it?

[stray reef]

cartesian power

$A^2 = A \times A$, where $\times$ means the cartesian product of sets

[vital dew]

Ann