you want functions that limit your function as x gets larger
#discrete-math
solemn dome
would that be (x^4 + 4x)/(x +2)
errant bear
and g?
leaden pebble
yikes, that source uses equals instead of \in
solemn dome
uh x^n
leaden pebble
think about it pierre, what is the smallest x^n that can limit your function up to a constant
for polynomials this should be trivial
for instance
say you have f(x)=x^2+3
you should have something like
f=O(x^2)
because
for example
solemn dome
im reading btw
leaden pebble
take 2x^2
errant bear
fractal this isnt helpful :sully:
leaden pebble
2x^2 will always be bigger than x^2+3 after a certain x
solemn dome
yeah
leaden pebble
so that means x^2+3 = O(x^2)
because your x^2 can limit your x^2+3 up to constant
(in this case, 2)
solemn dome
before you continue
i think im even more confused because i dont know the end product or like where im trying to go with solving this problem
is the goal/answer finding the smallest x^n?
leaden pebble
"Find the smalles integer n"
solemn dome
i dont even know why i did long division
errant bear
just ignore what they said and use the definition 
leaden pebble
Im trying to make the definition intuitive for them 
trail steppe
You can see this easily with Desmos.
This graph implies that 2x^2+6x-10 is in O(x^2)
leaden pebble
because of the constant 3 btw ^
solemn dome
ok
i rly do appreciate u guys trying to help me btw, like im not just being stupid im actively trying but the point is just flying over my head
trail steppe
Showing the bounds more clearly, I changed the functions a bit to have the constants nearer the middle of the screen
@leaden pebble And yes you're right, the constant at the front should be changeable, but I have no idea how to better show it
You'd need like a sequence of increasing constants IMO to show that there exists one constant which is a quite a bit of real estate for one small result
stray reef
yknow
if g doesn't vanish too often then f = O(g) is equivalent to f/g being asymptotically bounded
trail steppe
@stray reef I'm not too sure if the audience here knows 'asymptotically bounded'
stray reef
so you want the smallest $n$ such that $\frac{x^4 + 4x}{x^n(x+2)}$ doesn't blow up as $x \to \infty$
vital dewBOT
Ann:
trail steppe
'audience' being the guy asking the question
solemn dome
the audience definitely doesnt know LOL good assumption
stray reef
i mean at least instead of two functions you're now thinking about their ratio
trail steppe
^I like showing the ratio though, that's a good idea
stray reef
if n is too small the numerator will overpower the denominator and go to infinity which you don't want
solemn dome
i see what you're trying to say
but what do i do to accomplish finding the smallest n
errant bear
well you should have 3 cases to consider
stray reef
wym three cases
i mean like
the numerator behaves like x^4
the denominator behaves like x^(n+1)
you want these to cancel out
n=3
trail steppe
To show Smallest integer very systematically I would start with O(x^0)
Then O(x^1)
etc.
solemn dome
so the most basic way to say how to solve this problem is just plugging in numbers until it explodes to infinity
trail steppe
Might not be easy to show that there does not exist any constants n, c_0 ... for O(x^1) but there should be a way
solemn dome
and the number before that will be the answer?
trail steppe
Not quite, I'd consider differentiation actually (since these functions are differentiable)
The 'there exists no pair of constants' part should be doable
The answer is not O(x^100) so your working won't be 3000 pages
hasty glade
@stray reef
I need you help
Consider a Polygraph T
Then $\sum g^{+}(v) = \sum g^{-}(v)$ Is this true ?
vital dewBOT
AfterJack:
stray reef
should be true @hasty glade
peak sorrel
How to solve this? T.T
naive saffron
potent mirage
Could anyone help me with these two problems?
oak plaza
What's going on with r(t) in the first problem. Is it supposed to be a vector-valued function?
oak plaza
so for reach t you're given a vector whose coordinates are $ r(t) = \left < \sqrt{4-t}, \frac{e^t - t }{t}, ln(t+3) \right> $
vital dewBOT
JohntheDon:
oak plaza
It kind of matters what you want the values of r(t) to be. If we are considering r(t) to be a real-valued function - which is probably safe to assume here - then you need to restrict the values of t such that coordinates of r(t) are strictly real.
and , of course, for which values of t the function is even defined at all.
If you look at the first coordinate, again assuming that we want r(t) to be real valued, then ti has to be the case that $ 4 - t \geq 0 $
vital dewBOT
JohntheDon:
oak plaza
$ 4 - t \geq 0 \iff 4 \geq t $
vital dewBOT
JohntheDon:
oak plaza
So that's one restriction that you have to put on t
looking at the second coordinate, then you have to note that t actually cannot be zero ; otherwise divison by zero occurs.
and for the third coordinate, because of the domain of the natural logarithm, it has to be the case that $ t > - 3 $
vital dewBOT
JohntheDon:
oak plaza
You have to use all three of those conditions in order to get the answer. Maybe from here you can deduce what needs to be done.
Also this question is probably better answered in the precalculus or algebra section.
I'm not sure what you know about regarding limits of whether or not you've been introduced to them. But for the second problem, you'll want to apply those.
loud sonnet
Where can I learn/read about generating functions?
obtuse lance
there's the book generatingfunctionology
dense pier
Hey quick question, anyone knows where the XOR stands in the priority list? 1.NOT 2. AND 3. OR 4. IMPLICATION 5. IFF
foggy hatch
around "OR"'s priority. Please don't write expressions without parentheses where the reader has to worry more than that
mild edge
anyone have any discrete sine wave resource recommendations? thank you if u do 🙂
sleek swallow
I have a really good recommendation regarding that
(On a more serious note, that sounds like a super specific thing so you could probably find lecture notes online that discuss it. https://www.google.com/search?q=discrete+sine+wave+lecture+notes&rlz=1C1CHBF_enSG822SG822&oq=discrete+sine+wave+lecture+notes&aqs=chrome..69i57.5727j1j9&sourceid=chrome&ie=UTF-8
There are lots of potential resources that pop up so have a look at those.)
@mild edge
last timber
winter rose
How do I find the total possible combinations for x1^a * x2^b where a + b <= 6?
compact shell
Let A={Ï•,{Ï•}} What is the total number of relations from A to A
Shouldnt it be 2?
autumn ember
The number of relations between two sets A and B is the number of subsets of the cartesian product of A and B. In this case, AxA has 4 elements, so the number of relations is 2^4 = 16
sleek swallow
@compact shell
compact shell
Thanks
silk swallow
Hi
cunning crescent
Can you help me find f(n1) and f(n2)
sour arrow
What is f?
cunning crescent
This is f(n) = n - 1, for every odd integer n in O @sour arrow
cunning crescent
Dont worry about that, I messed up but thank you very much
weary tiger
If I choose four cards from a standard 52-card deck, with replacement, what is the probability that I will end up with one card from each suit?
i know that
(52 * 39 * 26 * 13)/52^4 is overcounting
but what does it overcount?
because if you look at it in steps
that's how many choices you have at each step
52 cards of any suit for the first card
39 cards of a diff suit for the second card
26 cards of a diff suit from first two for the next
and only 13 cards of the remaining suit left
so what does this overcount?
@stray reef ?
stray reef
gimme a sec
restive finch
I got 9.375% probability that you will end up with one card from each suit. Not sure if it's correct though.
stray reef
sen the numerical value is of little to no relevance here
anyway
@weary tiger afaict your thing DOESN'T overcount
weary tiger
can you show your paper
stray reef
do you really want to see exactly what i wrote down
weary tiger
yes please
weary tiger
oh
nope
that's counting something else
hmm
i feel like we're introducing order here on purpose
stray reef
there are 4! ways to arrange the four suits in a row and 13^4 draw sequences which have one in each suit for every particular suit arrangement
weary tiger
with the multiplication by 4!
is there a way to not introduce order in the # of possible
i.e. so we don't have to multiply by 4!
leaden pebble
werent you making fun of that guy for not knowing combinatorics
stray reef
who what where
weary tiger
@leaden pebble no i wasn't
but he said he's good at math and doesn't know what a combination was
leaden pebble
Im just joking tbh
weary tiger
also idk why you are typing
weary tiger
what do you mean yikes
you can't insult someone
then say yikes when they bite back
stray reef
aight can we get back to the problem
weary tiger
sure
stray reef
is there a way to not introduce order in the # of possible
i.e. so we don't have to multiply by 4!
weary tiger
so how else can we get rid of order in the denom
stray reef
sure, you could say that there are 52 options for the first card
weary tiger
no i mean
stray reef
39 for the second since you exclude the 13 cards in the first one's suit
weary tiger
if we wanted to keep the 13^4
stray reef
are you asking if it's possible to make a different problem whose answer would be 13^4/52^4
weary tiger
this is what i did originally
no
how can we change our set of possible
because our set of possible is ordered right now
but our desired is unordered
correct?
stray reef
what
weary tiger
(that's why you multiplied by 4!)
stray reef
vital dewBOT
polynomial:
weary tiger
you have to multiply this by $4!$
vital dewBOT
polynomial:
stray reef
4! ways to arrange the suits
ie whether you draw them in the order ♤♡♢♧ or ♧♡♤♢ or what have you
weary tiger
sure
we only need to do this
because we already do that in each of our denominators
the 52^4 accounts for all such orderings
so what kind of denominator would we have to count as if we didn't want that
could we do something like
stray reef
52^4 is the count of all possible draw sequences without caring what the cards are
weary tiger
C(52,4)?
weary tiger
yeah
stray reef
it sounds like what you're trying to do is impossible
sleek swallow
Well, not quite
Let $A$ be a set and $R$ be an equivalence relation on $A$. Let $a,b \in A$ and suppose that $[a] \cap [b] \neq \varnothing$.
\
Since the intersection is nonempty, there exists a $t \in A$ such that $(t,a) \in R$ and $(t,b) \in R$. By symmetry and transitivity, we can see that $(a,b) \in R$.
\
Now, let $x \in [a]$. Then, $(x,a) \in R$. By transitivity, $(x,b) \in R$ so $x \in [b]$. Similarly, let $x \in [b]$. Then, $(x,b) \in R$. Then, by transitivity and symmetry again, we have $(x,a) \in R$. Hence, $[a] \subseteq [b]$ and $[b] \subseteq [a]$. So, both equivalence classes are equal. That proves the result by contrapositive.
vital dewBOT
Abhijeet Vats:
sleek swallow
@umbral summit I'm using set-theoretic notation since that's much more clear to me but if you need to, you can just convert it into infix notation for your own convenience.
Please respond so that i know you're done with the problem
You're welcome
Ah that's fine
weary tiger
Does anyone know if for a stirling number of the second kind i.e S(n,k), where n is the n-set and k the k parts that the n-set is partitioned into, if the order of the parts matters?
For instance:
X = {a,b,c,d}
And we get for instance the partition:
H = {x1,x2,x3,x4}, where
x1 = {a}, x2={b}, x3={c},x4{d}
This counts as 1 possible partition, but would the following also be the equivalent of the same partition:
if x1 = {b}, x2={a}, x3={c},x4{d}? Would the stirling number just count these two examples as the same partition?
If this is not true, then what does it mean that the order of the parts does not matter?
abstract whale
Hi guys, https://youtu.be/z8HKWUWS-lA?t=2436. Could someone please explain to me how he got the (-n) into the equation at 40:35? I was following the reasoning until that point.
weary tiger
from what I can see he just added and subtracted the expression with n so that it would still equal the previous answer. But by doing so he got it to the form n^3-n. Adding n and then subtracting by n doesn't change the value of the equation. It's like I have a value 5, subtract by 1, then add 1 again, it will 5 again, so the value doesn't change.
So what he did:
n^3 + 3n^2 + 2n = (n^3 + 3n^2 + 2n) - n + n = (n^3 - n + 3n^2 + 2n + n) = n^3 - n + 3n^2 + 3n
And so you can see now:
n^3-n is divisible by 3 as stated in the assumption.
3n^2 and 3n each are also divisible by 3.
so the entire expression is therefore divisible by 3
abstract whale
I see, so it's pretty much an "algebraic trick" in order for the "assumption" to be true. I get it! Thank you @weary tiger . So as long as you don't technically "change the value" of the original equation, things like that are allowed. I guess I will be seeing a lot of those things on discrete math lol.
weary tiger
ye, I feel like induction is almost more of an art sometimes, you sometimes have to be creative hehe
abstract whale
No wonder I suck at it so much lol
weary tiger
practise makes perfect though hehe
one advice i think is
the assumption that you make can give you a hint of what form you what your induction proof to be like
so in this case n^3-n was the assumption, so if we hold that in the back of our mind, trying to somehow manipulate the inductive proof to include that term, that can kinda guide us how to conduct the proof
because my understanding is that the inductive step is dependent on that assumption
abstract whale
Damn, do you want to be my math teacher? That was some of the clearest explanations I have seen of induction lol.
Thank you, @weary tiger . I really appreciate it. Induction is making a ton more sense now.
weary tiger
haha im no better than you, i'm also taking a course in discrete math xD
abstract whale
Seems that someone's has actually been paying attention lol
but yeah, dude, it takes a different kind of intelligence, more creativity than actual "memorization"
weary tiger
ye idk, whenever you are stuck on something I think it really helps to be very EXPLICIT about what you don't understand. Because it gives you structure of how u can break what you don't understand down step by step and solving each step in order to acquire a deep understanding of the answer.
I think 1bluebrown3 has a good video about this
it's kinda meta, like learning how to learn in math
if you got time then u can check it out
abstract whale
Awesome, thanks man.
weary tiger
no worries, happy I could help!
orchid pine
what is the difference between the alphabet and the state space in a finite state machine?
pale epoch
the state space is the set of states and the alphabet is the input alphabet? @orchid pine
those are two totally different things
weary tiger
could someone help me in proving this
weary tiger
alebraically would be perfered but if not, combinatorially
lyric pumice
Lets look at it combinatorially.
A good start would be to come up with structures that can be counted by a formula that looks like the binomial coefficient on the right side of the equation.
weary tiger
just a fyi I am really bad with combinatorially so you might have to explain it like extra clear for me to understand..
lyric pumice
Are you familiar with paths on a rectangular grid?
weary tiger
no
lyric pumice
Then you can start by using repeated applications of Pascal's formula on the right side of the equation.
weary tiger
isn't it easier to do pascal's identity on the left side?
im not sure how repeated application of pascal's on left would help
lyric pumice
The trick is that you can use it once on the right side of the equation.
hasty glade
If I say that a ring is $\left ( Z_{62},+,* \right )$, then, is it right to say that the equation $43*x=8$ has no solution ??
vital dewBOT
AfterJack:
weary tiger
but you get a n-1 choose -1 just from the first iteration..
honest barn
If I say that a ring is $\left ( Z_{62},+,* \right )$, then, is it right to say that the equation $43*x=8$ has no solution ??
@hasty glade this isn’t true
vital dewBOT
Mathemagician:
honest barn
I think
hasty glade
Which would be the solution then ?
honest barn
then there exists some x such that 43x = 1 mod 62 right?
So then just take y = 8x
Then 43y = 8 mod 62
honest barn
I mean...
If there’s x y such that 43x + 62y = 1
Reduce mod 62
Then you just have 43x = 1 mod 62
So you can multiply this by 8
hasty glade
I will tell what I did. Because I think I did it wrong
I did 43x = 8 (mod 62)
Then 43x + 62k = 8
honest barn
Yeah
hasty glade
Doing euclid
honest barn
No this has to exist
hasty glade
1 = 43.13 + 92.-9
honest barn
For any two numbers a and b there exist integers x,y such that ax + by = gcd(a,b)
This is Bezout’s lemma
hasty glade
Okay
honest barn
If gcd(a,b) = 1
Then you can reach any integer by taking Z-linear combinations of a and b
hasty glade
The values of that x and y are 13 and -9
honest barn
Hmmmmmm 🤔
hasty glade
And yes you can make any int a linear combination of a and b if gcd(a,b) = 1
honest barn
So then shouldn’t 43*13 = 1 mod 62?
hasty glade
But why that ?
hasty glade
I get it dont worry
hasty glade
Oh hahaha
hasty glade
I m so sorry but I dont understand
hasty glade
Yep
honest barn
In the second one the two differ by a multiple of 62
hasty glade
I get that
honest barn
So they’re the same mod 62
This is the definition of being equal mod 62
2 = 64 mod 62 because 64 - 2 = 62k for some k
In that case k = 1
43 x 13 + 62 x -9 = 43 x 13 mod 62 because
Their difference is 62 x -9
Is a multiple of 62
hasty glade
So what is your conclusison ?
honest barn
That 43 x 13 = 1 mod 62
honest barn
Mod 62
hasty glade
1
hasty glade
But what I cannot find a relation for is why that would conclude that it has a solution
honest barn
Because this is your solution lol
This says there is equality of 43 * 13 and 1 in Z/62Z
So that 43x = 1 has a solution
honest barn
43 * (13 * 8) = 8 mod 62
hasty glade
Then that x is not a member of the ring
honest barn
hasty glade
{0,1,2,(...),61}
hasty glade
Yep I get that hahaha I do not know how to explain myself. I m not an english speacker
Hmmm..
hasty glade
So I said that (Z62,+,*) was a ring right ?
hasty glade
Then the elements of Z62 (Because I m working with no-infinite structures)
Will be {0,61}
hasty glade
But I m not talking about classes in this case
honest barn
0 = 62 = 124 = 186...
hasty glade
[0]
hasty glade
I get what you say
honest barn
If x isn’t in {0,...,61}
By reducing mod 62
You can keep that equality mod 62
And take x to be in {0,...,61}
Just add or subtract 62 until it’s in there
hasty glade
MEN YOU ARE RIGHT..
honest barn
This is why it’s pointless to make Z/62Z the actual numbers 0,1,...,61
hasty glade
[108] will be a member of some class inside Z62
honest barn
Okay haha
hasty glade
I m so stupid hahaha
hasty glade
If the solution exists.. then it does for class inside Z62
hasty glade
Sorry for wasting your time.. At least, it was super worth for me
honest barn
No worries
hasty glade
Can we say that all these equations.. Will have only 1 answer ??
honest barn
Uh
Yeah
Up to equivalence
So like if x works then x + 62 works
But those are the same in Z62
The reason there’s only one solution is that a polynomial f(x) can have at most as many solutions as its degree
So 42x - 1 = 0
Is what you solved
And that’s degree 1 so it has at most 1 solution
This is true for any ring
hasty glade
For ANY ring ??
honest barn
Yes
I can outline a proof basically
Err... does it need to be an integral domain for this to be true
Hold up I might have lied actually haha sorry
So like if f(x) has a as a root
You can show that f(x) = (x - a)g(x) for some g
hasty glade
Gauss theorem
honest barn
And this should be enough to say that
Uh, maybe I don’t know it by that name
But you should be able to just keep going until g is linear
And you can’t go any more
I just can’t remember right now if you need that the ring is an integral domain
Sorry, i can’t remember right now which is really bad lol 😰
Oh it’s false
So I lied
Here’s an easy example
Take 4x = 0 in Z8
hasty glade
of what I did ?
hasty glade
Wait ? do you think I m asking it for an exam or something like that hahaha ?
honest barn
I mean
hasty glade
Oh men I m so sorry hahaha
honest barn
Just do the computation I guess
hasty glade
I have 13 and 104
honest barn
You should have
43 * 104 = 8 mod 62
From there you get 43 * 42 = 8 mod 62
Anyway I gtg
hasty glade
I get it
I did 108/62
104*
The reminder
Has to be the answer
Thanks a lot @honest barn
lyric pumice
@weary tiger Hi. Did you get it?
weary tiger
How many ways are there to arrange 6 beads of distinct colors in a 2x3 grid if reflections and rotations are considered the same? (In other words, two arrangements are considered the same if I can rotate and/or reflect one arrangement to get the other.)
i am so stuck on this problem
i don't know how to do this at all without doing a ton of casework
obtuse lance
sounds like an application of burnside's lemma
weary tiger
nah
obtuse lance
lol
I'd guess 6! ways to lie the bead on the grid, then divide by a power of 2 to account for the rotations and reflections you're double counting
weary tiger
@obtuse lance but the 2x3 makes me think there is more or less symmetry to it
since it's not a square of things
obtuse lance
yeah, I addressed that in my message
naive saffron
Burnside’s lemma works
The set of symmetries is the dihedral group on 2-gon
Since all colors are distinct, nothing is fixed by a non identity element, while everything is fixed by the identity
naive saffron
Ye
obtuse lance
I didn't say 4 cause I wanted him to work out what power of 2 was needed to account for the rotations and reflections 😩
stray reef
😩
hardy remnant
could someone help me with c
my book sucks at explaining
and im not sure how to start solving it
i get b
i think i get a
its like -1,0, 1
-2, 0 ,2
and goes to infinity, right?
so with Union, it would be Z and the intersection would be 0
thats the problem, idk how to write it out correctly
{-1, -1+1, ... , -1,0 1, ..., 1-1, 1}
so like {-1, 0, ..., -1, 0, 1..., 0,1}
idk what that means, does it mean the set only contains -1, 0, and 1?
then A_2 would be {-2, -1, ..., -1, 0, 1, 1, 2}
A_1 U A_2 would be {-2, -1, 0, 1, 2}
is this what its asking?
what does the ... mean
hmm i see
ahh
i gotcha
what the heck is problem c asking then
its asking for numbers between i and -i
{-i, i}
{-1, 1}
{-2, 2}
{-3, 3}
so the numbers between them are 0, 1, -2, 3, -3 and continues on right
{-R, R}?
isnt the symbol for real numbesr R
oh
c
oh
i didnt see that they were using []
yeah
so it goes from -1 to 1
vital dewBOT
slimvesus:
vital dewBOT
slimvesus:
hardy remnant
oh
vital dewBOT
slimvesus:
hardy remnant
hmm i see
hardy remnant
[-1,1]
oh
ok i gotcha
{[-1,1], [-2,2]}?
The union of a set A with a B is the set of elements that are in either set A or B. The union is denoted as A∪B.
{-2, -1,0, 1, 2}
dang
weary tiger
@weary tiger I just did a induction +combinatorial proof
weary tiger
where can i find practice problems for combinations and permutations ,i am really struggling on word problems
lean flume
If a function F is one-to-one correspondence from its Domain to its Co-domain then does it have an Inverse Function?
pale epoch
what do you mean by one-to-one correspondence?
junior mantle
Isn't one-to-one correspondence is the same as bijective?
junior mantle
and yeah, a function is invertible iff the function itself is bijective
@lean flume
near root
Question: If P(C) = P(A) U P(B) then B=C or A=C.
I proved it using the fact that C is held within P(A) or P(B) and then saying that A holds C, now can I deduct from that, that C holds A or is that not an option?
I know there also exists the way to prove it using negative on the latter part but I used this method, and want to know if that's a reasonable proof
lean flume
what does it mean if for a function F to be a one-to-one correspondence?
robust mango
A function which is both, one-to-one(injective) and onto(surjective).
In other words, a bijective function.
weary tiger
if you google for the different "types" of functions you can probably find a picture that illustrates it well, maybe it's easier to understand with a picture like this:
so the orange dots are the elements from the domain while the green ones from the codomain
In the bijective case you can see that every element from the domain maps to exactly one element in the codomain. No element from the domain maps to the same in the codomain, that's why it's a one-to-one correspondence.
hardy remnant
my book barely covered any bit string stuff and how to start bit string questions
how do i know if a bit string with no bit 0 is countable or not?
does this mean
{1,11,111,1111,11111,...} is countable? it looks like it
rain stone
@hardy remnant establish a bijection with N, or show no such bijection exists
in this case, finding a bijection is pretty easy
hardy remnant
i see
rain stone
do you see how you'd do it?
hardy remnant
the bit strings with 1s are in the set of N, so its countable?
pale epoch
sure, but that does not (fully) answer the question
rain stone
@hardy remnant so it's not just asking you to prove that a bijection exists. {1, 11, ...} is a subset of N, and it's infinite, so it's countable. That would work, but the question doesn't just want you to prove a bijection exists, it wants you to explicitly construct one
construct a function f that maps {1, 11, ...} to N, such that every element of N is mapped to by an element of {1, 11, ...}, and such that every element of {1, 11, ...} maps to exactly one element of N
rain stone
no problem!
ping me whenever :)
do you know how to construct bijections between finite sets?
sleek swallow
@hardy remnant
hardy remnant
bijections are one to one so i should be able to
sleek swallow
No
Let A = {1,2} and B = {3,4}. Can you construct a bijection between A and B?
We'll start simple and work our way up. I can just provide the solution since i've written up but it's probably more useful for you to get comfortable with the basics
@hardy remnant
hardy remnant
no
rain stone
yeah, I wrote up the solution too abhijeet, although I probably did it slightly more consicely cause mine is about 2 lines
sleek swallow
What do you mean "no"? "no", like, you don't know how to or what?
the solution to abhijeet, yes, my mum still tries to solve the mystery of how i became like i am today tbh
hardy remnant
oops, i thought we cant construct a bijection between a and b
sleek swallow
Do you know what a bijection is?
hardy remnant
yes
sleek swallow
Tell me what it is
sleek swallow
Use capital letters for sets.
one element in set a is mapped to one element in set b
This is the definition of a map, not a bijection. I mean, it still needs one or two more words to be complete but still, it doesn't describe a bijection.
| A | = | B |, i believe
In fact, we say that two sets A and B have the same cardinalities (|A| = |B|) when there is a bijection f: A ---> B that exists between them
hardy remnant
the element from Set A is paired with exactly one element from Set B
rain stone
"the" element - do you think it's something that happens to only one element in the set?
sleek swallow
Let $A$ and $B$ be sets. A bijection $f: A \to B$ is a function such that every element of $B$ is mapped to exactly one element of $A$.
vital dewBOT
Abhijeet Vats:
hardy remnant
no, it happens to every element in the set
sleek swallow
You're very rough with your definitions. It's not a good thing.
hardy remnant
yeah, sorry
sleek swallow
Don't apologize. You're trying but you need to get yourself familiarized with basic definitions before you move forward.
i.e. review the definitions of things like a map, an injection, a surjection and a bijection
rain stone
and try to understand why the definitions are what they are
what's special about a bijection? why do we care about them?
hardy remnant
theyre mapped to their paired element in a different set so we can use an element in Set A to retrieved an element in Set B, is that it?
rain stone
Yes!! that's one big part. The idea of "retreiving" can be formalized with an inverse function.
If you have the set A = {1, 2, 3} and B = {1, 2}, and you have the function f(1) = 1, f(2) = 1 and f(3) = 2.
This isn't a bijection, because two elements in A are mapped to the same element of B. Also note that there isn't an inverse function, since you wouldn't be sure what to map 1 to. that's one nice property of bijections!
another nice property is that there's a bijection between two sets if and only if they have the same number of elements
read through the definition that abhijeet wrote, and see if you understand why that makes sense
the idea of a bijection is that it "pairs off" elements from the first set with the second set, and every element is in exactly one pair
rain stone
@hardy remnant
hardy remnant
yup, i get that idea
rain stone
great! so for an example of a bijection between infinite sets
I'm gonna show a bijection between {1, 2, ...} and {2, 4, ...}
ie between N and all even numbers in N
consider f(x) = x/2. if you apply this function to the second set (all even numbers), the resulting set is N
Clearly, the function gets you one natural number from each even number. Additionally, no two distinct even numbers map to the same natural, since if x/2 = y/2, then x = y
finally, each number in N is mapped to by some even number, since ever even number is in the form 2n, so dividing this by 2 gets you any number n
@hardy remnant this is a bit of an informal argument, but it's the gist
novel spire
Hey y'all. Would love some help creating a discrete math question. Or really just talking about how one might go about coming up with things for it.
Here's something I'm working on right now. I'd LIKE to have a false statement.
But like ... it seems to be much harder coming up with plausible-but-false statements than true ones. 😛
honest barn
I feel like making something false is incredibly hard
novel spire
Yeah. Exactly. 😛
honest barn
The main thing I have is that anything that's false likely has to be proven wrong by just making a random shape and showing that it's false
But everything I thought of that has some sort of counterexample is really obviously false if you think about it for a second
novel spire
The intent is to have the pigeonhole principle fail.
I don't mind if it has a relatively easy counterexample though, as long as the student has to attempt to make it.
honest barn
Maybe something like "there exists a triangle which contains all 10 points" that at first glance might sound plausible?
novel spire
One I thought of a second ago was "There exist three points that form an acute triangle".
honest barn
But it seems like you want stuff in terms of liek distance for pigeonhole like you said
can you actually make that fail?
novel spire
Yeah. Draw the points as part of a quarter-circular curve.
honest barn
oh huh yeah
novel spire
If you pick any three points, there's an obtuse angle.
honest barn
ohhhh whoops
I misread that lol
For some reason I thought that was saying you can fail to have any acute angle
for some reason triangle to me seemed like the angle ABC for a second
My ideas were mainly about like stuff involving convex hulls, or like making polygons around them
one idea I had was like "one can form an up-to 5 verticed polygon whose vertices are all one of the 10 points such that all 10 points lie in this polygon"
it seemed plausible to me since like 5 is half of 10
but a regular... decagon??
10-sided polygon lol
Will fail this I think
since the convex hull is just the polygon itself
honest barn
Also the notion that there exists a triangle inside of the unit square which contains all 10 points
this is clearly possible if you allow a square
but I'm pretty sure it isn't true for a triangle
I can't think of a nice proof that it doesn't exist lol, I'd have to think more but if a nice and relatively simple proof exists it might be a good option
Actually I have one, but it's kinda blech
novel spire
Well just put four points at all four corners
honest barn
Any triangle is convex, so if a triangle contained all 10 points it has to contain the convex hull
the convex hull being the smallest convex polygon containing it
And it has as vertices some subset of the points
so you can make a set of points such that the convex hull has too large an area
since a triangle inside the unit square has an upper bound on its area
novel spire
I think I'm going to stick with the acute triangle though
Because of what you said where it's easy to confuse that if you're not thinking and think "well there's always going to be an acute angle" 😛
So this
Well ... actually come to think of it. XD
I might keep playing with this.
How about "There exist four points that form a quadrilateral containing at least one of the other points."
That sounds even simpler but the convex hull thing ends up being a great way to disprove it
Thank you~
true hare
hey there, wsa wondering if i could get some help with this practice problem by chance
pale epoch
what have you tried?
hasty glade
I m not being able to find a group that is not conmutative...
honest barn
Invertible Matrices under multiplication
Endomorphisms under composition
In some sense the latter is a superset of the former lol
sour arrow
The smallest finite non-commutative group is S3
sour arrow
I mean small is a weird word
It's got a lot of weird letters
Like "m"
And two "l"s!
Together!
hasty glade
Well the thing is..
honest barn
Why are you posting this in discrete math
hasty glade
Because it is discrete math
honest barn
No it isn’t lol
hasty glade
I think it is
honest barn
That’s #groups-rings-fields
Dude this isn’t the channel for this
Go to #groups-rings-fields
rain stone
I mean nobody else was using this channel so it's not like it's a huge deal
but you know for next time!
hasty glade
Now I m coming back with a discrete math question
Forget about what I ve just said... I was looking to the wrong quesiton
pearl jackal
can someone help me understand this, I highlighted the specific parts I don't understand if that helps
sick swallow
use greatest common divisor or even euclidean algorithm ideas
as n is a multiple of p^e
like u also could use p-adic valuation but it is very unnecessary
pearl jackal
Oh so if p divides n-k it must divide n and k individually
And then that translates into p being able to divide the term (p^e-k)
Am I understanding it correctly? But I still don't get where the (m-k) thing comes from
obtuse lance
I kinda like the p-adic valuation way for this after you mentioned it, it's more "plug and chug" easier to reason but requires knowing the formula at a minimum and also a little bit of reasoning
compact shell
Hello, Let |A| = n and |B| = n. How many functions from A to B is invertible? Could someone explain this?
obtuse lance
what does it mean to be invertible?
compact shell
Not sure, could you explain?
obtuse lance
does your book have a definition
the down to earth idea of being invertible is that anything you do, you can undo
mixing up the order of pens on your desk is an invertible operation
mixing paints isn't, you can't unmix paint
I'm just saying this to give a vague idea of what it is until you tell me what definition your book/teacher has given you
have you heard the term injective or surjective before?
hasty glade
Hi guys
Consider (Z21,+,*)
The ecuation 3*x = 11 has no solution because mcd(3, 21) = 3 and 3 do not divide 11
Is my reasoning right ?
weary tiger
is that a typo or
hasty glade
@honest barn tell me this goes here and not in #groups-rings-fields
hahaha
is right to post it here ?
weary tiger
i guess but you posted a question that makes no sense
so i'm asking if you made a typo
quaint lichen
{(1,1)} would be transitive? since (1,1) -> (1,1)-> (1,1)?
i.e there's no uniqueness condition on a,b,c?
errant bear
? is that supposed to be a relation
naive saffron
Yes that would be a transitive relation
quaint lichen
then how on earth is
{(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}
not transitive (according to answer key)?
(0,2) -> (2,0) => (0,0) ✅
(2,3) -> (3,2) => (2,2) ✅
(a,a) -> (a,a) => (a,a) for a=0,2,3 ✅
@naive saffron
quaint lichen
ahhh right
errant bear
also 3,0
honest barn
If your question has not been answered for a minimum of 15 minutes, you may use the @ helpers tag once. Please do not try to bump your question using this ping unnecessarily. Do not abuse this ping. Do not individually ping users with the Helpers tag without their express permission.
cloud horizon
@honest barn well, can you answer it then?
honest barn
You should also figure out why that's what you want
cloud horizon
k=1.5
honest barn
because the problem doesn't explicitly say so lmao
umm
you need an integer boss
between 0 and 26
cloud horizon
o
honest barn
this has to exist cuz 2 and 3 are coprime
cloud horizon
but thats impossible tho
honest barn
lol wut
cloud horizon
how does that work in the equation tho
cloud horizon
Figure out what k gives 2k = 3 mod 26
honest barn
Because presumably what they do is take the nth letter of the alphabet
cloud horizon
yeah
rain stone
@honest barn it says ends a message not starts a message
cloud horizon
LOL
rain stone
So B -> L
honest barn
Oh fuck
cloud horizon
yeah b to L
cloud horizon
B
cloud horizon
if starting from 1 , yeah its #12
cloud horizon
mod 26. B=L.
honest barn
Oh nvm
I see
I thought since L is isolated
like no word is just "B"
but I guess the idea is that's their like signature
so we're good
cloud horizon
yeah just the letter.
cloud horizon
hmm...
honest barn
But I think such a k isn't unique
inside the constraints
So I guess if you test 6
and undo the message
you get some garbage
honest barn
I still don't even think that multiplication by 6 in mod 26
is injective though?
LIke is it even true that you can uniquely undo the encryption
I feel like some numbers get sent to by more than 1 element
actually this has to be true since it isn't surjective
so like
take 3
cloud horizon
hmm
honest barn
3 is not of the form 6n mod 26
so it doesn't hit every letter
so it has to send at least 2 to the same letter
because this is a function from the alphabet to the alphabet
cloud horizon
mhmm
honest barn
But
The same issue happens for any k such that 2k = 12 mod 26 I think
since k has to be even
so it isn't coprime to 26
This seems screwy man
cloud horizon
lol ikr
errant bear
why did you cross out how many points this test question is worth 
honest barn
uhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
cloud horizon
gotta save my honour on this one
rain stone
Oh wait this is a quiz?? I thought that was your name lmao
novel spire
So it is a quiz?
errant bear
novel spire
cloud horizon
online teacher was hella generous
honest barn
Bruh you're gonna get banned
novel spire
A quiz is a type of exam.
novel spire
Is it a question that will be on your exam?
cloud horizon
not on my exam no
issa bonus question my teacher got from the textbook
gave it early cause he nice like that
novel spire
But it's worth points on your exam?
novel spire
Same thing.
cloud horizon
bonus pts
novel spire
So points.
novel spire
So it affects your grade on the quiz.
novel spire
Then that is exactly the kind of thing to not do here.
full reef
Can anyone think of an injective function from $\mathbb{R}\times\mathbb{N}\to\mathbb{R}$?
vital dewBOT
user450-425*10^-9:
naive saffron
$$f(x,n)=\frac{\tan\inv(x)}{\pi}+n$$
vital dewBOT
Whoever:
naive saffron
@full reef
full reef
Ohhhh, that's really clever, yeah!!
Okay, what about an injective function from $\mathbb{R}^2\to\mathbb{R}$? I have one but it's not very mathematical
vital dewBOT
user450-425*10^-9:
honest barn
Honestly
a lot of these weird ones aren't very "mathematical"
if you're familiar with showing N x N is countable
you literally arrange out the stuff in a grid and zig zag through
you might be able to find a way to state it precisely
full reef
Yeah hahaha
My thinking for $\mathbb{R}^2\to\mathbb{R}$ was to define a function that takes a $(x,y)$ on the $\mathbb{R}^2$ plane and makes that the unique origin for a line on that plane at $45\degree$. Then, the real number line ($\mathbb{R}$) can be mapped onto that line, producing reals from the $\mathbb{R}^2$ plane... But does that work???
vital dewBOT
user450-425*10^-9:
Compile Error! Click the 
reaction for details. (You may edit your message)
full reef
45 degrees*
honest barn
I don't get it
this seems like a copy of R
for every single point in R^2
You want to map a point of R^2 to a point of R
not map a point of R^2 to something that like, is R
Anyway I think making an explicit function is gonna be hard as fuck
If it's countable you can do some stuff leveraging that but idk how to do it for uncountable
full reef
How do you mean decimal expansions?
honest barn
Normally this is writing a number as like
a sum of a_0 x 10^0 + a_1 x 10 +a_2 x 10^-2
And so on
You separate the ones, tens, hundreds,... places as that digit times a suitable power of ten
Similarly the points after the decimal place are like a_-1 x 10^-1 + ...
So take 147.63 this is 3 x 10^-2 + 6 x 10^-1 + 7 x 10^0 + 4 x 10^1 + 1 x 10^2
I’m not sure how this applies though tbh
full reef
Huh, interesting
I will have a play around with these, thank you
gah i dunno, everything I try doesn't work..
honest barn
Is there a reason you need an explicit map?
For a class or something?
If not there’s set theoretic reasons it exists
full reef
Yeah, trying to show that $|\mathbb{R}^2|=|\mathbb{R}|$. To do this, I am showing an injective function both ways (i.e., a bijection), which by Cantor-Schröder-Bernstein Theorem says they have the same cardinality. But I've just found another proof for this...
vital dewBOT
user450-425*10^-9:
full reef
Actually, no I haven't, never mind 😢
honest barn
Wel
So
There’s set theoretic reasons these have the same size
In terms of just cardinal arithmetic
And the absorptive properties of cardinal multiplication
full reef
Hmmm...I don't understand those words
I mean, I understand then in isolation
But put together like that
honest barn
Basically
For infinite cardinals
You know that alpha * beta = alpha
If beta is small enough compared to beta
And this actually implies R x R is the same cardinality as R
full reef
Hmmm...right. But I don't think my teacher would want us to use that fact (as we haven't technically learned it yet) 😛
I asked him after class and this is an email I got this evening:
honest barn
Oh yikes
Yeah I’m gonna tap out on this one
Also I like how it says |R| = |P(N)|
Which I believe, but is contentious
Do you like
Glue the two numbers?
Actually bmmm
I feel like i did exactly that before
Haha
I think this is the decimal expansion thing
full reef
I have no idea. I'm doing two other math courses and they're all like la dee da and then this one just hits us with uncountability and like 5 proofs in the first assignment
honest barn
There’s something you have to be careful about
About like non terminating stuff I think
Or what conventions you take for the decimal representation
full reef
You can find an injective function from (0,1) x (0,1) to (0,1)
@worthy palm That's actually a really good idea
Any suggestions as to what this function would look like?
honest barn
I think I did exactly this method of proof
full reef
Imma have dinner. I'll be back in 30 or so minutes. I appreciate people's help on this 🙂
honest barn
Viburnum isn’t there some convention you need to pick for uniqueness on this?
It’s something about like repeating digits I think
Like is it 0.8 or 0.799999999...
I forget if it’s only for repeating 9s though
weary tiger
@stray reef now can you tell me
stray reef
ok this is a marginally less unfitting channel
anyway you're asking me if a springer book is good
weary tiger
i mean not all springer books are good?
stray reef
and my instinct after reading the toc would be to say yes
frosty epoch
yo heres a question
how many possible sudoku grids are there which have the anti-knight constraint (cells a knights move apart do not contain the same digit)
no idea how to approach this but id imagine it decreases the count significantly
cursive steppe
this is a dumb question but...
what exactly is discrete math? what does it entail?
I'm currently signed up to take an intro to discrete math course at my college but I'm not too sure what to expect
stray reef
it varies from institution to institution but it's probably some mix of combinatorics, basic set theory, and introduction to proof
woeful jewel
If you are a computer science major discrete math is required. But it covers intro to writing proofs, set theory and a small introduction to combinatorics
obtuse minnow
Hewwo. I have a question about Posa's Theorem. I'd just like an example or two on how it is applied.
weary tiger
banned for the hewwo
obtuse minnow
please tell me you are joking?
buddy I'm going to give you 5 minutes to 1) prove you are a mod and 2) tell me if you're joking. I don't take kindly to empty threats :). I have to deal with plenty of them day to day.
sacred dune
XD overreactions are funny
mint shore
i have a question about a proof
this is induction step
and that part kinda confused me
it's probably a typo but i wanna make sure
since it determines at the beginning that a(i) = a + i cdot d
then a(0) would be a + 0 cdot d = a
as seen in the next step
(sorry for the greek slide)
quaint star
That a_1 should definitely be a_0
mint shore
yes ty for that
one more thing
i get how (k+1)a gets created
you multiply the bracket w k/2
then have a be common factor
but what about that?
breaking the bracket up you get
nvm got it
kd common factor
more induction stuff: can anyone explain to me the gist of strong induction?
i don't get the idea behind it
stray reef
in weak induction you use P(k) to prove P(k+1)
in strong induction you use P(1), P(2), ..., P(k) to prove P(k+1)
mint shore
so like
weak induction: prove for one number (usually 1), then take arbitrary k and then prove for k+1
strong induction: prove it for literally every number in the field before k
then k
then k+1
stray reef
no
strong induction is strong because you use more hypotheses
P(k) => P(k+1)
vs (∀j<k)(P(j)) => P(k)
sacred dune
You're not proving it for everything before k, but letting it be true to show that it implies that it is true for k
So that you can then apply the familiar domino effect
You still only have to prove it for one number, the only difference is the assumption is bigger
mint shore
so instead of saying
say, i want to prove something for n >= 1
weak induction would usually be
prove for 1
suppose for k >= 1 it's true
prove for k + 1
so strong induction then is
prove for 1
suppose for k >= 1 and every number before k that what i'm trying to prove is true
prove for k + 1
true hare
Trying to work through this, started off by using f(1),(2) and (3) to look for potential patterns, but am stumped, can anyone help? <@&286206848099549185>
sick swallow
which question
also how can u be stumped from not seeing the pattern, it is pretty obvious
true hare
i saw the pattern when i tried it for a