discrete-math

[warm coral]

and then prove that

[vocal forum]

can someone help me out with an induction question?
http://prntscr.com/qvbn7j

my base case is different regardless of the nth term

left side at n=1 is equal to 4
right side at n=1 is equal to 1

i'm not sure how to proceed, if I messed up in an earlier answer then i could use an assist 😛

i think I caught one of my mistakes, the answer to (i) should actually be 3n-2 not 1+3n because the question specifies n > 0 and 1+3n doesnt work unless i is equal to 0

so I guess my question is now how to answer (iii) now

[solid ice]

An assignment says that this language is not regular (does not have a finite automaton that recognizes it). But I don't think so? I think it's regular.

$\left{w t w | w, t \in{a, b}^{*}\right}$

[vital dew]

Icohedron:

[obtuse lance]

well if you think it's regular, create the finite automaton

[solid ice]

It's the finite automaton that accepts all strings

Since w can take on the value of anything in {a,b}* it can be an empty string. If w is the empty string then the language becomes the set of all strings.

But the assignment asks me to prove that this language is not regular

.<

[obtuse lance]

they probably meant to add a caveat that w is specifically some given nonempty word

don't get too distracted by a corner case

[solid ice]

I asked a TA via email about this and they replied "Think about the cardinality of the empty set."

Which doesn't seem to clarify anything

[obtuse lance]

I wouldn't worry about it

try to create the finite automaton for when w is just a

[solid ice]

that's just any string that starts and ends with a

[obtuse lance]

so should be easy then

do it

write down the states and transitions

[solid ice]

I prefer drawing my finite automata

[obtuse lance]

that's what I'm saying, draw it

[solid ice]

NFA version

[obtuse lance]

seems fine to me

[solid ice]

But if w in {a,b}* except the empty string then the language isn't regular

[obtuse lance]

the problem is w is just an arbitrary word it can be the empty string

when it's an empty string it's not an entirely separate language

w is not fixed

sure, you can make a FSA for part of your language for any fixed w

you can do it for an empty string, you just did it for w=a

you can do it for any specific given w

but not all w simultaneously

w is just as arbitrary as t here

[solid ice]

hmm

[obtuse lance]

there's no reason to fix just that word

the opposite would be like if you were to fix t and look for all possible w

no reason to do that either

idk why you're fixating on w here when it's on equal footing as t, hopefully that's clear what I mean

the problem is the FSA has no kind of "memory" so trying to repeat the w after t is not really possible in general like this

[solid ice]

Well it's just that the way the language is defined implies that it's the set of all strings. Since any string is in the language since w can be made empty. That's all.

[obtuse lance]

ahh shit

you're right

haha alright I'm totally blind I see what you mean, I guess the problem was meant to be w, t in {a,b}+

[solid ice]

In class we never defined +

Haha

[obtuse lance]

just means {a,b}* but you have at least one

[solid ice]

Yea

[obtuse lance]

at least, that would make your TA's remark make sense

well, maybe, I don't know

[analog dagger]

thats neat

[vital dew]

Vincent:

[regal merlin]

is this approach correct?

[vital dew]

Vincent:

[stray reef]

Arrangement: 5!
mind elaborating?

[lyric pumice]

Assuming that the boys and girls are all distinguishable, if the order of the boy-girl pairings is taken into account, then the number of arrangements is 460800, and if the order of the boy-girl pairings is not taken into account, then the number of arrangements is 92160.

[hybrid plume]

can someone please explain to me what is the difference between the two ?

[faint narwhal]

These are isomorphic groups

So usually we would say that there is no difference

[hybrid plume]

it s just the syntax that is different then ?

[faint narwhal]

yeah

There's a difference, but i don't think its really that important

[hybrid plume]

thanks a lot for the quick answer

[regal merlin]

@stray reef Since we have 5 sides and rotation doesnt matter. I guess it's 4! instead? Also should it be multiplied by 2! to arrange the boy/girl pair on each side of a table?

[stray reef]

should be multiplied by 2^5

once for each side

4! * 5! * 2^5 should be the final answer

[regal merlin]

Ah right

Thank you 🙂

[hybrid plume]

i still don't get the difference between the two in group theorie

does anyone have an idea ?

[pale epoch]

just notation

the dot is used as the group operation

but often you dont write it, because writing things sucks

[stray reef]

you know how in algebra you write $2x$ for "2 multiplied by $x$"?

[vital dew]

Ann:

[stray reef]

instead of $2 \cdot x$

[vital dew]

Ann:

[hybrid plume]

ok cool i thought it meant a cartesian product the first one

but without the x

[stray reef]

it's the same kind of shorthand here. makes things a lot more compact.

[hybrid plume]

i see thanks

[hybrid plume]

is there only one number is this group that has this property or there is many but we choose the one that has the smallest k?

[stray reef]

what

[hybrid plume]

this is called a group generator right?

[stray reef]

no

what you've sent here is the definition of the order of a group element

[hybrid plume]

ok one sec i ll send u smth

this means (i m translating) if <a> = G then this ord(a) is a group generator

my uni stuff are in german sorry

so i ll translate

"Erzeuger" means generator or creator

does anyone have a good resource for orders and so on ?

[pale epoch]

erzeuger is generator

also no, the order is not a group generator

the order is the smallest natural number k, such that a^k is the identity

every element has a order

[hybrid plume]

but a is ?

oh

[pale epoch]

a is any group element

now if there is an a in G such that <a> = {a^k | k in N} is the whole group G, then we call a a generator of the group

that means that you can write any element of the group as a^k for some k in N

[hybrid plume]

do you have an example ?

[pale epoch]

what groups do you know

[hybrid plume]

i find this very abstract

let s say this one

[pale epoch]

i mean, this is still very abstract

Z with addition is a group

it is generated by 1

because you can write any integer as k*1 for some k

[hybrid plume]

i see

do u have some resources about this in german btw ?

[pale epoch]

a textbook?

[hybrid plume]

anything really on the internet

[pale epoch]

i used "Algebra" by Karpfinger and Meyberg a bit

[hybrid plume]

nice thanks i ll take a look at it

[pale epoch]

i have some lecture notes from my uni

i.e. my prof wrote basically a book for my algebra class

not sure if im allowed to share though

[hybrid plume]

i won t be sending it to anyone i just need to understand this topic

[pale epoch]

but it used karpfinger, meyberg as a resource for almost everything

[hybrid plume]

ok

[regal yew]

I'm so lost

I don't understand induction

[stray reef]

which of these seven problems is giving you trouble?

[regal yew]

well, all of them, but specifically f

this is what i have so far but it could be way off

[stray reef]

have you verified the statement for n = 1 through 4 as instructed?

[regal yew]

wait, what did i fuck up

n=2 gives 1/6=2/3

[stray reef]

does it?

what's $\sum_{i=1}^2 \frac{1}{i(i+1)}$ written out as an actual sum?

[vital dew]

Ann:

[regal yew]

oof, yeah, big brain fart

sorry ive been banging my head at this stuff for a few hours now

okay, i verified the statement

[stray reef]

and now you're at the inductive step. yes?

[regal yew]

correct

[stray reef]

well, you've expressed the sum to m as the sum to m-1 plus the last term

[regal yew]

yeah, I don't understand the next step. suddenly the book sorta makes a leap in logic and I'm not following

[stray reef]

can you show what the book says?

[regal yew]

Where did we get the 2 to divide?

i need sleep

fuck me

[stray reef]

we assume that the formula is true for all numbers below m

we use that to prove that the formula is true for m too.

this is kind of the whole point of induction.

i can try to explain this with a metaphor if that'd help

[regal yew]

yeah theres something i'm not grasping conceptually.

i'm not grasping how to go from (in that example) an equation with + ... + to a proper formula getting rid of all those inbetween numbers

[stray reef]

imagine an infinite ladder

and imagine that you wanted to prove that you could climb it

a proof by induction consists of proving two things:

• you can climb the first rung
• If you've climbed all the way up to some rung, you can climb up to that rung too

[regal yew]

okay, I grasp that

but then just algebraically, where does that divisor (2) come from?

[stray reef]

you're just applying the formula for n=m-1

nothing more

[stray reef]

line 4 is wrong.

you didn't apply the formula properly.

it should have been $\frac{m-1}{(m-1)+1}$, not $\frac{m(m-1)+1}{m(m-1)}$.

[vital dew]

Ann:

[regal yew]

wait so you actually literally just plug in m-1, not what I have where m-1 is (in step 3)

i'm sorry dude, it takes things too long to click for me sometimes

thank you so much for the help btw

[stray reef]

you're welcome

i'd prefer if you didn't call me dude tho

[regal yew]

alright, my bad! i use it as a gender neutral term but absolutely no problem, wont happen again (:

[stray reef]

also don't worry about induction taking a while to click

it requires a bit of a viewpoint shift

so just about everyone goes through a phase of not getting it

[regal yew]

this whole class does

holy

learning about the pigeon hole problem changes my view on so much

[stray reef]

as did i, several years ago

[regal yew]

so is this correct? skipping a few algebra steps but other than that ^^

[stray reef]

fourth line is wrong. you fucked up your algebra. also, line 1 sound not be there. unless you prefix it with a "To be proved:" or equivalent.

[regal yew]

gotcha, alright thank you

i need to take a break from discrete math, off to calc whee lol

[regal yew]

aight i'm struggling again

trying to find a recursive relation

$a(n) = 2(3^0 + 3^1 + 3^2 + ... + 3^{n-1})$

[vital dew]

Star:

[loud basalt]

well

i mean

in trinary

[regal yew]

i see the pattern

but

idk how to get a recursive function out of that

[loud basalt]

hmm

[stray reef]

consider $a(n+1)$

[vital dew]

Ann:

[regal yew]

$a(n+1) = a(n) + 2 * 3^n$?

[vital dew]

Star:

[regal yew]

but dont i have to figure out a(n-1)?

[pale epoch]

you just did

[regal yew]

just $a(n-1) = a(n) - 2*3^n$?

[vital dew]

Star:

[pale epoch]

how did you come to that conclusion

[regal yew]

inverted my a(n+1)

oh.

[pale epoch]

oh?

[regal yew]

$a(n) = a(n-1) + 2*3^{n-1}, a(1) = 2$

[vital dew]

Star:

[regal yew]

i got it (:

[pale epoch]

looks good

[regal yew]

is this at all on the right track?

yeeeee okay

[regal yew]

that homework was awful

holy

9 hours T.T

[hybrid plume]

does anyone have an idea how could i find all isomorphs to this graph using these two permutations?

[pale epoch]

what? do you want to find all isomorphisms of this graph or figure out if those permutations are isomorphisms?

[hybrid plume]

we need to find all automorphisms?

using both permutations

[pale epoch]

just apply the permutation and check if the resulting graph is isomorphic then?

[hybrid plume]

no that will be only two examples

i need to find all the possiblities

that s the point of the exercise

[pale epoch]

then what does "using both permutations" mean?

i mean, you can compose them

then do that, and check if it's an automorphism

[hybrid plume]

yes it will stay a automoph to the graph g

using both permutations means it doesn t matter if i use one of them or not

the whole point is to generate as much autmorphisms as possible

[pale epoch]

you can also just write down all automorphisms of your graph

and then check which can be written as a composition of your given permutations

[hybrid plume]

yeah i ve just found the answer

[hybrid plume]

can someone tell me why does this makes sense ?

[analog sonnet]

no, I think that minus sign has to be some sort of typo

[hybrid plume]

no it s not

:/

[analog sonnet]

So if k = l = 1, you're telling me that a^(-1) = a for any a in G?

[hybrid plume]

only if it s a group generator

a is a group generator

can u read german ?

[analog sonnet]

I can read German

But the statement specifies a to be any element in G, not just a generator

[ivory badge]

a^-1 doesn’t have to equal a, even from ur generators anyway

[hybrid plume]

i ll sen d the whole page

[ivory badge]

für all a€G
This doesn’t look like a generator to me

Look like just some arbitrary element

[hybrid plume]

no a is specified above

it got me really confused

because that doesn t make any sense

[ivory badge]

It says for all a in G

They just use a as elements

[pale epoch]

it's just a typo

[ivory badge]

^

[pale epoch]

even if its a generator

[analog sonnet]

They reused the name a

[pale epoch]

Z is generated by 1 and 1 =/= -1

[hybrid plume]

yeah i thought it was a typo then i dismissed the idea because my friedn had anoher version of the pdf

and it has -l too

[pale epoch]

it's supposed to be (a^k)^l = a^(kl) = (a^l)^k

[hybrid plume]

yeah i think so too

[analog sonnet]

Ask lecturer

[ivory badge]

People reuse symbols, also it’s a typo that wasn’t corrected

[hybrid plume]

thank you

i ll ask for it

[pale epoch]

honestly

on this whole page a is always an arbitrary element of a group

and never specified to be a generator

[analog sonnet]

There's only a condition specified as to when a can be called a generator

[pale epoch]

yes

if a happens to generate the group, it's called a generator

who would've thought

[analog sonnet]

I would've thought

[pale epoch]

that's a smart thought

[analog sonnet]

Funny thing is that I followed an algebra course in German

Because it wasn't taught in English

And I needed to pass it to graduate

[hybrid plume]

nice

i m having diskrete strukturen atm

[pale epoch]

also i might add that your prof uses bad notation

[hybrid plume]

which notation exactly

?

[pale epoch]

he uses <> both to specify a group and a generated set

also $\emptyset$ instead of $\varnothing$

[vital dew]

Lochverstärker:

[hybrid plume]

i see

[pale epoch]

just an opinion, don't take it seriously

[ivory badge]

Smh complaining about choice of $\not 0$

[vital dew]

Darkrifts:

[hybrid plume]

there is a lot of germans here btw

[analog sonnet]

tfw lecturer doesn't use ( instead of $\langle$

[vital dew]

Rijinaru:

[pale epoch]

varnothing is objectively better looking

[analog sonnet]

I agree with that objective statement

[pale epoch]

i also dislike the mathbb for groups

[analog sonnet]

Me too

[hybrid plume]

what is the dollar sign thing u keep adding ?

[analog sonnet]

@pale epoch are you $\phi$ gang or $\varphi$ gang?

[vital dew]

Rijinaru:

[pale epoch]

it's latex

i use both, but varphi more commonly

[hybrid plume]

$\varphi$

[vital dew]

Kasadraf:

[analog sonnet]

Also I think it's common knowledge that $\varepsilon$ is better than $\epsilon$

[vital dew]

Rijinaru:

[hybrid plume]

i m learning latex

nice

[pale epoch]

also the pic you sent has bad definition symbol i think

it's := instead of coloneqq

:= is not symmetric

$\coloneqq :=$

[analog sonnet]

$\LaTeX$

[vital dew]

Rijinaru:

Lochverstärker:

[analog sonnet]

tf

I never noticed that

[ivory badge]

Lmao

[pale epoch]

you now have to use coloneqq always

[analog sonnet]

I always used := instead of \coloneqq

damn it

[pale epoch]

once you notice it, you see it everywhere

[analog sonnet]

I wouldn't have noticed it if you didn't bring it up

[pale epoch]

everyone uses bad latex

[analog sonnet]

Now I'll have to use coloneqq everywhere which is much more typing than :=

Curse you Loch

Curse you!!!!

[pale epoch]

i guess you can macro it

somehow

[ivory badge]

Just make new command for \ceq or smth

[analog sonnet]

do you pronounce \ceq as "sek" or

[ivory badge]

yes

[hybrid plume]

is it me or group theory is a pain in the ass

like what the hell is the use of a group exponent

???

[pale epoch]

it's just you

[faint narwhal]

What exactly do you mean by group exponent

[hybrid plume]

v

https://de.wikipedia.org/wiki/Gruppenexponent

this

[faint narwhal]

It's an important thing structurally

Torsion groups have very different structure than non torsion groups

And very different properties

[hybrid plume]

so it describes the structure of the group ?

like what is the exponent here ?

[pale epoch]

so of the symmetric group on {1, 2, .., n}?

[hybrid plume]

yes

S(n)

i found it it´s kgV([n])

$\kgV([n])$

[vital dew]

Kasadraf:
Compile Error! Click the reaction for details. (You may edit your message)

[hybrid plume]

it s missing kleinste gemeinsame Teiler

[stray reef]

lowest common multiple?

[pale epoch]

yeah, kgv is lcm (lowest common multiple)

[tired axle]

@weary tiger Open problems or general algorithms that I can apply

Would anyone have a discrete math textbook around uni level

[weary tiger]

How to prove it

highly recommended

@tired axle

[faint narwhal]

That's a nice book, but not exactly what I'd call discrete math

The book by Rosen is nice

[weary tiger]

yeah it's just about proofs

but I'd start there first

then move on to topics like graph theory, number theory

diestel's graph theory

david burton's number theory

[faint narwhal]

Yeah but if he's doing like cs or something, he won't really need all the proofs stuff, outside of what's in a standard discrete math book

[weary tiger]

very beginner friendly

ofc you won't be using 100% of the stuff taught in how to prove it, but the mathematical maturity and reasoning gained would be very useful when learning other math topics

I've tried rosen too

but anyway this is what worked for me

[sleek swallow]

Logic and Discrete Mathematics by Goranko & Conradie is nice

[weary tiger]

but grinding through how to prove it has made me a lot better i believe, i can feel the difference

[tired axle]

im already pretty confident with graph theory

Im looking for stuff beyond/more applications

[faint narwhal]

Well, what exactly are you looking for then

More graph theory things? Other discrete math things?

[weary tiger]

idk about applications, but a bit harder book related to discrete math would be knuth's concrete mathematics

[weary tiger]

Anyone got an resource where I can read up on that symbol? Couldn't find in my discrete-book and my latex/google is bad 😦

Hmmmm could it be that i'm from the intrawebz and understand != and not that one ...

[cerulean sentinel]

I'm having a brain fart again, why is this true?

(start of proof of inclusion-exclusion)

[pale epoch]

what is this notation

[cerulean sentinel]

complement to universe U

[pale epoch]

the bar on the latter with the upside down omega

ok

i mean if you want to count all the elements in the LHS, you can count all of them that are also in A_n

and add them to all of them that are also in A_n complement

|A| = |A intersect B| + |A intersect B complement|

[cerulean sentinel]

I get that the intersection of those is the empty set

but, still loading on how/why we add A_n this way

[pale epoch]

so you see why it's correct but not why it is done?

[cerulean sentinel]

not sure about how it's correct

[pale epoch]

it's just $A = (A \cap B) \cup (A \cap B^c)$

[vital dew]

Lochverstärker:

[pale epoch]

and the fact that $A\cap B$ and $A \cap B^c$ are disjoint

[vital dew]

Lochverstärker:

[pale epoch]

as to why it's done, you would have to look at the rest of the proof, i guess

[cerulean sentinel]

oky, thanks

[dry patrol]

Hey guys, I am stuck on a question in one of my hwk exercises (for practice) and I need a bit of guidance im not particularly great at discrete math but I want to do well this semester. Is there anyone willing to help on a call?

[cobalt shell]

what sort of topic within discrete?

[dry patrol]

The theme of this is proving a theorem by strong induction, its a structural induction question.

Pretty much, it's taking the idea of a binary number and giving it functions which define it

so a bit of background info on it

[cobalt shell]

hmm, can't say ill be the most helpful there, sorry 😭

[dry patrol]

I dont wanna spam the chat but if someone can help me out that would be great

[cobalt shell]

[dry patrol]

Thanks for replying Zac I appreciate it

should I send screenshots of the hwk q

[cobalt shell]

would be better!

[dry patrol]

a lil long but its quite straightforward

any luck @cobalt shell

[cobalt shell]

unfortunately, I cannot say i'm as useful as you'd appreciate

[dry patrol]

ah, I mean bouncing ideas off each other wouldnt be terrible but yeah its okay!

[cobalt shell]

I have a question lurking in the multivar-calc tab, if you want to have a look..

hmm, sorry I would give it a go, but genuinely am quite useless haha

[dry patrol]

i love multivar calc and diffeq that was my fave course so far in uni but I legit dont have the time for now but maybe i can be of help later on

[cobalt shell]

no problem, best of luck with a response

[dry patrol]

thanks

[neon geyser]

I just learned about discrete calculus tonight and I'm sHOOKETH

i always thought it was cool how FTC carries over into multivariate stuff but I never knew it carries over into the discrete world too

[sour arrow]

It does a what now?

Is there a book for this?

[neon geyser]

Look up "concrete mathematics - a foundation for computer science", middle of chapter 2 has the spicy stuff

or google 'finite calculus of differences'

if you wanna experiment with it yourself, let $Δf = f(x + 1) - f(x)$ and evaluate the sum:
$\sum_{x=a}^{b-a}Δf(x)$
the Δ operator works beautifully with falling factorials, which can themselves be converted into powers and used with this to evaluate sums of powers
harmonic numbers are similar to $ln x$, and $2^x$ is similar to $e^x$

[vital dew]

∇ζ(s):

[neon geyser]

it's like an acid trip, would definitely recommend researching into it

[hybrid plume]

this stuff is pretty self explanatory anyone has an idea how to prove them ?

[faint narwhal]

What have you tried

[hybrid plume]

i have them as lemmas so i don't know really i don t know where to start

as i a said it s pretty self explanatory

[pale epoch]

i mean the idea here is probably to prove those "self explanatory" rigorously

you prove all of them directly via the definitions

[hybrid plume]

ok thanks

so i just right them back ?

that doesn t make sense

[pale epoch]

i mean for (a), you can write down a^k explicitly

it's just a*a*a*... (k times)

then write down the inverse of it

and check that the equal signs are justified

this is meant by applying the definition

you look up what "^k" means

and what "^(-1)" means

and apply that

[hybrid plume]

understood

[hybrid plume]

opinions ?

[stray reef]

i would rather not write that big pi notation

you're not in a setting where multiplication can be assumed commutative

otherwise this is ok

[hybrid plume]

ok nice thanks

[vocal forum]

could someone help me identity the general expression for the following sequence?

http://prntscr.com/qwg4zf

I felt like what I answered for (i) was but then I wouldnt be able to figure out what the answer for that is

i know the formula is a_n = ar^(n-1) but i get the same answer as (i)

so im a bit confused

[obtuse lance]

no, you're using the formula for the wrong thing just because it is labeled like something you've seen before

the sum of the first n terms is what it's asking for, not the nth term

[vocal forum]

so it would be: 2(1-3^n)/1-3

[obtuse lance]

yeah

[vocal forum]

ah ok, and (i) would be correct then

[obtuse lance]

yep

[vocal forum]

awesome thank you

[obtuse lance]

you're welcome

[dry patrol]

anyone able to help me with a question I sent in yesterday

proof using storng induction

[timber pike]

Would anyone possibly be able to explain the thought process behind this explanation?

apparently it's obvious, but I'm still struggling to figure out the trick/approach to getting this formula. the context is that A = { a,b,c,d,x }

okay, I guess I've figured it out

size of AxA is the total number of choices for the full function, then it's just 5 possibilities for each, I guess

[obtuse lance]

@vital stag Write out the axioms of a group and check them

[lyric pumice]

The set A consists of the elements in the domain of a function. A binary operation on A is a function that maps a combination of two elements from A to an element of A. Since the size of A is 5, there are 25 distinct pairs, or combinations, of elements from A to be mapped. Since there are 5 elements to choose from for each pair, the number of maps must be 5^25=298023223876953125.

[timber pike]

Thank you very much, this is a comprehensive explanation. I will read it until my mind wraps around it properly ❤️

[weary tiger]

Am I proving this correctly?

Is 6a/b rational

6a/b - 1 I mean

[soft thorn]

that's not the contrapositive is it?

[weary tiger]

ah wait ur right

not q -> not p

but im supposed to do proof of equivalence right?

[soft thorn]

i mean yeah

it's not an issue

it's a valid part of the proof anyway

just not for what you stated

[weary tiger]

just change prove p->q to prove q->p

?

[soft thorn]

yeah

[weary tiger]

so i would also have to prove p->q by using the contrapositive of that?

[soft thorn]

you can

not q -> not p

[weary tiger]

thats the only way to prove irrational

[soft thorn]

sure

[weary tiger]

So like this?

[soft thorn]

that algebra looks kind of suspicious

[weary tiger]

oof

3a/b +1

shit

I think I got it

[weary tiger]

B = {s | s is the set of bit strings with length 5 that have exactly one 1 digit }

what is this

{ 10000, 01000, 00100, 00010, 00001 }

is it that?

[weary tiger]

would the intersection of two power sets include the empty set aswell?

[lyric pumice]

@weary tiger Yes.

[weary tiger]

@lyric pumice yes to the first question or second?

lol

[vocal forum]

Could someone help me out w/ a proof by induction? I am stuck on the induction step. This is what i've got so far: http://prntscr.com/qwlemd

I have a feeling I added k+1 incorrectly

[lyric pumice]

@weary tiger "Yes" applies to the second question.

[weary tiger]

ok thanks

[daring wing]

p AND ~q means both p and ~q are true

[weary tiger]

is f(x) = x^2+2x+6 one-to-one

@weary tiger if it is then x^2+2x+6 = y^2+2y+6

where does the y come from

i got that it wasnt becasue f(-2) = f(0)

a function will be injective if f(x) and f(y) can be simplified to x = y.

because if you have two outputs that are the same

then their inputs must be the same

ah okay

[daring wing]

you can

but there would be no point

[weary tiger]

question

In the proof that

sqrt(2) is irrational

why do we have to assume that a/b is in lowest terms

[daring wing]

 wait uh

if all the females are adjacent...they'd all have to be next to each othe right

so there arne't that many?

depends on whether the seats are unqiue

[weary tiger]

@weary tiger f(a) = f(b) implies a = b

[daring wing]

could be 1 if they arent

[weary tiger]

so for x^2 + 2x + 6, its not one-to-one and not onto

[daring wing]

12 if they are

like is it a different table

i fyou rotate it?

this is a circular table rihgt

[weary tiger]

@weary tiger my algebra might be rusty but the max i'm able to simplify it to is x^2+2x = y^2+2y

[daring wing]

yeah so do you get a different table by rotating the table

also are the people unique

no then are the people unique?

does the order they're sitting in matter

or are the boys and girsl identiical

oh then multiply by the number of ways you can order the boys and the girls

oh wait

are you saying they are unqiue

or not

?

i asked if they were unique and also if they are idnetical lol

ok

then it's like 5!7!

uh because it's not really ciruclar

with circular permutations you divide to account for the fact that your counting rotations as unique

but here you can't rotate an ordering to get another ordering

[weary tiger]

I’m completely lost for this

[daring wing]

yeah

i mean just htink about it

if yu had 1 guy on seat and liek 5 girls in the othe rseats

how owuld you rotate it around

to get another ordering that you count already

but if instead you had 5 girls

you can just rotate it a little

and you'll get one ordering you've counted already

so like 123 and 231 would be the same on a ciruclar table

but let's say you instead had a23 instead you'd do 2!*1!

and that would repressent a23 and a32

you can't rotate to get between those

[weary tiger]

@weary tiger to prove by contradiction assume that G is not injective

and that must lead to a contradiction or falsehood

yeah i got that 😂 dont know where to go from there

[daring wing]

uh you said the Ms are not identical right?

so they would have numbers?

and all the Fs are adjacent

yeah here what i said b4 doesn't necessarily apply

yeah

you'd need like burnside's lemma here or osmething

or bell's numbers

to count it all

uh you probably wont get somethig like this tho?

[weary tiger]

@weary tiger i would probably poke around here https://math.stackexchange.com/questions/845284/if-g-circ-f-is-injective-so-is-g?rq=1

[daring wing]

yeah you'd need burnside's lemma for that

[weary tiger]

Thank you @weary tiger

Does anyone know

Why

When proving that sqrt(2) is irrational

that we assume a/b are in lowest terms

for example in sqrt(2) = a/b

Why do we assume a and b are in lowest terms and base our contradiction on that

irreductible

sorry im from quebec

like their greatest common divisor is 1

[faint narwhal]

because it works? I don't really see your point

We're contradicting the fact that we can write sqrt(2) as a rational number

[weary tiger]

yea but what if we could get sqrt(2) from a fraction that's not in lowest terms

then it wouldn't mean anything that a/b is not in lowest terms

[faint narwhal]

well if sqrt(2) = c/d where c and d are not in lowest terms

then c/d = a/b where a/b is in lowest terms

So we can always simplify down to the case where it is in lowest terms

[weary tiger]

hm

this might sound weird

but we can always simplify down to lowest terms right

so why specify that the fraction is in lowest terms then

[faint narwhal]

so we can get our contradiction

[weary tiger]

right

right okay

so it's a contradiction because it would be impossible to write sqrt(2) as a fraction in lowest terms

i gotcha

[daring wing]

we can also just state c and d are relatively prime

[bleak pollen]

yo is x^2+4=0 a statement?

[void panther]

damn i cant get a tutor V_V

where can i get a tutor lol

[sleek swallow]

don't lol

[weary tiger]

I have no clue if this is right

@sleek swallow wat u think

[sleek swallow]

Your negation of t is not correct

g(a) = g(b) => a=b has the negation g(a) = g(b) and a !=b

Anyways, I just woke up so i'll come back to this after I don't feel like dying lol

[weary tiger]

i put that

g(x1) = g(x2) => a != b

[void panther]

{6,7}={7,6}
true or false

flase right?

false*

[soft thorn]

🤔

[void panther]

😢

[weary tiger]

True

[soft thorn]

i think the proof is fine overall

the general idea at least

[void panther]

true how

[weary tiger]

cuz they contain the same items

[void panther]

so? 🤔

[sleek swallow]

No your implication arrow is misplaced

'And' and 'implies' are two different things

[soft thorn]

except that

[weary tiger]

damn it

[void panther]

whats the damn it for as in youre right or wrong?

[weary tiger]

i have no clue

[void panther]

like damn it im (me drew) are a noob

[weary tiger]

lmfao

[void panther]

rip.

[weary tiger]

discrete math hurts my brain

[void panther]

im hurting inside too

[weary tiger]

im taking computer architecture along side it

so this quarter is hell

[soft thorn]

also idk if just me

but the intermediate variables seems to make the proof harder to read for me

[sleek swallow]

Dude then just don't do computer architecture

Prank

[weary tiger]

taking those classes while trying to find an internship is destroying me

ill just take an L on this problem

ive been working on this HW for 6 hours

[soft thorn]

[weary tiger]

i've accepted my fate of taking 2 classes per semester and no more

a long time ago 🤣

im on quarter system

so we go through material fast

sounds not fun

but only take 3 classes a quarter so 😄

what are you studying ?

soft eng for me

CS

[soft thorn]

[weary tiger]

what year

idk exactly i havent been taking a full courseload

Ah

[soft thorn]

CS is ok

[weary tiger]

All of my friends are watching the super bowl while I’m locked away in my room trying to clutch

lol

it'll pay off

I hope

[soft thorn]

i'm taking today off and procrastinating

[weary tiger]

literally all of my friends were stem majors and switched to business

im the last man standing

the hardest part of studying software engineering for me is

that in soft. eng. you don't learn anything modern

u gotta self learn it all

yet internships want people who know their shit

so you have to learn shit by yourself while managing a course load

the fuck ??

exactly

i only got 1 phone screen out of my 45 applications

they havent gotten back to me yet 😭

[soft thorn]

[weary tiger]

if your school has a career fair use it

yep next week

dont got a suit tho lol

sending out random resumes is reallyyy low chance of success

my only personal project is http://www.coinconv.me

for example I applied for a shopify internship and they got back to me that they had 9000 resumes

have u done any yet?

not half bad but very simple

[soft thorn]

internships sound stressful

[weary tiger]

but they pay very well

make something more involved

and u gain experience

http://138.197.164.139/

here's one of mine

trying to learn react

atm

[soft thorn]

i have some coding stuff

[weary tiger]

but literally no time

[soft thorn]

but i can't show

i'm learning react as well

[weary tiger]

y'all got girlfriends?

they take up a shit ton of time too 😂

[soft thorn]

[weary tiger]

loll

F

[soft thorn]

i already have part time work and full time uni to worry about

[weary tiger]

disregard females acquire currency

kidding

[soft thorn]

true

[weary tiger]

:/

[soft thorn]

i need to acquire currency

[weary tiger]

my female is great female

hahah

i mean ill always have my right hand

👌

[soft thorn]

[sleek swallow]

What is this 'girlfriend' that you speak of?

[soft thorn]

[weary tiger]

https://tenor.com/view/dr-house-oops-gif-6118887

[sleek swallow]

Izzok I'm used to being a lonely boy

I expect that entirely in uni as well

[weary tiger]

how old are u

time to aquire currency 🤣

all will be solved

[sleek swallow]

I'm 21 now

[weary tiger]

acquire currency -> buy girlfriend

u arent a CS major right ?

[sleek swallow]

Nope, i'll be doing math

[soft thorn]

cs 🤢

[weary tiger]

ahh

i got accepted into a better school for applied math, but then i chose the shittier school for CS

[sleek swallow]

Where do you study?

[weary tiger]

Seattle U lmao

but hey its in seattle

ill give bezos a handjob for a job

[sleek swallow]

Idk anything about seattle lol

[weary tiger]

what kind of job do u have with a BS in math

you can do data science

[sleek swallow]

My seniors who did math in uni became quants lol

Apparently, it's easy to get that if you're a math major and can do it well.

[soft thorn]

idk if i'm going to continue with my math major

[sleek swallow]

Why?

[weary tiger]

i like math, im just not the best at it

[soft thorn]

i just can't do maths

[sleek swallow]

Wot

Ya'll are good though?

Idk, i'm at this weird point where I really wanna do a lot of pure math but i also wanna do a lot of theoretical physics

[soft thorn]

i just find it hard to balance uni and work

[sleek swallow]

You're in australia

[soft thorn]

yeah

[sleek swallow]

Ah

Is your degree particularly difficult? How come you gotta work?

[soft thorn]

i like money

nah but really

it's dev work

so it's not awful

and there's a decent amount of flexbility

i like the job

that's why i want to keep it

also i get to learn a lot at work

[proven girder]

{0,{0},{1,{1}},0,{{0}}}

Can someone correct me if this isn't 6 elements?

[faint narwhal]

it isnt

if your brackets are correct

[sleek swallow]

Why would you think that there are 6 elements in that set?

[weary tiger]

5 elements

[proven girder]

The brackets are correct, I'd assume that "{{0}}" is 2 elements, would that be wrong?

An element, inside of an element containing 0

[faint narwhal]

No there are only 4 elements

[feral hearth]

I think it's four elements. Since you count the sets in a set as one element.

[sleek swallow]

See, {{0}} is the set containing {0}. In this case, it's an element of the set you've provided.

Also, a set has distinct elements. It has two copies of the element '0'. Hence, it's a 4 element set

[proven girder]

I see, this is how I was viewing it - different colors representing different elements.

[sleek swallow]

1 is not an element of the given set

[proven girder]

So a set can be inside of another set, I thought it'd just be an element instead.

[sleek swallow]

It is an element of {1,{1}}

Yeap, you can have sets of sets. Those are usually called families but I don't see that distinction being made too often.

[proven girder]

Thank you, I understand it now

[void panther]

@weary tiger you were right about the other one

im big confuse on the one above

are {a, b,​ c} and​ {c, b,​ a} equal but not equivalent?

nevermind

i got it

[analog sonnet]

Nice words to read

[proven girder]

You guys think this is a reasonable answer?

[soft thorn]

sounds reasonable to me

[pale epoch]

yeah

i would remove the "as a whole", but wtv

[hybrid plume]

can someone tell me the cyclic notation of this graph ?

[stray reef]

define "cyclic notation"?

[hybrid plume]

this one

please summit wait a bit

i asked first

i m just kidding xD

post ur question again

[stray reef]

yes summit

[hybrid plume]

ann

?

[stray reef]

what

i didn't ask you to pull something completely irrelevant off wikipedia

i asked you to clarify what in the world you meant by the "cyclic notation" of a graph

[hybrid plume]

cyclic notation is a notation in which the points of the graph are ordered in a way that each one follows the one connected to it. The notation then describes a cycle

and see the picture i sent above to see what i mean

i sent it because i can t write it in discord that way

[stray reef]

can you show me another example of a graph together with its cyclic notation

it's not adding up for me the way you're explaining it

either your graph doesn't even have a cyclic notation or you're neglecting to explain something

[vital stag]

is composition of permutations associative

[stray reef]

is composition of functions associative?

[hybrid plume]

@stray reef that is my question u just asked? idk if that graph even has a cyclic notation

[stray reef]

@vital stag you have your answer then

@hybrid plume you've still yet to explain to me in clear terms what "cyclic notation" means for a graph that isn't simply one big cycle with nothing else

[stray reef]

hey real quick

what's the largest possible edge count on a 3-edge-colorable graph of n nodes?

actually no

disregard that

i have another question

given a set X of n points, what's the maximum number of three-point subsets of X such that any two of them have at most one point in common?

[hybrid plume]

how can you help me though if you don t have such a basic understanding of graphs. I can t explain any further sorry. it s just simply that what i ve said

[stray reef]

how can you help me though if you don t have such a basic understanding of graphs.
you're using terminology i'm unfamiliar with and are outright REFUSING to clarify

[hybrid plume]

no worries

[stray reef]

so you're just not gonna

[hybrid plume]

i ve already explained

[stray reef]

NO YOU HAVEN'T.

[hybrid plume]

In group theory, a branch of abstract algebra, a cyclic group or monogenous group is a group that is generated by a single element.[1] That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group

[faint narwhal]

This has nothing to do with cycle notation

[stray reef]

ffs

[hybrid plume]

idk how to explain any further Ö

[stray reef]

YOU DIDN'T EXPLAIN SHIT!!!

[hybrid plume]

cyclic notation is a notation in which the points of the graph are ordered in a way that each one follows the one connected to it. The notation then describes a cycle
and see the picture i sent above to see what i mean

[stray reef]

the picture has precisely NOTHING, ZILCH, NADA to do with the problem you posted earlier.

[hybrid plume]

it s a bijective function written in a way that describes a cycle

[stray reef]

YOU'RE TALKING ABOUT LIKE TWELVE DIFFERENT THINGS AT ONCE

[faint narwhal]

We know what cycle notation is, when talking about permutation groups

[hybrid plume]

ok what don t you understand precisely

[stray reef]

WHAT. IS. "CYCLIC NOTATION". WHEN TALKING ABOUT GRAPHS?!?!?! NOT GROUPS. GRAPHS. I WANT TO KNOW WHAT IT MEANS, BUT YOU'RE STILL NOT PROVIDING THE MOST BASIC OF INFO.

[faint narwhal]

How do you related this to graphs

[stray reef]

forget groups.

[faint narwhal]

I'm not sure there is a relation to graphs, after some googling

I could see it for a directed graph maybe, but undirected seems weird

[hybrid plume]

please google it i don t have the specific terms to explain it any further i studz in german so

yeah

that s what i thought to

[stray reef]

do you

not have your lecture notes

or whatever

[hybrid plume]

it s mostly used with undirected grphs

i have them in german

[faint narwhal]

Googling it gives nothing

[hybrid plume]

cyclic notation u mean

?

[faint narwhal]

As I said, we know what cycle notation is

Googling how it relates to graphs gives nothing

[hybrid plume]

ok uhm no worries i ll just skip the question thanks anyways

[old imp]

trying to solve the recurrence relation T(n) = 2T(n-1) + n^2 using the substitution method and having trouble figuring out what to substitute for n

[craggy gale]

idk what kind of "substitution" you're looking for but you could try something like U(n)=T(n)/2ⁿ

as the equation would turn into U(n)=U(n-1)+n²/2ⁿ

@old imp

[old imp]

My teacher introduced it to us by substituting a number in for n such as 3^m and writing the recursion individually down from m= 4 until finding T(1) = k

I’ll try working with your suggestion 🙂

[proven girder]

Could someone check my answer and see if I did this incorrectly as I am now confused after seeing the next question (2nd image).

[gleaming zephyr]

show that for some x there is more than 1 y such that xRy

@proven girder

[thick sky]

is there a better way of learning to do proofs for exams than looking at other people's solutions to every proof i can find and memorizing the 'trick' to them

like memorizing that the 'trick' to proving there are an infinite number of prime numbers is that every prime multiplied plus 1 equals a new prime

[obtuse lance]

when learning a proof try not to approach it as "memorization" try to approach it by trying to prove it yourself from scratch, from your common sense

[pale epoch]

every prime multiplied plus 1 equals a new prime

[obtuse lance]

lol I didn't read their example lol

it will take more time but if you don't have some understanding yourself of why it's hard, you won't really gain insight from reading the steps of the proof

[pale epoch]

in general exams only ask really basic stuff that follow directly from the definitions or as corollaries from major theorems anyway

so i guess when trying to proof things, look at the definitions first

and what you know

also the "trick" to the standard proof that there are infinitely many prime numbers, is just "suppose there aren't, then we can ..."

so yeah, try that. if you try to prove something, assume it's wrong and see what happens then

[thick sky]

q = p1p2 … pn + 1

that's what i meant by that

[obtuse lance]

that's wrong, it's not always true that q is prime

just that q is divisible by primes not in the set p1, p2,..., pn

[thick sky]

doesn't that prove there's not a finite number of primes

[obtuse lance]

earlier you said "every prime multiplied plus 1 equals a new prime"

this is false

[thick sky]

i see

[heady geyser]

is it true that $a+b \equiv 2b (\text{mod}, a-b)$?

[vital dew]

l spacebaR l:

[faint narwhal]

yes

[proven girder]

Could someone assist me with this, it's my last 2 questions and I've completely lost hope in solving it

[faint narwhal]

What have you thought about

[proven girder]

I thought if it was non-neg then there would only be one Y-value for each X-value

Making it a function, but the question asks to state why it's isn't a function

[soft thorn]

I mean

So we agree that we have no x mapping to multiple y values right?

So I guess the only other thing to check

Is there something in the domain that doesn't map to anything in the codomain?

@proven girder

[weary tiger]

So I have this stars and bars related question here:

How many 7 digit phone numbers are there in which the digits are non-increasing? That is, every digit is less than or equal to the previous one.

The answer is 16 choose 9 but I'm wondering why that is? I'm confused with the significance of the non-increasing restriction. What does that have to do with the statement?

Say for example these two combinations:

123-4567 and 765-4321

Aren't these two distinct and are counted on the 16 choose 9 expression?

[stray reef]

first one doesn't fit the restriction

[weary tiger]

I know it doesn't. Hmm... I'm just confused with the restriction's significance on the outcome of the question, like why exactly does the stars and bars method work here?

🤦 aight, I get it now why stars and bars work. Cause like, if I rephrase the question as How many subsets are there with the size of 7 on the set of numbers {0, 1, 2, ... , 9}? it makes sense

[stray reef]

no

that's not a valid rephrasing

[weary tiger]

like with that, {1,2,3,4,5,6,7} = {7,6,5,4,3,2,1} right?

that's not a valid rephrasing
how come?

[stray reef]

that gives you the count of numbers which are STRICTLY DECREASING

so you're not counting numbers like 6655531

which are valid under the original phrasing but not under yours

any phone number fitting the non-decreasing restriction is structured as follows: it consists of some 9s, followed by some 8s, followed by some 7s, ..., followed by some 0s. (where of course each "some" can very well refer to one or zero digits.)

[weary tiger]

my brain is melting

lol

ahhh!!!

So yea, I kinda get it now! My rephrasing makes it smaller cause that would just be 10 choose 7, correct?

Also 123-4567 and 765-4321 in the case of the problem are the same things, yes? And if they weren't, it'd be a permutation then, yes?

[stray reef]

no

they are not the same.

[weary tiger]

no I mean like

[stray reef]

one is valid and counted, the other is invalid and not counted.

[weary tiger]

yea, but what I mean is 123-4567 and 765-4321 are the same, but it just so happens that for the problem, it is relevant that 765-4321 is the way to represent that particular pair of combination, rather than 123-4567

[stray reef]

NO

[weary tiger]

😦

damn it, lol

[stray reef]

how hard is it to grasp

that the problem only wants you to count a specific SUBSET of the set of all possible seven digit phone numbers

WITHOUT identifying everything else with something in said subset

[weary tiger]

Ok ok, my b, and thanks! I'm just stringing through my thought process here.

[wanton sable]

is the negation of $$\forall A > 0 $$ equal to $$\exists A \leq 0$$?

[vital dew]

SushiHammer:

[wanton sable]

just wanted to make sure; ngl i'm a little rusty and not sure if i should negate the inequality as well

[stray reef]

no

$(\forall A > 0)(P(A))$ negates to $(\exists A > 0)(\neg P(A))$

[vital dew]

Ann:

[wanton sable]

ah okay thank you!

[hybrid plume]

why is the cardinality of a symetrical group n! ?

[pale epoch]

there is n! ways to permute the numbers 1 to n

[hybrid plume]

is there a proof for it

?

[pale epoch]

of course

it's pretty obvious if you think about it though

guess you can prove it with induction

[lyric pumice]

@neon thorn You are missing the assumption step.

Apply the assumption to the inequality.

Then use the result to obtain the larger inequality.

[old imp]

I feel like this is a really stupid question but can I multiply S = 2^m * T(n-m) by anything to make it xS = 2^m * T(n-m-1) ?

[lyric pumice]

Yes.

There is no getting rid of k+1. It emerges from the sequence of inequalities.

[old imp]

induction is so hard dude at first dude, I had a lot of success walking through answers of stackoverflow step by step

[lyric pumice]

There is no substitution necessary. You should know something numerical about k.

What values can k be?

So, 0<k<2^k.

Then you can formulate inequalities for k+1.

Yes.

You must prove this.

Is this true?

Prove that.

Suppose k=1. Then

Thus

No.

If the inequality is true, then you must show that it is true mathematically.

Yes, but the textbook is very terse.

You should show why the intermediate inequality is true.

Show that this is true.

[old imp]

Does this recurrence relation look right? It seems a little too simple so I think I missed something at the end.

[hybrid plume]

can someone tell me what is this called in english ?

[gleaming zephyr]

power set

[hybrid plume]

thanks

i need the one with the empty set though

like a binary set or something

[gleaming zephyr]

what

[hybrid plume]

the power set of elements that are represented with the empty set

like in the example

[pale epoch]

this makes even less sense

[hybrid plume]

ok lemme explain

u already know how numbers can be represented with binaries 0s and 1s

in this case the empty set is 0

and a set containing it is 1

i want to know the term of it in english

[pale epoch]

this is just regular natural numbers

its how they are usually constructed

[hybrid plume]

exactly

do u have an example

?

on the internet

[pale epoch]

i think its due to von neumann

[sleek swallow]

You’re doing it using the axiom of infinity

[pale epoch]

von neumann ordinals

[sleek swallow]

Search that up

[pale epoch]

yeah, or zermelo ordinals