discrete-math

[azure lichen]

because 1~2 and 2~1 but not 1~1

[fallen flicker]

oh

you have to have reflexive aswell ofc

[azure lichen]

the given relation is not reflexive

[fallen flicker]

yeah in that case it doesn't work

[echo lintel]

Sally goes into a candy store and selects 12 pieces of taffy. The candy store offers 75 varieties of taffy. How many ways are there for Sally to select her 12 pieces of taffy?

is it 75 choose 12

or is it12+75-1 choose 12-1

[hybrid patio]

Hey can anyone explain to me what (and how) the regular expression (\d+(,\d*\d)*) is expressing?

[vital dew]

Diemia:

[hybrid patio]

Oh man some symbols are gone

Two asterisks are gone

[stray reef]

enclose it in ` `

so that discord formats it as monospace

[lament shell]

if someone could help me out here.

[stray reef]

ok as is these are out of order, except step 1 which is in its right place

[lament shell]

this is late but 5 would be 2nd ? for the induction hypothesis ?

[stray reef]

no, this is not an inductive proof

[quiet kraken]

What is the coefficient of x^4y^3 when the expression (x+y+2)^9 is expanded?

can someone help me with this

[stray reef]

what have you tried so far?

[quiet kraken]

honestly, from what ive seen of these type of questions so far the the powers of the x and y add to give the power of the equation

so i dont really know what to do

sorry my explanation reads so bad

@stray reef is the answer 5040

[stray reef]

uhh lemme do that myself and see if my answer matches yours

[quiet kraken]

ok thank you

[stray reef]

yup

your answer matches mine

[quiet kraken]

thanks

[fallen flicker]

you chose 4 x among 9 factors, and then 3 y among the 5 left, and then multiply by 2^2=4

Or smth like that

[modest zealot]

does anyone know how to do this

[ivory badge]

I remember this exact question

have you tried $A^4$

[vital dew]

Darkrifts:

[ivory badge]

the adjacency matrix to the power of whatever gives the number of paths of length whatever, right?

[modest zealot]

yea the solution is like that

but idk how that works

mind explaining it?

[ivory badge]

So, if you have the adjacency matrix A, it gives whether or not an edge exists, yes?

[modest zealot]

yes

makes sense

[ivory badge]

when you multiply it with itself

$\begin{bmatrix} a & b \ c & d\end{bmatrix}^2 = \begin{bmatrix} bc+a & ab+bd \ ca+cd & bc+d\end{bmatrix}$ since the squares don't matter

[vital dew]

Darkrifts:

[modest zealot]

does it just turn out, that multiplying them gives you path length or osmething

[ivory badge]

p much

[modest zealot]

im sure theres a proof out there

but thanks

[ivory badge]

since the term only increases in the top left (for example) iff there exists a connection from a to a and bc, which would give you a path of length 2 i believe

[modest zealot]

hmmmm

so many things you can do with matrix multiplication holy shiet

[ivory badge]

of course it's not from a to a, it's like if it connects with itself and if they connect with each other, but whatever

adjacency matrix is weird to do without indices but I'm not typing out that full thing for time reasons

[modest zealot]

and im assuming when you multiply them together, you just count the number of values that are greater than 0 then

damn i ned another example, these slides only give one example

fk

[ivory badge]

The specific position of the value is important since the number is the number of paths of length n from point a to b

based on the indices, ofc

[modest zealot]

do u think u can give another example?

where teh graph is pretty fuked up

[ivory badge]

I can't write one down since lmao latex is inefficient

[modest zealot]

o

[ivory badge]

Just draw a graph yourself

and make the matrix

then see how it works

preferably a more asymmetrical one

[modest zealot]

yes yes

oh so undirected or directed

[ivory badge]

The adjacency one here relies on undirected, but i bet it'd work for directed even

[modest zealot]

oh

shoots

ok brb

wait question though

when do i give it a 0 and when do i give it a 1

damn

[ivory badge]

the directed one would be much less symmetrical, so not all numbers would be equal

1 when a c onnection exists

0 when no such connection exists

[modest zealot]

ok lets say i have from a to b

[ivory badge]

if there's more than one connection, who cares

[modest zealot]

would i put one in a,b or one in b,a

[ivory badge]

pick vertices and label them with the integers

[modest zealot]

im so confused as how a connection is established

[ivory badge]

number the vertices

I forget if it's rows or columns first, but it's probably listed on the slides

[modest zealot]

does it even matter?

[ivory badge]

Then if vertex 1 connects to vertex 2, $a_{1,2}$ should be 1

[vital dew]

Darkrifts:

[modest zealot]

nope its not on slides

[ivory badge]

shit

[modest zealot]

how would adjacenty work in directed graphs

hmmmmmMMM

[ivory badge]

Obviously no paths exist, but for directed, decide if it starts on rows or columns (which I don't remember)

and if it goes from a point to another point, put it on the first's row, the second's column (or the other way around, idk)

but the matrix will clearly be asymmetrical

[modest zealot]

uhhhh ok

o boi this is tough

[ivory badge]

GImme a sec

Alright so, assume that $a_{a,b}=1$ means there is a connection $a\to b$

[vital dew]

Darkrifts:

[modest zealot]

ok

[ivory badge]

so, using that, draw a more complex graph and fill the matrix

[modest zealot]

ok

lets do this

[ivory badge]

i just looked it up, the key detail is that it's asymmetric, so swapping rows and columns first will just be the transpose which won't change much

[modest zealot]

as long as ur consistent right

[ivory badge]

also yes the powers thing works with directed graphs too

and yes ofc

[modest zealot]

a to b means A(a,b) gets 1

ok

[ivory badge]

ye

I looked it up as well, the number should represent the number of connections as well

so if there are two edges, it should be 2

[modest zealot]

whoops wrong picture

done

[ivory badge]

ye

[modest zealot]

ok so lets say

want to find the amount of paths of length 3 that exist

wait no how about length 2

[ivory badge]

A^2

i think

[modest zealot]

from some vertex tos ome vertex

ok esoooo lets say from a to c

of length 2

multiply them, and then what am i searching for again?

[ivory badge]

if you did rows then columns, find the number in (a,c) of A^2

[modest zealot]

hmmmm ok

[ivory badge]

which should be 1, I believe

[modest zealot]

ok i foudn 1

o

o boi

o foudn 2 paths from a to d of length 2

whoa dude this works wonders

[ivory badge]

ye

Because they only add together if there exists a connection from the first to the second and from the second to the third etc in that chain

(or from one to itself, but they can just be considered possible distinct positions in the chain)

now all you have to do is prove it

[modest zealot]

can i pass

on proving it

[ivory badge]

n o

[modest zealot]

no

u

[ivory badge]

shit

[modest zealot]

thats aids

i dont even know where to begin

[ivory badge]

You could just treat them as conditions of whether or not connections exist

[modest zealot]

yeaaaaaa im gonna pass on that

[ivory badge]

same

[modest zealot]

im gonna yeet outta here

[final surge]

how could i represent this using symbology ?

because i get lost with the part 'if ab is even, then a is even and b is even'

maybe that part is an implication ?

[hexed rune]

Make some symbol E(x) which means x is even

Then E(ab) implies (E(a) and E(b))

[quaint river]

isnt that statement false

[hexed rune]

It is false

In the naturals

[final surge]

the example is this one, but i don't know how to get that negation

because if i negate this 'Then E(ab) implies (E(a) and E(b))' i don't get that

[hexed rune]

$\forall a \forall b( E(ab) \implies (E(a) \wedge E(b)))$

Take the negation

[vital dew]

Liquid:

[hexed rune]

$\neg \forall a \forall b( E(ab) \implies (E(a) \wedge E(b)))$

[vital dew]

Liquid:

[final surge]

~(E(ab)) v E(a) ^ E(b) ?

[hexed rune]

$\exists a \neg \forall b( E(ab) \implies (E(a) \wedge E(b)))$

[vital dew]

Liquid:

[hexed rune]

$\exists a \exists b\neg ( E(ab) \implies (E(a) \wedge E(b)))$

[vital dew]

Liquid:

[hexed rune]

And then just deal with the inside

[final surge]

but ~E(ab) wouldn't be 'ab is odd' ?

because the negation of an implication is ~E(ab) v (E(a) ^ E(b))

[hexed rune]

Basically this is because $\neg \forall a (s(a)) \equiv \exists a ( \neg s(a))$

[vital dew]

Liquid:

[hexed rune]

The negation of E(ab) would be ab is odd

But now let's deal with the inside

[final surge]

okay so it's or E(a) and E(b) so 'or a is even and b is even' ?

what

it shouldn't be 'E(a) and E(b) implies E(ab)' or something ?

[hexed rune]

So let's first write E(ab) implies ( E(a) and E(b)) as not E(ab) or ( E(a) and E(b))

So the negation of that is E(ab) and not ( E(a) and E(b))

Which is equivalent to E(ab) and (not E(a) or not E(b))

[final surge]

omg i'm sorry

now i get it hahah

i was thinking that the negation of an implication was ~P or Q and that's just an equivalence for the implication not for the negation of an implication

yes you're right then

and thanks for teaching me that it is possible to use the universal quantifier along with implications

i have another question, isn't it necessary to state that a and b belongs to some set ?

[hexed rune]

So the logical formulas are separate from the set (structure) you're working in

They are then interpreted by the structure

[bold cipher]

is that an algebraic equation

Lololol

[stray reef]

no, it is not

[weary tiger]

or maybe just ask in #❓how-to-get-help

that's better

[mossy palm]

in this entry http://jdh.hamkins.org/the-connect-infinity-game/ jdh analyzes connect-infinity

on the board w x n, n finite, there are strategy stealing arguments that both players cannot have winning strategies, and even though he doesnt describe a concrete drawing strategy, i've already constructed one

in the entry jdh uses the rule that you win if you form a connected w-sequence in a single row

now suppose we change the rule to, "you win if you form a connected w-sequence which may connect diagonally"

do the players have winning strategies? strategy stealing arguments still apply so the answer is no. but do they have concrete drawing strategies?

[hexed rune]

When you say w, do you mean $\omega$?

[vital dew]

Liquid:

[mossy palm]

yes

also, if it helps, the concrete strategy for the single row rule is here https://math.stackexchange.com/questions/3208923/the-connect-infinity-game

[hexed rune]

How can a diagonal $\omega$ sequence exist?

[vital dew]

Liquid:

[hexed rune]

Or maybe I'm missing something

[mossy palm]

like in the original game, say i plan on winning on the bottom row

you can block me anytime, just place a coin on the right of mine on an empty column

[hexed rune]

Sure

[mossy palm]

but say i connect mine all the way to yours, then afterwards ill just place a coin on top of yours

and that counts as diagonally connected

[hexed rune]

Oh I see

But that's a lot harder

[mossy palm]

harder to block yeah

[hexed rune]

It's possible that there's no obvious drawing strategy

[mossy palm]

it seems at first that both players have winning strategies (it seems they cannot block each other)

every position except for bottom and top have 3 "degrees of freedom"

in the MSE answer, you place isolated towers (assuming you are trying to draw). that way, you can force that they attempt to win on the top row

except in that case, if they try to fill the gaps i.e. build k-towers where k=max height, you can stop them the moment they build a k-1-tower

now with the modified rule, the top row has 2 degrees of freedom: they can connect through k-1 or k, so you can't block them both

[modest zealot]

is there a way to show that a certain degree sequence for a tree exists?

[final surge]

does this mean that a characterization is an another way in which i could identify some concept? instead of only using its definition?

[mossy palm]

yes

[stray reef]

yup

[dense thicket]

ye

[modest zealot]

for hasse diagram, you just get rid of reflexive + transitive right?

and change all directed to undirected

[granite raptor]

pre-requisites to learning discrete mathematics?

[azure lichen]

like, none

just gotta find material that starts easy

which should readily exist, it’s often an intro class of sorts

[granite raptor]

thanks. I've been researching on this subject

most answers are sporadic

any book recommendations for discrete math?

for beginner level

[sharp ravine]

I use Books of Proof (3rd edition) Richard Hammack and Epp's Discrete math. Books of proof pdf version is free

[shell jewel]

can someone remidn what does congruence mean when used with a mod?

i.e: a congruent 1 mod b

[safe sapphire]

Congruence is a relationship, so it must be "a is congruent to b mod n"

[shell jewel]

i know i wanted to know what it means but I found out now

it is b divide 1-a in this case

It is called congruent modulo and, i am not sure, I think it is not the same as saying a congruent to b

[safe sapphire]

I am pretty sure it's the same as saying "a is congruent to 1 mod b"

[shell jewel]

alright then

[shell jewel]

anyone familiar with RSA encryption

I have a question about a small proof involving it

[granite raptor]

@sharp ravine thanks

[shell jewel]

if $y_A = a^{x_A }modq$
how is $a^{x_Ax_B} mod q = y_A^{x_B} mod q$

[vital dew]

moar55:

[shell jewel]

but $y_A = a^{x_A} mod q$ where is the mod q part?

[vital dew]

moar55:

[weary tiger]

what

$$y_A \equiv a^{x_A} \pmod{q}$$
$$y_A^{x_B} \equiv \br{a^{x_A}}^{x_B} \equiv a^{x_A x_B} \pmod{q}$$

[shell jewel]

the equations i wrote where equality relations not congruence, or does it not matter in this context?

[weary tiger]

same meaning

\equiv is just a more rigorous way of writing it

[shell jewel]

alright, thanks

I actually found this property:
$(g^a mod p)^b mod p = g^{ab}mod p$

[vital dew]

moar55:

[rich trail]

anyone from Hunter college here that has taken discrete math

or am I truly alone in this world?

[weary tiger]

im not in college yet but i am taking discrete math rn

its easy but its so forgettable

its something u have to review over like every 2 weeks if u wanna master what you were taught

[obtuse minnow]

You're also delusional, @rich trail. There is no world. You have been in a coma for 5 years!

[weary tiger]

lol

[dense thicket]

lol

[proud yarrow]

@weary tiger do the exercise

[azure lichen]

a sequence of edges that bring you from A to A without repetitions. like, literally… a cycle

a circle in the edges

(when I say without repetitions I jist mean that you can’t just go back an forth over the same edge)

[prisma junco]

Need help with #8, im unsure of the syntax

[faint narwhal]

What are you unsure about?

[prisma junco]

how to write the answer..

my teacher said I could explain it considering i missed the classes we learned this

but still unsure if my explanations fits the format

so i wanted to know how id denote this properly

@faint narwhal

[faint narwhal]

Well what's your explanation

[prisma junco]

well based on my current understanding, whether correct or incorrect:

a string of 0, 11, 11 followed by some amount of 0s, 11 followed by some amount of 0s ands 1s, 1 followed by some amount of 0s followed by some amount of 1s, some amount of 0s followed by some amount of 1s, some amount of 0s followed by some amount of 1s and 0s

maybe I'm missing something but I'm assuming this isn't how I'm supposed to write this..

also, probably not understanding this properly

@faint narwhal sorry if you dont want pings

[faint narwhal]

Yeah this isn't correct. There's a very simple way of describing this

For example, would the string 00 be accepted?

[prisma junco]

im assuming yes cause the loop?

or is it that when u get to the final state it ends, so only 0 would be accepted

[ivory badge]

@prisma junco They likely want it as a regular expression

[prisma junco]

@ivory badge they said i could do it written out considering time constraints and that I missed this section.

[ivory badge]

Ah

[faint narwhal]

Yes it would be accepted

The only thing that matters is where you end up. So it's accepted it you end at s_0, rejected otherwise

[ivory badge]

$0^*(1(0)^*1)^0^$ certainly is recognized, but i'm not sure if that's the best way to write it

[vital dew]

Darkrifts:

[ivory badge]

(i'm horrible at formatting and optimizing)

Clearly it requires an even number of ones and that's really all you need to be accepted by this one, right?

@prisma junco Since they gave you the ||nword|| not-regular expression pass, you could say something about how it requires an even number of ones and the 0s do not affect acceptability

[faint narwhal]

Nice job just giving him the answer

[prisma junco]

lol

i got like 20 minutes to send a picture of this to my teacher for credit

eek

[ivory badge]

But uh, regular expressions like $0^(11)^$ mean the thing with the * is repeated any arbitrary number of times (including 0 times as a possible valid representation)

[vital dew]

Darkrifts:

[ivory badge]

so anything like 011, 0001111, etc would be members of that expression

[prisma junco]

but it could be 0101 tho

[ivory badge]

Nope, since the 0 comes before the 11

0 and 11 are valid, as is the empty string though

[prisma junco]

but the loop on s1

[ivory badge]

Oh, for that automata yes, but not for 0*(11)*

[prisma junco]

ohh

ok

[ivory badge]

sorry

[prisma junco]

what about #1 on this one

if uc an read it

am i allowed to add a a production or whatever its called

like A -> A0

or does that not work

[ivory badge]

I think they want you to use only those productions given

like S -> 1s0 -> 11s00 etc

which, btw, is sufficient to generate that string

But yeah, regular expressions are nice and there's a nice little thing you either have already seen or will see about how for every regular expression there's a FSA which accepts it

Also on your second step, you went from 1s0 to 11s0, you didn't add another 0

[prisma junco]

oh snap

thank u lol

last question is about the turing machine..

my issue si the blank between the 1 and 0 kinda confuses me

[ivory badge]

Sorry, had to c o n su me, but i have no idea what T is lmao

[prisma junco]

t the machine

its alright i turned in waht i had, probably failed but fudge i prolly got a c- in thec alss

[analog sonnet]

,rotate

[west crater]

what kind of stuff should you try to skip using a recurrence relation and go to finding an explicit function? For example I had a question like Find an expression for the number of bit strings of length n that contain the string 01 which i was supposed to just look at it with a explicit function but how would I know to do that instead of a r.r.?

[stray reef]

well in this case you can try to count the strings that don't contain 01

which is relatively straightforward as any such string is composed of a run of 1s followed by a run of 0s, either one potentially being of zero length

[peak crag]

I don't know what your course is but in general I'd say it's always better to find a "closed form" (i.e., not a recurrence relation)

and most recurrence relations that model basic combinatorial problems (it might take some time to recognize when less basic things like derangements or partitions are hiding) can be expressed in a closed form

[mossy palm]

@west crater in a bit string of length n, you have (n-1) choices of where the substring '01' may be. then each of the other (n-2) bits may be zero or one. so solution is (n-1)*2^(n-2)

[peak crag]

@mossy palm that overcounts - you're specially distinguishing the instance of the 01 that you place

Using your procedure I can choose "01" to be in the first spot, and then arbitrarily set the 3rd and 4th to be 0, 1 and everything else to be 0

I can also choose "01" to be in the third spot, and then arbitrarily set the 1st and 2nd to be 0, 1 and everything else to be 0

This is the same sequence but your procedure counts it twice (actually way more than twice)

[west crater]

i know the actual answer

but i just dont know when to give up on trying to friend a r.r.

[mossy palm]

@peak crag oh that is true. let's use ann's method instead. any string not containing '01' is determined by an initial segment of 1s, of which there are (n+1) many, so solution is 2^n-(n+1)

[peak crag]

@west crater why do you want to find a recurrence instead of a closed form?

[west crater]

well i just learned about recurrence relations and there was a very similar question basically the same thing but instead its a string of 00

So i tried to apply the same logic

butit doesnt work, I guess now i figured out why

[mossy palm]

so how did you solve the one with '00'?

maybe that method could work...

[peak crag]

I'd say you should basically always start by looking for a closed form unless you recognize some extremely obvious recursive structure or you realize the problem might have no closed form

Even if the problem is obviously recursive, a closed form is preferable to an open form

If it's no 00 then you have the recurrence f(n) = f(n-1) + f(n-2)

That problem seems to be a special case with no closed form... not a combinatorial closed form anyway, but you could write it in terms of the golden ratio

[obsidian heath]

A topographical ordering has no repeated vertex right?

A topographical ordering is a directed, acyclic graph (DAG)

An acyclic graph has no repeated vertex? Meaning a topgraphicial ordering also has no repeated vertex?

I'm basically trying to justify that a topographical graph, with the function f(v_i) = i is injective (one-to-one).

Where v_i is a vertex of index i.

My original argument was that there can't be two vertexes with the same index i. But this seems too simple.

[rare barn]

@stray reef @peak crag @mossy palm the way to address these in general is to build a DFA and then compute the number of possible paths in it by exponentiting the transition matrix

or by solving a linear recurrence

which is the same

[rare barn]

here's the knuth-morris-pratt DFA for 01:

[vital dew]

mniip:

[rare barn]

its transition matrix is

$$ \begin{pmatrix}1&1&0\0&1&1\0&0&2\end{pmatrix}$$

[vital dew]

mniip:

[rare barn]

the answer hence is

$$\begin{pmatrix}1 & 0 & 0\end{pmatrix}\begin{pmatrix}1&1&0\0&1&1\0&0&2\end{pmatrix}^n \begin{pmatrix}0\0\1\end{pmatrix}$$

now of course to get a closed form answer you could turn this matrix into jordan normal form et cetera

[vital dew]

mniip:

[rare barn]

the answer seems to be 2^n-n-1

[stray reef]

wow you really nuked this

[rare barn]

what

they asked for full generality

I gave them full generality

[peak crag]

I don't think he was looking for generality on specifically problems where there's a forbidden substring lol

[weary tiger]

so, im supposed to find out the solution to a set of congruences via generalized chinese remainder theorem
i know the answer already, i understand "normal" chinese remainder theorem, but i dont understand how come that solving both differs so much

given the set of x = 6 (mod 12); x = 2 (mod 14); x = 3 (mod 15); x = 9 (mod 21)

clearly they are not coprime, so must use the generalized version somehow

first i begin with the LCM of the modulos, that is 420

i know what im supposed to reach is x = 198

(thanks to the very few online calculators that solve generalized chinese remainder theorem, they r all for normal one only, however they still dont goddamn show steps)

there are supposed to be two more steps there, but i dont know what they are
all i figured out is that there is one set of integers (imma call it "D") for each of the congruences and altogether if all the D's are multiplied together, they also are equal to the LCM somehow

and through them i can calculate another set of integers (imma call it "C") for each congruence that each C is congruent to 1 (mod of its respective D)

i spent trying to figure this out for 3 days now

[peak crag]

@weary tiger this would probably be better in #elementary-number-theory

[west crater]

@mossy palm to solve it with 00 it basically looking at each case. So If it ended in a 10, 1 or 00, then adding all those combinations where it would have a 00 in it

[peak crag]

does anybody know of any relationship between bridges in a graph and edge coloring

[quiet kraken]

Consider distributing 28 identical balls into 8 distinct boxes numbered 1, . . . , 8

What is the number of such distributions in which for every i ∈ {1, 2, 3, 4}, box i receives
at least i balls?

is the answer C (25,7)?

[peak crag]

No, it's C (27, 7)

Give i balls to box i, now you have 28 - 1 - 2 - 3 - 4 = 28 - 10 = 20 balls left, so using stars & bars it's C (20 + 8 - 1, 8 - 1)

@quiet kraken

[quiet kraken]

@peak crag i think you made a mistake 28 - 10 = 18

but continuing from there it seems my answers the same

[peak crag]

oops lmao cant arithmetic

haha yes my bad

[spring helm]

Hey everyone! Can anyone help out with the image and preimage of floor and characteristic functions?

[azure lichen]

ask your questions

[stray reef]

^

[spring helm]

First, the floor function as f:R->R and f(x)=(floor)x

[azure lichen]

(there’s multiple definitions of “floor”)

[spring helm]

Can I send a picture?

[azure lichen]

(specifically, “round down” vs “round toward 0”)

of course you can

[spring helm]

Sending the two questions I've been working on

And here is my work for 4, not understanding what it's asking for preimage and would like my work on (a) and (b) to be checked

[azure lichen]

what’s happening in the graph there

did you just mess up and make the distance from 0 to 1 twice as long?

on the x axis

[spring helm]

Oh yeah, don't worry about scale

It's going 0,1,2,3 etc

[azure lichen]

aight. the circle at ½ is also confusing, might wanna go over that with some whiteout :P

[spring helm]

Will do, supposed to be the 0

[azure lichen]

well, there should be a solid circle at 0

anyway, the graph is correct if you defined floor as “round down”

[spring helm]

That's how it's to be defined

[azure lichen]

(the usual definition in math)

[spring helm]

And did I describe the image correctly?

[azure lichen]

(in programming it’s often round to 0)

you say “ranges”, that kinda implies that the image is an interval

like “ranges from 0 to 1” reads to me like the interval [0,1]

it’s imprecise

you should be more specific

I assume you got the right idea, but you didn’t describe it clearly

[spring helm]

So how would I make that image describe more precisely? The only values should be -1, 0, 1, 2

If I'm correct that is

[azure lichen]

you are

how about… {-1, 0, 1, 2}

they did say you could just do that

if you wanna describe it in words: “the integers from -1 to 2, inclusive”

or sth along those lines

[spring helm]

Will do, and can you describe how to find the preimage?

[azure lichen]

consider first just the preimage of 1

can you describe that?

that’s all the points which map to 1

[spring helm]

All the points which map to 1? So like -infinity to 1 or (0,1)

[azure lichen]

what makes you think -infinity to 1 could be plausible?

what’s you thought process

like… floor(-5) isn’t 1, is it

[spring helm]

No, it's not. I was thinking on a broad term of "all points mapping to 1", sorry.

So if the preimage of 0 is all the points mapping to 1 then it would be 1.01 to 1.99 correct?

[azure lichen]

the preimage of 0 is all the points mapping to 0

but I assume that was a typo

also, 1.0001 also maps to 1

as does, in fact, 1

and 1.9999 too

[spring helm]

True just meant shortened it for typing sake

[azure lichen]

no being imprecise

write it as an interval

[spring helm]

(1,2) then?

[azure lichen]

what about 1?

[spring helm]

Preimage of 1 so all the points mapping to 1?

[azure lichen]

yes

exactaly those, no more, no less

which, just to have the correct answer written somewhere, is [1,2)

now

what about the preimage of 1.5

[spring helm]

That would map to 1

[azure lichen]

preimage

not image

what gets mapped to 1.5?

[spring helm]

Nothing, in a floor function

[azure lichen]

indeed

so the preimage of {1.5} is the empty set

now. what’s the preimage of [1,2)

so that’s all the points which get mapped to something inside [1,2)

[spring helm]

Does that mean the preimage of [1,2) is [1,2)? As the only things being mapped to something inside that are those numbers

[azure lichen]

yes!

now I think you can answer the question

[spring helm]

So expanding that, it's asking from (0,4) so it would be {x|0 (less than or equal to) x <4}

In builder form

[azure lichen]

so [0, 4)
what’s floor(0)?

[spring helm]

Floor of 0 is 0

[azure lichen]

which is not in (0,4)

so 0 cannot be in the preimage of (0,4)

[spring helm]

My bad, 0 isn't include

So it'd be [1,4)

[azure lichen]

aye

that sounds right

[stray reef]

<= for ≤ if you can't type ≤

and likewise >= for ≥

[spring helm]

Did I write that down correctly?

[stray reef]

no

[0,4) isn't the same thing as { [0,4) }

[spring helm]

My bad, I wrote down [0,4) when I ment [1, 4)

But how would I write [1,4) as a set?

[azure lichen]

that doesn’t invalidate ann’s point however

you just did

[1,4) is shorthand notation for {x ∈ ℝ | 1 ≤ x < 4}

putting {} around it would make it a set of sets, which is not what you want

[spring helm]

Just about to type that out. Sorry for the mistake.

Onto the characteristic function, my teacher never showed an example of what the graph looks like.

[azure lichen]

try to work it out yourself

good practice

okay actually that example is gonna be a bit ugly

to draw

let’s take something easier like, say, the characteristic function of [0,1]

can you give me a definition of that function?

maybe write it down and see if you can graph it

[spring helm]

Give me just a second to check my teachers video resource and try to graph it

[azure lichen]

I encourage you to try and work it out yourself

look up the definition of a characteristic function if you don0t remember

[spring helm]

Wasn't going to copy the graph, just an outline of how to create it.

[azure lichen]

but try to figure out how the graph should look

it’s better to think on your own, I didn’t want to accuse you of cheating

but rather

I think it’s more valuable to think hard for a minute or two and figure it out on your own

than to find a “guide” / a too similar example

which will spoil the challenge

challenge is good

[spring helm]

I'm just not sure where to start, is the thing. I think the graph would be points at in a line?

[azure lichen]

start with definitions

what is the characteristic function of a set?

use [0,1] as a concrete example

[spring helm]

So, that means it's graphed to 0 when it's not when it's not 1 correct?

[azure lichen]

can you say that in more precise words

“f(x) is 0 when {blah} and 1 when {bluh}”

[spring helm]

F(x) is 0 when x-€A and 1 when x€A, where € is "an element of" and -€ is "not an element of"

Where A would be within the domain

[azure lichen]

good

so, if f is the characteristic function of [0,1], then f(x) = 1 when x∈[0,1], and otherwise it’s 0

draw that

[azure lichen]

that’s a bit imprecise… what about to the left? and what’s the vertical line?

[spring helm]

On the left it would drop down to 0 and the vertical line would be the function after it leaves [0,1] or would you draw that as two line?

Would this be more correct than the vertical drop?

[azure lichen]

yes, though as with the floor function before you should indicate what happens at the endpoints

[spring helm]

What would be the proper indication?

[azure lichen]

a solid circle where the value is, an empty where it isn’t

[spring helm]

So this would be the correct graph of the characteristic function?

[azure lichen]

yes

now, the exercise has the characteristic function of the naturals

which is a bit uglier, but perfectly drawable

[spring helm]

If it's only for the naturals, how is the function from -2 <= x <= 2

As Z+ should be from just 0 to infinity right?

[azure lichen]

if you wanna do it rigorously, then the function is from [-2, 2] to {0,1}, taking on 1 at the intersection of ℤ⁺ and [-2,2]

that is, at the points {x ∈ [-2,2] | x ∈ ℤ⁺}

actually, no, nevermind

you just misread the excercise

the function is from ℝ

you’re just only supposed to draw that part of it

[spring helm]

Sorry for being a little lost, so I'm only to be drawing the positive integers?

[azure lichen]

you’re gonna draw the function f(x), which itself is defined on the entirety of ℝ (and takes on values either 0 or 1… mostly 0), but you only have to draw a snippet of it, namely for x between -2 and 2

[spring helm]

So like this?

[azure lichen]

that’s the characteristic function of [-2,2]

that’s not f

f is the characteristic function of ℤ⁺ = {1,2,3…}

[spring helm]

So cut off the everything from 1 back?

As Z is those positive integers?

[azure lichen]

the numbers between 1 and 2 aren’t integers

f(1.5) = 0

[spring helm]

So the graph would just be individual points?

[azure lichen]

you should draw a function which goes
f(-2) = 0
f(-1.99) = 0
…
f(0.99) = 0
f(1) = 1
f(1.001) = 0
…
f(2) = 1

yes, it is a function which is mostly 0

[azure lichen]

yea

that’s what they asked for

[spring helm]

So that would be the correct graph, onto the imaging of a characteristic function

[azure lichen]

yea, I‘ll leave you to that now, though

and just remember the two magic steps to solving math problems:

1. read very carefully
2. recall definitions

[ivory badge]

don't forget 3
3) expand everything (off to the side, of course) that isn't "fundamental" with respect to the problem so that you can more visually see what you have available

[spring helm]

Will do, if imaging is just the values then it should be the set {0,1} as those are the only possible values

[spring helm]

@azure lichen was that right? The image being that while the preimage is again {0,1}.

[azure lichen]

no, preimage is wrong

(not in the mood for more math tutoring, sorry)

[spring helm]

alrighty

[spring helm]

(Whenever you feel like answering) (or anyone else) was the image right?

And Im not sure what's wrong with the preimage,

[ivory badge]

@spring helm what

[spring helm]

Trying to find the image and preimage of these problems

Or this problem, #5

Here's the graph,

[ivory badge]

@spring helm so b asks what the image of the function is for f((-1,3))

[spring helm]

Yes,

Pretty sure the image is just {0,1} as those are the only possible solutions

I'm really just stumped on the preimage

[ivory badge]

yep

ofc the image is {0,1}

So, the preimage
if i remember correctly, it's f^-1({0,1})

wait sorry misread

[spring helm]

You're partially right, it's just asking for a different set

[ivory badge]

So, the preimage question wants to know
$f^{-1}({x,,| 0< x < 4})$

[vital dew]

Darkrifts:

[ivory badge]

so, what would be the preimage of 3?

[spring helm]

Well it has to be 1 or 2 to be plotted

would there not be a preimage for 3 as I can't get 3?

[ivory badge]

Yeah, 3 isn't in the codomain

[spring helm]

and the only thing that is, within those conditions, would be 1

[ivory badge]

Yes, I suppose so if you map all things without a preimage to the empty set

So all you need now is the preimage of 1

[spring helm]

only 1? that looked a lot more difficult on paper 😅 i guess i just thought about it too hard

thank you!

[ivory badge]

That is of course unless your course adopts some convention like the preimage of an object not in the range of the function being undefined

I'd think you should map to empty tho

[spring helm]

Map to empty?

[ivory badge]

Like f^-1(2) would be the empty set because there are no objects which map to 2 through f

You have to find the preimage of 1 btw

the answer isn't 1

you need the set of objects such that f(x) = 1

[spring helm]

oh yeah! so it would be {1,2,∅}

as the preimage of 1 can be 1 or 2

and then the empty set

[ivory badge]

You don't need the empty set

[spring helm]

so just {1,2} would be proper notation?

[ivory badge]

No, it's not just 1, 2

since the function is over the full real number line

you just only drew a section with 1, 2 on it for a

[spring helm]

so.... Z+?

all positive integers?

[ivory badge]

Yeah, i'd believe so

[spring helm]

but what about the problem saying 𝑓
−1
({𝑥|0 < 𝑥 < 4})?

[ivory badge]

also explain it ofc

That is the problem

[spring helm]

is that just limiting the answer to 1,2,3

and the only answer is 1?

and every positive integer can be one

[ivory badge]

Yeah, but you only have a non-empty preimage of 1, so your preimage consists of all naturals

[spring helm]

@ivory badge explained good? And thank you so much!

[ivory badge]

Don't forget about how the preimage of all other x =/= 1 in that set must necessarily be the empty set

You don't need {Z}

you could just say Z+

I mean you don't need the brackets

The reason Z+ is a subset of the preimage is because 1 is inside the set you're finding f-1 of

the reason R isn't the preimage is because 0 isn't in there as well

[spring helm]

Ill include the bit about R also!

thank you so much!

[ivory badge]

I'll hope you don't misinterpret what I say

ye, but the { } around Z is uneccessary

[spring helm]

got it

[ivory badge]

the preimage of this doesn't return a set holding Z

it returns z+

[spring helm]

Thank you so much Darkrifts!

[tulip sable]

I know that an edge-weighted graph can be defined as a 3-tuple G=(V,E,w), where w is the weight function. Let's say I also want to add a weight to the vertices, how would I model that formally?

[azure lichen]

a weighting of the edges is really just a function E→ℝ (or whereever else your weights live), so a weighting of the vertices would just be a function V→ℝ

the rest is just notation

[weary tiger]

Can anyone tell me if this proof is correct?

\textbf{Show that the additive inverse, or negative, of an even number is an even number using a direct proof.}

We assume that $a$ is an even number. By the definition of an even number, it follows that there is an integer $k$ such that $a = 2k$. We want to proof that $a + b = 0$, where $b$ is the additive inverse, or negative of $a$. Because $a$ is $2k$ away from zero in the line of real numbers, we need to add the number which is $2k$ away from $0$ in the opposite direction in the line of real numbers. For this reason, $b =  -a$. We know that $a = 2k$, so we have $b = -2k = 2\left( - k\right)$. By the definition of an even number, it follows that  $b = 2\left( - k\right)$ is an even number.

[vital dew]

╱∞╲ UncaughtException ╱∞╲:

[stray reef]

unnecessarily verbose??? you can go from a + b = 0 to a = -b directly, just by using the definition of additive inverse. cut that "line of real numbers" talk, it really doesn't belong

[weary tiger]

We assume that $a$ is an even number. By the definition of an even number, $a = 2k$ for some integer $k$. We want to proof that the additive inverse of $a$, $b$, is an even number. By the definition of the additive inverse, $a + b =0$. Solving for $b$, we get $b =  - a$. Substituting $a = 2k$ into $b =  - a$, gives $b =  - 2k =  2( - k)$. By the definition of an even number, it follows that $b$ is an even number.

[vital dew]

╱∞╲ UncaughtException ╱∞╲:

[weary tiger]

How about now? Is it better? @stray reef

[stray reef]

yes

not ideal but acceptable

[weary tiger]

Could you give me a recommendation to make my proofs more "acceptable"?

[timber plaza]

Here is what I would call an "ideal" proof:

Let (a) be an even number. That is, (a = 2k) for some integer (k). Hence, the additive inverse of (2k) is (-2k = 2 \times (-k)). This is also an even number, as (-k) is also an integer.

[vital dew]

Tony Wang:

[vagrant niche]

So here is the problem:
Find the number of different decompositions of the number "n" using only numbers 4, 6, and 10.
For example for n = 18 there are only three ways (the order doesn't matter):
4+4+4+6
4+4+10
6+6+6
The following generating function was deduced:
1 / ((1 - z^4) * (1 - z^6) * (1 - z^10))
So my question is. How can I deduce a recurrent relation using this generating function?

[stray reef]

you can use the generating function to obtain the explicit formula

the recurrence relation can be obtained without it

[vagrant niche]

without generating function?

[stray reef]

yes

let P(n) be the number of {4,6,10}-decompositions of n (which is definitely not a term i just made up on the spot)

P(n) = P(n-4) + P(n-6) + P(n-10) - P(n-10) - P(n-14) - P(n-16) + P(n-20)

[vagrant niche]

are you using the rules that are applied to the operations with sets?

like Inclusion–exclusion principle

[stray reef]

well essentially i'm relating the set of {4,6,10}-decompositions of n to those of n-4, n-6 and so on

incl-excl is exactly what i'm using

[vagrant niche]

I was going to try this method actually. But is it possible to deduce the same formula using this particular generating function? Im currently watching the lecture on this subject, and the lecturer said that it can be done quite easily. But I have no idea how

[stray reef]

eh?

you usually go the other way around

from recurrence to GF

[vagrant niche]

yes, I know. This is why I am asking

I usually deduced GF from a recurrence, and than deduced the explicit formula from GF

btw, it looks kinda hard to deduce the explicit formula in this particular case

or maybe I don't know something

but still, thanks for the help

btw perhaps I misunderstood what the lecturer said. He said that you can easily deduce this recurrent relation if you know this generating function

[faint narwhal]

P(n) = p(n-4) +p(n-6) + p(n-10) I think?

No this isn't true you double count a lot

[vagrant niche]

yes

i know the answer

it is given in the lecture

i just thought, that there is a way to deduce it USING this generating function somehow. But it seems to me I was wrong

this is the answer from the lecture

so it is just the formula for the union of three sets

|A V B V C| = |A| + |B| + |C| - |AB| - |AC| - |BC| + |AB*C|

well, i messed it up a bit, but I think the idea is clear

[faint narwhal]

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/LRGF.html#section3

This link has some tables about general cases I think

[vagrant niche]

wow, thanks, I was actually looking for something like this

[dapper hound]

can i jump to discrete math if i only have a math background up to algebra II?

[lucid pivot]

Like highschool algebra? @dapper hound

You should probably know calculus 2 before learning discrete mathematics

[fresh fog]

Hi all, in my 2nd week of discrete math and am trying to discern which type of proof to use against the following statement.
"Let x and y be real numbers. Prove that if x <= y + e for every positive real number e, then x <= y".

We're going over indirect proofs now (existence, contrapositive, case, contradiction). I believe since it's impossible to check for every number, I'm not going to use contradiction or contrapositive. If I use case, then does that mean I only need to provide a few examples, which would conclude the statement is true?

[faint narwhal]

Do you think that your last sentence is true?

Why can't you use contradiction or contrapositive?

[fresh fog]

What I meant in my last sentence was, if I was using cases then if p1 or p2 or... pn were true, I can conclude the statement was true as well. I didn't think I could use contradiction or contrapositive in this question, but let me go back and see if i could plug that in

[faint narwhal]

Explain what you mean by you'd have to check every number?

[fresh fog]

"Prove that if x <= y + e for every positive real number e".. I meant that I need to find a way to prove* the statement is true without proving it's true for every positive real number 'e'

[faint narwhal]

But you're not proving this statement is true

You're trying to prove that x<= y, and you can use the fact that x <= y + e for every positive real number e

[fresh fog]

Good point

[summer dragon]

I understand reflexivoty symmetry and transivity with graphs and zeroone matrices. But when functions are added i lose it. Can someone please explain the concept to do these exercises?

[stray reef]

,rotate 90

[harsh lark]

@summer dragon do you understand what the reflexivity, symmetry, and transitivity mean with respect to these?

for the first one ANY two functions f: Z -> Z and g : Z-> Z are related if f(1) = g(1)

now what you need to show for it to be an equivalence relation is that

Ref) (f,f) is in the relation
Sym) If (f,g) is in the relation, then so is (g,f)
Tran) If (f,g),(g,h) is in the relation, then so is (f,h)

for the first, this is pretty easy because it is just based on things being equal.

[summer dragon]

So is this a right way to prove it?
Are there better ways?

[harsh lark]

sorta

i didnt check the details but yeah

you should use more words

also for the ones that arent equivalence relations, try to think of a counterexample for the propertie(s) that dont hold

like 1, 2 or 3 specific functions where either ref, sym, or transitivity doesnt hold

[spring helm]

Hello! I was wondering if anyone was on that could help with propositional logic formulas and their truth tables

[smoky needle]

[spring helm]

(p|p)|(q|q) where | is the NAND operator is the table im trying to create

I can create the truth table for (p|p) and (q|q), im just not sure about the complete thing

[smoky needle]

take those two results and AND them

then take the compliment

[spring helm]

Ok, give me a bit to work on that table

[spring helm]

@smoky needle are these tables correct?

[smoky needle]

,w (p NAND p) NAND (q NAND q)

[vital dew]

Display results online and refine query

Requested by MiracleMan#3499

[smoky needle]

yes

[spring helm]

Sweet thank you! Are you going to be around for a bit in case I have any other questions?

[smoky needle]

just ask

plenty of people here that know what they're doing

[spring helm]

"state the negation of the following sentence (Do not state “It is not the case that Jan is young and happy.”) Jan is young and happy."

Is the better answer to this "Jan is not young and happy"

or

"Jan is young, but not happy"?

[ivory badge]

they're both wrong

Do you know how to do symbolic stuff?

[spring helm]

yes, it does want the response in an english statement though

[ivory badge]

$\neg(Y \land H)$ becomes $\neg Y \lor \neg H$

[vital dew]

Darkrifts:

[ivory badge]

if i remember correctly

[spring helm]

So wouldnt that be "Jan is not young and not happy"?

[ivory badge]

Not young OR not happy

the negation only requires one to be false

[spring helm]

Oh I understand that, thank you. I was applying the neg as if it only stated one thing

[ivory badge]

yeah can't ignore that and

[spring helm]

perfectly find to change it to "Jan is not young or unhappy" right?

[ivory badge]

yeah

or maybe Jan is either not young or unhappy or some other such translatipon

it's not too important

[spring helm]

thanks again!

[spring helm]

“I stay indoors whenever the weather is bad.”

Would the negation be, "I stay indoors whenever the weather is good"

[ivory badge]

Bad $\to$ indoors
i forget exactly how the $\to$ thing is negated, but you'd just have to say you go outside when the weather is bad if I'm reading it right

[vital dew]

Darkrifts:

[proven shard]

Original: If the weather is bad I stay indoors.
Contrapositive: If I go outdoors then the weather is good.

[spring helm]

"I go outside whenever the weather is good"

thats what ive landed on

[ivory badge]

I forget how to negate ->, but all you'd have to do is state there's a time when you are outdoors and the weather is bad

[twilit wadi]

can anyone tell how he got this answer

[spring helm]

My answer?

[twilit wadi]

not yours

can anyone tell how to get RoS

[ivory badge]

R o S is function composition, so since it's a matrix you end up applying the outer R matrix to the inner S matrix

same

[spring helm]

anyone else here that can?

[ivory badge]

Any context on that r

?

[spring helm]

Nope, all it says is use logical equivalences to prove its a tautology or a contradiction

state the laws you used

[ivory badge]

$P \to Q$ is false iff P is false and Q is true, right?

[vital dew]

Darkrifts:

[ivory badge]

$((p\land r) \land (p \to q))\to q$

[vital dew]

Darkrifts:

[ivory badge]

i mixed them up lmao it's P true and Q false but whatever

[spring helm]

thats the correct formula and the implication law is (p -> q) <=> (¬p v q

[ivory badge]

I still don't really get why r is there

[scarlet otter]

yo

I can elp

[vital dew]

SolitaryWolf:

SolitaryWolf:

[scarlet otter]

@spring helm I think you can continue

laws you'll need

• de Morgan
• double negation

andd a few more whose names I have forgotten!

[spring helm]

me and another student steve have worked and talked about it, id like if you could check the work though?

[scarlet otter]

Sure

[spring helm]

itll be a few minutes for a picture

[scarlet otter]

I'll wait

Can you give me a missed call once you send?

[spring helm]

@scarlet otter

[scarlet otter]

Ah hek I'm sorry

@spring helm I'm here

[twilit wadi]

can anyone tell how to get RoS

[faint narwhal]

Which part are you confused about?

[twilit wadi]

one after = [ ]

[faint narwhal]

The ordered pairs are just describing which entries of M_{RoS} have ones in them

By (row, column)

[twilit wadi]

ok

[indigo cedar]

Can someone explain what a partition is, intuitively? I’m looking at the definition and it’s quite verbose and hard to grasp for me

WAIT

Is it literally just like if you have a bag of marbles, and then you separated them into three different bags?

The three bags together would be the partition of the original bag?

Yo, I get it now

Thanks, guys 😂

And Wikipedia

Hey, here’s a question. If you have a set of size n, how many different partitions does it have?

[azure lichen]

partitions into nonempty sets, I assume, otherwise infinitely many (since you can add as many empty sets into it as you want)

https://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function

“no closed form is known”

so basically there’s no nice formula

but it can still be computed exactly using recurrance relations (ie recursive algorithms)

[indigo cedar]

Oh wowsers

That’s cool

Ye, I believe the text I was reading said a partition cannot contain the empty set

I think partitions of integers might be a separate thing tho.

[azure lichen]

partitions of integers are just all the ways you can partition an n-element set into non-empty subsets

[indigo cedar]

Cuz I just read that the total number of partitions of n element set is a “Bell number”

[azure lichen]

but spelled out as a sum

[indigo cedar]

Yeah

I was thinking about just sets in general

[azure lichen]

oh wait

right

I see the difference

in a set there’s of course distinct elements :P

[indigo cedar]

Yup yup

[azure lichen]

{1} {2,3} is different from {1,2} {3}

sorry for the confusion

[indigo cedar]

There’s a cool looking recursive formula on Wikipedia, now that I look

No worries

[azure lichen]

the triangle thingie?

[indigo cedar]

Yeah

Wow

This is actually an astoundingly complex topic

Just this one question

This is why I love discrete math

[azure lichen]

turns out easy questions can have hard answers

[indigo cedar]

Very true

[weary tiger]

'

A pretty nice explanation from wikipedia :)

[proven shard]

I like that

[oak creek]

hm, it's very nice and clean

[wintry hawk]

http://prntscr.com/nvnwu8 can anyone help me out

[ivory badge]

R as in real numbers?

[wintry hawk]

i am assuming so

[ivory badge]

I'd also assume so given the thing on the right

[wintry hawk]

i have no idea what r-{1} means

[ivory badge]

Set minus

R except without 1

They probably want you to see that it creates a surjection even without 1, with a similar argument for R-{2}

[wintry hawk]

all i know is that the function has to be one-one and onto

[ivory badge]

Which is injective and surjective (respectively) btw

You just have to show that the f(x) they give (and possibly one for x-2 if you want to do a middle man with the normal reals R) is surjective and injective

[wintry hawk]

so whts the point of r-{1} and r-{2}

[ivory badge]

To show that removing one element from the set doesn't change the cardinality (especially should be obvious when you compare it to another set which removes only 1 element as well)

Also you really probably should know what set minus stuff is

[wintry hawk]

would e^x be considered one to one but not onto

[wintry hawk]

whts an example of a function that is onto but not one to one on R

[faint narwhal]

Can you prove your first statement?

[ivory badge]

@wintry hawk as for surjective but not injective, consider the function
$$f(x)=\begin{cases} x+1 & x<1 \ x & x \geq 1\end{cases}$$

[vital dew]

Darkrifts:

[wintry hawk]

wait why would tht not be injective

@faint narwhal because e^x = -1 doesnt exist

[ivory badge]

He also meant the injective part but uh

It's not injective because consider f(0) and f(1)

which are equal

[wintry hawk]

ah i see

[faint narwhal]

You also have to prove that the function is injective

[wintry hawk]

e^x1 = e^x2

[faint narwhal]

What you said only shows it's not onto

[wintry hawk]

x1 = x2

[ivory badge]

He also meant the injective part but uh

smh

[faint narwhal]

That's not an argument at all lmao

[glossy adder]

"proof every function is injective:
f(x1)=f(x2)
x1=x2"

[wintry hawk]

f(x1) = f(x2) = e^x1 = e^2x where x1 = x2

[glossy adder]

[wintry hawk]

e^x2*

[ivory badge]

Well, that doesn't exclude the possibility that f(x1)=f(x2) but x1=/=x2

[prime steeple]

https://youtu.be/VW0RAonW8Aw

[hollow stirrup]

Can anybody help provide me the formula for working this one out?

Only need for b) rather x

[stray reef]

have you done (a) already

[hollow stirrup]

Yes sir,

Mam*

[stray reef]

okay so let A = that

think about what A^2 might represent.

it's not the answer to your problem but if you give it some thought it should push you in the right direction

[hollow stirrup]

Ooof

I'm trying here haha

A squared you say.

[stray reef]

hint: the (i,j)'th entry of A is equal to the number of paths of length 1 from i to j

[hollow stirrup]

Hmm

Are you able to walk me through it? This isn't course work, this is last years exam. I am just doing extra study for my exam on Wednesday haha

I'm a bit lost with this one right now, sorry.

[stray reef]

alright so i hope you're familiar with how matrix multiplication works

[hollow stirrup]

Yep!

Can voice chat if that works any better?

[stray reef]

can't voice chat rn i'm afraid

[hollow stirrup]

No problem!

[stray reef]

so suppose we have a graph with adjacency matrix $A$. my claim is that, for any positive integer $n$, the number of paths of length $n$ from vertex $i$ to vertex $j$ is exactly $(A^n)_{ij}$

[vital dew]

Ann:

[stray reef]

i'm going to prove this by induction

the case n=1 is true definitionally, as an edge is the same as a path of length 1

suppose now that we know the claim is true for $n-1$ and want to prove it for $n$

[vital dew]

Ann:

[stray reef]

do you follow so far

[hollow stirrup]

So far so good!

[stray reef]

so let's count the paths of length n from i to j

they can be classified by their penultimate vertex (i.e. which vertex the path goes through right before ending at j)

so uhh... let's say the graph has $N$ vertices. bc i'm going to need that now

[vital dew]

Ann:

[stray reef]

accordingly, $A$ is an $N \times N$ matrix

[vital dew]

Ann:

[stray reef]

so the number of paths of length $n$ from $i$ to $j$ whose penultimate vertex is $k$ is $(A^{n-1}){ik} \cdot A{kj}$

[vital dew]

Ann:

[stray reef]

basically, if A_kj = 0, then there is no edge from k to j, and we can't get from k to j in one step

but if A_kj = 1, then there is an edge from k to j, and we can get from k to j. and this gives us as many total paths of length n as there were paths of length n-1 from i to k

does that make sense

[hollow stirrup]

Just going to re-read now slowly and try compile it in my brain!

I'm with you all the way until that final step

It's right at the end that gets me

[tacit garden]

How do I negate the statement "The processor is fast or else the printer is slow." ?

[glossy adder]

something like "there exists a time in the set of times during which the processor is not fast and the printer is not slow"

[pale epoch]

@tacit garden the actual negation is "Either the processor is not fast and the printer is not slow or the printer is slow and the processor is fast"

assuming your "or else" is an exclusive or

[tacit garden]

Thank you. I thought it would be something like that but wasn't sure if the phrasing was correct.

[indigo cedar]

I’m having trouble understanding what an equivalence class is by reading the definition

Can someone restate or explain it in a simpler way?

[oak creek]

hm, given an entire set, you can break it into subsets based off of some arbitrary measure of equivalence

that's a rather poor explanation

lets say you have the set of integers

you can use the modulus function as the defining feature of equivalence

for example, all integers x for which x mod 3 = 1 are in an equivalence class

and so hold true for x mod 3 = 2 and x mod 3 = 0

or perhaps

for the set of all triangles, you can use similarity as what you state to be equivalent

so each group of similar triangles would be an equivalence class

[indigo cedar]

Ok

I just noticed something about the definition of an equivalence relation that I hadn’t before

It’s a subset of X x X

Not X x Y

So then an equivalence relation maps elements of a set to other elements in the same set?

And also based on your example I can see how the collection of all equivalence classes from a relation on X form a partition

[faint narwhal]

Don't really think of it as a map, since a single value can be related to many different values

[indigo cedar]

Ok

[ivory badge]

An equivalence relation isn't a map in the sense you think of it

It's more of an identification of the elements of the set X with elements of a set (of which those elements partition X)

You don't map things to other things in the same set, instead you simply (more or less) say "this is the same thing" and bundle together those things which are equivalent to each other

@indigo cedar An equivalence relation is a relation that's reflexive (a = a), transitive (a=b and b=c means a=c), and symmetric (a=b iff b=a).

if you want to keep your function/map definition, it induces a mapping from the set X to the partitions, sending $x \mapsto [x]$ where $[x]$ is the equivalence class of $x\in X$, but the equivalence relation itself should not be thought of as a function

[vital dew]

Darkrifts:

[indigo cedar]

Okay, gotcha

Thanks for the explanation

Ye I guess I was thinking more in terms of functions

[ivory badge]

Nah

Equivalence relations just partition the set

[stray reef]

it's like putting the elements of your set into buckets

[ivory badge]

they don't exist because functions really (but they do implicitly induce one)

[stray reef]

in such a way that two elements are in the same bucket iff they're equivalent under the relation

then the buckets are the equivalence classes

[ivory badge]

I forget most people on this server, but I remember rmoney knowing what a partition was

[indigo cedar]

Yep that made me happy

To get what a partition was

We covered all this stuff in a discrete math course I took in the fall

But I’m going back now that school is over and trying to fill the gaps in my understanding

Some of this stuff I never really grasped

But now I’m getting it! Thanks to you guys as well 👌

[spring helm]

Hey all, Im looking to right the domain "all non zero real numbers". What would be the correct way to write this? I know it involves of course R

[pale epoch]

to right?

oh, you mean write?

R\{0}

[spring helm]

thank you!

[spring helm]

I am given the following premises in a problem, "I am hallucinating or I am having bad dreams", "I am not having bad dreams", and "If I am having bad dreams, I see elephants running down the road"

I attributed P= I am hallucinating, Q= I am having a bad dream, R= I see elephants running down the road

i formed the premises with symbols as, "P v Q", (negate)Q, and "q -> r"

Im asked to determine if "I am hallucinating" and "I do not see elephants running down the road" are valid, false, or cant be determined

I am hallucinating can't be determined correct? As we do not know if this person sees elephants running down the road

[spring helm]

Anyone here?

And if someone could check this proof that'd be great

@ivory badge are you available?

[ivory badge]

Whomst

so
uh
what do you want

[spring helm]

If you could look at my previous messages it'd be appreciated!

Just checking that proof and a question about the dreams