discrete-math

[little prism]

No that's not maximum

[spark silo]

oh is it {2, 3, 4, 5, 7}

[little prism]

Yes that works

[spark silo]

yea i got confused with my conjoined green line. that makes alot of sense

[little prism]

Yes not a good way to draw it

[spark silo]

noted😅

thx tho 🙂

[little prism]

It's pretty standard to draw these diagrams multiple times

Once to get the connections and then again until it looks good

[spark silo]

why is it choose 6 gaps, shouldnt it be choose 5 gaps?

like take this example which is the same as above but smaller scale, if i choose two seperators i get 3 different aged kids,i dont choose 3 seperators

[indigo ferry]

It says the sum of all 6 ages is less than 32, which is where the x comes in. So you're dividing 32 into 7 parts

In other words, choosing 6 out of the 31 gaps

[spark silo]

ah isee, the x is just the remainder. thanks

[dry raven]

So I’m a little lost in this class on evaluating a polynomial. They give us a polynomial function and some coefficients and tell us to evaluate it I’m so lost though

Also confused on how to connect polynomials to there summation form

[spark silo]

this orbit stuff makes no sense to me..

how come it needs to be divisible by 3?

and i got no clue how they got those numbers

[narrow trench]

This relies on a fact called the orbit-stabilizer formula

Have you seen what stabilizers are ?

[spark silo]

my only real understanding is its something you can do which keeps it the same as its identity

[narrow trench]

yes

A group action at its heart is just taking a set and defining a left-multiplication where you multiply by a group

So for some g in a group and x in a set, you define gx

And it satisfies the reasonable properties that if e is the identity, then ex = x

and ghx = (gh)x = g(hx), i.e you don't have to worry about brackets

Examples of "reasonable" group actions would be the set of all symmetries of a cube, acting on the set of vertices

Or the group of all permutations of [1..n] acting, well, on [1..n]

Anyhow, given x∈X, its stabilizer is the set of elements in G that keep it fixed, i.e gx=x

You can actually show this is a subgroup of G

But how is this linked to orbits? Well, the orbit of a point x is {gx, g∈G}. But it's likely that all of these g's don't give distinct elements of the orbit, there could be overlap.

To be more precise, what does it mean when gx = g'x ? Well, if you multiply by g⁻¹, you get that g⁻¹g'x = (g⁻¹g)x = ex = x. By definition, this means g⁻¹g' is in the stabilizer of x.

Writing this another way, $g'$ is in the set $g\cdot\text{Stabilizer}(x)$

[vital dew]

Syst3ms

[narrow trench]

The formalism isn't all that important, the point is that for any element in the orbit, you can find many other ways of writing it. How many? As many elements as there are in the stabilizer.

[spark silo]

lol i dont know if i should stop you because the conclusion might make sense but alot of that is just going over my head ngl

[narrow trench]

It's a lot to take in, but this explanation isn't a limited-time offer, either

If the orbit of $x$ looks like ${x_1, x_2, \ldots, x_n}$, what i'm saying is that there are exactly $|\text{Stab}(x)|$ ways of writing each and every one of these $n$ elements.

[vital dew]

Syst3ms

[narrow trench]

And through all of these possible ways of writing, you come across every single element of G exactly once.

What you've done is divvied up the elements of G into n distinct packets, each one with the same number of elements. But that's literally the definition of |G| being divisible by n. You've just shown that the cardinal of the orbit divides the cardinal of G.

I'd prefer if we tried an example, just to cement the intuition

Let S_3 be the group of permutations of {1,2,3}, and let it act on two element subsets of {1,2,3}

So for example (1,2,3)×{1,2} = {2,3}, id×{1,3} = {1,3}, (1,2)×{1,3} = {2,3}, etc

you apply the permutation to each element of the set and consider the result

Let's take some element, say {1,2}. If you choose your pemutations well, it's not hard to see that you can get any other element, so its orbit is {{1,2},{1,3},{2,3}}

Now, what's the stabilizer of {1,2} ? Well, you obviously have the identity, that's a given. But you also have the transposition (1,2) that switches 1 and 2. It turns {1,2} into {2,1}, which doesn't do anything because sets aren't ordered. That's two elements in the stabilizer

Any other permutation sends something to 3 so it wouldn't work.

And now here's what I mean when I say the stabilizer gives us all possible ways of writing elements in the orbit

{1,3} = (2,3){1,2}, easy enough. But since we know the stabilizer, we know that (2,3)(1,2){1,2} = {1,2} as well

Likewise, {2,3} = (1,3){1,2} = (1,3)(1,2){1,2}

So we've divided S_3 into three groups of equal size, based on where they send {1,2}. Three is the size of our orbit !

That was a little application of the general thing i presented

The long and short of it is that the size of any orbit divides the size of the group, and that's what they used in the answer. I'm aware I talked a lot, so don't feel bad at all if you don't get it all at once.

[spark silo]

okay, so even after you know that the size of the orbit divides the size of the group and to use the divisors, how do they get those answers?

[narrow trench]

Sure, let's try to construct an orbit of size 3 without knowing what it could look like.

Let's say it's the orbit of some set A, and for the sake of simplicity suppose that 0 ∈ A.

Adding 1 (mod 15) to element is the simplest (nontrivial) operation, and in fact you only need to look at this one

Adding 2 is just adding 1, twice

Adding 3 is just adding 1, thrice, etc

If we add 1 to every element of A, we get some new set B. Since 0 ∈ A, 1 ∈ B. Nothing scary here.

Since we want our orbit to be of size 3, we really don't want A = B, so A ≠ B.

Now let's do the same thing to B and get some new set C that contains 2. If we want an orbit of size 3, we have to have C distinct from A and B.

A contains 0, B contains 1, C contains 2. If we add 1 to C, it makes sense that we should end up in A to get a neat cycle, so A contains 3.

B contains 4, C contains 5, A contains 6, B contains 7 ... and so on

So A contains every multiple of 3, B every number that's 1 mod 3, and C every number that's 2 mod 3

So A = {0,3,6,9,12}, B = {1,4,7,10,13}, C = {2,5,8,11,14} and there you have it

So what you want to have is that to go from one member of the orbit to the next (in a cycle) you just add one

[blazing steppe]

Quick question, please:

[spark silo]

i see

[narrow trench]

For something of length 5, you'd cycle every 5 increments, so the first set would contain all multiples of 5

etc

And this gives you a very rigid structure on the orbits that aren't of length 15 actually

So something like {0,2} ? 2 isn't a divisor of 15, so that orbit has length 15.

[blazing rose]

can someone explain this to me?

i mean A is element of the power set of all natural numbers right, and n is element N.

What I dont rly get is the Gauss sum, like I have a specific n and I have a element A until a = n it sums up right

but how do i even sum up elements out of a power set?

cause im going to have elements like {1,2,3,...} right?

as theyre a subset of N

[narrow trench]

the powerset is the set of subsets, what you're summing are the elements of those subsets

not the subsets themselves

[blazing rose]

ok so

if i have n = 4

do i have the sum out of 1,2,3,4 2,3,4 3,4 4 and 1,2,3 1,2 1 and 2,3 and so on?

like theres no way thats less than 2n or what am i missing

[narrow trench]

no, what you're wondering is "for a subset A, if you sum all elements less than n, is it ≤ 2n ?"

For {2,3,4,6,7} this isn't the case because 2+3+4 = 9 > 8

But for {1,2,51665214} it is because 1+2 = 3 ≤ 8

[blazing rose]

ohh i see ty

and since A is element of the power set its also a subset of N right?

[narrow trench]

yes

the power set of ℕ is the set of subsets of ℕ

[sudden minnow]

do you have an idea?

[blazing steppe]

I've been told that it's "preimage map".

[sudden minnow]

it is

[narrow trench]

though the usual notation for that would be $f^{-1}({y})$

[vital dew]

Syst3ms

[blazing rose]

This is a countable set right?

As i could just do a bijection between every i in the set of N and 2^i?

Like mapping 1 with 2^1 and 2 with 2^2 and so on

[haughty garden]

Yes

[blazing rose]

Okay

And

Hold on

[sudden minnow]

that is not a bijection

oh if you mean bijection to its image then yeah

[blazing rose]

Yes

How can I use this

To prove the upper set being countable or not?

Like I thought of somehow trying to use a bijection of a known countable set but I’m not sure how

Maybe I can use this lemma?

[cerulean wind]

note that every A in S has to be finite

so S is a subset of the set of finite subsets of N

show that the set of finite subsets of N is countable

since every subset of a countable set is countable, then S is countable

@blazing rose

[blazing rose]

How can I show that?

[blazing rose]

Oh because the sum has an upper bound which is when a=n right?

[cerulean wind]

i gave u some misinformation actually

[blazing rose]

Oh

[pale epoch]

ok so @uneven inlet

can you first give me the definition of $L_1L_3$?

[vital dew]

Lochverstärker

[uneven inlet]

those are languages

[pale epoch]

ye but what does the "multiplication" mean?

is it concatenation?

[uneven inlet]

L1L2 would mean, a group with words where you take the beginning from L1 and the end from L2

[pale epoch]

ok, this is called concatenation

[uneven inlet]

oh

[pale epoch]

so hmm

[uneven inlet]

like

im pretty sure i know how to prove you can get from the left side to the right

but in order to prove they are the same, you also need to do it the other way around

and i have my doubts there

[pale epoch]

the other direction should be very similar

[uneven inlet]

i know

[pale epoch]

i think the hardest part here is writing this down correctly

[uneven inlet]

do you wanna see how i wrote one side?

[pale epoch]

yeah

[uneven inlet]

ok

so lets say x is a word in (L1UL2)L3

that means the y (beginning of x) is in (L1UL2) and z (end of x) is in L3

that means (y is in L1 or y is in L2) and z is in L3

that means (y is in L1 or z is in L3) or (y is in L2 and z is in L3)

that means (x is in L1L3) or (x is in L2L3)

that means x is in (L1L3UL2L3)

thats it

[pale epoch]

there is still a typo here

other than that, this is correct

[uneven inlet]

typo?

[pale epoch]

or a mistake?

its not correct like this

[uneven inlet]

ah yes

its and in the first bracket

its a type

typo

that proof is good right?

[pale epoch]

yes, thats it

yes

so hmm

[uneven inlet]

ok

[pale epoch]

i think you are already done

[uneven inlet]

the other side is problematic to me though

but you need to show it to both sides no?

[pale epoch]

you do

[uneven inlet]

but heres the problem

[pale epoch]

but if you read this same proof backwards line by line

it still works

[uneven inlet]

i dont think so

because

lets start it

x is in (L1L3UL2L3)

(x is in L1L3) or (x is in L2L3)

now heres the problem

[pale epoch]

oh i see

you dont have a y and a z at this point?

[uneven inlet]

adding them now is problematic i think

because i dont think you can gurantee that y1=y2

[pale epoch]

what you can do is split into two separate cases

[uneven inlet]

perhaps the beginning and end for x are different in the different brackets

i tried that

[pale epoch]

case 1: (x is in L1L3)

then x is of the form yz with y in L1 and z in L3

but then y is certainly in L1UL2, right?

and thus yz = x is in (L1UL2)L3

[uneven inlet]

hmmm

yeah... let me digest this

[pale epoch]

sure

im trying to think what your issue is and it seems like its dealing with both cases at once

[uneven inlet]

perha

perhaps

you see, what i did was then this

(y1 is in L1 and z1 is in L3) or (y2 is in L2 and z2 is in L3)

and then i got stuck

[pale epoch]

ok, you can do this

but then you have to consider two cases again

you have to show that y1z1 is in (L1UL2)L3

and then show that y2z2 is in (L1UL2)L3

[uneven inlet]

dont you mean one of them

i dont need both right?

[pale epoch]

you need both

the x you started with

you dont know in which of those sets it is

you know that its in one of them or both

so to be sure you have to check both

[uneven inlet]

yeah but i couldnt reach a form where y1and z1 or y2 and z2 were in the same position

[pale epoch]

what do you mean in the same position?

[uneven inlet]

lik

position them so i can get something like y1 is in L1UL2 and z1 is in L3

wait

[pale epoch]

it boils down to what i did above

[uneven inlet]

yeah

i just noticed

[pale epoch]

if y1 is in L1, its certainly in L1UL2

which is an even bigger set

[uneven inlet]

yeah

i was trying to do logical tricks that were too complex

like adding disjunctions

[pale epoch]

ye well

if you have an "or", just do two cases

[uneven inlet]

yes

i can just add the U to both sides

and get that x is in (L1UL2)L3 or x is in (L1UL2)L3

and that would solve it

that made a lot of order in my mind now

because there is another question which is the same, except with upside down U

and one side is possible to do, but the other shouldnt be possible since the groups shouldnt identical

sets

[pale epoch]

hmm

[uneven inlet]

so you cant just do one side and say "just do the same but backwards"

the fact you can add U is the trick to the opposite side that doesnt work for the other question

thats the difference

[pale epoch]

might be that sometimes one direction is slightly more work

[uneven inlet]

yes

but one direction working, doesnt mean the other will work

[pale epoch]

but tbh if you consider cases, it should work

i mean sure, thats also true

but if you are asked to show equality, then you can be sure its possible

[uneven inlet]

which is why you cant just finish one direction and get out easily by saying "just do it backwards". sometimes you cant

this question was, prove or deny

this was the next question

they arent equal

but im pretty sure you can do one side. from left to right

[pale epoch]

let me think for a second

[uneven inlet]

i already know they arent the same

i found an example

L1=(ε,a)

L2=(b)

L3=(ε,b)

ε is an empty word

in this example, the left side is empty

the right side is b

one side is possible to prove (left to right) because the right side contains it

but the opposite side cant be done

[pale epoch]

ye

[uneven inlet]

in the last question, our trick was to add U

in this one it doesnt work because we need upside down U

[pale epoch]

so you have to read the questions carefully

if its "proof or deny" it can be either

[uneven inlet]

yup

thanks a bunch

you really helped 🙂

[pale epoch]

so yeah, good work

one more thing though

use curly braces {} for sets

[uneven inlet]

true

i actually did on paper in my proof

[foggy marsh]

how would u prove that k3,3 is not planar

you would do it by contradiction i assume ?

[haughty garden]

If it were planar, then Euler’s characteristic formula tells us that V - E + F = 2 where V is the number of vertices, E is the number of edges, and F is the number of faces (enclosed regions)

Vertices and edges are easy to count

So you just need to show that the number of faces contradicts the formula

[foggy marsh]

ohh ok ill give it a try

so F = 1 wich is wrong so contradiction how would prove how many faces k3,3 actualy has ?

[haughty garden]

Think about how many edges you need to form a face/region

The K_{3, 3} graph has a very particular structure

[foggy marsh]

so it having 1 faces dose not make sense beacsue it is bipartite ?

[haughty garden]

It certainly does not have 1 face. Note that your graph is simple so 2 edges aren’t enough; in particular, 4 edges are required to form a face because it is a bipartite graph (hence requires an even number of edges to form an enclosed region)

So every face requires 4 edges. But each edge forms a side of exactly two faces

[foggy marsh]

ohh i understand

[haughty garden]

Once you deduce that, the contradiction becomes apparent

[foggy marsh]

thanks for ur help

i think i get it completely now i also did the calculation above wrong, so F = 5 but k3,3 requires 4 edges to make a face so 4F and due to boundries between to faces it must be 2F edges wich would require 10 edges

[haughty garden]

Yep

[spark silo]

what is 7C(3=35)??? formatting error?
i thought it would be 7C3 * 7C4 because unlike the first example, it matters what team you are on for the number of combinations

[vale cairn]

7 choose 3 is 35 I think

So yeah just a formatting error

[vale cairn]

Once you have chosen one team, the other is automatically determined

[spark silo]

i see, thanks

[hollow dagger]

hi, i hv a question:
if i have a graph G and G1 =(V, E1) and G2 = (V, E2) are 2 distinct DAG of G, how can i show that there exists an edge s.t. if i reverse said edge from the set E1\E2 from G1, G1 remains a dag?

[lofty flax]

anyone can explain how to find the upper bound and least upper bound in a Hess Diagram

[reef dirge]

How does one approach question 2?

[brave rock]

Hint: consider remainders modulo 6.

A stronger hint: ||If p > 3 is a prime, then p is either 1 or 5 mod 6.||

[coral parcel]

Even simpler is to consider remainders modulo 3.

[fickle meteor]

Is there a mathematical formula which proves that one node has a degree too high compared to the other degrees of nodes in a degree sequence?

[unreal stump]

No?

Take a connected graph

That's not trur

[fickle meteor]

So just give an example of a false connected graph?

[blazing rose]

Can anyone help me with this?

I don’t have a good approach I guess

My thought was saying the set of 2^i is in S, but there are also elements in S for which 2^i is not the case

Therefore since the cardinality of 2^i set and the set of all natural numbers is the same and they’re both finite and countable, S has more elements and is therefore uncountable

But I’m rly not sure If I’m thinking right here

[grand totem]

You've said some correct things that almost give you a proof if you put them together in the right way, but also some wrong stuff which I have a hard time parsing (certainly $\mathbb{N}$ is not finite!)

Here are some collective ideas that might help you with a proof of $S$ being uncountable:

• To prove $S$ uncountable, it is sufficient to prove that there is injection from $\mathcal{P}(\mathbb{N})$ to $S$ (can you see why?)

• The hint provided you with the set ${2^n\mid n\in\mathbb{N}}$, which you noticed is in fact in $S$. It might be a good idea to stop here and prove an intermediate Lemma that tells you that all subsets of members of $S$ are also in $S$. The upshot here is that this tells you that not only is ${2^n\mid n\in\mathbb{N}}$ in $S$, but also all of its subsets. Allowing you to conclude that $\mathcal{P}({2^n\mid n\in\mathbb{N}})\subseteq S$.

• This shifts our focus to finding an injection from $\mathcal{P}(\mathbb{N})$ to $\mathcal{P}({2^n\mid n\in\mathbb{N}})$. You may provide another Lemma telling you that any injection from a set $X$ to a set $Y$ gives rise to an injection from $\mathcal{P}(X)$ to $\mathcal{P}(Y)$. This would boil down the problem to pointing out an injection from $\mathbb{N}$ to ${2^n\mid n\in\mathbb{N}}$, but certainly the map $n\mapsto 2^n$ provides you with such an injection.

At that point you just have to plug things together to get an injection $\mathcal{P}(\mathbb{N})\rightarrowtail\mathcal{P}({2^n\mid n\in\mathbb{N}})\hookrightarrow S$.

[blazing rose]

yea i meant infinite and countable oops

sorry lol

brainlag

[grand totem]

sorry gotta edit some stuff, writing latex without IDE is pain

[vital dew]

Neverbloom

[blazing rose]

what is the difference between injection and bijection again?

am i not showing that there exist bijections between these sets?

[grand totem]

bijection is also surjective

between which sets? and what is your definition of a set being countable (just to be clear)?

[blazing rose]

ohh right

[blazing rose]

I thought if a set is countable there is a bijection between the set of all natural numbers and that set

but it is injection instead i guess?

[grand totem]

that is why i asked, usually one would call such a set (i.e. one in bijective correspondence with the naturals) countably infinite (or denumerable)

just "countable" usually then means "finite or countably infinite"

its best if you check your notes (or book or script) for the definition

[blazing rose]

yes this is the case

as the script says

ok i understood injection now good

[grand totem]

ok this definition does make things slightly less obvious as to why i started by telling you that it is sufficient to show the existence of an injection from P(N) to S, so let me clarify

there are a lot of equivalent definitions of countable (in the "finite or countably infinite" sense)

one of them is that a set S is countable iff there is an injection from S to N

[blazing rose]

ok i got that but dont i have to proof then that there exists and injection from my set S to the set of all natural numbers?

[grand totem]

That would mean that S is countable, but we suspect that it isn't countable

[blazing rose]

ohh

[blazing rose]

so the last line here with the double injection shows that?

[grand totem]

Well if you have two injections and you compose them together then you get another injection

[blazing rose]

yea that i got

i just dont understand how that proves S is uncountable

is it because i couldnt create an inverse injection from S back to the other power sets?

[grand totem]

Ok, let's take the proof above as just saying that there is an injection from P(N) to S

To prove that S is uncountable you suppose it was countable and try to arrive at a contradiction

Now if S was countable we'd have an injection from S to N

[blazing rose]

yes

[grand totem]

Our proof above gave us an injection from P(N) to S, our assumption just gave us an injection from S to N

Composing those two together would lead us to an injection from P(N) to N

[blazing rose]

ahhhh

and this is not possible

[grand totem]

I hope that your class has already covered this, because that basically contradicts Cantor's theorem

[blazing rose]

yes okay

yea nah we didnt have that but i watched a video abt it

I was just not sure how to use that theorem here but now everythings cleasr

tysm!!!

[coral lantern]

Problem looks interesting, but how would I formally prove that the hint set is a subset of S

[sly sinew]

could anyone help with this question? i've been stuck on it for a minute

[indigo ferry]

A minute?

[sly sinew]

As in a while

[indigo ferry]

ah makes sense, these things take a while sometimes

Did you identify a set?

[sly sinew]

I’m thinking like base 12?

Bit

[indigo ferry]

mhm

well doesn't have to be, but that's one example

[sly sinew]

I have no idea how to visualize that or write that down tho

[indigo ferry]

You could say it's the set of all strings of length n, over an alphabet of 12 characters

[sly sinew]

Right

[indigo ferry]

or just consisting of 12 letters, you get the idea

[sly sinew]

Then u use an identity? To get the result?

[indigo ferry]

You're required to give a combinatorial proof

using an identity would be algebraic

a combinatorial proof is saying both equations are counting the same thing

[sly sinew]

Oh I see

[indigo ferry]

For example

Here's a losely worded combinatorial proof I wrote for this

[sly sinew]

wait before that, do i need to provide a proof that 12^n is equal to the cardinality of S

[indigo ferry]

The equation on the left, which we know is the cardinality of our set, is the number of all possible such strings

I mean it should be trivial

but you could write a line for that, I'm not sure how this would be graded

[indigo ferry]

So, back to our proof

[indigo ferry]

Think about what the sigma looks like after it's expanded

[sly sinew]

it'd be 1 + something

[indigo ferry]

try writing that out in ( ) + ( ) + .... + ( ) form, without simplifying the combinations

so the first term is ${n \choose 0} 11^0$

[vital dew]

Franz

[sly sinew]

you're saying if i write out the expansion

i can simplify it to 12^n

[indigo ferry]

You might find some algebraic identity, but that's not what we're looking for

You don't need to expand it if you can visualize the sigma itself, but it usually helps

What we're looking at is

$12^n = {n \choose 0} 11^0 + {n \choose 1} 11^1 + ... + {n \choose n} 11^n$

[vital dew]

Franz

[indigo ferry]

See if you can count the same set, with the equation on the right

without going into any factorials

[indigo ferry]

Let me know if you come up with a plausible explaination, or need a hint

[sly sinew]

im just trying to figure out what the conditions are for a combinatorial proof

[indigo ferry]

oh

[sly sinew]

and i've got that down now

but i dont know where the 11 comes from

or how to derive that

[indigo ferry]

Just as an fyi, you can find most of these online

definitions, I mean

From wiki -
In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

• A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. Since those expressions count the same objects, they must be equal to each other and thus the identity is established.
• A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.

[indigo ferry]

what we're doing here would be the first kind, counting. I've only encountered bijective proofs in set theory.

[indigo ferry]

I suppose, a hint, then

Notice the series goes from (n 0) to (n n)

and the only thing we know regarding n, is that it's the length of our string

so each of these terms, are choosing 0, 1, ..., n letters from the string

[sly sinew]

yeah

so the first term is just the subset with 0 letters

[indigo ferry]

hmm

wait, is it?

[indigo ferry]

could you explain what you mean by this

[sly sinew]

like it counts the subsets of s that choose 0 letters

[indigo ferry]

all elements of s has 12 letters

so it doesn't help to consider taking subsets of less than n letters

[sly sinew]

all elements of s are size n

wait no

[indigo ferry]

wait that's my bad

all elements of S have n letters

[sly sinew]

yeah

[indigo ferry]

how do you mean subsets of s that choose 0 letters?

[sly sinew]

wait so i just say (n n) means a particular symbol is in n places

then that leaves no room for the 11 other symbols

so 11^0

[indigo ferry]

That's how I worked it out

[sly sinew]

then multiply them? is that allowed in combinatorial proof?

[indigo ferry]

multiply?

[sly sinew]

like (n n)11^0

[indigo ferry]

okay that's not exactly what I thought of

let's look at (n 1) 11^1

[indigo ferry]

Oh, okay so you can convert (n 0) to (n n) and write basically the same proof

[indigo ferry]

and I see what you're getting at here

[indigo ferry]

It's usually best to not swap this in a combinatorial proof, if possible

Instead of taking (n 0) 11^0 = (n n) 11 ^0
and saying (n n) means a particular symbol is in n places

You'd say there are 0 letters that are not this particular symbol

[sly sinew]

so (n 0)11^0 counts the number of the other symbols

im writing a proof like that right now, but it just seems hard to justify that its a count

[indigo ferry]

and each of those symbols, can take 11 differnt values

[blazing steppe]

Say I have a function f.

It takes in elements x from a set of sets X.

And for each x it returns another function that takes in a single number and returns a tuple of natural numbers that are |x| long. How would I specify the type signature of such a function?

Something like f: X —> (N —> N^k)

But I'm not sure what the appropriate notation is to specify k in an unambiguous manner.

I could instead specify the codomain as the union over k in N of N^k but I suspect that may be more confusing/less clear than if I could indicate what I was trying to get at.

[indigo ferry]

first you can take a special symbol 'y' and take x_1 to x_11 as the rest of your symbols

Then, consider a string that has r letter 'x_n's (for n = 1 to 11)

(n r) gives you the number of ways you can place the r 'x_n's in n places

[sly sinew]

yup yup

that makes sense

[indigo ferry]

and 11^r gives you the number of possible values an ordered set of r 'x_n's can take

(or I guess more formally, the total number of such sets)

So, (n r) 11^r is counting the total number of ways you can arrange and assign values to, a string (in S) that has r 'x_n's

sum that up from 0 to n and you've got the total count □

okay, I'm off to watch season 4 of the dragon prince

[sly sinew]

that was excellent thank you

[indigo ferry]

couldn't you just write $f: X \rightarrow (g:N \rightarrow N^{|x|})$

[vital dew]

Franz

[indigo ferry]

wait I see the issue here

[indigo ferry]

Oh, there one thing I noted reading my proof,
You want to write "consider a string that has exactly r letter 'x_n's " (though it seems evident from the proof)

since by "r" we could be saying 'at least r' or 'exactly r'

[haughty garden]

Consider an infinite set $T$. For each finite subset $S \subset T$, suppose that the set $K_S \subseteq \mathbb R$. Define $K = \bigcup_S K_S$, where $S$ runs through all finite subsets of $T$. Is it true that $K \subseteq \mathbb R$? My intuition tells me yes because, if $x \in K$, then there exist some $S \subseteq T$ such that $x \in K_S$. But since $K_S \subseteq \mathbb R$, it follows that $x \in \mathbb R$. I just want to get a sanity check here. Thanks!

[grand totem]

lots of stuff going on here, but yes $\bigcup X\subseteq Y$ iff $\forall x\in X; x\subseteq Y$

[vital dew]

Neverbloom

[naive plover]

Can someone give me some hints to this? :

Let D be a digraph on 2022 vertices. We want to order the vertices of D, from left to right, say v1,v2,...,v2022 so that every arc of D is form vi to vj with i<j. What is the necessary condition for having such an ordering ? Suppose the condition is satisfied then explain a way for finding such an ordering.

[gaunt kraken]

I am so confused on how to do any of this

[indigo ferry]

what does id_A and id_B mean?

[gaunt kraken]

Beats me

[indigo ferry]

._.

[gaunt kraken]

It doesn't say lol

[indigo ferry]

where's this from?

[indigo ferry]

okay I think I might have a solution, not sure if it would fit the notaton / definitions though

[gaunt kraken]

Anything helps, I'm starting to understand how the two-sided inverses would work

[indigo ferry]

Same here, so g o f (a) = id_A means g o f (a) = a for all a in A

basically the identity function on A

[dense tusk]

hihi,

New to discrete mathematics, where exactly does the empty set come from in the second question?

List at least 4 elements of P(*b*)

[indigo ferry]

definition of the power set

[gaunt kraken]

The empty set, to my understanding, is just always added to a power set incase nothing from the original set exists

[indigo ferry]

since the empty set is a subset of any set

[dense tusk]

Ohh, I haven't covered that. Thank you so much! I'll go read up on that now :)

[gaunt kraken]

Alright, for (b) wouldn't the answer just be 4 since both sets only have 4 values?

[indigo ferry]

so back to this right here, if we go by the example (2, 3, 3, 47) is in A but not B, we can kind of see how a very nice bijection would look

[gaunt kraken]

Correct

[indigo ferry]

4 values but you need to use combinations on choosing 4 values for x's

[indigo ferry]

sooo did you get it

[gaunt kraken]

I think I got A, for B its just adding up all the possible combinations?

[indigo ferry]

mhm

It's easier to calculate for set B than A, because there are no duplicates

[gaunt kraken]

So the numbers go in ascending order and none can be the same from 1-50

Hmm

[indigo ferry]

1 - 53

[gaunt kraken]

Oh yeah

[indigo ferry]

how does your function look?

[gaunt kraken]

This is probably completely wrong, but I did this because they were inverses

f: A -> B, n -> n^2
g: B -> A, n -> sqrt(n)

now that i think of it this is probably completely wrong

[indigo ferry]

pretty much

like you need a bijection

so you need to map all elements in A, to all elements in B

and having to be two sided inverses

[gaunt kraken]

I guess I have no idea what I am doing

[indigo ferry]

try a simpler case

lower the 50

to like, 1

and lower the 53 to 4

If you mess around with it you'll see it works for any n and n+3 in place of 50 and 53

[gaunt kraken]

f: A -> B, n -> n+3

[indigo ferry]

hmm

[gaunt kraken]

Well then you cant get 1,2,3

[indigo ferry]

could you write down one element in A?

[gaunt kraken]

A = {1}

[indigo ferry]

re-visit like the 2nd paragraph here

[gaunt kraken]

Wait a second

each element is 4 values

A = {(1,2,3,4)} would be one element then?

[indigo ferry]

Is that the only element?

[gaunt kraken]

No there would be many more elements as long as the 1 <= x1 <= x2 ... is followed

[indigo ferry]

You seem to know how a power set works, so I'll assume you know set theory

[gaunt kraken]

Somewhat, I'm like 5 weeks into my class

I'd say yes though

[indigo ferry]

so your notation $A = {(1,2,3,4)}$ is wrong, here you're saying this is the only element in A
You want to say (1,2,3,4) is an element of A, or $(1,2,3,4) \in A$

[vital dew]

Franz

[gaunt kraken]

Correct, I didn't meant to say (1,2,3,4) was the only element

[indigo ferry]

just making sure

but if you do use the notation, it's implied

[gaunt kraken]

Alright

[indigo ferry]

back to the matter at hand, if we take 1 and 4 instead of 50 and 53

what would A and B look like

[gaunt kraken]

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

[indigo ferry]

can you think of a function (expressed algebraically) that maps A to B, and another from B to A?

actually let's go for 2 and 5 instead of 1 and 4, to make it clearer

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

[gaunt kraken]

I am not sure what function would do that, maybe f(a) = b just matching one to one?

[indigo ferry]

try constructing tow-sided inverse functions f and g for these two sets

[indigo ferry]

your function would have a tuple as an input, so you have f((a,b,c,d))=

[indigo ferry]

f:A → B, and g:B → A, for this paricular example

[gaunt kraken]

So in this case it would just be f: A -> B and g: B -> A? Matching each tuple to the tuple of the same position of the other set?

[indigo ferry]

Yes, but you couldn't say "In the same position", since we don't have an ordering defined

so your job, is to define a function to do that

(mapping, not the ordering)

[indigo ferry]

and it's not obvious the number of elements are the same for our original case (50 and 53), hence why we are required to find a bijection

[gaunt kraken]

I'm trying to think of a function that would do that but I have no idea

[indigo ferry]

Think of what makes greater than or equal to, different from strictly greater than

[gaunt kraken]

Greater than or equal to can have the same values when strictly greater than cannot have duplicate values

[indigo ferry]

if we take tuples that have x_1=10 in our original problem, what values can x_2 take for elements in set A, and set B?

assume y_n is also x_n since the definition remains the same

[gaunt kraken]

In set A, x_2 can take 10 thru 50 and in set B x_2 can take 11 thru 53

[indigo ferry]

what values can x_3 take? x_4?

[gaunt kraken]

So set A, x_n can be x_(n-1) or greater

[indigo ferry]

._.

[indigo ferry]

hmm, this is wrong

can x_2 really be 53 for B?

[gaunt kraken]

I guess x_2 could only go to 51 for B

[indigo ferry]

mhm

and for x_3, In set A it can take 10 through 50, but for set B it's 12 through 52

x_4, same values in A, but 13 through 53 for B

[gaunt kraken]

I see the pattern, but don't know how to make a function out of it

[indigo ferry]

consider what kind of sets are unique to A and B

[gaunt kraken]

So for set B, lets say back to the original function,

49+ n >= x_n > x_n-1

[indigo ferry]

the max value (not a rigorous definition) a tuple from A can take is (50, 50, 50, 50) and for B it's (50, 51, 52, 53)

the minimum, is (1,1,1,1) vs (1,2,3,4)

and I'm using maximum and minimum very losely here

[gaunt kraken]

Understood

[indigo ferry]

could you explain what this is?

[gaunt kraken]

For set B, just what the next value of x_n would be

[indigo ferry]

hmm

oh, right

okay makes sense

[gaunt kraken]

Don't know if that has any use here, but I wrote that out

[indigo ferry]

but the reason I pointed it out, is just to notice the +1 pattern here

[devout stag]

hello I have a quick question, It it true that ceiling(x+y)=ceiling(x)+ceiling(y)?

[indigo ferry]

c(4.2) + c(4.2) = 10
c(4.2+4.2)= 9

I assume that's what you mean by "ceiling"

[indigo ferry]

so now, we noticed the +1 pattern

[devout stag]

yeahh

thank you

[indigo ferry]

So we can construct a nice function $f((x_1,x_2,x_3,x_4))=(x_1,x_2+1,x_3+2,x_4+3)$

[vital dew]

Franz

[gaunt kraken]

Ohhh

[indigo ferry]

You're not required to prove this spans the whole of A and B but like, it's true

[gaunt kraken]

So if that is the function from A -> B, would the function B -> A be

$f((x_1, x_2, x_3, x_4))=(x_1, x_2 - 1, x_3 - 2, x_4 - 3)$

[vital dew]

Mini

[indigo ferry]

going by what's asked in a), if you construct a suitable g, showing f o g and g o f are identity functions suffice

[indigo ferry]

mhm

well, g, not f

[gaunt kraken]

my bad

[indigo ferry]

okay! we have a nice function for part a, and you see this is in fact a bijection?

[gaunt kraken]

So could I just write it like f: A -> B, $f((x_1, x_2, x_3, x_4))=(x_1, x_2 + 1, x_3 + 2, x_4 + 3)$

[vital dew]

Mini

[indigo ferry]

yeah

and you'll see $f o g (x_1, x_2, x_3, x_4) = g o f (x_1, x_2, x_3, x_4) = (x_1, x_2, x_3, x_4)$

[vital dew]

Franz

[indigo ferry]

which is the identity dunction we needed

[gaunt kraken]

Ok, got it 😄

[indigo ferry]

So that's most of the heavy lifting, now we need to use combinations to find the number of all possible y values for B

have any ideas?

[gaunt kraken]

So for B, you can have a max of 50 different numbers in each spot of the tuple

And the same goes for A

So would it be 50^4 different combinations?

Thank you for your time by the way, my professor does 2 lectures a week and doesn't explain anything

[indigo ferry]

Yw, I'm just bored and I should be doing Analysis problems rn

[indigo ferry]

the tuples are ordered

There's a reason they ask you to find the size of B and not A

[gaunt kraken]

Oh yeah

[indigo ferry]

it becomes more nuanced when you can take two or three of the same value, but it's pretty easy to calculate when they're 4 distinct values

[indigo ferry]

what class is this btw?

[gaunt kraken]

Elementary Discrete Math 1

I need to take Discrete Math 2 next term

[gaunt kraken]

I'm confused why the total amount still wouldn't be 50 x 50 x 50 x 50 even if ordered, cause the first value can be anywhere from 1-50, the second can be 2-51, the third can be 3-52, and the fourth can be 4-53

[indigo ferry]

well if the first value's like 50, the other 3 values are fixed

[gaunt kraken]

Correct, but thats just one combination

[indigo ferry]

If you take 50^4, you're saying there are 50^3 combinations for EACH of the 50 first values

[gaunt kraken]

Hmm

Oh

[indigo ferry]

we can use this ordering to our advantage

[gaunt kraken]

I'm just confused about how you would count them all up because if x_1 is 49, there are only 5 combinations but if x_1 is 1, there are many combinations

[indigo ferry]

say you took some 4, distinct, numbers in the range of 1 to 53 at random

[gaunt kraken]

53 choose 4

[indigo ferry]

How many ways can you arrange such a selection, into y1 y2 y3 and y4?

[gaunt kraken]

If the order of those doesn't matter than 53 choose 4 to the power of 4?

[indigo ferry]

In the context of our set of tuples B

[gaunt kraken]

I do not know

Well it would be 53 choose 4, but then you need to take out all the combinations in which are not ordered

[buoyant pewter]

Prove that if m|x and m|y then m|(ax+by)

[indigo ferry]

consider a single selection of 4 distinct numbers, in the range of 1 to 53

in how many ways, can you fit those 4 numbers into y1 y2 y3 and y4

[gaunt kraken]

(4,6,32,51), 1 way?

[indigo ferry]

o_o

[gaunt kraken]

never mind, that makes no sense

[gaunt kraken]

So if these are the 4 distinct numbers, there are only 1 way to put them

[indigo ferry]

Do something with this, and ^

[gaunt kraken]

I'm stuck

[indigo ferry]

uhhh, what've you got so far?

[gaunt kraken]

Nothing, I'm just trying to think about it and don't know how you would do that

Is it not just 53 choose 4 combinations?

[indigo ferry]

It is .-.

[gaunt kraken]

..............

[indigo ferry]

............................

[gaunt kraken]

I made this way too complicated

lmfao

[indigo ferry]

so there's 53 choose 4 ways to select 4 distinct numbers, and only 1 way to arrange each

[gaunt kraken]

Now that makes a lot more sense

Cause there is only one way to arrange them

[indigo ferry]

you can see how this'd be complicated if we had the equality (ie the case for A)

[gaunt kraken]

I was thinking of like 53 choose 4 minus something to take out other cases, but there is only 1 case per

[indigo ferry]

mhm

[gaunt kraken]

Damn

[indigo ferry]

but since we spent like an hour constructing a bijection from B to A, we know their cardinality is equal

[gaunt kraken]

Hey, I really appreciate your time and help. I have probably already learned more from you than my professor. He has like a 1.4 star on ratemyprofessor but he's the only one who teaches it and its required for my CS major.

[indigo ferry]

glad I could be of help

[gaunt kraken]

That took nearly two hours, I kinda feel bad now that it took so long

[indigo ferry]

It was fun to work through the process though, wasn't it?

[gaunt kraken]

It was, thank you for having me do that. I'm now starting to think of how this stuff actually works rather than just being given an answer and not knowing how any of it works

[indigo ferry]

There are some great channels on youtube, that've made playlists explaining some of this stuff

[gaunt kraken]

You have a playlist you recommend?

[indigo ferry]

Two channels I've found to be very helpful, are Neso Academy (mostly CS) and The Bright Side of Mathematics
3Blue1Brown has some great explanations of Calculus and Linear Algebra, if you haven't watched those already

Neso Academy has a great introductory playlist for Discrete Mathematics, tho I haven't come across a problem exactly like this

[gaunt kraken]

I will definitely check them all out! Haven’t gotten to linear algebra yet but will definitely be useful in the future. Again, I can’t express enough how much I appreciate all the help and teaching you have given me.

[indigo ferry]

you're most welcome

[indigo ferry]

Linear Algebra has some neat applications in CS

I guess it's time I stopped procrastanating on these Analysis problems

have a great day

[gaunt kraken]

Neat! I’m a first-year with past CS experience but haven’t even able to apply any math to anything or do any complex applications. I’m excited to move further with my degree.

[gaunt kraken]

You too, have a great one!

[haughty garden]

Linear Algebra surprisingly (or not surprisingly) has some neat applications to combinatorics which might be of interest to computer science students; in particular, if you want to get into extremal combinatorics (incl. extremal graph theory), you'd be exposed to quite a fair amount of linear algebra

[verbal crystal]

I've got a midterm tomorrow, can someone explain to me what is happening here?

I think that is the middle term because the 3rd summation became -30

but I have no idea how these are being broken up

[haughty garden]

Do you mean how they got the second line from the first line?

Or how you compute the sums?

[verbal crystal]

no, how the sum(i=4)(9) i became 2 sums

[haughty garden]

Observe that [ \sum_{i = 1}^m a_i + \sum_{i = m + 1}^n a_i = \sum_{i = 1}^n a_i] in general. In other words, [ \sum_{i = 1}^3 i + \sum_{i = 4}^9 i = \sum_{i = 1}^9 i]

[haughty garden]

You can think of it as grouping the sum: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 as (1 + 2 + 3) + (4 + 5 + 6 + 7 + 8 + 9) and then subtracting one to get the desired sum that you wanted

[verbal crystal]

Interesting, is there a reason why it was broken up like that? Easier to compute?

[haughty garden]

there's a well-known formula for the sum of the first n integers

namely, [ \sum_{i = 1}^n i = \frac{n(n + 1)}{2}]

[verbal crystal]

Ah yeah the closed formula

[haughty garden]

Yeah, they basically just exploited that formula

[verbal crystal]

New question, Where did the 19 and 7 come from in the numerator, and 6 in the denominator?

[haughty garden]

Are you familiar with the closed formula for the first n squares

[verbal crystal]

is that the one for i^2?

[haughty garden]

yes

[verbal crystal]

n(n+1)(2n+1)/6

[haughty garden]

yep

2 * 9 + 1 = 19, 2 * 3 + 1 = 7

[verbal crystal]

Alrighty that makes a lot of sense now. Appreciate it

[hoary cedar]

hi, the question is to make f R→ R x → |x| bijective and find f ^−1 1) I got ̃f : R+→ R+ : x → |x| for the first part and was wondering if that was also correct.

2. For the second part I got ̃f^ −1 = R+ → R+: x → |x|, because I thougt you had to do: |x|=y and then solve for x to get ̃f^ −1 witch is just |x|=y again, so I dont understand why its not just that

correct answer: ̃f : R−→ R+ : x → |x|, ̃f^ −1 = R+ → R−: x → −x

[spark silo]

i need help with these colouring questions

i get a), thats straight forward
b) i dont understand, a triangular prism (no a pyramid) can be rotated horizontally, but we need to consider it being rotated vertically as well? thats kind of where i get lost i think (although im not good at determing how many colourings a horizontal move would need - its based on duplicates i think..).
c) makes sense, they flip across the orange lines so there will only be 2 faces which can change
but the base of the triangle also doesnt change, so isnt it 3 colours, not 2?

d) i dont understand how they get 8 or 3 do that final calculation

[stray reef]

@spark silo what is this talk of a triangular prism? you have a triangular PYRAMID, not a prism...

[spark silo]

yea u right, fixed that

[stray reef]

and you are explicitly asked to fix ONE order-3 rotation and consider what colorings get fixed by THAT rotation.

[spark silo]

i dont understand, how do you know what colorings get fixed?
and what do you mean fix one? are you saying you only consider R(90) but ignore R(180) or R(270)

[stray reef]

what's R(90)?

[spark silo]

oops i mean R(60) or R(120)

[stray reef]

what's R(60)?

[spark silo]

but the amount of degrees you rotate it?

[stray reef]

the tetrahedron does not possess any 60-degree rotational symmetry.

it does have one that rotates 120 degrees though.

but yes, you take one such rotation and ignore the others temporarily. (the rotations cannot be described by a number alone anyway, there's multiple different axes of rotation...)

and think about what faces would have to have the same color for the coloring to stay the same after rotation.

[spark silo]

im trying to understand why there is a 120 degree symmetry but not 60?

obviously the base of it will always be any colour and it would be the same after rotate
but rotating 60 degrees will need one colour to be the same for all 3 sides - idk how to think of this other then using a diagram and trying to rotate into the same colours

120 degrees however would be the same... like if u replace the B (Blue) with R(red) rotating by 120 still doesnt give the same orientation of colours

[stray reef]

im trying to understand why there is a 120 degree symmetry but not 60?
one-third of a full turn is 120 degrees

[spark silo]

oh yea ur right, i was using the degrees of the triangle itself but thats wrong
so the actual rotations would be R(0) R(120) R(240)

[stray reef]

well,

(the rotations cannot be described by a number alone anyway, there's multiple different axes of rotation...)
but yes

[spark silo]

so ur suggesting that red line i picked could have been changed to any of the 3 other corners
but\ that would be even more confusing to calculate lol

[weary tiger]

can anyone help me with this?

[viral crown]

$a\equiv b (\mod{m})$ is the same thing as $a = km + b$ for some integer $k$

[vital dew]

valley

[covert bolt]

I dont really understand the solution

[haughty garden]

Start by computing [ \prod_{j = 1}^n 2^i \cdot 3^j.] Note that, since $2^i$ is independent of $j$, you effectively get $n$ copies of $2^i$, while the product of $3^j$ becomes a sum in the power. So the inner product gives you [ \prod_{j = 1}^n 2^i 3^j = 2^{ni} 3^{\sum_{j = 1}^n j}]

[haughty garden]

Then consider what the outer product does (completely analogous to how we computed the inner product)

[covert bolt]

ooo

ok thank

[spark silo]

there's alot of questions where they just use a sum of expression just seemingly randomly which doesnt make any sense. what are all the sum of expressions do i need to know (i know thats a bit of a vague question..) and where to apply them??

i dont understand any of the working out any help appreciated..

[hoary cedar]

is f^−1(T1 ∪ T2) = f^−1(T1) ∪ f^−1(T2)? is this correct?

[valid agate]

discrete math vs calculus which is harder

[stray reef]

subjective

[wicked bolt]

discrete math more fun 💅

[marsh ibex]

hi, I need help. How should I go about proving that

[haughty garden]

It would be useful to think of O(…) as sets or classes of functions; in other words, you’re proving that two sets are equal

Recall that $g(n) \in O(f(n))$ as $n \to \infty$ if there exist some $c, N > 0$ such that $g(n) \leq c \cdot f(n)$ for all $n \geq N$

[haughty garden]

So showing that $O(f(n)) \subseteq O(c f(n))$ is immediate

[haughty garden]

To show that $O(c f(n)) \subseteq O(f(n))$, suppose that $g(n) \in O(c f(n))$. Then, by definition, there exist $b, N > 0$ such that $g(n) \leq b(cf(n))$ for all $n \geq N$. But noting that, for $c \geq 0$, we have that $bc \geq 0$, which gives us the result required almost right away

[marsh ibex]

does that mean if I prove that g(n) = O(f(n)), I can conclude that O(f(n)) is a subset of O(cf(n), what should I base this on?

sorry let me comprehend it again

[haughty garden]

Well, showing that O(f(n)) is a subset of O(cf(n)) is immediate just by unrolling the definition of Big-Oh

[marsh ibex]

i understand now, thank you very much

[magic abyss]

i feel dumb seeing this.

[covert bolt]

I dont understand why it approaches infinity

[stray reef]

@covert bolt do you mean "i think it should approach something else" or do you mean "what even is going on here???"

[covert bolt]

the latter tbh

[stray reef]

right well

the limit was l'hôpital'd 10,000,000,000 times (the exponent in g(n))

and now the expression inside the limit has the form $c \cdot a^n$ where $c > 0$ and $a > 1$

[vital dew]

Ann

[covert bolt]

omg that was line 2 to 3?

💀

[stray reef]

yes

[covert bolt]

what about line 1 to 2 doe

[stray reef]

well to be more exact

line 1 to 2 is one application of l'hop

line 2 to 3 is the other 9,999,999,999 applications of l'hop

[covert bolt]

o right

yea that makes sense 💀

thancc

[stray reef]

$c$ is actually absurdly small btw, it's around $10^{-1.957 \times 10^{11}}$

[vital dew]

Ann

[stray reef]

but it is positive regardless

[covert bolt]

ah ic

[covert bolt]

jfc was 10 chosen arbitrarily?

[haughty garden]

It was chosen since, if n > a for some constant a, then n^n > a^n. So, if a = 10, choosing n > 10 is the most natural choice to choose. Although 10

[covert bolt]

o so arbitrary

ok thancc

[dusky tendon]

Can someone please help me with this functions question? I understand the meaning of surjective and total.

[dry raven]

Anyone know what I did wrong here?

[stray reef]

where'd that formula come from

or rather that expression

which looks like 2n + n - 2 as written but apparently it is 2^n + n - 2

[dry raven]

It’s supposed to be 2^n + n-2

[stray reef]

ok but where does it come from

[dry raven]

Formula sheet we have I could’ve done it wrong but I didn’t think I did

[stray reef]

show the formula sheet!

[winged kelp]

shouldn't d) be false, wouldn't it only be true if it were a proper subset symbol instead?

unless im getting hte wrong definition, im thinking the ⊆ means every element of a set is also every element of another set.

and ⊂ means every element in one set is also in another set (but this set also has additional elements)

[uneven violet]

d) is true. For A ⊆ B to be true, all elements of A should be contained in B, but it is ok if B has some elements that are not in A.

Examples:
{1,2} ⊆ {1,2} is true,
{1,2} ⊂ {1,2} is false,
{1} ⊆ {1,2} is true,
{1} ⊂ {1,2} is true

[winged kelp]

then would ⊂ , a proper subset of. another, just a more verbose way to say a little more about the relationship between to sets when it satisfies?

[uneven violet]

Right, ⊂ would mean a proper subset of.

[winged kelp]

thank you ! lol i was looking at examples online, they dont show the example u did.

made me think that theres a distinction

[uneven violet]

np 🙂

[indigo ferry]

dude wtf

[dry raven]

?

[indigo ferry]

what formula sheet would you use for this

[dry raven]

One my professor gave us

Like with general types of problems and how to solve them

[indigo ferry]

can I see it?

[tidal tulip]

not all equivalence relations are totally ordered sets due to the trichotomy law, correct?

but there could be equivalence relations that are totally ordered sets?

[slender flame]

what kind of series do use for this: 𝑓(𝑥)=𝑥^4 * ln(1−𝑥3) ?

[uneven violet]

Are you asking if an equivalence relation can be a total order?

Assume that R is a relation on a set S, and that R is both an equivalence relation and a total order. Take two elements a, b in S. Since R is total, either aRb or bRa, so assume the first aRb. Since R is symmetric, then also bRa, so both aRb and bRa. Since R is anti-symmetric, then a = b. Thus S can contain at most one element.

[cerulean wind]

question unclear

[chrome sand]

Hi guys

can anyone help me show that this is surjective

Can i just finish the proof with

because for every y in R the equation (1-y)/2 is solvable in R and produce a value for x which is also in R?

[sudden minnow]

to be clean

for arbitrary real number y, 1-y/2 is also a real number

and f((1-y/2)) = y

and you are done

[dusky tendon]

Guys.

Please help me with my question

Essentially, they give you an example of a real-life situation and you have to suggest which out of the ten options it is likely most to be. I am not too sure how to solve it but I will explain my reasoning
Please can someone check my reasoning.

My reasoning:
I believe option a is a total surjective function (3). I believe this as the domain is all of the possible GPS coordinates and the range is either true or false. It is not injective as it is many to one. More than one GPS coordinate will produce an output of true for example. I am also assuming that there cannot be two trees at one GPS coordinate - if this was the case, option A would not be a function.
I believe option d is a partial surjective function (6). I believe this as the domain is the building identity and the range is a set of GPS co-ordinates. Since there are some GPS coordinates that do not have a building upon them, they would not be in the range and they would not be mapped. Hence, I believe it is partially surjective.
I believe option c is a partial bijective function. (4) The domain is the set of all GPS coordinates and a car might not be present at a certain GPS coordinate making the function partial but wherever there is a car present at a GPS coordinate, it is uniquely mapped out to a unique license registration. Since there is a one-to-one and onto correspondence, it must be bijective.
I believe option b is partial surjective function (6). I am quite uncertain about this answer. I believe there is an infinite number of pixel types in the domain and not all colours may be in the range so it is partial. Many different types of pixels may map to the same colour, hence it cannot be injective.

[spark silo]

could someone help me give an idea on finding latin squares which idempotent/half idepontent symmetric/not symmetric
i understand symmetry, but the idempotency doesnt make much sense to me. thanks alot

[marsh ibex]

hi, how can I find out the Big O complexity of this funtion?

[indigo ferry]

You can rewrite n as k^log n

So you'd have $k^{5 (log n)^2}$

[vital dew]

Franz

[indigo ferry]

(log n) ^ 2 grows slower than n

[marsh ibex]

I see, thanks a lot.

[solemn zephyr]

Prove or disprove: if R and S are two equivalence relations on a set X then R \S is also an equivalence relation.

its not correct right

if X is (1,2,3)

R is (1,1) 2,2 3,3 2.3 3,2

S is just 1,1 2,2 3,3

then if u remove its 2,3 3,2 which is symetric but not reflexive

[shut bolt]

i think this has to do with well ordering but i dont really understand how to figure this one out

i think its the first one

[chrome sand]

Hi guys

Anyone know why g1 and g2 are not right inverse to f?

if i have it left

g1 $\circ$ f

[vital dew]

Wuff

[chrome sand]

its 2n/2

which is 2

eh which is n

if i have

f $\circ$ g1

[vital dew]

Wuff

[chrome sand]

i have 2n /2

which is again n

[dry raven]

Does this seem right? Look just at x2 x4 and x6 then obviously you’ll need one more to get to second largest

I got 3

If anyone looos at this please @ me! Thank you in advance

[keen geode]

If we say that n{a_i}={n*a_i} for any real number n, then what does the following mean?

Is it the union of all w_1 and their multiples with the power of 2 altogether unified with all w_2 with their multiples of the powwers of 2 unified with w_3 with all teh powers of and etc?

[sudden minnow]

in more generality, consider every equivalence relation has to include the diagonal (a,a)

so if you subtract one from the other, the diagonal will be excluded

contradicts reflexivity as you said

so not only does it fail for your specific example, it necessarily fails for every example

[solemn zephyr]

👍

actually incorrect

@sudden minnow

if R=S

empty set is also equivalent

[sudden minnow]

no

only if X is also empty, but then everything is vacuous

[solemn zephyr]

X=(1,2,3)

R is just (1,1)

S is (1,1)

R minus S

[sudden minnow]

no, those are not equivalence relations

[solemn zephyr]

is empty

how so?

[sudden minnow]

you need (1,1) , (2,2) and (3,3) on any equivalence relation on X

[solemn zephyr]

ok so if its that

then u get empty set

[sudden minnow]

...which is not an equivalence relation

[solemn zephyr]

what rly

i thought empty is also equivalance

[sudden minnow]

unless the base set is empty, an empty set can never be an equivalence relation

as I said, you need the diagonal as a subset of the equivalence relation

[solemn zephyr]

ure right actually

yeh

[sudden minnow]

by reflexivity

[solemn zephyr]

function on finite set is injective only if surjective, right

this doesnt apply to infinite set

[sudden minnow]

no no no what

if domain and codomain have the same size sure

otherwise hell no

[solemn zephyr]

X is finite

function on this set X is injective only if on

[sudden minnow]

are you saying the function is X -> X

[solemn zephyr]

yes

[sudden minnow]

then yes

and yes, doesn't apply to infinite

[solemn zephyr]

yes could you give some example

of function on infinite set

to which it doesnt apply?

[sudden minnow]

very easy

N -> N

f(x) = 2x

[solemn zephyr]

yeh ure right its not on cuz u dont get 1

[sudden minnow]

or any odd number, but yes

[solemn zephyr]

i could add anything

f(x)=15424x

N->N

@sudden minnowright?

[sudden minnow]

yes this works the same way

[vague island]

hi, what does the modular of congruence mean? what is a modular of congruence?

[dry raven]

Someone mind checking if I’m correct on this? I got 3

[weary tiger]

probably 2 or 1 idk

[dry raven]

How’d you get 2 or 1

[spring hound]

Yes, that's fine.

You need to check which is the greatest, which takes two comparisons. Then, you need to check which is the second greatest, which takes one more.

That's also the best case.

[pastel coral]

How would I start this question:
$$\frac{(7\cdot 2017)!}{7^{2017}}\mod 7 = ?$$

Just a hint to get me started would be enough

[vital dew]

cedric_

[stray reef]

try to find the exponent of 7 in the prime factorization of (7*2017)!

feels to me like it ought to be strictly greater than 2017

[spring elk]

Why is it "->"? Shouldnt it be "^" (and)? because p->q would state that if p is false and q is true the statement is still true. So in this case if x<=y is false (so x>y) and f(x) >= f(y) this would mean the statement is still true but f would increase in this case so this shouldnt be true

[little prism]

if x>y, then y<=x so then f(y) >= f(x)

so x>y and f(x) >= f(y) cant happen

(ignoring equality)

[torn tendon]

More generally if p is false then the statement is vacuously true , in other words the statement is meaningless and always true because its impossible to have p(x<=y True ) --> q(f(x) < f(y) False) as p is always false

[little prism]

also a statement of the form "for all x,y (x <=y and(...) )" would be false

cause clearly there are x and y for which x <= y is false

[copper acorn]

would it be appropriate for this server to ask questions about algorithm analysis (complexity)? Specifically I was looking for help on topics like amortized analysis and average-case analysis. These are more computer-science topics but perhaps related to disccrete maths to some extent. I haven't seen a suitable channel around here

[spring elk]

this makes sense. thanks!

[spring elk]

are my solutions right? im pretty confident about a but i think i missed something in b.

i feel like in (b) my quantified statement is saying A has one zero columns and also non zero columns

[covert bolt]

I dont understand the solution

Also I dont understand why they didnt use $$B(-2)^n$$

[vital dew]

Opify

[indigo ferry]

which part?

do you see why the Lemma is true?

[covert bolt]

yea

I mean why they even decided they need the lemma

I dont understand that part

[indigo ferry]

$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n}$

[vital dew]

Franz

[indigo ferry]

So we need to find un upper limit for A_n+1

From the induction hypothesis we have the upper limit for A_n/2

but to find the upper limit for 1/A_n, we need a lower limit for A_n

which is there the lemma comes in

$A_{n} = \frac{A_{n-1}}{2} + \frac{1}{A_{n-1}}$ for some $A_{n-1} \in \mathbb{R}$

[vital dew]

Franz

[indigo ferry]

$\Rightarrow A_n \leq \sqrt{2}$

[vital dew]

Franz

[indigo ferry]

which follows from the Lemma

[covert bolt]

so the lemma was just for $\frac{1}{A_n}$ ???

[vital dew]

Opify

[indigo ferry]

yeah

[covert bolt]

wow

[covert bolt]

how bout this

[indigo ferry]

Idk what a homogenous recurrence is

[covert bolt]

ooo

[indigo ferry]

oh wait I think I do know what that is

[indigo ferry]

Sorry, I got nothing

[covert bolt]

It's ok, thank you

[weary tiger]

ok im done trying

the ^ means gcd

knowing that gcd(a,b) = xa +yb

the equality is trivial if x > 0 and y >= 0

but for x > 0 and y < 0

idk what to do

[weary tiger]

a,m,n >0

i tried another thing but it aint going nowhere

which is n = gcd(n,m)n'
m = gcd(n,m)m'

gcd(n',m') = 1

then proving gcd(a^m' - 1 , a^n' - 1) = a - 1

which seems simpler

but it still went nowhere

idek know but i spent sm time on this q that i ended up with this question in my hand

[weary tiger]

if this has some kinda very unique trick im switching to literature studies

[weary tiger]

it's this mf right here that's causing me all the trouble

meaning of this half circle

please

very dumb

but

very important

[weary tiger]

card(A) >= carb({{b}})

with b in A

yes got it

thanks

🫡

[brave rock]

Uh what, no

[brave rock]

This is the subset symbol. If we write A ⊆ B, we say "A is a subset of B", and it means that every element of A is also an element of B.

What section symbol said is not correct.

[weary tiger]

right it doesnt mean that

[brave rock]

It doesn't mean that b is in A, either

However in this particular case it does mean that {b} is in A, and in fact this is sufficient.

[weary tiger]

but if A ⊆ B, fhen cardA =< cardB

[brave rock]

This is not sufficient.

[weary tiger]

.

[brave rock]

This is false

E.g. {1} is in A={{1}, {2}} but 1 is not in A.

[weary tiger]

huh

ok what do you men by "is in"

and what do you mean by "{}"

[brave rock]

I mean is in. Perhaps you should review some set theory

[weary tiger]

thats what i was thinking

[brave rock]

I don't want to go through these definitions here.

[weary tiger]

but

{{b}} is a set

[brave rock]

It certainly is.

[weary tiger]

and {b} is an elemnt

of {{b}}

[brave rock]

That is right.

[weary tiger]

wait

by in

did u mean

⊆

or

[brave rock]

No.

[weary tiger]

€