all I see is
#discrete-math
unreal stump
For all values of x ( f(x)=0 or g(x)=0 )
(f(x)=0 or g(x)=0) is a boolean
Which always evaluates to true for all x,our choice of f and g should be like that
lost sequoia
Which always evaluates to true for all x,our choice of f and g should be like th...
OHHHHHHHHHHHHHHHHHHHHH
unreal stump
Actually I should have said Boolean before
weary tiger
LESGOOOOOO
lost sequoia
the final output should be always true due to the nature of the proposition
like this?
that's why we are trying to make it true
lost sequoia
a part done ; w ;
unreal stump
Ok,Granted discrete math is more than Boolean manipulation(combi ,graph theory,etc)
But for our case it is
Actually you know what I will just spell that out in python
unreal stump
(1) is
flag=true
for x in R:
flag = flag and ( (f(x)==0) or (g(x)==0) )
return flag
(2) is
flag1=true
for x in R:
flag=flag and (f(x)==0)
flag2=true
for x in R:
flag2=flag2 and (g(x)==0)
return flag or flag2
R is set of real numbers
unreal stump
Well make f(x) and g(x) nonzero at 2 distinct points
The first flag will be true
The second flag will be false
lost sequoia
so.... reverse prove?
set one of them to be true and false
and if that works then its not equal
unreal stump
Well that means those 2 expression are not equivalent
lost sequoia
unreal stump
Because one of them returns a false while another returns a true for same case
lost sequoia
ohh
unreal stump
*not equivalent
You know,This is unironically how people think about these expressions
lost sequoia
so ehm, I understand this now
but how do I justify it?
its required to justify it QwQ
lost sequoia
and Im still kinda clueless in some tiny parts
barren bluff
graph theory goes brrr
unreal stump
You just write
Pick f(x)=1 at x=2 and 0 elsewhere
And g(x)=1 at x=3 and 0 elsewhere
Then the first expression is satisfied by our f and g
since
for any given x,we can pick either f or g to be equal to 0
The second expression is not satsified because (\forall x (f(x)=0)) is not satisfied since f(x)=1 at x=2 and
(\forall x (g(x)=0)) is not satisfied since g(x)=1 at x=3,so f and g don't satsified the 2nd expression
OH
MY
GOD
THAT'S WHAT IM MISSUNDERSTANDING
I HATE MYSELF
unreal stump
Instead of true you just say satisfied and instead of false not satisfied
lost sequoia
I literally forgot that this is an expression itself
unreal stump
Weird semantic differences but that's what you do
lost sequoia
unlike the first one which the entire thing is nested expression
can I just write like,
for every value of x, there might be a f(x) = 0 while g(x) doesn't
for expression one, the expression will satisfied if f(x) = 0 or g(x) = 0
while for expression two, the expression (\forall x (f(x)=0)) or (\forall x (g(x)=0)) must be true for the expression to be true
@unreal stump ?
unreal stump
You just write
```
Pick f(x)=1 at x=2 and 0 elsewhere
And g(x)=1 at x=3 and 0 e...
Kinda messy to read. Use this
unreal stump
Yea,But well this is more detailed in terms of words
Well if you think it's the same go ahead
lost sequoia
Yea,But well this is more detailed in terms of words
if I understand, that's all I care about
cause I'll improve the phrasing as I do more and more
so thank you guys so much and sry for the trouble
💖
unreal stump
I mean I didn't realise discrete math can be taught better until now lmao
Literally python pseudocode will clear up all the confusions a student will have
lost sequoia
🤣
lost sequoia
Well,I choose to be an unpaid TA.
sending 💸 to you 
young knot
In graph theory, how useful is it to have an approximate value for the minimum number of colors a graph will need in a vertex coloring problem? Only the number btw, not the color of each vertex
unreal stump
I guess that will be sorta useful in applications stuff
young knot
well, I do often use graph theory for algorithm stuff
so on that field do you have any idea of the uses that number could have?
it's ok if you don't
unreal stump
Well maybe you have a graph coloring problem and you can afford to waste some resources
So I guess it might be faster to just approximate instead of finding the exact solution
young knot
ight, that sounds good enough. Thanks
wide vine
In graph theory, how useful is it to have an approximate value for the minimum n...
I suppose it depends on your needs and what is "good enough". Being that the time complexity of finding the correct lowest number is hard you just use a faster but not as perfect algorithm
icy garden
Hello! Quick question, is the 2D graph representation of a regular polyhedron a planar graph?
For all regular polyhedrons
Just took a big gamble in a final by assuming so and I wanna know if it was a bad move
Every regular polyhedron I know the graph representation of is planar, so I just assumed
Also it seems intuitively true since otherwise, you wouldn’t be able to fold that polyhedron with paper
coral parcel
The graph of a convex polyhedron, regular or not, is always planar.
young knot
I suppose it depends on your needs and what is "good enough". Being that the tim...
Well, mine is often off by 1 or 2, and it is quite fast ig (my implementation in c takes O(n²)), so it should be good
coral parcel
You can project the graph to a sphere, and then project the sphere stereographically to the plane, choosing the pole to lie in the interior of a face.
icy garden
Okay, sick. So then Euler's Formula for planar graphs holds if I wanted to calculate the number of edges an n-gon would have?
coral parcel
Yes.
vital dewBOT
stable vine
Do i need to right the empty set ?
Both power sets have 4 and an empty set in common(union)
coral parcel
The empty set is an element of both the power sets, right?
So it's also an element of the intersection.
On the other hand, 4 is not an element of either of the power sets.
But {4} is.
coral parcel
{{4}} is not an element of any of the sets either.
The empty set is an element of both the power sets, right?
stable vine
Yea
coral parcel
Then it is also an element of their intersection.
stable vine
Am sorry but dont we have {4} in both power sets?
coral parcel
Yes, {4} is an element of both power sets.
4 is not an element of both power sets.
So 4 is not an element of their intersection either.
coral parcel
Yes. An{ followed by a list of the elements, followed by }.
coral parcel
What is anything minus an empty set?
oblique dew
hey guys .. i'm learning math all over again (pre-algebra) and saw a video recommending discrete mathematics by susanna epp .. he recommended it as good book for beginners .. i read the intro on it, she says this is not intended for beginners and it's for experienced mathematicians. soooo i'm confused here .. should i go with it or not ?
coral parcel
Are you sure you have the right book? The one I can find at Google Books very much like it's a beginners' textbook.
oblique dew
yah i got the 5th edition
coral parcel
Can you post the part of it you interpret as "this is not intended for beginners and it's for experienced mathematicians"?
oblique dew
sure hold on let me get the book
coral parcel
Fifth edition is what I seem to be looking at too.
For example I see this on the first page of the preface.
oblique dew
A good background in algebra is the only prerequisite; the course may be taken by students either before or after a course in calculus
and this was said to be good for complete beginner pre-algebra like myself
coral parcel
That's hardly the same as saying it's "for experienced mathematicians".
oblique dew
yah it was my bad of wording .. but i do see people who know some math somewhat experienced
coral parcel
The person giving the recommendation might be saying it delivers more than it promises.
oblique dew
soo do you think i really should start reading it ?
because i'm doing khan academy's pre-algebra courses .. and i would want to read this book on the side
coral parcel
If you have a copy, it would certainly be worth a try.
barren bluff
good understanding of discrete mathematics early on may be very helpful in mathematics career
stable vine
barren bluff
but that being said if you are doing pre-calculus right now note that it may not be relevant for quite a long time
stable vine
A) false B) true. C) false am i correct ?
oblique dew
good understanding of discrete mathematics early on may be very helpful in mathe...
i don't even know what discrete mathematics is .. nor am i familiar with most mathematics terms. soo i'm just learning.
coral parcel
If you've failed to make good sense of ordinary highschool teaching and you're motivated to learn, it just might be that the more formally grounded approach of a freshman university textbook is what will make it click for you.
oblique dew
If you've failed to make good sense of ordinary highschool teaching _and_ you're...
oofff yess .. i always failed math and barely even passed it. soo yes, i've always struggled with math.
doing khan academy now is good .. but i was thinking i want to supplement it with some math reading. atleast to understand how math is important and how it's used.
coral parcel
In some countries/systems, much of school teaching is atrocious and more focused on teaching ill-motivated students to pass tests instead of to understand the math. That approach mildly speaking doesn't work for everyone.
wide vine
Im a bit confused on what they are trying to show. It just seems if you give a specific n_0 and c, you can show that under a certain f and g function that g(n) will grow faster after the n >= n_0. Is this correct?
so essentially there is a way to manipulate the g function so that it will grow faster then this f function under specific parameters.
oblique dew
i'm intending to learn it to be able to learn physics eventually .. to be able to learn the physics equations
coral parcel
hmm, yes, discrete mathematics might not be the most direct route in that case.
oblique dew
ohh okayy .. what are your recommendation ?
bleak void
Im a bit confused on what they are trying to show. It just seems if you give a ...
They're trying to show that the graph of f(n) is below c * g(n) for some c after some n > n0.
So basically f(n) is growing no faster than g(n).
wide vine
Yeah i see the point now
You want to make sure your f = O(g) is accurate so that it is accurately modelling the growth somewhat
coral parcel
f(n) = O(g(n)) essentially means "f(n) <= g(n), except that we don't care about constant factors, and we don't care about stuff that happens only at the beginning of the n-axis either.
wide vine
I see so it is possibly that the true g(n) is smaller in time for small values n but it doesn't really matter in context of big O and what it is out to explain?
because I think the whole idea is large n values?
coral parcel
ohh okayy .. what are your recommendation ?
I can't recommend any particular titles ... but the conventional route would be to go through standard high-school algebra and then calculus, after which you should be ready to begin reading freshman physics texts.
bleak void
because I think the whole idea is large n values?
Correct. It's about what happens in the limit.
oblique dew
I can't recommend any particular titles ... but the conventional route would be ...
i've been told by physics students that initially algebra, geometry and trigonometry are sufficient for physics entry .. after that, i will be learning calculus and linear algebra along the way.
coral parcel
That could work too.
oblique dew
but i'm just a bit lost of how would i be learning the calculus part though .. is it that physics text books will teach me or i'd have to learn it separately.
wide vine
Correct. It's about what happens in the limit.
maybe I missed something but what stops f from just being f =0
and always satisifying that
I must be confusing myself with something else
Im familiar with big O stuff how like you might have n^3+n^2+2n and then you just say = n^3
but this doesn't seem to actually be saying that
coral parcel
Sure, f(n) = 0 is also big-O of everything.
wide vine
but that doesn't seem very interesting
I guess I am missing where the f(n) and g(n) came from. these are just something you pick?
coral parcel
The zero function is one of mant things that have this property.
wide vine
in this example
bleak void
Well f(n) is usually the number of steps required by say an algorithm.
coral parcel
I guess I am missing where the f(n) and g(n) came from. these are just something...
They're just random examples to illustrate the concept.
Speaking of "the big O" is defintely misunderstood.
For any given function there are many different functions it is big-O of.
It is always big-O of itself, for example.
wide vine
I am a bit confused I must be thinking about it backwards though
like f(n) might be the real time complexity? and g(n) would be some sort of approximation?
bleak void
g is usually a simple function whose growth is obvious.
coral parcel
You should also always keep in mind that the "=" in f(n) = O(g(n)) is a very peculiar use of the equals sign -- it doesn't mean that f(n) and O(g(n)) are the same thing, but just that they have a certain relation to each other.
coral parcel
like f(n) might be the real time complexity? and g(n) would be some sort of appr...
Usually f(n) is the "true" time usage of an algorithm, but that is more detailed information than we're really interested in -- it is sensitive to how we count steps, and does this multiplication really take the same time as that addition, and so forth. So we want not to care about the difference between functions that are mutually big-O of each other.
wide vine
I must be getting confused with some other notations
I see they are talking about Ω, O, and Θ
and now I am not sure which one I am talking about when I say
n^2 ~ n^2 + 2n+3
I am familiar with what the CS does with this stuff. how for loop inside for loop might be n^2
and then you might have a linear search
O(n)
anyways I think Ill just have to look at it more
coral parcel
It might be simpler if we just wrote something like $f\sqsupseteq g$ and $f \sqsubseteq g$ and $f \equiv g$ instead of $f(n) = \Omega(g(n))$ and $f(n)=O(g(n))$ and $f(n) = \Theta(g(n))$. They're really way to compare functions instead of operations you can do on them.
bleak void
It will probably make more sense when you see this asymptotic notation in action.
vital dewBOT
Troposphere
wide vine
Anyways gtg for now though. I'll figure it out. Thanks for the input.
neat notch
anyone know how to find (239^19 mod 7) WITHOUT using a caculator?
coral parcel
Fermat's little theorem tells you it is the same as 239^1 mod 7.
Dividing 239 by 7 may or may not be doable in your head, but if you need to grab pencil and paper to do long division, that is still not a calculator.
(In fact, it you start by finding 239 mod 7, you will discover that you don't even need Fermat's little theorem here ...)
young knot
Hm, isn't fermat's little theorem a^p ≡ a mod p if p is prime?
coral parcel
Yes.
So when p=7 we have a^19 == a^(12+7) == a^(12+1) == a^(6+7) == a^(6+1) == a^7 == a.
fallow zodiac
Can someone possibly take a look at this homework problem? I'm not too sure what I'm doing wrong. I've been staring at it for the last 20 minutes or so and I'm at a loss
coral parcel
Wolfram says there is no +10 eigenvalue, but that -10 has multiplicity 2: https://www.wolframalpha.com/input?i=eigensystem+{{-16%2C-60%2C-3}%2C{1%2C0%2C0}%2C{0%2C0%2C-10}}
That should give rise to a cn(-10)^n term.
wide vine
so I learned about this technique of "witness" with O(g) but I am not sure if what I wrote is good enough of proof for showing that f = O(g) for the example provided
I was working off the example
``In showing that a polynomial function f(n) of degree k is O(n^k), the following combination will work as a witness:
n0 = 1
c = the sum of the positive coefficients in f (including the constant term)
For example, if f(n) = 3n^5 + 7n^4 - 3n^3 + 2, a proof that f is O(n^5) could use c = 3 + 7 + 2 = 12 and n0 = 1.``
unreal stump
I don't know what the hell is this witness thing
wide vine
The constants c and n_0 in the definition of Oh-notation are said to be a witness to the fact that f = O(g).
unreal stump
But the common sense approach is just
3n^5<=3n^5,7n^4<=7n^5,-3n^3<=0n^5,2<=2n^5 \forall n>1
wide vine
just wanted to make sure my proof showing f = O(g) is correct for the example they gave
unreal stump
And you just add everything up
Can you share your notes or something? Can't find anything on this witness thing
wide vine
Can you share your notes or something? Can't find anything on this witness thing
The constants c and n0 in the definition of Oh-notation are said to be a witness
and this is the context for c and n_0
unreal stump
Lmao exactly the same thing as what I did
Yea yours is good enough
Also how exactly is this even a technique
wide vine
But the common sense approach is just
3n^5<=3n^5,7n^4<=7n^5,-3n^3<=0n^5,2<=2n^5 ...
yeah this way makes it way more clear
it is just what they said
it was more so for generating an easy function that f would be Oh of
and showing it is the case I guess
unreal stump
I see
wide vine
apply the recursive definition with your given initial conditions and work your way up to a_13
or work backwards by pluggin in a_13 and see what missing a_n term you need until you hit the initial conditions.
sand smelt
can I get the answer first? I just don't have the confidence to solve the problem without the answer 😦
fallow zodiac
Can I get help solving this?
stray reef
presumably because you're required to use circles and not just any jordan curves you like
sand smelt
then how do I solve that?
stray reef
intuition says region count might be maximized if you arrange the circles as symmetrically as possible
not sure though
wide vine
okay I am a bit confused on the "contradiction part". I get intitivue that n is something hat is positive and suppose to be growing and that if you say "n <= 2c+4" you would be saying this n changing variable is less than a constant
tbh I just don't get what the blue text is saying
wide vine
okay I am a bit confused on the "contradiction part". I get intitivue that n is ...
okay so I missed the whole "2c +5" and thought it was "2c+4" and that is where I blundered
azure cliff
https://plato.stanford.edu/entries/set-theory/#AxiSetThe
2.1 The axioms of ZFC
sick lantern
Q: Regarding the number of boolean functions given n variables
The formula is 2^(2^n)
The following image is one explanation I found surfing the internet
It has me till "you could have the output of the function be 0 or 1 ...." After this, to me, it seems like the formula should be 2.(2^n) by this line of reasoning since there are 2^n possible sequences of 0's and 1's and each can evaluate to either a 0 or a 1 thus 2.(2^n)
what am i misunderstanding here?
austere cedar
what am i misunderstanding here?
Lets look at n=2: Let $f(_x_1, x_2)$ be a boolean function. Then you need to know $f(0,0), f(0,1), f(1,0)$ and $f(1,1)$ to know the function. So your function can be represented as a list of four booleans, where the first one is $f(0,0)$, the second one is $f(0,1), etc. And there are $2^4$ lists of four booleans, so there are $2^4=2^{2^n}$ possible functions
vital dewBOT
Alexander42
Compile Error! Click the 
reaction for more information.
(You may edit your message to recompile.)
weary tiger
asked to prove by induction.
what I did so far:
- tried to prove for h_n+1 but encountered the parity problem, seems to work when n is even and not when it's odd.
-tried to prove by contradiction for h_n+1 by using h_n somehow. got stuck.
-tried using all h_1,..,h_n but got lost
any hints?
am I banned lol
brb
i cant use texit even in my own server
vital dewBOT
Ann
vital dewBOT
Crep
weary tiger
finally
weary tiger
what are these h_n tho
harmonica
splitting cases doesnt really make sense to me here 
wait i havent used the fact thats valid for evens to prove for odds
gonna try rq
d solved
chungus
coral parcel
Alternatively:
$$ \sum_{k=1}^n \frac1k = \sum_{k\text{ odd}\le n}\frac 1k + \frac12 \sum_{k=1}^{\lfloor n/2\rfloor}\frac1k$$
The first sum obviously has odd denominator; by long induction we can assume the denominator (in lowest terms) of the second sum is even. And it holds in general that $$\frac{\text{whatever}}{\text{odd}}+\frac{\text{odd}}{\text{even}} = \frac{\text{odd}}{\text{even}}$$
vital dewBOT
Troposphere
sick lantern
Lets look at n=2: Let $f(_x_1, x_2)$ be a boolean function. Then you need to kno...
sorry for being a dunderhead but what is $ a placeholder/representative for here?
austere cedar
it is for latex coding. You start and end formulas with that sign
coral parcel
$ signals to the TeXit bot that the material between the dollar signs is formulas it should typeset nicely.
sick lantern
ah alright thanks
sick lantern
Lets look at n=2: Let $f(_x_1, x_2)$ be a boolean function. Then you need to kno...
right yeah makes sense thanks
weary tiger
**Troposphere**
sorry but why is the top in the second odd
coral parcel
The second sum is half of an earlier harmonic number that the induction hypothesis says is odd/even. Dividing it by 2 is not going to change that.
coral parcel
Hmm, that was actually a bit roundabout -- the relevant knowledge from the induction hypothesis is just that the numerator of the earlier harmonic number is odd in lowest terms. The factor of 1/2 then makes sure we get an even denominator.
weary tiger
i see
pastel hollow
I'm trying to find the coefficient of x^5 in the expansion of (1 + x + x^2)^8 and I think I've reduced it to finding the number of solutions to y_0 + 2y_1 + 3y_2 = 13, but I'm not sure how to do that. Could someone give me a hint?
(where the y_is are natural numbers)
weary tiger
I think it might be very easy if you use trinomial expansion
pastel hollow
Like actually expand it out by hand?
It's a combinatorics exercise so I'm trying to solve it with counting techniques
weary tiger
I mean if you can use this then it's not that bad, there is still some counting involved, but for now I don't really see a better approach, although if its equivalent to that equation you mentioned you can probably consider cases to count all the solutions (like maybe set y_0=k, not many other possibilites but it is brute forcing pretty much)
pastel hollow
I don't see how I can use that since im not looking for the coefficient of a term with particular values of i, j, k
weary tiger
if you let c=x^2, b=x then for example when k=2, j=1 you get one term with x^5, you find all of those
pastel hollow
idgi
blissful sand
is there a rule that whenever we are using existential quantifiers, we have to use conjunction? or in the case of universal quantifiers, we have to use implication?
wide vine
It might be simpler if we just wrote something like $f\sqsupseteq g$ and $f \sq...
Okay so i ended up getting the hang of this but I really despise the notation with the use of "=". I guess it is just based on the definition that was provided but the way you wrote it makes it much more clear.
coral parcel
is there a rule that whenever we are using existential quantifiers, we have to u...
Yes -- I wrote an attempt to explain just how that works here: https://math.stackexchange.com/questions/48161/in-classical-logic-why-is-p-rightarrow-q-true-if-both-p-and-q-are-false/4385559#4385559
wide vine
okay this makes sense
but im not sure how I would go aboutt proving it
I see i is essentially saying that if you take the higest degree of your polynomial (k), then it will be theta(n^K)
. Every polynomial function is Oh of every exponential function, which also means that every exponential function is Ω of every polynomial function. There is no polynomial function that is Ω of any exponential function, which also means that there is no exponential function which is Oh of any polynomial function. Why does this seem completely backwards
Oh of refers to a upper bound
Ω of refers to being a lower bound
either I am mixing up how you say these or this is backwards
grand elm
they are correct. formally O(f) is the set of functions bounded above by f, so polynomials being O of every exponential means polynomials are bounded above by any exponential function (bounded above in the O sense)
wide vine
okay so for example. x^2 = O(2^x)
this is saying 2^x would be an upperbound function of x^2?
grand elm
yes
wide vine
okay I think I see what happened. I was think it was saying exponential function = Oh(polynomial function)
but I guess reading it it was saying the opposite
Every polynomial function is Oh of every exponential function <=> polynomial function = O(exponential function)
correct?
coral parcel
Yes.
wide vine
idk why I am struggling so hard reading this stuff
coral parcel
There's a lot of confusion here because students easily gets an impression that there's a definite procedure that you can carry out where you start with for example n²-25n+6+23nlog²(n) and after cranking the handle you end up with "O(n²)".
And many students instinctively end up expressing this impression as something like *"the big oh of n²-25n+6+23nlog²(n) is n²" -- which is not at all how the formalism works.
What is true is that (in the conventional notation)
n²-25n+6+23nlog²(n) = O(n²)
which in my (fictitious but more honest) notation would be
n²-25n+6+23nlog²(n) sqsubseteq n²
wide vine
idk i guess I just don't like "n^2 = O(n^3)" or "n^2 is O(n^3)"
coral parcel
That's fair.
You don't need to fight the instincts that lead you not to like it; they're good instincts.
You just need to get used to it anyway.
wide vine
Yeah 
feel like it would have made more sense if "<" or ">" signs were used
but by the definition that is just how it is I suppose. f = O(g) just means that you have some f(n) <= c*g(n). Basically you could manipulate the g with some constant and some n where it will always be greater than or equal to f
thus making it a upper bound
coral parcel
The reason why the notation survives even though it confuses every student who first sees it, is that it is very convenient to be able to use it inside expressions, once you have sufficiently internalized what it means. Then we can write things like
n²-25n+O(nlog³(n))
to mean
I'm thinking of a function that is the sum of two things. The first is n²-25n and the second is something that I don't care to write down in details, but it's enough for my purpose here to know it compares below-or-equal to nlog³(n).
That's something you can't really write compactly just with comparison symbols.
wide vine
I see. Yeah I have not really had any practice of seeing it used in that context but I see how that could be important
coral parcel
So as long as you're just doing exercises of comparing two particular functions to help you understand the technical definition, you're not getting any of the motivation for the crazy way of writing it.
coral parcel
Sometimes, but you need to be careful with that because "i don't care about constant factors" doesn't always survive being composed with f.
For example, 2^(n²) and 2^(2n²) grow at distinctly different asymptotic rates even though n²=O(2n²) and 2n²=O(n²).
So saying 2^O(n²) would not tell a lot about which function you're looking at.
jolly rivet
In a graph k,12,10 does that mean there are 12 vertices and 10 edges
Like obviously here vertices and edges are 10
but if they were different would it be vertices first
coral parcel
It K_{10,10} means the complete bipartite graph with 10 vertices on one side and 10 vertices on the other so in total 20 vertices and 100 edges.
jolly rivet
Oh I forgot about bipartites
Thank you
And if they are the same then their could be a Hamiltonian circuit right
Because each vertex maps to another vertex
flat wagon
coral parcel
First reduce the base modulo 23. Should be able to do that by eye alone.
The result is obviously a square, so you rewrite it to (the square root)^38.
Even though that doesn't seem like progress, Fermat's little theorem now allows you to chop 22 off the exponent, leaving 16.
But that's just squaring four times in succession -- one of which you've already done -- and reducing modulo 23 after each squaring.
icy garden
hi! I'm trying to express "two of these four variables must be true while the others are false" in conjunctive normal form, and it's kind of kicking me in the butt.
I think mainly because I know the "tricks" for when you have two variables, and applying the tricks individually, but coming together with them is confusing me
also it's kind of wigging me out trying to get it in boolean algebra just outside of cnf to begin with, i'm gonna beat my head against a wall for a bit and post when I at least have that
I think the way you'd express that if I only wanted to say, with vars 1, 2, 3, and 4, use 1 and 2 and not 3 or 4, that'd be (1 ∧ 2) ∧ (-3 ∧ -4)
which should expand to uhhhh
gosh
actually
is a series of ands not in cnf?
think this probably fits better in proofs and logic since this is boolean logic
severe swan
Can someone explain this to me?
You flip six fair coins. Let A be the event that exactly three of the six coins lands on Heads.
If p(A) = w/16 what is the value of w?
Answer is 5
What calculations do I need to do in order to get 5?
Why is the denominator 16?
I know that 2^4 = 16 but I don't know where you would get the 4 in the problem to get 16 as the denominator.
stray reef
Can someone explain this to me?
You flip six fair coins. Let A be the event tha...
would you be able to just calculate P(A)?
it sounds like you're getting hung up on the unusual directions that are probably just aimed at getting an integer answer; whichever answer you get, the value of w that they want will be equal to 16*P(A), be that an integer or not
aside from that, this is a simple binomial distribution problem if you're familiar w/ that
wide vine
hi! I'm trying to express "two of these four variables must be true while the ot...
Not sure if it is related, but this might be similar to boolean satisfiability.
stray reef
@severe swan
unreal stump
First you choose which 3 coins should be head. This can be done in $\binom{6}{3}$ ways. Now you check the probability with which this case will happen.This would be a factor of $\left({\frac{1}{2}}\right)^{3}$. For the other three coins to be tail ,you have to multiply with a factor of $\left({\frac{1}{2}}\right)^{3}$
Simplifying this gives you the answer
stray reef
parentheses + bad wording
icy garden
Not sure if it is related, but this might be similar to boolean satisfiability.
I am actually working on boolean satisfiability yeah
wide vine
Not sure if it is related, but this might be similar to boolean satisfiability.
Although with such expression you are not really forcing the variables to do anything but just checking to see if they satisfy some specific expression. So you could make an expression where you could check for such a case but it isn't like you can make sure it happens
icy garden
converting a problem to a sat problem so that it can be shoved into a sat solver
I think? I figured it out
I'm going to probably use ridiculously more clauses than I need but, it's a sat solver, not a human, so that's not a problem
vital dewBOT
Drake
wide vine
converting a problem to a sat problem so that it can be shoved into a sat solver
Could you not also just write it out in sum of products form?
icy garden
I am a mere stupid cs major and do not know what sum of products form is
so I probably shouldn't
it'll add work if I try and use something I don't know how to use
wide vine
(A)(B)(!C)(!D) + (!A)(!B)(C)(D)+ .....
icy garden
ah
wide vine
but is there any connect between the 4 variables
is it any 2 variables or are they connected some how
icy garden
so, as far as I know, every sat solver takes conjunctive normal form inputs
so while I could convert that into cnf
If I could quickly convert stuff to cnf, that would solve my problem
the 4 variables aren't connected, it's just some 2 of them
the cnf version of what I want is uhhh
this would be disjunctive (A ∧ B ∧ ¬C ∧ ¬D) ∨ (A ∧ C ∧ ¬B ∧ ¬D) ∨ (A ∧ D ∧ ¬B ∧ ¬C) ∨ (B ∧ C ∧ ¬A ∧ ¬D) ∨ (B ∧ D ∧ ¬A ∧ ¬C) ∨ (C ∧ D ∧ ¬A ∧ ¬B)
and the CNF is a mighty bit giant
wide vine
something something demorgan
icy garden
yeah you can but that's a really hard one to do by hand
since it's multiple ors with 4 part clauses
I can't think of an easier way to represent it than that, when all four variables are independent
as in, there's no implications
just
the four variables and I need only two to be true and the other two false
wide vine
just write out a true table 2^4
unreal stump
Well This isn't too bad
wide vine
and you can get your DNF form
but I mean if you want it in CNF I think there is a way
Why do you need it in CNF though
icy garden
as I said, I'm plugging it into a sat solver
and I don't know any sat solvers that don't require CNF input
unreal stump
Let f=(ab'+a'b)
then f'=(ab+a'b')
(f') '=(a'+b')(a+b)
There's your Sum of products to Product of sums
icy garden
but yeah every sat solver I know takes only cnf input
pySAT for instance
or cryptosatsolver or anything else
unreal stump
Yea just convert
It's not that difficult
You just replace a product term like a'bc'd with a sum term like (a+b'+c+d')
wide vine
A+B+C+D =2
I think you could just make an if statment and check that they sum to 2
or umm
or you could so some switch statment or if else stuff
yeah seems to work fine
so I guess as long as it is 2 then it would be True to say you have your correct expression of 2 trues and 2 false.
unreal stump
Ok yea that works
wide vine
ummm not sure this exactly #discrete-math but I do recall you looking at the growth of the order and seeing if the top grows faster than the bottom or vice versa
I mean I suppose this might be but seems more like something that shows up in #calculus
onyx hull
Does this channel fall under Graph Theory? xD
unreal stump
Sure
onyx hull
Construct all the (isomorphism types of ) r-regular graphs, for total nodes n = 1, 2, 3, 4. (hint: 0 ≤ r < n, e.g., when n = 2, r can be 0 or 1.)
when n = 1, is there only 1 Node?
stray reef
yes, that's what it says
onyx hull
okie, so when n = 3, r can be 0,1,2?
stray reef
yes, except a 1-regular graph would violate the handshake lemma.
onyx hull
okay thanks 🙂
unreal stump
Since this is a connected graph,This just becomes a combi problem
There are 4 ways of choosing the starting node,3 ways of choosing the second node,etc.
So you get 24
@onyx hull
Well not connected I meant complete
onyx hull
Combi problem makes sense, but I don't fully understand that, I have already manually counted more than 24 xd, but I am most likely incorrect
unreal stump
Well,A path has to have 5 distinct points
So at most you have 120 different paths on any graph of order 5
Oh mb I thought the path had to include all the vertices
It will be 24(all 5 points in path)+6(4C3) (4 points) + (2)(4C2)(3 points) +1(4C1) (2 points)+1(4C0) (only 1 point)
pastel mica
why does this algorithm always end up with a n%5 = 0?
ive listed all the cases from 0,1,2,3,4 and how it would work in the algorithm, but im having trouble proving that it actualyl works for very choice of input n
would I just have to say that every non negative integer is divisible by either 0,1,2,3,4?
onyx hull
Thanks Drake, I will save my wrist and brain from manually counting lmao
onyx hull
Looks like something you could prove using even numbers(2k), and odd numbers (2k+1)
pastel mica
rea;;y
really
idk how tho
currently what i have is ive put in 0,1,2,3,4 into the algorithm and shown that in the end they all end with a result of 0
and im trying to say that all the other non negative integers you could put in factor these numbers
which means that the mod number will be the same
onyx hull
are you asked to write a "proof"?
bleak void
but i have to prove it
One way to prove this is by cases on the last digit of n.
last flicker
Doesn't have to be the last digit, if you know modular arithmetic you can just consider the congruence classes mod 5
stray reef
^
woven cape
Note that 3, under remainder addition generates all the remainders mod 5. This means that for any input n there exists an integer j (less than or equal to 5) such that n+3j is divisible by 5.
hard citrus
If we know that f: A -> B is an injection, then must it be true that |A| <= |B?
coral parcel
Yes, by definition of how to compare cardinalities.
hard citrus
It seems a little straightforward but I had to make sure
coral parcel
"By definition" is when A and/or B is an infinite sets. If they are finite sets, then |A| and |B| are ordinary numbers, and it takes a proof to claim that they compare in the stated way. (But there is such a proof, by induction).
hard citrus
Right, I was looking more around when a function is an injection, rather than at cardinalities. Thanks for the quick response
raven grove
need help on setting this up
raven grove
I found the gcd but what do you mean by simplify
weary tiger
I found the gcd but what do you mean by simplify
divide 27.. and that other number by it
2lazy
raven grove
divide the two numbers by the gcd?
weary tiger
divide the two numbers by the gcd?
oys
to get 1 on the other side
to make euclid easier
raven grove
im still confused
pale epoch
how did you calculate the gcd? euclidean algorithm?
raven grove
yes
pale epoch
can you share a picture or something?
you will have to do whats known as the extended euclidean algorithm
raven grove
58212 = 27720 * 2 +2772 then i did 27720 = 2772 *10 +0 so that means 2772 is the gcd cause my remainder reached zero
raven grove
yeah i am just confused on how to find two integers "r" and "s"
raven grove
yes so what two numbers "r" and "s" make this equation work r27720+s58212=2772
pale epoch
just look at 58212 = 27720 * 2 +2772
just subtract 27720*2 from both sides?
then you get your solution
or what is the problem
raven grove
how does that give me 2 numbers
pale epoch
i dont know what to tell you, they are right there
in front of 58212 its an implied 1*...
raven grove
i think i got it now r= -2 and s= 1
pale epoch
yes
sour cairn
I am attempting to solve a group theory problem.
Given that N is a normal subgroup of G and N <= H <= G (where <= means "is a subgroup"), I must show that H/N is a subgroup of G/H.
Now, I can't see how this can be right. As far as I understand it, G/H is only a group if H is a normal subgroup of G, but, perplexingly, there's a part 2 to this question which begins with "Assume further that H is a normal subgroup of G," implying that H may be non-normal.
If G/H is not a group, H/N surely can't be a subgroup of G/H.
In addition, it seems to me that if G = H = S_3 (the symmetric group on 3 objects) and N is the subgroup of S_3 containing the identity and the 3-cycles, then G/H is order 1 and H/N is order 2, so H/N clearly isn't a subgroup of G/H.
I'm not all that confident on quotient groups yet, so if anyone can point out where I'm mistaken here I'd appreciate it.
pale epoch
why can H/N not be a group?
N is normal in G, so it should suffice to show that it is also normal in H
sour cairn
I'm saying it can't be a subgroup of G/H, if G/H isn't a group in the first place.
pale epoch
oh
sorry, i misread
ye, that doesnt work
the correct statement is G/N has a subgroup isomorphic to H/N
sour cairn
I see. It must be a misprint. Thanks.
pale epoch
yeah, you should ask your teacher to be sure of what he wanted
pale epoch
the correct statement is G/N has a subgroup isomorphic to H/N
i assume you covered the first isomorphism theorem and ^ should be deduceable from that
sour cairn
Yes, that's right.
pale epoch
also you can go to #groups-rings-fields for such questions, might have better results there (read the channel topic on how to get access)
sour cairn
I wasn't sure if it was the right place, since it's under "advanced mathematics"
pale epoch
generally abstract algebra is like a third or higher semester class, so its fine
onyx hull
Can a induced subgraph have disconnected edges?
weary tiger
ping me for assignments and exam help
balmy jay
ping me for assignments and exam help
Can you solve collatz for me
subtle ermine
I'm trying to understand linear congruences better
ax ≡ b mod m
This has unique solutions when a and m are relatively prime
If not, a and m can be written as a multiple of some number ( i presuem the gcd)
From there I was able to see that if b / gcd is an integer, there are unique solutions
And if b / gcd is not an integer, then there are no solutions
Where do I go from here
Assuming b / gcd exists, I can find values of x
Now how do I approach relating that back to the original solutiosn of x?
I noticed that the solution of the simplified congruence accounts for all the other solutions in the original congruence, as they differ by mk where m is the new modulo of the simplified congruence
Why is this the case?
Also
I'm unsure why if b / gcd is not an integer, does there exist no solution, because can't we do this:
b / gcd = b * gcd^-1
So gcd^-1 must not exist? But I've done some playing around with numbers and there are scenarios where it does exist
6x ≡ 3 mod 10 conver to equal signs form and then divide by 2
3x ≡ 3 * 2^{-1} mod 5
3^-1 = 2
2^-1 = 3 ** 2^-1 exists**
3 * 3^-1 * x ≡ 3 *3^-1 * 3 mod 5
x ≡ 3 mod 5
Clearly not correct because x = 3 is not a solution to the original congruence :/
unreal stump
Also
I'm unsure why if b / gcd is not an integer, does there exist no solution,...
You have to look at gcd(6,10)=2 , inverse of 2 doesn't exist
unreal stump
Also
I'm unsure why if b / gcd is not an integer, does there exist no solution,...
Think about it in terms of divisibility,if ax= b mod m then
ax-mk=b
gcd(a,m) divides LHS
So it has to divide RHS for there to be any solutions
subtle ermine
You have to look at gcd(6,10)=2 , inverse of 2 doesn't exist
But it does exist mod 5
AH
That does make sense
Oh and even if it does exist mod 5, it doesn't matter, the point is it doesn't exist mod 10 so we shouldn't use it?
The LHS/RHS divisibility thing makes sense though
subtle ermine
One more thing
When dividing a congruenc ein the form
aFx = bF + (mF)k
F = gcd
ax equiv b (mod m)
The solution for this gives us one of the multiple solutions for the original congruence (Also this has a uniques olution because a and m must be relatively prime)
And then doing that solution + mk gives us the rest
How does that work?
I thought of it as dividing by the gcd basically lowered our modulo, therefore lowered the range of {0....mF - 1} to {0...m -1}
Hence, eliminated some of the multiple solutions
But I can't intuitively see why they have at least one same solution
unreal stump
So take 6x=4 mod 10 for example
You have 3x =2 mod 5 so one solution is x=4 mod 5
Now x=4 mod 5 and 9 mod 5 both satisfy this but we just take them to be the same class
But x=4 mod 10 and x=9 mod 10 are different things
Your solution is only constrained by "x=4 mod 5"
So you try all k ,such that x=k mod 10 => x=4 mod 5
This corresponds to what you are doing
This can be read as if (x=10m+k) ,does 5 divide x-4?
subtle ermine
So 5 divide x - 4 (or x + 1) is necessary for x = 10m + k ?
unreal stump
You find a constraint on x by dividing with gcd
And then you check what values in the original base satisfy that
subtle ermine
Oh wait I can write this as a compound proposition lol
So really, we've formed an alternate congruence that maintains the environment for x
And all that really does is give a RESTRICTION
So that all values of x for x = 10m + k HAVE to fulfill that
Oh and also we divide by the gcd because that ensures our alternate congruence has a UNIQUE solution?
subtle ermine
Oh yeah, that too
Because we're making the numbers simpler
(and making the a and m not have gcd > 1)
unreal stump
Oh wait I can write this as a compound proposition lol
So really, we've formed ...
Also this is more of an if and only if,not an only if
Because
$ax \cong b \mod m \iff \frac{ax}{gcd(a,m)} \cong \frac{b}{gcd(a,m)} \mod \frac{m}{gcd(a,m)}$
vital dewBOT
Drake
fleet mesa
Drake
unreal stump
We showed the forward direction,The other direction is easy to see(just multiply everything with gcd(a,m))
unreal stump
Because
$ax \cong b \mod m \iff \frac{ax}{gcd(a,m)} \cong \frac{b}{gcd(a,m)} \mo...
Only if gcd(a,m) | b
subtle ermine
Ok so we showed that the solutions of x in the original have to work for our new congruence -> because the 4 and 9 are the SAME for example in our new congruence, so the multipel solutions are the same
And in the other direction
Our solution of x for our new congruence will work for our original because we can just multiply all values by gcd(a, m) and each term cancels?
unreal stump
Yea
What that means is all values that satisfy our constraint are solutions
And all solutions satisfy our constraint
subtle ermine
I get that the solutions for the original have to satisfy the new congruence
The other way around is that the new congruences solution has to be a solution in the original?
subtle ermine
Which is why (gcd(a, m)) | b has to be true
Because if it isn't true
Then finding the inverse for the new mod m reveals a solution that doesn't work in the original, making everything null
Ah
So that's what it means about going both ways
If it's a solution for the left, it has to be one for the right, and vice versa
unreal stump
Yes
subtle ermine
That makes so much sense! Thanks!
It still feels a little fuzzy but I'll try writing this out a bit later to ensure I understand
unreal stump
np
final cliff
help
It's just an identity?
One way to look at part (a): Say you have n cards to start and you want to build a k-1 card deck and a separate single card deck.
One way to do it: select k cards from your total n cards to build a deck of k cards then remove one card from your new deck of k cards. You'll be left with a deck of k-1 cards and a deck containing a single card. There are n choose k ways to select k cards from a deck of n cards and there are k ways to choose a single card from this new deck of k cards. So, there are k(n choose k) ways to build the two decks in this way.
But there's another way to build the two decks of cards: suppose you select the single card for the single card deck first? Then to build the k-1 card deck you can just select k-1 cards directly from the n-1 remaining cards. There are n ways to select a single card and (n-1 choose k-1) ways to select k-1 cards from the n-1 remaining cards. So, there are n(n-1 choose k-1) ways to build your two decks this way.
(Notice how we just counted the same quantity in two different ways?)
crude garnet
💗
burnt monolith
Could someone explain how the partial order definition works on set B?
also is (2, null) comparable to (2, [2, 6])
given that definition of a partial order
high iron
Hi
I have a small chapter
The professor explained SO fast and i dont understand anything
Its uh
Big o notation
Is their an online calculator? That shows steps
I couldn't find anything
Useful
burnt monolith
I can help with this!
@high iron
Big O is a way of representing the speed at which the runtime of an algorithm will grow from the size of it's input
so say we have an algorithm that is O(n^2)
that means that if we increase the input size by n, the runtime will increase by n^2
high iron
Ahh
Hang on leme send picture
Its really confusing
Like where did we conclude x>1
Or why
Its just guessing at this point
pale epoch
its not a conclusion its an assumption
big O notation doesnt care about what happens for small values of x
so you can assume x big (in this case x > 1) if that helps you find an upper bound
pale epoch
often
the idea is that x^n grows faster than x^{n-1}
like, x^5 grows faster than x^4, which grows faster than x^3 etc
burnt monolith
pale epoch
and you want to ignore the smaller factors
burnt monolith
this might help
pale epoch
because at large scale x^2 for example grows just as fast as x^2 + x
or x^2 + x + 10000
burnt monolith
big o becomes relevant when comparing something like sorting algorithms
so we can say something like
quicksort, in average case, sorts at O(n log n)
which means at large input sizes, it will have a quicker runtime than insertionsort, which on average case has O(n^2)
alg i need to sleep its late where i am
gl
weary tiger
how would someone show that R^n has the same cardinality as R?
of course it implies that you can make a bijection but the question is how
stray reef
bijecting R to R^2 is the hard part
once you have that it's easy to show that R^n can be bijected with R^(n-1) for any n
wide vine
Anyone know how they are getting "3 ops" for the while statement? I only see 2 checks within the while loop.
I only see the a_1 !=x, i < n, and i:=i+1
which would be 3
but they say it is 4
pale epoch
maybe evaluating the and is another operation
tribal blade
Would anyone be willing to help me with this problem:
I believe one way to go about it is proof by contrapositive.
pale epoch
please stick to one channel.
light heath
what does min mean since we have whole numbers?
vale cairn
What does being whole numbers have to do with that?
light heath
lol honestly that dosent make since say it asks min of 3 to 4 well wouldent that be 3?
vale cairn
It's the minimum of the two numbers
Not of an interval if that's where the confusion lies
light heath
Not of an interval if that's where the confusion lies
that was, thanks for clarifying
deep flame
is there a more concise term for "all vertices that are with a path of size 2 from a vertex"?
I got it: "second neighborhood"
weary tiger
bijecting R to R^2 is the hard part
Is there something of the nature of a cantors pairing function?
gilded ember
Hi I am reading a book about cardinality and have some random thought.
Suppose $f:A\to B$ is bijective.
Then by definition, $A\sim B$.
And by the properties of cardinality, $B\sim A$.
Then there exists some bijective function $g:B\to A$.
But since bijectivity implies the existence of inverse, can I conclude that, the pre-image sets, $f^{-1}(A)$ and $f^{-1}(B)$, are of cardinality equals to each other, too?
vital dewBOT
Trenton
severe swan
Which of the following is true over the domain of real numbers?
To test over real numbers I think you would use 1/2 and -1/2
Answer: ∀x(x<0 --> x^2 > x)
Why is this not correct?
∀x (x + 1) ^2 > 0)
((1/2) + 1) ^2 > 0) is True
4/9 > 0 is True
final cliff
Hi I am reading a book about cardinality and have some random thought.
Suppose ...
What if A,B are disjoint? Then f^{-1}[B]=A but f^{-1}[A]={}.
If you mean g^{-1}[A] and f^{-1}[B] I'm pretty sure it will be guaranteed by noticing g^{-1}[A]=B and f^{-1}[B]=A then pointing out that f is a bijection from A onto B.
(Or something vaguely along those lines)
gilded ember
If you mean g^{-1}[A] and f^{-1}[B] I'm pretty sure it will be guaranteed by not...
oh yes there is some typo in my paragraph
gilded ember
What if A,B are disjoint? Then f^{-1}[B]=A but f^{-1}[A]={}.
Umm if the pre-image set of A is empty, then there does not exists the function g?
final cliff
Which of the following is true over the domain of real numbers?
To test over re...
For universal formulas to be true they have to hold for any x in your domain. So, picking x=-1/2 to test your formulas won't work. What if they fail for some other x?
final cliff
Umm if the pre-image set of A is empty, then there does not exists the function ...
What about this? Pick A=N and B=Nx{0} define f(n)=(n,0). f is a bijection from A to B where A and B are disjoint. g just maps g((n,0)) to n.
(N as in natural nums)
Recall f^{-1}[A]={x in domf : f(x) in A} but f takes in natural numbers and maps to ordered pairs. A does not contain any ordered pairs by construction so f^{-1}[A]={}.
gilded ember
Recall f^{-1}[A]={x in domf : f(x) in A} but f takes in natural numbers and maps...
Oh got it. Nice counter example. Thank you so much!
final cliff
No problem.
stray reef
To test over real numbers I think you would use 1/2 and -1/2
1/2 and -1/2 aren't the only real numbers in existence.
burnt monolith
Is an invertible function always one-to-one?
solemn knoll
Yes
stray reef
you have 50 holes (of which one can hold at most one pigeon) and 51 pigeons
the pigeons are the numbers
the holes are the pairs youve written
no you can't
{1, 2, ..., 50} has no pair among them whose sum is 100
gilded ember
I am reading a book introducing how we obtain the commutative law of the addition of natural numbers.
Let $A$, $B$ be finite sets. Suppose $\alpha=\vert A \vert$ and $\beta=\vert B \vert$
$\alpha +\beta=|A\cup B|= |B\cup A|=\beta +\alpha$
But why does $\mathfrak{c}+\aleph_0= \aleph_0+\mathfrak{c}$?
I know this seems to be stupid question. But the fact that $\mathfrak{c}$ is the cardinality of continuum and $\aleph_0$ is that of natural numbers implies that they are both infinite. Why can we apply the commutative law applies here?
vital dewBOT
Trenton
stray reef
because union is commutative as an operation on sets
no matter if said sets are finite or infinite
@gilded ember
pale epoch
as a note, the union here should probably be disjoint union ?
gilded ember
no matter if said sets are finite or infinite
Ok thank you.
gilded ember
as a note, the union here should probably be disjoint union ?
Oh yes, I forget to put that down too, otherwise it doesn’t make sense
Thanks
Oh sorry I still have some follow-up questions.
If the two sets are supposed to be disjoint, why can we define $\mathfrak{c}+\aleph_0$?
(As $\mathbb{N}\cup\mathbb{R}=\mathbb{N}\ne\emptyset$ obviously.)
vital dewBOT
Trenton
stray reef
you meant $\bN \cap \bR$
vital dewBOT
Ann
stray reef
and it is not hard to make them disjoint: replace $\bN$ with $\bN \times {1}$ and $\bR$ with $\bR \times {2}$
vital dewBOT
Ann
gilded ember
you meant $\bN \cap \bR$
Oh yes sorry for the killer typo
gilded ember
and it is not hard to make them disjoint: replace $\bN$ with $\bN \times \{1\}$ ...
Oh I see. Got it thanks.
vital dewBOT
Trenton
gilded ember
I have seen have text. They all tends to assume the difference to be 0, but use the theorem that assuming the difference to be infinite
unreal stump
I think - is set difference
gilded ember
I think - is set difference
Umm but the $\aleph$ is not a set I guess
vital dewBOT
Trenton
pale epoch
i mean by definition of - you want \aleph - \aleph = 0
gilded ember
It is the cardinality
gilded ember
i mean by definition of - you want \aleph - \aleph = 0
Yes, why not their difference to be any finite number or even infinite but 0 specifically?
pale epoch
that wouldnt be what - means?
gilded finch
i mean by definition of - you want \aleph - \aleph = 0
Subtraction cannot be properly defined on transfinite cardinals
pale epoch
Subtraction cannot be properly defined on transfinite cardinals
which is literally in my next message?
gilded finch
which is literally in my next message?
mb
gilded ember
And I guess it may happens that, “$\aleph -\aleph=n$” but $n$ not necessarily 0
vital dewBOT
Trenton
pale epoch
ok uh, by the same proof \aleph - \aleph cant be finite
so what do you want it to be?
gilded ember
Umm can I in general show that, aleph-aleph cannot be any finite or infinite value?
pale epoch
well, the same proof works for any finite value
gilded ember
In the proof, the book use this theorem, but this implies aleph to be infinite, but if (aleph-aleph)=0,(or any finite value n), it will be finite I guess.
Sorry for not presenting my idea well
gilded finch
Umm can I in general show that, aleph-aleph cannot be any finite or infinite val...
Well it can.
Take the naturals N. Even naturals are a strict subset of N, but subtracting them from N gives you the set of odds naturals, of cardinal Aleph0.
Take the naturals N, they are a strict subset of N U { 1.5 }, so subtracting N from N U { 1.5 } gives { 1.5 }, of cardinal 1.
So you cannot properly define the subtraction for transfinite cardinals.
Because depending on the set they "come from" the result can be completely different
gilded ember
Wait but I am not sure is it set subtraction or not, the Aleph is defined as as infinite cardinal
Sorry I missed one line
gilded ember
Because depending on the set they "come from" the result can be completely diffe...
Oh yes, so we can try to show the $\aleph -\aleph$ is not unique value. But I am not sure since the cardinality of infinite sets is too large compare to a finite one, and basically the disjoint set just do not change the overall cardinality
vital dewBOT
Trenton
hoary cloak
anyone knows of a document that compiles proof techniques for graph theory? example proofs would be a plus
i'm looking mainly for applications of the strong theorem for perfect graphs
subtle juniper
is this diophantine calculation wrong or correct?
weary tiger
Can anyone recommend an efficient resource for self studying discrete math?
I am working a difficult job this summer and am going to be taking three math classes including discrete math as one, so need something I can check out to prepare myself as much as possible
paper fractal
Light work
paper fractal
I am working a difficult job this summer and am going to be taking three math cl...
What job you doing
coral parcel
Oh yes, so we can try to show the $\aleph -\aleph$ is not unique value. But I am...
The question is not really "can subtraction of transfinite cardinals be defined", but "can it be defined such that it keeps the properties of subtraction that made you wish to subtract in the first place?".
I'd say the most basic property of subtraction is that it undoes addition: for all a and b such that (a+b)-b is defined, it must equal a.
We can't do that for transfinite cardinals, because |N|+|R| and |R|+|R| have the same result, and no matter what our proposed definition makes that result minus |R| be, it can't be both |N| and |R| at the same time.
severe swan
How can I calculate this?
In a class there are three quizzes, three assignments, and one final exam.
The quiz average is worth 70% of the grade
The assignment average is worth 10% of the grade
The final exam is worth 20% of the grade
James's quiz grades are 40, 50, and 60.
His assignment grades are 85, 90, and 95.
To receive a 'C' in the class, the weighted average must be at least 60.
What is the minimum grade that James needs on the final exam to receive a 'C' in the class?
Here is what I calculated:
Quiz avg: ((40+50+60)/3)=50
Assignment avg: ((80+90+95)/3)=88.33
Grade: (50x0.70)+(88.33x0.10)=43.8333
How can I calculate the minimum grade needed to get at least 60?
wicked basin
im not sure how to solve 4 nodes
for 2 nodes, there are 2 graphs, and for 3 nodes there are 8
but idk how to solve for 4
i was able to draw the graphs out to get my answers for 2 and 3 nodes
gilded ember
The question is not really "can subtraction of transfinite cardinals be defined"...
Oh yes got it. Thank you
unreal stump
$S={x|x=am+bn \exists m, n \in S a,b \in \bN_0}$
stray reef
(a) that really needs some spaces
(b) even with spaces this is still self-referential
from what i can see it sounds like you're describing a set that is closed under addition
but there are many such sets
even the empty set, for one
weary tiger
A carpenter went to the store and bought 10 planks of wood. Each plank has a length that is a whole number of centimeters. The longest plank has a length of exactly 54 centimeters. Prove that there exist three planks that can be arranged to form a triangle.
how is my solution so far
Lets assume that you cant make a triangle. This means that the sum of any two lengths will be less than another. Since the longest plank has a length of 54 cm, this means that either every plank has a length less than 27, or one plank exactly has a length of 27 and every other is less.
stuck on what to do next
weary tiger
anyone?
pls
im starting to think you can do it
since evry length would have to be different
i think
idkidk
How to solve in all this one
ded channel
elder berry
Why dead chat
elder berry
Lets assume that you cant make a triangle. This means that the sum of any two le...
The idea is good, however the negation of the triangle inequality is super wrong.
This means the sum of any two lengths will be less than another.
The above is not true for any three positive real numbers
fallen lichen
no its yeah
elder berry
Here is what I've come up with for the problem
weary tiger
The idea is good, however the negation of the triangle inequality is super wrong...
oh
is it the solution?
elder berry
well you don't really have a solution
it's a start, but let's kind of make it a bit more substantive
So let's name the side lengths, say they are a1 <= a2 < ... < a10 = 54
I ordered them from smallest to largest.
coral parcel
You need: No number in the set is less than the sum of two smaller numbers.
elder berry
Can you think of a reason why I put less or equal only on a1 and a2, but the other planks must be strictly greater than the next ones?
Think about what happens when we have two big planks of equal length, and one smaller plank. Is it always possible to construct a triangle with those @weary tiger ?
Should I give you a bit of time to think, or do I reveal a construction for why a triangle with two big planks (say with length 10 and 10) and one smaller plank (say 4) is possible?
weary tiger
Should I give you a bit of time to think, or do I reveal a construction for why ...
sorry i was somewhere
i'll think about this tommorow
or today if i have the time
coral parcel
You're taking an, um, very relaxed approach to state your reasoning in proper sentences.
For "symmetric" you're just restating the definition without connecting to the definition of R1 at all.
For "antisymmetric" it looks like you're trying to state a counterexample, but you're not stating which sets A and B it is you suggest as a counterexample.
For "transitive" you are actually stating values for A, B, and C -- but your values don't make sense. You're giving them as numbers, but R1 relates sets of natural numbers, not single integers.
I don't get why the preprinted text thinks R1 is symmetric, though. There are lots of counterexamples, for example {1,2,3,4} R1 {3,4} holds, but {3,4} R1 {1,2,3,4} doesn't.
severe swan
Can someone explain this to me? I don't understand how to get the answer of 10%.
Five horses named Ali, Bob, Cat, Dee, and Eva are in a race where no ties are possible. Bob and Eva have the same chance of winning. Cat is twice as likely to win as Bob, and Ali is half as likely to win as Eva. Dee has a 10% chance of winning. What is the probability that Ali wins?
Answer is 10%
livid drum
Can someone explain this to me? I don't understand how to get the answer of 10%....
As a start, let a, b, c, d, and e be the probabilities of ali, bob, cat, dee, and eva winning respectively.
They give you 4 facts; this corresponds to 4 equations.
There is a 5th equation lurking (what's the sum of the odds?).
With 5 unknowns and 5 equations our mind can be at ease.
unreal stump
Ok,Simple question but I don't know how to solve this using pigeonhole?
"given 30 balls and 5 boxes ,show that there is atleast one box such that it has atmost 6 balls"
stray reef
are you required to apply the pigeonhole principle here
unreal stump
Yes
stray reef
cause honestly this is a simple contradiction problem
unreal stump
I know the contradiction way
stray reef
if every box has more than 6 balls then the total is more than 30
pigeonhole seems inapplicable here
unreal stump
I am reading bona and he wants me to use pigeonhole
stray reef
can you post the exact problem statement here
just to be sure
cause if pigeonhole is applicable it's going to be weird as hell
unreal stump
3rd problem
Well this reduces to that because five line segments x,y,z,w,u such that sum is 30
stray reef
your reformulation into boxes and balls is inadequate
because who said the rest areas had to be a whole number of miles away from each other or the endpoints
it is true that you get five stretches of bike track between adjacent rest areas
unreal stump
Ok,So it's just the contradiction approach right? Because this is like the very first set of exercises after introducing pigeonhole
stray reef
contradiction yes
unreal stump
Yea I can do that
stray reef
this is a continuous setup, so pigeonhole doesnt really fly here
heavy tinsel
What am I checking here to see if this is an equivalence relation?
sour arrow
I don't see any question in there
heavy tinsel
Yeah, this is an example showing this is an equivalence relation
sour arrow
Ah I see
You'd check the axioms of an equivalence relation
Symmetric, reflexive, transitive
heavy tinsel
The three axioms, yep. But how am I checking them in this case?
heavy tinsel
by definition that is n |(a-a)
weary tiger
yes which is n | 0 which is true for all n
for symmetry, why does a = b mod n => b = a mod n
and transitivity is similar as well
heavy tinsel
ok, I understand what Im checking now. But why is this an if and only if?
idk if that makes sense
weary tiger
for symmetric i think you only have to check one direction, although it is an if and only if
|| a = b mod n <=> n | (b - a) <=> n | (a - b) <=> b = a mod n ||
coral parcel
The other direction is always exactly the same claim, just with different names for the variables, so it is not usually included explicitly in the definition of symmetry.
weary tiger
Can you think of a reason why I put less or equal only on a1 and a2, but the oth...
yes
elder berry
yes
Alright, furthermore, we also have to have the following inequalities which will guarantee we won't be able to construct a triangle
a1 + a2 <= a3
a2 + a3 <= a4
:
a8 + a9 <= a10 = 54```Makes sense?
weary tiger
wait i havent thought about it yet
im gonna try and come up with some stuff
@elder berry
Let’s assume every plank has a different length, and name the sidelengths such that a1 <= a2 < … < a10 = 54. Now let’s assume in our 10 planks, we have two long planks of the same length and one shorter. This will be able to make a triangle since it will be isosceles, and follow the triangle inequality.
That is the explanation why we can't have a2 <= a3 <= ... and we must have a2 < a3 < ...
So it's a good start
The part that bugs me a bit is
Now let’s assume in our 10 planks, ...
As you can't assume this if you are using the fact thata1 <= a2 < … < a10 = 54.
weary tiger
That is the explanation why we can't have `a2 <= a3 <= ...` and we must have `a2...
right
bc we are trying to do a proof by contradiction
elder berry
I'll follow your idea, so instead write
We prove the claim using contradiction. Name the sidelengths a1 <= a2 <= … <= a10 = 54. Now let’s assume in our 10 planks, we have two long planks of the same length and one shorter. This will be able to make a triangle since it will be isosceles, and follow the triangle inequality. So we must have a1 <= a2 < … < a10 = 54
Notice the differences between <= and <. This is just a start though, how do you plan to proceed?
Oh I need to add a correction
We don't need the assumption that every plank has a different length
@weary tiger good so far?
weary tiger
I'll follow your idea, so instead write
```We prove the claim using contradicti...
how come a1 <= a2 in the second one
shouldnt it be a1 < a2
elder berry
we have two long planks of the same length and one shorter.
weary tiger
oh right
weary tiger
now what do we consider?
elder berry
So since the triangle inequality mustn't hold, the longest side of the triangle must be bigger than the sum of the two shorter sides
elder berry
Alright, furthermore, we also have to have the following inequalities which will...
this means that we can make up the following inequalities ^
weary tiger
So since the triangle inequality mustn't hold, the longest side of the triangle ...
right
ok let me see what i can think of
elder berry
Alright, if you need a nudge ping me
weary tiger
this means that we can make up the following inequalities ^
wait, but it shouldnt be <=, bc then that would satisfy triangle inequality
elder berry
wait, but it shouldnt be `<=`, bc then that would satisfy triangle inequality
then it wouldn't
triangle inequality states a+b>c
elder berry
it depends if you include the degenerate case of a triangle which is a line
elder berry
I don't see a way to utilize it here
work with the inequalities
a2 + a3 <= a4
:
a8 + a9 <= a10 = 54```Rather, work with a10 >= a9 + a8 and repeatedly use the inequalities for a9, a8, ...
First step: a10 >= a9 + a8 >= (a8 + a7) + a8 = 2a8 + a7
weary tiger
First step: `a10 >= a9 + a8 >= (a8 + a7) + a8 = 2a8 + a7`
oh
coral parcel
It's easier to work in the other direction, starting with a1 >= 1 and a2 >= 1.
weary tiger
ok
coral parcel
You get nice Fibonacci numbers as bounds for the other an's.
weary tiger
hm
hows this start? We can start with a1 >= 1 and a2 >= 1. Then a1 + a2 >= 2,
oh wait
should be <=
i think
coral parcel
And therefore a3 >= 2
Depending on what exactly we're assuming. I think it's easiest to say: Assume we have a set of planks that cannot make any (non-degenerate) triangles anywhere. Then (calculate calculate calculate) we have a10 >= 55, contradicting the information in the problem.
weary tiger
ok i got the answer
i was a bit confused on thsi tho
How many two-digit numbers give a perfect square when added to its “mirror” (the two-digit number written with its digits in reverse order)?
Does 00 count?
Otherwise, if the number is 10a+b, then adding its mirror produces 11(a+b), and there's just one relevant way for that to be a perfect square.
weary tiger
Does 00 count?
probably not
weary tiger
Otherwise, if the number is 10a+b, then adding its mirror produces 11(a+b), and ...
right, i actually got that far
thanks for the extra hint
i know how to solve this now
wide vine
Consider a finite alphabet Σ. The set of all finite strings over Σ is denoted by Σ*. What does "the set of all finite strings over" mean? Im familir with something like B* and how you might have B^1 = {0,1}, B^2 = {00,01,10,11} etc.
Im just not really following this
Okay nvm I think I got it
suppose Σ = {a,b}
then
Σ* = {λ, a,b, aa, bb, ab, ba, aaa...}
?
coral parcel
Yes.
wide vine
when they say this do they actually mean they string will read "Yes" or just some form of encoding of it.
If Σ is a finite alphabet, then a subset of Σ* is called a language over Σ. Every decision problem (along with an encoding of the input objects to strings in Σ*) defines a language over Σ as follows: x ∈ Σ* is in the language if x is a valid encoding of an input and the answer to the decision problem on input x is "Yes". The string x is not in the language if either x does not correspond to a valid input or the answer on input x is "No".
or like an accept / reject state
coral parcel
For the time being it looks like those answers are just your intuitive concepts of "yes" and "no", not any particular strings or other encodings.
wide vine
Okay
Yeah this book just has a small section about turing machines
we did look at transition functions and would that be what you would consider a "Yes" or "No"
coral parcel
No doubt the book will specify a technical representation of the yes/no later, possibly different for each formal framework for expressing solutions.
Accepting/rejecting is one way to map "yes" and "no" to formal behavior of a computational model.
coral parcel
It's useful to have a mechanism-independent way of talking about what the desired answer to a decision problem is.
That allows us to say for example that such-and-such problem can be solved by a Turing machine if it's allowed to express "no" as "either reach a rejecting state, or keep running forever without meeting any halting states", but the same problem cannot be solved by a Turing machine if it has to express "no" as "reach a rejecting state".
wide vine
I see
running forever is okay?
my book only mentioned
As with other computer programs, the Turing machine may never halt on a particular input in which case the Turing machine neither accepts or rejects the input.
I could easily see if the program just continuously wrote the same letter into a new cell and moved right.
Is there a name for a state in which the program neither rejects or halts?
coral parcel
Whether or not running forever is okay is a choice we make when we set up a computational model. We can either consider it to be a valid way to answer "no", or consider it to be an always-wrong behavior.
These two choices lead to different answers to "which decision problems can be solved by Turing machines?"
The first leads to "recursively enumerable" problems, the second to "computable" problems.
coral parcel
Is there a name for a state in which the program neither rejects or halts?
It's not a "state" as such, but the behavior of running forever without halting is usually called "diverging".
wide vine
what does "recursively enumerable" mean and why would we choice to use one over the other?
coral parcel
Recursively enumerable means a problem that can be solved by a Turing machine if we allow it to use "run forever" to mean "no".
Both of the concepts are important and useful for different purposes.
wide vine
where does this stuff show more as a topic?
like subject/field
Seems like this language stuff is probably its own field?
Automata theory it seems
coral parcel
There are fuzzy boundaries between "formal language theory", "automata theory", "computability theory".
coral parcel
All belong to he overlap between mathematics and computer science.
"Formal language theory" is mostly about "languages" meaning sets of finite strings of symbols, and classifying languages by how complex mechanisms you need for determining membership in the language.
In particular "formal language theory" is usually not concerned with any meaning the symbol strings might have.
unreal stump
As in "does there exist a DFA/NFA/CFG/PDA/TM/Whatever that accepts the language"
coral parcel
Yes.
coral parcel
Mostly the same thing, perhaps with a difference in focus. As I said, it's fuzzy. They're not completely the same thing: Formal languages also care about grammars and other non-automata ways to specify a language; automata theory also cares about facets of automata that are not about using them for recognizing languages.
silver panther
if you want to know what basic Automata theory is you can read my report on it if you'd like
unreal stump
Well,I had an entire class on automata this sem
Just They never distinguished formal language theory from automata
coral parcel
Generally, people don't care overly much about dividing the area crisply and objectively into named subfields.
silver panther
It's more focussed on the application to a certain counting problem
Rather than proper automata
unreal stump
That was a nice introductory paper ig
silver panther
ty but i doubt i get a good mark cuz it's not mathsy enough
silver panther
No one lol
It was for a discrete mathematics course
Just wrote about what i found interesting from what i learnt
automata was really useful one year in the IMC
one of the questions was literally automata
wide vine
IMC?
silver panther
International Maths Competition
wide vine
oh
unreal stump
Well you are looking for x^n y^m
That matches with exactly one possible term in the sum
The x^n(1+y)^n term
Because that's the only thing which can produce a term with x^n y^m
pastel hollow
Wdym
unreal stump
Tell me can x^(n-2) (1+y)^(n-2) produce x^n y^m
unreal stump
I still don’t understand the equality tho
It means no term other than x^n(1+y)^n can simplify to produce a x^n y^m term
Since coefficient of x^n is 1 this is simply finding the coefficient of y^m in (1+y)^n
So this problem reduces to that
wide vine
International Maths Competition
was reading your paper and noticed you have the 0 state with a double circle but you claimed 4 was your accepting state (simple password checker diagram). Did you mean to do that?
tawdry rapids
coral parcel
