discrete-math

[obsidian cove]

How does the field i provided satisfy that condition

[inland zenith]

addition is defined modulo 2, so if you have 1, you can add 1 and get 0, so 1 is its own inverse

wrt addition

[obsidian cove]

see thats the thing ion understand. What is the whole modulo 2 definition of addition thing

where is it coming from

[inland zenith]

a field is like a set of things together with two operations on those things which satisfies the field axioms, what the operations are doesn't matter so long as the axioms are satsified

so here the operation is chosen as mod 2, that's in a sense what makes {0,1} a field

wrt addition

are you starting with abstract algebra with fields?

I would recommend studying group theory first and absorbing the core ideas

[obsidian cove]

its part of my introduction to proofs course

[inland zenith]

I see

[obsidian cove]

this term test will include induction (pretty straight forward), functions (doesn't seem to bad), and this field stuff

[inland zenith]

okay, well, just remember that you have a set, in this case {0,1}, and two operations, one corresonds to addition and the other with multiplication

but the operations need to satisfy a lot of properties

so there needs to be an additive inverse (minus is possible) and multiplicative inverse (division is possible)

by the way division in finite fields is very weird, you won't recognize it as division probably

[obsidian cove]

wait a second, what do you mean by "corresponds to"

as in, it doesn't have to be addition itself?

[inland zenith]

nope

it just needs to have the same properties as normal addition

it can be almost anything

[obsidian cove]

what is it in the case of the field i provided

[inland zenith]

hence why this field (of math) is called abstract algebra, it's like algebra but not necessarily on numbers

[inland zenith]

addition modulo 2

[obsidian cove]

But like how could you tell immiddietly just by the field being provided

[inland zenith]

well, I know this field so I knew immediately what the operation is, but otherwise you would need to study the operations

on wikipedia they provide a definition of what addition means with tables

https://en.wikipedia.org/wiki/GF(2)

you are talking about this field, right?

[obsidian cove]

yes

[neon harbor]

Note that the operations are part of the definition of a field, so saying that {0, 1} is a field is really underspecified - you need to specify what the operations are

[inland zenith]

yeah ^

[neon harbor]

but it turns out that for each prime p and integer n there's a unique finite field of size p^n, so we can deduce what the operations are just by looking at the set

[inland zenith]

is this a reasonable argument for showing that $\chi_e(K_n)=n$ where $n$ is odd?

Let's assume that $K_n$ is colorable using $n-1$ colors (it's definitely not possible to color using less than that) and show that that leads to a contradiction. Since every vertex has degree $n-1$ we must use all of our colors at each vertex. Then we can construct a spanning tree for $K_n$ out of edges of only two of the colors. The spanning tree is bipartite and hence this coloring of the tree is a perfect matching, which implies that $n$ is even, which is a contradiction

[vital dew]

masterbuilder

[inland zenith]

may need some work, I'm honestly super stuck on this

[gritty shadow]

i have a really stupid question but

negate ∀x P((x^2)>0) ???

[cursive nymph]

this is unrelated to your question, but:

is it really exists [negative] ?!

what about vacuous truth?
I.e. we say for all x but there are no x's. so there is nothing to exist

[gritty shadow]

ion man im new and i think my prof is not that great 😭

he put the negation of it as E! then one another question he put it as E, so like?????

im considering just getting a course at this point he not helping 💀

[cursive nymph]

I mean, I was triggered by the phrase 'picks representative' 🥹

[cursive nymph]

just in case: that wasn't a question to you

[gritty shadow]

oh my bad lol

[odd heart]

I'm a bit rusty, but there's some discussion here: https://math.stackexchange.com/questions/1172005/chromatic-index-of-a-complete-graph

[inland zenith]

thanks, I also found this, to be honest I'm not really a big fan of this, there must be a simpler argument

[grand totem]

That's kind of what it does though. A right inverse f : A/∼ -> A to a quotient map [-] : A -> A/∼ would satisfy f([a]) ∼ a for every a in A.

[latent spruce]

what sites can i practice discrete math in?

[inland zenith]

I got it, it took a while though, the idea is this: Assume that $n$ is even (the odd case is already taken care of), we have already shown that $\chi_e(K_{n-1})$ so we only need to show that adding a vertex to $K_{n-1}$ does not affect the chromatic index. Because the degree of each vertex is $n-2$ there is an unused color that is not used to color an edge incident to that vertex. We show that these unused colors are all distinct by contradiction. Assume that for arbitrary distinct vertices $u$ and $v$ that we can color the edges incident to them using the same $n-2$ colors. Since $u$ and $v$ are incident we must use one color to color that edge which leaves $n-3$ colors. Now notice that the rest of the vertices all form a triangle with $u$ and $v$, it's easy to show that you need 2 colors to color this triangle. To color all of these triangles you need an even number of colors, but we only have an odd number of colors available, which contradicts the assumption that we can color $K_{n-1}$. Therefore $u$ and $v$ each have a different unused color. But then it's easy to show that we can add a vertex to $K_{n-1}$ without affecting the edge chromatic number, just color the new edges using the unused colors, which are $n-1$ in total and all distinct.

[vital dew]

masterbuilder

[inland zenith]

I believe this proof will work fine for the odd case, so I suppose this proof is acceptable

I wrote the wrong thing when describing the contradiction, but it's probably clear what I meant to write there

[obsidian cove]

Quick question. I saw a video where they had a field GF(3), and the operation they were using is mod 3, so does it mean that that if you have a field with elements {1, 2, ... n}, the operation is basically mod(n+1)?

so for example, the field {0, 1}, we do mod 2

for {0, 1, 2} we do mod 3?

[vapid token]

Yeah basically

[brave rock]

Not all finite fields look like this, but GF(p) when p is prime is of this form. People also write F_p

[vapid token]

Yeah yeah

But any two finite fields of order p^k with p prime are isomorphic

What’s the easiest way to show a $k$-regular bipartite graph $G$ with $k\geq2$ cannot have a vertex connectivity of $1$

[vital dew]

KirPlop

[vapid token]

This is a rough sketch of what I’ve gotten so far

[inland zenith]

how do you define vertex connectivity?

specifically, what does connectivity of 1 mean?

[vapid token]

The minimum number of vertices required to disconnect the graph

[inland zenith]

okay

[inland zenith]

well, the only way to disconnect the graph is if you have all of the vertices of one partition connected to only one vertex of the other partition, right? but that's impossible because G is k-regular with k>=2

so the size of either partition must be greater than 1

[vapid token]

Not right

That isn’t the only situation you may disconnect the graph

[rigid night]

Each connected component of G' is a k-regular bipartite graph and thus has connectivity greater than 1, right? Construct a graph K (with repeated edges but not loops allowed) on the set of connected components C_1, ..., C_m of G', with an edge between C_i and C_j for each edge in the perfect matching between a vertex in C_i and a vertex in C_j. Then in K, deg(C_i) = |C_i|. Deleting a vertex v in C_i from G is essentially equivalent to deleting it from C_i (which we know remains connected) and the single edge in K corresponding to it. It should thus suffice to show that deleting a single edge from K leaves it connected. I believe that in K the number of edges between any C_i and C_j should be even, which would prove this.

IG tidying up the idea a bit, after deleting any vertex v, the connected component of G' containing v remains connected by inductive hypothesis, so any path through v using edges of G' can be "rerouted". And if uvw is a path through v with vw an edge from the perfect matching, then (according to my conjecture) there's another edge between vertices in the same connected components of G' as u and v - say u1 and v1 - and v and w - say v2 and w2 - and we can replace uvw by u...u1v1...v2w2...w using the inductive hypothesis for the ... parts.

[inland zenith]

what other cases are there?

oh. I misunderstood a bit the premise

[rigid night]

Let {a,b,c}, {d,e,f} be the parts with edges ad, bd, be, bf, ce, cf for example.

[inland zenith]

yeah

sorry

[rigid night]

My conjecture in the last sentence doesn't seem to be true: imagine there are four C_i's, all K_{2,2}'s; then we can have 3 edges between C_1 and C_2 and between C_3 and C_4, and 1 between C_1, C_3 and C_2, C_4 just by pairing up vertices (maintaining bipartite-ness) to make edges. In fact, probably pretty much any distribution of edges consistent with the degrees can be manufactured.

It should still be true (because it's necessary and sufficient for the conclusion to hold if I'm not mistaken) that K remains connected upon removing one edge.

[vapid token]

not that helpful, but I made these

the same graph, but two distinct ways to 1-factorize it

[solar marsh]

Every vertex is in a cycle

[vapid token]

That's trivial as there are no leaves

[solar marsh]

If you delete x and a path from u to v uses te vertex x

[rigid night]

The cycle might not involve u or v, though.

[vapid token]

Yes, but who is to say there are not two cycles connected by the mutual vertex x

[vapid token]

Maybe we’ll never know

[rigid night]

This is true: for any partition of K into two pieces A and B, the number of edges between A and B must be positive (because K is connected) and even (because every vertex in, say, A has even degree); hence there will remain an edge between A and B after removing any one edge from K.

[rigid night]

Which taken together proves this result.

It does feel a bit longer than necessary.

[ocean socket]

what is the difference between a relation and a binary relation?

[vestal bronze]

none?

relation is short for binary relation

you could imagine a ternary relation but you can;t call it "relation" people would be confused

[full pawn]

Hi may I please seek help: Let F: 𝒫(ℕ) ∖ {∅} -> ℕ by setting 𝑓(𝑆) to be the smallest element of 𝑆

How can I know Setwise Preimage({𝑛}) is uncountable for some 𝑛 ∈ ℕ.

my current solution is to use n = 0, but i am stuck

[grave anchor]

is this sum equivalent to:
$$n((n-1)2^{n-2}+2^{n-1})$$?

[vital dew]

>_<

[verbal zephyr]

Any subset of N that contains 0 is in the preimage of 0, that's quite a few!

[grave anchor]

its correct for the first 4 ns

my work

[full pawn]

Hiw would I go about proving?

[verbal zephyr]

Let X be any subset of N containing 0, then X is not empty and so F(X) is well-defined. Since 0 is smaller than any other natural number, it is also smaller than any other element of X. Therefore 0 is the smallest element of X. So F(X) = 0 and hence X is in the preimage of 0.

Now we still need to show that the set of all such X's is uncountable

[grave anchor]

yeah this is correct

[full pawn]

Would it be like: Since every f-1({0}) can be written as {0} U S, where S is a subset of positive integers, there is a bijection between f-1({0}) and Power set of positive integers

[verbal zephyr]

That's the idea, but you still need to show that this operation P(N) -> F^-1(0) that sends a subset S to {0} U S is a bijection

[full pawn]

How would I do that? Like this? Let S_1 and S_2 be different elements of P(N)
Then {0} ∪ S_1 ≠ {0} ∪ S_2.

[verbal zephyr]

Hmmm I guess it's not actually a bijection, since both {} and {0} get sent to {0}

[full pawn]

hmm the domain excludes {}

[verbal zephyr]

Right, that works, then we still need that P(N) \ {} is uncountable

[verbal zephyr]

This is not a proof yet, you need to use that neither S_1 nor S_2 are {} somewhere

[full pawn]

Cantor rule says that when N is countable infinite -> P(N) is uncountable

[verbal zephyr]

Yes, but why is then also P(N) \ {} uncountable? (This is really obvious but you should prove it)

[full pawn]

How would I do this though?

[sand thorn]

I'm not sure how to prove that g(a).g(b) is also composed of positive integers that have gcdAB = 1

This is for a homework so don’t give direct answers please

Just hints or similar problems

[verbal zephyr]

You made a mistake, fg(n) is not f(g(n)) here, but rather f(n) * g(n)

[sand thorn]

Oh I see

The notation was a bit weird thank you

[sand thorn]

But then it just means f(n)*g(n) = f(n)*g(n)

I’ll ask to confirm with my prof but that sounds too easy to be a proof

[verbal zephyr]

No that's not what is asked

[sand thorn]

Oh

[verbal zephyr]

The question is to show that f(n)g(n) is a multiplicative function if f and g are

[sand thorn]

Oh wait I have reread it

[sand thorn]

Thank you

[verbal zephyr]

the "fg(n) = f(n)g(n)" in the statement is just the definition of the notation fg(n)

[sand thorn]

So the prop is
f, g are both multiplicative => f(n)*g(n) is multiplicative

[verbal zephyr]

you missed one word

[sand thorn]

Both

[verbal zephyr]

one more xd

[sand thorn]

For all

?

[verbal zephyr]

f, g are both multiplicative => f(n)*g(n) is multiplicative

[sand thorn]

Ohh

[novel ore]

does anyone have any ideas for 1a? I tried writing it as the union of the sets A_n = {X in P(N) | |X| = n} and showing that each A_n is countable (ie a bijection onto N) but I haven't been able to come up with one

[verbal zephyr]

For a set to be countable, you only need an injection into N

[novel ore]

my prof defined it as |A| = |N|

but yeah that's the definition i've seen

but ig he wants us to use his

but yeah, i'm assuming an injection would suffice, bc other than that I have no clue how to construct a bijection

[verbal zephyr]

A bijection is not too hard either I think. For example, {X in P(N) | |X| = 2} is precisely N*N

You could use a similar construction to showing that Q is countable

Wait no it's not

Almost precisely the same (except for the diagonal)...

[cursive nymph]

on possible way:

take some particular subset {a1,...,an} and try to assign a number to it

what if we use some prime numbers?

[novel ore]

yea that's also an idea

i remember showing an injection from N x N into N also used prim enumbers

[cursive nymph]

just make sure that that 'assignment' is a function

[verbal zephyr]

But this will never make a bijection

[novel ore]

yeah but just in terms of injections it seems apt

[cursive nymph]

why not:)

if we do a1^p1 • ... • an^pn — no, not a surjection. not even an injection

what about p1^a1 • ... • pn^an?

tho first — order the a1,...,an's — bc ow it might not be a mathematical function

surjection part will follow from decomposing every natural into primes

[verbal zephyr]

How about {a,b,c} |-> 2^a * 2^b * 2^b?

Send any finite subset of N to the binary number that has a 1 in those positions

Bam immediate bijection

[cursive nymph]

this ain't injection

sends {1, 2} and {3} to the same number

[verbal zephyr]

No {1,2} gets sent to 6 and {3} to 8

O wait

That should be 2^a + 2^b + 2^c ....

As in binary numbers

[novel ore]

if we let A_n = {X in P(N) | |X| = n} maybe we could produce an injection into N x N x ... x N (this is the product of N n times over itself) and since that has the same cardinality as N that would show each A_n is countable?

oh wait no, sets don't preserve order

maybe adding up the numbers in the set?

nvm lol

[verbal zephyr]

My suggestion is: do (b) first, then use it to prove (a). You don't need the "countable union of countable sets" in this case

[novel ore]

this one is kind of annoying

b that is

because {0, 1}^n is clearly finite, it has cardinality 2^n

but i think i have to show that

in other words show that there's a bijection from {0, 1}^n onto 2^n (as a set)

[verbal zephyr]

Binary numberssss!

And then you can split up (a) not by cardinality but by the maximal element of the finite set

[novel ore]

uhh so would something like $f \mapsto \sum_{i = 0}^{n - 1} f(i)2^i$ work for a bijection onto $2^n$

[vital dew]

okeyokay

[verbal zephyr]

Yes

[novel ore]

oh wait no that could take values greater than 2^n - 1

oh

[verbal zephyr]

I think so? These are just binary numbers right?

[novel ore]

yeah it should work

but then I would have to show that $\sum_{i = 0}^{n - 1} 2^{i} \leq 2^n - 1$

[vital dew]

okeyokay

[verbal zephyr]

Thats an equality

[novel ore]

how

is there a formula i forgot

[grand totem]

That's a geometric series

[fast forge]

my automated DPLL algorithm works for most test cases except for one with over 100 clauses and I have no clue how to debug it except for manually applying DPLL to a 29 variable 123 clause set 😭

[verbal zephyr]

Could there be an overflow somewhere? Maybe try generating some smaller test cases that fail?

[fast forge]

Trying my best rn to do that

Its really strange

I'm pretty confident there's no overflow

[verbal zephyr]

Could be a fun case to learn about fuzzers

[fast forge]

Yeah probably should

Whip up a python script

Just generate satisfiable CNFs of a small size until my DPLL fails one

[verbal zephyr]

Is it crashing or just giving incorrect results?

[fast forge]

Latter

I'm considering even making it create tex output in a tree form so I can check where it's applying a rule wrong

[novel ore]

oh i thought the formula was only valid in the infinite case lol

[serene iron]

how to proof this? help $$\sum _{ u \ \in I } \ \sum _{ \left( u , v \right) \ \in E } f \left( u \right) = \sum _{ u \ \in I } \ \sum _{ \left( v , u \right) \ \in E } f \left( v \right)$$

[fast forge]

However that probably wouldnt exactly work since THIS is the clause set

[vital dew]

Aku

[serene iron]

It seems trival, but i can't give a concrete proof

The I is the set of all nodes， The E is the set of

all edges

[novel ore]

i'm having a little trouble on b, namely showing that f = g. bc what if f(i) = 0 and g(i) = 1 so that f(i) - g(i) < 0, then we could have f(k) > g(k) for some other term so that the sum would still be zero

i'm tempted to just say that oh each natural number has a unique binary expansion or whatever

but that doesn't seem rigorous enough

never mind

the terms don't cancel out

so we're chillen

or maybe i could just say they're linearly independent

[cursive nymph]

my solution didn't convince you? 🙂

btw, that's how we solved it in class

anyways

[novel ore]

lol mb i kinda skipped over the problem and will come back

[fast forge]

Off by one error in the stack of assignments

When backtracking instead of remvoing every assignment strictly after the point of backtrack

I removed the backtrack itself from all but one variable, so that inconsistency messed it up lol

[verbal zephyr]

Classic!

But then the question remains why the smaller test cases didnt catch this

[fast forge]

Yeah thats really strange

I guess maybe the smaller test cases just through sheer chance

didnt even have to backtrack?

[drifting sand]

I dont see how 💀

[drifting sand]

Ah wait i see it, damn

[lyric quartz]

The homset is isomorphic to the dihedral group D_6, right?

[novel ore]

does anybody know what the continuum is here

[inland raft]

R?

[novel ore]

yeah

[clever sail]

Yeah would be 2^\aleph_0

Which is the cardinality of the powerset of N

[hollow fractal]

Sorry, but someone told me to message this in #discrete-math which is why I am doing it because I am not sure how to solve the following problem:

[sand thorn]

Isn't the b) false for third case?

cause imagine u(81)

take m = 3

then m² = 9

So it works

But then n=9*9

So then gcd(9,9) is 9

So not multiplicative for all a,b

This is an assignment btw

Don’t give full response but do point out mistakes in reasoning or hints

[lyric quartz]

If gcd(a, b) /= 1 then there isn't a contradiction?

[sand thorn]

there is I think because that doesnt fit the definition of multiplicative functions which we're trying to prove for the 3rd case

if gcd(a,b) =/= 1 then it follows that it is not multiplicative

[lyric quartz]

If µ isn't multiplicative you have to show for some a and b s.t. gcd(a, b) = 1 that f(ab) \neq f(a)f(b).
What is your contradiction example?

[novel spire]

Could finite projective planes and combinatorial designs be appropriate for this channel, or would that be too advanced (and hence more appropriate for #combinatorial-structures)?

[sand thorn]

Ok I negated it incorrectly

Thank you

Can I get a hint on this problem I have no clue how to go about it

[maiden fern]

reduce it mod 8
x^2 mod 8 can only take values 0, 1, 4

[sand thorn]

Yup got it now but I spent far too much time on it

😭

[novel ore]

any ideas on bijections from (a) to (b)?

[vapid token]

(b) is clearly countable, right? just show a an injective function exists from (a) to (b)

[novel ore]

yes that's what i'm trying to do

so any ideas?

maybe i should try to inject the set into N

[vapid token]

Let $X\in\mathcal{P}{<\infty}(\mathbb{N})$ and define $\phi(X) = \sum{n\in X}10^{-n}$

[vital dew]

KirPlop

[vapid token]

the finite decimal expansion is a finite binary sequence

and $\phi$ is injective

[vital dew]

KirPlop

[novel ore]

ah yeah that works

thank you!

[vapid token]

https://cdn.discordapp.com/attachments/1228461037846532228/1254533648561213562/20240622_221056.gif

[marble tree]

Heyyy I think the answer should be
a) G is planar (i can't find a k5 or k3,3 minor)
b) G is hamiltonina (i found a hamiltonian cycle)
c) 4 colorable since G is planar
d) not sure yet

but theres no way our prof will take this as an answer as we will need to provide a justification/proof for each. so Im sorta lost as to how to prove a and b ?

[inland zenith]

you prove a) by producing a drawing/embedding in the plane. Just because you can't find K_5 or K_3,3 minors doesn't mean there aren't any, but if you can draw this graph, then it is definitely planar
b) it's enough to show the cycle
c) assuming this graph is planar, how do you know you don't need less than 4 colors?
d) is chi prime = edge chromatic number?

[marble tree]

ah thanks!

but for b) i found a cycle but would there be a way to concretely show that this is hamiltonian? maybe a relation/proof?

and yup for d its edge chromatic

[fossil mural]

this is a small enough graph that if you just give the cycle it should be obvious that it's hamiltonian

[inland zenith]

yeah it's easy for the reader to check that it is hamiltonian

[marble tree]

ohhh i wish my prof is like that 🫠

but yea ill try to work on it thanks!

[fossil venture]

What is 5 choose 7?

[oblique pelican]

,w 5 choose 7

[vital dew]

Results provided by WolframAlpha

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

Requested by dilly_19

[gusty dome]

anyone can explain where does |A{n+1}| gone? and how sum becomes k=1 to n+1

https://math.stackexchange.com/a/2038170/1048756

(The SS is taken from here)

i think i got it

$|A_{n+1}|=\sum_{1\leq i_1=n+1}|A_{i_1}|$

[vital dew]

Afzal σ − alg

[gusty dome]

now what about this

how they are equal

[haughty garden]

the first sum looks at all possible k-subsets of {1, ..., n} and the second sum looks at all possible subsets of (k - 1)-subsets of {1, ..., n} since i_k = n + 1 is forced

in this way, you enumerate over all subsets of {1, ..., n + 1}

another way to think about it is: any k-subset of {1, ..., n + 1} must either include the set i_k = n + 1 or not. If it includes i_k = n + 1, then you obtain a (k - 1)-subset of {1, ..., n}, which is given by the second sum. If it doesn't include i_k = n + 1, then you obtain a k-subset of {1, ..., n}, which is given by the first sum

and then you enumerate over all set sizes k

[gusty dome]

ok, but why the $\sum_{k=1}^{n+1}$ is outside?

[vital dew]

Afzal σ − alg

[haughty garden]

in the second sum?

[gusty dome]

rather than \sum_{k=1}^n

yes

[haughty garden]

probably for convenience

if you just do k = 1..n, then you're not considering the case where you obtain |A_1 \cap ... \cap A_n \cap A_{n + 1}|

[gusty dome]

i mean it makes sense now that why
$$\sum_{1\leq i_1<\cdots <i_k\leq n} +\sum_{1\leq i_1<\cdots <i_{k-1}\leq n<i_k=\leq n+1}=\sum_{1\leq i_1<\cdots <i_k\leq n+1}$$ but i wonder how we got $\sum_{k=1]}^{n+1}$ in the second equality (last line)

[vital dew]

Afzal σ − alg

[haughty garden]

remember that the k in the second case accounts for (k - 1) sets being chosen (since we force n + 1 to be chosen)

[gusty dome]

Oh yeah this makes sense.

[gusty dome]

oh ya sory its = rather than =\leq in the second sum (a typo)

Well now this proof makes sense

[haughty garden]

nice!

[gusty dome]

Thank You so much opengangs :D

[haughty garden]

nws :)

[lyric quartz]

@final veldt in your problem set 1 problem 1 (:D), can I use the fact that a signature is functional complete if it represents {v, -} or do you want the reader to use formula induction or something?

[final veldt]

No need to use formula induction

[lyric quartz]

I guess I would first have to prove that if a signature m is complete and that if n can represent every connective in m that then n is complete?

[final veldt]

You can skip that

[lyric quartz]

ok

Thanks

[dreamy shard]

Can anyone help me figure out on how to go about this?

I checked the reflexivity, symmetry and transivity already but dont know how to determine the partition

[brave rock]

In general it can be really hard to do this, but here are some ways to help write down the equivalence classes explicitly:

Try describing the equivalence class of an explicit example or two. For example perhaps you can describe the class of (0, 1). Try to write down the elements, maybe graph them, and try to describe them maybe in words first and then explicitly.

Notice that you can also rearrange the condition on the values a, b, c, and d in a nice way, by moving a and b to one side and b and c to another. If you think carefully about what this means, you can figure out the equivalence classes without computing anything.

Here is a fact about equivalence relations and partitions. For any set M and equivalence relation R, there is some set X and function f : M -> X such that m R n if and only if f(m) = f(n). If you can find a function f and a set X that is somehow meaningful, then you can describe the equivalence classes via this function f. Can you spot a good function f here?

[dreamy shard]

So something like (0,1) R (x,y) = 0-x = 1-y? and I could form that into x-y = -1.

[brave rock]

You could indeed

[dreamy shard]

you mean something like f(k) = x-y = k
and if I would replace the f(k) with f(a,b) it would mean the same as k = a-b?

ofc I need to write that different but is that close to the idea?

[brave rock]

So I'm not sure what f(k) = x-y = k means exactly but

Yeah, setting f(a, b) = a - b is a pretty good idea. Try making it work

[dreamy shard]

kk thx

[latent spruce]

what sites can i practice discrete math in?

[sand thorn]

For a)

I’ve looked at the definitions

Ive tried a few proofs but i cant find a link between gcd(ab) = 1 and the 3 above conditions

Or a zero divisor modulo

If someone can give hints or similar examples that would be nice

It’s an assignment so no full response

Ok no nvm i got it

[dense charm]

hey.
seeking help with a proof by weak induction question

Construct a proof by (weak) induction that, for every integer value of n > 27, the claim specified below is true. No marks will be awarded for anything other than a proof by (weak) induction. Please ensure that you clearly state your base case, your inductive hypothesis, and your inductive case, and show all of your work in full detail.

33 + 34 + 35 +...+(n+5)=((n^2) +((2*5) +1)*n) ÷2-513

[inland zenith]

wow, rng induction, that's something

[inland zenith]

what do you need help with specifically?

[dense charm]

Sorry, I edited the message, I realized the question was missing some stuff. I am struggling with the topic in general. I'd appreciate a breakdown

[inland zenith]

enclose it in `...` please or use LaTeX

the equation

backtick

it will appear like this

[dense charm]

okok thanks

[inland zenith]

can you please do that? I can't read what it's supposed to be

[dense charm]

trynna figure it out give me a sec. kinda new to this

[inland zenith]

no worries

[dense charm]

there we go

thanks for the patience

[inland zenith]

okay, so do you know what a proof by induction is?

@dense charm

[dense charm]

no, i feel like i'm genuinely lost in this class

[inland zenith]

no worries, a proof by induction is just a proof of a statement of the form "for all natural numbers n, something is true", it's a bit more complicated than that but for now that will do

[dense charm]

got it

[inland zenith]

and it's good to understand why it works, seeing as there are infinitely many natural numbers, how do you prove that it holds for them all? it's because the natural numbers enjoy a special property that there is a smallest natural number (1, or 0 depending on who you ask) and they are ordered, you can definitely tell whether a natural number is less than some other one

so that means that if you can prove that it holds of the smallest natural number, and also that if you "move up the chain" that it still holds, that means in principle you can continue doing it for ever

you know it holds of 1, and so you can show it holds of 2, so you can show it holds of 3, and so on

if you accept that, then the format of induction proofs is easy

first you prove that your statement is true of the number 1, which is called the base case

there is however one problem here, which is that this statement is not true of numbers smaller than or equal to 27 according to your assignment

so you would start by proving that it holds for 28

I hope that isn't too confusing

if you think about it this is also true of 1 because the implication 1 > 27 -> 33 + 34 + 35 +...+(1+5)=((1^2) +((2*5) +1)*1) ÷2-513 is vacuously true

that's why it's OK to start at 28 instead

are you with me so far? @dense charm

[dense charm]

how do i know whether or not it holds 0,1,2 or 3?

[inland zenith]

it holds for those numbers because the condition n > 27 is not satisfied

false -> x is always true no matter what x is

[dense charm]

ohh ok understood

[inland zenith]

great, so you first start by proving that it is true for n=28

that is your base case

then, you will assume that this is true for some unspecified natural number n

that is you assume that 33 + 34 + 35 +...+(n+5)=((n^2) +((2*5) +1)*n) ÷2-513 is true

this assumption is called the induction hypothesis

because you assume that it the thing you want to prove is true about some arbitrary number

[dense charm]

do i always assume it is true?

[inland zenith]

and if you can, under that assumpion, show that 33 + 34 + 35 +...+((n+1)+5)=(((n+1)^2) +((2*5) +1)*(n+1)) ÷2-513 is also true, this is called the induction step, then your proof is finished

[dense charm]

or only in this situation?

[inland zenith]

Always

it is the only way to prove statements that should hold for all numbers unless it is a trivial property

[dense charm]

ohhhhh i see

[inland zenith]

it's important to realize this isn't cheating, what you really are proving is that it holds for n+1, the induction hypothesis is just telling you that the last number in the chain has this property

the trick with all induction proofs is to find a way to rewrite 33 + 34 + 35 +...+((n+1)+5)=(((n+1)^2) +((2*5) +1)*(n+1)) ÷2-513 this kind of thing into something where you can use the induction hypothesis

find a way to use algebra to produce some subexpression that looks like either side of the equation in the induction hypothesis 33 + 34 + 35 +...+(n+5)=((n^2) +((2*5) +1)*n) ÷2-513

you might need some trial and error

in this case it's easy

[dense charm]

proving it would include me proving 33,34,35 and then substituting n for k to make sure it is for all other numbers?

[inland zenith]

you only need to prove it for one number, 28

although in this case that's a bit weird

maybe there was an error in the generation

[dense charm]

okok

[dense charm]

i wouldnt even be able to tell

[inland zenith]

I'd say you can prove it for n=30, that means you show that 33+34+35=(30^2)+(2*5+1)*30÷2-513, I hope that's true?

hmm, my calculator says it's not true

oh, my mistake, I misread your formula

[dense charm]

all good

[inland zenith]

ok

it's fine

it even works for 28

so you start with 33=(28^2+(2*5+1)*28)÷2-513

very annoying statement to prove

but yeah, I would say this is what was intended, to start with the first number that satisfies n>27

[dense charm]

ok this kinda help. my prof attached these slides thats like a step by step thing i'm not sure if i do it also or the question doesnt ask for that

i'll attach

here

[inland zenith]

Right, this is kind of like the definition of induction

[inland zenith]

it's a formal version of what I said here

for your proof the instructions only say to specify the base case, the induction hypothesis and the inductive case

[dense charm]

okok thank you very much

you actually broke it down so much for me. before it just felt like i was just following steps without reason

[inland zenith]

you're welcome! good luck

[fresh belfry]

Yeah so I have a set theory test in 8 hours and genuinely this thing still makes no sense. Every part by itself is simple enough, but putting them all together for convoluted proofs is beyond me. We'll see how this goes

[haughty garden]

good luck! 🫡

[sand thorn]

I know that I can aways multiple r1 by an r2 I decide to take such that it’ll turn into a huge number which is a multiple of n

Idk how to explain or prove that

Can someone help with that

No full answer this is an assignment, athough htis is kind of pretty much the finish part

[haughty garden]

is there a condition on r_2?

[sand thorn]

Yeah it cant be

0 or 1 I think

Let me double check\

[haughty garden]

If you can decide on what r_2 to pick, you can always pick r_2 to be a multiple of n

[sand thorn]

No it just cant be 0

[sand thorn]

Ok that’s smart

Thank you now im done with this gruesome proof

Discrete math is actually fun I must say though

Actually I dont think I can take it as a multiple of n

Or c would be equal to 0 mod n which it can’t be

This is a proof for the zero divisor

The only restrictions we have is that R1 cant be 0 or 1

And R2 cant be 0

But then the issue is that if n is a prime then R2 actually can never cancel both out I think

Hm

Ok I got one of the steps of hte proof wrong but thank you, I might post a new question i I still dont get it

Yeah I guess I’m not sure what to do next

It’s a draft proof so excuse the poor format

[haughty garden]

It might help to write out the definition of zero divisors and invertible elements a bit more clearly.

• a is a zero divisor if there exist some nonzero element x such that ax = 0.
• b is invertible if there exist some element y such that by = 1.
• Firstly, verify that ab ≠ 0
  We now want to show that there exist some element z such that (ab)z ≠ 0 and z ≠ 0

[sand thorn]

I guess that works, though it’s different from how our assignment defined them

[haughty garden]

Ok we can work with the definitions from your assignment

do you have the definitions

[sand thorn]

a =/= 0 mod n

b =/= 0 mod n

And ab = 0 mod n

[haughty garden]

as in, how do they define zero divisors and invertibility

[sand thorn]

The above is for zero divisor

For invertibility it is not defined in the assignment itself but in our textbook they define it as

Remainder of 1 or the same definition that you gave

I just realised I can prove it by ab = cd (mod n)

In 2 sentences

https://tenor.com/view/facepalm-cat-facepalm-cat-bruh-bru-gif-3855516381892795428

[errant trail]

How many derangements of the Set {1, 2, 3, 4, 5, 6, 7, 8, } begin with the integers 1, 2, 3, 4 in some order?

is the answer 81

[vestal bronze]

yeah

[vestal bronze]

there's no 3,2 in e

[errant trail]

thats the only wrong?

[errant trail]

how did u get 3,2

nvm

i figure it out

[fresh belfry]

Are there any other good resources for learning this stuff outside of lectures: I've got a whole year of discrete ahead of me? I've had some interaction with the libremath textbooks and thought they were decent, but wondering if there's anything else

[weary tiger]

i like

this book

[final cliff]

Kenneth Rosen's discrete math book is decent

Dang sniped

[weary tiger]

lmao

💀

[final cliff]

The schaum's series of books have some discrete books. Two iirc. One is a basic discrete math book. The other is a collection of solved problems.

[weary tiger]

u can read knuth after that ig

thats what im gonna do

concrete mathematics

[final cliff]

There's another really popular discrete book I always forget.

Epp? Epps? Something like that.

[weary tiger]

Susanna epp

yeah

thats another standard

book

i heard

its easier then rosen

[stiff plinth]

My answer for question 2 is 3x5x9x8,is it correct?

[mint moon]

Hi can someone help me with these questions please? 🙏🏻🙏🏻

[cursive nymph]

it's not immediately obvious to me either how to prove or disprove this:

countable union of uncountable sets is / is not of the same cardinality that only one uncountable set

[odd heart]

This is slightly imprecise, because the uncountable sets might have varying cardinalities.

Unless you mean countable union of uncountable sets which all have equal cardinalities.

[novel ore]

any ideas for a?

I've tried diagonalizing by setting f(n) = 1 if f_n(n) = 0 and 0 otherwise, but this doesn't work since it could lead to a sequence containing 00

[brave rock]

Hint: look at pairs of characters rather than individual ones

[novel ore]

wdym by pairs of characters?

[brave rock]

Group the sequence by pairs, not single characters

E.g. view 010101010101 as (01)(01)(01)...

[novel ore]

i see

i'll try that thanks

[wheat lichen]

You will get a 0 haha what a threat, anyway what have you tried

[dusky glade]

FR, Thnx but I've done it, it's funny because due to the way the q is set up, I was trying to add (2k+1)^2 instead of (2k+3)^2 and GOING mad because the algebra didn't prove the Expressions equal

[night magnet]

Why do I struggle with discrete math but no with coding, I hate this shit

https://tenor.com/view/penguin-explosion-пингвин-взрыв-взорвался-gif-15227356808687307063

[vast hare]

im using that as well for my class

[inland zenith]

math is hard

[cursive nymph]

no, it's because coding is easy

upd: i mean, i'm biased. i've been coding (unprofessionally) for a few years

but still: there isn't anything intrinsically hard in coding

[inland zenith]

it completely depends on what you mean by coding

[novel ore]

can somebody give me a hint for c?

[cursive nymph]

this is offtopic, but can you give an example definition of coding that is considered to be hard?

I just can't imagine it. 99% of 'coding'/'programming' is implementing ideas someone thought of

[novel ore]

leetcode

[cursive nymph]

I mean, you just implement your solution
u can solve it on paper if u want – the fun part
the coding part is just 'translating' it to 'another language'

[novel ore]

yeah i mean coming up with the solution is the hard part

idk maybe it's because i've only had like a year of experience with coding

but i thought problem solving from math would translate a little bit more over to coding

but to me it seems to be a different way of thinking

[cursive nymph]

<ChangeMyMind>
into what coding looks like as a job – not to any that I know of ) :
</ChangeMyMind>

[brave rock]

Hint: another way of seeing these functions is as sequences of disjoint sets that cover N: a set of things that get sent to 1, a set of things that get send to 2, etc. Two functions are equal iff these sets agree.

[brave rock]

The hard part of coding is designing and maintaining complex projects with delicate and intricate moving parts. Implementing a particular algorithm may be easy, but understanding the caveats and pitfalls of utf-8 and utf-16 while having to deal with HTTPS bugs and understanding what security flaws you could introduce when adding a new feature? That shit is hard as fuck.

[inland zenith]

have you tried programming in dependently typed languages? it is exactly as hard as math because it is math, writing correct programs is incredibly difficult and in many cases impossible, so if by coding you mean using a programming language to do some stuff that may or may not be right, that's not that hard

but programming can be very hard, it depends entirely on the domain

[cursive nymph]

I mean, this is just experience / debugging
not much thinking required, imho

u just bodge ur semi-working code with other quasi-working libraries until everything works just doesn't break

[inland zenith]

yeah, if this is your definition of coding you can go far by just winging it

and you can even be an excellent programmer, but if your standard is just "it's mostly right" then that is a lower bar than "absolutely right" as it is in mathematics

when you are writing important algorithms that need to be 100% correct it becomes very challenging fast

[cursive nymph]

yep
and in industry 'mostly right' is much much better than 'absolutely right'
because of limited time / budget requirements etc

[inland zenith]

Correct, that's how it is

[cursive nymph]

I meannnnnn...... we are very much stretching the definition of programming here xD
designing those algorithms – this ain't coding, this is computer science

implementing without bugs – not 100% possible to guarantee anything, but getting as close as possible to 'good enough' is experience and debugging

[inland zenith]

okay, you're right, I'm talking about computer science

[cursive nymph]

and btw, an 'average programmer' will never in their lives implement any crypo or whatever important algorithms that they will need to use in prod

most likely they will just stick to time-tested code

[inland zenith]

it is possible to 100% guarantee that certain code is correctly implemented, just not correctly specified

it's not possible to guarantee it for arbitrary code

[cursive nymph]

it is possible to 100% guarantee that certain code is correctly implemented,
your code runs in an os

[inland zenith]

it doesn't have to

[cursive nymph]

your code uses CPU instructions xDD

[inland zenith]

which often use verified designs

theoretically you could design your own CPU, but anyway, that's not realistic

that's beside the point, you can do your due diligence, you don't need to guarantee that nothing possible will go wrong

background radiation might flip a bit in RAM, etc.

but that's not an excuse to just throw your hands in the air if you really care

[cursive nymph]

i never said that
i just said coding it 'getting as close as possible to good enough' and 'bodging until everything just works' in real world

[inland zenith]

ok, I'm not arguing with you, I'm just saying that programming can be hard, it's not inherently easy like you said

[neon harbor]

I feel like your position is "easy programming is easy". Have you ever worked on a huge project with 1000s of lines of code? You have to figure out how to structure the code, what classes to make, how should things fit together, etc. If you program in C you would have to be careful of undefined behaviour, a small bug in one part of the code can affect a completely different part by magic. Or if you use async in JS or Rust for example you could get into some really tricky scenarios of deadlocks and race conditions. I feel like the truly "easy" part of programming is just "toy" programming, simple script etc. where you already know exactly what to write

[cursive nymph]

when I say 'easy' I mean 'not much thinking required'

[neon harbor]

yeah, that's the part I have an issue with. Programming is not just writing things in code, it's almost 100% thinking

of course you could just turn off your brain and change things randomly until bugs disappear, but I don't think you'll get very far with that approach

[cursive nymph]

Or if you use async in JS or Rust for example you could get into some really tricky scenarios of deadlocks and race conditions
again, in practice, you do not prove everything works
you just have to make sure it's good enough
you follow best practices etc

[neon harbor]

but if your program just stops randomly, it just freezes, what do you do then? How do you fix it without thinking?

[cursive nymph]

u debug with ur accumulated experience

we might have different definitions for 'thinking' xD

anyways, let's continue somewhere else ig

[neon harbor]

maybe, "debug with accumulated experience" sounds like thinking to me

[novel ore]

i'm trying to show that this set has the same cardinality as R - for this it suffices to show that |A| <= |{0, 1}^N| and |{0, 1}^N| <= |A|. Now |A| \leq |{0, 1}^N| by an injection, however I'm struggling with the converse. That is, how do I uniquely determine a binary string not containing "00" from any binary string?

[brave rock]

I would suggest using diagonalisation to show that it's uncountable instead, but if you absolutely have to show it has the same cardinality as R specifically, I'd think about encoding decimals in base 3.

[novel ore]

yeah it's an exercise later LOL

[spiral ocean]

are there any tips or resources to use to get netter at discrete maths?

[brave rock]

I'm afraid there's no trick beyond practice.

As for resources, I think there are suggested books pinned in #book-recommendations? If not you can ask there.

[sage ferry]

Can someone help me understand what an S-structure is and what it acually does for first order logic

I dont get the point of having a universe A and the idea of "interpretations of constants,relations, functions within the structure"

My best guess is that an s structure gives meaning to the constants, functions, and relations

So A could represent the universe "Cooking amongst family members".
Then an example of c^A could be the name of someone in the family.
R^A could be x cooks better than y or something

thats the only way it makes sense to me since right after truth assignments are only defined given an S-structure with a universe A.

[sick grail]

yes: similarly to how the truth of a formula in propositional logic depends on the truth of the propositional variable (which we would normally determine based on their meaning), the truth of a formula in first order logic depends on what you mean by your functions, relations etc.

and that process of assigning meaning is what the structures are for

[storm wing]

Would this be the correct place to ask about context free grammers?

[sick grail]

idk what those are, they might be advanced enough for #foundations

[storm wing]

they're in my automata theory class but I'll ask there, thanks

[sage ferry]

so the reason why we never needed structures for propositional logic is because we didn't really need context for truth assignments?

For some truth assignment v, (A V B) is true as long as A or B are true under v.

But for some S-structure with universe A = "Fastest runner amongs friends"
c^A would have different meaning then anothher S-structure with universe B = "Highest jumpers at home".

but now that leads me to the questions how is this different from just another truth assignment w in propositional logic?

If I wanted a representation of both universes A and B, couldn't I tweak truth assignments v,w accordingly?

[sick grail]

You're doing something weird with your universes

[sick grail]

like here the universe would just be "family members"

because that's what the variables x, y etc. will be

[sage ferry]

oh

[sick grail]

and for "cooking" to get involved, that's what the interpretation of R is for ig

[sage ferry]

ohh wait I think it makes sense now.
So the reason why propositional logic doesnt have structures is because the sentential symbols dont vary so the selection of a truth assignment v represents the whole context.

but in first order logic the universe decides the meaning of the terms and seperately the truth assignments decide the context they're acting in?

so you have control over both in first order but propostional logic has limited expression when you want to change the meanins of the actors?

[sick grail]

I'm not entirely sure what you mean by "truth assignments decide the context" or "change the meanings of the actors"

in propositional logic, we have no way to establish what propositional variables p, q, r whatever actually mean. the best we can do is say whether they are true or false

first order logic gives us that ability, so now we can express things like "all x are positive" or "2 is prime"

but this is clearly going to depend on our universe

the first is only a true if our universe is positive numbers, alongside with interpretations of "being positive" meaning greater than 0 (what's 0? it's a constant, or you can black box "positive" into an unary relation I guess and forget about 'greater than' and '0'), the second on what "2" is, since to begin with it's just a weird squiggle and we need to assign the meaning to it as 1 + 1 (and in turn what '1' is)

[sage ferry]

hmm okay

thanks, I'll look into it more but I've got a better idea now

I think it'll make more sense once I get to more concrete examples in the book

but I get the idea of what you mean

@sick grail

So like this, where the universe just directly assigns meanings to each f, R, and c

[sick grail]

the structure assigns meanings

[sage ferry]

yea sorry

[sick grail]

a universe is just what the objects are, in this case they're natural numbers

[sage ferry]

the universe is just a set of objects, and the structure assigns the objects to the symbols of S

[sick grail]

To the constants, not the function or relation symbols

• isn't a natural number, it's a binary function on the objects that we assign to f_0

[hollow fractal]

hello, apologies if this is not the right channel to send this, but I have a problem: We are given a simple graph of n vertices and k edges and assign nonnegative values to each vertex. Alice gets to choose an edge, and Bob gets to plus 1 to one vertex and minus 1 to the other if it is possible to keep both nonnegative. Bob wins if he assigns values on the vertices of the simple graph such that no matter what Alice picks, Bob can make a move in order to always avoid Alice picking a edge with 0 at both ends. Find the smallest sum of the values of all vertices given a simple graph

[hollow fractal]

refer to this image for simple graphs with small number of vertices:

[hollow fractal]

for the top left one, it’s 0, and we shall refer the next one by going down and subsequently keep going right until we cannot find a graph in that row. The next one is 0 too, next is 1, next is 0, next is 1, next is 2, next is 3, (and for the four vertices I am but unsure but I think I double checked: 0, next is 1, next is 2, next is 2, next is 3, next is 3, next is 3, next is 4, next is 4, next is 5, and finally the last one is 6. from this alone, I conjectured that f(n,k) = k (aka the number of edges), but I don’t even know how to prove this. Maybe by induction, idk?

[velvet knoll]

Is this equivalent to smallest independent set?

Or, sorry largest independent set

You want the largest number of vertices to be 0, and the remaining ones to be 1

[hollow fractal]

and also if no one knows a graph theory or other mathematical approach for this problem, at least it would be great if someone could write a program or python script for this problem :)). (for example the python script could be that we list the vertices a_i by their values and their interconnected edges as (a_x , a_y) for which we could test if Bob always wins due to problem conditions

[hollow fractal]

I am sorry, what do you mean by this?

[velvet knoll]

You want the smallest possible sum of all values on a simple graph where there is no edge with 0 on both ends right?

[hollow fractal]

yes

[velvet knoll]

And in that case, every vertex would either have 0 or 1 on it

And then since we want the smallest possible sum, we'd want as many vertices to have 0 on them as possible

[hollow fractal]

Not necessarily, it can be nonnegative meaning it can be 2, 3, 4, etc.

well I mean depends on the graph

[velvet knoll]

Uh

Then I'm not sure what you mean, like my understanding is if we have these two graphs

2 -- 3

0 -- 1

We would care more about the second one than the first, because the 2nd has a total sum of 1 while the 1st has a total sum of 5

[hollow fractal]

Oh yes, that’s true. 0 — 1 is optimal for that graph

It makes sense that we only use 0’s and 1’s to minimise the sum, but is that necessarily optimal or correct for all graphs all the time? I see it happens a lot though

[velvet knoll]

Well if all we care about is whether an edge has two 0s or not, then in any case we could use a 2 a 1 would work even better, right?

[hollow fractal]

yeah, if you are talking about that graph, ofc 2 — 1 is better than 2 — 3. In fact 0 — 1 is the best we can do

[velvet knoll]

So then the only things we'd want on our graphs are 0s and 1s right?

And we'd want as many 0s as possible on the graph, without any of them being connected to any other

[hollow fractal]

How can you prove that this works for every graph, especially one with a big number of vertices? Like I get your intuition, but I found cases where it might not be true

[velvet knoll]

Uhhh

[hollow fractal]

like for a 4 vertex complete graph, we can assign each vertex to be 1, 1, 1, 3 which is minimal?

[velvet knoll]

How is 1, 1, 1, 3 minimal?

[hollow fractal]

so youre implying that through a series of operations this can be changed to 1's and 0's

[velvet knoll]

Why not 1, 1, 1, 0?

[hollow fractal]

let us call a_1 = 1, a_2 = 1, a_3 = 1, a_4 = 0 in this 4 vertex complete graph. Perform an operation with (a_1, a_3) and then an operation with (a_2, a_4). No matter what there exists a (0,0) pair in the end

[hollow fractal]

the order of the operations in this case does not matter here

[velvet knoll]

Okay I guess I don't understand the question

[hollow fractal]

thats fine, what doubts do you have?

[velvet knoll]

Can you tell me what the graph looks like after you do these operations?

[hollow fractal]

sure, ill send a pic

[hollow fractal]

actually you only just need the (a_1, a_3) operation, mb

[hollow fractal]

here

[velvet knoll]

Why not do (a4,a3) ?

1,1,1,0 -> 1,1,0,1 ?

[hollow fractal]

oh because Alice wants to win no matter what which is why she picks (a_1, a_3)

[velvet knoll]

Oh I see now

I thought Bob was picking the edge and Alice was doing something else, mb

[hollow fractal]

ah thats fine

[velvet knoll]

Okay then, but wouldn't 1,1,1,1 still work?

[hollow fractal]

(a_1, a_3) and (a_2, a_4). no matter what Bob does Alice forces a (0,0) in the end of the complete graph

[velvet knoll]

Alright yeah

[hollow fractal]

try with smaller simple graphs and see how you go:

[hollow fractal]

for example, if you had a triangle of 3 vertices, the minimum sum is actually 3. and you can apply smaller graphs into bigger graphs too which should help you

[hollow fractal]

after finding the minimum for all these graphs, i conjectured that the minimum sum happened to be the number of edges in the graph, but idk if this is true or not (probably not actually).

[velvet knoll]

Hmm well

I think it's possible to show that the number of edges is at least an upper bound

Like, if you started with all the vertices being 0, then for each edge you added 1 to one of its vertices, then Bob could always swap that 1 between either vertex without affecting any other edge

[hollow fractal]

i think so but im not sure

[velvet knoll]

Okay well... think of the set of all graphs that can be made with that pattern, where for each edge a 1 is added to one of its vertices

For any edge Alice picked, Bob is able to do the change so that he winds up with another graph from that set

[hollow fractal]

how does he wind up with another graph? wait, are the graphs same, but just all the ways of adding 1 to one vertex of an edge different?

[hollow fractal]

i think it makes sense

[velvet knoll]

Yeah

Maybe I should have said another state

[hollow fractal]

thats fine, i get what you mean

[velvet knoll]

Great

Not sure how to get the lower bound tho, good luck

[hollow fractal]

do you know any programming perhaps for this problem?

[novel ore]

does anybody know how to show that b has the same cardinality as R

I know that the set of injective functions is the continuum

so I'd like to ideally define a bijection between the two sets

[lethal linden]

The exercise asks you to use diagonalization, so you want to show that no function f from N to non-infective functions N^N is surjective (using diagonalization).

Denote by I the set of non-objective functions from N to N.

If f is a function from N to I, your job is to construct a g in I which is not in the image of f.

[fossil mural]

well then 6 says to prove that it's the cardinality of the continuum, and i don't see how you can do that other than by constructing a bijection

[fossil mural]

if you have schroder-bernstein (if there's an injection from A to B and an injection from B to A then there's a bijection) then this is easy
if you don't then it's more annoying

[lethal linden]

Oh I see. It's about 6, which wants you to say something about (b)

I just read 5b

[fossil mural]

tbh i think what i'd do is show a bijection between that and N^N, the set of all functions from N to N

[oblique pelican]

something about constructing reals with sequences

[sand thorn]

assignment (no full answer) how does this work because i cant go back to the m of the “n” case cause m could be bigger for the “n+1” case

i thought of just doing n = r (mod m) and then n+1 = r+1 (mod m) issue is that m wouldnt necessarily be the same if i use induction

like imagine n+20 well then ck wont be smaller than k! if i dont change the m so the induction doesnt work if you get what I mean

[remote jay]

is there any way i can learn dicrete maths im so tired watching all the yt videos

[inland raft]

pick up a book

[inland raft]

but if there's a specific topic in discrete math that interests you then you could just get a book on just that too

[remote jay]

ican understand topics but i suck at solving problems :/

[remote jay]

any recommendations ?

[inland raft]

idk our class used Rosen but theres probably better ones around, try looking at some msg history in #book-recommendations

[remote jay]

im cooked

[inland zenith]

practice

do exercises, that's the only way to learn

[marble tree]

I was looking at a solution for this problem but I don’t understand the last step which claims that there is a ceiling of k/3 minor in G that corresponds to the one I got from induction hypothesis. Like I contract w to u and then to v to apply hypothesis but then how can I just claim that I must have a k/3 minor?

[lethal linden]

Do exercises, seek feedback, incorporate feedback, repeat.

[hard citrus]

how to find out in how many ways you can divide a group of 12 people into groups of 3,4, and 5 peoples? (of course each person can be in only one group)
is it 12C3+12C4+12C5 or 12C3 + (12-3)C4 + (12-3-4)C5 ? or some other way entirely? combinatorics is my weak spot and i struggle with basic questions

[cerulean plover]

i don't understand how E ends up being this; the probability of choosing a red ball is just 10/16, because there are 10 red balls out of a total 16 red balls, right? or does the fact that he must first choose a box make it so that the probability is different?

[haughty garden]

we can have the following splits:

• one group of 3, one group of 4, one group of 5,
• three groups of 4,
• four groups of 3

note that you can't have two groups of something; two groups of 3 will leave 6 people remaining and that can't be partitioned using the remaining group sizes, two groups of 4 will leave 4 people remaining and that can't be partitioned using the remaining group sizes

it suffices to compute the number of ways in each case

[cunning egret]

is there a closed form solution to the sum of factorials till n, so 1!+2!+...+n!

[haughty garden]

it depends on what you accept as a closed form

you might be interested in: https://mathworld.wolfram.com/FactorialSums.html

[cunning egret]

oh yikes, but thanks!

[hard citrus]

i didn't explain myself correctly, you have to divide them into a group of 3, a group of 4 and a group of 5

[haughty garden]

Choose the group of five first. Then of the remaining people, choose the group of four. Then of the remaining people, choose the group of 3

That gets you C(12, 5) * C(7, 4) * C(3, 3)

[agile magnet]

what is the sum $\sum_{i = 1}^n i * \log(i)$? I just need big-$\Theta$ analysis for this. Upper bound by saying $\log(i) \leq \log(n)$ is easy but not sure how to get a matching lower bound.

NVM got it

[fast forge]

Hi, kind of a long shot but I have a question since I believe I'm misunderstanding something when implementing my SAT solver
I know I shouldn't ask to ask but the question is kind of long, so if anyone is familiar with CDCL and the two watched literal approach when implementing unit propagation could you ping me?

[vital dew]

Spamakin🎷

[frosty blade]

is it the right understanding that " A If and only if B" means that B is a nesscary and sufficent condtion for A?

[cerulean plover]

Yes, the biconditional operator is symmetric

A necessary and sufficient for B, B necessary and sufficient for A

[frosty blade]

ok thank you

[fierce cedar]

when proving partial order relations, given we have a relation that is absolutely reflexive in nature (since every set is a subset of itself), could I say that "the following is vacuously antisymmetric given that for a R b, b R a, we must have a = b to satisfy reflexivity?

I mean I already know it has to be antisymmetric because spoiler it's specifically the subset relation but still

[dull charm]

Please I need a lot of exercises in logic, proofs, sets, and relations.

[oblique pelican]

You can have a reflexive relation that isn't antisymmetric.

{(1,2),(2,1),(1,1),(2,2)}

[fierce cedar]

I see. So a more acceptable statement would be the subset relation ⊆ is antisymmetric because a set A ⊆ A, and A = A?

[fierce cedar]

I have a good amount from this epp book, type "discrete math with applications epp" and the first result should be a PDF of it.

[oblique pelican]

Well for the subset relation it is true that if A ⊆ B and B ⊆ A, then A = B.

But for relations in general, it's not necessarily vacuously true that if it's reflexive then it's antisymmetric

[oblique pelican]

But basically what I said here is enough for proving that the subset relation is antisymmetric

[fierce cedar]

thanks man https://cdn.discordapp.com/emojis/921356905279021097.gif?size=48&quality=lossless&name=kurisugoodjob

[marble tree]

Heyyy guys I'm really struggling with proving minors. like edge contraction is really not braining 😅

My approach is induction like this, but I’m kinda stuck on the last part when I want to show that this will lead to a contradiction…

[dull charm]

Could you please send it to me on private

[fierce cedar]

yeah of course

[cursive nymph]

is the following a well-defined statement?

let A be a set. a,b in A
let R subset A x A be an equivalence relation on A

then either

• [a]_R=[b]_R; OR
• [a]_R intersection [b]_R = ø

---

we can't take the intersection if we are not sure if the sets aren't empty, right?

ah, wait
by reflexivity eq classes aren't empty
my bad

[cerulean plover]

do i have to state "transitivity property" when proving things?

i feel like the reader can pick up on that on their own, right?

like if i do x = y = z, then the next step i have x = z, i don't have to write out "transitive property", right

[lethal linden]

Depends on the context.

[cerulean plover]

the orange is my reasoning

i don't have to write out "transitive property" here, right?

i mean it doesn't hurt to

[oblique pelican]

Yeah I mean you can, but if thats not the focus of the topic youre on then it's a given (for integers/reals)

[lethal linden]

No, in fact it distracts because transitivity isn't what the proof is about.

It's the second equality that should be spelled out. The thrust of the proof is that you're applying the binomial theorem.

You should state the binomial theorem and say how this is an instance of it.

Or at the very least say "by the binomial theorem"

[cerulean plover]

i did in a previous step

[lethal linden]

Like this:
\begin{align*}
0 &= (1-1)^n \
&= \sum_{k=0}^n {n \choose k} 1^{n-k}(-1)^k && \mbox{by binomial theorem} \
&= \sum_{k=0}^n {n \choose k} (-1)^k
\end{align*}

[vital dew]

Cufflink

[cerulean plover]

binomial theorem is in my assumption, hold on

[lethal linden]

I'm not illustrating content that's missing, I'm illustrating how to guide the reader through the forest without getting lost in the trees.

[cerulean plover]

ah gotchu

kk

[lethal linden]

You can fully state the binomial theorem if you'd like, e.g., "Recall the binomial theorem: ..."

[lethal linden]

It's not like Pokémon. Gotta catch 'em all! Gotta list every assumption and theorem!

You're telling a story. Stories have an appropriate level of detail, depending on the nature of the story and the person reading.

Like, I wouldn't ever say "Assumption: (text of binomial theorem)."

If someone knows the binomial theorem, they don't need the text, but it might be helpful to give them a heads up about what to expect below. If someone doesn't know or doesn't recognize the binomial theorem they'd read that line and go "Uhh...how?"

So that line is either about reminding the reader of the content of the binomial theorem or giving them enough to go look up a proof in their own.

Hence, if you're going to include the text, you'd say: "We use the binomial theorem: (text)" or "Recall the binomial theorem: (text)" or something similar.

[proper beacon]

I’m super stuck on this problem - 3 fair 6 sided die, what is the probibility that the product of the 3 rolled is not a multiple of 8

[true venture]

First, what are all the possible products you can get rolling the 3 dice?

[proper beacon]

1-216

[true venture]

Ok, then what have you tried next?

[proper beacon]

I tried splitting into cases

So like we know we must have 3 factors of 2 minimum to have multiple of 8

I also wanted to solve all cases that are a multiple of 8 then doing 1 minus that

Would it be easier to do the opposite because I feel like accounting for cases with 4 might be annoying

[true venture]

Can you write a program, or do you need a written answer?

[proper beacon]

Written answer

[true venture]

Dang, I think the first approach is good then think of all the ways to get a multiple of 8

[proper beacon]

alright

So for all evens there are 3^3 ways

We must have minimum 2 evens

[true venture]

Yea you need 3 evens

Or yea 2×4×1 works

[proper beacon]

But thays weird to solve becusse not all two even cases will work

Like 2x2x1 won’t work

[true venture]

Yea

[proper beacon]

I’ve been stuck on this problem for like 2 days haha I really don’t know how I should approach it

I feel like it’s the right track

I have an idea for the two evens we have 2 choices for the even spots being 4 and 6

Then 4 for the last did

[true venture]

Think you can just find all triplets that have at least 3 factors of 2, then account for all permutations of those triplets

I would just write out all the triplets first

[proper beacon]

With factors of 2?

3 factors of 2*

[true venture]

No like (2,2,2) (2,2,4), (2,4,1)...

[proper beacon]

Ah ok

[true venture]

Wait I've errored 6×2×1 is not a multiple of 8

[proper beacon]

Hmm

I wonder if it’s easier to go the other way we know that 3^3 will not be a multiple of 8

[true venture]

No, duh 621 is only 2 factors of 2

[proper beacon]

So we know it must be 6 and 4?

Or 4 and 2

[true venture]

So yea, first find all distinct triples that have at least 3 factors of 2.

[proper beacon]

So that will be 3 choices for the odd number, 3 choices for the even then we make the last one 4 ? So 3x3x1 cases

Wait don’t we know that we must have a 4 becusse we can never have just 6 and 2

In the case of it being one odd

[true venture]

For the triples you can first order them, so how many start with 2, how many start with 4...

Only the even numbers need to be ordered

Because once you find all distinct triples of numbers 1-6 that mutiply to 8k, you can find all permutations of those triples. That gives all ways to roll the dice and get 8k

[proper beacon]

That makes sense

For the case that the first die is 4 don’t we need to take out the permutation with a repeating 3

4*

[true venture]

Starting with 2:
(2,2,2)
(2,2,4)
(2,2,6)
(2,4,1)
(2,4,3)
(2,4,4)
(2,4,5)
(2,4,6)

[true venture]

Idk, for this it is helpful just to write them all out. Then you can probably find a better pattern or closed form for the total number

[proper beacon]

Would it be 1x2x3 for the cases that have an odd number then we permute that so x 3!

Wait but for the other cases we would be over counting Nevermind

[true venture]

Did you write them all out?

[proper beacon]

Maybe we just permute the last two digits ?

Mostly

[true venture]

There are only 6 triples other than the ones starting with 2 I think

[proper beacon]

Ok

I have an idea I’m gona solve it and see if it works

[true venture]

I get 6/27 as the probability that a roll of 3 dice is a multiple of 8

[proper beacon]

I’ll see if I get the same

[true venture]

The answer to the original problem, will be 1 - 6/27

[proper beacon]

Yeah my solution doesn’t work I didn’t do it right

Did you brute force it ?

[true venture]

Pretty much

I wrote out all distinct triples that will multiply to a multiple of 8. Then summed up all the permutations of each triple. To get all the total number of dice rolls that product to a multiple of 8.

[proper beacon]

Ahhhhhhh

I seee

4 4 4 is missing no?

[true venture]

From the ones i typed above ? Yes

[proper beacon]

I got 7/8

My ta in my class said that the solution was 1- (216/8)(216) which is the same

But I really didn’t beleive him

[true venture]

Oh, they are probably right

Oh I forgot a few

[true venture]

With the ones I forgot I still get 2/3.

[proper beacon]

Hm

Wait

Nevermind

Look at what I did

[true venture]

Good write up

What about (4,4,6), is that counted?

Oh all even, I see

(4,6,5)?

[true venture]

How are (4,6,1) (4,6,3) (4,6,5) counted?

[proper beacon]

Sorry I’m had class, thanks for pointing that out though I didn’t account for that

Got .819 with that last case

How did you get 2/3?

[true venture]

I get 72 total ways to roll a multiple of 8.

(216-72)/216 = 2/3

3^3 =27 with all even
3! * 3 =18 for (2,4,odd)
3! * 3 =18 for (4,6,odd)
(3!/2!) * 3 =9 for (4,4,odd)

27+18+18+9=72

[proper beacon]

That’s what I did do I think I must have some arithmetic error

Thanks for the help !!!

[civic dew]

If a planar graph has loops, do they count as a face when constructing the dual graph?

Would they be considered a single face enclosed by a single edge?

[novel ore]

why do we need two maximal elements in 1c? can't we just say if there is a largest element x and we have one maximal element m, m < x, contradicting the maximality of m?

[fast forge]

x=m in that case

[novel ore]

ah right

[novel ore]

well isn't this the case only for a weak order

if a < b then we can't conclude b < a

no matter if it's maximal or not

[fast forge]

if a < b and b > a in a total order, then a=b

sorry

oh

wait

no yeah if its total umm

no but how can you only have one maximal element that isn't the largest

if there's one maximal element it's implied said maximal element is also the largest

[novel ore]

how tho, isn't that what we're trying to prove in the second half of 1c

[fast forge]

does strong order mean it's total? i.e all elements are comaprable

[novel ore]

i don't believe so no

[fast forge]

otherwise it may be the case that there is a uniquely maximal element that is incomparable

i.e the skyscraper is maximal since no building is taller than it, however (this is a bit of a strange example) you can't even say its bigger than a shack because it's just not comparable

[novel ore]

yeah i'm just trying to think of a example involving set theoreteic inclusion

because something like {{0}, {1, 2}} doesn't work since {0} and {1, 2} are both maximal elements

hence not unique

is this even true?

[fast forge]

If neither are comparable they're both maximal

but Im also confused yeah

[novel ore]

yeah but they said unique maximal element contradicting two maximal elements

[fast forge]

I think the solution would involve a lone element with no connection to the main "island" of the relation

So it's only related to itself

But then I'm trying to imagine how it could be the case how the main island has no maximal element

Since the relation is transitive it can't be the case that an element in the island is related to the lone element since that'd mean the entire island is lesser than the lone element

@novel ore Oh it says there can be more than one maximal element

what if there's a set {a, b} such that the relation is just empty

a and b are both maximal and unique but neither are the largest

[novel ore]

i see i see

wait by unique element they don't mean only one right

there can be multiple unique maximal elements

?

@fast forge

[fast forge]

No

Just that it's not equal to the other maximal

And by equal not like

ordered equal, like they are just not the same element

[novel ore]

i see

thanks for the help!

what is a strong linear order? aren't these two incompatible lol

strong order means a < b => not b < a

wait nm

[silk talon]

hey all, do you recommend any resources to prepare for discrete mathematics or at least get a head start before i go into CompSci in the spring? thanks!

I have never been very good at math but I really wanna learn because i've always been fascinated by it :D

[novel ore]

in general for proofs i would recommend How to Prove It by Velleman

it also covers most of discrete math

[silk talon]

thanks! i'll give it a look 👍

[novel ore]

bruh wait how is this true, if R is a linear order and a, b in A, then either a = b, a < b or b < a, if a = b then (a, b) = (a, a) is in R, but then we can't have (a, b) or (b, a) in (A x A) \ R because then (a, b) = (a, a) = (b, a) \in (R)...

[oblique pelican]

You can also check out Discrete Mathematics and it's Applications by Kenneth Rosen. It's definitely a much longer read than Velleman, but itll also cover graph theory which isn't in How to Prove it.

[silk talon]

thank you!

[fierce cedar]

Chains are implicitly tosets as they’re subsets containing all the comparable elements of a poset, right?

I’m working with Epp’s book but each chapter confuses me more and more prof is lowkey bouncing around

[true venture]

Yes, chains of poset P are themselves posets.

Oh, toset

Yes chains are totally ordered, or have a total order

[crimson hemlock]

i got this question for homework:

2. In this question, x represents some specific integer (Note: it just means that you do
   not know its value). In each of the items there is a mathematical statement. Determine
   whether it is true or false, or whether this cannot be determined without knowledge of
   the value of x. If the truth value cannot be determined, show one example of a value of
   x for which the claim is true, and one example for which the claim is false.
   (a) x2 + 1 = 0 or x ≤−2.
   (b) If x^2 = 4 then x = 2.
   (c) If x^2 = 4 then x^4 = 16.
   (d) x < 4 if and only if x ≤3.
   (e) If x^2 > 0 then (x > 0 or 0 > x).

i assumed it was
a) depends (T:X=-3, F:X=3)
b) F
c+d+e) T

but some people suggest the case for (b) in which they say it depends because, of course, if the first part is false, then the statment is correct.
but for the x=-2 case, its true leads to false, which is false. which mean it could either be true or false. what do you think?

[patent pilot]

am i overthinking these problems or just dumb lost, and if you have a recourse I could use to help me solve them (that isnt chatgpt or chegg) id appreciate

I think you would just write out the series a0= a1= a2=
and then use induction and do the
Base case
induction hypothesis
solve

is there more to it then that or no

the last part too says "what common mathematical operation does this sequence implement?" which afaik it wasnt in lecture

[lethal linden]

For (5), what is a_10?

[patent pilot]

would it be 120?

[lethal linden]

How did you calculate that?

[fossil mural]

that looks like you calculated a_5, not a_10

[patent pilot]

and i read him asking for a_5 not 10

brb

[lethal linden]

Yes, a_k is k factorial

[lethal linden]

Reflect on your "afaik it wasn't in lecture" 😉

It vanished as soon as you looked at a few concrete examples.

So your job is to prove that a_k = k! by induction

[patent pilot]

I got induction down

As for the last portion asking for the common mathematical operation does this sequence implement

will that become more apparent or is it just google search

[lethal linden]

You said it yourself! Factorial!

They want you to notice that this is the factorial function and prove it

[patent pilot]

Thanks cuff for the explanation it definitely helped alot

[fierce cedar]

Awesome! Thanks

[cerulean plover]

in this question, why is the combinations formula used instead of the permutations formula?

shouldn't a bitstring "1111000000" be counted as different from the bitstring "0001111000"?

the order of the 1's in the number does matter

nevermind i get it now. the order at which the numbers are selected doesn't matter, but the position of the numbers in the string does matter

[dull charm]

hello, I need some final exams in discrete maths examples, urgently

[brisk lagoon]

Guys someone help me with thus

I dont understand why did we put in the steps S --------> t at first?

and i dont understand how we did the steps

[novel ore]

I'm trying to show that $(A \times A) \setminus R$ is a linear order, however I'm having trouble in the case that $a = b$ and $(a, a) \in R$. If that's the case, $(a, a) \notin (A \times A) \setminus R$; moreover, $(a, b) = (b, a) = (a, a) \notin (A \times A) \setminus R$, so it appears that $(A \times A) \setminus R$ is not linear; where am I going wrong?

[vital dew]

okeyokay

[novel ore]

oh nvm, (a, a) is not in R since it's a strong order

[snow cedar]

I'm having trouble understanding the concept of k-degenerate graph. Informally I was told that it means every vertex has at most k "forward" neighbours.

But I'm not sure how to draw an example of this for say, 2-degenerate. Can someone help me out?

Like starting from the graph, then knowing how to label the vertices

[inland zenith]

how do you prove that a graph doesn't have a topological minor?

I think I have an idea, find a cycle in the topological minor and show it doesn't exist in the graph, subdivisions can't create new cycles

I don't think that will work in this case sadly

oh wait, yes it will, use the hamiltonian cycle (the minor is K5)

that definitely is not in the graph

[cerulean plover]

s implies t, and t is false. therefore, s is false. you need the context of "s implies t" and "not t" to get to "not s"

[snow cedar]

Not sure how to see the contradiction for the => part, I think the issue is i don't know what to actually look at

[sand thorn]

(Assignment) I am unable to do the inductive step

[inland zenith]

the algebra here is just wrong, x^(2^(m+1)) is not the same as (x^2)^(m+1), and also (x^2)^(m+1) is not (x^2)^m+x^2, it's (x^2)^m * x^2

maybe try again with that in mind

[sand thorn]

Thank you

[sand thorn]

I'm kind of stuck here too

Cause a^p - 1 is not congruent to 0 for all "a"

and since a^p - 1 encodes all of the terms that should at least have 1 of them possibly be divisible by the prime

then i should be getting another result

[sand thorn]

Problem solved

Small mishaps

[marble tree]

Hey guysss i feel like this problem should be relatively straight forward induction on number of vertices and then proving the induction case by removing a vertex with strictly less than 10 neighbours and adding it back in.

But i dont know how to work out a degree argument with "no k4" graphs

any help would be really beneficial 🙏 🙏

[haughty garden]

Hadwiger’s conjecture on k = 4 tells us that H is 3-colourable

[snow cedar]

Anyone have advice for this? I think it is hard to find the contradiction for me because I don't fully know how to use the definition

[haughty garden]

do you have the formal definition that your class is using for k-degeneracy

[glossy orchid]

hi i have a problem with this predicate proof, would this be correct? if not im unsure from line 10

the last part thats cut out (my bad) is ... or exists z in U (not Q(z))

[marble tree]

Humm thats true, and then I can conlcude via four color theorem that G is 4-colourable. But then dealing with the color overlap cases would be tough

[tawny orchid]

[
\sum_{x}^{} \sum_{y}^{}
\left(
\binom{40}{x} +
\binom{35}{y} +
\binom{25}{10-x-y}
\right) =?
\binom{100}{10}
]

[vital dew]

MadAbdo

[weary tiger]

what is the difference between discrete and continous meth?!

[versed oasis]

{0, 1} vs [0, 1]

[bronze spire]

set vs domain?

[versed oasis]

interval

[clever sail]

before and after melting it

[sand thorn]

Lol

[muted pumice]

Let A=[1, 3], B=[3, 5], C=[2, 4] and D=[4, 6]. What is the set of (A × B) n (C × D)?

[thorn tusk]

meth! 🤤

[muted pumice]

So the answer is =[2,3]×[4,5] or ={(2,4), (3,5)} for (A × B) n (C × D)?

[oblique pelican]

the first one yes

{(2,4),(3,5)} is just a set of 2 points or a set of 2 intervals (intervals are sets, so it could be a set containing 2 sets)

[muted pumice]

so {(2,4),(3,5)} cannot be written as answer because it is just set of 2 points (does not form a rectangle)

then if I write all the four points in a set (to form rectangle), can it be as an answer?

[fossil mural]

well no because like

(2.3, 4.6) is also in (A × B) n (C × D)

but it's not any of the four corners

there's not really any way to write the answer by just listing every point because there are too many points in that rectangle for it to be reasonable to list them

[muted pumice]

okay, but by Cartesian Product of two sets A and B, they list all the ordered pairs (x,y) such that {(x,y)}. How do you know by forming as an answer for A x B = {(x,y), …} or A x B = [x1,x2] x [y1,y2]?

is the set of A x B (to form as a rectangle) only used to = [x1,x2] x [y1,y2]?

[fossil mural]

...i don't actually understand what question you're asking but i guess i can just say some more things and hope that works?

so yes, A x B is the set of all (x,y) with x \in A and y \in B

but [2,3] and [4,5] have a lot more elements than just 2, 3, 4, and 5

(if we were looking at {2, 3} x {4, 5} then this would have only the four points (2,4) (2,5) (3,4) (3,5) and is therefore equal to {(2, 4), (2, 5), (3, 4), (3, 5)})

so in an abstract sense it's the same thing, the problem is that it's just not practical in real life to list all of the elements of an infinite set one by one

you could spend the rest of your life just adding more points that should be in there and you'd have done basically nothing compared to how many there are in total

so that's why we're writing it as [2, 3] x [4, 5], because it's infinite

[civic pike]

i was doing my discrete math homework and i somehow discovered that adding up the total number of permutations of a set of n elements (nP0 + nP1 + nP2 ...... + nPn) equals floor(n! * e)

is this known to be true cause I don't know where to look up if it's true

i don't think it's super useful info anyways lol but i thought it was neat

[fossil mural]

...huh
yeah i think that is true actually

nPk is n!/(n-k)!

so you end up with $n! \sum_{k=0}^n \frac1{k!}$

[vital dew]

bee [it/its]

[civic pike]

yeah that's what i did

[civic pike]

oh hey that's my textbook!!

❤️

[cerulean plover]

it's a pretty popular one i'm sure

[civic pike]

yeah we're on the same topic right now

i just got done doing the problem right after

[snow cedar]

I attached a photo in my image, that's the one we use

[marble tree]

I am like 99% sure I should prove it using a similar argument as Schur's theorem's proof but I am struggling coming up with how I should color the edges and like if it is actually a k6 that I want to construct?

[glacial turret]

Is there a notation for the degree of the term with the lowest degree in a polynomial?

something like if $P(x) = \sum_{i=0}^n P_i(x)$ where every Pi is a monomial, then $F(x) = min{deg(P_i)|o\leq i\leq n}$

[vital dew]

VY (Logic_VY)