3k + 3 = 3k + 6
#discrete-math
obsidian rampart
obsidian rampart
ohh +3 ok
i was confused by that lul
wait did you get the +3 by substituting k+1 in for n getting 3((k+1) + 1)?
that would make sense but wanna make sure.
obsidian rampart
yeah the base case?
obsidian rampart
what would the base case be then?
stray reef
the base case is the case n=0, and you have that already
obsidian rampart
yeah it = 3
stray reef
say you were working with $\sum_{j=0}^{k+1} j^7$ or something
obsidian rampart
ok
stray reef
so then
vital dewBOT
Ann:
obsidian rampart
you start with 0?
stray reef
i'm just showing you how to split the sum in a way analogous to what i did earlier
obsidian rampart
oh ok
stray reef
$\sum_{j=0}^{k+1} j^7 = \left(\sum_{j=0}^{k} j^7 \right) + \left(\sum_{j=k+1}^{k+1} j^7 \right) = \left(\sum_{j=0}^{k} j^7 \right) + (k+1)^7$
vital dewBOT
Ann:
obsidian rampart
ok i can see the steps in that
makes sense
once again, thank you. my professor tried to cover this in a 45min lecture lol
was confusing.
elder frigate
If I have a function where the domain is a subset of the codomain, and the function is surjective, how can I prove that the cardinality of the domain is equal to the cardinality of the codomain?
I can prove that the cardinality of the domain is greater than or equal to the cardinality of the codomain since I know that there exists at least one element in the domain for each element in the codomain (since the function is surjective).
But I would need to prove that the cardinality of the codomain is greater than or equal to the cardinality of the domain to prove that they are equal. I don't know how to prove that
viral stump
how did you define cardinality?
you usually have that A <= B if there is an injection from A to B
and for subsets this is true
to show that a surjection A -> B gives rise to an injection B ->A you need to use choice
elder frigate
the number of elements in the set
I mean it makes sense that |A| = |B|, because A is a subset of B and every element in A must map to every element in B, but apparently I cannot use the fact that it is a subset to prove |A| <= |B| which is what throws me off
@viral stump what do you mean by "choice"
viral stump
are your sets finite?
viral stump
then how did you define cardinality?
elder frigate
the number of elements in a set
viral stump
no
elder frigate
that's what the prof says is true
viral stump
that's informal
elder frigate
|A| = |B| where A and B are infinite sets
elder frigate
the number of elements in A
elder frigate
it's not supposed to be a number, but the idea is that if A has an infinite number of elements then the number of elements in A is equal to the number of elements in any other infinite set
viral stump
that's wrong
elder frigate
like |Z| = |N| even though N is a subset of Z
elder frigate
that's not what the course is teaching
I don't really care what's accurate or not I just want to pass the damn class
viral stump
i have no idea what your class is about then
elder frigate
discrete math
viral stump
you said cardinality, I'm telling you how cardinality works
elder frigate
anyway, so if I have a surjective function from A to B
how do I create an injection from B to A
viral stump
using choice
elder frigate
the function is not defined btw, it's just saying a function from A to B
and that it's surjective
can you explain what you mean by "choice"
like give an example
viral stump
axiom of choice
let f:B->A be a surjection
this means that for any a in A the fiber f-1(a) is nonempty
by the axiom of choice there exists a function g:A->B that assigns to each a in A some element of the fiber f-1(a)
azure lichen
you can probably use it without justification. axiom of choice is generally just accepted
it’s needed to even state that such a function exists, basically
anyway, defining cardinality as “number of elements in the set” works perfectly for finite sets, but “if A and B are infinite sets, then |A| = |B|” is just wrong
there are infinite sets of different cardinality
for example, the powerset of a set is always larger than the original set
elder frigate
I understand that
Basically the way how it's being taught is we create a function that maps from one set to another and use that to determine if it's smaller than or equal to and then another function where we can determine if it's greater than or equal to and then use that to infer that it's equal
like all infinite sets are equal but you need to prove it through functions you can't just declare them equal
quaint river
there are different infinities 🤔
elder frigate
yes
azure lichen
like all infinite sets are equal but you need to prove it through functions you can't just declare them equal
but they aren’t and you can’t do that
sage island
elder frigate
@azure lichen yes I understand that there are an infinite number of infinities but, at least for the purpose of this course, two infinite sets have equal cardinalities
as long as you can prove it (and normally you can)
like the cardinality of the set of natural numbers is equal to the cardinality of the set of all integers
azure lichen
yes, but it is not equal to the cardinality of the real numbers, which is very important™
elder frigate
if you're talking about countable/uncountable infinities, that's some other thing I wasn't talking about
azure lichen
if you say “infinite sets” without any qualifier, then uncountable sets are part of that
if you only want to think about countable sets, that’s fine
but you have to specify that
ripe cave
"for the purpose of this course two infinite sets have equal cardinalities as long as you can prove it"
If you can prove it that means you somehow had to define cardinality, right?
viral stump
clearly they defined cardinality in the usual way in his class
as he admits sometimes
marble wing
If K (r,s) is a bipartite graph with 2p vertices, prove that there is no ordering of vertices such that the greedy colouring algorithm produces a p + 2 colouring
Can anyone help? I've got a long ass proof for this but I feel there's a way shorter one
sudden knot
what does K(r,s) mean? complete with r+s=2p?
marble wing
r + s = 2p, not necessarily complete
marble wing
Like 2 pages
It involves creating a path of length p + 2 starting at a vertex with a p + 2 colouring, then showing that you end up with too many vertices in s
But it seems very verbose
(s <= r)
marble wing
Interesting
marble wing
Ok no worries, it's the final q in the assignment so quite hard
stray reef
hello
wise holly
hi Ann could you help me ? :((
stray reef
with what
wise holly
I was quite confused with this question
"How many one-to-one functions are there from X to Y"
X = {empty, {empty}, {1,2,3} } Y = {b, {z ,z}, b}
wise holly
there are 3 in X and 3 in Y
wise holly
so the answer is 0 function from X to Y, right?
slow socket
hey are u familiar with Big oh notation
stray reef
yes, there are no one-to-one functions from X to Y @wise holly
lunar wigeon
Can I get some help with number 2
stray reef
oh god several people in one channel again
wise holly
thank you so much @stray reef , I didn't mention duplicated elements.
sage island
@stray reef just saying you have msg deletion perms
stray reef
sure but that still leaves me with having to decide what to delete
slow socket
i have to find the smallest number k such that S(n) = Big o(n^k)
https://cdn.discordapp.com/attachments/238956921581862913/552356617828565012/90ceb358cd12a477da6688110a25913d.png
stray reef
well, what do you think that number is?
stray reef
to prove that 2 is the smallest value of that makes s(n) = O(n^k) true, you need to show two things:
- that k=2 works (i.e. makes the statement true)
- that no smaller value of k works (i.e. when k<2 it is false that s(n) is O(n^k))
lunar wigeon
is anyone able to help me out with this? im just having trouble putting it into words, i know what the symbols mean but
like there exists an x, for every y, y isnt x, d(x) or not p(x,y)
but she doesnt want us just strictly just translating the symbols
lunar wigeon
would it say "There's a penguin that is dangerous or not uglier than all other penguins"
slow socket
How can i do this
slow socket
all are "n's"
oak creek
not 100% sure but hoping i'm right lol
so you can split it into two separate groups:
5n^3 + s(n) and 3n^4 + t(n)
5n^3 + s(n) = 5n^3 + O(n^2) (\because s(n) = O(n^2))
3n^4 + t(n) = 3n^4 + O(n^3) (\because t(n) = O(n^3))
so the two groups together becomes:
(5n^3 + O(n^2)) + (3n^4 + O(n^3)) which can be simplified to 3n^4 + O(n^3) because you go with the larger complexities by convention as those influence the values the most
@lunar wigeon
a) there is a penguin(x) that is either dangerous or not uglier than all penguin(y)
b) If a penguin is dangerous, it is uglier than all others
also nice discord tag lmao
lunar wigeon
oh thx
oak creek
Hello! would it be possible to get a bit of help with this? I think i've got the overall problem down, i just don't understand the difference in choosing a directed over undirected graph in this particular use case
azure lichen
if the graph is undirected, that means whenever AB is good, so is BA
both orders are allowed, or neither
@oak creek
worthy thistle
How do I prove that c = a + (b - a) sm = b + (a - b)tn satisfies c ☰ amodm and c ☰ bmodm
I've managed to get to c-a= (b-a)sm is that close enough
viral stump
look at the definition of equality mod m
worthy thistle
I know c ☰ amodm is c-a = km
harsh warren
what should i do when i have to express the coefficient of a term x^3y^2 when the expression expanded from consists of an actual number e.g. (x+y+2)^8
chilly granite
if I have two graphs that are disconnected from each other and each graph has edge weights and a MST. But I augment two edges joining graph one and graph two, how would I prove that the MST of this new graph contains both edges (a and b) ??
I already kinda proved that when you join graph one and two with only one edge, that the MST of the new graph would contain this new edge because of the cut property
but I'm having trouble trying to prove how it'd work for two edges
crystal oar
it doesn't have to contain both edges
it depends on the weights
this is two triangles joined by two edges, but the weights force you to use at most one of the two edges connecting the triangles
chilly granite
i stated that if the edge weights of the two new edges were less than the max of MST edges of the disconnected graphs then both would be used
because of Kruskals algorithm
is that correct in me saying that?
@crystal oar
crystal oar
the two edges have to be smaller than the max weight of an edge in either of the MSTs of the disconnected graphs
like if you had G1 and G2 with MSTs T1 and T2, and then two new edges e and f, then e and f have to both be less than max w(E(T1)), or they have to both be less than max w(E(T2))
chilly granite
then in which case are both edges in the MST of the entire G (G1 union G2) ?
crystal oar
in both cases
if w(e) < max w(E(T1)) and w(f) < max w(E(T1)) then they'll both be in the big MST
if w(e) < max w(E(T2)) and w(f) < max w(E(T2)) they will again both be in the big MST
otherwise at most one of them will
chilly granite
ohh .. huh, is that not what i stated earlier? lol
crystal oar
it kind of sounded like you were asking which of the two
"in which case are both edges in the MST of the entire G" sounds like a question
chilly granite
ahh mb mb
crystal oar
but yeah you got it
chilly granite
so just to confirm, in your example you drew only one of the edges would be chosen in the MST because the edge weights are bigger, right?
crystal oar
yes
you need to take at least one of the edges of weight 2, because together they form a cut, but if you want to take both then there needs to be sufficient incentive
chilly granite
ok awesome! thank you so much!!
lofty maple
Anyone available to help me with this question?
crystal bough
The answer says that x⊕y = x - y doesn't have an identity
Isn't 0 the identity element for it?
azure lichen
x⊕0 = x, but 0⊕x ≠ x
pine orbit
azure lichen
honestly, draw a picture (draw a function as actually pairing elements between finite sets, not a graph). it'll help figuring out what could go wrong and why the first should work. Then make that intuituon into a proof
crystal bough
none of them are even closure
stray reef
au contraire
R is closed under multiplication
(c) is true
it might help if you write $R$ as ${1, i, -1, -i}$
vital dewBOT
Ann:
crystal bough
How to find number of isomorphic groups of given order?
stray reef
...wait
can you say that again
do you mean the number of non-isomorphic groups of a given order
i.e. how many there are up to iso
crystal bough
well the question says number of non non isomorphic groups of order 4
so I think non non isomorphic is isomorphic?
stray reef
are you sure the repeated "non" isn't a typo
stray reef
yes, most likely so
crystal bough
so it's number of non isomorphic groups then
and btw these groups should be abelian?
stray reef
not generally, but it is true that every group of order under 6 is abelian
blissful basalt
Hello All, does this make sense to anyone, the way it's layed out?
crystal bough
¯_(ツ)_/¯
There is an Abelian group of order n for all n belongs to positive integers
is this statement true?
When the operation is multiplication then there is no inverse
crystal bough
but they didn't mentioned addition
viral stump
they say that for each n there's an abelian group of order n
an example of such a group is Z mod n
under addition
crystal bough
but I still don't get why under addition
viral stump
it's an example
the group (Z mod n, +) has order n
there might be many other groups of order n
for some n
but this is an example that works for any n
crystal bough
so we'll say that the statement is true?
viral stump
yes
viral stump
which part
crystal bough
I mean statement never said to take only addition into account
the statement is false for multiplication so why only take addition operation
viral stump
what
the statement says, if you give n, you can make an abelian group of order n
that's all it says
in principle there are a lot of groups
crystal bough
I see
I think I get it now
so basically it means we can make an abelian group for any n belonging to Z+, right?
viral stump
yes
crystal bough
thanks!
tranquil roost
Hi, anyone able to assist with this question, what is meant by normalised form?
mint steeple
1010.01 base 2 ==> 10.25 base 10
is this the question? im just learning math in a different language...
For any number after the dot, the count is going down in negative integers
ashen magnet
hi guys, i mostly understand the statement :
Let h: ℘({a, b, c, d}) → ℘({a, b, c, d}) be the function defined by h(S) = S ∪ {a}.
but for h(S), does S mean, Subset, ergo the element? in this case the domain has 2^4 elements and the codomain 2^4 elements.
but if that's the case, why would h(S) be the union of each subset with element {a}. Wouldn't that just ensure that it can neither be
injective or surjective?
right? because there are elements in the codomain that don't have element {a}
opal crescent
so it's not surjective indeed
ashen magnet
it's not surjective but i gotta check if it's injective
injective would mean a unique element codomain for each element in the domain
opal crescent
is there only one element from the domain which maps to, say {a} ?
opal crescent
{a} also maps to {a}
ashen magnet
oh, cause {a} ∪ {a} ={a}?
ashen magnet
but it still can't be injective
opal crescent
that's exactly what we're showing with this example
ashen magnet
just like {c},{a} and {c} have the same output.
opal crescent
2 elements from the domain map to the same elem
ashen magnet
oh right i got you
opal crescent
yes also
ashen magnet
thanks a lot, it really helped clear things up^^
opal crescent
👌
ashen magnet
hey guys i'm back with a new question. Z X N -> Z and p(m, n) = m^n therefore
m ∈ Z and n ∈ N
would i be correct in saying this is surjective and not injective?
Not injective because p({1} x {1}) = 1
and p({1}x{2}) = 1
Surjective however... I know m^|n| has a codomain of of 0,inf when n is even and -inf, inf when odd so would the general range of the codomain be -inf,inf?
n can not be less than 0 so the codomain has to be the set all Z. since the domain is all Integers and the codomain is all integers, therefore it's surjective?
even 0 and the negative numbers in the codomain have a preimage even if it's just -m^n.
weary tiger
well it does look like it's surjective and pretty simple to prove it too
for any k in Z, consider p(k,1)
so it's surjective
weary tiger
lol
ashen magnet
thanks though ^_^ proves i need to go about attacking these sorts of questions 0/
sharp ravine
Hi, I am answering exercises from Book of Proof but there's no solution manual. Can anyone check my answer if it is correct?
English: There exists a real number a for which a+x=x for every real number x.
(Answer) Logic Symbol: ∃ a∈ℝ, ∀x∈ℝ, a + x = x
night fossil
sharp ravine
So it will become like this?
∃ a∈ℝ : a + x = x, ∀x∈ℝ
sour arrow
The use of : or | is important here, the "such that" means a is the subject, x is a free variable
sharp ravine
I have to switch back ∀x∈ℝ and a + x = x like this
∃ a∈ℝ, ∀x∈ℝ : a + x = x
sour arrow
No you had it right the first time imo
But I'm not sure the distinction is huge
lime mantle
sage island
crystal bough
If cyclic group G have exactly 3 subgroups : G, {e}, and subgroup of order 7 then what is order of G?
stray reef
what do you know about cyclic groups, and specifically, what order subgroups they have?
crystal bough
@stray reef cyclic groups have atleast one generating element
their subgroups are also cyclic
and if cyclic group is of order n and if d divides n then there is going to be an unique subgroup of order d
stray reef
well
let n be the order of your group
then you know that the only divisors of n are 1, 7 and n itself
crystal bough
yeah
right
so n can only be multiple of 7
but not divisible by any other primes
so power of 7
stray reef
you're getting closer, but there is actually only one such n that works
crystal bough
right so it can only be 49 cuz if it was cube of 7 then it'll be divisible by 49 as well
is this right?
azure lichen
yes
crystal bough
A={1,2,3} ang G={f | f is a bijective funtion on A→A} then I have to find whether G is group or semigroup or monoid under composition
weary tiger
what do you not understand?
crystal bough
It doesn't have identity?
weary tiger
ok stop
I don't understand your notation
how many elements are in your G?
can you list them?
crystal bough
not at same time?
weary tiger
what function is it?
crystal bough
x maps to y
crystal bough
but where every x have single image
weary tiger
you need to specify f(1), f(2) and f(3) to describe a function
crystal bough
the images
weary tiger
so either what you list is not functions
or I don't understand your notation
opal crescent
weary tiger
lol
crystal bough
@weary tiger so I thought this during test
all the elements of function g will form composition with all the elements in group g
so {(1,1),(2,2),(3,3)} would be identity
is this correct?
weary tiger
yes, this is the identity
crystal bough
thanks!
near bronze
36^6 - 10^5 ?
crystal bough
(5x10)x(36x35x34x33x32)
maybe
ruby hearth
Hello :D I just chose discrete math as one of my classes for my second year of electrical engineering. Could anyone provide me with good studying material on the subject? The professor seems to be taking the class really linear and doesn't answer question all that well which is a bummer...
weary tiger
Do you have a textbook?
ruby hearth
Not yet
But he seems to be focusing on combinations and generator functions at least now at the start
weary tiger
ruby hearth
ok if you turn %2520 to %20 it works
heady lantern
@ if u have ideas how to start the long division
heady lantern
<@&286206848099549185>
wanton sable
would anyone be able to explain the runtime for this?
:=(
I've looked at it for a while and can't figure out why its nlogn
my answer was O(n)
since it seemingly traverses through the entire data set
stray reef
letting $R(n)$ be its runtime, you have that $R(n) = l(n) + 2R(n/2)$, where $l(n)$ is $O(n)$
vital dewBOT
Ann:
wanton sable
yes, and the 2R(n/2) would be O(n) as well, right?
that would still be O(n) overall I think.. so I don't get where theyre getting the nlogn from
vital dewBOT
Ann:
stray reef
bit of abuse of notation
but still
there are approximately log(n) terms in this
and l is approximately linear so each one is approximately equal to l(n)
heady lantern
tfw no one answers ur question
narrow escarp
sad
weary tiger
Can a set have exactly 9 subsets?
no
since the number of subsets must always be a power of 2
craggy summit
I'm trying to find, or at least try and come up with an algorithm, to lower the complexity of a graph with its nodes layed out in a line. The algorithm can move the nodes around but where the vertices join can not change
I'm defining the complexity of a vertex as the distance a vertex has to travel or rather the number of nodes it has to leap across. The complexity of a graph is the sum of all the vertices. Also the graph can have two nodes with multiple vertices joining them sort of adding weight to the vertices
So a graph like this would have a complexity of 8
And rearranging the nodes it can be brought down to 5
I already have an algorithm that manages some simple cases but it trips up on this graph. It swaps neighboring nodes and recalculates the complexity, keeping the swap if it improves. But this graph requires a swap between two nodes that are a node apart. Every neighboring swap appears optimal
I only found the solution by brute forcing but that takes O(n!) time so I want to try and lower that xD
magic parcel
Would it be correct to say that the tuples that make up the equivalence relation of R ⊆ A × A given that A={a, b, c, d, e, f, g} and has the following equivalenceclasses {a, d, f}, {c}, {b, g} og {e} is {a,d,f}= ({a,d},{da},{df},{fd},{af},{fa}), {c}={c,c}, {b,g}= ({b,g},{g,b}) and {e}={e,e}?
Apologies if this is abit confusing to read, english is not my first language and its kinda hard to translate everything correctly
ripe cave
The equality signs in {a, d, f}=({a, d}, etc. are kinda notation abuse
And also you missed a couple pairs
||remember that every element is in relaion with itself||
craggy summit
I should note that I know more about computer science than set theory :p
magic parcel
Can someone give me an example of a part of a relation that is not reflexive? the way i've understood it is that all elements relate to itself, so it wouldent make sense for something to non-reflexive?
and i dont really understand the difference between anti-symmetric relations and asymmetric relations
analog sonnet
azure lichen
asymmetric just means that you can’t tell from xRy whether yRx is true or not
antisymmetric on the other hand, xRy and yRx can only co-occur if x=y
magic parcel
I see, thanks
azure lichen
(note that both can still be false)
craggy summit
I wonder if this could be solved by looking for community structures
weary tiger
can anyone help with a problem on sets?
(A ⊂ B ∧ B ⊂ C) → (A ∩ B) ⊂ C
im kinda lost on how to prove with with the method of contradiction
do you have to do contradiction only?
you can do it directly
quaint river
assume A intersection B is not a subset of C
that implies there exists a element, say x, in both a and b that does not exist in c
but then, B is a subset of c, which by definition means all elements of B have to be in C
weary tiger
thank you !!
weary tiger
(B – A) ∪ (C – A) = (B ∪ C) – A
can anyone explain how to prove that with the direct method
magic parcel
∃x(∃y((Men(y) ⊆ People) or (Women(y) ⊆ People))MarriedTo(x,y)) would this be a correct way to translate "Some couples are made up of the same gender" using the relations MarriedTo(x,y), men ⊆ people, women ⊆ people where MarriedTo is true if x is married to y?
sterile sable
not really sure about how rigorous is forming (A and B) or C from (A or C) and (B or C) here (and conversion of this) but should work
@magic parcel you need to translate second to first?
("statement" to logic)
if so than it's not really correct
because x can be anything
magic parcel
So i need to write it like this then? ∃x(∃y((Men(y) ⊆ People) or (Women(y) ⊆ People) or (Men(x) ⊆ People) or (Women(x) ⊆ People)MarriedTo(x,y))
sterile sable
still not
from this x can be man and y can be woman
and we have only 1 x and y
ill try to explain
"Some couples are made up of the same gender"
from this we can say that couple made up of the same gender exists
and that means at least that we have one x and one y that differs (idk why there isn't predicate about this) and they are couple
and this couple should be made up of the same gender
which means gender of x and y should be same
in our case male-male or female-female
so we can say
there is exists x and y that forms a couple and [(x is male and y is male) or (x is female and y is female)]
to be more rigorous
there is exists such x so there if exist such y that x and y are couple and [(x is male and y is male) or (x is female and y is female)]
and this forms ∃x(∃y(MarriedTo(x,y) and [(Men(x) ⊆ People) and (Men(y) ⊆ People) or (Women(x) ⊆ People) or (Women(x) ⊆ People)]))
(and has more priority than or)
stuck bough
Anyone here understand coding theory?
I am lost on how a code detects error patter and correct the error pattern
weary tiger
stuck bough
oh that's basically it
this is the question I have
but I am trying to understand how code correcting and detecting work
so that I can solve this
weary tiger
can somebody tell me what this means in plain english?
𝒇:𝑹 − {𝟎} → 𝑹 − {𝟐}
quaint river
function that maps from the real numbers excluding 0 to the real numbers excluding 2
weary tiger
ohh thats what i wrote
thanks
how come it wants to exlude 2
i get why it wants to exclude 0
okay ill try doing this
ya how come it wants to exlude 2? it looks like this 𝑓(𝑥) = (2x+1)/x
0 means it would be undefined
narrow escarp
putting f(x)=2 gives 1=0
weary tiger
doesn it do 5/2
weary tiger
ohh
let me try
oh i see now!!
how come that works its so interesting
is that just the nature of the function
so does that mean the R - {0} means the f(x) != 0 too
i mean R - {0}
narrow escarp
there are some values functions never attain. and there are some values that functions tend to
like f(x)->2 as x-> infty
so u never get 2 on your image. but the functions goes towards it
digital crag
I study odd maths
weary tiger
oh some of my friend's main fields are comptuer science but they learn until a certain point in math
and some are in engineering but they learn higher level of calculus up to a certain point or something
does : in discrete math mean such that? my professor uses this notation " | " for such that so i get confused
are they the same, : and |
viral stump
yes
copper ore
how does the second line work?
the associative and commutative line one
any help would be appreciated
stray reef
this is an intersection of 4 sets they're working with
intersection is associative and commutative, so it is okay to shuffle terms around like that
copper ore
but could you show me one step at a time. So what would it look like if i applied associative first? Could you please write it down maybe? @stray reef
stray reef
what, do you want me to write it down in the most formal way possible?
copper ore
like my professor did 2 steps in one line. so idk how he got there
could you do it one step at a time for me?
idk what you mean by formal but yeah like i just want more steps shown
stray reef
(A n C') n (B n C')
= A n (C' n (B n C'))
= A n ((C' n B) n C')
= A n ((B n C') n C')
= A n (B n (C' n C'))
= (A n B) n (C' n C')
used commutativity once to go from line 3 to line 4, all the other transitions are with associativity
fierce crest
hey can someone help me fill this out
i got this not sure if right or not
can anyone confirm?
<@&286206848099549185>
stray reef
the font is a bit too small to read comfortably
seems like the key step - rewriting (2k+1)(2q+1) as 4kq + 2k + 2q + 1 - is somehow missing from your list of blocks
or is the blank block meant to be "write your own"? @fierce crest
fierce crest
i think its just meant to be a filler space since you have to fill in all the blocks somehow
yeah idk why that isnt there
also yeah sorry i had to zoom out in order to get the whole picture otherwise some of the blocks wouldve been cut off
stray reef
no i mean are you able to type stuff into the block or what
stray reef
true, the blank block's purpose is not clear at all
do you only have one attempt to submit this
fierce crest
no i have 3
but i still have other questions after this to work through
i will work through those first before coming back to this
sterile sable
it should be
(or maybe "Therefore, y must be rational" can be put between "lalala quotient is rational" and "lalala contradiction cuz y is rational")
but i would stay w/o this
cold meteor
Show that for any three sets A, B, and C:
AU(B\C)=(AUB)(C\A)
I dont really get what it is asking
sterile sable
proof this
(show that AU(B\C) is subset of (AUB)(C\A) and that (AUB)(C\A) is subset of AU(B\C))
example
(where x is random "point" of corresponding set)
member? element?
cold meteor
should i change the "" to something like BnC^c?
sterile sable
BnC^c?
cold meteor
i dont know
sterile sable
just show that they're subsets of each other
take any member of the first set and show that this member is also member of second set
cold meteor
ok
chilly granite
I've got a partial math/coding question
How would I do a BFS search of a directional graph if I only had the edge list
for example this is the edge list of this graph
[(1,4),(2,1),(3,2),(1,3),(4,2)]
quaint river
Well you start at some node, so you just look at the neighbors(tuples with 1 as the first element) and then you visit the adjacent nodes of your next node in the queue?
I think 4 and 3 should be both 2nd but maybe its just notation because they're both adjacent nodes to 1
chilly granite
we choose in numerical order
quaint river
Ok so ¯_(ツ)_/¯
you start off with the minimal element or the root node
1 in this case
you iterate through your edge list and find tuples with 1 as the first element
and you then look at the 2nd element
add it to your queue
after you find all tuples with 1 as the first element you go back to your queue and look at the adjacent nodes of the first element in the queue
chilly granite
Yeah I'm doing that but just having trouble with the loop back to the root, when 2 goes to 1
Cuz I gotta do this using recursion 😄
quaint river
Oh okay
Hm
most of the time its like a tree so they don't direct back to themselves
But I guess one method would be to also remove all other edges with 1 in it
so you don't end up in a loop
another method is to just keep track of all the nodes you've visited
chilly granite
Hmmm okay so I'm doing it mostly right just implementing stuff wrong I guess, thanks
quaint river
recursive definition of m*n
modest zealot
i dont understand the subscript m part
Psubscriptm
wat tf does that mean
can i just leave that alone?
modest zealot
so i can leave it alone...?
viral stump
???????????????
viral stump
you want to give a recursive definition of the function Pm
viral stump
cuz that's just what it's called
modest zealot
functions dont normally have that
viral stump
call it f if you want
modest zealot
for matrices
does order matter?
AB = BA???
crap it does nvm
wait then how come it works for a problem like this (proof via induction)
slow socket
when im told "solve the following recurrence relations "
does that mean to find the explicit formula?
modest zealot
A(A^k) vs (A^k)A
sour arrow
For example, look at A^2. AA = AA, right? What if I told you I messed up the order of the A's? You wouldn't care
Same with A³
AAA = AAA = AAA = AAA = AAA = AAA
All 6 ways to arrange the A's, but they look the exact same no matter how I do it
AⁿA = AAⁿ
If you follow that trend
@modest zealot
modest zealot
is they're all the fkin same
gotcha
that makes a ton of sense
Prove that in a bit string, the string 01 occurs at most one more time than the string 10.
One more question
whats an example that shows 01 occurs at most one more time than string 10
azure lichen
well if the statement is true then any
I mean just try to construct a bitstring where 01 occurs as many times as possible and count the 10
or try to make 10 as rare as possible and see how you can't fit many 01 in it
stray reef
01010
azure lichen
or, you know, any other bitstring
weary tiger
lol
azure lichen
we can’t see the given statement…
dense thicket
Equal also work I think
fierce crest
i can see them all working thats the problem
but in one of the following problems concerning the same statement , it asks why i dont need to prove the statement for all cases
and im pretty sure i got this part right since none of the other answers make sense to me
prisma junco
crystal bough
What I did was that 1 have 3 choices, 4 have 2, 6 have 2 as well and 7 also have 2 choices so in total 9 ways
but is this way of solving it wrong?
crystal bough
Are 3-regular graph perfect matching?
uncut groveBOT
weary tiger
🍮
weary tiger
🍮
crystal bough
and make everyone else hungry
fierce crest
@dense thicket you think equal is the answer
i tried the second and fourth options but those didnt work
dense thicket
yes
blissful basalt
Evening All, I got this question and I am having a few difficulties understanding it.
Base Case:
let P(n) be the predicate Xn = n(n + 2)
if n = 1, then 1 ( 1 + 2 ) = 3. P(1) is False?
opal crescent
no?
blissful basalt
Is it saying that X1 = 3 is the 1st number in the sequence?
X1 = 3 based on n ( n + 2 )
x2 = 8 based on n (n + 2 )
:S
weary tiger
well you need to prove that
blissful basalt
Am I on the right track though ? If I take this assumption that is
Havent done any of this stuff so its very new
weary tiger
do you understand the main idea of induction
blissful basalt
to determine that all values are true based on a sequence of numbers?
weary tiger
close
the idea is, if you have some statement P(n) and want to prove it for positive integers, then what you can do is:
Show that P(1) or P(0) is true.
Show that if P(k) is true, then P(k+1) is true automatically.
These 2 conditions means that P(1) implies P(2) which implies P(3) which implies...
it's like falling dominoes
weary tiger
and then since k+1 is true, k+2 is true too
basically
so you have 2 pieces of information here
vital dewBOT
weary tiger
now P(1) is obviously true, since 3 = 1(1+2)
Assume the statement is true for some number m. Then for m+1
vital dewBOT
weary tiger
But since you assumed P(m) to be true, what might you substitute in place of x_m?
blissful basalt
the previous number in the sequence?
blissful basalt
something our lecturer didn't teach 😕
vital dewBOT
weary tiger
so what will you substitute
blissful basalt
the m
vital dewBOT
weary tiger
this is the correct one
so since we assumed x_m = m(m+2), we can put that in the place of x_m right
blissful basalt
dont get it 😅
weary tiger
so here's what we have
vital dewBOT
blissful basalt
Where are you getting 2(m + 1) ?
blissful basalt
so if P(1) = 3
P(2) would be X1 (which is 3) + 2x2 + 3
P(2) would be 10 ?
weary tiger
ye
blissful basalt
Now we need to prove if that equation for Xm + 1 is the same as n(n + 2) ?
vital dewBOT
blissful basalt
= m2 + 2m + 2m + 3
= m2 + 4m + 3 ?
Wait wrong equation no?
Factorise this one no?
weary tiger
i replaced x_m with m(m+2)
blissful basalt
Then it would be = m2 + 4m + 3 ? after factorising no?
weary tiger
$(m+1)( (m+1) + 2)$
vital dewBOT
blissful basalt
that was expanding Xn = n(n + 2) ?
weary tiger
yeah, but with X_(n+1) instead
blissful basalt
Xk + 1 = k + 1 ((k + 1) + 2 ) ?
weary tiger
yeah
slow socket
i think is reflexive cuz
m | m is true
weary tiger
$aRb \land bRa \implies a = b$
vital dewBOT
slow socket
xd
weary tiger
yes
slow socket
so
m | n and n | m
weary tiger
what does that imply
weary tiger
no
slow socket
ya thats wat i used to prove its not symmetric
weary tiger
rambo, what if m | n and n | m
feel free to use the inequality, that whenever a | b, then a ≤ |b|
opal crescent
in natural numbers
opal crescent
@me lol
slow socket
i did that to prove it wasnt symmetric
i cant do that?
this is wat i did to says is not symmetric
is this wrong?
weary tiger
for Base case am i allowed to use n=0 for mathematical induction?:
yes
@weary tiger my question says for all positive integers so im not allowed to use 0 anymore i think right?>
but when I prove n= 1, both sides don't equal...
huh
what's the q
my solution: https://i.imgur.com/xnUNs63.png
your mistake was that you considered only the term rather than the sum
so it should be (1 - 2) = expression
which is indeed -1
ohh, so it['s supposed to be 2^n - 1^n and they're not supposed to multiply ._.
okay i get it! it's supposed to be + [2^n - 1^n]
nonononon
you misunderstood me
we are not performing induction on the last term, we're doing it for the entire sum
oh
so for n= 1 the sum is this:
(-1)^0 * (2)^(0) + (-1)¹ (2)¹ = 1 - 2
oh i kind of see now
how come i need the (-1)^0 * (2)^(0) this part
because that's the first term
as you said, we could prove it for n=0 but the problem only requires it to be proved for positive values
oh i see
oh i kind of see
so f or example, if i used n= 2
then what do you think it would be
then it would be (-1)^0 *2^0 + (-1)^1*2*1 + (-1)*2*2^2 = [2^(n+2)(-1)^2 + 1 ] / 3
yeah
that is right
i had to do that because discord was taking my * and changing it to a stylish thingy
lol
okay thank you! i get it now!
np
how do i give you a cat treat
like this
there we go
weary tiger
@weary tiger meow meow solved the whole thing!! @weary tiger including (k+1) for the whole solution!
nice
yay
slow socket
is a converse relation the same as inverse relation?
weary tiger
discrete maths, sounds clean
analog sonnet
not to be confused with discreet maths
slow socket
i can write m | n (m divides n ) like this right?
n = mk
slow socket
alright, thanks
slow socket
can someone help me understand how to find equivalence classes
i only know how to find it if im given something like
S = {1,2,3}
R = {(1,2),(2,1),(1,1),(2,2)}
sour arrow
@slow socket
That's too broad, what do you mean "find"?
slow socket
like for the problem above
if it asks [1] (equivalence class of 1)
then its [1] = {1, 2} ?
sour arrow
Also note that 3 is equivalent to itself, and only itself
sour arrow
m and n are equivalent if they have the same square
1 and -1 have the same square, so -1~1 is a true statement
slow socket
so equivalence class basically means what something is equivalent to?
sour arrow
Equivalence classes are an alternative to "equal"
slow socket
so for that problem how would u do it
its confusing
so u said 1 and -1 have the same square, so -1~1 is a true statement
so this would be true for 2 and -2?
slow socket
so do u write this a specific way? or?
sour arrow
You could write the partitions
(0)(-1, 1)(-2, 2)(-3, 3)...
Or you could write R
But that's a mess lol
slow socket
but what would be the equivalence class that im answering for
sour arrow
It's better to describe why the equivalence class is the way it is
slow socket
like [m] or [n]?
slow socket
and 0?
slow socket
i understand it now that u explained it , but i feel if im giving like a different type of problem i wont know wat to do
just curious
wat if is
[n] = {-n, n } is this wrong
why is this the answer
[m] = {-m, m}
and not n
slow socket
ok i have this other example that is the same answer, but i dont get why
functions g and h, mapping Z into N.
g(n) = |n| and h(n) = 1 + (-1)^n
it says, describe the sets in the partition {g<-(k) : k is in the codomain of g} of Z. how many sets are there
its g arrow on top pointing to the left (k)
sour arrow
@slow socket
Still looking for it?
sour arrow
g says two numbers are equivalent if they have the same absolute value
|-1| = |1| therefore -1 ≡ 1
slow socket
wat
how do u see this "g says two numbers are equivalent if they have the same absolute value"
sour arrow
I take it away from the word "partition"
An equivalence relation is a partitioning of the domain
Although I don't know what "{g<-(k) : k is in the codomain of g} of Z" means
Maybe take a picture?
slow socket
the domain here is integers?
sour arrow
Yus
slow socket
this is hard
so u said u got it from the word partition
how did u partition the domain?
sour arrow
An equivalence relation is a partitioning of the domain.
That's a fancy way to say that it breaks the domain up into groups that share no elements. Kind of like cutting a cake, every element ends up in a slice and only one slice
slow socket
ok lets see
the other example is the same thing as a
just for h(n) now
so i knew that the codomain of h(n) is 0, 2
sour arrow
The codomain of h is ℕ
The range of h is {0, 2}
slow socket
prof said codomain of h = {0,2)
h<-(k) : k is in the codomain of h} of Z
thats wat b says
same as part a, but for h
idk
this is so confusing
so for part a u said if g(a) = g(b), a ≡ b
wat would make the equivalence for h
is it 1 + (-1)^m = 1 + (-1)^n ?
slow socket
i got it
crimson reef
yo anyone mind telling me the answer to c/d
I wanna check my answers
for c) I got {(2,1) , (3,2), (4,3)}
for d) I got {(1,3), (2,4)}
if yall could @ me that owuld be great
ty
slow socket
@crimson reef yes is correct
slow socket
ya both
cyan socket
Why do they go over? Shouldn't it be 13 instead of 14?
cyan socket
I don't understand
weary tiger
what do you not understand
i am asking you a separate question
what are the number of terms in this list:
0,1,2
cyan socket
Oh, 3
weary tiger
so what would be the number of terms in 0,1,2,...,13
weary tiger
:)
cyan socket
Thank you!
weary tiger
np
slow socket
given a matrix for a graph, how can find how many edges it has
azure lichen
well, what does the matrix encode?
slow socket
given an adjacency matrix, find how many edges it has
is not a directed graph
just a graph
azure lichen
yea I understood the question. I’m asking you
to tell me what’s in the matrix
I’m trying to guide you to the solution
quaint river
an adjacency matrix is just nodes that are connected to each other like [(a,b), (c,d), (b,d)] means a - > b -> d -> c
assuming your adjacency matrix repeats (a,b) and (b,a)
since it is not directed
take the number of elements in the matrix and simply divide by 2
quaint river
:|
azure lichen
that’s never useful
you want to get the asking person to arrive at the solution themselves
but, well, there you have it
quaint river
oof sorry
weary tiger
lol