discrete-math

[spark field]

That's how combinatorics is

I don't know that there's any way to better approach than just more practice

Maybe someone who has had more formal education in it could comment though

(I learned combinatorics mostly self guided)

[craggy flint]

i feel so stupid

[spark field]

Do you have an example problem, maybe I could explain how I approach it

[spark field]

I suppose my approach is similar to how I do a physics problem (thankfully, they provided quite the explanation), essentially I imagine/draw the situation to gain a better understanding

I identify the keywords like probability

For my first attempt I'll try to calculate the probability by calculating the number of valid scenarios (no row or file will more than one rook) and then the number of total scenarios

So the probability is valid scenarios / total scenarios

The total is probably the easier one

[craggy flint]

for total scenarios i was thinking that theres 64 squares

and theres 8 rooks

so it would be combination of (64, 8)

and then for a scenario to be valid, no row or file contains more than one rook,,, so basically rooks will never be in the same rows

theres 8 rows

[spark field]

Yep

Sorry my wifi is super on the fritz

[craggy flint]

yeah this is the part where im kind of stuck now

[spark field]

Yep to this

[craggy flint]

cuz i was thinking of 8!

but im not really confident that that is the right answer

[spark field]

The idea is how we construct this

[spark field]

Consider back to the way we can construct this total

You have 64 squares to place the first rook down in
Then 63 squares remain to place the second
Then 62 for the third,
etc.
Down to 57 for the last
i.e. 64*63*62...*56 = 64!/56!
But since it doesn't matter what order we place the rooks, we have to divide by the number of permutations
so the total scenarios is 64!/(56!8!) = (64,8)

(this is how the combinations formula is derived in the first place)

[spark field]

We can essentially do the same thing for the valid scenarios

Which is when the drawing comes in handy

Consider placing the first rook down

[craggy flint]

wait is it bad that i skipped this thing, i didnt even think about this whole thing

[spark field]

No matter what rank or file you put it in, you always remove 14 possible squares for any of the other rooks to go in

[craggy flint]

i kinda was just like, "theres 8 things i need to place,, the order doesnt matter, and there 64 squares i can put them"

[spark field]

It's not necessarily 'bad'

But it's important to at least know the technique

Since we can use it not just for basic choosing

[spark field]

But also more complicated

[fossil mural]

i find myself dissecting what the english is saying and trying to figure out how to interpret it
i mean that's kind of just how most of maths works

[spark field]

True as well

[craggy flint]

but for some reason,, courses like calculus or linear algebra,, i can visualize them and interpret the questions much easier

cuz for me they have some kind of structure regarding the questions

but for discrete math i feel like theres is no "sure" structure to hold on to

[spark field]

Meanwhile discrete (and even just combi) is a big subject encompassing way too many things

[fossil mural]

the education system up to... well, around the point where you are now, i guess, acts like maths is about rigid procedures and symbolic calculations
but in reality, even though those are useful sometimes, there are a lot of things where an approach like that just doesn't make sense, or wouldn't work

[craggy flint]

dont u mean 15

[spark field]

Oh yeah it sits on a square too

But yeah the first one removed 15 square, so the second only has 49 to choose from

The second one removes 13 squares (since two that would be removed overlap with the rows/columns already excluded by the first rook)

And so on

A little multiplication then leads us to an answer

[craggy flint]

so do you mean like i should approach this course differently

[spark field]

An open/creative mindset is good to have for all math courses but this one especially

[fossil mural]

maths is really just, precise reasoning about abstract objects, and so there isn't really any unified approach to all of it except, like, "look at the problem and think about it"

[spark field]

Math research in a nutshell

But such is the approach to any problem big or small

Think until you figure out what tools you can apply

[craggy flint]

im kind of unsure but do you mean like a multiplication of combinations so like (64, 1) * (49, 1) * and so on?

[fossil mural]

well (64, 1) is just, 64

[spark field]

Yeah you could write them as a series of combinations technically

[craggy flint]

i think my reasoning skills are not as good so i guess i just have to practice more

[spark field]

But like bee said it's just the numbers anyway

[fossil mural]

how many ways can you pick 1 thing from a set of 64 things? ...well, 64, each element of the set is a way of picking 1 element from that set

[spark field]

As long as you remember to divide by 8! at the end since the order of placement doesn't matter

[craggy flint]

no no i know what you mean but like i like to be specific regarding how i used combinations on the denominator,, so i want to use combinations on the numerator

i like to simplify step by step so i dont question myself when i check the question and my answer again

[craggy flint]

wait i still have to divide by 8! even though i did the combinations formula ?

[spark field]

Because technically here we are multiplying numbers

[spark field]

Just like this construction

That's why I did that construction first so you could see it

Dividing out the permutations is a necessary step when doing a construction with ordered placements

Another way to write it would be

[fossil mural]

the thing is, multiplication includes order

something like 64 * 49 counts how many ways you can choose an element from a set with 64 things, and then choose an element from a set with 49 things, in that order

[spark field]

Place the first rook
There are 64 positions and 8 rooks to choose from

Place the second rook
There are 49 positions and 7 rooks to choose from

Place the third rook
There are 36 positions and 6 rooks to choose from

.
.
.

Oh funny 64/8 * 49/7 * 36/6 gives you the 8*7*6... = 8! you originally suspected

[fossil mural]

there's a more direct way to see that it's 8!

[spark field]

Ah yes 8! makes sense because every group is isomorphic to a group of permutations

That's nice
I knew that would come up somehow as soon as I saw one per row and column

[fossil mural]

"C(n, k)" doesn't just magically remove order from random things, it means specifically "choose k things from a set of n, with the order of the k things not mattering"

in the case of C(64, 1), that means that the order in which you choose the 1 thing does not matter

[spark field]

(as shown in the first construction, we had P(n,k) then divided out k!)

[fossil mural]

which... we're only choosing one thing so there isn't really any "order" to be ignored in this case, so it comes out to the same thing as if you chose 1 thing "with the order mattering"

[spark field]

Indeed

Although you lose the nice representation of 8!/(64,8), you'd still get same answer

[fossil mural]

huh i didn't actually think of that

i just thought, in a valid arrangement there's a rook in every row

so you just go through the rows, in order, picking which column the rook in that row is in

and each time you place one you have one less option for the next row

[spark field]

That's also a nice way to view it

[fossil mural]

which i guess is kind of the same thing as the standard argument for why n! counts permutations of n things

[craggy flint]

okay

[spark field]

I basically link everything back to that 💀 the one combinatorics clue that came up in abstract

[spark field]

I really like this and then just multiply in 8! to permute the columns back
8!*8!/8! = 8!

And you keep the nice representation of 8!/(64,8)

[fossil mural]

...i don't see how my approach doesn't get you 8!/(64, 8)?

[spark field]

All approaches should get you the same answer

[fossil mural]

i counted the number of valid ways to arrange the rooks and got 8!

[fossil mural]

well yes obviously

but like

[fossil mural]

what are you talking about here

in what sense does my solution not already do that

or if it does then why are you multiplying and dividing by 8!

[spark field]

Oh I meant specifically in reference to when you mentioned that you can forgo dividing out 8! in both top and bottom
Which leaves
64*49*36*25*16*9*4*1/P(64,8)

[fossil mural]

...i did not mention that

that is true but i don't think i said anything about it

[spark field]

Ah you said when choosing one thing

I thought you had said across the problem

Definitely true when choosing one thing, dividing 1! cancels

For some reason I read it as we can WLOG order the rooks and then not depermute them in the valid cases or the total cases

Which is true but nasty

Sorry lack of reading comprehension over here

[craggy flint]

i think i have worse reading comprehension than you

i feel utterly stupid

[spark field]

Don't worry practice makes progress 🙂 as you keep working through problems and expanding your toolbox you'll also find your familiarity grows

[craggy flint]

wait okay i just started reading back i think im getting most of it,, but not all of it

im not sure if my understanding is right

but so lets say on the numerator we have 64 * 49 * ... * 1
that represents all the ways we can place each rooks right

but since technically each rooks are identical,,, we want to avoid repeating the same placements just because it was different rooks,,, so we divide by 8! ?

[spark field]

Right

[spark field]

Yes

We can see it in a simpler scenario with two rooks on a 2x2 board

You have 4 options for rook 1 and 1 option for rook 2
This should be 4 placements right?
Wrong, and you can draw this simpler scenario yourself to see that there are only 2

Because we need to divide by 2!

[craggy flint]

right cuz if we place the rook1 in the top left and rook2 in the bottom right,,, that would be the same thing as placing the rook2 in the top left and vice versa

thank you guys so much for helping im sure im not perfect at it but i think my approach got at least a little better

wait @spark field what book or resource did you use to learn discrete math/probability, my prof's slides sucks so im looking for other resources

he also doesnt give us like practice questions to work on so yea

[spark field]

Oh those are absolutely necessary, evil to not include p.p

So personally my discrete class used an online book sadly I can't access but

Discrete Math and its Applications by Rosen is renowned (I've been skimming it lately and I like the presentations)

I definitely like it for the discrete structures

Maybe not so much the foundations (of math)

But definitely eg domino tilings and problems that give you combinatorial tools

[craggy flint]

do you remember if that book contains stuff regarding probability

[spark field]

Probability tbh my understanding is fairly rudimentary

Probability* XD

I know the basics and intuit/work out everything else on the spot

[craggy flint]

that is so impressive

[spark field]

But some of the common theorems and such I don't actually know them (I usually end up using combinatorics to work them out 🤣)

So I can't recommend anything on that front sadly

#book-recommendations might be a good place to ask though

[craggy flint]

okay

thanks a lot for the help!!!!

[spark field]

I see this book was recommended as a good introductory book as well, so you may be interested:

The Art and Craft of Problem Solving (Paul Zeitz)
Assumes some basic calculus and comparable fundamentals. Anyone with an open mind should be able to profit from it.
The book is really well written, and focuses a lot on the process of solving a problem in addition to actual problem solving. It has a lot of problems after theory. It focuses on the basics of problem solving, and have chapters on problem solving strategies, cross-over tactics, combinatorics, number theory, geometry and some analysis and linear algebra.

Especially since it focuses on problem solving technique

[spark field]

No problem! and good luck 🙂 feel free to @ me if you ever come by with another question

[craggy flint]

i probably will,,,, i have not struggled in a math course this bad until now

lol

[spark field]

Challenge builds ability 💪

[craggy flint]

• i cant fail this course cuz its a grad requirement + i need to take it to take upper level courses lol

[spark field]

Real

[flat lintel]

I asked this in #book-recomendations but no one said anything, maybe you could say something😔

[spark field]

I'll take a look when I get a moment today

[leaden gulch]

How much number theory is needed for combinatorics research?

Not graph theory

[spark field]

Depends on what you're in

I started working in combinatorics before I took my first NT class

And I haven't particularly applied anything from NT so far except a few things (more abstract algebra than NT)

But there are definitely NT heavy parts of combinatorics (just like NT heavy parts of abstract algebra)

I would say for combinatorics in general though not particularly much NT is necessary

Your informal understanding of numbers will suffice

[flat lintel]

Does anyone have the book How to Prove It (or know the exercises), can you help me with this one?

Please, don't do anything too fancy, I'm just starting out

[spare slate]

work mod 3

[flat lintel]

But I don't know mod

[spare slate]

Remainder when you divide by 3*

[flat lintel]

Is it true that for 3 consecutive integers, one of them must be a multiple of 3? I was asking chatgpt (please don't hate on me for that 🙁 )

[arctic needle]

list it out and prove it

[flat lintel]

But I don't know how to prove things😭

[arctic needle]

aren't you learning how to prove

[flat lintel]

Not yet, this is the exercises of the introduction

[arctic needle]

hmm

[arctic needle]

how could you construct one kind of triplet of consecutive integers

like, by free will

if you wanted to show it to be true

[haughty garden]

There’s an entire field of combinatorics that looks at problems at the intersection of number theory and combinatorics called arithmetic (and additive) combinatorics. But in general, I would say that they are pretty independent fields, so you don’t need much number theory knowledge to get started

[spark field]

What opengangs said

[spark field]

Ingenious idea

[winged delta]

I use this book in my course, I like it a lot. Admittedly I mostly use lecture notes, but it's a great supplement

[slim geode]

You can use ChatGPT for help, but be careful. If you just ask it and get the right answer, you won't go through the process of actually thinking for yourself and so you won't learn as much. I recommend you always try yourself first before asking for help (and that goes for any kind of help, not just AI).

[flat lintel]

Yes, I tried it first but I didn't know where to start

[slim geode]

How long were you trying for?

Starting is often the hardest part because you need to get the right idea

[hybrid quiver]

i mean try and find counterexample

or pick random numbers

276-277-278

ok there is one

altternativey think about it this way

multipes of 3
3-6-9-12-15....

we have a multiple of 3 every 3 numbers

you can use modulo properties

pick an arbitrary number

x mod 3 = 0,1 or 2

if it is 0 you are done

if it is 1, then consider (x + 2 )mod 3..

[flat lintel]

But I didn't learn mod yet

[hybrid quiver]

do you have to prove this formally ?

or is it just enough to see why it is true

[flat lintel]

Just enough

[hybrid quiver]

the multiples of 3 by definition repeat every 3 numbers

.3,6,9,12,15

so if you take 3 consecutive numbers

1 of them must be it

[hybrid quiver]

even if you don't understand mod i can explain the idea

[flat lintel]

I see, thanks

[hybrid quiver]

have you learnt remainder ?

[flat lintel]

Yes

[hybrid quiver]

ok so if you take a random number and divide it by 3

it's remainder can 0 or 1 or 2

correct ?

[flat lintel]

Maybe

[hybrid quiver]

well if you divide by 3 you can't have remainder 4 right

[flat lintel]

Ah yes, sure

[hybrid quiver]

ok so if you have remainder 0 then it is multiple of 3 agreed

but if it has remainder 1, then if you look at the number after it, it will have remainder 2, and then after it remainder 3 which is same as remainder 0

[flat lintel]

Remainder 3 is the same as remainder 0?

[hybrid quiver]

yes if u divide by 3

think about numbers where if you divide by 3 you have 3 left

doesnt existp'

[keen flower]

Did I do this right? He said to use commutative 3 times but idk where to use the 3rd

[spark field]

,rcw

[spark field]

Looks like it should be right

[spark field]

<@&268886789983436800>

oh it's gone

[spark field]

<@&268886789983436800>

[stuck trout]

Is my recursion correct?

[random sparrow]

I need help with b)

basically, f(1) = 5
f(2) = 6

5 + 6 = 11 = 2 = g(1)+g(2) (mod 3)

so g(1)+g(2) = 2 (mod 3)

how many injective g functions satisfy this?

where g : {1,...,10} -> {0,...,30}

[cerulean wind]

first find many ordered pairs (with first component different from the second component) in {0,…,30} there are whose sum is 2 mod 3

[random sparrow]

care to elaborate?

[random sparrow]

yeah the problem is that counting them by hand is very hard there's like a gazillion possibilities

@cerulean wind

[spark field]

I think it should be a fairly straightforward counting problem

For example, let g(1) = 0
There are 10 values in [0,30] that g(2) could be so that g(1) + g(2) = 2 (mod 3)

Then there are (28 choose 8) possibilities for the rest of the function values

The same is true for g(1) = 3,6, etc. the 11 members of the equivalence class of 0 mod 3 in [0,30]

So there are 11*10*(28 choose 8) possibilities for g(1) = 0,3,6,...

Now you just do the same process for g(1) = 1,4,7,... and g(2) = 2,5,8,... and add the answers and done

[cerulean wind]

yea, the remainders mod 3 are 0, 1, and 2. all possible sums of remainders are 0,1,2,3,4; 3 and 4 are identified with 0 and 1 mod 3, resp.

the residue classes up to 30, modulo 3, are:
{0,3,6,9,12,15,18,21,24,27,30} ::: 0 mod 3
{1,4,7,10,13,16,19,22,25,28} ::: 1 mod 3
{2,5,8,11,14,17,20,23,26,29} ::: 2 mod 3

the only ways to get a sum x + y with x != y and (x + y) = 2 mod 3 are:
x = 0 mod 3, y = 2 mod 3 (along with the roles of x and y swapped)
x = 1 mod 3, y = 1 mod 3

so there are 2(11 * 10) + (10 * 9) = 310 distinct pairs of numbers (x,y) with x != y between 0 and 30 such that x + y = 2 mod 3.

package main

import "fmt"

func main() {
    n := 30
    count := 0
    for x := 0; x <= n; x++ {
        for y := 0; y <= n; y++ {
            if x != y && (x+y)%3 == 2 {
                count++
            }
        }
    }
    fmt.Println(count)
}

golang code to verify lmao

so once you have that

you just need to multiply by the number of injective functions [8] —> [28]

[whole gale]

does anyone have discrete math exercises/resources? especially things on graphs, trees, forests and other recursive structures

[spark field]

Discrete Math and its Applications has exercises on graphs I know at least

[keen flower]

can someone help me with this please

its hw and i have no idea how to do it

i know not p and not q is 1

and p and q is 1

[hidden totem]

so there are at least two ways to think about these logical operations

one way is to draw the circuit components

another is to think of them as expressions

do you have a preference?

[keen flower]

draw

this is what i have so far

[grand crown]

you mixed up the OR and AND

think of AND like multiple things happening at once, and OR as at least one thing happening

you want "not P and not Q" or "P and Q" to happen

[keen flower]

i redid it

[hidden totem]

that looks good!

i believe thats the 5 gates

do you want hints for how to do it in 4?

[keen flower]

no its ok i have more things to study

did i do this right?

[hidden totem]

what's this?

[keen flower]

logic

[hidden totem]

what's the question?

[keen flower]

the top one

to simplify

[hidden totem]

oh i never saw this

[keen flower]

say what?

[hidden totem]

nvm i get the question now

[keen flower]

ok!

i used reverse distributive law to get the p and not p together

and not q on the outside

after that, i used the contradiction law

[hidden totem]

yeah looks good then

[whole gale]

thank you!

[slim geode]

Isn't this also 1 for p=1 and q=0?

[spark field]

Yes - the truth value is always (not q)

So if q=0 then the whole thing must be 1

[slim geode]

So this is a different question than the one with logic gates

[spark field]

Yeah

Logic gates was (p and q) or (not p and not q)

[slim geode]

I thought you were trying to find the solution with only 4 gates

[spark field]

They said they didnt have time for it

[slim geode]

Oh

[nimble condor]

how do people actually go about extracting 'key steps' in proofs? it's something that i really struggle with - i do a lot of problems but i don't have much, if any intuition for why i'm supposed to do a given step

for example

this is a problem in the textbook

i just don't get why i would want to let x=2^b-1 and y=1+2^b+2^(2b)+......

like: obviously i need to find some arbitrary x and y such that x,y>1 and x,y are integers
but it's just incomprehensible to me how anyone could immediately arrive at making x=2^b-1 if they don't know from before and (2^b-1)* (1+2^b+2^(2b)+...)=2^(ab)-1

[spark field]

Practice and experience

[odd heart]

Yeah, this proof doesn't present the key insight very well in my opinions, it starts by noting that there's a general formula/pattern for expressions of the form a^n-b^n (you can look at what happens with the difference of squares, or the difference of cubes, and generalize). So then you want to apply this kind of thing to 2^n-1, which is 2^n-1^n. Doing it like this won't work, because the formula will give you 2^n-1^n = (2-1)*(something), so it won't be a product of two integers greater than 1, but you also know that n is the product of two numbers, so you write 2^n-1^n = 2^(ab) - 1^(ab) = (2^b)^a-(1^b)^a and proceed from there.

In the proof as written they basically immediately plug in the thing you'd figure out by doing these auxiliary steps

[nimble condor]

yeah but i practice a lot, i took discrete 3 years ago

[spark field]

Oh I meant to come back and continue writing

I wrote that on my phone and came to my computer

That is to say, exposure

In the words of one of my profs

You see a proof like this and you gain a hammer, a technique you could think about applying elsewhere

(the generalization described by outsider, I suppose)
It's what makes new results sometimes groundbreaking, since someone has come up with a hammer that no one else realized to come with for the given nail (problem)

[nimble condor]

see that makes sense, sort of. but that kind of feels like kicking the can backwards - bc how would i know that the general formula for expressions of the form a^n-b^n is something that i should use for this problem?

[odd heart]

Your starting point (i.e. the thing you are aiming to prove something about) is 2^n-1, and the idea to rewrite it as 2^n-1^n is one that comes with experience and having seen this kind of thing several times previously

[spark field]

In any case I will say that the intuition probably follows

1. I want to prove that something is not prime
2. I need to show that I can multiply two things to get it (i.e. it has a non1 factor)
3. How to factor 2^n - 1?
4. One must know the fundamental algebra identity of 1 + x + x^2 + ... + x^n = (1 - x^{n+1})/(1 - x)
5. Therefore, (1 - x)(1 + x + x^2 + ... + x^n) = 1 - x^{n+1} and we are done

Now me personally I probably would have forgotten and looked stupid xd

I really should always remember I can factor x^n -1 since it clearly has 1 as a root

The important thing here is the choice of x

x =2 doesn't work since then x-1 = 1 and we haven't factorized into non1 factors

so instead they use x = 2^b, hence the requirement of n not prime, an important hint

Just to add on my train of thought to what outsider has already said

[agile magnet]

I think there's a thing that people are skating around here

[agile magnet]

And that no one would likely come up with this proof in this line by line order off the bat in one shot

You write the proof in this manner, because it is the clearest way to communicate the proof

but you may not figure out the proof in this manner

and also yea this does come from knowing the expression for a^n - b^n which is a good formula to keep in the back of your pocket

but often the answer to "how does someone come up with this" is that they came up with it via scratch work and trying a few different ideas

[mortal ermine]

I'm getting discrete math class for thr first time next week for my computer science degree I'm first year

[spark field]

Nicee

[mortal ermine]

Does anyone have some tips or advises to share?

Like how to study what to avoid what to focus on

[mortal ermine]

Thanks

U have any tips?

[spark field]

Mmm from my experience what you end up covering depends in a not insignificant part on the school but I guess in terms of tips as a CS major pay attention in the beginning when they go over logic (true-false), since it's relevant (you'll likely have to take a class dealing with digital design at some point) as well as algorithms (if the class covers them)

On the other hand if the class is more proofs focused then for your success it would be beneficial to learn the techniques well, doing extra practice or something of the sort to become properly familiar

[mortal ermine]

I think it's gonna be more about proofs bc we cover algorithms in other classes

To be honest doing practice problems is the best thing to do in every class but

I'm kinda afraid what I won't be able to solve the practice problems?

Proofs kinda seem weird or the theories behind discrete math. For me atleast

Hence why I'm asking for tips or advice to start off good

[spark field]

That's what this server is for, you can ask and be guided through any questions

[mortal ermine]

Thank you

[spark field]

Hm, someone may come by and have more concrete suggestions then

I personally haven't taught discrete and I took it my first semester which was almost 3 years ago now

So let's just wait and see if anyone else has anything else to add for you

[nimble condor]

ic
my intuition took me to step 3 but then i got stuck there - i knew that identity from before but it just… didn’t occur to me to apply it

[spark field]

haha yeah like I said I probably also wouldn't have remembered it and thought to apply it 😆

What's important is to grow from having read the proof and recognize you can always factor x^n - 1 if it ever comes up again in another proof

You remembering and everyone else not is what will turn the table and have them asking you 'how did you come up with that' about your proof 😆

[trim thicket]

is this the channel to ask about boolean algebra

[robust monolith]

Either yes or no

[trim thicket]

so its yes then

[grand crown]

i thought this was a cool result that's fairly easy to compute

find the number of monic polynomials of degree n, over Z/pZ (for prime p <= n), that have no roots

[hybrid quiver]

At least 4

[grand crown]

not if p = n = 2 :(

oh, and if anyone here hasnt seen Z/pZ before that's just the integers mod p

so the polynomial coefficients are only elements of Z/pZ, and we only plug in elements of Z/pZ into the polynomials to determine roots

maybe this is better posted in the grf channel actually

[eager wadi]

Can you guys help me out in this rsa qn

[odd vale]

"HI" is too large to be encrypted with N=7*13

[upbeat sequoia]

i have a question when i ask gemini about the time complexity of this tipe of graphs (paths) while using the kruskal alghorithem the answer is eloge?

why ist it just e? as there is not path to sort should the time complexity in this case be exclusivly dependent on the number of nodes (or more precisly edges)?

[hexed axle]

Assume we know the graph is a path graph, then we know the MST of G is the path itself. Hence it would be exculsivly dependent on |V|, yes. But since you use Kruskals Algo you have to sort the edges first to make sure you pick the smallest unused edge next. The sorting works in O(E log E), because you take each edge and compare it to a subgroup of all edges. It is inefficient in this case of the Graph, but the sorting needs to happen as it is part of Kruskals Algo.

[prime cloud]

hey quick question for yall, is there an actual closed form formula for the bijection that shows that Q is countable? The construction is so simple that I feel like there must be a way to write it mathematically, but none of the many discrete math classes ive taken have shown it, so im wondering if it even exists.

[stray reef]

"the" bijection?

[hybrid quiver]

idk what you mean

[stray reef]

there's a great many of those.

[hybrid quiver]

like a map from Q to Z that is explicit ?

The one i like using is with fundamental theorem of arithmetic

also works great for Z x Z for instance

[prime cloud]

well i mean the standard one, the one that involves writing the numbers in a grid and drawing a line through all of them to define the bijection

[hybrid quiver]

idk what you mean by standard one but there is many

[prime cloud]

lemme get an image

[hybrid quiver]

the one you're referring to is useful visually but there are many closed form formulas which are quite easy to see and construct

pick your 3 favourite primes

given a/b non zero and reduced to simplest form with b positive:
(p1)^{a}*(p2)^b*(p3)^{1 if a > 0, 0 otherwise)

[prime cloud]

im referring to cantor's diagonalization argument

thats the name i was looking for

[hybrid quiver]

isn't that to prove uncountability of R ?

[prime cloud]

oh right

uh damn i forgot what the name is then

[hybrid quiver]

ik what you're thinking of i think

[prime cloud]

this is what im thinking of

[hybrid quiver]

yea

that's useful visually if you're looking for closed for that specifically hmmm

[prime cloud]

i presume it involves something mod m + n for m / n, but thats about as far as ive gotten just thinking about it

[hybrid quiver]

idk it seems like a pain in the ass

[hybrid quiver]

i'd use this

if you just need one

[prime cloud]

i see

[hybrid quiver]

You know uniqueness of prime decomposition or fta ?

[prime cloud]

i was mostly just curious but now ig i see why its omitted even though it might be possible theoretically

[prime cloud]

yeye

[hybrid quiver]

yeah then these countability proofs become much easier

because you can always create injective maps

[prime cloud]

oh yeah that totally makes sense

i never thought of it like that

[hybrid quiver]

there's a very useful theorem

it says that

if you have a function that's injective into Z

then it's countable

Likewise if you have a surjective function from Z to A then A is countable

it's not too much work to prove

[prime cloud]

ooh interesting

ive been thinking about writing something on discrete math i might add that in as a result

[little prism]

some people speak of cantors first and second diagonal argument. the first being for Q, the second being for R. hence thats probably the source of your confusion

[prime cloud]

ahhh i see

[neon harbor]

this is not a bijection btw, it's not injective since for example 1/1 = 2/2 = 3/3 etc. But it's a surjection, which is enough to show Q is countable

[prime cloud]

yeah the image leads to believe otherwise but the usual construction as i've seen it skips over fractions which are integer multiples of fractions previously encountered

[hidden totem]

also just fyi any "list" will do as long as you can demonstrate no element is missing from that list

so this winding path can take on almost any shape you want it to take on, as long as you can get it to cover everything

[jovial sail]

i remember this

[thin anchor]

Hi all! There is a language here: a^i b^i c^j with j >= i which I am concerned with. Is this language context-free? It is claimed in my homework assignment that it is, but I have my doubts. Please just let me know whether it is or is not. I am not looking for a specific CFG to generate it.

Thank you in advance.

[spark field]

Yes, this is commonly called the extended euclidean algorithm

And yes A and B have infinite choices (there's actually a formula based on whatever values you get)

You can use any of them, so just the output from extended euclidean would be enough

And no, the combination is not unique

3(1) + 2(-1) = 1
3(3) + 2(-4) = 1
In general
3(1 + 2k) + 2(-1 - 3k) = 1

You can do that but depending on X and Y you may be guessing for a very long time

Yes

The thing is by doing euclidean algorithm you also do half of the steps for the extended version

[spark field]

again, yes

There are infinitely many solutions

If you're only looking for one though you only need one of those infinitely many

[little prism]

you need to practice more, then

no way around that

[static light]

advice for someone taking discrete next year?

[agile magnet]

Number one issue I see people not actually learning the definitions as they go. Number two issue I see is people not giving themselves enough time on homework

honestly this advice applies to most any math class not just discrete math

[hidden totem]

i would argue that it is particularly important in discrete math. in terms of theory or amount of concepts to learn, there are a lot less in discrete math compared to other math fields, so the difficulty comes precisely from getting familiar with how to apply the methods to solve problems

[hybrid quiver]

Do a lot of problems

[wooden moth]

how to 1+1

[wary viper]

Dm me

[wooden moth]

huh

[wary viper]

Jk haha

[wooden moth]

tf was that 😭

[wary viper]

HAHAHAH

:p

[odd heart]

!help

[lofty cloud]

To ask for mathematics help on this server, please open your own help channel or help thread. See #❓how-to-get-help for instructions.

[pallid plover]

i am doing part (b) actually

we shall use induction on $n$. Setting $n=1$, the only elements in the second row are 1 and so natural numbers. Inductively, assume $\binom{n}{k}$ is a natural number for all $k$. Then
[
\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1},
]
where $\binom{n}{k}$ is a natural number and $\binom{n}{k-1}$ is again a natural number as each element of $n+1$ th row are natural. Hence $\binom{n}{k}$ is always a natural number.

[vital dew]

Afzal mathcod #1 fan

[spark field]

Interesting

[pallid plover]

i mean it is easy to show nCk is a natural number by showing its nothing but choosing k items from n. but using pascals triangle is kinda new for me

[robust thunder]

Hey everyone!
Quick question: when learning logic gates and Boolean expressions, do you mostly stick with discrete math symbols (∧, ∨, ¬) or CS-style symbols (*, +, ~)?
I find the logic symbols easier for reasoning, but I want to know what’s actually practical to focus on while learning. Any tips on juggling both?

[spark field]

Personally I find the engineering(/CS) notation (juxtaposition, +, overline) easier to work with when actually doing problems

The discrete math notation I really only use when doing set theory or writing mathematical formulas

Basically engineering notation whenever working with pure boolean algebra and math notation whenever it could be confused

At least that's my preference now that I've finished all my courses involving them

[pallid plover]

math symbols

[cloud rampart]

is it for a class? if so, use whatever notation the class uses

[robust thunder]

Yeah, two different classes

[spark field]

Then use the one in the one class and the other in the other

If that's what each uses

As mentioned my personal preference is now that I've finished with the classes but I took two math class and two CS classes each which used one or the other notation and had to stick with each during

[robust thunder]

Yeah, it looks like I'll have to dual wield and learn them both. Just wanted one to focus on but all good

[boreal isle]

How do i make a mathematical function with no input?

for example
f : Q
f(null) = 2.43354654

where Q is rational numbers

Basically a variable but with the syntax of a function

[little prism]

f:{1}->Q

but why do it with this perspective

why not just a constant

[boreal isle]

Functional programming languages define constant functions like this

f : Int
f = 2

and functions that do things like

f : Int -> Real
f x = x + 0.1

the second example's definition is exactly the same as in math so I was wondering how the first one would look

[fossil mural]

also exactly the same

[little prism]

I mean the first one isnt really a function. its just an element. f\in \Z

[fossil mural]

it's just, ⁨2⁩

if you think ⁨Int⁩ is the type of nullary functions that output integers then to be consistent you should also think that the input ⁨x⁩ in the ⁨f : Int -> Real⁩ example is actually also a function

which is... obviously kind of silly, although it's arguably not wrong in the sense that there just really isn't much difference between "a function that takes no arguments and outputs an element of ⁨T⁩" and "an element of ⁨T⁩"

[bitter vortex]

are they isomophic

[little prism]

what do you think

[bitter vortex]

teacher said not but AIs say isomorph

[odd heart]

What do you think, though?

[bitter vortex]

isn't

[odd heart]

Why do you think that?

[stray reef]

!noai

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[crimson canopy]

what is a graph component?

a component of graph G, is a subgraph H such that no other subgraphs of G contains H

so i have 29 components....and i want to find the minimal number of edges, which is a tree i think which is vertex amount - 1

i am imagining that i can approximate each component into a "vertex", so that's 29-1. because i have a tree of components
then each component has edge number = vertex number(in component) -1

so minimal amount of edges is (total vertex number) - 1 - 29 = v - 30?

or is G supposed to be disconnected?

so i get 29 stuff floating on their own

[grand crown]

that seems like a strange definition of component

are you sure it isn't something like

a connected subgraph such that no other connected subgraphs contain it

[crimson canopy]

erm... isn't that what i meant? (i sincerly think so, and now i am worried)

i got the definition from
https://math.gordon.edu/courses/mat230/handouts/graphs.pdf

definition 16

Definition 16. A connected component of G is a connected subgraph H of G such that
no other connected subgraph of G contains H

oh, i forgot the connected word

[spark field]

connected is an important word

In this definition

XD

[crimson canopy]

yeah, my bad

so... does this mean, each component is disconnected from another?

or are they connected like a tree(which is G), and so the branches are ...mhm... connected to each other, via the main tree, but otherwise are "separate" and thus no other subgraphs contain each component?

[spark field]

Yes

Example

,tikz
\draw (1,0) -- (1,1) -- (2,0) -- cycle;
\draw (1,1) -- (3,1);
\draw (0,0) -- (0,1);
Example with 2 connected components

[vital dew]

Coolempire93

[crimson canopy]

that's 2 components?

oh. ok

[crimson canopy]

thank you

damn... and i thought GT is all about everything connected to everything in some way

[spark field]

A graph specifically with everything connected to every thing (i.e. single component) is called a connected graph

But forests (graph where all components are trees themselves) for example are also studied in GT

[crimson canopy]

if i were to draw a subgraph of a forest, there will be repeats(of subgraphs)?

that didn't come out well

erm... if i define a subgraph of a forest, and i define another subgraph of said forest

is it always possible that the latter can contain the former?

like... my left hand is a subgraph, same as my right

i suppose i can segment my body in such a way that it includes both left and right? which is another subgraph

even though its a tree from the torso

[spark field]

If I'm understanding the question right this is possible for any graph 🤔

[grand crown]

a graph is a subgraph of itself although maybe thats not what youre imagining

if we specify proper subgraphs then you would only not be able to do this if your subgraph is only missing 1 vertex

[spark field]

,tikz
\node[draw, circle, inner sep=2pt] (A) at (0,0) {$A$};
\node[draw, circle, inner sep=2pt] (B) at (1,0) {$B$};
\node[draw, circle, inner sep=2pt] (C) at (1,-1) {$C$};\nodedraw, circle,inner sep=2pt at (0,-1) {$D$};

\draw[-,thick] (A) -- (B) -- (C) -- (D) -- (A);

[vital dew]

Coolempire93

[spark field]

Like if I choose a subgraph {A,B} and one {A} one contains the other

pretending this is a forest ig

[spark field]

🤔 is that so

[grand crown]

its not a deep statement, like if i force my subgraphs to be proper than im already at "max capacity"

well i guess you could just delete and add in edges

idk i dont think this is a particularly interesting notion

[spark field]

Oh right it doesn't say induced subgraph

XD

[spark field]

agreed

[crimson canopy]

suppose we delete c, so it looks like a tree, andA, B and D are trees themselves

so i can have a subgraph(of the entire thing) that contains A and B? even though they each are only connected by 1 edge to each other?

[spark field]

Unless you specify the subgraph is connected then they need not be connected in the first place

But even if they need to be connected then if I'm understanding the question correctly then the answer is yes
Snowflake may be able to say more clearly

[grand crown]

just to clarify what do you understand a subgraph to be

[spark field]

good question

[grand crown]

subgraphs are extremely general, i dont think youre going to get a lot of interesting structure out of this

unless you specify more about them which i imagine youre doing in your head?

[crimson canopy]

subgraphs are graphs within the graph

okay, i suppose you are right that is proper subgraph

i think, i have an intuition, even if i can't articulate it well

[grand crown]

okay so a graph is a set of vertices V and a set of (ordered) pairs of vertices E, where each pair represents an edge

and then a subgraph is a subset of the vertices V1 and subset of the pairs E1 such that the pairs in E1 only contain vertices in V1

we could add the restriction that V != V1 or E != E1 to enforce that we have a proper subgraph

is this what you're thinking?

[crimson canopy]

we could add the restriction that V != V1 or E != E1 to enforce that we have a proper subgraph
er... i thought proper is just to... how should i say, prevent someone saying V is a subgraph of V

[grand crown]

right, meaning we shouldn't allow the same vertices and edges

[crimson canopy]

ye

[grand crown]

we should drop at least one edge or at least one vertex

so V != V1 or E != E1

[crimson canopy]

yes, i suppose so

so it is impossible for a connected graph G, to (when listing all possible proper subgraphs) have subgraphs completely mutually exclusive?

[grand crown]

that's totally possible

unless G only has 1 vertex

graph theory is one of the most visual math subjects out there, i highly recommend drawing some graphs out

[crimson canopy]

yeah, i think i will draw something out, and post. its going to be ugly

[grand crown]

they can be small graphs, they dont need to be super complicated

[crimson canopy]

i think i answered my own question

so (dotted lined) green and oranges are subgraphs

they are "self contained", but its possible for me to draw another subgraph(of G i.e the entire thing) that contains some elements of green and orange right?

that did not turn out well

[grand crown]

right these are disjoint subgraphs but there are other subgraphs that overlap with these

[grand crown]

subgrapsh also don't have to be connected

if you're asking specifically about connected subgraphs that adds a lot more structure

like here for instance i can just pick 1 vertex from the left and 1 vertex from the right with no edges

and that would be a subgraph that overlaps with both subgraphs you drew here

it just wouldn't be connected

[crimson canopy]

oh, i didn't know that. until earlier.

[crimson canopy]

oh ok. that's interesting. i have never thought about this

[grand crown]

like, a subgraph is literally just any subset of vertices and any subset of edges that are contained amongst those vertices

we aren't specifying connectedness or really anything at all

[crimson canopy]

so i can some really wacky combinations?

like not only disjointedd vertices but also edges completely unrelated to those vertices?

just for kicks and giggles

[grand crown]

the edges do have to be amongst the vertices you selected

for an edge to be in your subgraph, its endpoints have to be there too

that's the one restriction we're really putting here

but you can have vertices in the subgraph without putting in any edges that those vertices connect to

[crimson canopy]

thank you. this is most clear

thank you @grand crown @spark field

[crimson canopy]

Regarding dijstra's algo, what if we end up in a dead end?

A is connected to blah blah blah
lets say the shortest distance is C

but C is a dead end

(dijstra's algo iirc is that you list out the distance from a point, overwrite if necessary, then when you move on to the next step, you choose the point with the minimal distance)
what if the next point is a dead end by itself?

[grand crown]

djikstra looks at all possible outgoing edges and takes the overall cheapest move from source to a new target

if none of the current outgoing edges go to new vertices, then you can’t reach any other vertices in the graph

if a point C has no outgoing edges (or all edges only revisit vertices already reached), then C doesn’t contribute to the outgoing edges

[crimson canopy]

so, i choose the next smallest from A?

and continue dijstra?

e.g

[grand crown]

like, let’s say we currently have processed a subset S of the vertices (and we assume the shortest paths to each vertex in S is contained within the subgraph induced by S)

Then we just look for the cheapest edge that starts in S and ends outside of S (and by cheapest I mean that the overall distance from source to possible targets is cheapest), and that’ll be the new vertex we add to S

Yeah, so C has no more outgoing edges so we just look at the edges outgoing from B

If C did have any outgoing edges that didn’t just go back to our visited cluster, then we would be comparing those too

[crimson canopy]

thank you 🙏

[pallid plover]

How to prove that $\sqrt{2}+\sqrt{6}$ is an irrational number? In my opinion, say $\sqrt{2}+\sqrt{6}=\frac{p}{q}$ then $2q^2(4+2\sqrt{3})=p^2$. But $p$ can either be written in the form of $2n$ or $2n+1$ so surely $p=2n$ as left side of the equation is even. Thus simplification shows
[
q^2 = (2-\sqrt{3})n^2.
]
I dont know how to proceed further!!

[vital dew]

Afzal mathcod #1 fan

[spark field]

Are you allowed to derive a contradiction from the fact that you've just shown that the difference between two integers is irrational

[pallid plover]

oh

yes, we have proved somewhere that this is irrational, and surely the right side is irrational but left is rational (in particular an integer)

ahhh wao

thank you so much coolempire

[spark field]

No problem :))

[pallid plover]

[cunning plank]

sqrt2+sqrt6 = 4cos(pi/12) which must be irrational since cos(x) only has rational values when its equal to ±1 or ±1/2

[stray reef]

isn't sqrt(2) + sqrt(6) the root of some quartic polynomial with integer coeffs?

[pallid plover]

well how we can prove that cos(x) has +-1 , +-1/2 only rational values?

[pallid plover]

yes, but how does it reflect its an irrational??

[stray reef]

find the quartic that annihilates it, then throw RRT at the quartic

[pallid plover]

RRT?

well i guess the quartic is $x^4-16x^2+16=0$

[vital dew]

Afzal mathcod #1 fan

[stray reef]

rational root theorem

[little prism]

well thats obviously false since cosx is continuous and therefore hits every rational number between -1 and 1. you need to be more precise about your statement

(the result you want is called nivens theorem and can for example be proved with the double angle formula)

but RRT is certainly easier here

[pallid plover]

ok i see, since i assumed \sqrt{2}+\sqrt{6} is a rational solution of the above polynomial with integer coefficients so it must satisfy rational root theorem. that mean 16 divides \sqrt{2}+\sqrt{6} but it isnt true

and its a contradiction

right?

isnt (a) kinda confusing? i guess we have to prove that either x is irrataional or an integer ?

[stray reef]

that mean 16 divides \sqrt{2}+\sqrt{6} but it isnt true
are you... sure about that

[pallid plover]

oh no, i misunderstood RRT, the numerator of the rational root divides the constant term.

[stray reef]

yes

so rather you should check that x=1, x=2, x=4, x=8 and x=16 all are not solutions of the eq

[pallid plover]

umm got it, thank you so much

[little prism]

alternatively just check that sqrt2+sqrt6 is not an integer. or at the very least show that if its an integer from those then it would be 4

[tacit ore]

1+1

[spark field]

again?

[robust monolith]

How's the + operator defined?

[hybrid quiver]

is elem nt useful

do any of the more advanced nt courses require it as prereq?

[quick folio]

no

[next sail]

doe sanyone know how to solve this problem? it's for my automata and computation (upper div cs) class

[winged delta]

Depending on your formalism, this will take k+1 states

Think about how you'd recognize {w ends in 1}, and how you'd do {w ends in 11}, etc.

[next sail]

im unclear on what they mean by "w ends in k 1's"

does that mean for a L(subscript 1) = {q: w ends in 1 1's}... 01 and 01111 would be accepted?

[floral merlin]

yes, the last k symbols of w are all 1.

[shrewd obsidian]

feels ambiguous to me whether they mean exactly k or at least k. I'd interpret it as at least. They're both possible but that one's easier.

[floral merlin]

usually if the problem wanted to exclude strings with more than k 1s at the end, it would explicitly say ends in exactly k 1s

[next sail]

okay would u suggest i create dfa for k=1, k=2, and try to find a dfa pattern?

[floral merlin]

sure

[next sail]

im starting to notice a pattern among the transition functions

am i on the right track?

the accepted states would be Q subscript k

lemme sketch out the dfas for k=1 and k =2

[surreal musk]

hey guys in a few days I'm starting my discrete math course in uni but i still havent understood what its about

i have noticed it has some similar concepts with digital systems

[spark field]

Indeed

At least the beginning parts

In a general discrete math class you'll probably cover

• Logic (basically your boolean stuff from digital)
• Propositional/predicate logic (the mathematical stuff)
• What are sets
• Basics of proofwriting (in a mathematical sense)
• Working with sets (functions, relations)
  And possibly
• Discrete structures (graphs)

I'm probably forgetting a few things so someone can probably add more

[surreal musk]

thanks for the info!

[spark field]

No problem 🙂

[pallid plover]

moment when i saw this, RRT pop in my mind

A clear application of rational root theorem

unluckly i am not allowed to use rational root theorem so probably i will use some basic stuff.

op nvm, i thought i am in my thread (but none exists here) and start yapping

[little prism]

whats problem 17?

just do the same proof as RRT

its not like its a particularly challenging proof

[hybrid quiver]

Then why is it studied

[robust monolith]

Counting

[spark field]

Most mathematical fields have merit by themselves?

[spark field]

I would venture to say that a lot of mathematical study find its utility in its direct applications, rather than its usage in other fields of math

[daring gyro]

is this how your class normally writes FA? i've only ever seen them drawn as a digraph, and i'm a TA

it's right, but you're off by one. yours recognizes L_k+1

[pallid plover]

it is about kth root of a number x is irrational unless x=m^k for some integer m

[harsh kestrel]

hii, could someone explain to me wheter or not Its a good idea for me to take a discrete maths course, thank yoouu

[spark field]

What do you plan to do

[harsh kestrel]

right now im really unsure what even discrete is, well the only thing Ik about is its not consisted of infinite ammount of numbers, only a finite

[harsh kestrel]

recently i thought of becoming like a consultant, taking phone calls, working in an industry and basically using my maths skills to a solve perhaps clients problems or even firms

i heard it was called a management consultant, im not too sure

[spark field]

In general this is what you might see in a typical discrete class

You will work some with infinities in a typical discrete class

The main benefit would likely be the logic parts (develop logical and critical thinking skills) and possibly the proof part (develop abstract and mathematical thinking skills), and depending on what structures are covered maybe they pop up

I would say a project management course might go further for you though if that's the line of work you want to go into

Although personally I think everyone should take a discrete class, logic class and/or philosophy class that's more of a matter of personal opinion

Someone with more experience may be able to add on and provide a more measured opinion here

[harsh kestrel]

thanks for the advice

[thorn hemlock]

This should just be pinned honestly

[spark field]

<@&268886789983436800>

hacker.bot is a crazy username

[fathom verge]

hm

is there a difference between well ordering theorem and well ordering principle

also assuming that AOC is equivalent to well ordering theorem?

[fathom verge]

actually wait the zermelon fraenkel axiom of well ordering proves the well ordering theorem right

[grave hawk]

What do you mean by well-ordering principle

That the naturals are well ordered?

The well-ordering theorem is that any set can be well-ordered, even if they are very very large (like the reals)

And that's equivalent to the axiom of choice

[pallid plover]

i have a kind of basic question, but it seems confusing to me for real !!

when my sir was solving the inequality $|x-3|<4$ he said this implies $-4<x-3<4$ and then $-1<x<7$ cool enough

[vital dew]

Afzal mathcord #1 fan

[pallid plover]

but but, doesn't from $|x-3|<4$ we have two \textbf{cases}, $x-3<4$ or $x-3>-4$ thus $x<7$ or $x>-1$ thus the solution set must be $$(-\infty,7)\cup (-1,\infty)=\mathbb{R}$$

[vital dew]

Afzal mathcord #1 fan

[pallid plover]

but it isnt true whyyyy

altho for the other problem such as $|2x-1|\geq 4$ this argument works

[vital dew]

Afzal mathcord #1 fan

[pallid plover]

honestly idk if this question belongs here or in #proofs-and-logic or #calculus

[haughty garden]

you need to be careful about the domain. When x >= 3, then |x - 3| = x - 3 so, on the interval [3, inf), we have the case where x - 3 < 4 or equivalently x < 7. When x < 3, then |x - 3| = 3 - x so on the interval (-inf, 3), we have that 3 - x < 4 or equivalently x > -1

[pallid plover]

oh and $(-1,3)\cup [3,4)=(-1,4)$

[vital dew]

Afzal mathcord #1 fan

[pallid plover]

oh gosh this makes a lot of sense, i was so dumb

oh God

thank you so much opengangs

you saved my day fr

[haughty garden]

nws!

well actually it should be [3, 7) but yes you have the right idea

[pallid plover]

yes lol, I misinterpreted lol but i got the idea

[fathom verge]

so the well ordering theorem is generalized for any set

whereas the well ordering principle states that theres a least element for the naturals i think

[grave hawk]

yeah

it's a vast generalization, because it's easy to show for the naturals, but for larger sets it's not at all obvious

an OBSCENE generalization

[fathom verge]

got it thank you

[grave hawk]

all well ordered sets are either finite

or a bunch of N's pasted one after the other

(possibly with a finite segment at the end)

[spark field]

or infinite

[fathom verge]

only if you were to combine googology and category theory (crazy combo)

georg cantor would literally define every countable number possible

[fossil mural]

i would also note that the well-ordering theorem doesn't actually immediately imply the well-ordering principle

the well-ordering theorem, applied to the set N, just tells you that there is some well-ordering on N

the well-ordering principle is the stronger statement that the particular order < is a well-ordering of N

[grave hawk]

that's true

[keen flower]

can someone help me with this? i dont understand it at all

[spark field]

Do you know the meaning of the quantifiers

We can go through it step by step here

[keen flower]

can you explain it?

im on step 3

but i wanna learn it fresh

[spark field]

Sure

Essentially, quantifiers allow us to talk about how a proposition acts when we consider a specific set of elements (called the universe)

We have two quantifiers, $\forall$ and $\exists$

[vital dew]

Coolempire93

[keen flower]

righ

[spark field]

Starting with the first one

$\forall x, P(x)$ means that $P(x)$ is true for every element (we call $x$) in the universe

[vital dew]

Coolempire93

[spark field]

How do we verify it?

Normally, we look at every element in the universe, and check that it is true for every single one of them

[keen flower]

lol

method of exhaustion?

[spark field]

Typically, yeah (but that won't work here, we'll talk about what we go to when we can't do exhaustion)

[spark field]

If we come across any element $y$ that makes $P(y)$ false, then we say the proposition $\forall x P(x)$ is false, and we call $y$ a counterexample

[vital dew]

Coolempire93

[spark field]

Let's try 1. from your paper as an example

[keen flower]

ahh right

[spark field]

Using the universe ${1,2,3}$

[vital dew]

Coolempire93

[spark field]

Let's check if $\forall y, P(0,y)$

[vital dew]

Coolempire93

[spark field]

To do so like we said we turn to the method of exhaustion:

When y = 1:
P(0,1) says 1 - 0 = 1 + 0^2
i.e. 1 = 1, true

When y = 2:
P(0,2) says 2 - 0 = 2 + 0^2
i.e. 2 = 2, true

When y = 3:
P(0,3) says 3 - 0 = 3 + 0^2
i.e. 3 = 3

true

So P(0,y) holds for all y in our universe

That means that $\forall y, P(0,y)$ is true for that smaller universe

[vital dew]

Coolempire93

[spark field]

Do you follow how I did that part

[keen flower]

yes

[spark field]

Okay great 👍

Now let's consider, they asked us about $\ZZ$, which has infinitely many elements

[vital dew]

Coolempire93

[spark field]

We can't use exhaustion

Instead, we use what we know about $\ZZ$

[vital dew]

Coolempire93

[spark field]

Which is that $x + 0 = x$ and $0^2 = 0$

[vital dew]

Coolempire93

[spare slate]

hi

[spark field]

For any integer y, then
P(0,y) says y - 0 = y + 0^2
i.e. y = y
Which is always true

[keen flower]

right

thats what i got

[spark field]

Good 👍

[spark field]

Hiiii 💃

[spark field]

do you wanna take over I'm gonna have to go tutor someone in person in about 10 minutes

[spark field]

good negation

Mmm, now let's think about exists

[keen flower]

2 or 3

[spark field]

2

[keen flower]

ok

[spark field]

$\exists x$ s.t. $P(x)$ means that there is an element $x$ in the universe such that $P(x)$ is true

[vital dew]

Coolempire93

[spark field]

We call $x$ a witness

[vital dew]

Coolempire93

[spark field]

All we need to find is a single element x such that P(x) is true
(Just like how we only need to find a single element x such that P(x) is false to negate the forall)

For a small set, you may end up exhausting the whole set before you find an element that works

But again, since $\ZZ$ is infinite, we need to think a little harder

[vital dew]

Coolempire93

[keen flower]

cant we just do what we did for step 1 for step 2

plug in 1

for x

[spark field]

In this case, we can show that it's impossible by plugging in 1, exactly

[keen flower]

so i have it right?

[spark field]

$P(1,y)$ says $y - 1 = y + 1^2$, i.e. $0 = 2$, which is impossible

[vital dew]

Coolempire93

[spark field]

So what we have proven is $\forall y, \mathord{\sim} P(1,y)$

oh oldneg isn't in here

[vital dew]

Coolempire93

[spark field]

Which is the negation of 2

i.e. 2 is false, its negation is true

so very good

just remember that ``$\forall$ s.t." doesn't exist

[vital dew]

Coolempire93

[keen flower]

im having trouble with the 3rd one

ohhh

[spark field]

Yes, now we have to talk about nested quantifiers

Nested quantifiers work like so:
First you choose an element for the outer quantifier, then you read the inner quantifier

How does that look?

$\forall x, \exists y$ s.t. $P(x,y)$

[vital dew]

Coolempire93

[spark field]

Would mean

[keen flower]

For all x, there exists y s.t p(x,y)

[spark field]

choose an x

Now there must exist a y such that P(x,y)

[keen flower]

yeah

[spark field]

So the way to verify would be

[keen flower]

negate it first?

[spark field]

choose x

Find a y such that P(x,y)

If you can choose any x for which you can't find a y, you have a counterexample

[spark field]

Yeah, basically we're looking for if we can come up with a counterexample

[keen flower]

ok im confused

[spark field]

i.e. proving the negation is true

[keen flower]

so do i just plug in random number?

[spark field]

You have to be smart about it, but that's basically the process

For a general proposition

But p gives us something to work with

Once again, we know about how $\ZZ$ works

[vital dew]

Coolempire93

[spark field]

Let's simplify $P(x,y)$

[vital dew]

Coolempire93

[spark field]

$P(x,y)$ says $y - x = y + x^2$

[vital dew]

Coolempire93

[spark field]

We can cancel out the y's on both sides

That is, we get the equation $-x = x^2$

[vital dew]

Coolempire93

[spark field]

So if we can find any x such that -x does not = x^2, there cannot exist a value of y such that P(x,y)

Let's do an example so you see what I mean

Try $x = 1$

[vital dew]

Coolempire93

[spark field]

$-1 \neq 1^2$

[vital dew]

Coolempire93

[spark field]

So $P(1,y)$ is false, no matter what $y$ you put in

[vital dew]

Coolempire93

[spark field]

That is a counterexample

Because the proposition says that for all x, I can find a y such that P(x,y)

And I have an x such that there are no y such that P(x,y)

I have to run for about an hour but see if you can understand what I just did there

If not I can explain it more when I get back or someone else will pick it up

[keen flower]

can i add you?

[spark field]

Yeah 👍

[keen flower]

thanks!

[spark field]

No problem

[keen flower]

how would i draw the diagram

Like so?

i dont think anyones up rn :/

[stoic heart]

healthy dogs inside four-legs circle, lucky is outside both, and it's modus tollens

[keen flower]

how do i differentiate the different errors?

im having hard time with all the different kinds of errors

[stoic heart]

basically check if they're negating the condition or the result, that's the trick

[stoic heart]

inverse error negates the start, converse error just swaps the two parts

[keen flower]

can u elaborate please

[stoic heart]

converse is flipping P -> Q to Q -> P, inverse is just ~P -> ~Q

[keen flower]

Ahh

[daring shore]

Hey! If possible could I get an explanation on this set? I’m not entirely sure what would be included or how they would be included if I listed off the answers that fulfill the right part. Thanks!

[spark field]

Essentially you have a set of numbers represented by $\frac{p}{q}$, where $p$ and $q$ are integers, and $q$ is not 0

So examples would be $\frac{1}{1}, \frac{-1}{2}, \frac{2}{2}, \frac{3}{2}, \frac{1}{3}, \frac{2}{-3}, ...$ and so on

[vital dew]

Coolempire93

[spark field]

We interpret the fraction with our standard interpretation of division, so for example $\frac{1}{1} = 1 = \frac{2}{2}$, and $\frac{-1}{2} = -\frac{1}{2} = \frac{1}{-2}$

[vital dew]

Coolempire93

[spark field]

(so if you were writing out all the elements included in the set you wouldn't duplicate numbers that have the same value)

Your intuitive understanding might just be that this is the set of fractions

both positive and negative, and including whole numbers, both negative and positive (i.e. integers)

[daring shore]

I understand this part. Just to add context this is a much higher level of maths than I’m used to. But the way that I understood it, was as long as it wasn’t divided by 0 it’s fine

[spark field]

yep, since we can't divide by 0

[daring shore]

So as long as it’s not duplicate, anything can go as long as it’s not divided by 0?

[spark field]

Yep

As long as you can write it as a division of two integers

[daring shore]

And it has to spit out a whole number right?

[spark field]

Most fractions aren't whole, for example $\frac{1}{2}$

[vital dew]

Coolempire93

[spark field]

But since I can write it as a whole over a (nonzero) whole, it's still in our set

[daring shore]

Oh okay I think I get it

Yea ok that makes a bit more sense actually. Sorry tbh I never passed standard math so this is all new to me haha thanks for helping!

[spark field]

No problem! That's what we're here for

[daring shore]

It’s all stuff that I’m learning in my uni class at the moment, but is there some other kind of book or something that’s recommended for discrete maths? Something that’s like not overly complicated

[spark field]

There are a lot of discrete math books, I'm not sure which might be best for entry level

[daring shore]

I gotta do some research for it then haha. Thanks!

[spark field]

No problem, #book-recommendations may be able to help as wel

Maybe they can find one that assumes a less mathematical perspective/background

[daring shore]

Easy I’ll take a peek over there

[rugged sky]

Can somebody help me to solve the following problem: Claudia wants to use 8 indistinguishable red beads and 32 indistinguishable blue beads to make a necklace such that there are at least 2 blue beads between any 2 red beads. In how many wayscan she do this?

[vestal bronze]

that's kinda hard

[modern night]

have you tried "stars and bars"?

[rugged sky]

I have. Here my explanation: Well, we have 8 gaps to place 2 blue beads. Because the necklace is circular, and using stars and bars, we can say that 2 × 8 = 16 beads are evenly placed in every gap (since there must be at least 2 in each gap). So the problem really is to figure out how many different possibilities there are to choose the set of bars from n + k - 1, where n is the number of stars and k - 1 is the number of bars. Here, n = 32 - 16 = 16, and thus n + k - 1 = 16 + 8 - 1 = 23, and logically k - 1 = 7. Therefore, we have 23 choose 7.

[rugged sky]

.

[modern night]

yes, looks good to me. with the 8 bars of the form "red blue blue", place the stars (the remaining blue beads) at random.

[vestal bronze]

it's necklace, there's left-right symmetry, and likely rotational symmetry too

so like these 3 are the same necklace

i basically can't solve it

I guess I can solve left-right and rotational cases separately

[spare slate]

burnsides bash ig

[vestal bronze]

that's the cheating method

[rugged sky]

Ok

[hidden totem]

doing the cases individually is not that bad

as long as the heavy case you do last, because complementary counting makes it much simpler

[vestal bronze]

nah I gave up

[shrewd mauve]

New to this server lol

[ancient thicket]

Epp, S. S. (2011). Discrete mathematics with applications (5th ed.). Brooks/Cole.
I found this interesting, and I'm sharing it here.

[flat eagle]

math history is always interesting to read about

[leaden portal]

Not sure if this is the right channel for this, but I’m currently studying billiards, in particular periodic billiard paths.

Right now I’m working on the case of outer billiards on a square table. Here a ‘reflection’ happens through the vertices of the square, in particular the one you first meet by clockwise rotation , starting by facing away from the square. See the attached image for an example.

I know for certain that every single path is periodic. In particular, I can state with confidence that the period is 4(|m|+|n|), where (m,n) are the coordinates of the lettice square. However I’ve been pondering on a formal proof of this for hours now. Could someone please help me with this?

[spark field]

Yeah either here or maybe xpost to #combinatorial-structures

Hopefully someoneis able to help

[vital dew]

AwaknThundr

AwaknThundr

AwaknThundr

[leaden portal]

Could someone check this proof for any mistakes?

[night drift]

Ok I believe I get relations but does anyone know if something being related to something only applies to the elements in the set or also the set itself and how the Cartesian product fits in the picture?

[spark field]

Yes, if a relation is on a set, then you can only talk about elements being "related" in reference to those in the set

The cartesian product fits into the picture because

The cartesian product $A \times A$ is set of all possible ordered pairs of elements in $A$

So, if we write a relation as a set of ordered pairs of elements in $A$, it would have to be a subset of $A \times A$

[vital dew]

Coolempire93

[spark field]

Essentially, if $R$ is a defined relation, we might write $R = {(x,y) \in A \times A : xRy}$

[vital dew]

Coolempire93

[spark field]

And we see all of the elements in R are ordered pairs of elements in A, and thus in the cartesian product AxA

[night drift]

But like in terminology you can’t say that like “A R B”

Only like “a R b”

[spark field]

If you have a set of sets you could (i.e., now our elements are sets)

Remember that elements are arbitrary, they can be anything

[night drift]

Ahh gotcha

[spark field]

For example, $A\mathcal{R}B$ iff $A \subseteq B$ is a relation

[vital dew]

Coolempire93

[spark field]

With $\mathcal{R} \subseteq \mathcal{P}(S) \times \mathcal{P}(S)$

where P is the powerset

And S is some set

This relation is the common partial order of inclusion on sets

[spare slate]

hi

[spark field]

CSP 💃

[night drift]

Is the relation here being subsets? Hope I’m not confusing it

[spark field]

Yes 👍

[vital dew]

Coolempire93

[spark field]

Forgot the cartesian product

\hsize=50pt
So for example if $S = {1,2,3}$, then for $A = {1} \subseteq B = {1,2}$, we have $A \mathcal{R} B$

useless thing why not put it all on one line

[vital dew]

Coolempire93

[spark field]

ig it just wants to be useless

[night drift]

lol

So if they define a relation can you like determine if sets and A and B are related by whether or not there exists a pair in the relation R that doesn’t exist in A x B ? Or can you only determine what the relation set is from the product?

[spark field]

If you have a defined relation, say on S with A,B in S

A and B are related iff the (A,B) is in R

(A,B) will always be in SxS because that's the set of all ordered pairs of elements in S

So SxS tells you nothing about a relation on S
And R tells you nothing about SxS

[night drift]

Hmm I think that makes sense I just gotta reread that

Wait the second line are they related if there is at least one ordered pair from SxS in R?

[spark field]

which second line

are who related

[night drift]

Uh this one “A and B are related iff the (A,B) is in R”

[spark field]

That's the definition of a relation

[night drift]

Sorry A and B

[spark field]

If there is at least one ordered pair from SxS in R that means that some element is related to itself/another

We don't know anything about that element

[night drift]

OK, but if we know that can we say that sets A and B are related or that there exists some relation between the sets?

[spark field]

Not necessarily

What if $R = {(C,D)}$

[vital dew]

Coolempire93

[spark field]

A and B are unrelated, even though R is nonempty

[night drift]

So when there isn’t a subset of a SxS that has at least one pair in the relation R defined we say the sets are unrelated? Or is that kind of wording reserved for elements only?

[night drift]

Sorry I might not respond later it’s late where I am

[spark field]

No problem, it's also late where I am 😆 so I'll sleep at some point

oh good c squared is here

Maybe they can explain in a more clear manner

[night drift]

Sorry guys I promise it’s not you I’m just slow on the uptake

[cerulean wind]

to reiterate, for a relation R on a set A, we only relate elements of A.

[cerulean wind]

i think you did great!

there is a more general notion of a relation between two sets X and Y: a relation from X to Y is just a subset R of X x Y. you could write X R Y to say that R is a relation from X to Y, but keep in mind, this is just an abbreviation for R subseteq X x Y. i don't think this is standard notation, though.

[ivory patio]

Hi what's up?
Could anyone help me with understanding/directing me to a proof online
Why is it that the coefficients of the discrete fourier transform have this identity:

$ \sum^{N-1}_{x,y=0 } e^{\frac{-2\pi i (uy}{N} = N if u = 0 and otherwise 0 $

[grand crown]

$\sum^{N-1}_{x,y=0 } e^{\frac{-2\pi i (uy}{N} = N$ if u = 0 and otherwise 0

[vital dew]

snowflake
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[grand crown]

some of the constants seem mismatched, what's x,y,u?

are you doing a 2D transform

[harsh hamlet]

yall which sources are best to learn generating fucntions for competetive programming

[trim thicket]

im not sure if this is the right place to ask this but

if minterm is something like
F=sum m (0)
then
F = product M(1)
F' = sum m (1)
F' = product M(0)
?

[normal river]

Guys why is the yellow group an essential prime implicant

[grand crown]

it's a prime implicant because it can't be expanded in any direction to give a valid implicant

it's an essential prime implicant because it can't be covered by other prime implicants

if there was a 1 in cell 6 for instance, it wouldn't be an essential prime implicant, because
6-14 and 31-30 would cover it

[normal river]

Minterm 14 Can be covered by the yellow group $(14, 30)$, but it can also be covered by grouping $(12, 14)$
Minterm 30: Can be covered by the yellow group $(14, 30)$, but it can also be covered by grouping $(30, 31)$,. Now as both minterm 14 and minterm 30 have alternative valid prime implicants that can cover them, how is the yellow group an EPI?

[grand crown]

hm yeah you're right

[vital dew]

Sean [Ping On Reply Please!]

[normal river]

but the quine mccluskey solver is showing it as an epi

https://geeekyboy.github.io/Quine-McCluskey-Solver/

if it is using the correct algorithm then it shouldnt output wrong results

[grand crown]

is this the same prime implicant chart that it gave you

[grand crown]

i think the issue is with how the algorithm is interpreting the results

a prime implicant is essential if and only if it covers a 1 cell that no other prime implicant covers

over the course of the algorithm, rows get removed due to row and column dominance, so you can't determine if a prime implicant is essential just from the output

you have to check the prime implicant table and check which columns only have 1 X

https://en.wikipedia.org/wiki/Quine–McCluskey_algorithm#Finding_the_essential_prime_implicants

like if you read this, all the algorithm does is make the prime implicant table, and then you just identify the columns that only have 1 X in them

the prime implicants that correspond to those columns will be essential prime implicants

any further reduction steps are just to obtain some final covering, but the terms you add aren't going to be essential prime implicants

[charred tapir]

Is discrete math about discrete functions

[flat eagle]

about any discrete (rather than continuous) thing. i.e. graphs, logic, number theory, etc

[glass leaf]

also combinatorics

and discrete probability

[flat eagle]

falls under my beautiful etc

[glass leaf]

it was more so for OP

[glass leaf]

but yeah, discrete functions are also part of it

[charred tapir]

im actually freshmen but im good at calculus sooo pls dont sue me

[glass leaf]

ok?

[charred tapir]

freashmen like in highschool

[charred tapir]

thats not ok. my math teacher said i should go to a sanitoruim and stay there

[glass leaf]

ok

[charred tapir]

That's not OK I swear

[narrow agate]

Can anyone explain how the 3rd statement here is True?

[vestal bronze]

that's what necessary means

sufficient is the opposite direction