discrete-math

[obtuse lance]

what's the question?

are you just trying to negate the statement or are you wanting to prove the statement

[weary tiger]

prove it

by contradiction

[obtuse lance]

yeah, sounds like the right path

I'd suppose that r=m+nx is rational

then solve for x and get a contradiction

[weary tiger]

okay thanks!

[obtuse lance]

yup you're welcome

[proud zenith]

Hey guys, could you please explain to me the Transitivity Ratio? maybe with example? on two teams?

[stray reef]

the what now?

[proud zenith]

??

[stray reef]

can't explain something if you don't tell us the definition or where you saw that term :p

[proud zenith]

Uhmm, there is that term called Transitivity, isn't that a known term?

I studied reflex ratio, symmetrical ratio, anti symmetrical ratio, and Transitivity, maybe that rings a bell?

[obtuse lance]

never heard of any of these as ratios

[stray reef]

^

though looking it up, it looks like the transitivity ratio is simply the percentage (or fraction) of instances in which the transitive law holds for your graph

with the transitive property holding iff the transitivity ratio is 1

[proud zenith]

Oh okay, thanks man!

[peak seal]

Hey all. I joined this server a week back; been a lurker since. I’m a 2nd yr undergrad student. I just started an online combinatorics course. Was wondering if I could get some assistance/input with the pigeonhole principle.
The theorem(or principle) states that if we have to put N+1 or more pigeons into n pigeonholes, then there exists at least one pigeonhole that has 2 or more pigeons.
I was thinking about some possible examples of this process of putting pigeons into holes in my head. So for instance, what if we had some 5 holes and let’s say 8 pigeons. Then one way to do this is to put 2 pigeons for 3 holes each, and the rest we can put one pigeon for one hole. I know this sounds silly but can we just shove all 8 pigeons into one hole, and have like 4 empty pigeonholes left? Or 3 pigeons for a hole, 3 for another, 2 for another, and hence have 2 empty holes.What I’m trying to say is that can we have empty pigeonholes?

[obtuse lance]

yeah you can

it doesn't really matter so much, so long as they go somewhere

[peak seal]

Yeah I thought so as well.. just wanted to have some clarification, thank you!

[obtuse lance]

but if someone's trying to spread them out as much as possible to minimize the maximum number in each hole, it would be kind of a poor choice on their end

yeah you're welcome

[peak seal]

Hmm yeah.. makes sense 👍🏼

[simple vale]

I have this graph and I have an exercise which asks if this is a planar graph. I know that if |L| ≤ 3*|V| - 6 (Where L is the set of the edges and V is the set of the vertices) then the graph is planar, but the graph in the photo (or at least the way in which is represented) doesn't match the definition of planar graph. So, it's or it isn't a planar graph?

[proven shard]

This is the complete graph on 5 verticies

Its definitely not planar

(But you can embed it on a torus )

[austere swan]

In class, we've seen a proof that a planar graph is 5-colourable, but the end part of the proof was very handwavey, and I was wondering if anyone had a more rigorous proof.

It basically went like this: By induction on the number of vertices, in the induction step, assume WLOG that G is connected (Otherwise we can look at each connected component separately). There is a vertex of degree at most 5, if the degree of the vertex is <5, then we've seen how to handle this.

Let G' be the graph obtained by deleting this vertex, then G' is 5-colourable. Let v_i, i=1,2,3,4,5 be the vertices connected to our edge v, then if two are of the same colour, we again know how to handle this and so we are done, so assume they all have different colours.

We consider two edges, WLOG v_1,v_2 with colours 1,2, and look at their connected components after deleting all vertices with colours 3,4,5

In the case where the connected components are disjoint, I'm fine with the proof, the problem is when the connected components are identical

the argument basically boils down to the fact that there cannot be a path of alternating colours between every 2 vertices v_i,v_j because of planarity, so there must be a pair where the connected components in those 2 colours are disjoint

but the prof basically showed this by example and not very rigorously which is frustrating

[distant pollen]

shouldnt the only element changing here be 5 to 10?

{2,4,10,11,12,13,14}

[warped pecan]

How can I find the number of lattice paths from 0,0 to n,n?

[stray reef]

what size is the lattice and what moves are allowed?

[warped pecan]

right and up

basically the ones that don’t cross x=y

You can touch it but not cross

@stray reef

[stray reef]

i think you might want to look into something called the Catalan numbers

[warped pecan]

Yeah I saw that but that hasn’t been taught to us

So we are supposed to figure it out intuitively and I’m not sure how to do that

[snow sleet]

Well are you trying to find the number of Shortest paths?

@warped pecan

If so @warped pecan my hint would be to write what one path looks like (and rearrange the letters in that ‘word’).

[snow sleet]

@warped pecan are you there? Or can we open this channel back up for other questions?

[austere swan]

i'm still waiting for an answer haha

[warped pecan]

@snow sleet I figured it out thanks!

[snow sleet]

You’re welcome! @warped pecan

[snow sleet]

Did you by chance get the answer being: $\binom{2n}{n}$ @warped pecan ?

[vital dew]

logician_pdx
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[snow sleet]

Sorry, I saw your question, but graph theory is not my strong suit.

<@&286206848099549185> Would someone be able to help @austere swan with the graph theory question?

[austere swan]

Thanks man

I figured you'd have answered if you knew

[snow sleet]

You're welcome!

[tranquil flint]

hey guys any insight to prove a bipartite graph on n=10 vertices and 15 edges whose vertices all have degree 3 is not planar

i assumed planar to get f = 7 using eulers

and 2m >= 4f for bipartite graphs as they do not contain odd cycles

[tranquil flint]

is #combinatorial-structures a better place to ask this instead btw?

[snow sleet]

I would say yes. Because graph theory and combinatorics have much overlap @tranquil flint

You might also try the proofs-and-logic channel since you're asking about a proof

[tranquil flint]

okk thank you

can i repeat the question

or is that not allowed

[snow sleet]

You're welcome!

I think you can repeat it...just maybe also say which channels you've asked your question in and state something like "I'm not sure which channel this is supposed to fall under, and I've asked this here, here, and here. I was wondering if anyone could answer my question regarding bipartite graphs....my question is ...." @tranquil flint That's just my recommendation, totally up to you tho.

[snow sleet]

But, @tranquil flint , you're not technically wrong posting your graph theory question here since graph theory falls under discrete math...it's just that graph theory isn't always covered in a discrete math course.

[zinc marsh]

Hi I have a question regarding flow networks. If I have a flow network G with some positive flow f. Now I construct G' from G by removing all the edges on which the flow = 0. Let s be source, and t be sink. Consider S the set of vertices reached from s in the graph G'.

isn't t always in S?

[latent comet]

I anyone able to help me with the construction on a discrete time markov chain transition matrix

[tranquil flint]

Anyone comfortable with Brooks Theorem?

[deft dock]

i have no clue how to do the third one

wait actually

i think i figured it out

but im not sure

[errant bear]

[deft dock]

idk how to use index

also how do u simplify this?

i think im being dumb

[errant bear]

well, theres 2 copies of 2^(k+1)

[deft dock]

okay so 2(2^(k+1))

but then what

[errant bear]

what is 2(2)

what is 2(2^2)

what is 2(2^n)

@deft dock

[deft dock]

4

[deft dock]

8

[deft dock]

uh

4^n?

[errant bear]

try an example

[deft dock]

wait no

no workie

um

no clue

becuase n =2

then 8

but

[errant bear]

what is 8=

[deft dock]

how 2(2^n) = something = 8?

[deft dock]

2^3

[errant bear]

so 2(2^2) = 2^3

[deft dock]

[errant bear]

..

[deft dock]

oh wait

do you just

add the exponents?

[errant bear]

[deft dock]

but

then shouldnt it be 2k + 2?

[errant bear]

?

nyani

[deft dock]

^^

[errant bear]

oh

[deft dock]

shouldnt that be 2k + 2?

[errant bear]

no

[errant bear]

or do u mean

[deft dock]

like 2^2k + 2

[errant bear]

are u missing a ^

[deft dock]

yeah yeha

[errant bear]

yes

[deft dock]

but its not doe

calculator says 2^k+2

and the proof also works with that value

so im confusion

[errant bear]

i misread

[errant bear]

i thougt u meant 2^(k+2)

[deft dock]

oh no

[errant bear]

not thaf whole expression as the exponent

[deft dock]

no no that whole thing as exponent

[errant bear]

so

treat k+1 as n for now

we have 2(2^n) like earlier

= 2^(n+1)

now sub back in k+1 for n

if it wasnt clear

[deft dock]

hold on what

[deft dock]

???????

[errant bear]

ok hold on

i thought you said that you recognized 2(2^n)=2^(n+1)

did you not

x^n is x multiplied by itself n times, correct?

[deft dock]

yes

[errant bear]

so if we have x times x^n its x multiplied by itself n times, multiplied by x again

[deft dock]

mhm

[errant bear]

which is x multiplied by itself n+1 times

[deft dock]

okay what

[errant bear]

hurb

[deft dock]

how

how does x(x^n) = x^n+1

OHHHHHHHHHH

2(2^2) = 2^3

?

[errant bear]

yes this was said earlier

[deft dock]

okay oaky

[errant bear]

its the same as x^a • x^b = x^(a + b)

[deft dock]

ohhhhhhhhh

so then

why is it not 2^2k+2

[errant bear]

we are just adding 1 to the exponent

it might be easier to let k+1 = n

either way, we have 2(2^(k+1)) right

[deft dock]

yes

[errant bear]

so using our rule, this is equal to 2^((k+1) + 1)

right

[deft dock]

and then

ohhhhhhhh

[deft dock]

so this is the rule

[errant bear]

yes

[deft dock]

ohhhhhh okay i never knew that rule exited

at least explicitly

ah okay

[errant bear]

well

ur missing parenthesis

[deft dock]

uh

like?

oh wairt

x(x^n) = x^(n+1).

[errant bear]

yes

[deft dock]

kk

[deft dock]

i was wondering if someone could check my homework?

its 6 questions, mostly mathematical induction

with a few summation and product notation questions

[errant bear]

no its illegal unfortunately

[deft dock]

bruh

okay nvm ill just check

wait can you at least check these ones

[red nest]

The denominator on the first one should be k^2+4 i think

[deft dock]

ohhhhhhhh yes

wait i think i didnt something wrong for this step?

because for all the other ones LHS and RHS equal

or should it say 2^0 = 1?

for the LHS

[obtuse lance]

yeah

hopefully 0 is not equal to 1 lol

[deft dock]

yeah lol thanks

[deft dock]

also should this say Their difference is also divisible by 8 instead?

oh shit sorry for the ping

wait actually no

nvm

[obtuse lance]

lol

does that mean you got it after all?

[simple token]

Heya! I hope this is the right channel to ask for this.
I kinda just need someone to check if my logic is correct trying to proof the following:

We need to show that

Proof:

So what I am not sure about is, that one can assume that e < m aswell as simply saying that bcs of this, there wont be a case of a^x mod m = a^y mod m .
(Hope writing it in latex makes it easier to read)

And if one cant just say that (or its even wrong), how would we proof it / whats a better way to approach this?

[terse rune]

I can't see the point of your proof. So I can only suggest to try to prove by contradiction. First, https://en.wikipedia.org/wiki/Euler's_theorem. Then show that there exists inverse of a. Apply the existence of inverse to #discrete-math message and deduce contradiction to 1 <= x < y < e.

[terse rune]

The Euler's theorem is regarding your redundant assumptions about exponents of >= m.

[simple token]

Thanks for the reply! The idea was that since Id say that x and y are < m (since e < m , but obv assuming this, cant show myself), a^x mod m and a^y mod m are different (if x,y would be <= m, this wouldnt apply anymore) but might aswell had some mistake thinking about it

ah ic

that link helps, will take a look at it in a bit, thank you

[terse rune]

Just take as granted at first that all the considered exponents are < m (see Euler's theorem). The coprime property is necessary. Still, you don't use it.

[simple token]

ic ic. thanks for the hints already. will take a further look once home again

[civic horizon]

You dont need eulers theorem, simply the fact that a is invertible suffices

As a further hint: look at a^{y-x}

[simple token]

With invertible u mean that
$x \cdot a \equiv 1 (mod m)$
So for, lets say, a = 2 and m = 9 it would be x = 5

[vital dew]

Ollowain

[civic horizon]

Yes

[simple token]

Okay, so because a and m are coprimes we can say that the inverse exists due to the gcd(a,n) == 1 (at least our script reads like that)
Not quite sure how to use this together with a^(y-x) however

[civic horizon]

Assume for contradiction that a^x = a^y mod n

Now does the inverse of a^x exist?

[simple token]

well yes, because a and m are still coprimes therefor the inverse exists

[civic horizon]

And what is the inverse of a^x

If we denote the inverse of a as a^(-1)

[simple token]

practially the number x in Z so that x * a = 1 (mod m)
so a^(-1) would be this x

Might be that for 1 <= x < y < e the inverse for a^x and a^y are different.
but even if thats the case id not be sure how to use that in the contradiction, as it seems similar to my initial thought saying that the modulo for 1 <= x < y < e is always different for a^x and a^y

[snow sleet]

okay, so let me rewrite the statement you're trying to prove and could you please confirm whether this is the statement you're trying prove?

[simple token]

sure

[snow sleet]

kk thanks. So you're trying to show the following (I'll LaTeX it)

[civic horizon]

showing that the inverse of a^x is equal to a^(-x) isnt too bad

then multiplying both sides of the congruence by a^(-x) yields that a^(y-x) = 1 mod n

[snow sleet]

Let $a>0$ and $m>2$ be relatively prime integers. Then $a^x\not\equiv a^y\pmod{m}$ for all distinct $x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)-1}$.

look right? @simple token

[vital dew]

logician_pdx
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[simple token]

not really sure what the ord_m(a) stands for, basically x, y for 1 <= x < y < e

[simple token]

oh thanks, yea that works then

[snow sleet]

So I'd use a proof by contradiction for this theorem you're trying to prove

[simple token]

yea, basically assuming that the statement. so a^x = a^y mod m is true and we work until theres a contradiction
(sry, not used to the english terms for stuff like that)

[snow sleet]

yeah

it's all good

so you can assume WLOG that x>y for some x and y in the set

then you know m divides (a^x-a^y)=a^y(a^k-1) for some integer k>0. This implies m|(a^k-1) for such k

[simple token]

how come we can assume that when 1 <= x < y < e
I assume WLOG = without loss of generality, according to google lol

[snow sleet]

are you asking why we can assume x>y>=1?

for some x,y in that set

[simple token]

well, kinda I guess. since we try to show the statement for all 1 <= x < y < e
I think we can because we assume a^x = a^y (mod m) and arent trying to show a^x =!= a^y (mod m)

[snow sleet]

right it's because of symmetry

[simple token]

aight that makes sense

[snow sleet]

so now we that we're gonna give a proof by contradiction, where do we go from here?

[simple token]

we pretty much try to show that our assumption is invalid and therefor showing that the original statement is therefor valid

[snow sleet]

right

but how

[simple token]

so we need a contradiction for a^x = a^y (mod m) which would be if a^x mod m != a^y (mod m) or a^x != a^y + x * m

[snow sleet]

well there could be other types of contradictions

Here's a start, (thought not a completed proof):

so where do we go from here?

and I think we actually want to prove this instead:

Let $a>0$ and $m>2$ be relatively prime integers. Then $a^x\not\equiv a^y\pmod{m}$ for all distinct $x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$.

[vital dew]

logician_pdx

[snow sleet]

proving this statement will prove the statement you're trying to prove

So our proof so far is

\begin{proof}
Let $a>0$ and $m>2$ be relatively prime integers. For the sake of contradiction, suppose $a^x\equiv a^y\pmod{m}$ for some distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$. Without loss of generality, assume $x=y+k>y$ for some integer $k>0$. Then $m|a^x-a^y=a^y(a^k-1)$. Since $(a^k,m)=1$, this implies $m|a^k-1$.
\end{proof}

[vital dew]

logician_pdx

[snow sleet]

So now what?

my hint would be to think about k

Why is $m|a^k-1$ a contradiction?

[vital dew]

logician_pdx

[simple token]

(saved what i just wrote)
kinda lost on this
i assume because a^x = a^y when m | (a-b) and we can use m | a^k - 1 as a contradiction

[snow sleet]

what do you mean $m|a-b$? where is this $b$ coming from

?

[vital dew]

logician_pdx

[simple token]

ah mb

i mean

$m | (a^x - a^y)$ would show that $a^x = a^y$ mod m

[vital dew]

Ollowain

[snow sleet]

Right but we're assuming that already

because this is a proof by contradiction

okay so let's start with my partial proof

Here it is: Remember It's not yet complete

\begin{proof}
Let $a>0$ and $m>2$ be relatively prime integers. For the sake of contradiction, suppose $a^x\equiv a^y\pmod{m}$ for some distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$. Without loss of generality, assume $x=y+k>y$ for some integer $k>0$. Then $m|a^x-a^y=a^y(a^k-1)$. Since $(a^y,m)=1$, this implies $m|a^k-1$.
\end{proof}

Since $m|a^k-1$, $\operatorname{ord}_m(a)|k$, right?

[vital dew]

logician_pdx

[snow sleet]

@simple token

[vital dew]

logician_pdx

[simple token]

yea that works out. so e (ord_m(a)) is dividable by k

[snow sleet]

no

k is divisible by it

i.e., (ord_m(a)) divides k

make sense so far?

[simple token]

oh sorry, i meant that

[snow sleet]

kk awesome

so let's show (ord_m(a)) doesn't divide k

this will give a contradiction

right?

[simple token]

yea

[snow sleet]

kk so isn't it true that k=|x-y|?

[simple token]

so since were chosing a k for ..

^ ye that

[snow sleet]

kk

well what is the largest possible value of |x-y|

?

and what is the smallest possible value of |x-y|?

[simple token]

well, since y >= 1 and x < ord_m(a)
it would be ord_m(a) - 2
(i.e ord_m(a) = 10 ,x = 9, y = 1, k = 8)

[snow sleet]

um what?

[simple token]

largest possible k

just made up numbers in the example

[snow sleet]

I'm asking you to find $u,v\in\mathbb N$ such that $u\leq|x-y|=k<v$.

remember, x and y are distinct

[vital dew]

logician_pdx

[simple token]

i might just be confused, but yea x and y are distinct.
the largest possible value of x - y would be when x is the max value (ord_m(a)-1) and y = 1 would would lead to ord_m(a)-2 = k

thats what i meant with the answer to the largest possible k

[snow sleet]

if x and y live in {1,2,3,...,ord_m(a)}, what is |x-y| bounded by?

[snow sleet]

remember we're proving this instead

I'll give you a hint

$1\leq x-y=k$

[vital dew]

logician_pdx

[snow sleet]

$k$ is less than what?

[vital dew]

logician_pdx

[simple token]

well, less than x

[snow sleet]

not necessarily

$k$ is the positive difference between $x$ and $y$

[vital dew]

logician_pdx

[snow sleet]

Since x and y live in {1,2,3,...,ord_m(a)}, what is the largest possible value of |x-y|=k?

literally choose the two elements in the set that are the furthest apart from each other

[simple token]

well, if x would be ord_m(a) and y = 1

but shouldnt it be 1 to ord_m(a)-1

[snow sleet]

right

good

So can ord_m(a) divide k?

[simple token]

^ thats why i meant largest k would be ord_m(a) - 2 earlier
but no, it cannot divide if its the largest possible

[snow sleet]

okay awesome. Don't forget the statement I suggested we prove. For the statement I suggested we prove, the largest possible value of k is ord_m(a) - 1, not ord_m(a) - 2.

So now we've reached a contradiction, right?

We said ord_m(a) divide k, but we just showed that can't be true

This contradiction proves the statement (mine and yours)

[simple token]

yep, so the contradiction statement cant be true which proves my statement

[snow sleet]

well I think you're on the right track, but those aren't the correct words

The contradiction we reached proves my statement, which in turn proves your statement

So here's what the proof now looks like

We show Let $a>0$ and $m>2$ be relatively prime integers. Then $a^x\not\equiv a^y\pmod{m}$ for all distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$.

[vital dew]

logician_pdx

[snow sleet]

\begin{proof}
Let $a>0$ and $m>2$ be relatively prime integers. For the sake of contradiction, suppose $a^x\equiv a^y\pmod{m}$ for some distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$. Without loss of generality, assume $x=y+k>y$ for some integer $k>0$. Then $m|a^x-a^y=a^y(a^k-1)$. Since $(a^y,m)=1$, this implies $m|a^k-1$. Thus $\operatorname{ord}_m(a)|k$. This is a contradiction since the Division Algorithm guarantees $\operatorname{ord}_m(a)\nmid k$ since $1\leq k=|x-y|<\operatorname{ord}_m(a)$. This contradiction proves the theorem.
\end{proof}

[simple token]

yea, ive never spoke in english about something like that. but pretty much what i meant

[vital dew]

logician_pdx

[simple token]

so, i generally get the idea of that. Its just that I personally have no clue how to connect it and formulate as a proof

[snow sleet]

ah gotcha.

Yeah these can be tricky to come up with, and there are likely other ways to prove this

[simple token]

But one last question which I am not sure u answered already, but u mention here for ord_m(a)
Distinct x, y in (1,2,3...ord_m(a)) would mean that x > y is possible, no? But the actual thing that wanted to be proven was about 1 < x < y < ord_m(a)
(perhaps this was just a typo in the latex here)

thats what i meant earlier where I was confused about the selection of x / y in the set

[snow sleet]

well if x and y are distinct, then x>y is possible, yes.

so we've covered that case

and also if 1 < x < y < ord_m(a), x and y are still in our set and so the result still holds

[simple token]

so for x = y + k > y would work the same, since x cant be > y
ah nvm, u mentioned that already with symmetry earlier

[snow sleet]

Yes so @simple token :

Let $a>0$ and $m>2$ be relatively prime integers. Then $a^x\not\equiv a^y\pmod{m}$ for all distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)}$. proves: Let $a>0$ and $m>2$ be relatively prime integers. Then $a^x\not\equiv a^y\pmod{m}$ for all distinct $x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)-1}$

[vital dew]

logician_pdx

[snow sleet]

does that make sense?

@simple token

[simple token]

not really tbh, except I didnt see / read something.

[snow sleet]

what you mean?

[simple token]

ah nvm mb, if i read it correctly it says that the statement for x,y in {1,2,3,... ord_m(a)} proves that the same thing just with x ,y in {1,2,3,... ord_m(a) - 1}
so basically because the 1st is already proven, the 2nd, which is in the 1st set is proven aswell

[snow sleet]

yes

exactly

and we've already covered the x>y case and the y<x case since we assumed x and y were distinct

[simple token]

okay yea that makes sense now

[snow sleet]

dope

So for your proof, I'd write this:

\begin{proof}
Let $a>0$ and $m>2$ be relatively prime integers. For the sake of contradiction, suppose $a^x\equiv a^y\pmod{m}$ for some distinct
$x,y\in{1,2,3,\dots,\operatorname{ord}_m(a)-1}$. Without loss of generality, assume $x=y+k>y$ for some integer $k>0$. Then $m|a^x-a^y=a^y(a^k-1)$. Since $(a^y,m)=1$, this implies $m|a^k-1$. Thus $\operatorname{ord}_m(a)|k$. This is a contradiction since the Division Algorithm guarantees $\operatorname{ord}_m(a)\nmid k$ since $1\leq k=|x-y|<\operatorname{ord}_m(a)-1$. This contradiction proves the theorem.
\end{proof}

[vital dew]

logician_pdx

[snow sleet]

@simple token

cuz you wanted to prove for 1<=y<x<ord_m(a)

[simple token]

exactly yea. the contradiction part makes sense now, prolly wouldnt have gotten that myself however

[snow sleet]

I mean, that's what this server is for (to help with a little guidance)

[simple token]

this is perhaps a little off topic, but do u have some good sources for stuff like that? as our script isnt really, uhm, great.

[simple token]

yea, thanks a lot <3 hope my tired ass hasnt been too annoying / stupid. ill try to go over it slowly tmrw again and perhaps do the same thing alone again w/o the preset.

[snow sleet]

you mean for like how to write proofs?

[snow sleet]

You've been a pleasure to work with.

[simple token]

i doubt

[simple token]

well, kinda yea. Also the theoretical knowledge for the implications / conversions (guess thats not the correct word)

[snow sleet]

oh that just comes with practice

[simple token]

ive generally been scraping some online sources trying to find stuff / math exchange, but couldnt find anything like a source where most of the stuff is gathered

[snow sleet]

sometimes reading other proofs (valid and sufficient proofs) can help too

[simple token]

yea i guess

well. thanks a lot again. if u dont mind could I ping u if ill have some follow up questions tmrw after going over it again? (obv keeping timezones in mind)

[snow sleet]

You're welcome! Sure you can dm me if you'd like

[simple token]

ty :) hope youre gonna enjoy the rest of your day / evening. gn

[snow sleet]

You're welcome. Thanks, I hope you're enjoy your day/night too.

[snow sleet]

This channel is open for questions

[cold summit]

Hi, I've been trying to prove this statement : let E be an infinite set, prove that there exists a one to one correspondence between ExE and E. There is an easy injection E -> ExE, but I can't figure an ExE -> E injection. Also apparently the axiom of choice is required for solving this exercise. If anyone has an idea, thanks

[rigid tartan]

this is the first paragraph of a proof from Enderton's Elements of Set Theory.

Hopefully that hint is enough to get you off the ground

[cerulean wind]

is there a way to do this with writing E x E as the union of {e} x E for all e in E?

something mirroring the proof that the countable union of countable sets is countable?

[rigid tartan]

I think that's a good idea. I don't know if it works.

[cerulean wind]

idk too much about cardinals, but just on a limb, is it true that if k is some infinite cardinal and there is a collection of at most k sets each with cardinality k, then the union is also of cardinality k?

[rigid tartan]

Yeah, that's not too different than what we're trying to show here

[tranquil flint]

How do you count # of lattice paths from (0,0) to (n,n) that do not pass thru points A, B or C?

Is it: total # of paths from start to finish - total paths from start to finish that pass thru A - total paths from start to finish that pass thru B - total paths from start to finish that pass thru C + total paths that pass thru A and B + total paths that pass thru A+C + total paths that pass thru B+C - total paths that pass thru A+B+C?

[snow sleet]

I would count the complement and subtract from the total @tranquil flint

[tranquil flint]

is what i wrote correct?

to not overcount

[snow sleet]

yeah looks good. You've essentially made use of PIE @tranquil flint

nice!

[tranquil flint]

Thank you!

[snow sleet]

You're welcome!

This channel is open for questions

[snow sleet]

Well you've already kind of shown half of what you need to show since you've shown $f:E\rightarrowE\times E$ is injective. \textit{All you need to do now is show $f$ is surjective}. I'm not sure exactly how that'd be done, but I don't think you need to find an injection $g:E\times E\rightarrow E$.

[vital dew]

logician_pdx
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[red nest]

The obvious injection from E to ExE is never surjective if E has more than two elements

[snow sleet]

Ah, I was thinking he had found a nontrivial but relatively easy injection

[narrow trench]

I mean, Tarski's theorem about choice says that this property of infinite sets implies AC

By contrapositive, it isn't true if you don't assume AC

[muted bane]

Hello everyone, quick question: are ∃x(S(x)∧∀y (F(y)→A(x,y))) and ∃x∀y(S(x)∧ F(y)→A(x,y)) equivalent? (it's just the scope of the universal quantifier for y I'm not sure if it has the same meaning if I put it at the beginning)

[narrow trench]

Okay, after revising my example, this isn't true

Take S(x)=x≥0, F(y)=y≤0, A(x,y)=x>y

The first is saying "there exists a nonnegative number larger than any nonpositive number". 1 works, it's true

Okay nevermind that still doesn't work

Perhaps it is true

[narrow trench]

Do you have any information over what sets x and y range?

[muted bane]

Yes sorry that would have been helpful. We are assuming that the predicate S(x) is "x is a student", F(x) is "x is a faculty member" and A(x,y) is "x has asked y a question", where the domain for x and y consists of all people associated with your school. I need to use nested quantifiers to express "some student has asked every faculty member a question". The proposed solution is ∃x(S(x)∧∀y (F(y)→A(x,y))) but I came up with ∃x∀y(S(x)∧ F(y)→A(x,y)) so I couldn't really get my head around the difference.

[narrow trench]

It can cause some issues if say, the faculty is empty

Then the solution you came up holds as long as you can find any person

"There is a person that (is a student and has asked every faculty member a question), since there are no faculty members"

[red nest]

These statements are equivalent

[red nest]

I don’t see any issues even when the set of faculty is empty. Both statements are still equivalent and are the same and correspond to what they asked him

[narrow trench]

Feels iffy, but oh well ¯_(ツ)_/¯

[muted bane]

Thank you both guys, I think I'll stick with @red nest even if one of the sets is null the equivalence wouldn't be impacted

[marble pivot]

Is it true that if $m,n$ are coprime, then every element of $\bZ/m\bZ$ contains a multiple of $n$?

[vital dew]

abs_0

[unreal stump]

Yes

Do you still want a proof?(Hint:Bezout)

@marble pivot

[marble pivot]

Nah nah nah

[marble pivot]

Thanks tho

[errant bear]

bzoo

[gentle nebula]

Assuming axiom of choice there is a well ordering on E. Conclude from there

[last timber]

he may not yet have proved well ordering tho

[gentle nebula]

proof is simple tho

To well order S, let f be a choice function on P(S), define s_α=f(S-{s_β|β<α}) and we're done

[past burrow]

how is sb { S

[hardy viper]

@past burrow the recursive steps says that you can connect strands of RNA together

it's just an easy way to go from {A,C,U,G} to all possible strands of those letters

[marble pivot]

``It is pretty clear that if $a$ and $n$ have a common prime factor, then there is no hope of finding a reciprocal element $b$ so that $ab = 1$ in $\bZ_n$''

[vital dew]

abs_0

[marble pivot]

^ This doesn't feel obvious at all for some reason

how do I intuit this?

[zenith palm]

If we think about $ab$ modulo $n$, the congruence implies that for nonnegative $k$, $$ab = nk+1 \implies ab-nk=1.$$ Suppose $d= \gcd(a, n) > 1$, which is given since $a$ and $n$ have a common prime factor, this would imply the LHS is divisible by $d$, while the RHS is not divisible by $d$, implying that there does not exist a $b$ that satisfies our diophantine equation.

[vital dew]

Green4Applez

[zenith palm]

@marble pivot

does that make sense?

[tranquil flint]

How do I find # of solutions to:
x+y+z+w = 20

where 9>=x,y,z>=0 and 9>=w>=1

Is generating functions a shortcut? im not sure how to use them

[stray reef]

is there any reason in particular why you wrote the bounds backwards

i.e. 9 ≥ w ≥ 1 as opposed to 1 ≤ w ≤ 9

anyway, you could instead count the solutions to x + y + z + w' = 19 with x, y, z, w' ≥ 0; x, y, z ≤ 9; w' ≤ 8

which can be done with generating functions if desired

or via some applications of inclusion-exclusion

[tranquil flint]

Oh no no reason

[tranquil flint]

yess i was thinking this

for the generating function (i didnt learn them yet fully but would rather use them than PIE)

since they seem shortcut level easy

is it just the coefficient of

4 sums

[stray reef]

coefficient of $t^{19}$ in $(1 + t + \dots + t^9)^3(1 + t + \dots + t^8)$

[vital dew]

Ann

[tranquil flint]

OOoooh ok

thank you sm

period

Do we have to use taylor series to reduce that

🤔

[stray reef]

yes and no

you can write it as $\frac{(1-t^{10})^3(1 - t^9)}{(1-t)^4}$

[vital dew]

Ann

[stray reef]

so really it's 1/(1-t)^4 whose taylor series you would need

and even that you can get from differentiating 1/(1-t) thrice

[tranquil flint]

wait can i ask how u got this

[stray reef]

1 + t + ... + t^9 = (1 - t^10)/(1-t)

[tranquil flint]

omg

Wow

1/(1-t) = 1 + t + t^2 ...

taking deriv 3x

is

2*3/(1-t)^4 = 3! + 4! t + 5! t^2 + ...

i think

[stray reef]

it'll be $\frac{6}{(1-t)^4} = \sum_{n=0}^{\infty} (n+3)(n+2)(n+1)x^n$

[vital dew]

Ann

[tranquil flint]

o yea i missed one term

ok period

$\frac{1}{(1-t)^4} = \frac{1/6}\sum_{n=0}^{\infty} (n+3)(n+2)(n+1)t^n$

LMFAO

WOOPS

$\frac{1}{(1-t)^4} = 1/6\sum_{n=0}^{\infty} (n+3)(n+2)(n+1)t^n$

$\frac{1}{6}{(1-t^{10})^3(1 - t^9)}\sum_{n=0}^{\infty} (n+3)(n+2)(n+1)t^n$

[vital dew]

Ramtin

[tranquil flint]

ok latex is cool

i have no idea how to use it properly tho just copy pasting ur text lmaoo

[last timber]

@tranquil flint you can get more information at #latex-help but in general
$ are used to enclose math.
\foo indicates latex "macro" named foo (e.g \foo)
_ for subscripts
^ for superscripts

[tranquil flint]

Hm but looking at it im not sure how much faster this is since still gotta find coeff of t^19 which doesnt seem that easy

Oh thank you so much 😄

[tawdry gorge]

Dont use \ in front of $

[carmine gust]

.

[warped pecan]

Any guidance?

[obtuse lance]

try working out small examples by hand to get a feel for it

maybe work out the even simpler case of just one power of a prime first

[marble pivot]

ohhhhhhhh you're amazing thank you. that's so cool

[zenith palm]

no problem!

[fast ledge]

can someone tell me what a cancelled mod is

[zenith palm]

are u referring to the cancellation property of mod?

[fast ledge]

yes

[zenith palm]

ah ok

Consider positive integers $n, k, u$, and $v$. Also, suppose $n$ and $k$ are coprime. From this, $$kv \equiv ku \pmod{n}$$ may be simplified by cancelling $k$ from each side. This is done by multiplying the multiplicative inverse of $k$ modulo $n$ on both sides. So, that would result in $$v \equiv u \pmod{n}.$$

[vital dew]

Green4Applez

[fast ledge]

oo gotchu

[zenith palm]

Also, an additional thing is that if $n$ and $k$ had some common divisor $d$, then the congruence could be simplified by dividing both sides of the congruence by $d$ along with dividing the modulus by $d$.

[vital dew]

Green4Applez

[fast ledge]

oo alright thank you for the help

what if its an integer lets say, k and the questions says can k be cancelled mod of n.
how do i approach this problem

[zenith palm]

So do u mean the question asks u what k mod n is?

[fast ledge]

okay let me give u problem the problem states, can 2 be cancelled mod of 2987638218

[snow sleet]

,w Expand[((Sum[x^i,{i,0,9}])^3)(Sum[x^i,{i,1,9}])]

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by logician_pdx#7452

[snow sleet]

@tranquil flint See above, the answer is the coefficient of $x^{20}$.

[vital dew]

logician_pdx

[tranquil flint]

Omg wow ok

i kinda like generating functions thank you sm

but idk how ud get that coeff

by hand

[snow sleet]

usually people don't expand those out by hand. That'd take too long

[tranquil flint]

but we reduced the

4 sums x each other to this:

https://cdn.discordapp.com/attachments/496785905474994186/865135072188563486/175067948338118656.png

for t^19

coeff of t^19

ann helped me find this

and i guess the infinite taylor polynomial

we can stop it at n = 19

since any further is not relevant

but not sure how that finds

the thing

the coeff

[snow sleet]

yeah so you still got a messy sum there that you're prolly not going to do by hand lol

even the things outside the sum, can be messy

[tranquil flint]

well its t^10xt^9

in a bunch of ways

and a bucnh of other things

idk

[snow sleet]

yeah I'd use a calculator...polynomial expansion is one of the reasons I love Mathematica

You could also make use of the binomial theorem if you really wanted and that might help, but I'm not sure it would be super helpful

[weary tiger]

kinda stuck on this question

so far I have

$D_r={(x,y)\in{\mathbb{R}\times{\mathbb{R}}}||x-y|<r}, D_s={(z,t)\in{\mathbb{R}\times{\mathbb{R}}}||z-t|<s}$ so we have that $D_{r}\circ{D_s}={(x,y)\in{\mathbb{R}\times{\mathbb{R}}}|\exists{c\in{\mathbb{R}}}(|x-c|<s|\land{|c-y|<r)}}$

[vital dew]

jswatj

[weary tiger]

but im not really sure where to go from here

must i prove that for every real number $x,y$ there exists a $c\in{\mathbb{R}}$ such that $|x-c|<s$ and $|c-y|<r$?

[vital dew]

jswatj

[cerulean wind]

i think your set needs to be $$D_r\circ D_s={(x,z)\in\mathbb{R}^2:(\exists y\in \mathbb{R}:(x,y)\in D_r\wedge (y,z)\in D_s)}$$

[vital dew]

coycoy

[weary tiger]

Yeah

[cerulean wind]

sry if it’s the same

[weary tiger]

Oh it is

the same thing

[cerulean wind]

just didn’t feel like parsing it lol

[weary tiger]

i just wrote it out

sorry

yeah so i would have to prove that for every $x,z\in{\mathbb{R}}$ there exists a $y\in{\mathbb{R}}$ such that $(x,y)\in{D_r}$ and $(y,z)\in{D_s}$

[vital dew]

jswatj

[weary tiger]

but hmm

im not sure how to go about doing that

triangle inequality says $|x-y|\leq{|x|-|y|}$ and $|y-z|\leq{|y|-|z|}$

[vital dew]

jswatj

[weary tiger]

oh wait

it just says "What is X"

but how do u prove that

🥸

[cerulean wind]

bad example

[weary tiger]

what

[cerulean wind]

but my point is, i don’t think D_r o D_s is all of R^2 like ur suggesting

[weary tiger]

Ok

I don't think it is either

but

how would i go about justifying my answer with a proof?

[cerulean wind]

this is not true. do you mean |x-y| <= |x| + |y|

[weary tiger]

oh

that is not true

you are right

[cerulean wind]

well, i don’t have an answer yet, but i think the question is asking, what set is D_r o D_s. my initial guess is that it is equal to D_{r+s}

[weary tiger]

it would be that $|x-y|\geq{||x|-|y||}$

[vital dew]

jswatj

[cerulean wind]

both of those were true

[weary tiger]

yeah this would be more helpful

if it were $D_{r+s}$ then we would have $|x-y|<r+s$ for any $x,y$ real numbers no?

[vital dew]

jswatj

[weary tiger]

wait no im trippin

sorry

there exists a positive real number r+s

[cerulean wind]

so the reason i say this is because it’s really easy to show that D_r o D_s is a subset of D_{r+s}

can you see why that’s true?

[weary tiger]

i think its because

using the 'and' statement you can manipulate one of the inequalities such that $|x-y|<r \implies |x-y|+s<r+s$ and by transitivity $|x-y|<r+s$?

[vital dew]

jswatj

[weary tiger]

so we can have $D_{r+s}$

[vital dew]

jswatj

[weary tiger]

since s>0

[cerulean wind]

that shows that D_r is a subset of D_{r+s}

[weary tiger]

Yeah but

Doesn't D_r o D_s contain D_r anyway?

oh wait no

[cerulean wind]

if (x,z) is in the composition, then there is a y so that |x-y|< r and |y-z|<s

by the triangle inequality, we have |x-z|<=|x-y|+|y-z|<r+s

so (x,z) is in D_{r+s}

[weary tiger]

wait

howd u do that

[cerulean wind]

do what lol

[weary tiger]

|x-z|<=|x-y|+|y-z|?

[cerulean wind]

that is the triangle inequality

[weary tiger]

wouldn't it be |x|+|z|?

[cerulean wind]

|x-z|=|(x-y)+(y-z)|

[weary tiger]

ohhhhh shit

[cerulean wind]

so is that part clear now?

[weary tiger]

Yeah

i can see the subset

[cerulean wind]

ok cool

[weary tiger]

wouldn't the other way around just be the same

[cerulean wind]

if we can show that D_{r+s} is a subset of the composition, then we’re done

[weary tiger]

oh

hmmm

[cerulean wind]

after some more thought, my initial guess isn’t true. it’s something else

[tranquil flint]

How many spanning subgraphs of K5 have no vertex of deg4:
K5 has 2^(5C2) spanning subgraphs
then if I label each vertex {1,2,3,4,5}

is it just PIE

case where vertex 1 has degree 4 + vertex 2 has degree 4... - vertex 1 and 2 degree 4 ... + vertex 1 and 2 and 3 degree 4 .... - vertex 1 and 2 and 3 and 4 degree 4 ... + case where vertex 1,2,3,4,5 degree 4?

Or is my logic flawed

[weary tiger]

yeahh i may just skip it and come back

[cerulean wind]

this text looks like vellmans. is it?

[weary tiger]

yes

it is vellemans

[cerulean wind]

@weary tiger
okay. so maybe i was right. let’s just suppose that |x-z| < r+s.

then i believe the set (x-r, x+r) intersect (z-s, z+s) is non-empty.

if y is in the above set, then |x-y| is less than r and |z-y| is less than s.

so we have D_{r+s} being a subset of the composition, hence D_{r+s} is equal to the composition

[weary tiger]

I think the way backwards is the same no?

[cerulean wind]

well, in what sense

[weary tiger]

so

backwards would just be that

|a-c|<r+s

because of that there exists an element b such that |a-b|<s and |b-c|<r by the triangle inequality

so we'd just have the original

i think we can move forwards and backwards using the triangle inequality

[cerulean wind]

can u explain this step

[weary tiger]

|a-c|<|a-b|+|b-c|

waiitt

[cerulean wind]

yea

[weary tiger]

cause we said that since

|a-c|<|a-b|+|b-c|<r+s

so |a-c|<r+s

can't we just reverse the steps?

bring in an element b

[cerulean wind]

no because if |x-z| < r+s, then |x-y| + |y-z| < r + sis not true for arbitrary y

[weary tiger]

isn't it just there exists a y?

[cerulean wind]

yes. but if you just know that |x-z| < r + s, then you need to choose y carefully to have |x-y| < r and |y-z| < s

and y should be in the intersection of the intervals (x-r, x+r) and (z-s, z+s)

see here #discrete-math message

[weary tiger]

Ok

but how do you know that to be true?

[cerulean wind]

well, let’s just assume that we have shown that the intersection of those two sets is non-empty first

[weary tiger]

Ok we'll assume

[cerulean wind]

pick some y in that intersection

then x-r < y < x+r so -r < y-x < r
which implies |x-y| < r

similar argumentation shows that |y-z| < s

since we also have z-s < y < z+s

so we have shown the existence of some real y such that |x-y| < r and |y-z| < s given that (x,z) is in D_{r+s} hence the ordered pair (x,z) is also in the composition

is everything clear there?

[weary tiger]

yes

Ohhhh

i see now

[cerulean wind]

awesome! all that’s left to show is that the intersection of the two intervals that we care about is non-empty

can you try that?

[hasty magnet]

hey uhhh in general is this class very time consuming? i'm taking it next semester along w/ a bunch of other stuff and im wondering what your guys' workload usually is like, ty!

[weary tiger]

If I perform right rotate on the node with element 4, do I get
4 2 1 3 8 6 5 7 9 10
as the preorder traversal?

I am a bit skeptical about this tbh

the node with element 4 became root

and its right subtree was attached to node with element 8, is that the correct approach when right rotating? In other words, node 6 and its children was attached to node 8

[desert badger]

I was solving the textbook questions of Kenneth Rosen's "Discrete math" related to quantifiers and come to this question:

[unreal stump]

f will be $\exists y\forall x !L(x,y)$

[vital dew]

Buncho Dragons

[desert badger]

My answer to number f) is different from the model answer but I think they are the same

[unreal stump]

These 2 are very very different

Your answer is "If you choose some x,you can find some y such that x doesn't love y"

That y need not remain the same person as you vary x

[desert badger]

That's what I missed

Thanks a lot

[narrow trench]

As a concrete example for why the two are different and why one is far stronger than the other

$\forall n\in\bN,\exists N\in\bN,n\le N$ : given a natural number you can find one larger than it \
$\exists N\in\bN,\forall n\in\bN,n\le N$ : there is a natural number N greater than every natural number

[vital dew]

Syst3ms

[fallow rain]

Modular exponentiation 3^65 mod 7 , (1,4 5,10,20,25) ,3^1) mod 7 = 3 , (3^2)^2 mod 7 = 4 m (3^5)^1 mod 7 = 5 , (3^5)^2 mod 7 = 6, (3^10)^2 mod 7 = 2, (3^5)^5 mod 7 =3 ,3 *4 *5 *6 *2 * 3 this isn't making sense to me the remainder is suppose to be 5 but the way I did it which I though was the right way ended up giving me the wrong answer, any help is greatly appreciated . thank you

[loud copper]

can u be clearer as to what ur doing here . i dont really get it

[loud copper]

ok i think i get what ur doing but u made a slight error

3^10 = (3^5)^2 = 4 (mod 7)

not 6

u can do this much more easily by using fermats little theorem

fermats theorem says 3^6 = 1 ( mod 7)

so 3^65 = 3^(6*10 + 5) = (3^6)^10 * 3^5 = 3^5 = 5 (mod 7)

[desert badger]

Using nested quantifiers:

[vital dew]

PeterFayez

PeterFayez

PeterFayez

[desert badger]

Is there a logical difference between both answers?

[last timber]

@desert badger yes since your model does not indicate that x != y

[desert badger]

You mean I must add $ \land x \neq y $ ?

[vital dew]

PeterFayez

[last timber]

yes

[narrow trench]

(it wouldn't be fun if the student had just chatted with themself)

[vital dew]

Commander Vimes

anyway i would prolly state this in a fashion similar to their
$$\exists x \exists y \forall z (x \ne y \land C(x,y) \land C(x,z) \implies y 😒 )$$

[last timber]

yes leave it be in utf8

[vital dew]

Commander Vimes

[last timber]

or i we want be funny we can formulate this is complicated manner lol

this is not of particular use but

[narrow trench]

Actually

[desert badger]

I am having hard times with the nested quantifiers

[vital dew]

Commander Vimes

[narrow trench]

$$\exists x, \exists y, (x \ne y \land \forall z, (C(x,z) \implies y=z))$$ suffices

[last timber]

this is really weird and unuseful formulation

[vital dew]

Syst3ms

[last timber]

no this does not

since what if C(x,z) is false for all z

@narrow trench

[narrow trench]

Right

[last timber]

but

[olive wraith]

what is the name of E shape like symbol I think use in calculus

[narrow trench]

∃ ? ∈ ?

[olive wraith]

latter one

[narrow trench]

set membership

[olive wraith]

right

and what is the name of the symbol S tail attach with back

S like fish like bird tail ?

[narrow trench]

now here i have no idea what you're talking about

this website may help https://shapecatcher.com/

[olive wraith]

noose from one end hook from one

[narrow trench]

delta

δ

that's a greek letter

also I'm guessing I got the first one wrong

If you meant ε then that's epsilon

also a greek letter

please learn greek letters, they're everywhere

[olive wraith]

no i read this in discrete math

and they mention it requires calculus

[narrow trench]

that doesn't change anything to my point though

[olive wraith]

is calculus is important for discrete math or just cover needed topics side by side

[narrow trench]

look at the channel description

most of these are only distantly related to calculus

but it can crop up in a couple of places

[olive wraith]

discrete math's is the thing that makes you better in logic building and help you to made algorithms in a nutshell a better programmer?

[narrow trench]

ehhh, programming can be applied to so many fields I doubt the advice you need all lies in one channel

[ancient herald]

was just trying my hand at the overlapping circle problem by categorizing configurations using the number of intersections, found that only one 3-circle configuration has the same number of intersections of a 2-circle configuration
so I started to look at how many ways sets can be catagorized

as a computer science student I realized that this could be useful for file systems and databases
I wonder is there a way to calculate how many ways there are to catagorize a collection of data in a file system?

[ancient herald]

More playing-arounds

[kindred kindle]

Nice drawings

Not gonna lie, not sure what you are doing

Oh

you are counting the number of ways you can have inclusions I think

So like say you have A,B,C and XY=X intersect Y

so XYZ = XY intersect Z

Is your question if you were to make a set of all combinations of types of inclusions given some sets, how many are valid?

So like for A,B,AB you have:
A in B
B in A
AB in A
AB in B
B in AB
A in AB
A in AB
B in AB

And out of those only 4 are valid

oh i forgot

A in empty and B in empty

[ancient herald]

So we calculate all possibilities and exclude invalid ones?

[kindred kindle]

Thats an easy way of doing it

[ancient herald]

ah
but does not seem to be the most efficient

[kindred kindle]

Yea doing it that way is not efficient

but we can probably come up with an algorithm that can calculate it easier

becasue if there exist any XY then we can ensure that there XY in X and XY in Y holds

and because of that there are X and Y which contain the empty set

$\emptyset \subset XY \subset X \ \emptyset \subset XY \subset Y \ \emptyset \subset X \ \emptyset \subset Y$

bruh moment

[vital dew]

celina baeza

[kindred kindle]

Also i found ambiguity in your 3-tuple on the left

You write (2,1,0) But 2 doesnt specify if its A B or B C

so if you have a function f:(s,d,t)->N where s are sets with 0 intersections, d are sets with 1 intersection (XY) and t are sets with two intersections (XYZ)

(s,d,t) isnt well defined

So you should work with another tuple that is more clear

The function in the end will resemble something using nCr function

[ancient herald]

this is exactly what got me from circle overlapping to set inclusion
I think if I can find a pattern in set inclusion I can generate most of the possible configurations, at least with a low number of circles

[kindred kindle]

I dont know about you but setting up a function seems obvious to me

So im not sure if you want a function or not

Because I would make the function f:P(X) -> N where P(X) is power set of X

And the input would be collections of sets in the power set.

So say you have X = {A,B,C} then the powerset is P(X)={empty,A,B,C,AB,BC,AC,ABC}

And if you were to input a set T ={A,C,AB} we can find the number of proper inclusions from here.

There isnt any easy way to calculate the number of proper inclusions for any random collection given as input besides counting

A simple computer program can figure it out though

[ancient herald]

I see

[kindred kindle]

The reason there isnt any quicker way besides counting is because the result heavily relies on the colleciton you give as input

The program would treat each set in the collection as a string and then parse it

[wild shoal]

I'm having issues understanding De Morgans law in this instance. In particular with regards to the movement from (¬p ∨ r ) ∨ ¬q = ¬(p ∧ ¬r) ∨ ¬q. How does the law move the negation out from p and add to r?

[kindred kindle]

You start with (p^q)->r

you negate and you get (~p or ~q) and r

you can distribute the and r

we have that (p and q) implies (p and ~r) -> ~q

By distributing we get (~p and r) or (~q and r)

So to recap (p and q)->r implies (~p and r) or (~q and r)

a hint is to use (p and q) implies (p and ~r) -> ~q

[kindred kindle]

In particular with regards to the movement from (¬p ∨ r ) ∨ ¬q = ¬(p ∧ ¬r) ∨ ¬q.
Remember that ¬(p and q) = ¬p or ¬q

So (¬p v r) v ¬q turns into ¬(p ∧ ¬r) ∨ ¬q.
Since ¬p v r=¬(¬(¬p v r)) =¬(p ∧¬r), This is because ¬(¬P) = P and P in this case is (¬p v r)

[wild shoal]

Thank you for the explanation

[tranquil flint]

Its impossible to have a lattice path go thru (2,2), (2,4) and (3,3) right?

lets say from origin to (n,n)

or even

(2,4) and (3,3)

is impossible in the same lattice path

🤔 unless im mistaken

[snow sleet]

@tranquil flint Yes, that's impossible if you've assumed shortest lattice paths from (0,0) to (n,n). This is because if you have the restriction that you're considering only the shortest number of paths from (0,0) to (n,n), then the only moves allowed are 'right' and 'up', but going from (2,4) to (3,3) implies one did the opposite of 'up'.

[tranquil flint]

tyy

yea i realized

not possible haha

[deft dock]

could someone check if these are right? got a little confused about 2a.

[desert ibex]

Looks fine

[robust mango]

<@&268886789983436800>

[fierce osprey]

can someone check my work here? I’m also curious if there’s a way to write the answer to (d) more concisely

[deft dock]

where do i go from here?

[fierce osprey]

also fyi this isn’t an actual assignment, I’m just trying to study ahead for the fall

[fierce osprey]

I haven’t really done proofs yet, but maybe you can use the fact that 6 and 18 * something will always be a multiple of 6, and the +4 and -2 must make those multiples meet/equal each other because 4+2 is also 6...

[deft dock]

idrk but is this right

[grave sluice]

@fierce osprey all in all it looks good to me, I am not sure how important that is but in (b) you are missing parentheses and the order should be T and S not S and T although obviously equivalent (same with (d) only very nitpicky things)

@deft dock r=3s-1 no?

[deft dock]

ohhhhhhhhh yes yes

other than that its right?

[grave sluice]

but otherwise its correct yes

[deft dock]

wait how would you disprove???

i dont see any videos in my module page

[grave sluice]

find an element in A thats not in B

[deft dock]

and just mention it or do i have to write a formal proof?

[grave sluice]

I mean A subset B means: forall x in A it follows that x in B
so finding x in A which isnt in B is a proof

[deft dock]

no clue how to do this either

also does this worki?

actually this

[fierce osprey]

ah thanks! I’ll keep the order in mind. Also where in (b) should there be parentheses?

and is the implies ok? I used it just to mix things up, but I’m not sure if it’s any more or less correct in this context...

[tranquil flint]

if f: A to B

is it possible for some a in A

to be undefined when inputted into f?

f(a) = undefined?

where f is surjective

[remote cosmos]

if it's surjective then by definition you have an answer

it might help to draw an image of two sets with arrows

[iron cedar]

does anyone know how to start this problem?

[olive wraith]

where is the modus ponens in this picture?

[olive wraith]

It is below freezing now therefore it is either below freezing or raining

question regarding this statement

how you eleborate this statement

where is rain in this statement

does q denotes to rain and p to freezing ?

[weary tiger]

You have P and P->Q so the modus ponens is P with P->Q to get Q

[weary tiger]

you tell me???

How would we know

what do the predicates stand for

[olive wraith]

how do we know when it is modus ponens or tollens

how does this tautology form from above modus ponenz

[weary tiger]

modus tollens is if we have $P\implies{Q}$ and $\neg{Q}$ then we have $\neg{P}$

[vital dew]

jswatj

[weary tiger]

it derives from the idea of a contrapositive

$P\implies{Q} \iff \neg{Q}\implies{\neg{P}}$

[vital dew]

jswatj

[weary tiger]

????????????

Tautologies have the form $P\lor{\neg{P}}$

[vital dew]

jswatj

[ocean island]

What's the difference between a reflexive and symmetric set?

[snow sleet]

are you talking about relations/functions?

[ocean island]

Yeah

I think I got it tho

Something can be reflexive but not necessarily symmetric.

[snow sleet]

other way around

[ocean island]

Oh

Wait

Yeah

Oops lol

[snow sleet]

if (x,x) is in the relational set, then so is (x,x)...I swapped the x's but you can't really tell I did cuz they're identical

Note that I'm not saying a reflexive relational set is a symmetric set

[ocean island]

Oh it isnt?

Would that only occur if your set is solely reflexive

[snow sleet]

consider the relation on A={1,2}. Suppose the relational set is {(1,1),(2,2),(1,2)}. This set is reflexive but isn't symmetric. It's not symmetric because (2,1) isn't there. It's reflexive because (1,1) and (2,2) are there.

[ocean island]

Oh

[snow sleet]

yeah if the relational set is only reflexive, then it is symmetric.

[ocean island]

Ohh

I read my notes wrong

🤦‍♂️

Ty

[last timber]

wym

[last timber]

again here

it is reflexive

[snow sleet]

@last timber What are you saying? I already stated that was reflexive

and I explicitly said it's not symmetric

[last timber]

i mean this

[snow sleet]

what about it?

@last timber

[last timber]

fuck internet died

or discord

anyway

i think i got your point now ll

[snow sleet]

I was talking about relational sets on a set B such that for every x in B, we have (x,x) in the relational set and nothing like (x,y), with x not equal to y, in the relational set

This channel is open for questions

[clever arch]

h-hi log

uhm

i just started discrete mathematics

and i just dont get it

@snow sleet so will u teach me the basics pls

[ocean island]

You have to ask questions, no one is going to teach you XD

For something like

[clever arch]

oh

ik but my junior said this dude @snow sleet

[ocean island]

Why is it C(19,1)*C(34,7).
Why don't you do something like 19 * 34 * 33 * 32 * 31 * 30 * 29 * 28? I think I am getting the ideas confused.

[clever arch]

he explained him pnc it seems

[clever arch]

i need to start from the basics

i missed a lot of classes duo to some irl problems

and my mam wont start from basics

my junior told me to ask @snow sleet help

so i am asking

[ocean island]

Ok

So ask questions

[ocean island]

This is me asking my own question ^_^

[clever arch]

kk

[ocean island]

$\sum_{i=0}^8\binom{19}{i}\binom{34}{8-i}=\binom{19+34}{8}$

[vital dew]

Johnson

[ocean island]

,w Sum[Binomial[19,i]*Binomial[34,8-i],{i,0,8}]-Binomial[19+34,8]

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Johnson#0366

[rancid maple]

T(n) = 4T(n/2) + n^2/lg(n)

Can anyone tell me how to solve it using Masters theorem

I am confused in this question

[deft dock]

^^ hey logician remember how you were explaining how setting the divisor equal to 2 or 4 or any even number works? why wouldnt an odd number work? or would it? like could we have done three cases and said: 3s, 3s + 1, and 3s + 2?

[snow sleet]

We could've done it with any positive integer (even or odd...other than 1) it's just that the number of cases would increase

[deft dock]

wait i just tried with 3

no work

because

if we let n = 3q

then square

so 9q^2

we cant represent that as 4k or 4k+1

[snow sleet]

what was the statement we're trying to prove again? it's been a while

[deft dock]

started with this

[snow sleet]

oh! that one

sorry I was thinking of something else

yeah you can use 2, 4, 8, or any other multiple of 4 as the divisor

[deft dock]

but not odd numbers?

and why only 4?

is it because 4k and 4k+1?

[snow sleet]

2 is nice because when you square it, you end up with a 4 and 2 reduces how many cases we have to consider down to a whopping 2

[deft dock]

very satisfying

[snow sleet]

what do you mean only four?

[deft dock]

you said any other multiple of 4 as the divisor

[snow sleet]

and it has to do with the fact that 4 is even and odd integers are well....odd

right I meant positive multiple there

that way you're guaranteed to get a 4

which you can factor out

and then get 4k or 4k+1

[deft dock]

is by using even numbers as the divisor

yes yes

makes sense

[snow sleet]

as you noticed with 3, you can't factor a 4 out

[deft dock]

but dont we gurantee it will work with any divisor?

[snow sleet]

huh?

no

that's not what the theorem is saying

the theorem is saying that the square of any integer leaves a remainder 0 or 1 after division by 4

[deft dock]

mhm

[snow sleet]

when I was talking about the divisors, I was talking about how we can partition the set of integers

[deft dock]

yeah im on the same page

but why cant we use 3?

[snow sleet]

but there's no reason why one should try 3 as the divisor cuz that just makes things really hard

[deft dock]

oh

wait so

[deft dock]

this thing

can be proved without n = dq + r?

in another way?

[snow sleet]

you can technically use 3, it's just that showing 3q^2 is divisible by 4 or of the form 4k+1 depends on knowing/showing more about q^2

[deft dock]

how do you show 9q^2 is / by 4???

[snow sleet]

well if q=0, that's certainly divisble by 4

see, how we need to know more about q?

[deft dock]

ah so we'd take a different path from factorization