so iirc khan doesn't have one :/
#discrete-math
weary tiger
why not just grab a book
fierce osprey
I could, but sometimes I lose momentum with those unless it's funny 
(or something)
modern dew
let n be in N .....let [m] belong to Z/nZ its rest class ring...show that : ord([m])=n/gcd(m,n)
sorry its german had to translate..if its not clear i can explain
?
ord is order
ggt is gcd
unreal stump
Do you know any group theory?
modern dew
scratchin the surface
unreal stump
Do you know what order of an element is?
modern dew
yeah...the time i must combine it to reach the neutral elemnt or 1 mod n
unreal stump
Let o(a^m) be k
modern dew
i think so
modern dew
?
unreal stump
o(a) is notation for order of a
So you get o(a) divides mk and m divides mk
Which means lcm(o(a),m) divides mk
modern dew
ok even tho i didnt totally get it but ill try to prove that
modern dew
If a^m=1 then ord(a) has to divide m
but m is ord of a right??
unreal stump
No,m is some element satisfying that
For example take Z/2Z a=1 ,m=6
1+1+1+1+1+1=0
modern dew
i just dont get the difference between m and k
modern dew
lets say o(8) is like o(2^3) with 3 being the m....then k is o((2^3)^k)
tired basalt
What is discrete maths?
modern dew
should a be prime?
tired basalt
Integers are different and discrete but how?🥲
unreal stump
lets say o(8) is like o(2^3) with 3 being the m....then k is o((2^3)^k)
Let a=2 ,m=3
Then o(a^m)=o(8)
tired basalt
🥲
modern dew
okkkk now i kinda get it....i will try to do the other questions and will probably ask you you again if i cant figure it out....thanks alot mate@unreal stump
tired basalt
Pls help me also🥲🥲
unreal stump
What is discrete maths?
I have a very simple definition for discrete math
If induction helps you solve a problem,that problem is discrete
tired basalt
Ok first i will study induction then i will come to you
Induction is used for proofs right?
unreal stump
Yes
tired basalt
Buncho brother how much maths you know?
unreal stump
And by induction,I don't just mean induction
last timber
what about transfinite induction
unreal stump
That's transdiscrete
last timber
on complete well ordering
last timber
also @unreal stump is number theory discrete?
last timber
I am a noob cal student 🥲🥲🥲🥲what is this thing
induction on sets that are larger than N
unreal stump
also <@!734020733595942952> is number theory discrete?
Kind of
last timber
also buncho may i suggest us having fun anal
last timber
Kind of
so prove by induction that number p is prime
where p is 1932128381289312839123819231293919293213431
last timber
,w factor 1932128381289312839123819231293919293213431
vital dewBOT
last timber
last timber
Such a big number
by bruteforce
tired basalt
Brother how much maths you know?
last timber
ok @unreal stump prove that number x which i will say after you do proof is not prime
unreal stump
Not much
unreal stump
ok <@!734020733595942952> prove that number x which i will say after you do proo...
Analytic NT moment
tired basalt
You know calculus?
tired basalt
Can you prove the log base change formula
Like (log base a b)= log b/loga
This one
tired basalt
Bro pls do it
unreal stump
Origins
no foundations
tired basalt
I am not able to think of one
last timber
>Origins
>no foundations
foundations are in upper left
last timber
yw
errant bear
okay
granite sinew
Is there any web Calculator that can gives answer for logic step by step?
for example:
( ¬ p ∨ ¬ q ∨ ¬ R ) ∧ ( ¬ p ∨ ¬ q ∨ R ) ∧( ¬ p ∨ q ∨ ¬ R ) =p ⇒ ¬(q ∨r)
or (a-b) ∨(c-b) = (a ∨c)-b
tranquil flint
Is n choose 0 + n choose 2 + n choose 4 + .... (all even choose) = 2^n / 2
say n is even
cerulean wind
@tranquil flint yes. if you have a finite set X then the number of even element subsets and the number of odd element subsets are the same and they partition the power set P(X) into two disjoint subsets.
cerulean wind
or you could argue inductively
tranquil flint
tyty
simple nova
errant bear
yes
tranquil flint
How many lattice paths go from (0,0) to (a,b) that do not cross above the line y=x?
cerulean wind
do you mean northeast lattice paths ?
tranquil flint
yess
cerulean wind
https://math.stackexchange.com/questions/1569633/catalan-numbers-number-of-lattice-paths-from-0-0-to-a-b-ab
this may help
last tundra
Hello, I need help with making a combinational element diagram out of a Boolean function:
¬(x∧y∧z∧u)
I need smth like this diagram
cerulean wind
you can find it recursively
would be interested in hearing how that works
weary tiger
Can anyone suggest me a introductory book for discrete mathematics?
cerulean wind
#discrete-math message
i recently recommended this book. i thought it was good.
fierce osprey
by bruteforce
more or less
the time it takes a computer to count to 2^32 is not even funny
so you need a couple extra tricks
cerulean wind
i tried doing that. got the recurrence relation p(a,b)=p(a,b-1)+p(a-1,b-1) where p(u,v) is the number of paths from (0,0) to (u,v) that don’t cross the line y=x with initial conditions p(u,0)=1.
how would you recover the explicit formula? generating functions?
warm wren
Does anyone know which books to prepare for the Mathematics Olympiad in the field of number theory?
If someone knows which books, please write privately, I would be very happy. Thank you 🙂
pallid lintel
im struggling with a proof that shows vertex cover is NP complete. It works by using these things called gadgets that map 3SAT formula to a vertex cover. i.e we have vertex cover iff a particular 3cnf formula is true. Given any graph with a k vertex cover i don't know how to find the gadgets and truth values of the 3cnf formula
gritty crescent
Does anyone know which books to prepare for the Mathematics Olympiad in the fiel...
Check the latest pinned message in #books-old , someone reviewed a lot of number theory books at that level. AoPS seems to be the norm for greater part. There's a dedicated math olympiad server-you can find the invite in #old-network .
serene portal
anyone wanna work through diestel's graph theory text with me this summer? I need to learn the material for a research job and I think it'd be good to have some people so that we can keep each other accountable
tranquil flint
If G is a simple planar graph with 10 vertices, how can we prove there exists v1, v2 such that d(v1)+d(v2) is less than or equal to 9 using PHP
stray reef
PHP?
stray reef
hm
tranquil flint
if theres m edges, then
2m = sum of all deg(v) over n?
but idk what to do w that
and what graph being planar does
stray reef
planarity will mean we can't have too many edges
ah wait i think i got it
since G is planar it means we get euler's characteristic formula: V - E + F = 2
now suppose that d(v) + d(w) ≥ 10 for all vertices v, w in G
we then get that the sum of all degrees must be at least 50
do i need to explain how?
tranquil flint
now suppose that d(v) + d(w) ≥ 10 for all vertices v, w in G
do you mean greater than 10?
for like contradiction?
stray reef
no, i mean ≥ 10
tranquil flint
O nvm
stray reef
or to be more direct about the contradiction, > 9
stray reef
there are 10 vertices in your graph
split them into five pairs and apply the inequality to each pair
so then by the handshake lemma we get that there are at least 25 edges
stray reef
sum of all degrees = 2 * edge count
tranquil flint
ohh
stray reef
you wrote it out earlier
tranquil flint
okk
stray reef
10 - E + F = 2
...
this route may not be as productive as i thought
we get that F = E - 8, but this doesn't give us any useful info
tranquil flint
2-10+25 = 17 = F?
tranquil flint
I have one thm i see in my lect notes im allowed to use that might be useful
stray reef
please share
tranquil flint
if n >= 3 and G is planar then G has at most
3n-6 edges
and 2m >= 3f
is another one
tranquil flint
for planar graphs
stray reef
30 - 6 = 24
and i concluded up there that G must have at least 25 edges
so that bound is violated
stray reef
it's a contradiction
tranquil flint
o wait 2m = sum of deg v <= 6n - 12
stray reef
|E| ≥ 25 as i derived above, but |E| ≤ 24 by your theorem about planar graphs
can't have both
tranquil flint
OH
stray reef
therefore the assumption that d(v)+d(w) ≥ 10 for all v, w in G is false
tranquil flint
Oh ok thank you so much
Just wondering i noticed this aswell and would this be valid argument too
2m = sum of deg v <= 6n - 12 = 48
"now suppose that d(v) + d(w) ≥ 10 for all vertices v, w in G
we then get that the sum of all degrees must be at least 50" is what you said
stray reef
sure
tranquil flint
would that work too?
stray reef
that's just what i said but doubled
weary tiger
We have the two languages :
so Why L1 is
isn't L1 just the negation of L2 , AKA L2 cap ?
pale epoch
the complement of L2 will also include stuff like 'ababa'
weary tiger
ohh i see
gritty crescent
I tried to enumerate 11 (all?) non-isomorphic simple graphs with 4 vertices. Do these look good, or are any of these isomorphic?
Also, if these work, is there a systematic way to enumerate them for a given number of vertices? And to determine if they are isomorphic?
gritty crescent
last timber
Also, if these work, is there a systematic way to enumerate them for a given num...
no there is not
gritty crescent
Okay, I cannot find any graph isomorphic to this one
last timber
there is no good algorithm for graph isomorphism afaik
gritty crescent
no there is not
gritty crescent
there is no good algorithm for graph isomorphism afaik
It need not be computationally efficient, just one that works
And covers possibilities
last timber
The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. ```just try all possible bijections
gritty crescent
Hmmmm
last timber
It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level.[1] At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.[2]
gritty crescent
Which means manually I'll likely miss cases as number of vertices grow
last timber
See the thing with brute force is that it is not systematic
why it is not
label vertices of both graphs
try all possible bijections
gritty crescent
Oh, my question is more about enumerating graphs with given constraints
last timber
i mean there are also some invariants
to check for isomorphism
(like obviously number of vertcies and edges)
gritty crescent
Like here I want to find a way to list all graphs with given number of vertices which are simple and non-isomorphic
last timber
well again brute force seems to work
last timber
yes but i cannot come up with any satisfying
i mean i can take out of my ass some algo
but would it work?
gritty crescent
Hmmmm
last timber
while brute force being computationally inefficient is guaranteed to work
like look
Let G be set of all possible graphs with given set of vertices
cerulean wind
like looking at all possible sub-graphs of K_n
last timber
let G_n be subset of G s.t n is amount of edges in this graph
obviously G_n and G_m do not contain isomorphic graphs if n != m
thus you check only those who are in G_n
take some arbitrary and compare to it
repeat until list is exhausted
@gritty crescent something like that manan
(make me yellow)
gritty crescent
<@!697848465819959388> something like that manan
Oh, okay. Some of the ideas here make sense.
gritty crescent
(make me yellow)
This idea made no sense, seems very tangential to the problem at hand.
gritty crescent
I'll make you yellow if you win a Fields Medal.
gritty crescent
👎
livid drum
@manic dome
It is true both classically and intuitionistically.
Here is how you know it to be true classically:
By brute force, take all possible 8 configurations of truth values of p, q, r.
The two formulas will have the same truth evaluation.
Eg. here is one particular evaluation:
Take the model where p=q=r=true.
The lhs is true implies (true or true)
= true implies true
= true.
The rhs is (true and (not true)) implies true
= (true and false) implies true
= false implies true
= true.
So in this model, the lhs=rhs.
Perhaps to develop intuition , ask yourself this question:
”When is an implication false?”
It is true in all cases except when the antecedent is true and consequent false.
So the LHS is false only when:
p is true, and **q or r ** false— which is equivalent to:
p is true, q is false, and r is false.
This means the lhs is true in all posssible configurations except that one.
Think about the rhs, this way.
simple ingot
truth tables and laws of logic are fun
manic dome
Can someone help me with this question
cerulean wind
for a) what have you tried?
cerulean wind
the sets A1 and A2 are disjoint and infinite. can you think of two other disjoint, infinite subsets of the natural numbers?
manic dome
no I can't think of any
cerulean wind
the even and odd numbers? positive and negative? prime and not prime?
anyway, call $E$ the set of even integers and $O$ the set of odd integers. note that $E$ and $O$ are countable. since $A_1$ is countable, there is a bijection $f_1:A_1\to E$ and similarly, there is also a bijection $f_2:A_2\to O$. you need to define a bijection $f:A_1\cup A_2\to E\cup O$.
vital dewBOT
coycoy
manic dome
So all I need to do is prove it's bijective for the f1 and f2 correct?
cerulean wind
no. f_1 and f_2 are already bijective
u need to make a function $f:A_1\cup A_2\to E\cup O$ using $f_1$ and $f_2$
vital dewBOT
coycoy
manic dome
that's the struggle I'm having, making the function
cerulean wind
i’ve given you a pretty good start, could u make an attempt at something using what i’ve given u?
cerulean wind
yw. the subscripts are meant to be suggestive of the function you should make.
manic dome
wdym by subscripts?
cerulean wind
the numbers labeling the two functions f_1 and f_2. those are called subscripts.
manic dome
@cerulean wind I'm having some trouble with trying to create the function
cerulean wind
@manic dome okay, how about we try $$f:A_1\cup A_2\to E\cup O$$ given by $$f(x)\coloneqq\begin{cases}f_1(x)&\text{ if }x\in A_1\f_2(x)&\text{ if }x\in A_2\end{cases} $$
vital dewBOT
coycoy
cerulean wind
Notice that $E\cup O=\mathbb{N}$ so we need only show that this map is bijective. then you will be done. Ill do surjectivity. Let $n\in\mathbb{N}$. Then $n$ is either even or odd. If $n$ is even, then since $f_1$ is surjective, we know there exists an $x\in A_1$ such that $f(x)=f_1(x)=n$. The case where $n$ is odd is similar, so $f$ is surjective.
vital dewBOT
coycoy
manic dome
@cerulean wind how can I go about solving 5,b?
I understand what's going on, but we don't have a formula to use so I'm confused how I can use induction to prove thi
cerulean wind
so you know that the disjoint union of one set is countable. bam. theres your base case.
suppose that the disjoint union of A_1,A_2,...,A_n is countable for some natural number n, where each A_i is countably infinite. you want to show that the disjoint union of A_1,..,A_n,A_n+1 is countable, where each A_i is countably infinite.
you know that the disjoint union of A_1,...,A_n is countable and A_n+1 is countable by hypothesis.
so then use part 5a), since we have two disjoint, countable sets
manic dome
But if A1 is just all the even natural nubmers and A2 is all the odd natural numbers, how exactly can I prove An is countable infinite
that part I'm a bit confused by sorry
@cerulean wind
cerulean wind
you seem to be confused. A_n is countably infinite
you are not trying to prove that
manic dome
oh I mean An+1
cerulean wind
A1 and A2 were arbitrary countable sets.
perhaps that question may have been written in a misleading way
but A1 and A2 might as well have been called X and Y
think of 5a) and 5b) being two completely separate problems, just 5b) generalizes 5a)
manic dome
alright but this goes back to basically my original question on how exactly can I use induction to prove that statement
cause induction, I'd choose an x value and plug it in the function right,
but since there isn't an actual function to solve I'd have to use proofs instead
that's the part I'm just confused with
cerulean wind
are wyou with me up until this point ?
manic dome
Yeah I'm following, but I'm just confused where induction is being used/gonna be used
cerulean wind
ok. its coming up
manic dome
alright,
vital dewBOT
coycoy
simple ingot
Why are you so fluent with latex lol
cerulean wind
Why are you so fluent with latex lol
a lot of 25+ page hw assignments last year
vital dewBOT
coycoy
manic dome
yeah
vital dewBOT
coycoy
manic dome
**coycoy**
I did not know you can do something like this
cerulean wind
oh
simple ingot
I did not know you can do something like this
wow, so insightful technique!
manic dome
well thanks a lot for help coycoy
vital dewBOT
coycoy
manic dome
alright thanks
cerulean wind
well thanks a lot for help coycoy
np : )
timid spear
what is that symbol between P and Q means ?
last timber
P proves Q
toxic ferry
Can someone help me try to start part B?
I was thinking it's 7C5 instead of 8C5 since we're guaranteed to lose a dude
sour arrow
Ugh party's
Let's say A and B are feuding. How many parties involve A? How many involve B? How many involve neither?
The sum of those three cases is the total number of parties
timid spear
P proves Q
oh thanks
toxic ferry
The sum of those three cases is the total number of parties
Then it would be 6C5 + 2* 7C5 for the guys
weary tiger
so:```
f : N -> N
f(x) = x * 2
x can only be positive number(but isn't every positive number ofc) ?oh i mean y
sorry
y = f(x)
nice
f(x) = x/2
f(1) = 0.5 This would be consider invalid solution right?
f(2) = 1
f(3) = 1.5 This one also?
poggers
stray reef
f: N -> N, f(x) = x/2 is not a valid function definition
weary tiger
stray reef
if you want half-integer outputs then your output set must be a set that contains half-integers
but saying f: N -> N means the outputs of f must be natural, and f(x) = x/2 goes directly against that
vital dewBOT
Notaboredguy
stray reef
yes
stray reef
no
vital dewBOT
Notaboredguy
stray reef
you wrote n^n, not n^2
weary tiger
oh ye i meant n^2 sorry
weary tiger
I am learning #discrete-math just so i don't have to write code on paper ;))
$\sum_{n=1,m=2}^{10}n^m = ?$
vital dewBOT
Notaboredguy
weary tiger
is this valid?
stray reef
it can be given a valid interpretation
last timber
i mean if you assume that both n and m vary up to 10 you prolly can do this, but otherwise this is not really readable
stray reef
as $\sum_{n=1}^{10}\sum_{m=2}^{10} n^m$
vital dewBOT
Ann
exotic ivy
Im totally new to discrete math
What does it mean for the statement in the parenthesis?
I dont get how logics and arithmetic can be mixed in that way
light ginkgo
The set of natural numbers that are a sum of two primes.
Set of natural numbers n such that there exists prime numbers p and q such that n=p+q
exotic ivy
wat. but i dont understand how you see the and operator can just be equal to an arithmetic p+q
oh
light ginkgo
The and operator isnt equal to anything.
exotic ivy
so the and operator takes precedence over the equal
because what im understanding is (p is prime and q is prime and n) = (p+q)
light ginkgo
Im not sure what youre talking about. You have 3 statements that are combined using and operator
No its and (n =p+q)
light ginkgo
No worries!
pale epoch
the multiplication in rings is distributive over addition
umbral iron
how to find the complementary of a relation ? 🤔
pale epoch
using the definition
jagged junco
Anyone?
What's the biggest size of a subset of {1,2,3,...,2020} that doesn't have 2 numbers that their sum is 2021?
It'd be the same asking
Find the biggest size of a subset of {1,2,3,...,2020} that sum of each 2 numbers is 2020 at most.
last timber
pigeonhole principle ig
last timber
It'd be the same asking
Find the biggest size of a subset of {1,2,3,...,2020} th...
also this is not equivalent
since {2020, 2019} satisfies condition
but sum is greater then 2020
but anyway
first of all consider subset contaning only even numbers
that is {2,4, ..., 2018, 2020}
it does not produce sum 2021
jagged junco
also this is not equivalent
you're right my bad
last timber
adding anything to it will result in violation
so {2,4,..., 2020} is potential option
consider coming up with another possible subset
jagged junco
yes in case of even numbers 2021 isn't possible like you say
but is it the best approach to tackle this question?
to tackle it with different type of sbusets
last timber
one option is {1,2,..., 1011}
stray reef
pigeonhole principle
jagged junco
pigeonhole principle ig
how does it apply here
stray reef
split 1:2020 into 1,010 pairs: {1,2020}, {2,2019}, {3,2018}, ..., {1010, 1011}
last timber
^
stray reef
a set of more than 1,010 numbers will necessarily include both numbers from some pair
weary tiger
To learn recurrence relations, does one need to know counting (probability)?
jagged junco
a set of more than 1,010 numbers will necessarily include both numbers from _som...
I understand
thank you Ann and howtogothelp 🙂
last timber
To learn recurrence relations, does one need to know counting (probability)?
you do not need probabiltiy for recurrence
last timber
you may need some parts of it
weary tiger
any sort of stats?
last timber
no
weary tiger
Ok
last timber
you may need some parts of it
but not rlly much
umbral iron
using the definition
can u send it to me ? i cant find it for some reason im so lost
pale epoch
I don't have your definition
last timber
intuitively i would define it as
xR^Cy iff (x,y) not in R
jagged junco
Help?
How many linear homogeneous recurrence relations of order 10 (with constant coefficients) that their characteristic polynomial roots are exactly {1, 2, 3} exist? (Meaning there aren't any other roots)
stray reef
instead of the recurrence relations look at their characteristic polynomials
which must be $(x-1)^m (x-2)^n (x-3)^p$ with $m, n, p \geq 1$ and $m+n+p=10$
vital dewBOT
Ann
jagged junco
Right. Is it okay to say m+n+p = 10 ? Isn't it m + n + p <= 10?
stray reef
our recurrence relation is order 10
therefore its charpoly will necessarily have degree 10
jagged junco
okay thanks for pointing out
and basically now I need to find how many solutions this have to find the number
I know what to do next, thank you 😄
ocean island
Can someone explain what that means?
I assume it means that for the function x^2, x can be any real number and (x^2) is any nonnegative real number and 0.
However, for the function g, how can the result be any real number ?
pale epoch
that's not the claim
just that the result is a real number, it does not mean that any real number is attained
weary tiger
However, for the function g, how can the result be any real number ?
R is just the range of the function g. If you want to be more precise, R+ is its image (the values of the range that get attained by the function)
The image is always a subset of the range of a function
The domain / image were defined in a way that matches the composition fog
deft dock
i was wondering if this was correct?
pale epoch
the negation is not correct
deft dock
the negation is not correct
would it instead be "There exists a real number a and b, such that if a<b then a^2>b^2 ?
pale epoch
thats almost the same thing, but also no
deft dock
maybe
pale epoch
the negation of "A implies B" is not "A implies not B"
deft dock
the negation of "A implies B" is not "A implies not B"
confusion
i was following this word for word
vital dewBOT
Lochverstärker
pale epoch
wait, you did not follow your screenshot word for word
your formulation doesn't even include the word and
you made it an "if ... then ..." statement
(which is not the same meaning)
deft dock
oh wait
bruh
There exists a real number a and b, such that if a<b and not a^2<b^2
then ig?
pale epoch
no
pale epoch
yes
deft dock
There exists a real number a and b, such that a<b and a^2__>__b^2
pale epoch
yes, thats correct
pale epoch
this is also exactly what your counterexample is
deft dock
are we just negtating Q(x)
pale epoch
you showed the existence of such a and b
the thing is
we are negating $P(x) \implies Q(x)$
vital dewBOT
Lochverstärker
pale epoch
which is equivalent to $\neg P(x) \lor Q(x)$
vital dewBOT
Lochverstärker
pale epoch
and the negation of that is then $P(x) \land \neg Q(x)$
vital dewBOT
Lochverstärker
pale epoch
(you can verify all of this using truth tables)
it basically means that you have to produce a counterexample
deft dock
ahhhh okay makes more sense
pale epoch
if you look at your original statement "if a < b then a^2 >= b^2", this is true for e.g. a = 3, b = 1
since the premise is false
but this isn't a counterexample to the statement you wanted to disprove
deft dock
so if the premise if false, and the conclusion is true then it isnt a counterexample
we wnat something where the premise if true and the conclusion is false?
i thjnk?
pale epoch
i just wanted to clarify why your solution was false
because the statement you gave is true for real numbers a, b that arent counterexamples
and thats not what how we want the negation of a statement to behave
but yes, what you said is correct
deft dock
ah okay i kinda get it
pale epoch
what you said is good way to think about it and remember the negation of a "P implies Q" type of statement
a counterexample has to satisfy P and not Q, otherwise ... well, it isnt a counterexample
deft dock
could someone check if these are right?
pale epoch
sure, that works
deft dock
does this work or?
or do i have to put "if r is rational, then -r is rational"?
i assumed i didnt because doesnt stating "r is in the real number domain" imply "r is rational"?
wait no
man i felt so stupid saying that
this should be correct
vital dewBOT
Sideurk
weary tiger
this should be correct
No i dont think thats what you were supposed to do
deft dock
**Sideurk**
oh.
weary tiger
I mean why use the words if then
Use symbols
Or like you can just skip the r in R part
deft dock
and just use the upside down A?
weary tiger
Just q in Q implies -q in Q no?
weary tiger
So you cant use implies?
deft dock
idk
weary tiger
Actually idk this problem is fucking stupid idc and im typing On a Phone so I double dc
deft dock
confused cuz i tried to use symbols one time and she corrected it to words
errant bear
idek what that says
deft dock
essentially she replaced symbols with "if, then"
errant bear
thats fine
deft dock
what about this
okay so then this works?
deft dock
could someone check this? i have no clue what im doing when it comes to proofs
cerulean wind
looks good to me
deft dock
looks good to me
wait actually?
cerulean wind
yea man
deft dock
cerulean wind
deft dock
<:pandaHugg:513069003120574464>
wait would i have to specify how t is an integer?
also is this one correct?
and to the last statement (hence...), i added "by the defintion of even"
is that fine?
errant bear
wait would i have to specify how t is an integer?
no. you dont have to prove integers are closed under add/mult
you shouldnt use k twice btw
deft dock
you shouldnt use k twice btw
like for 11 and 12 or just 12?
deft dock
ah okay lemme redo
errant bear
and to the last statement (hence...), i added "by the defintion of even"
also you dont need to, it should be clear to the reader
deft dock
okay
wait hold on
if i use different letters
it becomes odd...
unless im doing something wrong?
errant bear
ur gonna have to do smth else
deft dock
so something else
hmm
okay but before i do something else
this is right so far right
deft dock
???
errant bear
6n=2(3n)
which is even so it doesnt matter what n is
so you can just focus on the m^2+3 part for now
do u follow
errant bear
oh id assumed you musta already proven/shown that earlier sometime
any integer times an even is even
and also, even+even=even
idk this is just how id go about doing it, you can ignore me if ur way makes more sense to u lol
deft dock
man idek what im doing in the first place
my prof just gave one example on proofs a
and nothing about mechanics
so im just copying that video
errant bear
lol, okay well
we can do it your way by plugging in, its fine
the +7 term is wrong
errant bear
gud
also, the substitution with t can be done with less lines just like
continue from line 4 with "=2t for some t"
to save space
deft dock
continue from line 4 with "=2t for some t"
line 4
substitution one?
wait no facotorization?
errant bear
the one starting with "by facto"
deft dock
ohhhhhhh i see what you are saying
errant bear
yea, just add =2t for some t
deft dock
By factorization, 〖4k〗^2+4k+4+12j=2(〖2k〗^2+2k+2+6j) = 2t for some variable t
?
and then delete everything else
errant bear
sure
deft dock
except "hence..."?
errant bear
but you're still finding a way to add more words lol
deft dock
errant bear
why not in the shower 
cerulean wind
show that if r and c are rational, then cr is rational. then show that if a and b are rational, a+b is rational.
your question falls out as a special case of those two facts
deft dock
show that if r and c are rational, then cr is rational. then show that if a and ...
how would i show c is rational?
cerulean wind
what do you mean? you are assuming c is rational
" if r and c are rational, then cr is rational"
deft dock
oh i dont have to show c is rational?
cerulean wind
no.
deft dock
and wait why i am using c?
cerulean wind
nvm. lets try and work through what you have got already
can you write out what 3r+4s would be, given that r=a/b and s=c/d
cerulean wind
thats what r and s would be. add the two fractions together
cerulean wind
? what is that
deft dock
(ad+bc)/bd
cerulean wind
yes, but im asking you to add 3a/b and 4c/d
cerulean wind
yes. that fraction is equal to 3r + 4s, so you are done, because you have written 3r + 4s as a ratio of two integers
cerulean wind
i have no idea what that stands for
deft dock
yes. that fraction is equal to 3r + 4s, so you are done, because you have writte...
so then what would i write all the way at the end?
is there like a theorem?
cerulean wind
its really similar to what is written in the image you sent. since 3ad + 4bc is an integer, and bd is a non-zero integer, then 3r + 4s is rational
deft dock
ohhhhhhhhhhhhhhhhhhhhh
and we know bd is a non zero integer because r and s are rational numbers
i think?
cerulean wind
yea, because r and s are rational number, then neither b nor d are 0. you have stated that in your proof attempt
cerulean wind
im not familiar with it if it is
deft dock
hmm im guessing not reading its definition
cerulean wind
yes it is called the zero product property
deft dock
but how do we know 3ad + 4bc is an integer?
deft dock
yes it is called the zero product property
oh so it is?
cerulean wind
because integers are closed under addition and multiplicaton
you should be able to assume this fact
cerulean wind
closed meaning that if i add two integers n and m, then the result n+m is also an integer. similarly for multiplication
cerulean wind
would say that bd is a non-zero integer by ZPP, but yes that looks fine as is
cerulean wind
np
deft dock
wait no god damn it man
she really gave us another one
i didnt even see that one after getting excited for finally finishing this
lemme try first doe
cerulean wind
lol aight
deft dock
wait so
do i start completely from scratch?
or wait
can i just say that since t is rational
and 3r + 4s is rational
a rational times a rational is always rationa?
is there a name for that justification
?
errant bear
closure?
deft dock
but like how would i start doe
suppose 3r+4s is rational?
doesnt that imply i have to prove that agin?
errant bear
the question tells u to assume its rational from part a
so you can just set it to p/q or smth
cerulean wind
you want to say that since a and c are both integers, then ac is an integer as well. otherwise it looks good
deft dock
you want to say that since a and c are both integers, then ac is an integer as w...
oh wait
ohhhhhhh
so this
cerulean wind
yup
deft dock
thank you so much man 
cerulean wind
np dawg
deft dock
im boutta withdraw from this class anyways but like wtv
shoulda retaught taking this as a de class lmao
cerulean wind
whats a de class?
deft dock
dual enrollment
cerulean wind
nah, stick with it! it gets easier, trust me
deft dock
i think im going to have to doe man
the videos the prof gives out are terrible
its logic based, so one example doesnt suffice
i have a test tomorrow and an ap stat exam on the 29th and im underpreppared for both
and i wanted to study for comp math but discrete is in the way
cerulean wind
oh, well good luck either way
deft dock
subtle ermine
Guys, I'm a bit confused by the conditional proposition.
p -> q
if p, then q
Now I'm confused by when p is false
**Why is it that if the antecedent is false, then the proposition is always true? **
subtle ermine
After doing some research
Is it because if p is false, then we have no basis on which to evaluate q.
Like if I say if a word is a pronoun, then it is a noun
My word is Bike
Bike is not a pronoun, but it is a noun
Or If say my word is which
Which is not a pronoun, but it is a noun
So in this case the first part of the proposition doesn't matter now, because the second part could be true or false
And that's why we just assume it's true as a vacuous truth?
last timber
@subtle ermine consider example with politican which promises that he will repair road if he gets elected
if he gets elected and he repairs the road he obviously said truth
if he gets elected and he does not repair the road he lied
but if he is not elected, then we cannot say that he lied regardless of was road repaired or not
so we say that he vacuously said truth
sour arrow
@subtle ermine
I can come up with a few reasons why this is the definition
But, ultimately, this is just the definition.
F → _
Is a true statement, simply because that's how we define →. You might notice that this slightly disagrees with how we think of it in English. That's okay though, because math is better than English.
jagged junco
How many different graphs that have 5 vertices and 5 edges that has exactly 1 circle with 3 edges?
stray reef
different up to graph isomorphism?
stray reef
...is there an image on its way?
last timber
why you are picking vertices only out of circle
stray reef
let me just make a picture
last timber
nvm
jagged junco
let me just make a picture
stray reef
jagged junco
they're the same imo no?
stray reef
i'm not asking for YOUR opinion, i'm asking for the PROBLEM's opinion
or the book's
because your wording isn't clear
jagged junco
How many different graphs that have 5 vertices and 5 edges that has exactly 1 ci...
they didn't point this out, that was the whole question
stray reef
and when i asked whether or not the graphs should be counted up to iso, you answered unhelpfully
if labelings don't matter then im pretty sure only these three fit your criteria
jagged junco
hmm
cerulean wind
assuming they are simple graphs
stray reef
i'm trying my best to combat the imprecision in your book's problem statements
strange grotto
okay this is what i got
what is ZPP?
cerulean wind
what is ZPP?
zero product property. it states the the product of two non-zero elements is again non-zero, or in other words, ab = 0 iff a = 0 or b = 0. this is also known as the non-existence of non-trivial zero divisors. there is a wikipedia page if you look it up
strange grotto
zero product property. it states the the product of two non-zero elements is aga...
okay
so how would you say if a,b are non-zero integers then ab is non-zero integer too?
cerulean wind
ab != 0 iff a != 0 and b != 0
strange grotto
i understand this
i posed a different question
prove that ab is integer if a,b are integers
cerulean wind
what is your defintion of an integer? how are you defining ab? the question is a bit unclear as of now
strange grotto
ab= a×b
last timber
Suppose ab is not an integer, then show that a or b is not integer
strange grotto
oh got it
strange grotto
Suppose ab is not an integer, then show that a or b is not integer
i think the correct reason is:
multiplication is closed under set of integers
last timber
well yes it is
strange grotto
okay
last timber
i mean i dunno how you define integers
do you construct them as equivalence classes or what
strange grotto
idk maybe coycoy can answer
cerulean wind
this typically isnt something that you prove. one definition of the integers is as equivalence classes of natural numbers, and the binary operations of + and * are defined so that they are closed under + and *
strange grotto
this typically isnt something that you prove. one definition of the integers is ...
yeah okay.
and definition of natural numbers?
strange grotto
it is gt yes?
timid elk
Could someone take a look at this paper's section 2.2 (pages 6-7) and let me know if "maximal degree of G" simply refers to what is usually "maximum degree of a graph" or not? I'm not a native English speaker and this is the first time I come across this term. Googling isn't helping either, and it's really important to know what this number is.
https://arxiv.org/pdf/1302.5843.pdf
talking about this part btw
last timber
i would assume that unless otherwise specified/context gives information we have usual meaning
jagged junco
What's the number of automorphisms of this graph?
is it 2?
because you can replace 1 with 2
pale epoch
that argument shows it's at least 2
stray reef
1<->2 is not the only non-identity automorphism of this graph
jagged junco
1<->2 is not the only non-identity automorphism of this graph
what are other possible options?
stray reef
you could swap 1 and 3 instead
stray reef
any permutation of 1, 2 and 3 yields a valid automorphism
vertices 4, 5 and 6 must remain fixed simply by looking at their degrees
jagged junco
then it would be 3! right
stray reef
yes
jagged junco
A dice is thrown 10 times. In how many results are shown exactly 3 of the numbers 1, 2, 3, 4, 5, 6?
hybrid crown
jagged junco
but how do I make sure I get exactly 3 of them
3^10 means there are 3 options not necessarily forcing each one of those 3
you know what I mean?
weary tiger
its 6C3 * (3^(10) - (the results with just one of those + the results with exactly two of those)) which is easy to calculate
jagged junco
oh I think I know
so after 6c3. We got 3 numbers
Now the problem has become, have each one of the numbers picked shown at least once in 10 thrown attempts
jagged junco
its 6C3 * (3^(10) - (the results with just one of those + the results with exact...
yes
weary tiger
you acn also do it in a different way a bit 6c3 * ( 10C3 * 3^7 ) I think
you choose out of 10 rolls 3 for the 3 distinct numbers, then 3^7 anything
jagged junco
you acn also do it in a different way a bit 6c3 * ( 10C3 * 3^7 ) I think
I'm not sure it'll cover all the cases
jagged junco
yea might be it hmm
jagged junco
nice
jagged junco
what is the formula used to get the left side? (assuming you have the right side)
I got this formula in my book but it is different because there are skips
so the denominator I can understand it's 1-x^(the number of jump) so 10
but how do you get the numerator ?
pale epoch
it's the same but you plug in x^10
jagged junco
but if you plug x^10 in numerator you get 1-x^31?
pale epoch
how so?
jagged junco
I got this formula in my book but it is different because there are skips
maybe its my confusion or I don't understand it right, the m resemebles the last power?
warped pecan
Conjunctive *
deft dock
why would this not be:
∃ an integer n such that n is divisible by 6 and n is not divisible by 2 or 3
oh wait nvm youre negtating so demorgan
stoic anchor
is anyone able to explain this to me? im still having trouble understanding after reading the textbook and listening to the professor
reef thistle
yeah the issue here is that [a, b],[c, d] is not the notation for a set. You need to write it as a union of disjoint intervals
reef thistle
this is more #linear-algebra than #discrete-math
but yeah, that question is mainly calculating the product of matrices and interpreting as a 2d rotation
random sparrow
yeah i have the product but how do u interpret it
stoic anchor
yeah the issue here is that [a, b],[c, d] is not the notation for a set. You nee...
so like for a how would i even do that bc don't i have to worry about all those values that are less than two as well? do i just i have to write all of them out like that?
radiant trail
I am pretty sure the answer for a is just [1,2] since all the other sets are subsets of it.
stoic anchor
I am pretty sure the answer for a is just [1,2] since all the other sets are sub...
i had tried that as well after the answer in the ss i sent but it told me i was wrong
errant bear
how is a not [1,2]
radiant trail
i had tried that as well after the answer in the ss i sent but it told me i was ...
Is it an automated system or did a human tell u it’s wrong ?
stoic anchor
Is it an automated system or did a human tell u it’s wrong ?
automated
radiant trail
Then you probably just wrote it wrong
errant bear
put in [1,2] and send another pic
stoic anchor
radiant trail
🤔
errant bear
idk chief
radiant trail
Can you copy the comma and brackets from the question might be some dumb shit like that
Because this is definitely the right answer
errant bear
defiantly
radiant trail
It’s 2:00am 😂
stoic anchor
for b i got [1, 10/9] is that wrong too
stoic anchor
It’s 2:00am 😂
thank u guys for your help
radiant trail
for b i got [1, 10/9] is that wrong too
This should be correct
stoic anchor
🤔
so for d how is it wrong becuase if we're looking for everything inside shouldnt the upper bound or whatever be 1+ 1/n
radiant trail
d is union again so the answer will be [1,2]
radiant trail
Yup [1,2] is the answer for union always as long as you start from i = 1
stoic anchor
okay makes sense
radiant trail
Can you guess what the answer for intersection will be as you approach infinity ?
stoic anchor
its not 0 right
radiant trail
It can’t be 0 your biggest interval is [1,2] so it has to be a subset of it
stoic anchor
isn't 1 a part of the subset
radiant trail
Yup the set containing only 1 is a subset of [1,2]
And as i approaches infinity the fraction will get closer and closer to 0 so the inequality will be
1 <= x <= 1 + 0
stoic anchor
OH
okay
i think i understand that part now
im gonna try to re enter the answers again
it accepted them this time! thank you for making it easier to understand as well
radiant trail
Great to hear that
subtle ermine
<@379817712890806273>
I can come up with a few reasons *why* this is the defini...
Ah I see, that makes a lot more sense. Thank you.
Just wondering
Is the definition specifically that this is the same as "not p or q" . I saw this while trying to understand more about the conditional proposition.
Hmm now I also just learned that if p then q is the same as p only if q, which I tested the truth table for and got the same thing as the conditional proposition
subtle ermine
I think I understand it now. p only if q means that p can only be true if q is true. which fits the if p then q. And if p is false, then q can be anything, which also fits the original statement. Finally, if p is true and q is false, then that breaks the meaning.
Ok
The final thing I saw was that the implication in if p then q focuses on what happens if p is true, and what q must therefore b. But it doesn't focus on what would happen should p be false since q is not bound by any rules in that case, which is why we just say its true then.
warped pecan
Are there infinite equivalent propositional formulas for any given one?
Like take a AND b
are there infinitely many equivalent formulas?
stray reef
well you can have like...
$(a \land b) \land (a \land b) \ (a \land b) \land (a \land b) \land (a \land b) \ (a \land b) \land (a \land b) \land (a \land b) \land (a \land b) \ \vdots$
vital dewBOT
Ann
warped pecan
Oh okay that’s what I was thinking
pale magnet
A group of 15 executives are to share 5 assistants. Each executive is assigned exactly 1 assistant, and no assistant is assigned to more than 4 executives. Show that at least 3 assistants are assigned to 3 or more executives. How i can solve this problem using pigeonhole principle?
strange grotto
A group of 15 executives are to share 5 assistants. Each executive is assigned e...
summation of five variables are 15. atleast one must be 3. it can be 3 or 4. do the case separately recuding the variables
you can also use contraction, say a graph exists not satisfying the condition. maximum edges possible would be (4+4+2+2+2+15)/2=29/2
which is obviously < edges
mint shore
just so that i'm certain
what i've circled is wrong right
it's y_3 = 2
because 12 by 2 is 24
then remainder 1 to get to 25
quaint star
No
24 and 1 are not congruent mod 5
a and b are congruent mod n iff a-b is a multiple of n
24-1 is not a multiple of 5
In terms of remainders, 24/5 has remainder 4 not 1
quaint star
Np
quaint star
Btw
These are even easier if you simplify first
So 20 = 2 (mod 3), then your congruence becomes 2y = 1 (mod 3)
quaint star
Np
west rain
im trying to find a computationally efficient way to find a modular multiplicative inverse d of e (mod n) given that e and n are coprime. Wikipedia says to use the Extended Euclidean Algorithm but to be honest, I dont really understand it.
quaint star
@west rain Okay, so what the Extended Euclidean Algorithm does is: If you have two integers a and b and their gcd is d, then it gives you x and y so that d = ax + by
Now in your case, a is e, b is n, and the gcd is 1
So you get ax + ny = 1. But then you can see ax = 1 (mod n), so x would be the multiplicative inverse of a
west rain
sure but I'm looking for that number, I understand how you get to that but that doesn't give me a numerical value for x
quaint star
Okay, so you have to follow the algorithm. Do you know the Euclidean Algorithm?
Like finding the gcd by long dividision
west rain
well I know how to find the gcd using the euclidean algorithm (at least I have the code for it)
quaint star
Okay good
Okay, I'll help you do the extended algorithm by hand so you understand it, could you then implement the code yourself? I don't have much time
west rain
sure that's perfect
quaint star
Okay, great
Let's do 35 and 20
Then the Euclidean Algorithm would go
Actually let's do a coprime example since that's what you need
west rain
yea so in that case the gcd is 1
also I should mention
I looked at beizout's identity and I was able to isolate d as d = (1 - yn)/e for some integer y but I feel like im not understanding what im doing
quaint star
Yeah, you need to actually do the whole algorithm to find y and d
Lol, it's hard to think of an example that isn't over in 2 lines
west rain
you need some coprime examples?
quaint star
590 and 241 seems to work
west rain
ok sure
quaint star
So let's use that
$$590 = 241(2) + 108$$
$$241 = 108(2) + 25$$
$$108 = 25(4) + 8$$
$$25 = 8(3) + 1$$
vital dewBOT
Lunasong the Supergay
quaint star
Okay, so this would be the Euclidean Algorithm right? And the gcd is 1. Happy with how to do this?
quaint star
Okay
So we use long division to make the numbers smaller
So instead of finding the gcd of 590 and 241, we can find the gcd of 241 and 108
But actually you can do it again
So instead you can find the gcd of 108 and 25
But you can keep doing it until you end up wanting to find the gcd of 25 and 1
Then actually if you did it again
You would get 8 = 1(8) + 0. So the gcd would be that of 1 and 0, which is 1
So as you keep doing long division like this
Your last nonzero remainder is the gcd
west rain
okay right i see what you're doing
quaint star
Okay, happy with that part? Because you will always have to do this part first