discrete-math

[chrome osprey]

p and ~q

~(p -> q) = (p and q)

[unreal stump]

Let q=a/b for a,b integers , then consider r=1/b

[chrome osprey]

i think?

[chrome osprey]

this results in an integer

but

[unreal stump]

Yeah that's the proof

[chrome osprey]

how do u find that

like

and how do u know there isnt a case where that fails

[unreal stump]

How do you prove what

[chrome osprey]

that the proof is all encompassing

[unreal stump]

There are always such integers a,b

[chrome osprey]

is finding a proof just

sitting and thinking

[unreal stump]

So given a q=a/b ,setting r=1/b finishes the thing

[chrome osprey]

until something hits u?

is there any like

[unreal stump]

Well you either do a construction

Or a contradiction

[chrome osprey]

this is a construction

right?

[unreal stump]

Or well you reduce it to a thing that you know to be true

Yes

[chrome osprey]

but ultimately

u just kinda

thought it thru right?

and it was correct?

[unreal stump]

Yeah

[ebon berry]

Someone helped me from a different server so nvm but tysm

[unreal stump]

Reductions are ultimately the ultimate thing in math

[chrome osprey]

gotcha

ok so i came up with what u typed out

but i just

didnt know if it was like

the complete proof

as in, i didnt know how to get to it in the first place

i just kinda thought about it and thought it made sense

i also only considered the case where b != 0

[unreal stump]

b will always be nonzero

[chrome osprey]

ok wait

did i write the negations properly?

also for the second case

is it also true

[chrome osprey]

@unreal stump

can z = a - b + 1

and its always true?

i feel like i set the negation up wrong for the 2nd one

both can always be true i think

[unreal stump]

Both negations are correct

[chrome osprey]

and both the given statements are true, and negations are false?

i dont understand how to prove the negation of 2 as false

is the given true, with z = a - b + 1

or is the negation true, with x = z, y = 0

[unreal stump]

For 2nd negation is true

[unreal stump]

Yes

[chrome osprey]

what about the given

are they both not true?

@unreal stump sorry for the ping again

im just

really confused how to prove

[ivory badge]

What do you want to prove

[chrome osprey]

that either the given or negation is wrong @ivory badge

so

x - y < z, for x,y int, there exists z int

or

x - y >= z, there exists x,y int

[ivory badge]

So you just need, for all x, y an integer greater than x-y?

[chrome osprey]

yea

or the negation

there exists an x - y that is always greater than z

given sol: z = x - y + 1
negation sol: x = z, y = 0

idk what to do

[ivory badge]

Notice that \exists z is before \forall x, y

[chrome osprey]

oh the order matters?

[ivory badge]

So you pick such a z, then all x, y satisfy x-y<z

yes

[chrome osprey]

so the negation is true?

not the given

interesting

[ivory badge]

Consider

$\forall x \exists y (x-y=0)$ i.e. y=-x

$\exists y \forall x (x-y=0)$ i.e. x -y= z-y = 0 for any x, z

[vital dew]

The great Sharp

[chrome osprey]

what?

i dont get it?

[ivory badge]

these are very different statements just interchanging \exists y and \forall x

Namely the bottom one really shouldn’t be true

[chrome osprey]

right

bcoz u dont know x

where as top one, u know x, and u can pick accordingly

[ivory badge]

Well, think \forall x P(x) and \exists y Q(y)

P and Q are entirely different things there, and the succeeding quantifiers can depend on the previous ones

Like a limit, for all epsilon>0 there exists a delta>0

[chrome osprey]

ah right

so the reason the given isnt true is because u are defining z first?

i think?

[ivory badge]

If you have multiple of the same kind of quantifiers they’re a bit more amenable to interchanging

[chrome osprey]

right

[ivory badge]

More like you’re requiring one z to be greater than all x

[chrome osprey]

sorry, thats what i meant

because u have said that there exists the z first

[ivory badge]

Rather than saying you have at least one such z for each x

[chrome osprey]

without knowing what x could be

yea

sorry that was i was trying to say

because z is defined first, it must be for all x

where as if u define all x first, z can be pick and match

right?

[ivory badge]

So this idea is a bit uhhhh constructive-y, but it’s not too bad intuition-wise

Think of \forall x P(x) as giving a function from where x is to a proof of P(x)

[chrome osprey]

x proves px

[ivory badge]

And \exists x P(x) as saying you can have a pair (x, proof of P(x))

So if you were to look at it you’d consider the first as a pair (z, function from (x, y) -> proof of x-y<z)

The second is a function from (x, y) -> pairs (z, proof x-y>=z)

[chrome osprey]

and so the second is definitive?

or

more solid?

[ivory badge]

The second is true, because consider x-y-1

That gives you a z for each x, y

The first isn’t, because x=z+1, and y=0 makes it impossible

[chrome osprey]

righ

[ivory badge]

And this function evaluation idea is just universal instantiation

$\forall x P(x)$ implies $P(u)$ right?

[vital dew]

The great Sharp

[ivory badge]

It’s true for all x, so clearly it’s true for x=u in particular

[chrome osprey]

right

thats true

[ivory badge]

And similarly P(u) -> \exists x P(u)

[chrome osprey]

gotcha

ok i think that makes sense

ill let it sink in

and it should be fully sensical to me

[ivory badge]

Don’t go swapping the orders, since (z, f:Z^2->proofs) is not quite the same as f:Z->Z^2 x proofs

(This is not a precise thing don’t worry about it too much, it’s just showing they look very different practically)

[chrome osprey]

ok np

[proven kayak]

Can someone explain how you would do the second question about the extra student

Do I just need to add an edge to my graph which makes it impossible to have 4 time slots?

[unreal stump]

Just think about how it reads in normal English

This is all notation for statements that could be in English

[iron marsh]

Okay, say we have a linear recurrence relation, and we are given that the characteristic equation has a repeated root (r).
How can we guarantee that nr^n will also solve the relation?

[unreal stump]

Do you know how to solve ODEs

[iron marsh]

Yep, and I know te^rt is the analogous solution for a repeated root

[unreal stump]

Ok so look up exponential generating functions

They are about reducing linear recurrences to ODEs

And you map the solutions of ODE back to solution of linear recurrence, so that gives you what you are asking

[unreal stump]

Well it's also n^2 r^n ,n^3 r^n ...

[iron marsh]

Doesn't that depend on how many times it repeats?

[unreal stump]

Well yeah

In ODEs these correspond to t^2 e^t and so on

[iron marsh]

Going about that, I guess I kind of have a similar question with repeated roots. Yes Cte^(rt) is a solution to the differential equation, but how do we know it is the only other family of solutions (assume root has multiplicity of 2).

[unreal stump]

Ok so there is this theorem called primary decomposition theorem which allows us to reduce this problem to "finding all solutions of the form (D-aI)^k y = 0"

So if your char equation is (x-2)(x-3)^2, solve for (D-2)y=0 and (D-3)^2y =0 and combine the solutions

Well if this is fine, you just solve (D-aI)^k y=0

Where D is the differentiation operatod

[iron marsh]

what is aI?

A constant times the identity matrix?

[unreal stump]

Yes

[iron marsh]

Okay. Right now, I am specifically looking at (D-1)^2y=0 to start. I know this should end up giving a repeated root. But how do we come to that conclusion?

[unreal stump]

You know (D-1)y =0 implies y=e^t correct?

[iron marsh]

100%

[unreal stump]

So consider g(t)=(D-1)y

So g(t) has to be ae^t for some a

Now you solve (D-1)y = a e^t

So a particular solution is a t e^t

So general solution for this is given by y(t)= a t e^t + b e^t

[iron marsh]

Again, I think this comes back to the idea of how do we actually know that?

[unreal stump]

Well you just guess

It's fine to guess one particular solution

[iron marsh]

Most books tend to say, oh hey, this thing that we tried works. But is there a way to actually derive that. That's really what I am interested in

[unreal stump]

Well you can do a by parts on this

[iron marsh]

oh? How so?

[unreal stump]

Because this is of the form y'-ay=f(x)

[iron marsh]

Follow up: how did solving this help with the original problem?

[iron marsh]

you are absolutely right though. Integrating factor does wonders here

[unreal stump]

So to get (D-I)^2 y = 0 your y has to satisfy (D-I) ( (D-I)y) =0, so for that (D-I)y has to be of the form ae^t

Because (D-I)y has to be in kernel of (D-I)

[iron marsh]

Okay, I think I am following

[unreal stump]

So you do a similar argument for arbitrary powers

Did you understand the k=2 case?

Well try around with different a where (D-aI)^2 y=0

[iron marsh]

Ah, okay I am seeing it. Consider the $n+1$ case. For $(D-1)^{n+1} y=0 \Rightarrow (D-1)^{n} [(D-1)y]=0$. Thus, $(D-1)y$ is in the kernel of $(D-1)^{n}$. But at this point we know the solution to $(D-1)^n y$ is [g(x)=A_0e^x+A_1xe^x+\dots+ A_{n-1}x^{n-1}e^x,]
so we can simply solve for when $(D-1)y=g(x)$, and that will give us the $n+1$ case.

[vital dew]

dackid

[unreal stump]

Yea

[iron marsh]

Okay, took me a minute, but I totally understand it now.

Now say we have a exponential generating function y that satisfies $(D-1)^2y=0$.
Then $y(x)=Ae^x+Bxe^x$ is a general solution. So how does this translate over to the recurrence relation, which would be $c_n=2c_{n-1}-c_{n-2}$?

[vital dew]

dackid

[unreal stump]

So you consider $F(x)=\sum_{n=0}^{\infty} \frac{c_n x^n}{n!}$

[vital dew]

DraK

[iron marsh]

Okay, and c_n is the coeffiecients for the sequence

[unreal stump]

So do you know F' looks like in terms of c_n

[iron marsh]

well F(x)=F'(x) in this case

[unreal stump]

$F'(x)=\sum_{n=1}^{\infty} \frac{c_n x^{n-1}}{{n-1}!}$

[iron marsh]

Oh no, you are generalizing it

Yea, I agree with that

Though n needs to be shifted by 1

[unreal stump]

mb

[vital dew]

DraK

[unreal stump]

So this is $F'(x)=\sum_{n=0}^{\infty} \frac{c_{n+1} x^n}{n!}$

[vital dew]

DraK

[unreal stump]

Similarly for F" it will be c_{n+2} instead of c_n

[iron marsh]

okay sure. I am with ya so far

[unreal stump]

So the main idea is F" = 2 F' - F

You get that if you compare coefficients of each term

[iron marsh]

Yea, we do end up with that relation.

And that gives the solution F(x)=Ae^x+Bxe^x

[unreal stump]

Yee

Now we want to recover c_n from this

[iron marsh]

In this particular problem c_n=1 for all n

[unreal stump]

No

You find coefficient of x^n/n! in F(x)

I guess that will come out to Bn+A?

[iron marsh]

Hmmm, trying to figure out how we come to that conclusion

[unreal stump]

Well just expand e^x and xe^x

[unreal stump]

Because that was our assumption

[unreal stump]

.

Coefficient of x^n/n! Term will be c_n

[iron marsh]

$xe^x=\sum_{n=0}^\infty \frac{x^{n+1}}{n!}$.

[vital dew]

dackid

[unreal stump]

Well coefficient x^n/n! term will be n.(multiply and divide by n+1 and adjust the thing)

[iron marsh]

does it necessarily matter that we lose the n=0 term when we do that?

[unreal stump]

Well n=0

So you can include that as well

[iron marsh]

oh duh

Okay that makes sense now. I learned quite an array of new things today. Thank you very much Drak. You have been most helpful

[unreal stump]

You are welcome

Well this was the question that got me into math

[iron marsh]

Which one? I asked a million :p

[unreal stump]

How do we know things like this will give us all the solutions to the linear recurrence

[iron marsh]

I'm glad I'm not the only one. I'm not particularly the biggest fan of the guess and test method. It works, but it's not all that satisfying when it comes to derivation.

[unreal stump]

I should learn complex analysis and finish generatinfunctionology

That's a good book if you are interested in generating functions

[iron marsh]

Wait, that's an actual book? I thought you just made up a word

[unreal stump]

https://www2.math.upenn.edu/~wilf/gfology2.pdf

[iron marsh]

I remember trying to learn generating functions 3 years back or so and I was way in over my head. Now that I have a good understanding of it, I'll definitely try to learn more about it.

[unreal stump]

I think like linear independence is the big thing behind why generating functions work

So you can have any linearly independent functions/formal polynomials in which you can encode your series

[plain spindle]

You will have to use DeMorgan's

(xy)' = x' + y'

[cyan plover]

Thank you

It's okay though

I've solved it now

[plain spindle]

okay cool

[iron sorrel]

anyone know how i can do e

[coral parcel]

That's somewhat creative task. You'll need to get yourself an intuitive understanding of how T works, then get that understanding into words.

[iron sorrel]

wdym

[coral parcel]

Do you know the word "conjecture"?

[iron sorrel]

no

[coral parcel]

It would be useful to lead with that when you ask for help.
"Conjecture" basically means a claim that you guess is probably true, but haven't found a solid proof for yet.

[iron sorrel]

is this similar?

[coral parcel]

Not quite -- there you're told outright what to prove.

Here the task is "use your imagination and understanding to guess at some nice way to describe which numbers are related to 0 (or 1, or 2) by T. Then write down your guess. And then prove that your guess was right".

[iron sorrel]

related

as in like how

[coral parcel]

There's not a single Right solution to that -- I can imagine at least two different perfectly nice statements that you could end up guessing and proving, and there might be ones I cannot immediately think of.

[iron sorrel]

wdym how related as in how

like 3|(m-n)

so

3|2

3|1

and 3|0

[coral parcel]

Neither of 3|2 nor 3|1 are true, though.

[iron sorrel]

so i have to make it related

is what i meant

[coral parcel]

Oooh right, I see. Yes, it's related in that sense.

[iron sorrel]

so

would 3k work

3|3(k)

3|3(2) = 6= 3*2

3|3(1) = 3= 3*1

3|3(0) = 0= 3*0

would that not work

[coral parcel]

But that doesn't seem to be immediately related to the definition of T.

What are your answers to parts (b), (c), (d)?

They will be a good place to start when you're looking for a nice way to describe the numbers in each set.

[iron sorrel]

3,6,9,-3,-6 for b

[coral parcel]

"3k" in itself won't work -- that's not even a whole sentence. But it could work to make your conjecture be the sentence

The numbers that are related by T to 0 are exactly the numbers that can be written as 3k for some k.

[iron sorrel]

i dont understand

what does it mean when its asking that

[coral parcel]

That's what I believed I had explained here.

[ebon berry]

?

what does this symbol mean

it it saying f of g?

whts tht circle called bc i never saw it

[worthy pivot]

composition of functions

[ebon berry]

tysm

[worn cipher]

How did adding these two terms result in the k+1 exponent being lost for one of the 2's?

[coral parcel]

It didn't. It's just a+a = 2·a where a happens to be 2^{k+1}.

[worn cipher]

Oh wait that makes sense lol, I wasn't seeing it like that for some reason

Thanks

[molten dirge]

I'm having a brain fart proving this with induction. The hint suggests finding a function f with f(n)>0 s.t. LHS<=2-f(n), but the obvious choice of f(n)=1/(n+1)^2 doesn't work.

[iron sorrel]

i dont get what that means

how can 0 1 or 2 be realted to t

like what does that mean

[ivory badge]

When is m T 1?

[iron sorrel]

so when is mt0

mt1

mt2

?

[iron sorrel]

is that what it means

[ivory badge]

Well I’m asking this as a leading question, and it should be capital T

Looking into what m satisfy m T 1, and what n satisfy n T 2

That’s what troposphere is trying to suggest

I think

[iron sorrel]

@coral parcel

u still here lol?

[coral parcel]

Yes, but I'm sort of stuck on coming up with a different way to explain it.

(Which is a bit ironic, given that the problem is a "come up with a different way to describe such-and-such" exercise).

[unreal stump]

I don't think you can do this with induction

[coral parcel]

The hint would be good if the denominators were 2^n rather than n^2. Perhaps it's a typo?

[unreal stump]

Well this is still bounded above by 2

[coral parcel]

True.

Perhaps something like $$\frac{1}{n^2} \le \int_{n-1}^n \frac{1}{x^2} dx$$ and so we could use the integral all the way to +infinity as f?

[vital dew]

Troposphere

[unreal stump]

Ok ig this may be what the hint wanted you to do in a sense,but here's how I would approach it:.

Define $v_2(n) := 2^k$ where $2^k \leq n < 2^{k+1}$
Now consider the sum
$\sum_{i=1}^{n} \frac{1}{v_2(i)^2}$

[vital dew]

DraK

[unreal stump]

Now you can say this is strictly greater than the sum we have, since i >= v_2(i) for all i

If you write down the terms of this sum it should be clear it decomposes to something of the form
$1+\frac{2}{2^2} +\frac{4}{4^2} + \frac{8}{8^2}... + \frac{n-v_2(n)+1} {v_2(n)^2}$

[vital dew]

DraK

[unreal stump]

Because there are 2 numbers with v_2(n)=2 , 4 numbers with v_2(n)=4 and so on

This is bounded above by 2

[unreal stump]

*greater than or equal to

[iron sorrel]

would u know how to help me lol

[molten dirge]

Interesting. But I feel like there should be an easier solution, the bar is set pretty low for all the other exercises. Thanks anyway

[regal gate]

this one is a fun problem. Induction does work, however, there's a problem: the right hand side is not dependent on n. So you might try to prove a sharper inequality

[molten dirge]

Unless I'm missing something, that's the whole point of the hint.

[regal gate]

ah ye didnt read the hint lol

mmh I dont think I can give further hints

without giving the entire solution I mean

but like, its not surprising

||1+1/2^2+...+1/n^2<2-1/n|| there you go if you cant figure it out

[weary tiger]

Hello, Idk if this is correct channel for this topic, but I have a doubt about graphs:
Isn't the chromatic number just the number of connected components of the complementary graph?
I mean the standard way of attributing colors: If u is connected to v they must have different colors.
What I was thinking is something in the lines of: Imagine you have the complete graph of n vertices. You need n colors because every edge is connected to every other. Now imagine you start taking of edges one by one. The first edge uv you take you can give the same color to u and v and now you only need n-1 colors. If you take another vw now, v and w can have the same colors, etc.

That would also explain intuitivelly why planar graphs are 4-colorable. In fact it would explain why any graph that doesn't contain K5 as a sub-graph need at most 4 colors

[haughty garden]

You’re on the right track. It turns out that the chromatic number of a graph is the minimum number of cocliques (minimum number of cliques in the complementary graph) / independent sets needed to cover all of the vertices in the graph

[weary tiger]

I see the problem, in my example u and w would still be connected so they couldn't have the same color untill uw is removed as well

Also makes sense with the complexity, because finding connected components is linear and finding clicks is way harder

I knew something was off because I knew coloring graphs is harder than finding connected components

[weary tiger]

Do you know a counter-example to the other proposition (any graph that doesn't contain K5 as a sub-graph need at most 4 colors) or is it correct

[haughty garden]

I believe this is still an open conjecture

See Hadwiger’s conjecture or Hajo’s conjecture

Hadwiger’s conjecture asserts that any graph with no K_t minor is (t - 1)-colorable; in particular, your case is specifically t = 5

Hajo’s conjecture looks at the same idea but with subdivisions instead of minors

Oh wait no it was proven to be true for t = 5

Since it’s equivalent to the four colour theorem

On the other hand, the generalised version of using subdivisions remains open

[weary tiger]

Do you recomment a wiki to find more about this topic? Is nLab or wikipedia a good (updated) source for this?

[haughty garden]

Feel free to peruse the Wikipedia page on Hadwiger’s conjecture. It’s a fascinating conjecture that generalises the four colour theorem: https://en.m.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)

I think they briefly discuss Hajos’ conjecture too

[mighty hawk]

Hello guys is this right and if not please explain how we figure it out

[iron sorrel]

can sm1 help me hejre
i dont get how to solve this
i have to say if this is reflexive
symmetry
or transitive
and i dont get how i do that

[rose steeple]

can you be more specific? what exactly dont you get about how to check those conditions?

[lusty panther]

Ok so I have part A and B figured out but how would I go about finding for part C?

I'm thinking a distribution table with X being either 0-5 and then a formula like P(X=K) where k is the number right?

[royal holly]

could sm1 explain d

[rose steeple]

specifically what about d is it that you need explained?

[rose steeple]

sure you could do that

[iron sorrel]

would this be a way to verify?

[rose steeple]

this implicitly assumes that 128 is congruent 2 mod 7 and likewise for 61 and 5 so no

the point of that problem is to actually show that 128 is congruent 2 and 61 is congruent 5, both mod 7

you can use a similar approach, though applied to each one

[hexed shore]

Someone has an idea where I fucked up?😂

[iron sorrel]

oh so it wants to know if 128 equal to 2mod7?

and 61=5mod7?

[weary tiger]

Can anyone here help with Network flow in graphs? I have a few assignment questions I need solved

[rose steeple]

yes. it wants you to show the congruences

[iron sorrel]

but my teacher did it the way i did

nvm

[gray sun]

When comparing sets. Is (a,c) the same as (c,a)?

Given two sets:
Set A
Set B
Is (A x B) = (B x A)

[ivory badge]

I wouldn't say they're equal

but clearly you should have a bijective function that sends (a, b) to (b, a) right?

You can't just rearrange ordered pairs as you so choose though

[gray sun]

Ok so set order doesn’t matter, but Cartesian products order matters

?

[ivory badge]

{a, b} = {b, a}

(a, b) does not equal (b, a)

[gray sun]

Those are sets

Ah ok

Thank you

[ivory badge]

ordered pairs are ordered

and similarly for more product terms

[iron sorrel]

could sm1 help me with this

[rose steeple]

also it would help if you mention what you already tried @iron sorrel

[ebon berry]

excuse me but what does this sign mean? I never seen it before

i only seen a proper set and subset symbol and none of them look like tht

ig it means superset

[stray reef]

yes it means superset

it's just subset turned the other way

[lofty patrol]

Hi! I'm wondering why A wouldn't be correct? Is there some property of bipartite graphs relating to edges/vertices that I can apply (I know bipartite graphs have no odd cycles, are 2-colorable, and has two subgraphs I think)

[agile magnet]

Why did you think it was incorrect

Let's start there

[lofty patrol]

Oh I thought I was correct, but it's actually incorrect

A*

[sacred fern]

Hello, I have a question about this problem here. For now we can ignore $5 bills and just focus on the other 3 denominations

For some reason I am getting fractional numbers

For the dollar coin I have the generating function 1/(1-x) same for $1 bill and for $2 bill I have 1/(1-x^2)

The 100th coefficient of the product should give me the result

But I keep getting fractions

Maybe I am doing the step after partial fraction decomposition wrong?

I get the following decomposition

[sacred fern]

<@&286206848099549185>

[weary tiger]

Yes?

@sacred fern

[sacred fern]

This

[weary tiger]

oh ok

For the first one, you can use 20 $5 to make $100

100 $1 to make 100$

[vital dew]

Control

[weary tiger]

Ayo?

[sacred fern]

The question asks for a generating function and doing $5 looks like a pain so I just noped

[weary tiger]

It's not hard tbh

[sacred fern]

Yeah I realized but the partial fraction I keep getting is really wonky

[weary tiger]

Oooh ok

[sacred fern]

Yeah I attached a picture of what I’ve already done

[weary tiger]

ok

First of All, That's Correct.

Very Correct

wait

[sacred fern]

I feel like I messed up with the Taylor series for 1/(1-x)^n for n = 2 and 3

[weary tiger]

No you didn't

[sacred fern]

Then why are there fractions 😞

[weary tiger]

Ik That's why it's so hard

Lots of Ppl get Confused with that

I am going to come back to you later.

i gtg

[unreal stump]

Expansion of 1/(1-x)^3 is wrong

[sacred fern]

I’m missing a 6 in the numerator?

[unreal stump]

Power of x should be n-2

And the constant should become 1/4 not 1

So it becomes
$\frac{1}{2} \sum_{n=2}^{\infty} {n \choose 2} x^{n-2}$

[vital dew]

DraK

[jagged hearth]

I wanna find amount of integer solutions to an equation $x_1 + x_2 + x_3 = 578$ by taking generating functions. One restriction is $x_1 \geq -7$, so I make a variable change to $y_1 = x_1 + 7$

[vital dew]

sam

[jagged hearth]

But not sure how to proceed to find generating function of y_1

y_1 would just be generating function of positive integers

so x_1 is just 1/(1-x)-7?

but doesnt seem right

1/(1-x) - 7/(1-x) might make more sense

idk

nvm

got it

[spiral aspen]

can someone tell me if my argumentation is right?
Lets prove by contradiction. Say T and D(s) is empty, then there doesnt exist any edge e in D(s) that is in T.
Lets pick the first vertex closest to s (so 1 edge difference) with the smallest weight and call it (s, v0). Clearly this is an element of D(s). Assume it is NOT an element of T, then there exists another edge in T (s, v1). But if thats the case we know (s, v1) > (s, v0) so the minimum spanning tree would just select (s, v0) instead as the edge, thus contradiction.

[autumn wyvern]

Rule:

A full m-ary tree with i internal vertices has n = mi+1 vertices, and l = (m-1)i+1 leaves.
Thus, when m is known and the tree is full, we can compute all four of the values e, i, n, and l, given any one of them.  
^ (e)dges, (i)nternal vertices, (n)odes, (l)eaves 

Why was n = mi+1 used instead of l = (m-1)i+1 ?

I have this:

(3-1)*(100+1) = 2*101 = 202

[stray reef]

i is the number of internal nodes.

you confused the number of internal nodes (i) with the total number of nodes (n), and also inserted a pair of parentheses that wasn't there.

and also you got an answer that should scream nonsensical to you.

how could a tree with only 100 nodes in all have TWO HUNDRED leaves?

[zealous elbow]

how do you generate a subgroup?

[stray reef]

#groups-rings-fields ?

[zealous elbow]

oh its in my discrete maths paper lol

think i got it just after i typed that anyway

[stray reef]

@autumn wyvern do you understand what i said up there?

[autumn wyvern]

oh, just saw this now

[autumn wyvern]

not immediately, but let me read it again

ah!

you confused the number of internal nodes (i) with the total number of nodes (n), and also inserted a pair of parentheses that wasn't there.

this clears things up

ty

[autumn wyvern]

and regarding the parens, I think you mean the order of precedence dictates that the mulitplication precedes the addition.

therefore, the extra parens I inserted is actually incorrect

[vernal oak]

does anybody know why there is a m+1

[stray reef]

that is in fact exactly my point. maybe i should have said "didn't belong" instead of "weren't there".

[autumn wyvern]

ok, ty

[river garden]

Can I construct a Turing machine using 1 tape to accept the language 0^p | p is prime?

[stray reef]

pretty sure that would constitute some kind of halting problem violation, but im not sure how or what

[river garden]

Ok

[haughty garden]

Multi tape Turing Machines have the same accepting power as a single tape Turing Machine, so you can construct a multi tape Turing Machine to accept the language and then use the canonical conversion to a single tape Turing Machine

[spiral aspen]

true right?

if not true then we would have two spanning trees where there exists at least one edge in say T1 greater than T2. In that case we could just add the edge of T2 instead and remove that greater edge in T1

right?

[agile magnet]

How do you know adding the edge from T2 maintains the fact that T1 is a tree?

[hard pivot]

Hello, I have a hard time learning simplifying recurrence. What are your best learning materials for this topic?

[analog tinsel]

by 0^p you mean words like :
00
000
00000
0000000
...
right ?
Because I am not completely sure but my first intuition would be to construct a TM that counts the length of the word and then computes a prime test on that.
I am quite confident this should be possible. But maybe I am missunderstanding or missing something

[river garden]

Yes 0^p mean 00000...0 p times

[river garden]

Yeah saw that yesterday I had a solution using 2 tape and I can convert that into single tape.

[haughty garden]

whoops I didn't mean to send a super reaction

[crystal bone]

Looking at Push Down Automata

I struggle understanding why the first and second one is non deterministic

[magic knoll]

is there a way to write mu(x,y) explicitly?

[unreal stump]

Well from the way they defined it, you can conclude \mu(x,x)=1 and \mu(x,x+1)=-1 for all x

As well as \mu(x,x+k)=0 for all k>1

You can't say anything for inputs of the form (x,y) where x>y from this definition

Well ig you don't really need to care about those

[magic knoll]

alright thanks

[weary tiger]

Explain the first bullet point of the proof please

!volunteers

[lofty cloud]

Helpers are just people volunteering their time to help you. Be polite.

[hexed shore]

How do I transform a generating function to a sum? Such as :

$x^4 \frac{(1 - x^4)^2}{(1 - x)^3}$

[vital dew]

MLR

[hexed shore]

What I know :

$x^4 \sum_{k \ge 0 }^{2} {2\choose k} (-x)^k \sum_{k \ge 0 }^{2} {2\choose k} (x)^k \sum_{n \ge 0}^{\infty} (n + 1) x^n$

[vital dew]

MLR

[hexed shore]

But then, I dont think we can multiply finite sum and infinite sum

[agile magnet]

Yes

There are trivial decidable algorithms to check if an integer is prime

[muted palm]

Let $G=(V,E)$ be a complete weighted graph with vertices V = ${v_1, ..., v_n}$ each representing a point in $\mathbb{R}^2$. Let the weight $w_{i,j}$ of edge $e_{i,j}$ be given by the euclidean distance between $v_i, v_j$.

Suppose $T_1$ is a minimum spanning tree of G. We choose a vertex $v_k$ and construct a minimum spanning tree $T_2$ for the graph $(V\backslash{v_k}, E\backslash{(v_1, v_2) | v_1, v_2 \ne v_k})$. Show that $T_1 \le T_2 + \min_{j \ne k}{w_{k,j}}$

[vital dew]

IV

[muted palm]

basically you remove a vertex from an existing MST and make a new MST but then connect the removed vertex to it

am i stupid or is this just "we created a spanning tree of G so it's at least as long as the MST"

ok it's just that

[green iron]

I have a generic question what are some applications in discrete math? I’m a computer science major and I’m currently taking it. The concept is quite hard for me to process. So I wonder do I have to be really good at this to be able to work with computer?

[green iron]

@ivory cliff but I can’t see how first order logic application other than translating a sentence into something sentence of symbol that’s shorter than the original sentence

[stiff shell]

Generally, there will be a lot of things you encounter in your degree that you won't use depending on what field you go into. But these things might still be useful to know. Discrete math is one of the pieces of math apart from calculus that I think pops up to at least some extent in most fields of CS.

The first things you learn is proof writing and logic, the direct proofs might not immediately be useful in most jobs but for later courses to follow along it is very necessary that you can follow proofs.

You might also encounter some algebra/number theory, which is very useful in cryptography. RSA is a direct application of abstract algebra (which is generally a course in its own but added to our universities DM course for CS)

Then there is also counting, which is used to analyze the complexity of algorithms or the security of passwords.

Probability, Apart from risk assessment probability and statistics are also essential in data science as well as machine learning

Graph theory, graphs are used to model connections between places, this is useful in path-finding algorithms but is also used to model complex networks. A lot of research in my math department is done on how connected graphs are, what happens if you remove certain connections, this can be used in anything from friend networks in social media to studying how information spreads through a system.

Again, how many you'll use any of these highly depends on what you find interesting, but a CS program is designed to prepare you for any direction you want to go into, a master's degree / job will tailer more to your personal preference. But generally I'd say discrete math is one of the more essential pieces of math you will encounter as a computer scientist

[leaden jay]

I need help with this:

[dense comet]

prepositional logic, Idk if this applies to this channel but I am lost on how we can get in a position to apply material equiv.

[dawn fulcrum]

Guys can someone help me in finding time complexity of shell sort algorithm

The 4th image is the program I'm going off of

The 1st image is the series I formed for worst case shell sort on an array of length 2^x

And the 3rd image is the summation form of the 1st image

2nd image is the answer by Wolfram mathematica

And I'm starting to think my analysis and my final answer is wrong

It might be correct in Big-O notation, but it's wrong if I'm talking exact

Pls ping me when you answer

[dawn fulcrum]

Yep my answer is wrong

I made the mistake of assuming that the innermost loop will run always

but in the sum

lets say 1 + 2 + 3 + .... + 7

it will run once for odd positions and not run for even positions

so it will actually be 1 + 0 + 1 + 0 + 1 + 0 + 1

[dawn fulcrum]

(Turns out I am approaching the problem in a very wrong way)

(and I understand now why it is n^2 worst case for shell sort)

[fast forge]

Hi! What's the easiest way to see that this graph is not vertex transitive?

Can I simply say that 1 cannot be sent to 5 since 1 is a part of a 3-cycle but 5 is not in any 3-cycle, but graph automorphisms preserve cycles?

[obtuse lance]

yup

[regal gate]

finite sums are infinite sums too.

ie polynomials are power series too

and you know how to multiply power series

another way, is say you have a polynomial $P(x)=a_0+a_1x+\cdots+a_mx^m$ and a power series $F(x)=\sum_{n\geq 1} c_n x^n$. Then
[
P(x)F(x)=a_0F(x)+\cdots+a_mx^mF(x)=
]
[
=\left(\sum_{n\geq 1} a_0c_n x^n\right)+\cdots+\left(\sum_{n\geq 1} a_mc_n x^{n+m}\right)
]

[vital dew]

Croqueta

[regal gate]

and like collect things

[inner marsh]

Is this a union of A0, A1, A2, A3 etc'?

[little prism]

yes

[safe carbon]

can anyone help me with this question: In order to gain access to a private web site, each person must have his or her own 6-digit password, where some digit is used 3 times and the remaining 3 digits are distinct. How many such passwords are there?

[coral parcel]

Stop doing math and fire the security person who made up those password rules.

[lament parrot]

is a formula clean when two different quantifiers bind the same variable in different scopes? and not clean when 2 different quantifiers bind the same variable and one is inside the scope of the other? my definition only says a formula is clean when no variable occurs both free and bound and the occurrence of two or more of the same quantifiers must bind different variables

but looking at questions it seems my second sentence is also part of the definition

[coral parcel]

"Clean" is usually not a technical term.

Your definition sounds like it is allowed to bind a variable twice if only it's by different quantifiers -- which doesn't make a lot of intuitive sense.

[lament parrot]

in the context of first order logic, when deciding if you should rename a variable, by first inspecting if it is "clean", for example in this formula says it is not clean and the y should be renamed...

[lament parrot]

yes that is the definition i have which is confusing me, I should recheck the definition maybe

[coral parcel]

Can you show the exact definition as a photo/screenshot?

[lament parrot]

this seems incomplete

[coral parcel]

Note that it says "every two occurrences of quantifiers", not "every two occurrences of the same quantifier".

So your formula is unclean simply because it contains a quantifier that binds y in two different places, no matter which quantiifiers and no matter what their relation to each other.

[lament parrot]

OH i get it now, just that you can't have a variable bound twice

thank you

[light egret]

hi, to check if my directed graph is strongly connected. Do I have to check whether we can visit every vertex from every node? And if 1 node is unable to visit all, means it is not strongly connected even if the other nodes successfully visited all vertex?

[agile magnet]

Yup

Strongly connected is an all or nothing thing

@light egret

[light egret]

thanks

[indigo rapids]

how would i go about doing this proof?

<@&286206848099549185>

[lofty cloud]

Please only use the <@&286206848099549185> ping once if your question has not been answered for 15 minutes. Please do not ping or DM individual users about your question.

[worthy pivot]

try to argue with the parity of the permutation

[indigo rapids]

i got it thanks though!

🙂

: )

[primal turret]

someone know what s.t. mean in the definite of a group?
this is from model of computation course , but for some reason the conventions of the symbols are different from other math course in my department

[worthy pivot]

such that?

[primal turret]

ok, we usually do " : " in my CS department

[worthy pivot]

yeah, same thing

[primal turret]

more confusion they also do '-' instead of '\'

[indigo pebble]

hey guys, ive been thinking about why we need the concept of compact sets/intervals. Compact means it is closed and bounded, but if a set is closed, lets say, [2,9] then it is also bounded

[worthy pivot]

Compactness is only equivalent to closedness and boundedness in certain spaces. In general, they're different concepts.

[vital dew]

eigenzan

[ivory badge]

There should also be some closed but not bounded sets which aren’t all of R, like [0, 1] u [2, 3] u .... u [2n, 2n+1] u ....

[safe carbon]

hey everyone! I ask this yesterday but didn't receive a response. can anyone explain this to me?

This is the question: In order to gain access to a private web site, each person must have his or her own 6-digit password, where some digit is used 3 times and the remaining 3 digits are distinct. How many such passwords are there?

[rigid oriole]

[1, infty) will do

[vale cairn]

or N

[agile magnet]

think about what choices have to be made

For example, what if you choose the digit used three times, now what is left to figure out?

[nocturne peak]

any of you guys good with baysian networks?

[broken sonnet]

Could some one provide some tips or guidance for this problem? I have a feeling that this can be solved using induction, but I am not sure what the predicate would be. Right now I am trying to solve this using contradiction

[coral parcel]

Um, there's a solution right in your screenshot. What is your question then?

[agile magnet]

just ask your question

and if someone can help, they will

[small plume]

can someone help me with these two on whether they're t rue or false

pretty sure e is true but I don't understand how d is any different than d

[unreal stump]

(d) is correct

(e) is wrong

[small plume]

oh

can you explain

[unreal stump]

A partition is a set of sets

Like a set whose elements are subsets of S

[small plume]

so separating the elements in S into subsets basically ?

[unreal stump]

Yes

[small plume]

but isn't S a subset of itself

or does that not satisfy the definition of a partition

[unreal stump]

S is a set of elements

[small plume]

say S is a set of elements with {1, 2, 3, 4}

is S not a subset of itself ?

[unreal stump]

{1,2,3,4} is not a partition of {1,2,3,4}

{ {1,2,3,4} } is

[small plume]

I don't understand why {1, 2, 3, 4} isn't a partition of {1, 2, 3, 4} though

because it's not a collection of subsets ?

[unreal stump]

Yes

[small plume]

but $$ S \subseteq S $$

[vital dew]

Pingu

[small plume]

or is this not true

and I'm tripping

[agile magnet]

it is true

however

lets take a step back

write out the definition of a partition of a set S for me

[small plume]

collection of nonempty subsets of S and contains every element of S in one element of the partition ?

[agile magnet]

yea

the key point is this

collection of nonempty subsets of S

if P is our partition, then every element of P has to be a subset of S

right?

[small plume]

yes

[agile magnet]

so if you claim that S is a partition of S

the every element of S has to be a subset of S

is this necessarily true?

[small plume]

ah

I see

[agile magnet]

however clearly {S} is a partition of S

see the difference?

[small plume]

yup

thanks

[small plume]

it's true if the set is finite, right ?

[agile magnet]

no

[vital dew]

Spamakin🎷

[small plume]

wym by every element isn't the only element of {1} just 1 which is subset of {1} ?

oh wait

[red relic]

whats the best way to figure out how many disconnected graphs i have from an edge list

[unreal stump]

Perform a DFS

[red relic]

ye that came to mind first but i feel like that's slow

actually wait let me think about it 😔

i think i figured it out, i got tripped up because it asked for O(E) and DFS is O(V+E) but in my case the given information is just comprised of edges and E-1 = V so it's technically O(2E) + O(E)? i hope im not misunderstanding

[unreal stump]

You probably need to use like the disjoint set union data structure

[broken sonnet]

My question was if it suppose to be solved using induction. The solution was something I came up with but I am not sure if it is correct.

Can someone give some tips on this? For some reason I think my approach is not correct.

[coral parcel]

You can't really "assume wlog that k=2" -- it's not clear how to reduce instances with a different k to that case.
Do you have the handshake lemma (aka "degree sum formula" available)?

[broken sonnet]

Yeah we do have the definition of the Handshaking Lemma

I suppose we can say for all in v in V, the deg(v) = 1, since we are given that |E| = k / 2. This would give us the total sum of degrees for all v in V, deg(v) = k

And so by that fact alone, each team can only have 1 match with another team

@coral parcel Thank you for pointing that out, I appreciate it

[latent cloud]

So I asked ChatGPT this question. Determine whether each of these conditional statements is true or false. a) If 1 + 1 = 3, then unicorns exist. b) If 1 + 1 = 3, then dogs can fly. c) If 1 + 1 = 2, then dogs can fly. d) If 2 + 2 = 4, then 1 + 2 = 3. It answered with a) False b) False c) False d) True But that is incorrect as it should be ```
a) true
b) true
c) False
d) True

It seems to forget that an implication conditional statement with a false hypothesis is always true.

[tight hound]

It gave you that answer because it is a language model. It is not meant to give technically correct answers, and I don't think the people associated with it claim that it does.

[dawn sleet]

I've found that it does a very good job at discussing technical subjects like math/logic in great detail, having clarifying conversations that would annoy a real person to death.

That said, you have to practice good information literacy and 'check its work' every time. Prompting it to check its own work can help, but ultimately you cannot 'trust' its output to be accurate.

But even probably mostly accurate can be super helpful as long as you are equipped to verify its statements.

o wait this is a math board. yeah no dont ask it math problems lmao

[latent cloud]

yes ofcourse. I was just curious if anyone knows why it gave that result. Any wording etc, or just something with how it got the data from the database etc.

It might have thought i was asking some question for some other kind of math aswell, which is why it didnt use implication correctly.

[dawn sleet]

It doesn't 'think' anything. It's basically a very robust version of just hitting autocomplete on your phone. It will be randomly wrong at any time because it's just choosing what words to say next based on what came before.

[acoustic crag]

Can anyone help me with this

[latent cloud]

it uses ai to gather data depending on keywords no?

[dawn sleet]

the 'data' in question being any and all text in its training data

describing chatbots as 'intelligence' is dubious marketing

[latent cloud]

yeah. so that means the data it has access to isnt enough to gather the conclusion of how to use implication (or that it should be used in that scenario).

so it "thinks" by gathering data and then using some kind of algorithm to draw a conclusion

[dawn sleet]

the 'conclusion' in question being its best guess at what words a person would use contextually in that conversation

it doesnt solve problems. it simulates communication.

[obtuse lance]

have you heard of the extended euclidean algorithm? If so, then try to see why 7x+9y=1 would be what you want to look at

[acoustic crag]

No I didn’t

[obtuse lance]

have you seen equations of the form 7x+9y=1 before

[acoustic crag]

Ye

[obtuse lance]

with integer solutions? and do you have a method to solve them?

[acoustic crag]

Not quite sure

[obtuse lance]

maybe check your notes to see if you ever solved something like ax+by=1 or ax+by=g where g is the gcd of a and b

[acoustic crag]

I know that this has only one solution, since the gcd is 1 of all 7 and 9

[acoustic crag]

I’ll see

[slender root]

is this the correct channel for lambda calculus

[weary dune]

Is anyone here interested in tutoring, I need help catching up in a course and would be willing to pay for help. Dm me if interested and competent.

[chilly hemlock]

@acoustic crag
You should learn Euclides Algorithm for this type of problems

[slender root]

@weary dune also check out #math in libera chat for help

[chilly hemlock]

But if you want the solutions then
9 = 7 * 1 + 2
7 = 2 * 3 + 1

1 = 7 - 2 * 3
1 = 7 - (9 - 7) * 3
1 = 7 * 4 - 3 * 9

thus we get that x = 4 is the answer, or general solution:
x = 4 + 9*k, where k is a element of the integers

[acoustic crag]

Still don’t get it
What about the mod

[chilly hemlock]

What happens if you add 9 to any number in mod 9?

Same thing with multiplicities of 9^

Look at the algorithm again

[vital locust]

not sure where to start

i was thinking of assuming G was a tree and trying to show it by contradiction

but i'm not sure i'm allowed to do that since the questions doesnt mention anything abt G being connected

[vital locust]

forest*

[unreal stump]

So let's say G is a connected graph with n vertices

If G is a tree(no cycles), there are n-1 edges

If all the individual components are trees (that is there are no cycles anywhere) you will have n-k edges. But well we don't have that

[vital locust]

oh so we are allowed to say G is connected?

[unreal stump]

Well G is a collection of trees

Each individual component is a tree by assumption

[vital locust]

I was wondering if we could use this result

If G is a forest with k trees then |V| = |E| + k

so in this case n = (n-k+1) + k

oh wait then that shows that G is not a forest

nvm nvm

[unreal stump]

This is the main thing you need

[unreal stump]

That's what you want

[vital locust]

oh so that extra edge is the one that creates a cycle in G?

[unreal stump]

Yea

[vital locust]

should i also include that there is a path in G we combine with that extra edge to create a cycle

or is that not necessary

[unreal stump]

Maybe

It's not strictly necessary

[vital locust]

okay thanks for all the help

appreciate it

[dusty trellis]

does anyone know how to do this?

[ivory badge]

!help

[lofty cloud]

Please read #❓how-to-get-help

[ionic tulip]

Anyone know good resources for counting and combinatorial proofs?

[bright knot]

Lol what is going on today?

@everyone

[floral forge]

hey does anyone have tips for discrete math? I studied all week n got 55 on my midterm, i really need to do better

[barren bear]

I know this is a bit late, but I just got here since I'm about to start studying as well. Are there any particular concepts you're struggling with?
I'm currently in a Discrete Math 2 class and struggling a little bit (), but I've spent a lot of time looking around to better my understanding.

Soooo... I might know of a good video on the topic if its something specific. If you're not sure, or you feel like it's most of the material that doesn't really make complete sense to you, I would recommend Kimberly Brehm's Discrete 1 & 2 playlists on YouTube, depending on what topics you're being tested on. Her videos have helped me the most, so far, because she explains things in ways that are just easier for me to understand.

[weary tiger]

hi, having trouble with an induction problem. so i can see this statement is clearly false but im not exactly sure how there proof still looks like it works

this is what i have written down so far but i dont really know if its the right thing

[unreal stump]

How are you starting with 2^{k+1} <= (k+1)+1?

Your thing is true iff 2^k <= k/2 +1

Which can be shown to br clearly false

[coral parcel]

The purported "induction step" assumes p(k+1) and derives p(k), which is the wrong way around.

[weary tiger]

ohh

[floral moss]

please

[silver mason]

is there someone who has a good discrete math course?

[noble lake]

this is the math textbook we use at carnegie mellon: https://infinitedescent.xyz/

(also speaking of, we're having a mascot contest and theo is the discrete math mascot if you want to vote for them 🦔 https://www.instagram.com/scsatcmu/)

[chilly hemlock]

Discrete Math by Biggs is the book my university uses

It is a good book

Easy to understand

[indigo rapids]

How many non-negative integer solutions are there to the following inequality? : $$x_1+x_2+⋯+x_{10}<7$$

[vital dew]

MildCurry

[indigo rapids]

could someone help me figure out how to do this?

i have it solved to =7and that gives 11440

but idk how to go about doing it with <7

[floral forge]

its nothing specific honestly i just thought i was fine w the material n then got a 55 so im kinda like 🧍🏽‍♀️

like i know some pp’ read the textbook

i do like that professor’s videos! ill def watch the series but other than that wld u guys suggest studying the textbook? doing probleme? Ljke idek how to study this but my last method was looking at the lecture slides, videos, and mcq questions online since our exam was supposrd to be mcq

[noble lake]

hint 1: ||stars and bars||
hint 2: ||is there somewhere you could put the “extra” stars so that <7 of them remain in x1,…,x10?||

[queen flax]

ayooo

Could anyone help point me in the right direction here for an inductive proof practice question im doing? It's our first one looking at equality of summations and im a bit stuck.

[ivory badge]

Do what it says in the text to the side of the box

[queen flax]

I'm not sure what that is telling me to do. Idk if i've been doing these questions for too long but it isnt making sense to me

what would the last two terms be in terms of n?

[ivory badge]

It says take the last two terms out

What are the last two terms of the summation

[queen flax]

2n+1 and 2n+2?

no thats not right

[ivory badge]

Look at the sum

And find what the terms are for the last two values of i

[queen flax]

ohhh i see

frick

[ivory badge]

[indigo rapids]

i dont get you?

i know the stars and bars

but idk what you mean by the second part?

[weary tiger]

bro channel name

[coral parcel]

Looking for the good stuff? I can set you up with some really degenerate non-commutative things ... non-associative too, if you have the guts for it.

[viral crown]

that's not enough

i need more

i need it to be the real good stuff

[vapid dune]

the book says the answer is e -> a

my first thought was a <-> e though

wouldn't a <-> e also be valid?

I suppose if the book wanted a bidirectional conditional proposition, it would essentially say "if and only if"

otherwise I should probably assume just a normal implication

it seems the key word is "only"

like in this question:

[true venture]

No one could come up with a better joke for this one?

Or I dibt get it?

[obtuse lance]

lol

could be worse

[coral parcel]

No, because the claim doesn't state that all administrators can edit.

Consider, for example: "You're not allowed to drive a car unless you have a license".
That doesn't say that everybody who has a license can legally drive -- for example, people who have a license and are drunk still cannot.

But it does say that everyone who is allowed to drive has a license.

[little prism]

do you know stars and bars?

[coral parcel]

Suppose we're looking at one of the solutions, say, 5+2+6. We can write this as

(2+1+1+1)+(2)+(2+1+1+1+1)

Another solution is 3+3+7, which can be written as

(2+1)+(2+1)+(2+1+1+1+1+1)

You can make one of these solutions by
a. Start by writing (2.
b. Write +1 seven times and )+(2 two times, in some order
c. End by writing ).

Each way to mix the +1 and )+(2 gives you a different solution, and each solution can be written this this way.

Sounds right.

3-1=7 is a fascinating new kind of arithmetic. Teach me more.

[weary tiger]

why u gae?

[rich wraith]

Don't bully raccoon

[weary tiger]

ahhhhhhhhh

[azure bough]

https://web.math.ucsb.edu/~agboola/teaching/2021/fall/8/liebeck.pdf is what my class uses at the University of Utah

[latent cloud]

If I have this question: Let P(x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school.and this assignment: No student at your school can speak Russian or knows C++ Both these are answer, right?: ∀x¬(P(x) ∨ Q(x)) and ∃x¬(P(x) ∨ Q(x))

Since ¬∃ would mean that there doesnt exist a student at the school since ∃ would mean that there exists minimum one.

and what is the difference between ∃x¬(P(x) ∨ Q(x)) and ¬∃x(P(x) ∨ Q(x))?

[marble bluff]

The difference there exists at least one NOT PxQx or NOT there exists at least one PxQx

Does that make sense? 😄

[analog tinsel]

Just out of honest curiosity since I am not a native speaker. Is it really "discreet math"? I always thought it was "discrete math"

[latent cloud]

not really xd

[azure bough]

I've always seen it as "discrete math". "Discrete Math" is also what Wikipedia uses. "Discreet" wouldn't even really make sense ("discreet" = intentionally unobtrusive.; "discrete" = individually separate and distinct.)

[analog tinsel]

Yeah thats what I thought too

[inner otter]

it was changed for April Fool's Day, as a joke

[analog tinsel]

Lol it was changed now. Well alright problem solved

[analog tinsel]

I had that on my mind

That maybe its some kind of joke I am not getting

But forgot it was the first of april

[obtuse lance]

how I'd think about it is every x_i has to have at least 2 in it, so we might as well remove them, which involves subtracting 6, and having z_i >= 0

z_1 + z_2 + z_3 = 7

Now you can imagine 7 stones with 2 dividers placed among them, and counting the number of ways to do this is 9 choose 2, this is your standard sort of stars and bars argument, good to learn and meditate on that if you're unfamiliar.

the 2+2+2=13 line is not kosher, I would instead write something more like x_i=2+z_i

so like $$x_1+x_2+x_3=13$$ $$z_1+2+z_2+2+z_3+2=13$$ $$z_1 + z_2 + z_3 = 7$$

[vital dew]

Merosity

[obtuse lance]

here maybe it's more clear that I'm literally substituting in x_1 = z_1 + 2, etc...

to go from x_i >=2 to z_i>=0

I think you're thinking the right thought there though but maybe it's not fully clear to you so I'm trying to be a bit more explicit to help

otherwise it looks good

yeah, you could just reuse the same variable names

which is often what I might do too, but I see how the laziness can be confusing

hmm not sure I follow what you mean there

I think you're near understanding though so we should keep pushing at this to clear it up

you're right this doesn't make sense that x_i = x_i +2, cause this is sorta an abuse of notation, these x_i are literally different variables, it's kind of like programming if that helps

that's why I started using z_i to help clarify the difference, or maybe you do understand that, I'm not sure

$$x_i\ge 2$$ you can plug in $x_i=z_i+2$ to that inequality and get $$z_i+2\ge 2$$ and subtract 2 from both sides to get $$z_i \ge 0$$

[vital dew]

Merosity

[obtuse lance]

maybe part of the confusion is - what's the motivation for picking them to be >=0 at all? since I know you're new to stars and bars I can just explain that now since it's pretty straight forward

yeah the z_i

so what's stars and bars? you usually think of like drawing out stars in a row like xxxxx and then putting in divider bars between them like xxx|x|x

the number of stars here is 5 and the number of bars is 2

and you can arrange these in any way you like, how many ways are there to do this?

no no this is just a separate problem

ignore your problem for a bit, we'll connect later to it, this is just explaining stars and bars first

13 isn't related ehre

for instance xxx|x|x is one way to arrange 5 stars and 2 bars, x||xxxx| is also valid, xx|x|x|x, etc

not quite, there are 7 things to choose from

and you're choosing 2 to be the 'bars'

or equivalently you're choosing 5 to be the 'stars'

yeah exactly

now we can think of the stars as like tally marks or stones we're counting up and dividers being the separator between different buckets

so 2 cuts means we have 3 buckets of stones

we can translate these stars and bars pictures into statements about integer partitions with z_i >=0 (a bucket can hold nothing or more)

xxx|x|x would become 3+1+1
x||xxxx becomes 1+0+4
etc

so stars and bars is giving you a way to count all these different ways of shoving numbers into variables

cool

yeah

basically that's just a matter of like, you slice a loaf of bread n times, you'll end up with n+1 pieces

(unless you're slicing your bread like a maniac)

awesome

so yeah, since stars and bars handles the case with z_i>=0 that's why I opted to shift from x_i>=2 to turn it into this form

yeah I guess I'll let you think about it or w/e, let me know if you still have any doubts or questions

cool, glad I could help you're welcome.

[slender root]

I am told this is where to go to discuss lambda calculus

I am studying the easiness of computer languages and I am eternally on the quest for the nextmost easy programming language in the world

I have found the lambda calculus to be among the most easy languages compared to how powerful it is

[unreal stump]

Ok write me an OS in a language that is inspired by lambda calculus

Well what's your question exactly

[slender root]

My thesis has to do with the idea that you can write a formal language for describing formal languages and that making the syntax grammar and semantics of your mathemacal papers unambiguous is much like the process of proofing and that I would argue it may be as important as proofing

So I am interested in systems as semantically syntatically and gramatically expansible as systems with reader macros

and they need to have a strong basis like lambda calculus or category theory

[unreal stump]

#foundations is a better fit for that ig

[young anvil]

what does the line Let ϕ(x)=(a,b)∈Q2 mean?

[stray reef]

they are defining a map from Iso(A) to Q^2 and calling it phi

[unreal stump]

I don't think the map is very well defined

You can find multiple a,b satisfying that

[sage creek]

Usually formal languages have little to do with programming. I think if you want to be able to add functionality to the language this is too difficult to accomplish. There's more potential in focusing on what you want your program to express rather than how you express it. Once you figure out what you want you can invest time into making a graphic user interface to support those features. Code itself is overrated. It's kind of silly that we're still using a serial format. No matter how expressive your language is you'll find that a lot of what you can't seem to express is due to a lack of annotations. Annotations simply don't belong directly in the code either way, that would make it impossible to read.

[fringe siren]

What is the regular expression that this automaton recognizes? is it
(a*b+ U a*(bb)+(aa)+)+?

[latent cloud]

How did they come up with that the middle column is a tautology?

[analog tinsel]

How exactly is your U in this case defined? The syntax I know is slightly different

[fringe siren]

the union of two regular languages

[analog tinsel]

Oh i see

Makes sense

[fringe siren]

(a*b)b(bb)*(aa)* maybe?

i dont know how to handle the b transition from the last state to the start state

[coral parcel]

What exactly does "tatuology" mean for you here?

[analog tinsel]

Im thinking about it give me a second

[fringe siren]

no problem, take your time and thank you for the help 🙂

[fringe siren]

how can we build an automaton that recognizes the intersection of two automata?

[jagged girder]

I began a project like this a while ago, but I was teaching myself the material so I never finished

I wasn't making an actual language per se, but rather I was using meta programming in Julia to parse expressions

[vapid dune]

what I think the answer would be, doesn't seem to be in that list

I thought the answer would be "I exercise and I don't feel tired" i.e. p and (not q)

maybe the answer is D, trying to confuse me with tricky wording

that's the closest to it

[silver mason]

Do you guys know some good resources to learn discrete math?

[outer estuary]

My uni uses Combinatorics - A Guided Tour by David Mazur, but I haven't taken the course yet so I can't really tell you anything about it

[latent cloud]

a tautology is a tautology, no?

[weary tiger]

Something that is always true, no?

[latent cloud]

yup

[coral parcel]

If you just want to see that the formula is always true, a truth table would be the gold standard for a proof.

[vapid dune]

I think this is has to do with "quantified logic"

S being a propositional function

or idk

confused

would the converse be G?

[analog tinsel]

I'm sorry, was about to text you when someone came to visit.

so first thing is, I am having some trouble formulating that regex. Seems quite complicated to me. I might miss something but I used FLACI , idk if you are familiar with that and this also tells me that the corresponding regex is fairly big.
I'll share it after this.

Now regarding your regexes :
(a*b)b(bb)*(aa)* would miss the word b to my understanding since you require at least bb to be present in an accepted word.

(a*b+) U a*(bb)+ (aa)+)+ would miss bbabb for example. Since (a*b+) can only form words that have a's first and then b's
and (a* (bb)+ (aa)+) can only form words that have bbaa in them.
I am not exactly sure how to use the + around the union. Maybe I am doing it wrong.

So what FLACI tells me is
((b|a*b)(a+b)*b(b(a+b)*b)*a((a|ba*b(a+b)*b)(b(a+b)*b)*a)*((a|ba*b(a+b)*b)(b(a+b)*b)*|a|ba*b(a+b)*b)|(b|a*b)(a+b)*b|(b|a*b)(a+b)*b(b(a+b)*b)*|(b|a*b)(a+b)*b(b(a+b)*b)*a((a|ba*b(a+b)*b)(b(a+b)*b)*a)*((a|ba*b(a+b)*b)(b(a+b)*b)*(b|b(a+b)*)|ba*b|ba*b(a+b)*)|(b|a*b)(a+b)*b(b(a+b)*b)*(b|b(a+b)*)|(b|a*b)(a+b)*|b|a*b)
the syntax is a bit different but as you can see its fairly big.
Maybe I can share the dfa with this link , I'm not sure whether you can see the dfa I created https://flaci.com/autoedit

Are you supposed to find the regex for this dfa or were you just curious and thought you should figure it out ? Because if it is an exercise you should be able to do I'd assume there is a simpler solution

[analog tinsel]

So from this definition and from what I remember I'd explain it like this. For each regular language you can construct a (minimal) dfa. Then you combine both dfa's to a new dfa where each state is a pair of the corresponding states from dfa1 und dfa2. Or lets call them M1 and M2.
Then when you read a symbol you proceed according to what the current state of M1 and M2 would both "do".
So it's always pairs of states where one is from M1 and the other is from M2.
Now since we want the intersection of L(M1) and L(M2) we would say that the final states of M1x2 are those where both states in the pair are final states from M1 and M2.
If I missed something or got something confused pls dont hesitate to correct me

[latent cloud]

Yeah. But how did someone come up with that specific tautology from nothing?

[sharp turtle]

how is 0<e0<1 needed for 1.4?

it seems to make things more convenient obviously, since e0^2^n will be decreasing, but why is this assumption nessecary?

or am i overthinking this and this is just to show the exponential convergence as e0^2^n wouldnt converge otherwise

[coral parcel]

It's a single-formula representation of the syllogism on the left. In other words, it is what you would need as an axiom in order to replace applications of "hypothetical syllogism" by an appeal to that axiom plus modus ponens.

[vapid dune]

someone helped me get the answer, but I don't understand this problem

is this a predicate logic problem?

quantified logic?

I don't know how to type it out in symbols

would it be correct to say: all x, P(x) (where x is men, and P(x) = is human)

or is this an implication

man -> human

hella confused by this problem

[coral parcel]

I would say it's not even a formal logic problem. It's a question that uses natural language to check that you've understood the meaning of the words "converse", "contrapositive" and "negation".

[vapid dune]

to solve it, wouldn't you need to know how to put the natural language statement into symbols?

[latent cloud]

Oh okay. that makes sense 🙂 thanks

[coral parcel]

No, I'd say if you need to put things into symbols, then you haven't grasped the meaning of those three concepts well enough yet.

[vapid dune]

I understand how to negate the statement, but what confuses me is that the converse/contrapositive doesn't seem to follow the same rules, it's like the statement behaves more like an implication when you're trying to do the converse/contrapositive

[vapid dune]

lol, I just started this class 2 days ago

[coral parcel]

Yes, "converse" and "contrapositive" are only meaningful for implications or implication-like statements.

[vapid dune]

I am very much a beginner

[latent cloud]

I have this question: ```
Find the argument form for the following argument and
determine whether it is valid. Can we conclude that the
conclusion is true if the premises are true?

If George does not have eight legs, then he is not a
spider.
George is a spider.
∴ George has eight legs.

Setting "If George does not have eight legs" to A and "then he is not a
spider" to B. Then I could use Modus tollens to get the result.
Premise1: If A, then B.
Premise2: ¬B
Conclusion: ¬A

[vapid dune]

so for the problem I linked, you can think of the statement as either quantified logic, or as an implication?

[coral parcel]

One important point here (which books often don't stress) is that "converse" and "contrapositive" are barely even technical terms here. There are no important rules or procedures that depend on being able to spot them. They're just a conventional way to speak about the relation between claims that can sound similar -- especially such that we can state warnings such as "be sure not to accidentally prove the converse of what you really want to prove". Or such that we can say "we will now prove the converse", but the latter can always be replaced by "we will now prove [explicit statement of what it is we now prove]".

[coral parcel]

I haven't immediately noticed any problem with that.

[latent cloud]

Okay. So I am allowed to negate variables as long as I negate all variables in the argument?

[coral parcel]

I'm not sure what you mean by "negate variables" in this context.

[latent cloud]

Cause if I did like the text the premises would look like this right?:```
Premise1: If ¬A, then ¬B.
Premise2: B

[latent cloud]

changing A to ¬A

Or can A and B be either If George does not have eight legs OR George has eight legs?

[coral parcel]

There's not even any A or B in the original question. You're not changing anything; you're just deciding to use A for the claim "George does not have eight legs". The letter A didn't mean anything else before you made that decision.

[latent cloud]

oh right. So its up to the one solving the problem. Okay thanks 🙂

[coral parcel]

I'm assuming that your context allows you to know, as a matter of common sense and English, that the negation of "George doesn't have eight legs" is "George has eight legs".

[latent cloud]

I hate that the book im using only have answers for odd-numbered exercises XD

[coral parcel]

One can imagine a super-pedantic setting that insists that the negation of "George doesn't have eight legs" should be "George doesn't not have eight legs", and that it requires explicit argument to connect that to "George has eight legs". But it would be quite uncommon to apply that level of pedantry to the stage where you're still working with English sentences at all.

[latent cloud]

Yeah that makes sense. I think I'll go with my answer and use tollens rule of inference there to prove it. Or did I prove it in this case?

[coral parcel]

I'd say you proved it fine.

[latent cloud]

so simply assigning the variables TRUE for the argument form is the way to prove it?

[coral parcel]

huh. That didn't look like what you did.

[latent cloud]

hm wait. if A is true and B is true, then it would look like this:```
(A -> B) and ¬B // (T -> T) and F

[coral parcel]

That looks like you're doing something different form your modus tollens argument.

[latent cloud]

yeah. But I'm not sure what is the correct way to prove the question xd

[coral parcel]

I've told you two times that what you already did looks correct to me.
You don't have to believe me, of course -- but if you don't, then there's really no purpose in asking me again, is there?

[latent cloud]

It's not that I dont believe you, sorry. Its just that I dont understand how that is the reason I solved it. I've been reading my notes and the chapter but not quiet sure.

[coral parcel]

Note that you're being asked to judge whether the argument is "valid" -- which most logic books are adamant has nothing to do with whether the premises and conclusions are actually true or not.

[latent cloud]

Yes. But the second part of the question is: Can we conclude that the
conclusion is true if the premises are true?

[coral parcel]

Oh, I see. Yes, because that's what valid arguments are for. The whole reason for being concerned with the validity of the argument is that once we declare that it is valid, we're automatically also declaring that the conclusion is true if the premises are true.

[latent cloud]

Hm. But what happens if the conclusion isnt true depending on the premises, is it still a valid argument then?

I have this which I wrote when reading the book: An argument is valid if the truth of all its premises implies that the conclusion is true.

Is this correct?

[coral parcel]

If the premises are true but the conclusion isn't, then we must have done something wrong when we declared the argument is valid.

"Valid" means that it is inconceivable that the premises are true but at the same time the conclusion is false.

[latent cloud]

Oooh. Now I get it!

That makes sense.

So in this case, we can conclude that the conclusion is true if the premises are true since it is a valid argument form.

And if one of the variables aren't true, that COULD mean that the conclusion isnt true. BUT that doesnt invalidate the argument, is that correct?

@coral parcel Thanks for the help btw! Wasn't my intention to sound rude earlier.

[coral parcel]

Right.

[edgy berry]

hey i was wondering if anyone could look at my work and see if the proof by strong induction checks out

this is the question, and part b) the question was state a property about the sequence a_k that is true for all k greater than or equal to 1 and part c) was prove by strong induction

[sweet island]

try proving something else, that all numbers in the sequence are odd

@edgy berry

not sure if you can prove that it's divergent that way, need to conclude that $a_{k+1} \geq a_k$

[vital dew]

June.

[edgy berry]

yea i decided to change the property to being always odd

much easier

[sweet island]

oh nice

[edgy berry]

i did this instead

ty for the suggestion

[latent cloud]

If I have the predicates: I(x) : x is an instructor, S(y) : y is a student, T(x, y) : x is teaching y Can I do something like: ∃x∃y T(I(x), S(y)) To say "There are instructors that teach students"? Basically, have I understood that I can replace the x, y with any other predicate?

[worthy pivot]

No, you can't plug in the statements I(x) and S(y) into T

[latent cloud]

can you explain why?

[worthy pivot]

What you have written there is "x is an instructor is teaching y is a student", which does not make any sense

I(x) and S(y) are statements, not variables

[latent cloud]

Okay. Thanks

[latent cloud]

So is the correct answer something like this?:```
∃x∃y(I(x)∧S(y)∧T(x, y))

[worthy pivot]

That's better

[surreal crescent]

Hello! I am looking for a measure of similarity on a graph.

I have a graph-ish thingie that represents persons and their qualities. An edge means that the person has the quality. (It is almost a bipartite graph. There is some small amount of real world messiness where a quality is related to another quality or a person is related to another person.) My goal is, given a person, a quality or a bunch thereof, to write a program that ranks other persons by similarity to this given bunch. What can I do? I can already measure distance, but it is not fine enough — the diameter of my graph is 5, so I can only classify stuff in at most 5 groups by distance.

What else can I try?

[unreal stump]

Sounds like you want to look into social network analysis

[latent cloud]

Can someone explain how he got (3) from (1) and (4) from (2) and (3)?

[vale cairn]

What proof system are you using? Or are you doing it informally

[latent cloud]

The teacher just proved that, he didnt say which type. I assume direct?

[vale cairn]

Uhh

Okay I assume you are just doing informal logic like a first course in maths undergrad then? idk

Okay cool

So the point is that if A holds, then A or B holds

that's how he got 3 from 1

and then 4 from 2 and 3 is modus ponens

Namely: if A holds and A implies B, then B holds