discrete-math

[hexed rune]

Let g be the polynomial whose coefficients are f(n)

Then we have $g = \sum_{n=1}^\infty n^2x^n +xg$

[vital dew]

Liquid:

[hexed rune]

Do you see why?

[versed hemlock]

1 sec

digesting

damn it

how did the g get there

xg

[hexed rune]

$g=\sum_{n=1}^\infty f(n)x^n $

[vital dew]

Liquid:

[versed hemlock]

and define f(n) again

since it changed slightly from our original recurrence

[hexed rune]

It's still the same

[versed hemlock]

f(n) = n^2 + f(n - 1)?

[hexed rune]

Oh so it's the actual number

[versed hemlock]

hmm what do you mean

[hexed rune]

Like f(n) is the number you would get by evaluating the recurrence

[versed hemlock]

so the result

[hexed rune]

Yep

Alright so now we want to find a generating function for $ \sum_{n=1}^\infty n^2x^n$

[versed hemlock]

i'll be honest im still not understanding how you've derrived the g = ...

[vital dew]

Liquid:

[versed hemlock]

im terrible at this stuff

[hexed rune]

Oh sorry

That's just by noticing that the first and last sum are the same

$\sum_{n=1}^\infty f(n)x^n = \sum_{n=1}^\infty n^2x^n + x\sum_{n=1}^\infty f(n)x^n$

[versed hemlock]

the first sum being the one to the left of the = sign?

the second being the middle one?

[hexed rune]

Just start at 1 instead of 0

The first and the third

[vital dew]

Liquid:

[hexed rune]

You can get rid of the n=0 term

[versed hemlock]

interesting

[hexed rune]

Because f(0) is 0

[versed hemlock]

right

ok now i see that they're the exact same

[hexed rune]

Okay, now we use some calculus to find a generating function for the second sum

So recall from calculus that $1/(1-x) =\sum_{n=0}^\infty x^n$ for x between 0 and 1

[vital dew]

Liquid:

[hexed rune]

We call 1/(1-x) the generating function for the sequence of coefficients of that sum

[versed hemlock]

hmm ok

[hexed rune]

That sequence being (1, 1, 1, ...)

[versed hemlock]

why just 1

[hexed rune]

Those are the coefficients

1(1)+1(x)+1(x^2) +...

[versed hemlock]

oh

right

[hexed rune]

Now if you derivate that sum you get $\sum_{n=0}^\infty nx^{n-1}$

[vital dew]

Liquid:

[hexed rune]

And if you derivate it again you get $\sum_{n=0}^\infty n(n-1)x^{n-2}$

[vital dew]

Liquid:

[versed hemlock]

what does the x actually represent

like where does it come from

[hexed rune]

So for the sake of generating functions

It's literally a place to put coefficients

[versed hemlock]

interesting

how did you derivate

[hexed rune]

That's just calculus

[versed hemlock]

im so rusty on calc

i need to go read probably

[hexed rune]

I just used the old (x^n)'=nx^n-1

But we're almost done now

[versed hemlock]

ok

so what is the next step

[hexed rune]

So let's write $\sum_{n=1}^\infty n^2x^n$ in terms of the functions we just talked about

[vital dew]

Liquid:

[hexed rune]

Note that the second derivative of 1/1-x is $\sum_{n=0}^\infty n(n-1)x^{n-2}=\sum_{n=2}^\infty(n)(n-1)x^{n-2}=\sum_{n=1}^\infty (n+1)nx^{n-1}$

[versed hemlock]

TeXit fell asleep

[vital dew]

Liquid:

[hexed rune]

That's on me

Extra $

[versed hemlock]

hmm so you derived again?

[hexed rune]

No I just rewrote the second derivative

[versed hemlock]

ah i see

[hexed rune]

Look at what happens if you take the second derivative - the first derivative

You get $\sum_{n=1}^\infty n^2 x^{n-1}$

[vital dew]

Liquid:

[versed hemlock]

which one was the first one again?

?

this one?

[hexed rune]

Yep

You can get rid of the 0 term

[versed hemlock]

and the second one is the one you rewrote yea?

[hexed rune]

Yep

(n+1)n-n=n^2

Alright so we've just shown that $x(\frac{1}{1-x}''-\frac{1}{1-x}') $is exactly the sum we want

[vital dew]

Liquid:

[versed hemlock]

what do the quotes mean

single vs double

[hexed rune]

Derivative

[versed hemlock]

2nd derivative - 1st derivative essentially?

[hexed rune]

Exactly

Note that $\frac{1}{1-x}'=\frac{1}{(1-x)^2}$ and $\frac{1}{1-x}''=\frac{2}{(1-x)^3}$

[vital dew]

Liquid:

[versed hemlock]

hmm ok

those are just equivalents?

[hexed rune]

That's taking the derivative

Using the quotient rule

Alright so going back to original problem

we have $g = \sum_{n=1}^\infty n^2x^n +xg$

[vital dew]

Liquid:

[versed hemlock]

please give me ~15 mins

i'll be right back

[hexed rune]

Using the stuff we derived we get $g(1-x) = x(\frac{1}{(1-x)^2} - \frac{2}{(1-x)^3})$

[versed hemlock]

I'll ask when I get back

[hexed rune]

Sure

[versed hemlock]

thanks

you're awesome

[vital dew]

Liquid:

[versed hemlock]

im back

so tell me this, up to this point which maths did you need to get this far?

I want to get into competitive programming, but math skills need to be pretty strong

my programming is pretty solid

math is my major weakness

Is it possible to learn everything I need to know by working backwards from problems, or do I have to go back and re-visit algebra, calc, and discrete math separately?

keep in mind i struggled to follow most of what you were doing

[azure lichen]

it might be a reasonalbe approach to look at problems, see what you need to know to solve them, then study the theory of that, then go back to the problems

repeat until you know the stuff

[versed hemlock]

thats kind of where i'm at with the question liquid was helping me on

i just realized that i know nothing about generating functions

very little about derivatives

[azure lichen]

and make sure you understand what you‘re learning. learning a bag of tricks is handy for fast problem solving, but not the way to actually learn things

[versed hemlock]

Mostly I'll need to be very solid in number theory, and discrete math

[azure lichen]

in studying the theory, you will by no doubt find things you need to know first before understanding the material, that’ll both serve as guides for what to learn and also motivation for learning those basics, I guess

[versed hemlock]

but the problem for me is that most texts that cover those, already assume knowledge of things like calc and algebra

[azure lichen]

which algebra

[versed hemlock]

thats a great question

i dont even know

[azure lichen]

the “solve for x“ or the “a simple group is a …”

kind of algebra

[versed hemlock]

honestly i'd probably fail both if they were complicated enough

even solving for x depending on how difficult the equation

[azure lichen]

well one is typically done before calculus, and the other only in university

[versed hemlock]

i took algebra, calc 1, calc 2, and forgot like all of it

its sad

[hexed rune]

Alright @versed hemlock let's finish this thing

[versed hemlock]

sounds good

[hexed rune]

Using the stuff we derived we get $g(1-x) = x(\frac{1}{(1-x)^2} - \frac{2}{(1-x)^3})$

[vital dew]

Liquid:

[hexed rune]

This gives us $g= x(\frac{1}{(1-x)^3} - \frac{2}{(1-x)^4})$

[vital dew]

Liquid:

[hexed rune]

No we look at the coefficients of the polynomials associated with $\frac{1}{(1-x)^3}$ and $\frac{1}{(1-x)^4}$

[vital dew]

Liquid:

[hexed rune]

Which isn't too hard

[versed hemlock]

so you added a power to the denominator

in the previous example

[hexed rune]

We divided by (1-x)

On both sides

So $\frac{1}{(1-x)^3}=(1+x+x^2+...)^3$

[vital dew]

Liquid:

[versed hemlock]

the two are equivalent?

[azure lichen]

this becomes clearer if you move the ^3 as surrounding the whole fraction

because $$\frac{1}{1 - x} = 1 + x + x^2 + \dots$$ for $|x| < 1$

[vital dew]

Sascha Baer:

[versed hemlock]

| X| is abs right?

[azure lichen]

yes

this is the geometric series, it’s rather useful

[versed hemlock]

but how is abs(x) < 1 different from x >= 0?

[azure lichen]

you can derive this identity with taylor series

[echo lintel]

https://gyazo.com/33443922acaaf49cae259fe95024cc66

where are they getting the 10 from C(10,5) and the 13 from C(13,8)

[azure lichen]

rather different don’t you think?

[versed hemlock]

Oh

I thought it was saying the |x| for x < 1

not x where |x| < 1

[azure lichen]

I was giving you a general statement, unrelated to the problem

[versed hemlock]

i see now

[azure lichen]

if the confusion comes from anywhere within the problem’s description (which I did not read)

[versed hemlock]

no it does not

i confused myself

There's really no problem statement. My original question was how to find a closed form for f(n) = n^2 + f(n - 1)

where f(0) = 0

[azure lichen]

ah well my approach to that would be “I give up” so

not really my cuppa tea

[hexed rune]

@azure lichen read my explanation so far

[azure lichen]

nah I mean I don’t care

[versed hemlock]

Its amazing to see how Liquid is coming up with a solution, but im struggling to understand most of it.

[hexed rune]

Generating functions are pretty cool though

[azure lichen]

it’s not the sort of problem that seems enjoyable to me

[versed hemlock]

let me explain why i asked it to begin with

https://www.spoj.com/problems/SAMER08F/

[hexed rune]

I came up with this solution like a year ago, I'm just struggling to recall all the steps

[versed hemlock]

that recurrence can be written in code with a runtime of O(N) @azure lichen

linear time

with a closed form, the code can run in O(1) constant time

thats a huge improvement

[azure lichen]

oh I’m aware of that

[versed hemlock]

order of magnitude

so for me I think I need to learn how to derive these closed forms for recurrences in order have the most efficient solutions

[azure lichen]

I’m just saying I’m not really into these things :P

[versed hemlock]

im just finding I lack a ton of knowledge to actually do it myself

[azure lichen]

well, all the more reason to learn!

[hexed rune]

Yeah you can solve all linear recurrences using generating functions

And I think polynomial recurrences as well

[versed hemlock]

its not arithmetic because the difference changes right?

and its not geometric because there's no clear multiplying pattern

so the difference itself changes linearly

which means linear recurrence correct?

[hexed rune]

You should look at the book generatingfunctionology

[versed hemlock]

Liquid how much math experience do you have up to this point

[hexed rune]

Im starting my PhD in the fall

[versed hemlock]

wow

thats awesome

congrats man

[hexed rune]

Also look at knuth's concrete mathematics

[versed hemlock]

I did!

i have the book!

i struggle to understand it

i was actually gonna ask you

how easy do you find it to read

[hexed rune]

I've only really used it as a reference but I liked it a lot

[versed hemlock]

what should I do if I struggle to understand his texts

[hexed rune]

Just keep at it

Everyone struggles

[versed hemlock]

the most difficult thing for me is knowing where to start

do you have any good learning material references?

for someone like myself who clearly struggles to follow what you were doing

[hexed rune]

Just read the first chapter or so of generatingfunctionology and you'll understand what I was doing

[versed hemlock]

do they explain the calc part of it

deriving etc

[hexed rune]

Just review Taylor series and the basics of derivation and integration

And that will make sense

[versed hemlock]

thats the problem

[hexed rune]

When you learn Taylor series you do a lot of similar manipulations

[versed hemlock]

how would I have known that without someone telling me

like how would I have known that its the Taylor series, and Generating functions that i'm missing

[hexed rune]

You wouldn't

Tbh the question probably just wanted you to look it up

It's not a standard exercise to derive that formula in the uni math curriculum

[versed hemlock]

i see

[hexed rune]

You're usually given it

[versed hemlock]

so i guess im doing the right thing ha?

[hexed rune]

And you have to prove it's true

[versed hemlock]

by asking of course

[hexed rune]

Yeah

Asking is good

[versed hemlock]

thanks for the help

i'll go read what you suggested

[hexed rune]

It would be a good exercise to finish my derivation

For after you've read a bit

[versed hemlock]

i'll try

so do you also recommend to keep reading the knuth text?

[hexed rune]

Yep

[versed hemlock]

its a tough read but maybe it'll get easier as I explore some of the gaps in my knowledge

[hexed rune]

Yeah

Also time helps

[azure lichen]

yea, don’t rush through things

[versed hemlock]

ok thanks guys

theoretically i have all the time i need

outside of work that is

[versed hemlock]

https://www.khanacademy.org/math/algebra-home/alg-series-and-induction/alg-sum-of-n-squares/v/sum-of-n-squares-1

interesting

Khan Academy actually describes this problem too

he solved it a different way

[hexed rune]

How does he solve it?

[versed hemlock]

he observed the pattern in the sequence

and concluded that it could be expressed as a cubic function

[hexed rune]

I finally remembered how to finish the derivation actually

[versed hemlock]

the one thing i dont understand from the end of his first video is how he got An^3 + Bn^2 + Cn + D

[hexed rune]

It's pretty easy once you realize that $\frac{1}{1-x}^n $ can be expressed in terms of the nth derivative

[vital dew]

Liquid:

[hexed rune]

What do you mean?

[versed hemlock]

its the first thing he wrote when he found that the difference of the difference of the difference is changing by a constant 2

[hexed rune]

So that's the general form of the cubic

[versed hemlock]

ah i see

then he got rid of the D by observing that when N is 0, D is left over

[hexed rune]

Yep

[versed hemlock]

and we need f(0) = 0

[hexed rune]

But tbh this isn't really a derivation

Like if he hadn't known the answer previously I doubt he would have checked the cubic

[versed hemlock]

well the reason he checked the cubic is because he saw how the sequence was changing

like 0, 1, 5, 14, 30

1, 4, 9, 16

3, 5, 7

2, 2

by seeing that the 2 remains constant as the difference of the difference of the difference, he concluded that it must be possible to express it as a cubic function

[hexed rune]

So I don't agree with that

I can make a sequence which is given by a 20 degree polynomial which also has those first 5 terms

Or a 1000 degree polynomial

That's not a valid justification

It just seems like a weird thing to check unless you know beforehand that it's a 3rd degree polynomial

[harsh warren]

very quick question: in graph theory, when a walk/path is simple, it means that no vertices are repeated. when we say no vertices are repeated, does that imply no edges are repeated too?

[hexed rune]

If no vertices are repeated then how can an edge be repeated?

[harsh warren]

yeah that was what i was thinking, so i was just double checking

[wild harness]

can anyone help with proof by induction

i have a closed formula that i need to prove

[stray reef]

sure, what's giving you trouble?

[wild harness]

is this how you show proof by induction? or is it not enough information

[stray reef]

okay you'll have to clarify what it is you're proving

from what it looks like though all you did was test three values of n (0, 1 and 2) and that's it

[wild harness]

how many values of n should i prove?

up to n+4 nvm

for this relation, i need to observe the equivalence classes and sketch in a picture by plotting a x,y and find a (w,z) that satisfies it

not sure how to find the (w,z)

[weary tiger]

what might be more helpful is stating it in this form:
(x,y) ~ (w,z) iff:
x² + y² = w² + z²

also recall the formula for a point's distance from the origin

[hexed rune]

That relation is only an equivalence relation on the plane minus the origin

Because of the way it's stated

[wild harness]

so use sqrt(x2-x1) + (y2-y1) ?

^2 on both

[hexed rune]

So distance from the origin

Not from a point

So just $\sqrt{(x^2+y^2)}$

[vital dew]

Liquid:

[weary tiger]

btw are you the same liquid that had a pfp with a hand on some mirror

[hexed rune]

Yep

I'm a horse now

[weary tiger]

lmao

[wild harness]

so how would I apply that? using my own x and y’s?

[weary tiger]

by realizing that two points are in the relation iff they have the same distance from origin

[hexed rune]

What does that mean geometrically?

[wild harness]

so is 0,0 the origin?

[hexed rune]

Yep

[wild harness]

but now what do I do with the x and y?

how do i apply w and z with this

[hexed rune]

So we know $\sqrt{x^2+y^2}=\sqrt{w^2+z^2}$

[vital dew]

Liquid:

[hexed rune]

Which tells us that (x, y) and (w, z) are the same distance from the origin

[wild harness]

ok yes

[hexed rune]

So what do the set of points which are of distance r from the origin look like?

[wild harness]

like how the graph looks?

[hexed rune]

Yes

What shape is it?

[wild harness]

a circle?

[hexed rune]

Yes

The circle of radius r

[wild harness]

so if it is equal to 1

is the radius 1?

[hexed rune]

If $\sqrt{(x^2+y^2)}$=1, then the circle is of radius 1

[vital dew]

Liquid:

[wild harness]

so i would just plot a circle with radius 1

and w and z would be equivalent to x and y

[hexed rune]

That would work

Every other point on the circle would be equivalent

[wild harness]

what do you mean by every other point

[hexed rune]

A point (w, z) is on the circle of radius 1 iff $\sqrt{w^2+z^2}=1$

[vital dew]

Liquid:

[wild harness]

so which points of sqrt w^2 and z^2 would equal to 1

cause points are -1 and 1

so sqrt2 wouldn’t be equal to 1

[hexed rune]

Oh they gave you points?

[wild harness]

no

i did this as my graph

should I use higher points?

[hexed rune]

You're thinking of the point (-1, 0)

That's fine

(-1, 0) and (1, 0) are equivalent

[wild harness]

so those would be my points of w and z?

[hexed rune]

You can choose (x, y) =(1, 0) and (w, z)=(-1, 0)

And that would be valid

[wild harness]

so that would sum it up?

[hexed rune]

Yeah, looks like it

[wild harness]

thanks so much for helping!

textbook had nothing on this at all

only how to graph equivalence classes

not showing distance from origin or anything

[weary tiger]

how do i go about calculating this

$14^{2019^{2019}}$ mod $60$

[vital dew]

yami:

[faint narwhal]

find the remainder mod 3,4,5 and then combine them to get the mod 60

@weary tiger

[weary tiger]

hm, i did something different

[faint narwhal]

how'd you do it?

[weary tiger]

first i computed 2019^2019 mod 60 by noticing that 2019 = 19 mod 60, and 19² = 1 mod 60
so 19^19 = 19^{2*9 + 1} = 19 mod 60

now you only have to do 14^19 mod 60, and then i forgot how modular arithmetic works

[faint narwhal]

a^b isnt equivalent to a^ (b mod p) though, cause fermat's little theorem

[opal crescent]

and 2019=19mod60 wat

[weary tiger]

that is why i included the forgot how modular arithmetic works >:(

[hexed rune]

is this question well posed actually?

how does the exponentiation work?

is it a^(b^c) or (a^b)^c

[weary tiger]

first one

[faint narwhal]

right associative is the norm

[hexed rune]

is it

oh lol, I didn't know that for some reason

[faint narwhal]

Yeah idk at least its what ive seen

I think it's mostly due to the fact that (a^b)^c = a^bc so people just write that

[hexed rune]

ah ok

makes sense

[weary tiger]

$14^{(2019^{2019})}$ mod $60$

its like that

[hexed rune]

lol

[vital dew]

yami:

[faint narwhal]

anyways yeah calculate it mod 3,4,5 and use chinese remainder theorem to get the mod 60

[weary tiger]

[wild harness]

anyone know how to solve b and c? i did a, but i am confused with the others

professor said to ask about “invariant” but when i emailed he said that he wouldn’t be able to answer lol 😐

[stray reef]

given two pairs $(a,b)$ and $(a',b')$ which are equivalent under the relation from example 8.3.12, show that $(a,b) + (c,d) = (a',b') + (c,d)$ and likewise with multiplication

[vital dew]

Ann:

[stray reef]

invariant means unchanging

basically you're asked to prove that choosing a different representative from the same equivalence class doesn't affect the result of the operation

[wild harness]

btw this is what i did so far

so what would i change if i showed division

since you need to change representative

or if i showed addition*

[echo lintel]

when do i use product rule and when do i use sum rule

i have a slight understanding of both, but is there a clear way to see during a problem

[wild harness]

if anyone who can help with my question, i’ll be getting off. send me whatever you can to my dm’s or ping me it. thanks!

[lunar wigeon]

hey so how do i do this type of induction proof? instead of piecewise its giving me summation

[wild harness]

anyone know definition of division of pairs?

i know there’s divisibility

but is there division of pairs?

[stray reef]

uh

context?

[wild harness]

Define division of pairs for (a,b) and (c,d) and show that it is well-defined

has to do with rational numbers as an equivalence class on the Cartesian product Z x Z.

it was from the question I sent last night

[weary tiger]

$14^{(2019^{2019})}$ mod $60$

[vital dew]

yami:

[weary tiger]

kinda struggling with how i get to split it up to use the CRT

[faint narwhal]

did you find the values mod 3,4,5?

[weary tiger]

that’s where the problem begins

[faint narwhal]

Okay well what have you tried? Or what have you thought about

[weary tiger]

uhh nothing really, i literally don’t know how to go about this

i saw some euler phi function stuff but i guess that’s about it

i have to do it without a calculator no matter what though

[faint narwhal]

Okay well start with $14^{2019^{2019}}$ mod 4. What is this?

[weary tiger]

i’m not sure how to answer

[faint narwhal]

Sorry

I messed up

[vital dew]

Zopherus:

[weary tiger]

ok so i can probably just do 14 mod 4 which would give me 2 mod 4

and then maybe also trim the exponents i guess?

2019 mod 4 would be 3 mod 4

[faint narwhal]

Remember that you can also interpret mod as remainder after division. You have 2^some big power and you're looking at this mod 4.

[weary tiger]

which means?

[faint narwhal]

what would be the remainder if you divided 2^big power by 4?

[weary tiger]

0 or 2, no?

[faint narwhal]

remember that 4 = 2^2, how would dividing 2^x by 4 work?

[weary tiger]

uhh.. modulo the exponent?

[faint narwhal]

What is 2^10 divided by 4?

[weary tiger]

i can’t tell

lol

[quaint river]

Well a = b mod 4
c = d mod 4
ac = bd mod 4

wait

thats wrong

OOPs

2^2 = 0 mod 4 then that implies 2^x = 2^2 * 2^(x-2) = 0 * 2^(x-2) mod 4

assuming x > 2

[weary tiger]

my brain boom

had to leave for a bit, sorry

@faint narwhal are you still here?

[faint narwhal]

Yeah

[weary tiger]

so it seems that 2^x mod 4 where x > 2 is always 0? seeing how victoria also explained it

seems to check out for the first few ones im doing in my head

[quaint river]

Uhh

0 * anything = 0

so yes

[faint narwhal]

Yeah this is true

And going back to the problem, we obviously have that 2019^2019 > 2, so we know that our number mod 4 is 0. Now we can think about it mod 3 and 5

[weary tiger]

2^... mod 3 and 4^... mod 5

2019 mod 3 is 0

2019 mod 5 is 4

what we do with this now

[quaint river]

are you modding 2^(big thing) by 3?

[weary tiger]

and 5

[quaint river]

if so

theres a pattern

2^2 = 1 mod 3 2^3 = 2 mod 3 2^4 = 1 mod 3 etc

it will keep repeating

[weary tiger]

it is, ive done some repeated squaring

[quaint river]

so then we have 2 ^ even .= 1 mod 3

2^ odd = 2 mod 3

[faint narwhal]

No. Remember the number we started with is 14, so instead of reducing that down to 2 like we were able to do when considering it mod 4, we have to reduce 14 down to different numbers

[weary tiger]

so what do we do now

[quaint river]

Well if you have 14^ big thing mod 3, using modular arithmetic we get that its equivalent to 2^ big thing mod3 because 14 = 2 mod 3

im confused what you want so 🤔 maybe im not helping here

[weary tiger]

$14^{(2019^{2019})}$ mod $60$

[vital dew]

yami:

[weary tiger]

we got the prime factorization of 60 being 3, 4, 5

[quaint river]

so you have x mod 60 and you want to use CRT to do x mod 3, x mod 4, x mod 5

ok

So then what i just said is correct

14^ (2019^2019) mod 3 = 2^(2019^2019) mod 3

because 14 = 2 mod 3

[weary tiger]

yuss

[quaint river]

so then now we are back to what i said just now

for 2^ x mod 3 theres a pattern

where if x is odd then 2^x = 2 mod 3 and if its even its 2^x = 1 mod 3

so we also know that any power of an odd number is odd

so then 2019^2019 is odd

so then 14^(2019^2019) = 2 mod 3

[serene vigil]

May i know the direct question?

[weary tiger]

we cant do anything with the exponent itself?

[quaint river]

what do you mean?

[weary tiger]

just scroll up a little bit @serene vigil

like taking the exponent modulo or something like that

[serene vigil]

14^ (2019^2019) mod 3 = 2^(2019^2019) mod 3

This?

[quaint river]

no

14^(2019^2019) mod 60

[vital dew]

yami:

[quaint river]

what do you mean take the exponent modulo?

if we had (14^2019)^2019 we could have solved 14^(2019) = 2 mod 3 then

2^(2019) = 2 mod 3

[weary tiger]

ah w/e i wanted to take the 2019 mod 3 but that wouldve been to easy

and wrong

[quaint river]

yes thats not correct

i mean

yes you can use wolfram

but you want to know how to do it

[weary tiger]

this is to be done exclusively by hand

[quaint river]

the point is to learn how to solve these not just get the answer

[serene vigil]

Oh ok

[weary tiger]

no calculator or anything

[serene vigil]

As you wish

[quaint river]

so now we have to do 14^(2019^2019) mod 5

which is 4 ^big thing mod 5 yes

the same pattern exists here, we have 4^ 2 = 1 mod 5, 4^3 = 4 mod 5, 4^4 = 1 mod 5 etc

so we get 4^ big thing = 4 mod 5 since its odd

so now you can just apply crt

however you have a 0 in your congruence for 4

[weary tiger]

$14^{(2019^{2019})}$ mod $3 = 2$ mod $3$ \ $14^{(2019^{2019})}$ mod $4 = 0$ mod $4$ \ $14^{(2019^{2019})}$ mod $5 = 4$ mod $5$

[vital dew]

yami:

[weary tiger]

so this is where we're at, yes?

[quaint river]

yes

[weary tiger]

okay

[quaint river]

you cant just apply crt here because of the 0

pretty sure

[weary tiger]

scuffed crt

[quaint river]

so if we have x mod 4 = 0

then i think you replace everything by 4x? and ignore the x mod 4

im actually not sure

[weary tiger]

sec i think this might have been in a previous assignment

[faint narwhal]

no you still can apply crt

[weary tiger]

oh yeah because the mods are coprime

no?

i know i had an example for moduli 5, 9, 10 where it didnt work because they werent all coprime

[quaint river]

ok nevermind it works

[faint narwhal]

yeah the mods are coprime is the only requirement

[weary tiger]

comes out as 224 mod 60

may i have some help with this one as well? i kind of solved it using recursion but then i saw some other people did it using euler's phi and fermat's theorem

$2^{(2^{32})}$ mod $11$

[vital dew]

yami:

[quaint river]

do you mean eulers theorem 🤔

[weary tiger]

his phi function

oh, i guess its called euler's theorem

[quaint river]

It doesn't seem that nice to work with

we have phi(11) = 10

so we know that 2^(10) = 1 mod 11

[weary tiger]

dont we have to take gcd of 2, 10 then

[quaint river]

wdym?

only 11 and 2 have to be coprime, phi(11) does not necessarily have to be coprime

[weary tiger]

[quaint river]

oh ok

1sec

[weary tiger]

i think youre fine

[quaint river]

so we have 2^(2^32) = 2^(2^32 mod 10) mod 11

[weary tiger]

yuss

[quaint river]

this gets a bit messy

but 2^ x repeats in powers of 4

im pretty sure

2, 4, 8 ,6 ,2 ,4 ,8 ,6

like 2^x mod 10

[weary tiger]

the mod 10 is part of the 32 or 2?

2 right?

[quaint river]

its (2^(32)) mod 10

[weary tiger]

oke

[quaint river]

ok so

note that 2^x mod 4 has the pattern 2,4, 8,6,2,4,8,6 ...

so 32 is a multiple of 4

thus 2^32 = 6 mod 10

so we have 2^6 mod 11

this has to just be done manually unfortunately

we have 2^4 = 16 = 5 mod 11 2^5 = 10 mod 11 2^6 = 20 mod11 = 9

so your answer is 9

[weary tiger]

isnt this supposed to be mod 10?

[quaint river]

no no no

[weary tiger]

2^x mod 4 has the pattern 2,4, 8,6,2,4,8,6 ...

[quaint river]

we mod the power by 10

ok so for coprime

a, n

we have this formula from eulers theorem

$ a^{x} \equiv a^{x\ mod \phi(n)} mod n $

[weary tiger]

yes

[vital dew]

Victoria:

[quaint river]

here phi(n) = 10

and our x is 2^32

yes?

[weary tiger]

yes

[quaint river]

we calculated 2^32 mod 10 by noticing it repeats

with period 4

since 32 is divisible by 4, its the fourth number in thep attern, which is 6

[weary tiger]

not yes

[quaint river]

ok so if we look at 2^x mod 10

we have 4 possible answers

2, 4, 8 or 6

because 2^x = 2 mod 10 -> 2^(x+1) = 2*2 mod 10 = 4 mod 10 -> 2^(x+2) = 8 mod 10 -> 2^(x+3) = 16 mod 10 = 6 - > 2^(x+4) = 6* 2 mod 10 = 2

so it repeats

[weary tiger]

you can escape the * with \

[quaint river]

ok discord formatting is terrible

im trying

[weary tiger]

\* *

[quaint river]

ok

[weary tiger]

XD

[quaint river]

i had to escape the first character

not the second one

but anyways, we have the pattern there

so noting that we start at 2^1 = 2 mod 10, and 2^4 = 6 mod 10, we have that 2^32 mod 10 = 2^4 mod 10 = 6

so then we end up with 2^(2^32) mod 11 = 2^6 mod 11

[weary tiger]

wait so

because 32 is a multiple of 4 and the pattern resets after every 4th result you determine that 2^32 mod 10 must be 6 becasue 2^4 mod 10 is also 6

[quaint river]

yes

[weary tiger]

and then the exponent gets reduced to 6

[quaint river]

yup

[weary tiger]

okay cool, seems like i understand the whole thing now

t!rep @quaint river

[uncut grove]

🆙 | yami has given @quaint river a reputation point!

[quaint river]

Yay

[weary tiger]

let me know if i can ever do something for you, perhaps not discrete math related tho maybe calculus or cs related stuff

[quaint river]

I dropped out of cs to become a math major oof

[weary tiger]

traitor

[quaint river]

My cs teachers were terrible and my discrete math teacher wrote mathematical statements that would trigger every math professor ever

with statements like the only definition of an odd number is a number of the form 2n+1

when i tried to say n = 1 mod 2 is a definition of an odd number

But yea cs sucks at my school and their math program is pretty good

[weary tiger]

ok i dont go to discrete math lectures either because of the prof

[quaint river]

so i decided to do math instead since I can self learn cs

[weary tiger]

definitely not a wrong approach, theres a lot of bloat that comes with cs majors come with

[quaint river]

http://www.ratemyprofessors.com/ShowRatings.jsp?tid=2036931

yea

also a lot of cs is like irrelevant theory imo if you really want to get a job

so unless you go into academia its not that useful

[weary tiger]

nice rating tbh

XD

[quaint river]

Yea its pretty yikes

[weary tiger]

my uni is very theoretical on stuff

[quaint river]

yea thats most cs programs which is honestly terrible

also I dont really like the idea of college in general honestly, theres too many useless classes that just waste your time

[weary tiger]

for me its not so much the classes themselves as much as it is the incompetence of professors to design a proper class

[quaint river]

cause universities dont hire professors to teach but to do research :/

they should hire specific professors to teach imo

[weary tiger]

like i had to work on a game where they would force you to use y, x to determine coordinates, or work on a database where datasets are incomplete/wrong multiple times after he "fixed" them

[quaint river]

Pay 40k a year for terrible classes and drown in student debt

[weary tiger]

i dont feel you on that one

free tuition

[quaint river]

Oof

[weary tiger]

but still horrible so whatever XD

[quaint river]

I mean personally its not an issue for me as my parents are pretty well off but a lot of my friends struggle with it

which is sad

[weary tiger]

i havent yet realized it completely but getting out of college w/ a degree and no debt seems like a massive advantage

[quaint river]

yea :feels

bad

man

And then even after tuition textbooks and online homework costs even more money

[weary tiger]

wdym?

online homework?

[quaint river]

Yea, you pay for a textbook, which has a code

which lets you do homework on their portal for your professor

[weary tiger]

o you mean in addition to the 40k/year

[quaint river]

cause your professor is lazy and wont grade it by hand

yes

100 dollar per class

I actually tried making something to replace those online homework portals but the hardest part is getting questions for every class

also server load i guess

[weary tiger]

hmm

we dont even use textbooks here

theres like a manual written by the directors of each course and you pay like $10 for it and it contains everything pertaining to the lecture

but then again its only for math classes it seems

and useless kinda because they sometimes have the kind of math statements like the ones your prof used ot make

lol

[quaint river]

yea math classes seem a lot better than the rest, usually the teachers are able to explain things much better too

[weary tiger]

so 98% of the time im really better off with this discord and youtube

nooo this discrete math class is horrible XD

[quaint river]

Anyways time to go fail my abstract algebra final

[weary tiger]

i loved calc/real analyiss, that prof was so good

good luck and thanks again

[quiet kraken]

hey can a simple graph by disconnected
?

[oak creek]

yes

A simple graph is defined as having no 1 node-cycles and no repeat edges

so being disconnected is possible

[modest zealot]

any trick to finding chromatic number guys?

[faint narwhal]

I mean it's a hard problem in general? Look for complete subgraphs to get a lower bound on the number? Then try to find colorings to get an upper bound for it

[analog sonnet]

Except there are triangle free graphs with arbitrarily high chromatic number :(

So if you're unlucky you might be unable to use that technique at all

[reef temple]

can someone help real quick

im not sure i understand how you're supposed to solve this

[analog sonnet]

What have you tried?

[faint narwhal]

What have you tried? Or what are you confused about?

[hexed rune]

You can do this using diagonalization or generating functions

[reef temple]

oh i figured it out

i forgot i asked for help here lol

[analog sonnet]

🍮

[covert glade]

Hey guys, is it possible for a relation to be both reflexive and irreflexive? I think no but i'm not 100% sure.

[hexed rune]

Look at the definitions lol

[reef temple]

No, if even just some of the elements are related to themselves then it fits neither definition.

and every element related to itself and no element related to itself cannot both be true

[covert glade]

I see thank you.

[wintry hawk]

is 0>= |x-a| >= b, same as x = a & x-a>= b

[analog sonnet]

Yes

[keen kelp]

can someone help me with my stat hw @here

[analog sonnet]

#probability-statistics

[keen kelp]

it's discrete math

but involving combinatoric

[pastel temple]

Shouldn't this proposition be an exclusive or instead of a disjunction?

[prime steeple]

This is the classical definition of an implication (which is quite debatable on its own).
But nontheless, what you don't see, I think, is that if you claim this statement to be true, then if the left hand side evaluates to false, then claiming this forces q to be true

[pastel temple]

So whenever I see an either/or phrase its a disjunction as long as its not explicitly mentioned "but not both"?

or does it depend on what is being discussed

for instance " You can have soup or salad"

[prime steeple]

I don't feel conforable as if any textbook or convention would be the way to go

[ashen thorn]

In English it's usually an exclusive or, IME

[prime steeple]

In logic as done by philosphers and mathematicans, nor isn't used that often - so much I can say

[ashen thorn]

it's pretty confusing though

[pastel temple]

Okay so this the initial example is indeed a disjunctive proposition?

[prime steeple]

None of the connectives in classical logic translate well to spoken language

We married and had beautiful night

isn't a logical or, as it implies causality

I hate all humans and I hate all Norwegians

isn't interpreted the same was as

I hate all humans

despite the second one being logically speaking redundant

(not P) or Q
is how the material implication is defined and useful in binary logic - the one you usually want in math

P => Q := (not P) or Q

[pastel temple]

Ah alright I'll focus on recreating the conditional from the disjunction

to better understand

[prime steeple]

Use truth tables. You only need the "negation" and "and"

not x := 1 - x
x and y := x * y

x or y = not ( (not x) and (not y) )

x implies y = (not x) or y

x xor y = ...

You find them all on the sidebar on the wikipedia pages

https://en.wikipedia.org/wiki/Exclusive_or

[pastel temple]

ok ill give it a look thank you nikolaj, i appreciate your time.

[prime steeple]

np

"keep calm and reject weakening and the law of excluded middle"

[weary tiger]

"Cats that love dogs don’t taunt dogs."

Solution : The domain may be any set containing the dogs and cats. Let
C(x) mean that x is a cat, D(x) mean that x is a dog, L(x,y) mean that x loves y, and T (x, y) mean that x taunts y. This sentence has a few plausible interpretations. Perhaps it means that cats that love all dogs don’t taunt dogs:
∀x(C(x) ∧ ∀y(D(y) → L(x, y)) → ∀y(D(y) → ¬T (x, y))). Perhaps it means that cats that love some dog don’t taunt dogs:
∀x(C(x) ∧ ∃y(D(y) ∧ L(x, y)) → ∀y(D(y) → ¬T (x, y))).

Can someone help me how to translate "∀x(C(x) ∧ ∀y(D(y) → L(x, y)) → ∀y(D(y) → ¬T (x, y))). "

I'm not sure if it should be read as C(x) ∧ (∀y(D(y) → L(x, y))) first, and then ∀y(D(y) → ¬T (x, y))) ?

[quaint river]

These brackets are terrible

[vital dew]

Victoria:

[weary tiger]

TeXit

[quaint river]

Your last line is the right way to read it

[weary tiger]

oh okay. let me try

For every x, it is a cat & for every y if it's a dog, then cat loves y, then for every y if it's a dog, x doesn't taunt y.

hm...

[quaint river]

I think a better way to phrase it is

For every cat, all dogs love the cat, and doesnt taunt them

Ok thats not much better

[weary tiger]

wait dogs not love the cat, cat loves dogs

[quaint river]

Oh ok

So cat loves dog and so cat doesnt taunt dog

[weary tiger]

""Cats that love dogs don’t taunt dogs."

[quaint river]

Yes

[weary tiger]

yea that's the original phrase, but I'm just having hard time how that whole thing translates into this

[quaint river]

Ok so look at the first part

It says, for every cat, cat loves every dog

So all cats love all dogs

[weary tiger]

yes

[quaint river]

Now the right side is all dogs do not get taunted by cats if the previous statement is true

[weary tiger]

right

[quaint river]

So, cats that love all dogs don’t taunt dogs

The first part is (all cats love all dogs) -> (cat doesnt taunt dogs)

So cats loving dogs imply cats doesnt taunt dogs

[weary tiger]

ooooh...

okay so there is some depth of implication i need to connect these two seperate statements smoothly

okay I think I get it now

thank you very much!

[weary tiger]

"Friend’s of Fido’s friends are Rover’s friends."

soln: Let the domain be, e.g., the set of dogs. Let f refer to Fido and r to Rover. Let F(x,y) mean that x is a friend of y.

,tex ∀x(F(x,f) → F(x,r))

[vital dew]

Nathan:

[weary tiger]

That's the soln given by my professor, but what I got is

∀x∀y(F(x,y) ^ F(y,f)→ F(x,r))

[weary tiger]

Wouldn't it require both x & y since I'm trying to make a relation between friend's of Fido's friend's?

[quaint river]

Uhh

No

If you're a friend of fido you're a friend of rover

so that means F(x,f) [you are a friend of fido] - > F(x,r) [ you are a friend of rover]

then you just generalise it to all x

[weary tiger]

right

but isn't it friends of friends of Fido?

not direct friend

Like "Oh I know of him. He's a friend of my friend.

So he's not my friend, but my friend's friend.

[quaint river]

Huh

oh crap

it says friends of fido s friends are rovers friends

i think thats a typo?

[weary tiger]

Assuming it's not a typo, it would be incorrect solution right?

@quaint river

[echo lintel]

https://gyazo.com/7888b78306c300fe3b8d2e34977d82a4

D:

[faint narwhal]

What are you having trouble with

[echo lintel]

idk what formula

to use

i dont think we got to this in class >_<

[faint narwhal]

It's called the binomial theorem

[reef temple]

you can expand it into this series

which is easier to solve

the binomial theorem

@echo lintel

so its asking for the coefficient of the 8th term in this expanded seies

[echo lintel]

ahh okay ty

lemme work it out

[faint narwhal]

That literally is the binomial theorem

[reef temple]

yes

i didnt mean that was easier to solve than the binomial theorem

i was saying thats what it was but worded it badly

[faint narwhal]

Oh okay sorry

[void valve]

Could anyone explain to me why the equeation 10x+3=5 (mod 22) does not equal 10x-22y=2? Like, are you not allowed to combine the constants on one side?

[stray reef]

well for starters the latter contains y while the former does not

[void valve]

Yeah sorry for being unclear, that is how I'm representing the mod

equivalent sing for the first equation

[stray reef]

who's telling you you're wrong though

[void valve]

It's not?

https://www.wolframalpha.com/input/?i=10x%2B3%3D5+(mod+22)

compared to: https://www.wolframalpha.com/input/?i=diophantine+10x%2B3%3D22y%2B5

Perhaps I'm just being stupid haha

[velvet spire]

both of those give the same solution sets tho

[remote inlet]

@echo lintel answer is - 900?

I got -900

[void valve]

yeah ok, I'm just confused. Got it, thanks

[quaint river]

@weary tiger yes, sorry for not replying earlier I was on a reallu long flight :(

[weary tiger]

oh no worries 😃

[vague maple]

How do I find the negation of this statement?

Specifically, I want to describe this statement using quantifiers: A sequence of real-valued functions (fn) defined on S does not converge uniformly on S.

[void valve]

Hey guys, I'm wondering whether there is a pain-free way of calculating 444^101 (mod 1961) or did my book just assume that one uses a computer for that?

[dense thicket]

ask in #elementary-number-theory maybe, I've seen people doing there similiar problems

[glossy adder]

not allowed to just use$\nexists$?

[vital dew]

CaptainLightning:

[glossy adder]

[dense thicket]

No he needs to use forall probably

so basically Alvin just change exists to for all and the other way around lol

[glossy adder]

if not you could do like $\forall f(x)$ on $S, \exists \epsilon>0$, $\forall N>0, \exists n>N \exists x \in S, \|f_n(x)-f(x)|\geq \epsilon$

bleh spacing

anyway yeah like that

[vital dew]

CaptainLightning:

[dense thicket]

@vague maple

[vague maple]

@dense thicket @glossy adder Thanks, but the problem I'm having is that I don't know why the > inequality sign is not negated

[glossy adder]

$\geq$ is the negation of $<$ basically

[vital dew]

CaptainLightning:

[dense thicket]

negation of x<0 is obviously x>=0, basically numbers that dont satisfy x<0

[vague maple]

oh

How come the there exists doesn't get negated?

i mean

this part

[dense thicket]

umm it is negated

in the message from texit

end of first line

[vague maple]

Shouldn't the negation be there exists an x not in S?

[glossy adder]

no

the x that aren't in S don't affect anything

[dense thicket]

In general, when negating a statement involving "for all," "for every", the phrase "for all" gets replaced with "there exists." Similarly, when negating a statement involving "there exists", the phrase "there exists" gets replaced with "for every" or "for all."

Becuase what you want to do in this case is find one number in S which doesnt satisfy the condtition after

[vague maple]

@dense thicket @glossy adder Sorry for the pings, but just to clarify, with statements involving quantifiers, only the quantifier part is negated and nothing else, i.e. inequalities?

[dense thicket]

The inequality at the end is negated

[vague maple]

Because there's no quantifier in front of it

[lean leaf]

I'm trying to describe matrix equality. Is this correct?

,tex Let A and B be matrices of the same order. $A = B \leftrightarrow \forall a_{ij} \forall b_{ij}, a_{ij} = b_{ij}$

[vital dew]

0x13A:

[weary tiger]

I'd just have "forall i, j" at the end and not be specific about their range of values (since you've just said "of the same order").

$A = B \leftrightarrow a_{i j} = b_{i j}, \forall i,j.$

[vital dew]

gcc:

[lean leaf]

Oh, yeah, that looks cleaner. But was mine wrong?

[faint narwhal]

Yes. Yours would imply that all elements of A and B are equal

[lean leaf]

Hm, I see.

[weary tiger]

For all sets A, B and C, (A − B) − (B − C) = A − B

Hi fellow maths fans! Does anyone know how I'd prove/disprove this?

[hexed rune]

Well B-C is inside B

So you're not removing anything that's inside A-B

If you convert A-B to $A\cap B^c$ every time you see a A-B this will follow immediately

[vital dew]

Liquid:

[hexed rune]

Or you could use the argument I said above

[weary tiger]

If A = {1,2,3} and B = {3,4},
A - B = {1,2}

Is this true?

[hexed rune]

Yes

[weary tiger]

Thanks Liquid!

I get what you mean

[weary tiger]

,tex
∀x(C(x) ∧ ∀y(D(y) → L(x, y)) → ∀y(D(y) → ¬T (x, y))).

[vital dew]

Nathan:

[weary tiger]

,tex
∀x∀y(C(x) ∧(D(y) → L(x, y)) → (D(y) → ¬T (x, y))).

[vital dew]

Nathan:

[weary tiger]

Are these two equivalent?

C(x) mean that x is a cat, D(x) mean that x is a dog, L(x,y) mean that x loves y, and T (x, y) mean that x taunts y

[hexed rune]

Yeah there are some rules about distribution of for alls

[weary tiger]

okay ty 😃

[echo lintel]

if A is a set and B is a set

and i want to say "A and B"

is it A union B or A intersection B

i always thought it was union

but this video is saying intersection

ah nvm and is intersection

[quaint river]

Elements in A and B is intersection

Elements in A or B is union

[hexed rune]

Intersection corresponds to and and union corresponds to or

[weary tiger]

C(x) mean that x is a cat, D(x) mean that x is a dog, L(x,y) mean that x loves y, and T (x, y) mean that x taunts y.

I need to translate: "Cats that love dogs don't taunt dogs".

[vital dew]

Nathan:

[weary tiger]

This is the solution.

Now I asked my professor if this would be the same as his soln.

[vital dew]

Nathan:

[weary tiger]

His response:
"The formula I wrote only makes a claim about those cats that love all dogs. Your formula also makes a claim about pairs of cats and dogs where the cat doesn’t necesssarily love all dogs ".

I still don't understand why it's not the same 😦

[echo lintel]

https://gyazo.com/e069e6e318e10801ed45a97527abb9ec

what formula is happening here..

[weary tiger]

binomial I believe

do you mind moving your post to another topic cuz this is for discrete math?

I think they can help you on precal or calculus

[echo lintel]

that is discrete lol

[weary tiger]

oh really? rofl

[echo lintel]

or in my textbook

[weary tiger]

mb lol

[echo lintel]

has to do with advanced counting

[weary tiger]

rip

[echo lintel]

ok so

https://gyazo.com/390ba9ffdd91012b5c3ad178ea1aa109

https://gyazo.com/b191e504d50ab0c6db28e32d4b5c5bf2

so according to the theorem

in b^k, k = 4

but why do they do 6 choose 4

is it because 6 choose 4 = 6 choose 2?

https://gyazo.com/d62e1062c198519e766f267a1632f502

they do it in here

[weary tiger]

yea

6 choose 4 = 6 choose 2

so either should be fine

<@&286206848099549185>

[faint narwhal]

Yes that's correct

[weary tiger]

hey

do you mind helping me?

@faint narwhal

[faint narwhal]

uh yeah sure im playing sekiro so might be slow to respond, but just ask in a question channel

[weary tiger]

oh i think I got it now. thank you though

[twilit wadi]

can anybody explain this

x+yz = (x+y)(x+z) distributive law

[craggy gale]

it seems some stuff is missing

[stray reef]

is this boolean algebra

[quaint river]

yes

it is

[stray reef]

uh huh

might be easier to express that in logical notation then

x || (y && z) == (x || y) && (x || z)

well

logical notation

C-style

[twilit wadi]

super @stray reef

@stray reef wonderful explanation

thanks

[modest zealot]

question, how come its implication, and not conjunction, the bottom

[weary tiger]

$\forall x( S(x) \wedge J(x))$ means that for every person, that person is a student and has taken a course in Java.

[weary tiger]

so it's false, since not all people are students

[echo lintel]

https://gyazo.com/d3f39cac390db6e43ecd62f9bfed3d2f

what does distinguishable and indistinguishable balls mean in this chart?

[weary tiger]

distinguishable: balls with different labels on them

or different colours or whatever

[echo lintel]

assuming the other is balls w no label

[weary tiger]

yes

[echo lintel]

tyvm

[weary tiger]

np

[wispy flicker]

If A is a set {1, 2} and R is a binary relation {(1,2)}

how can you tell if R is transitive if there are only two elements?

Does it default to true or false... or something else?

Thought just occured to me.

[faint narwhal]

When you consider transitivity, the three elements you choose to look at are not necessarily distinct.

[wispy flicker]

Hm.

R only has (1,2) though.

Has (1,2) but not (1,1) or (2,2) so it's not transitive?

Makes sense I suppose, if that is correct.

[azure lichen]

it’s vacuosly transitive

there is simply no triple x,y,z such that x~y and y~z

so the transitivity condition holds for all such triples (of which there are none)

making it transitive

[wispy flicker]

Ah, okay. Thanks.

Is it also antisymmetric then? Considering:

If R has (1,2) and (2,1) --> 2 = 1

[azure lichen]

I don’t think it’s antisemitic, no

[wispy flicker]

Since first condition is false, isn't it true?

rip my spelling rn

typos

antisymmetric*

fixed now

lol, apologies

[fallen flicker]

its because if you take x y and z in {1,2} you will have x=y or y=z or x=z

so ~ will be transitive

[azure lichen]

what?

[wispy flicker]

I mean to say antisymmetric.

If R has (1,2) and (2,1) --> 2 = 1

Since this is F --> F doesn't it become true?

[azure lichen]

yes, that sounds right. my “what” wasn’t directed at you

I don’t see how key’s argument is in any way… an argument

how does transitivity follow from that?

the relation R = {(1,2), (2,1)} is not transitive