Commander Vimes
#discrete-math
vital dewBOT
last timber
Let us look
vital dewBOT
Commander Vimes
last timber
@hardy quartz any ideas how to use definition of a_n here?
hardy quartz
no not really tbh LOL
last timber
Well consider what happens when you factor 1/3 out
vital dewBOT
Commander Vimes
slim walrus
Hello. I want to compute distance matrix from adjacency matrix for a simple undirected graph. I know what each of these matrices are but how do I get a distance matrix from adjacency matrix? I want to know about the logic and why it will be true.
I found one method in which the powers of adjacency matrix is used to evaluate number of walks. I am not crystal about the approach though
the powers of the adjacency matrix count the number of i→j walks, not paths (a walk can repeat vertices, while a path cannot). So, to create a distance matrix you need to iterativerly power your adjacency matrix, and as soon as a ijth element is non-zero you have to assign the distance k in your distance matrix.
So if I get the number of walk between 2 vertices, so in general if no such walk of length less than k exists from vertex i to j , then the i-j th entry of our k-th power of adjacency matrix would be zero, if we get a value of 1, then that would be the minimum distance and hence the value in the distance matrix.
What I don't understand is, why will the powers of adjacency matrix will give number of walks?
dusk stirrup
What am I doing wrong on part C? I think I'm confused on the symbols. I'm reading it as "what is the least element of the set n^2+3 that is an element of the set of natural numbers. Any suggestions as to how I'm getting this wrong? Not looking for the answer, just some direction.
Oh, wait.. is it 3?
errant bear
is 0 in N
dusk stirrup
no
pale epoch
n^2+3 is not a set
dusk stirrup
but the result would need to be in the natural number no?
pale epoch
anyways, this is the set that consists of elements of the form n^2 + 3, where n ranges through all natural numbers
autumn pebble
Could someone check out if I did these sequences correctly
dusk stirrup
so wouldn't it just be 1 since 1 is the least natural number?
sorry, just trying to grasp it.
pale epoch
so you have {left side : right side}
autumn pebble
@pale epoch but the outputs are correct right?
pale epoch
the left side tells you how the elements look in the set
i wasnt replying to you @autumn pebble
and the right side tells you what "rules must be obeyed"
so here your elements are of the form n^2 + 3 and the rule is n is in the natural numbers
so e.g. 28 is in the set because it can be written as 5^2 + 3
and 5 is a natural number
103 is in the set because 103 = 10^2 + 3
etc
dusk stirrup
So if I was looking for the smallest number, I'd find the smallest number in the set right? So, wouldn't that be 1? ie. 1^2+3= 4? Because 1 is a real number.
pale epoch
yes, but then 4 is the smallest number
pale epoch
are you sure that 0 is not a natural number?
dusk stirrup
I absolutely thought so.. but maybe not? I'll try three once I get the last one and see what it says.
Thank you for all the help. You are awesome.
It was 3. So she must be considering 0 a natural number. Thank you.
coral raven
ew
errant bear
0 is my favorite natural
dusk stirrup
Using A={7,8,9,10,11} B={9,10,11,12,13} and C={8,11,13}... then BuC={8,9,10,11,12,13}, meaning A ∩ (BuC)={8,9,10,11}. What am I doing wrong here?
pale epoch
overline probably means complement
spring temple
Yes.
stable kettle
I'm now sure the formula is wrong
But I don't know how to fix it
@finite depot I'm trying to get rge number of surjective functions given two finite sets of power |A| and |B|
finite depot
You made the formula?
finite depot
How do you know
stable kettle
Because it counts for every case one time
For example, if we consider only one element as image of f it gives 1 and not m
When you calculate the number of non-surjective functions, that is
finite depot
From my understanding m is the amount of elements in the set A
stable kettle
Yes
finite depot
Why there are odd number of | in your formula?
stable kettle
@finite depot the central one is just "such that"
finite depot
Ah
stable kettle
Inside the curly brackets
finite depot
Are you trying to find the combinations?
stable kettle
No
finite depot
Assuming m = {1,2,3} n = {1,2}
stable kettle
I need the amount of surjective functions from A to B
finite depot
What is Dr mn
finite depot
What’s rhe value
stable kettle
m^n
finite depot
Can m > n?
stable kettle
Yes
finite depot
m < n?
finite depot
wtf
stable kettle
Hmm
What is so strange?
@spring temple how do you think I can change the formula to make it right?
Pinging you because you seemed interested
spring temple
Uh.
Haven't really thought about it beyond trying to figure out what you were asking.
stable kettle
Uh...
spring temple
Yes.
spring temple
Otherwise it's simply impossible to be surjective.
stable kettle
I just thought of the definition of dispositions witg replacement
And there m can be >n
finite depot
or equal to
spring temple
Break it into cases.
stable kettle
1
stable kettle
Hmm
spring temple
There are more than 1 if n=m
spring temple
a0 -> b0, a0 -> b1, etc.
stable kettle
n!=m!
spring temple
That sounds right.
Not 100% sure, as I haven't thought it all the way through, but it sounds right.
And then for n > m, you have some duplicates.
spring temple
That would not be a function.
finite depot
look at the circle equation
stable kettle
@finite depot but it's not a function
spring temple
It is not a function.
stable kettle
It's just a relatiom
spring temple
It's an expression defining a locus.
finite depot
x = y^2
spring temple
Is not a function in x.
stable kettle
It would be in y
finite depot
isolate it
stable kettle
For x it's just a locus
spring temple
For something to be a function, f(x) -> one value for all x in the domain.
It's a hard requirement.
stable kettle
@finite depot this is not a function for x
spring temple
Please stop querying wolfram. This is not in question and we are not mistaken.
stable kettle
Well, let's return on our problem
spring temple
For every element in A, the function will map to a single element in B.
More than one element in A can map to an element in B for it to be surjective.
stable kettle
It's the opposite that could be false
spring temple
And -every- element in B must be mapped to.
vital dewBOT
finite depot
2 output
spring temple
Yes. That makes that not a function.
finite depot
why?
spring temple
Because a function requires that every input have a single output.
vital dewBOT
spring temple
In mathematics, a function is a binary relation between two sets that associates every element of the first set to exactly one element of the second set
stable kettle
Literally every book will tell the same thing
finite depot
k
stable kettle
Well let's return on our problem
stable kettle
Yes, because each element of B can have only a single counterimage
So the second element has n-1 choises
And so on
spring temple
You have each element of B with at least one counter-image.
stable kettle
so n!
spring temple
And then n-m extra.
stable kettle
Yep
spring temple
To be distributed however you like.
I'm not sure how to work out the combinatorics of that.
spring temple
stable kettle
The problem is the balls are numbered
stable kettle
Ok look, I'll show my reasoning
finite depot
but why n! ?
spring temple
For the first element of B, there are n possible mappings.
stable kettle
@finite depot for the case n=m, the function can't be but bijective
spring temple
For the second, there are n-1.
For the third, n-2
etc.
n!
This only works for n=m
finite depot
A = {1,2,3} B= {1,2,3}
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
stable kettle
This is not a function
finite depot
they are set
stable kettle
Yes, but you have to follow the definition of function in order to find the right answer
finite depot
That rule of function I broke?
spring temple
For example (1 > 1, 2 > 1, 3>1) is not a surjective function.
As not all elements of B are mapped.
I'm not sure how to interpret the list you've made.
If all of those are one mapping, then it's not a function, because 1 is mapped to 3 different elements of B.
spring temple
We're counting -mappings- not combinations of elements.
stable kettle
@finite depot what you found is just the amount of possible relations
spring temple
And specifically, -surjective- mappings.
So for each function from A -> B, choose three of those relations.
One for x=1, 2, and 3.
And insure that every y is present.
So if we pick (1,1) then we could also pick (2,2) and (3,3) OR we could choose (2, 3) and (3, 2)
If we pick (1,2), then we can choose (2, 1) and (3,3) or (2, 3) and (3,1)
And if we pick (1,3) then we can choose either (2,2) and (3,1) or (2,1) and (3,3)
That's every possible surjective function from {1, 2, 3} to {1, 2, 3}
spring temple
Anyway, for the n > m case, I'm probably not going to be much help. Combinatorics was never one of my better subjects.
stable kettle
@spring temple I'll show how I processed this
My method was to get the number of surjective functions from the total amount of possible functions removing the non-surjective ones
finite depot
If you can find a general formula for case n>m
Then it does also apply for case m=n
stable kettle
That's what I'm doing
The total amount of functions is tge dispositions with replacement of |B| in |A|
So $|B|^{|A|}$
vital dewBOT
Italyball
stable kettle
Then I can remove all the non-surjective functions
stable kettle
Given $n<|B|$ elements, the amount of functions to remove is $n^{|A|}$
vital dewBOT
Italyball
finite depot
@stable kettle right?
finite depot
Nah
stable kettle
I found the mistake
spring temple
Like I said, combinatorics was never my strong suit.
stable kettle
The number I said is valid only for those n elements
spring temple
I can do it, but I have to put a lot more thought into it than I'm able to spare right now.
stable kettle
I see
finite depot
Why are you doing this?
stable kettle
Because I had an exercise for this problem and wanted to find a general case
I think I fixed it
I have the belief I found the final formula
stable kettle
Yes
weary tiger
a way you can do it
but its a bit computational so cba
is consider it using inclusion exclusion by thinking of all functions that dont hit one of the values of B
then all of the functions that dont hit two of them and so on
them using inclusion/exclusion on that and subtracting from total functions
i dont think theres a nice way and will probably always result in a sum
stable kettle
This is my guess
Where D stands for simple dispositions and D^r for dispositions with replacement
@weary tiger I'm a first grader at uni so yeah
finite depot
stable kettle
Take it with a grain of salt
The problem is that this answer tackles only low powers of A and B
The non important cases are eliminated by simple observations
vital dewBOT
Italyball
stable kettle
I had made a little mistake
I'm pretty confident this is a fulky right answer
Well, if |B|=1 it works
If |B|=2, |A|=2, it works
I think we are onto a winner
For any value of |B| it works
Now I have to look for what happens when I change |A|
Nope it doesn't work
The second member doesn't work anymore when |A|>2
@weary tiger since I don't know what inclusion exclusion is, I tried to do it myself
@spring temple welp, my try has failed lmao
At least it's an A for effort 
spring temple
Did you learn anything?
Other than "This way doesn't work" that is. (not that that's a bad thing to learn)
stable kettle
Welp, I was applying in my mind how to work with combinatorics in this particular case
For some reasons, this formula actually got right the answer to the statement that sparked this whole thing @spring temple
And I was like "yes, this has to be right"
But nope
Wait
No nothing
I thought I found the mistake
But nope
If someone wants to tackle this
To modify my formula
clever sage
For $n \geq 1$, let $S_{n}$ denote all bijections from an $n$ -element set to itself. Prove that $\left|S_{n}\right|=n !$
vital dewBOT
Moosey
clever sage
What would be a good way to phrase this induction wise? I meant I feel like I can't just be like oh, {1} -> {1} only has one bijection, {1,2} -> {1,2} has two, so on
assume {1,2,3...k} works
I'm just strruggling to sound technical with it
haha
gritty crescent
Use a simple combinatorial argument?
clever sage
???
gritty crescent
Since you'd like bijections, map an arbitrary element to any of the n elements, then map another element to any of the remaining (n-1), and so on. The number of unique bijections you get is n(n-1)(n-2)...1=n!
clever sage
Yes. I understand that
because for each f(nth element) you'd want to preserve injectivity
gritty crescent
Yes.
clever sage
I'm just struggling to sound technical with that though haha, and I think our professor wants an injective arguement
unreal stump
If you want an argument by induction,Take S_(n+1) ,now map the first element to (n+1) available elements
Now you are left with having to map n elements to n elements bijectively
That is,we have the case of S_n
So, |S_{n+1}|=(n+1)|S_{n}|
clever sage
so would I need to define a function for a bijection, and a set for the bijections to take place between for base cases
or
is there a way not to do that
like could I say "observe that there is only one possible bijection between set of one element" or like, "define a bijection B_n that goes from nth element set to another nth element set
Hmm...reading closer, we don't have to use induction, so I might just do the other case, since it seems much easier.
Without using induction, we can prove this. Let $f: A \rightarrow A$, where $A$ is a set containing $n$ elements, and f is a bijective function. Let us start off with an arbitrary element in $A$, and label it $x_{1}$. $f(x_{1})$ must map to one value out of a possible $n$ elements in $A$. Let us go to another arbitrary value in $A$, and label it $x_{2}$ We know the possible values $f(x_{2})$ must be $n-1$, as it cannot be $n$, otherwise there would be an overlap, and $f$ would violate injectivity. Let us pick a third arbitrary value in $A$, and label it $x_{3}$. To preserve injectivity, $f(x_3)$ can only be a possible $(n-2)$ values, as if it were $n-1$, then there would be an overlap of values, and it would violate injectivity. Continuing this process to until we reach the last element that hasn't been mapped, we label it $x_{n}$. $f(x_{n})$ can only be $1$ possible value, as if it were $2$, it would violate injectivity, and overlap with the possible values of $f(x_{n-1})$. Combining all these possiblities, we get the product $n(n-1)(n-2)...=n!$ It's clear to see this is equivalent to $|S_{n}|$.
vital dewBOT
Moosey
clever sage
I always end up being too wordy
and being vague
If $f$ is a bijection from a set $A$ of cardinality $n$ to itself, then let $(a_{1}, ..., a_{n})$ bean ordering of the elements in $A$. The number of possible elements $f(a_{1})$ could be then to allow $f$ to remain injective is $n$. It’s then easy to see the number of possible elements $f(a_{2})$ can be is $n−1$ elements to remain injective. We willc ontinue this process until we get to $f(a_{n})$ This could only map to one more element in $A$, which would be the last element left in A, making $f$ bijective. Simply combining these possibilities into a product leads ton $(n−1)(n−2)...(2)(1)$ It’s clear to see this of the form $n$!, which is the number of possible bijections from $A to A$, i.e.$|S_{n}|$
vital dewBOT
Moosey
weary tiger
you are literally writing
First element can map to n things second to (n-1) and so on so there is n*(n-1)*..*1=n! bijections
seems a bit longwinded
clever sage
thank you
I feel like I shouldn't just say that though
so I don't have to specify a set, or anything like that???
I do recognize that it is brief
I just struggle putting these proofs into words
haha
and scared I will miss a case or smth
or my professor will be like 'oh what if n is 1' so n-2 doesn't make sense
just like, something annoying like that
wicked basin
i do not understand the third row can someone please explain
pale epoch
this is a definition
but this is the so called principle of explosion
if you assume something that is false, you can deduce anything
wicked basin
ok so it just be like that?
pale epoch
kinda
the formal reasoning is, that if you assume $p$ to be both true and false, then you can consider $p \lor q$
vital dewBOT
Lochverstärker
pale epoch
now that is true, because p is true
but p is also false, so q must be true
therefore proving any q
this explains the last two rows
dry patrol
i do not understand the third row can someone please explain
the way i was taught is, if p is false then whatever u say after it will be true, an example is if the sun is purple then the moon is green
since the first thing was false it doesnt matter what you say after, it will always be true
autumn pebble
I am not sure what these questions are asking
frigid moss
In how many di↵erent ways with respect to their numbering (irrespective of colour)
can the 11 sphere wood pieces be arranged in a line of length 11
Justify your answer
How would I do this
balmy cedar
hi can u solve this
Try to think of it this way: to get a spanning tree you must remove enough edges to get rid of cycles in the graph (on the other hand, once you get rid of the cycles, you can't remove more edges, since then it will no longer be a spanning tree).
iron pine
so there must be 5 edges for all spanning trees, right?
iron pine
Try to think of it this way: to get a spanning tree you must remove enough edges...
only 5 edges, not more not less?
iron pine
<@&286206848099549185>
balmy cedar
only 5 edges, not more not less?
Yes
@iron pine The question becomes: how many ways can you remove two edges to get a spanning tree?
iron pine
how can i generalize the solution. is there an explanation that says remove those edges which has those features
balmy cedar
First of all, did you solve this specific case? Generalising to any graph seems to be very non-trivial
balmy cedar
Yes, it is an interesting question, we can try to discuss it and work something out, if you want
I mean, the goal would be to come up with an algorithm that counts the number of spanning trees, I guess
Well, for that I guess you just need a modification of breadth search though
iron pine
Actually there is some formula called kirchoff . but if i want to think only this question i have detected the edges that I should remove one by one. If someone asked you forgot these 2 combination what should I say. Or if this graph were bigger what would I do
how can i generalize the 2 edges that i should remove
iron pine
how can i generalize the 2 edges that i should remove
this is more spesific and logical question i guess
balmy cedar
Well, there is one class of graph that is simple: if all the cycles in the graphs are edge-disjoint. Then you could remove any edge in each cycle, so the number of spanning trees is just the product of the sizes of the cycles
In the above graph the cycles intersect, because of the edge b-e
So that makes it a bit more complicated
iron pine
i wonder something else, is it always n vertices and n-1 edges in spanning trees
iron pine
and also the subgraph should include all vertices. i can remove edges but can not remove vertices?
balmy cedar
Yes, this is true. Also, you can't remove edges that disconnects the graph - then the subgraph can never be a spanning tree
(It could still be a "spanning forest", but that's something different)
iron pine
ok. thanks a lot. i am really really grateful
all of those information is really helpful for me
balmy cedar
Np. When it comes to counting spanning trees, I think the thing that complicates it is overlapping cycles. So a graph with high connectivity (= many edges, so a complete graph has the highest connectivity), will have many overlapping cycles and the counting of cycles will be more complicated
weary tiger
is there someone who knows graph theory?
obtuse lance
yes
errant bear
no
shut fjord
I’m stuck at this part where I’m trying to show a relation between gcd(x,y) = gcd(x +ky, y) through z
How can I show a relationship between the two sides?
I know that if k is some multiplier of y, ky will be divisible by the same values as y
noble wasp
can someone explain to me what this means
a set S is countable if one can find a bijection between natural numbers and S
minor zephyr
do you know what a bijection is?
or.... i guess you do since youve done some ring theory
It means you can define a function f : N to S such that f is injective and surjective
intuitively, it means you can use the natural numbers to enumerate the elements of S in a sequence
noble wasp
bijection is onto and 1-1
ohh, do you have example for that
ik N would be natural numbers but what is S ?
any set?
what do you mean by countable?
okay loll i came up with this example
will that be right?
errant bear
is f injective?
noble wasp
hmm i was trying to show that it was bijective
clear sierra
Can someone explain to me why a conditional statement with a false hypothesis is true?
clear sierra
nevermind lol, it just clicked after 20 minutes of thinking about it.
stable kettle
I guess it's free here
I have an exercise where I'm asked to prove the following sentence
vital dewBOT
Leo X de' Medici
stable kettle
The first thing I did was to divide the problem in the two subparts
Determined by the two directions of the iff
But then... I don't know how to continue
Like I have to prove in the first case the whole equality on the right?
stable kettle
<@&286206848099549185>
stable kettle
Welp, I resolved the first step of the problem
Now I'm trying to resolve that, given that the intersection of the images is equal to the image of the intersection, f is injective
I tried going this way:
We set $x_A \in A$ and $x_B\in B$ such that $f(x_A)=f(x_B)=y$. This tells us that $y\in f(A)\cap f(B)$ and, by hypothesis, we get $y\in f(A\cap B)\iff x_A,x_B\in A\cap B$
vital dewBOT
Leo X de' Medici
stable kettle
But I don't know how to continue, since there is nothing that can help me say x_A=x_B
stable kettle
@pale epoch My problem continues over this one
It's a continuation of what I posted before
pale epoch
yes, i know
stable kettle
A and B are subsets of the domain
pale epoch
in this direction the idea is that you choose A and B
generally you want to show f(a) = y = f(b) => a = b
so now you should choose smart subsets A, B of X and use the hypothesis
stable kettle
Yep
That's what I tried
But I only get that a and b are in the intersection of A and B
I can't find a condition that makes them equal
pale epoch
again, what is A and B?
stable kettle
Subsets of the domain
pale epoch
that's not very specific
stable kettle
Proper subsets of the domain
stable kettle
Yes
pale epoch
and you want to use this to create a statement about sets A, B
stable kettle
Yes
pale epoch
you can freely choose those sets A and B
it makes sense to choose an A such that a \in A and B such that b \in B
do you know a specific subset that includes A?
stable kettle
it makes sense to choose an A such that a \in A and B such that b \in B
It's what I did
stable kettle
do you know a *specific* subset that includes A?
Uh
The two sets can be any of the proper subsets
stable kettle
A and X
pale epoch
what's A
A is not given
X ok, but that won't work
what's the smallest set that includes a?
(the exercise doesn't even matter to answer this question)
stable kettle
what's the smallest set that includes a?
{a}?
pale epoch
yes
and certainly b is in {b}
and both {a} and {b} are subsets of X (since a, b is in X)
try applying what you know about f with those sets
stable kettle
OH
I set A to be {a} and B to be {b}. I know that f(a)=f(b)=y that belongs to the intersection of the images of A and B. For supposition, y belongs to the image of the intersection, so a and b are part of the intersection, but we know A and B contain only a and b and we're looking for the intersection, so we get that A=B, so a=b?
@pale epoch
pale epoch
essentially
stable kettle
I think I haven't explained it really well
pale epoch
writing it down "correctly" is a bit iffy, but that is the idea
you can also assume that a != b then the intersection of {a} and {b} is empty and then ...
stable kettle
Actually, the fact y belongs to the intersection of the images is enough to say that the intersection isn't empty?
pale epoch
what intersection?
stable kettle
Of A and B
pale epoch
well, you get that $f({a}) = {y} = f({b})$, so $f({a} \cap{b}) = f({a}) \cap f({b}) = {y} \neq \varnothing$
vital dewBOT
Lochverstärker
stable kettle
Both because of the supposition and for the definition of image, I suppose
pale epoch
yes
and well, if a != b then the intersection of the sets is empty, but the image of the empty set is the empty set
stable kettle
I get the steps to do. This is more of a off-topic question, but during a demonstration, adding additional properties to generic objects (like subsets in this case) can be done every time?
As long as the object is generic obviously
pale epoch
what do you mean by additional properties?
stable kettle
Like for example the fact here that I took subsets that contained only the elements I was considering
pale epoch
in this case you had a statement like "for all such and such you know that this is true"
and if you want to deduce something from that, you kind of have to make specific choices
and since you wanted to show something about elements a and b, there weren't many choices
you were only given that some statement is true for all subsets and you were given a, b in X
so there are really only a few subsets you even know can exist
X, {a}, {b} and {a, b}
stable kettle
@pale epoch I see. I've never been good with mathematical demonstrations...
Hope I'll be able to get better with them
Thanks for the help! 
latent rivet
Can anyone help woth mathematical logic questions?
last timber
shut fjord
I know this looks kinda rough in terms of a proof because I haven’t really formed proper sentences but my idea was to use a 1 to 1 correspondence to prove that both sides are equal,
Which means I have to show LHS <= RHS and RHS <= to LHS for them both to be equal
Is this a good approach for the problem I am attempting? I’m sorta lost as to what I need to do to prove this.
mystic moss
where did this come from?
lyric pumice
@mystic moss I deduced it. It is a generalization of a result that is found in Stanley's Enumerative Combinatorics.
@mystic moss Here is a more interesting one.
@obtuse lance
weary tiger
im having trouble trying to figure out which one of these are statements vs propositional functions
initially i thought these were all prop. functions
obtuse lance
<@!494362718321639427> I deduced it. It is a generalization of a result that is ...
by "where did this come from?" we're not asking for a physical location, but a derivation or counting problem or something
otherwise it's just a random formula without useful context
lyric pumice
@obtuse lance It is based on counting the number of ways to distribute objects of different types to different people.
So, you might be distributing n objects of t types to p people in some fashion.
obtuse lance
I see, and you derived this with generating functions I guess which is why you want a combinatorial argument?
lyric pumice
I did not use generating functions. I used a combinatorial argument.
mystic moss
@lyric pumice what do the double parentheses mean?
lyric pumice
@mystic moss Multi-choose.
wicked basin
what does the upside down A mean?
wicked basin
ok what about the rounded E
delicate cedar
"element of"
wicked basin
o ok thx
bleak jolt
if a relation R exists between elements of the set A X B, is the domain of R A, and the codomain B?
or would it be x for (x,y) in R for domain and y for (x,y) in R?
weary tiger
Can someone confirm that I did this negation right? I’m new to discrete apologies
haughty garden
wouldn't it be x ≥ n instead of x < n
weary tiger
Ah I see thank you
gritty crescent
if a relation R exists between elements of the set A X B, is the domain of R A, ...
It would likely be a map from AxB to itself, i.e., (x,y)R(p,q) for (x,y),(p,q) in AxB.
bleak jolt
@gritty crescent i see so in terms of like python it'd be like
C = D = {-3,-2,-1,1,2,3}
R = {(x,y) for x,y in itertools.product(C,D) if ((1/x)-(1/y)).is_integer()}
Rdomain = {x for x,y in R}
Rcodomain = {y for x,y in R}
just trying to see if i have it right
gritty crescent
I'm not entirely familiar with programming, but it looks good to me.
At least the math bit seems legible.
bleak jolt
alright cool so like
the domain of R is exclusive to the elements that fulfill it (excluding those that don't fit the relation that defines the set)
and the codomain is exclusive to the result of the method applied excluding those that don't fit the "rule"
ok
mystic moss
<@!494362718321639427> Multi-choose.
i see, makes sense. the first one was nice 
but i haven't gotten the second yet
bleak jolt
Sorry to bother you, but in this case the domain would then be {-1,0,1} and codomain would be {u,w}? @gritty crescent
lofty iron
Hi, I am doing a formal proof (well, formal enough anyway) which involves a set n and I am currently at the step |n|=2+a (a is a natural number {0, 1, 2, ...}). Essentially, I have proven that n has at least two elements. I need to instantiate two elements of this set n. This is my best guess as to how I can get there, is my logic correct? Any suggestions? I am not the most experienced with formal proofs. (note that I didn't really get to step 1 by assumption, but the previous work should be irrelevant). Any help would be greatly appreciated! Thanks! 🙂
P.S. I would appreciate a mention if I get an answer bc I have the server muted. Thanks again!
gritty crescent
Sorry to bother you, but in this case the domain would then be {-1,0,1} and codo...
You're right about the domain, but the codomain would be defined as the entire set B, i.e., {t,u,v,w}.
lyric pumice
@mystic moss Oh, good.
Hmm. I think I need to retract the second one.
@mystic moss
mystic moss
Hmm. I think I need to retract the second one.
Yeah, I’m not seeing where you got the rt from on the RHS.
wise agate
I think that this might be the right place! Sorry in advanced if not. I'm trying to understand this set, to me it seems like it's a set of 1 unit, a singleton (1,1),but I'm not entirely sure. Would appreciate if anyone can confirm
unreal stump
Did you get x.y=0?
wise agate
I thought x,y could only be equal to 1
unreal stump
Or does your defn of N not include 0?
wise agate
Yeah 1 and up
unreal stump
Yea, It's a singleton if so
wise agate
Thank you!
unreal stump
The first of the 2 statements(linked by or) will always be false
Yea, It's just the singleton (1,1)(because 2nd statement)
wise agate
I understand
Thank you
mystic moss
so from the previous identity, each of the factors on the LHS should reduce to $\left(t\choose{x_l - rt}\right)$, but the first term in the alternating sum is already that. is that intentional? do the rest of the terms happen to cancel out?
vital dewBOT
Madeleine
lyric pumice
@mystic moss That looks right. It is somewhat awkward, but the setup will prove to be important in a later example.
languid cradle
i know there is an even amount
in graph G
is it asking for the complement of G? not sure
minor dagger
yes the complement graph
mystic moss
<@!494362718321639427> That looks right. It is somewhat awkward, but the setup w...
doesn't it not work for r=1, t=3, and x_l=4?
balmy hornet
Wait to make sure I’m thinking this right, Φ = {Φ} and Φ < {Φ} is not true but Φ ⊆ {Φ} is true right?
burnt pewter
weary tiger
in set theory its correct that {} is an element and () is like an array, but I can't recall is array the right word?
e.g. say you had
{(1, 3), (1, 4), (2, 3), (2, 4)}
actually wait
this is confusing, help
what are the two differences in brackets here basically regarding set theory
is this right?
- () = ordered pair, collection of 2 elements```pls @ me when responding
weary tiger
wdym?
blissful zenith
Consider the following 2-player pebble game. We start with n pebbles and the players take turns removing1,2,3,4, or5 pebbles. Whoever takes the last pebble loses.For which n does the second player win?
i really am not sure how to start answering this
i also need to prove it w induction
magic peak
For a sentence to be a proposition it needs be declarative. Consider $x + 1 = 2$ it is not a proposition. Could we turn it to be a proposition if we add $x in {1,2,3}$?
vital dewBOT
Noby707
noble wasp
can someone help me with a proof
coral raven
proven silo
so since p/q is a root that means $a_n(p/q)^n+{n-1}(p/q)^{n-1}+...+a_1(p/q)+a_0=0$
vital dewBOT
ScapeProf
proven silo
if you then multiply by $q^n$ on both sides of the equation and do some simplifying and isolate $-a_0q^n$ you can then deduce that p divides $a_0$
vital dewBOT
ScapeProf
proven silo
and use the same trick for showing q divides $a_n$
vital dewBOT
ScapeProf
proven silo
@noble wasp
noble wasp
yes
tranquil jewel
can someone help with the part of this question where I use the inequality to prove the interval thing im not sure how to go about it
naive gulch
Just going to say I spent an hour trying to do a logic puzzle problem and didn’t get it right
it’s a tough life out here for the logically challenged
next pulsar
Hello, how would I convert a given pi digit at a certain position from hexadecimal to decimal?
My program is outputting the following in hexadecimal, but I can't manage to convert it to decimal after searching on Internet several times 3.243F6A8885A308D313198A2E037073
next pulsar
Any ideas?
coral raven
i think you just want to convert it to decimal first, since the digits before it will also affect it
just the whole thing
next pulsar
The number would be way too long
This seems to work before the 300th digit : ```lua
local dec = string.format("%x", hex) / math.pow(16, position) * math.pow(10, position)
dec = dec + overflow
local whole = math.floor(dec)
overflow = (dec % 1) * 10
return whole```
warm isle
This seems to work before the 300th digit : ```lua
local dec = string.format...
You could do some bit hacking for that but I dunno seems like that would be overkill. Something similar like converting the binary to BCD and that way get your position but I think double dabble would overflow aswell defeating the whole purpose.
warm isle
can you elaborate ?
I am trying to think of a better solution using Boolean algebra and modular arithmetic. The thing I proposed would be overengineering
next pulsar
Well, as long as it is reliable. Computing power doesn't really matter in my case @warm isle
I'm not looking to compute millions of digits
hollow badger
yo
this is number theory
could someone tell me what that symbol of the circle with the dot in the centre means
multiplication operator?
hollow badger
so it could be anything ?
hollow badger
yup
shell sparrow
can someone explain this to me, given no n and k, now we split n into k numbers, like if n=6, and k=4, then 6=1+1+1+3, or 6=1+1+2+2, ...
so whichever combination i choose it cannot have the maximum no smaller than 2,
now how do i find that number??
the ans is floor((n+k-1)/k) but how??? (for n=6, k=4, this gives floor(9/4)=2)
?
prime steeple
lethal prawn
Hi, I'm new to Discrete Math and I have trouble figuring out this problem.
Consider these relations on the set of integers (Z):R1 = {(a,b) | a ≤ b},R2 = {(a,b) | a > b},R3= {(a,b) | a = b or a = −b},R4= {(a,b) | a = b},R5= {(a,b) | a = b + 1},R6= {(a,b) | a + b ≤ 3}.Which of these relations contain each of the pairs(1,1),(1,2),(2,1),(1,−1),and(2,2)?
frigid abyss
anyone know how to go about making a truth table for this problem. I know how to for P but the variable 't' in the Q= expression is throwing me off
the goal is to find if P is logically equivalent to Q
naive gulch
Are the statements all do not and none do logically equivallent?
stray reef
are those even statements
naive gulch
If the statement was "None of the cats liked the fish" and "All the cats did not like the fish"
Like so
For all, not this and not this, and not this
stray reef
If the statement was "None of the cats liked the fish" and "All the cats did not...
see this way it's a lot less confusing
yes those are equivalent
naive gulch
Ah okay just checking
Am I allowed to write three quantifiers in a row like this
there is a student in your class who has this animal as
a pet.```So I assume saying E!x etc. and etc. and etc. means there is one unique student who owns all 3
but the question is asking one singular student owns one animal each
vital dewBOT
Ann [omw out]
stray reef
anyway i would replace those commas with ands
$(\exists x: C(x)) \land (\exists x: D(x)) \land (\exists x: F(x))$
vital dewBOT
Ann [omw out]
naive gulch
anyway i would replace those commas with ands
Oh I'm really stupid I read the question as there is one student not there is a student
that makes sense ty
ember solstice
Why is the following inequality correct? (metric graph theory)
$diam(G) \leq 2 rad(G)$
vital dewBOT
271828
stray reef
can you remind me of the definitions of diam(G) and rad(G)
i'm guessing diam(G) is the max distance between any two vertices
but i don't remember what the radius is
ember solstice
radius is the min of all eccentrities
and the eccentrity of a vertex v is the maximum distance between v and any other vertex
stray reef
uh huh
well
ok
let r be the radius and let c be a vertex of eccentricity r
(c for center, etc.)
then i claim the distance between any two vertices is at most 2r
because to go from a to b you can go through c
d(a,b) ≤ d(a,c) + d(c,b) ≤ r + r = 2r
d(a,b) ≤ 2r for all a, b ∈ V
stray reef
triangle inequality is very very important
weary tiger
Is in a graph theory hw
how do I even setup this problem to try and use graph theory lol
stray reef
something something colorings
neat fog
Is there a way to find the number of possible graphs, where each edge has length L and each node has valence w, that can be fitted inside a given shape like a square of length b for example?
obtuse lance
I think it'll be generally an infinite number since you can place vertices arbitrarily close together. You might be restricted based on trying to get the valency to match up though.
for instance in the valency w=2 case we can make every possible even cycle in a square as long as L is less than the b*sqrt(2)
neat fog
for instance in the valency w=2 case we can make every possible even cycle in a ...
oh how did you get that
obtuse lance
maybe I'm wrong I didn't work it out so there could be some issue in the details
weary tiger
Heya, I just wanted to verify if a proof I did was "enough" sound proof
stray reef
ok, show your proof
weary tiger
assuming a is an element of Z+, and a = (b**2)c, where c must be square free and c must not have a prime factor of the form (4x+3), I have to prove that a is the sum of two squares
The way I interpreted "Having a prime factor of the form 4x+3" was that basically it had to be something that ISN'T logically equivalent to 3mod4
stray reef
b**2?
weary tiger
b^2
stray reef
right hold on
weary tiger
(sorry, am a programmer)
stray reef
pythonist, huh.
stray reef
so you're given that $a = b^2 c$ where $c$ is squarefree and has no prime factors that are 3 mod 4... and you need to prove $a$ is a sum of two squares
vital dewBOT
Ann
weary tiger
right
stray reef
okay, how are you going about doing that?
weary tiger
So basically, I did a proof beforehand that basically said
stray reef
no "basically" if possible, please.
stray reef
do you have the proof written out on paper or something?
weary tiger
chicken scratch 😅
stray reef
i for one would prefer to have it in a form where i could look over it as a whole
oh.
weary tiger
but, I was able to deduce by cases, that a number $n = j^2 + i^2$ can only be equal to 0mod4, 1mod4, or 2mod4
vital dewBOT
Bread
weary tiger
simply by plugging in cases such as i = even, j = odd, etc...
There was no case where n had the form 3mod4
stray reef
okay, so no sum of two squares is ever 3 mod 4
weary tiger
Yeah
stray reef
yeah, so what
weary tiger
would that be something I can basically carry over as a proof?
stray reef
you haven't presented any proof yet
you proved "sum of two squares => not 3 mod 4"
notably, this doesn't imply "not 3 mod 4 => sum of two squares"
i'm still waiting for you to present your proof of the result you posted originally:
that if a = b^2 c, where c is squarefree without prime factors that are 3 mod 4, then a is a sum of two squares
weary tiger
Ahh alright, I might have to think about the semantics a little more then
stray reef
so do you have a proof or not
im serious you havent given me anything i could check yet
weary tiger
OH WAIT I think I know where I'm making the wrong step
I thought I could use the proof I made earlier but I forgot that m is square free
Hold on, I will try to answer this myself and get back to you when I am done, sorry to take up your time
stray reef
m?
weary tiger
I mean c
b^2c is also the sum of two squares if c is a sum of 2 squares
but I didn't catch the fact that c must be square free
that's where I tripped up
stray reef
proving that c is a sum of two squares implies b^2c is a sum of two squares is relatively trivial
weary tiger
yeah
stray reef
ngl, i looked back through my 1st year notes and it sounds like what youve set out to prove is a pretty tall order
weary tiger
xD I mean, I am 2nd year haha
slow jewel
hi guys
fossil crag
discrete maths make me want to jump of a bridge
slow jewel
ive just started decrete maths this semester
burnt nebula
Hey guys i hope u all doing well 😊 . So guys i need sm help in the part ''b'' of this question. Im really confused and i don't know what to do exactly 😅
Let R be defined as a relation over ℕ ✕ ℕ as follows.
((n,m),(k, l)) ∈ R ⇔ n + l = m + k
a) Prove that R is an equivalence relation. ✔️
b) Characterize the equivalence classes and Quotient set generated by this relation.
sand cipher
Hey guys, got a few questions, and just wanted to make sure if I did this problem correctly.
livid drum
@weary tiger Let us express (A) to help find an expression for (B).
It reads in my interpretation as this:
There exists an object y st. y is a real number and for all objects x, if x is a real number then y is greater than x.
And before seeking to symbolically translate (B),
Ask yourself if (A) is sensibly true.
From intuition, is there a real number larger than every other?
Obviously not, right.
And how might you convince others this?
||Suppose there were. Call it inf. What about inf + 1?||
weary tiger
@noble wasp you've got infinum and supremum the wrong way around
and why would sin(1/7) be the smallest when you can have sin(1/8) (and then sin(1/9) and so on)
near prawn
why randomly stop at 7 tho
noble wasp
hm yeah but would it be infinity?
noble wasp
hmm im lost lol
stray reef
and you mixed up supremum and infimum in your screenshot
you got it right that the sup is sin(1), because sin(1) is actually an element of your set & is greater than all the other elements
do you understand that much
y/n
noble wasp
yes what you told me yes
stray reef
okay
now to deal with the infimum
do you agree or disagree that 0 is a lower bound for your set?
noble wasp
oh, i got confused with that
stray reef
0 <= (any element in your set)
agree or disagree?
noble wasp
agree
stray reef
okay
now, can we make this bound tighter? that is, can we put a number bigger than 0 on the left, such that the inequality is still true?
the answer is no bc sin(1/n) gets arbitrarily close to zero for large enough n
noble wasp
ohh, question can we plug in 0 into sin (1/0) and it will make it undefined?
stray reef
and why, pray tell, would you want NaN in your set
ember solstice
what is nested union of sets?
vital dewBOT
Commander Vimes
last timber
@ember solstice
ember solstice
in the context of finitary closure operators
mystic moss
@lyric pumice you still here?
dire sphinx
i need some help interpreting (b) in this exercise, i don't quite understand the relation here
what is the meaning of x + 1 and why is it not used on the right hand side?
if x = 1 and y = 3 what would P(x,y) be and why?
fossil crag
can someone explain how to find the subgroups of a group?
pale epoch
in general it is not easy
fossil crag
can you help?
pale epoch
are you looking at a specific group?
pale epoch
well, in this case the group has small order (namely 6)
so there aren't too many possibilities due to lagrange's theorem
fossil crag
Is order the amount of elements in the set?
pale epoch
yes
fossil crag
so would the possibilities be like {0,1},{0,2}....
pale epoch
have you covered lagrange's theorem?
pale epoch
ok, so what orders can the subgroups have then?
fossil crag
3?
pale epoch
yes, but that's not the only possibility
fossil crag
and 2
pale epoch
yes, and also 1
fossil crag
and one is the identity ?
fossil crag
does each of the subgroup contain the identity?
fossil crag
ok
pale epoch
now is there anything you know about groups of order 2 or 3?
pale epoch
did you cover cyclic groups?
fossil crag
yes
pale epoch
then check your notes (or try to prove) that groups of prime order are cyclic
then conclude that all proper subgroups of your group must be cyclic
and this should tell you what to look for
pale epoch
eh, not necessarily
- is defined in a weird way
but that doesn't matter, because proper subgroups must be cyclic
(at least in this case)
fossil crag
how do i list the possibilities?
pale epoch
what is a cyclic group?
fossil crag
a group that is generated by a single element
pale epoch
yes, so you have to look at those subgroups
as they must be cyclic, they are generated by a single element of the group
fossil crag
what is the generator
fossil crag
thats long 😫
pale epoch
i don't think there is much else you can do
what are you trying to compute? the number of possible permutations or just the functional ones?
i am certain there are different ways to look at this
the way i would look at this is the following:
you have n possible spots
and a configuration is uniquely determined by where you place the defective antennas
so out of the n spots, you have to choose m spots on which the defective ones would be placed
well, is there a difference between placing defective antennas at spot 1 and 2 and placing them at spot 2 and 1?
indeed
i have an idea, but it's not fully fleshed out
ok, so imagine you place the defective ones first, all in a row
then you have m-1 spots (ignoring the edges) between them
and into each of those inbetween ones you have to put at least one functional antenna
so it's like placing n-m identical balls into m-1 boxes
such that each box contains at least 1 ball
i think this is stars and bars?
hm, actually you have to consider the edges as well
pale epoch
so it's like placing n-m identical balls into m-1 boxes
so this is not quite correct
but there might be a simpler way
graceful vapor
For (b), it would be 6 ways right?
and would (c) be null?
it probably is just 1 way though.
unreal stump
c is 1,b will be 4!/2!=12
unreal stump
Yes
unreal stump
When everything is distinct you have 4! Cases
Let's take A,B,C,D,E to denote the 5 distinct shrubs
Now suppose A and B are of the same type, note that
ABCDE and BACDE would have been distinct if A and B weren't the same,but assuming they are same makes them identical copies of each other
For each ordering,you can find 2 identical copies in the original arrangement
2!(distinct arrangements)=4!
graceful vapor
And that will apply the same even if its arranged in a circle?
graceful vapor
Okay thank you I think I understand
vital dewBOT
mirzathecutiepie
mirzathecutiepie
mirzathecutiepie
mirzathecutiepie
mirzathecutiepie
mirzathecutiepie
lyric pumice
@mystic moss Hello.
mystic moss
doesn't it not work for r=1, t=3, and x_l=4?
@lyric pumice so did this counterexample work?
lyric pumice
Yes, it is a counterexample.
mystic moss
ah wait, so is there a way to tweak the expression to make it true?
mystic moss
ah do tell!
lyric pumice
I'm working on a challenge problem.
mystic moss
i guess i'll see it when you put it up then
rustic stratus
Im confused why there is no 2 R 3 for this example
weary tiger
@rustic stratus there is
rustic stratus
is it just not listed?
weary tiger
ye
its just using examples
1 is related to 2, 2 is related to 3 and 3 is related to 1
rustic stratus
okay ty
dire sphinx
i did (a) of this exercise, but i am realizing that i don't quite understand what a corresponding relation means, e.g. in (b) and (e). can someone point me in the right direction?
is U = P(N) the universe of all sets of natural numbers?
the class i am taking haven't covered sets or relations yet, we just jumped straigth to chapter 12, which i find very strange
empty lintel
can someone help me with this problem
weary tiger
@empty lintel what do you need help with
what's the truth value of the statement if p,q are True?
empty lintel
@weary tiger here what I did
weary tiger
thats the whole problem
so you have your answer
the statment is T when P is T and Q is F
empty lintel
I don't know how to write it down in those squares
weary tiger
write T or F for the truth value of p,q
so you write T in the first square and F in the second
is that what u meant lol
dire sphinx
lgtm
weary tiger
ye
weary tiger
@noble wasp what is your definition of a set being countable?
graceful vapor
This is just using the Binomial Coefficient Formula right?
Where n = 8 and k = 3 for a and k = 2 for b
weary tiger
ok so do you see why (a) implies countable
noble wasp
hmm no 😦
weary tiger
so you have a map that looks something like this lets call it f
can you change this function so that it is a function between S and a subset of N (what is f(S))
humble bridge
How do I prove this?
errant bear
i mean, sure(?) but whats the context
autumn pebble
I was told to solve for n=3 through induction of the given variables a and b. The computation should equal n=1, 2.7+ n=2, -0.7+ n=3, -2.1 = -2.1
That’s all the “context” I was given for the problem induction where n=3 and k=1 for (ak+b) if a =-3.4 and b = 6.1
The final solution would be -2.1 correct since you add up the sum of each n until the third
Right?
@errant bear
weary tiger
Can anyone help me with some logic?
weary tiger
clear sierra
is this book making a mistake? What it’s asking me to prove is... false? They make it seem true by cubing the second 2. why do they cube it?
@weary tiger That’s a proof by contradiction problem. Try starting there.
weary tiger
I'm having trouble even setting up a negation, would that statement use XOR?
errant bear
i just gave you the contradiction, if x isnt an integer or irrational, then x is in Q \ Z = {p/q | q is not 1, and p and q minimal}
and yeah, not sure whats going on but there are definitely typos or smth levi
clear sierra
If n is a perfect square then sqrt(n) is a an integer and therefore rational, so it suffices to prove that if n is not a perfect square, then sqrt(n) is irrational.
We prove by contradiction. That is, we suppose that the square root of any non-square number is rational.
thank you @errant bear Just making sure i’m not crazy😂
errant bear
what book is that from
clear sierra
Discrete Mathematics and it’s Applications by Kenneth Rosen
it’s not the latest edition so that’s probably why
weary tiger
Can I DM either one of you what I have written down?
weary tiger
mk makes sense
weary tiger
I think he expects a mixture of both, but I need to atleast set up the negation using quantifiers and predicates.
errant bear
ok i mean, unless he specifically said to structure your proofs like this... i would stay away from using strictly symbols/predicates
most of the time its only necessary when learning it/the basics
ok i mean, i know its just the negation/statement
so its fine i guess
weary tiger
So you said start with sqrt(n) = a/b as a starting point
errant bear
yes
weary tiger
Alright I'll try to see what I can come up with thanks