#discrete-math

1 messages · Page 32 of 1

snow sleet
#

But you haven’t come up with two equivalent claims

#

U came up with one claim

#

Your two claims together make up one claim equivalent to this. However, each of your claims on their own aren't equivalent to this.

tidal tulip
snow sleet
#

Sure tbh I'm really lost now on where you're going with this

tidal tulip
#

Forget the two claims

#

This is my claim

#

And I need cases to prove this claim

#

Do I need cases at all for this proof? Can I just prove it without any cases? If not how many cases would I need

snow sleet
#

then do this^

snow sleet
#

Also note that A intersect B is precisely just A

#

since A is a subset of B

tidal tulip
#

Ok

#

It’s gonna be hard doing this in strictly set notation

snow sleet
#

set theory proofs are never fun lol

tidal tulip
#

Idek where to start

snow sleet
#

but it's good practice

tidal tulip
#

😭

snow sleet
#

that would be my outline of the proof, the rest is up to you

tidal tulip
#

What’s wrong with the cases I had?

snow sleet
tidal tulip
#

I see

snow sleet
tidal tulip
snow sleet
#

for the first one, it would be claim 1 here^. For my second assumption it would be claim 2 here^

#

because either "x is in A and therefore B" or "x is not in A but is in B" those are really the two meaningful cases

#

I'm gonna be afk for a bit getting lunch and such...but if u need any help in the meantime ping the Helpers

nocturne grove
#

i have to do this exact proof too lol

#

for this claim, I am getting stuck at $pk = qf, k,f\in\mathbb{Z}$

vital dewBOT
nocturne grove
#

They are relatively prime so I know i should do something with that from here on

#

but not sure how

tidal tulip
nocturne grove
tidal tulip
#

Didn’t you say it’s not right

snow sleet
snow sleet
#

After telling you your two claims weren't on their own equivalent to the statement with the equality, I later got the impression that you were wondering how to prove the equality. In which case, your two claims "cases" are a good way to go for a proof.

#

For example: for sets A and B....."A is a subset of B" isn't equivalent to saying "the set A equals B". However saying "A is a subset of B and B is a subset of A" is equivalent to saying "the sets A and B are equal"

tidal tulip
#

Ok so I’m gonna use these two cases to prove my claim in that case (no pun intended)

snow sleet
#

yes proving those two would prove this^

tidal tulip
snow sleet
#

Okay

#

That should be your first statement for case 1

tidal tulip
#

Can we use small a instead of x

snow sleet
#

that is a small x

#

$xX$

#

see the difference^?

tidal tulip
#

I mean a small a

#

Small “a”

snow sleet
#

no

tidal tulip
#

Ty

snow sleet
#

jk

#

Let $a\in\overline{(A-B)\cup(B-A)}$.

vital dewBOT
#

logician

snow sleet
#

There's your first statement

tidal tulip
#

Ok

snow sleet
#

So $a\notin(A-B)\cup(B-A)$.

vital dewBOT
#

logician

tidal tulip
#

Right

snow sleet
#

so $a\notin A-B$ and $a\notin B-A$.

vital dewBOT
#

logician

tidal tulip
#

Is there a set notation for “and”

snow sleet
tidal tulip
#

Ok so upside down U

snow sleet
#

$\cap$

vital dewBOT
#

logician

snow sleet
#

yup

tidal tulip
#

Ok

snow sleet
tidal tulip
#

Sure

snow sleet
#

$a\notin A-B$ implies $a\notin A$ since $A\subseteq B$.

vital dewBOT
#

logician

snow sleet
#

recall $A-B=A-(A\cap B)$.

tidal tulip
#

I’m thinking if that makes sense in my head

vital dewBOT
#

logician

tidal tulip
#

Ok yea

snow sleet
#

$A\cap B=A$ since $A\subseteq B$.

vital dewBOT
#

logician

snow sleet
tidal tulip
#

The above is part of the proof?

snow sleet
tidal tulip
#

It’s not letting me go to the message

tidal tulip
snow sleet
# vital dew **logician**

yes I mean this could really be the very first statement above both cases, but yea helpful to put it in your proof

#

okay so $a\notin B-A$, what does that mean?

vital dewBOT
#

logician

tidal tulip
# vital dew **logician**

I mean like if i place this step right after the “a is not in A - B implies” line part would it make sense

snow sleet
#

i honestly won't know until I see your final draft of your proof, right now we're going through the proof while I'm giving you pointers on why things are true (not all of these pointers need to be in the proof)

tidal tulip
#

Oh ok

snow sleet
tidal tulip
snow sleet
#

yes

#

but be more elaborate

tidal tulip
#

Like if we have an int a, the int a would not be in set B

snow sleet
#

right

snow sleet
vital dewBOT
#

logician

tidal tulip
#

That would be true

snow sleet
#

because $a\notin B-A$ implies $a\in\overline B$ ($a$ wasn't in $B$ in the first place) or $a\in A\cap B$ ($a$ was thrown out of the set $B$ when we calculated $B-A$).

vital dewBOT
#

logician

tidal tulip
#

Hmm

snow sleet
#

you following?

tidal tulip
#

I get that a is in the complement of B but I don’t get how a is in A intersection B

snow sleet
#

$B-A$ means take the set $B$ and delete the elements of $B$ that are also in $A$.

vital dewBOT
#

logician

snow sleet
#

Recall $A\cap B=A$

vital dewBOT
#

logician

tidal tulip
#

I think I get it now

snow sleet
#

okay great so that's the end of case 1

#

we just showed $\overline{(A-B)\cup(B-A)}\subseteq \overline{B}\cup(A\cap B)$

vital dewBOT
#

logician

tidal tulip
#

Correct

#

Case 2 now is the other way around

snow sleet
#

yes I'll leave that up to you right after I go over one piece we should elaborate more on from case 1

tidal tulip
#

I would say case 2 is similar to case 1

#

Is it possible that case 2 proof is backwards to what we did in case 1?

snow sleet
#

yes, saying $a$ is in the LHS of the equation, is the same as saying $a$ is not in the union of $A-B$ and $B-A$. Meaning $a\notin B-A$ and $a\notin A-B$.

vital dewBOT
#

logician

snow sleet
#

$a\notin B-A$ is how we got the first case complete

vital dewBOT
#

logician

snow sleet
#

Case 2: let $a\in \overline{B}\cup(A\cap B)$

vital dewBOT
#

logician

tidal tulip
#

Right

snow sleet
#

so $a$ is notin $B$ or $a$ is in $A$

vital dewBOT
#

logician

snow sleet
#

if $a$ is not in $B$, it definitely won't be in $B-A$

vital dewBOT
#

logician

tidal tulip
#

The second step would be that a is not in B

#

But I don’t get how to write the other half of that

snow sleet
#

if $a\in A$, then $a$ won't be in $A-B$ because $a$ is in $B$ as well

vital dewBOT
#

logician

snow sleet
tidal tulip
#

The part after B complement

snow sleet
#

hence $a\in\overline{(A-B)\cup(B-A)}

tidal tulip
snow sleet
#

do you agree that means $a$ not in B?

vital dewBOT
#

logician

snow sleet
#

or a is in A intersec B which is A

tidal tulip
#

I’m getting a bit confused

#

Too many things going on lol

#

For case 2, I have one step written down

#

And I’m a bit confused about step 2

snow sleet
#

Case 2 means a is not in B or a is in A intersect B

#

Right?

tidal tulip
snow sleet
#

This is not the title lol

snow sleet
tidal tulip
snow sleet
tidal tulip
#

Yes

snow sleet
#

Great so a not being in B means a isn’t in B-A

#

Right?

tidal tulip
#

Sure

snow sleet
#

It also means a notin A-B

#

Since everything in A must be in B

tidal tulip
#

Yes

snow sleet
#

Great so in this case a is in the set on the LHS of the equation we’re trying to prove

#

Cuz it’s not in A-B and not in B-A

tidal tulip
#

Right

#

That’s on the right side

snow sleet
#

No we’re trying to show a is in the set on the LHS of the equation we’re trying to prove

#

We already proved the other direction….

tidal tulip
#

We’re trying to prove that LHS is a subset of RHS

#

…no?

snow sleet
#

We already did that

tidal tulip
#

No but the case 2 is switched

snow sleet
tidal tulip
#

Right

#

But now that case is switched

#

?

snow sleet
#

What do u mean switched? We need to show the RHS is a subset of the LHS

tidal tulip
#

Yes that’s what I mean lol

#

I get what u were thinking now

#

Nvm keep going

snow sleet
#

Now the other half of case 2 is if a was in A intersect B

#

U following???

tidal tulip
#

Yes

snow sleet
#

K

#

This means a is in A

tidal tulip
#

Yes

snow sleet
#

So a notin A-B since everything in A is in B and would therefore get thrown out

#

Following?

tidal tulip
#

Yea

snow sleet
#

Great a in A also means a notin B-A because it would get thrown out of B

#

So we just showed the RHS is a subset of the LHS

#

Proof is complete

tidal tulip
#

Ok

#

I wrote down the cases but they’re in rough copy

#

And ik I’m missing some steps

snow sleet
#

That’s fine. Clean it up I walked you through the proof so as you’re writing up ur final draft just look back here

tidal tulip
#

For case 1 I think it’s good but case 2 I’m missing steps

#

And it’s a bit for confusing then case 1

snow sleet
#

Look at our chats lol I don’t wanna say the same thing 3times again when u can just scroll up

tidal tulip
#

I’m not asking for that lol

#

I can just share the rough is what I’m saying

snow sleet
#

Uh don’t do that

#

Clean it up

#

And then it’s complete

#

While it’s still fresh in ur mind

tidal tulip
#

It’s draining …

snow sleet
#

Yea these proofs are typically boring lol

#

Set theory proofs…..

tidal tulip
#

There isn’t a set notation for “also” is there?

snow sleet
#

Depends on the context…if a is in A and also in B then use that upside down U

tidal tulip
#

For case 2 I have it as, a is in A which also means a is not in (B - A)

snow sleet
#

There’s set notation for and or and not

#

That should say if a is in A….

#

Because the other option was a was in B complement

tidal tulip
#

Ok I’m gonna read case 2 again

#

Cuz I’m lowkey lost

snow sleet
#

K I’m gonna do some hw and see if anyone else needs some help

tidal tulip
snow sleet
#

Lmk when both cases are done

tidal tulip
#

Can we work on them one at a time to prevent confusion

snow sleet
#

I wanna see a complete proof

tidal tulip
#

Besides case 1 is more clear to me atm

snow sleet
#

Sure post a pic of what u got

tidal tulip
#

Ok

#

Uhh

#

It’s not letting me upload

#

… not letting me upload anything …

snow sleet
#

type what you have

tidal tulip
#

That’s too hard

snow sleet
#

ok outline what you got

tidal tulip
#

Shall I try dming it ?

snow sleet
#

sure

#

you should be able to upload pics here so not sure why that's not happening but yea we can try

snow sleet
#

<@&286206848099549185> Could someone help Milly. I've outlined a proof for Milly, we've been at this for 3+ hours because seems to be having a hard time following along...I don't wanna give the answers outright, hoping someone else here can explain it in a way that may help trigger his mathematical thinking.

umbral chasm
#

Ohmygod

#

The chat length is so long

snow sleet
#

yeah we've been at this since for 3+ hours

#

this is what they were trying to prove^

ivory badge
#

Just say x in the left iff (formula)

#

and in the right iff wtv

still isle
#

Pls gives me a hint on this. I think we are using Pigeon here but I don't know where to apply it.

ripe beacon
#

A domino tiling problem on 2 x n arrays:
https://stackoverflow.com/questions/37744971/filling-up-2-x-n-array-with-dominos

This gives us the fibonacci sequence.

Can someone explain to me, why we can simply add the probabilities?
So when we tile vertically -> f(n-1) probabilities or options
tile horizontally -> f(n-2) options.

I get that, but why can we simply add these? Is there a proof behind this? How does it work?

frigid oak
#

can anyone help me understand the third and the fourth example?

#

i want to say that there are no such functions but im sure that im missing something

safe steppe
#

Hi guys, is the only way I can prove a and b using a truth table or is there another way?

little prism
#

well truth table is by far the easiest way

#

and in the end every proof will be equivalent to the truth table

#

for a) anyway. for b) you can use a) assuming you already know stuff about 'and'

safe steppe
#

Thanks alot @little prism

foggy sentinel
#

In a workplace is a pool of 8 printers. One of the printers stops working. In how many possible ways can 19 print outs in the que be divided between the 7 functional printers if:

a) at least 1 printjob goes to each printer
b) at most 4 prints go to every printer

I got 177100 on a), is that correct?
I'm not sure how to solve b)

main cargo
#

I have a question regarding proof by induction (the theorem i'm proofing is about the adequacy statement for logic which makes use of trees/semantic tableaux). Basically what it comes down to is, imagine we have tested a property for the base case so it holds k = 0 for example. And then we assume that it holds for k, and I want to prove it for k+1. Can I then say that the property holds for everytihng smaller than k and use that to prove it for k+1 or not?

safe steppe
#

Hi guys, for this question, does my answer look correct, and how do I find the weakest preconditions, is it the top precondition {v<-1 or w>0}

little prism
main cargo
#

Okay thank you very much!!!!!

topaz flame
#

how to prove $p∨q, q∨r, p->¬r |- q$ using natural deduction

vital dewBOT
#

thatFirla

topaz flame
#

What I am struggling with is having two disjunctions and I don't know what to do? Because won't I have like 5 outcomes and all need to be true?

thorny hollow
#

Hi

#

What number is it?

#

What number would -x be?

#

Hmm

#

By substitution

y = 4. There exists only one x which satisfies the given formula

Then x = -4

4 = -(-4)

#

Is this right?

@pearl fern

#

@final cliff

#

sully sorry for pinging but I am so curious about this

final cliff
#

What are you trying to figure out here?

thorny hollow
#

What number would x be in the formula y = -x if substitute y by 4

#

And, also,

What is the notation for equinumerous sets…

#

I will kiss you if you clean my doubts

final cliff
#

You're trying to compare the set of positive "number" and the set of negative "numbers" right? @thorny hollow

thorny hollow
#

The formula

y = -x

#

It is a bijection
, yeah

#

Substitute the variable y by 4

4 = -x

#

What will x be

#

-4?

final cliff
#

"It can be seen at once that this function maps for instance, the set of all positive numbers onto the set of all negative numbers ..."

#

This is from your image.

thorny hollow
#

Yeahthen yes I am

final cliff
#

A formula by itself is not a bijection fwiw. Bijections are functions from one set to another that satisfy extra properties.

#

Here one of your sets is the positive real numbers and the other is the positive negative numbers.

#

So, you can define a function $f:\mathbb{R}^+\to\mathbb{R}^-$ such that $f(x)=-x$ for any $x\in\mathbb{R}^+$.

vital dewBOT
#

DootDooter

final cliff
#

Pretty sure this is the function they're talking about is all.

#

It's the same function I mentioned earlier.

#

For any x in the domain you map x to -x.

#

Not sure how much my notation makes sense to you.

#

$\mathbb{R}^+$ is the set of positive real numbers. $\mathbb{R}^-$ is the set of negative real numbers. $f:A\to B$ means f is a function with domain A and codomain B. $x\in A$ means x is an element of the set A.

vital dewBOT
#

DootDooter

thorny hollow
#

This I understand

final cliff
#

If you want to show my f is a bijection it just takes some arithmetic and basic facts about the sets above.

#

If y is a negative real number, then -x is a positive real number. Notice f(-x)=--x=x.

#

This shows f is a surjection onto the negative real numbers.

#

If x and y are positive real numbers and f(x)=f(y), then -x=-y by definition of f, so x=y follows by properties of real numbers.

#

This shows f is an injective function.

#

So, f is a bijection

#

You see what I mean @thorny hollow ?

thorny hollow
#

f(x) = -x

f(4) = --4

#

so, y = -x in a function notation

would simply be f(x)=-x?

bold tundra
#

I was looking at this question, and wondering why the answer wouldn't be $\forall_x \exists_y (P(x,y)\wedge \neg Q(x,y))$

vital dewBOT
#

bossysine

tidal bridge
#

Hi everyone. I colored the successive neighbours of a tile in an aperiodic hat-tiling and it looks like it produces hexagons. Is there a way to prove that ?

unborn vapor
# vital dew **bossysine**

That is correct actually - the only difference is they wrote “not (not P or Q)” and you wrote “P and not Q” but since those are equivalent, the two answers are the same

bold tundra
#

thanks

rare river
#

Hi guys I have a question

#

proof by contradiction basically means we assume the negation of a statement to be true? And we try to find a single contradiction from one of its premises to disprove that?

#

basically if we found out that a premise is false then we can conclude that the negation of a statement is actually false from just this singular contradiction

#

Therefore, if it this statement is false then the negation of the statement should be true instead?

#

I hope someone could help me stress-test my understanding of the concept, thank you!

final cliff
#

The mechanics of actually doing that are to assume the statement is true, do some calculations and inferences, derive some contradiction, and then to conclude the negation of your original statement must be true instead based on the contradiction.

#

You basically said all of this already, just phrased a little differently.

weary tiger
fallow dune
#

man i hate discrete math, especially cuz the teacher mad ass

tidal prawn
#

can someone help me understand what this means?

snow sleet
#

think about it by replacing y with x^2

#

y must be be the square of x in order for (x,y) to be in R.

#

that is only (x,x^2) is in R

#

@tidal prawn

static bone
#

Hi. Can anyone explain where they got the 4 from? is it because its a factor of 8?

fallow dune
#

what does a | b mean?

#

im thinking its b/a but idk

faint sphinx
#

That is, there is an integer k such that b = a*k

fallow dune
#

oh ok thx

plucky wedge
#

I know the answer is b and e, but I was wondering if c and a are the same thing in this statement?

#

is AxEy == EyAx?

faint sphinx
plucky wedge
#

oh

#

I looked it up and AxEy ~= EyAx

#

but I dont see how they would be different in the question

#

I think statement c says for all children of an existing parent?
and statement a says there exists a parent that for all children

#

which says two different things

#

I'm not sure if I translated that right though, could someone let me know if the quantifiers were translated correctly

plucky wedge
#

yeah im not sure if c is translated right and if it is then isn't that equivalent to a?

faint sphinx
#

a) is "there exists x, such that for all y, y is the child of x, and y works at a grocery store"

#

(idk why W(x) became W(y))

plucky wedge
#

I think that might be just my teachers mistake I had a couple of problems on my homework where she would accidently switch variables

faint sphinx
#

c) is "for all y, there exists x such that y is a child of x and y works at a grocery store"

#

So for a), there would be someone who's a parent of all the children. For c), each child has a parent (but this needs not be the same parent)

plucky wedge
#

oh ok

faint sphinx
#

+whatever about working, but idk that it's right as writen. In either case, this part alone shows they are different

fallow dune
#

Is this an acceptable proof or is there any steps I skipped in the parts after we must show that

snow sleet
fallow dune
snow sleet
#

I wrote a proof for a problem I assigned myself...was wondering if my proof is convincing to anyone else....I'm convinced but yea wondering if u guys are

#

pls ping me with whether or not ur convinced....I'm gonna grab some dinner rq and will prolly be helping other ppl in other channels

fossil mural
#

``$|S| = \infty$" is very weird notation

vital dewBOT
#

bee [it/its]

snow sleet
#

i agree lol

faint sphinx
#

I wouldn't call it complete

fossil mural
#

also it kind of feels like you just skipped over most of the proof?

snow sleet
#

LMFAO

#

no but my thinking is

fossil mural
#

like everything you said is true but you kind of just make one true statement and then jump to "so S is infinite, this is a contradiction"

faint sphinx
snow sleet
#

since s_i is arbitrary, then for s_l, there's something in S greater than that etc. Since s_j is also in S, then there's something in S less than that etc...

#

I should prolly right that^

nocturne grove
#

damn thats difficult

faint sphinx
#

That doesn't really fully show it's infinite though

snow sleet
#

I'm using that statement I proved recursively

#

I proved that u give me any element of S, I can find something in S smaller than it

#

u give me that "smaller" thing, I can find....

#

similarly for the greater elements

faint sphinx
#

Like yes that would be correct. But if I was grading it I would give you like 50%

snow sleet
#

Ryx

#

ok tanks

#

Yea I mean definitely more detail would be helpful to add in my proof

snow sleet
# nocturne grove LOL

Ryx also agrees with me that it's correct so I'm taking that win. But always good to hear other ppl's opinions on math work. That's how we get better, right?

faint sphinx
#

I would either prove it inductively, or do something along the lines of that you did to show (and ofc include this part in the proof) that if no max existed, you could then create an infinite, strictly increasing sequence of elements

nocturne grove
#

I want to be good at this proof stuff even though I am not lol

snow sleet
#

Aight thanks for the tips Ryx, much appreciated

faint sphinx
#

(and like ofc i know you know; just communicating that in a proof can be hard. I am also a bit of a harsh grader tbf)

nocturne grove
#

Are you guys like profs or something?

faint sphinx
nocturne grove
#

Oh damn

snow sleet
# nocturne grove I want to be good at this proof stuff even though I am not lol

I'm going into a Ph.D. program to be a mathematical logician so slick proofs for things are things I like to come up with. I pretty much leave things in the proof that are sufficient to prove the statement...which I did here too, but making sure the proof flows well and is reader friendly is also good to have other than just correctness.

#

proofs in textbooks are typically short for a reason

nocturne grove
#

Well either way, sounds cool, gl on the phd too

snow sleet
#

thanks. Proofs should be short and sweet. Some like mine are short and to the point, but may lack some flow that would be easier for readers to digest. A very short description of a mathematical logician is someone who uses tools in logic to go about proving things using tricks in logic that aren't typically taught in a intro to proof class. Proof theory is a huge topic as well.

nocturne grove
#

But hey seems like you enjoy what you do so I envy you

#

haha

#

Seems super cool though

snow sleet
# snow sleet

for instance like this one I posted^ it doesn't seem very obvious how the logic works, but it's there. This is why chatting with other mathematicians is always helpful...especially if I was teaching an undergraduate course. A professor would def understand my proof, but again if you can't convey your proof to ur readers well, it's not really much good if ur audience is not quite grasping what you're putting down

jagged grove
#

@snow sleet do u happen to know while compiler courses tend to focus on AST and dont use general graphs?

#

is there no use for general graph theory in those topics

#

or something along those lines?

#

i have to take compilers next academic period

snow sleet
#

and that @jagged grove is the only course I got a C in so I should not answer that question

#

Graph Theory was taught online and I was left teaching myself it so yea, I know when I shouldn't answer questions and send u down the wrong rabbit hole lol

nocturne grove
jagged grove
#

i got a 7 out of 10 in linear algebra cause i didnt take the final exam

#

i got a 10 in everything though

snow sleet
#

in graph theory too?

nocturne grove
jagged grove
#

@snow sleet i got a b+ in the discrete math

snow sleet
jagged grove
#

but we only took trees

#

so i studied some graph theory by myself

nocturne grove
snow sleet
jagged grove
#

no

#

i might finish all the proofs in my discrete math textbooks

snow sleet
#

One thing graph theory helps us with is some counting problems

jagged grove
#

and look at more advanced stuff

snow sleet
#

i know that for sure

snow sleet
jagged grove
#

ive looked at a thing called theory of ordered sets

snow sleet
#

Are you talking about the WOP?

#

the Well-Ordering Principle

jagged grove
#

that i do know

#

is every subset of the naturals has a minimum

snow sleet
#

nonempty subset

jagged grove
#

minimum is a n such that n < a for all a

snow sleet
#

but yea

jagged grove
#

yeah forgot that

#

but yeah

#

sec

snow sleet
#

<= actually

jagged grove
snow sleet
#

because n<n certainly isn't true

jagged grove
#

yeah

snow sleet
#

since n is in the nonempty subset

jagged grove
#

and were including n as an a

snow sleet
#

aight yea so u know the WOP then

jagged grove
#

in that for all quantifier

snow sleet
#

yup

jagged grove
#

sec

faint sphinx
nocturne grove
#

this some next hieroglyphs

#

what are these words bruh

faint sphinx
#

I am mentoring a directed reading program on them

snow sleet
#

noice noice

#

partially ordered sets

jagged grove
nocturne grove
jagged grove
#

i mean the stuff on that book

nocturne grove
#

liek certain elements are sorted or something?

#

partially idk

snow sleet
faint sphinx
#

correct

jagged grove
#

so ordered sets would be a subset of posets?

faint sphinx
#

It's a set with an "ordering" on it, which satisfies just 3 axioms/assumptions

nocturne grove
#

i should finish this last problem, no more distraction (i don't know waht im doing)

snow sleet
#

relations and stuff pretty much

#

but they're not equivalence relations

jagged grove
#

order i would assume

faint sphinx
#

Just different naming conventions

jagged grove
snow sleet
faint sphinx
#

I do not know or care for applications 🧍‍♂️

jagged grove
snow sleet
jagged grove
#

describe a counting problem quickly

snow sleet
#

combinatorialists are always in demand

jagged grove
#

is it like

#

permutations

#

and combinations?

snow sleet
#

yes

jagged grove
#

i know the basics from discrete

#

but i have not gone in depth

snow sleet
#

For instance, If S is a set with n elements, how many functions f: S^2 -> S are there?

jagged grove
#

is s^2 a cartesian product?

snow sleet
#

yes

jagged grove
#

n

#

or at least n

#

i would pressume

snow sleet
#

SxS=S^2 just like R^2=RxR

snow sleet
jagged grove
#

so n^2?

snow sleet
#

and they are sent to any one of S places right?

snow sleet
jagged grove
#

mm i havent counted possible functions

#

sec let me think

snow sleet
#

S^2 has n^2 elements

jagged grove
#

ohh

#

and its permutations right?

snow sleet
#

and each of those elements can go to any one of n places

jagged grove
#

the order doesnt mather

#

yes

#

so nxnxn

snow sleet
#

answer would be .........

#

?

jagged grove
#

n^3

snow sleet
#

oh god

jagged grove
#

im bad?

jagged grove
#

i know

snow sleet
#

bro missed the final exam in discrete too

#

nah jk

jagged grove
#

dont tell me were dealing with factorials

#

wait

#

we are

snow sleet
#

the answer is nxnxnxn....xn n^2 times right?

#

so $n^{n^2}$

vital dewBOT
#

logician

snow sleet
jagged grove
#

so i can choose a n

#

n to the 2 times

#

is what u mean

snow sleet
#

each element of S^2 ( and there are n^2 of these) goes to any one of n places so n times n times n.... (n^2 times)

#

(a,b) can go to n places

#

one of n places

#

(x,y) can go to one of n places as well

#

so can all of the ordered pairs

#

so n^(n^2) is the answer

faint sphinx
#

Now define this for infinite sets 🗿

snow sleet
#

LOL

jagged grove
snow sleet
#

I would start with

#

crying

#

LMAO

jagged grove
#

nahh more like

#

a book on combinatorics

snow sleet
#

and then I'd take a break for like years

#

it always does the trick

#

LOL

faint sphinx
#

tbf i don't know like cardinal arithmetic really. But the set of functions A --> B is really just the set B, producted with itself |A| times (lmaoo choice moment for infinite sets)

snow sleet
#

$\infty^\infty$

vital dewBOT
#

logician

snow sleet
#

LOL

jagged grove
#

so |A||B| ?

snow sleet
#

each element of A can go to one of |B| places

jagged grove
#

ahh

#

its cause their functions

snow sleet
#

yes

jagged grove
#

so a can only go to one

snow sleet
#

yes

jagged grove
#

for each possible function

faint sphinx
snow sleet
#

uh

faint sphinx
jagged grove
#

yes\

#

but we dont want that

#

cause thats not a function

#

a function is a subset of AxB

snow sleet
jagged grove
#

yeah but it has more to do with the fact that if (a,b) but if a is in b we cant have (a,a)

snow sleet
#

I'm asking how many functions we can have....they don't have to be injective

#

two elements fromt the domain can go to the same element in the co-domain that's totally fine

jagged grove
#

i edited

snow sleet
#

yes

jagged grove
#

cause thats not what i was trying to say

jagged grove
#

one element in a cant have to images in b

#

thats the important thing here

snow sleet
#

yes

#

wait are u still trying to count that function question I asked or are u thinking of something else?

jagged grove
#

im trying to figure out where the n^(n^2) reasoning came from

snow sleet
#

Each element of the domain can be sent to one of n places in the codomain

#

so u multiply n...n^2 times

jagged grove
#

question

snow sleet
#

yes

jagged grove
#

does this counting behave as a function itself?

snow sleet
#

I mean sure given different n, n^(n^2) should be different right?

faint sphinx
#

Better solution: Consider the set of functions from A --> B, where |A| = N and |B| = M. rather than working around the square in there

jagged grove
#

well M^A

snow sleet
#

no

faint sphinx
#

And justify why the | {set of functions A --> B} | = M^N

jagged grove
#

this is not

snow sleet
jagged grove
#

yes

#

cause codomain is not a cartesian product

snow sleet
#

Think about how many elements are in our domain

#

and how many elements are in our codomain

#

and use the reasoning that each element of our domain can go to only one element of our codomain

#

those three things are the only things needed for this problem

jagged grove
#

the power set is not needed?

snow sleet
#

you already noted S^2=n^2, and that's correct

faint sphinx
snow sleet
#

How about I write S like this instead

jagged grove
snow sleet
#

S={s1,s2,...,sn}

#

Given $S={s_1,s_2,s_3,\dots,s_n}$, count how many functions $f:S^2\rightarrow S$ exist. Recall $S^2={(s_i,s_j):s_i,s_j\in S}$.

faint sphinx
vital dewBOT
#

logician

snow sleet
jagged grove
snow sleet
#

dota streams?

jagged grove
#

yeah ronnie coleman is a meme within the admiral bulldog stream

#

also the culturist

snow sleet
#

nah I just watched Ronnie deadlift 800lbs and called it "lightweight baby"" ain't nothin to it but to do it

#

lmao true

snow sleet
jagged grove
#

there is a choosing for each element in the codomain of n

#

and since we have s^2 elements in the codomain

#

s can get map s^2 times

snow sleet
#

nope

jagged grove
#

in the domain

snow sleet
#

for each element of the domain [which is of the form (s_i,s_j)] it can be sent to any one of n places. Say it gets sent to s_1. Then for the next ordered pair, it can be sent to one of n places, say s_1 again...and so on

#

so all the ordered pairs each have n options for where they can go

jagged grove
#

wait

#

im gonna change what i typed earlier

snow sleet
#

k

jagged grove
#

done

snow sleet
#

uh okay, as long as it makes sense in ur head....what would the answer then be

jagged grove
#

for what rix mentioned?

snow sleet
#

no for my problem lol that u were doing

snow sleet
#

if u answer it for mine, you'll def be able to answer Ryx's much simpler problem

faint sphinx
#

no

#

bad

#

backwards

jagged grove
#

s^(s*s)

faint sphinx
#

Do mine, and conclude logicians as a special case lol

snow sleet
#

the reasoning goes both ways. If u generalize ur reasoning

jagged grove
#

for urs

snow sleet
jagged grove
#

yes

snow sleet
#

perfect

jagged grove
#

if it were lets say

#

SxSxSxS...xS -> S

#

it would be S^(s*s...*s)

snow sleet
#

so that's S^ what power?

#

u gotta define that power of S

#

cartesian product*

jagged grove
#

im mixing a indexx

#

in the notation

snow sleet
#

uh

#

How bout this:

#

For $|S|=n$, count the possible functions $f:S^k\rightarrow S$

vital dewBOT
#

logician

snow sleet
#

k and n are natural numbers

jagged grove
#

S^(S^k)

snow sleet
#

uh

#

S is a set

#

S^S doesn't make sense

jagged grove
#

n^(n^k)

snow sleet
#

yes

#

that's the answer

jagged grove
#

now for riz

faint sphinx
#

rizz

jagged grove
#

the only way of justifying that is by using induction

#

ryx

#

sorry

snow sleet
#

rizzard of oz

jagged grove
#

so is induction a valid approach

#

or not?

snow sleet
#

why would u even....

#

sure yes that would work

jagged grove
#

can u put the statement back in

#

so i can put it on paper

#

and actually write a proof

snow sleet
#

you could fix one of the sets and induct on the number of elements in the other set

snow sleet
jagged grove
#

yes

#

ryx's

snow sleet
#

Yea I'll type it

snow sleet
#

Given nonempty finite sets $A$ and $B$ with $|A|=N$ and $|B|=M$, count all the possible functions $f:A\rightarrow B$.

jagged grove
#

ur missing the second part

vital dewBOT
#

logician

snow sleet
jagged grove
#

no

#

justify

snow sleet
#

justify? what am I missing lol?

#

I'm so lost

jagged grove
#

i meant to prove that by induction

snow sleet
#

Given nonempty finite sets $A$ and $B$ with $|A|=N$ and $|B|=M$, count all the possible functions $f:A\rightarrow B$. Justify why this answer is $M^N$.

vital dewBOT
#

logician

faint sphinx
#

ooh no not induction

jagged grove
#

why?

snow sleet
faint sphinx
#

That doesn't really fit with this one

snow sleet
#

jk

jagged grove
#

him

#

m and n are naturals

snow sleet
faint sphinx
#

Yeah but you don't need it anyways, and I don't think it helps here

snow sleet
#

She's tryna geek out on proofs

#

let her do induction

jagged grove
#

u do know

#

im a he

snow sleet
#

oh

#

woops sorry

jagged grove
#

its ok

snow sleet
#

let him do induciton

#

great I can't spell now

#

induction*

jagged grove
#

writing give me a sec

snow sleet
#

Think about which set ur going to fix the cardinality of

jagged grove
#

writing it

#

sec

#

almost finished with n = 1

#

will share

snow sleet
#

Ping me when u have a proof I’ll be grabbing some food in the meantime but yea I wanna see this. I recommend induction on |the cardinality of A.|

#

Shoot was trying to make that one of those black things that u can open up to see

jagged grove
#

for n = 1

#

ill try for n+1

#

or i was thinking of using n-1 instead

#

@snow sleet

snow sleet
#

This looks fine for n=1, but the ordered pairs look backwards and the last line “which means…” isn’t convincing me that the number of functions when n is 1 is precisely m

jagged grove
#

thats what was bugging me

#

how can i express the counting of the possible functions

#

like i have shown that for a function there are m elements sure

#

its what i figured

snow sleet
#

If A={a}, (a, b_1) etc

jagged grove
#

ahh

#

ok

snow sleet
#

(a,b_1) represents one function

jagged grove
snow sleet
#

(a, b_2) another etc

snow sleet
#

Discrete math is the overarching area combinatorics is the more precise area

jagged grove
snow sleet
#

Im glad u fixed the right set tho ahaha

jagged grove
#

i was just sort of thinking how i would expand the terms

#

lol

#

let me keep going

snow sleet
#

K

jagged grove
#

that is corrected

#

now going for n+1

#

@snow sleet

plucky wedge
#

did she mean m + 2 = 2?

snow sleet
jagged grove
#

wait im going through branshi stuff

#

that inequality look sus

#

to me

snow sleet
plucky wedge
#

oh n is also 0 I see

jagged grove
#

i was thinking more like n+2m+1>= n+2*1+1

snow sleet
#

n being a perfect square means its nonnegative

jagged grove
#

since m>=1

snow sleet
#

that should be a >= instead of > there

jagged grove
#

u go spreading that formalism on everyone jo

#

jeez

#

lol

#

let me go back to the other proof

snow sleet
#

lmao

plucky wedge
#

why did she replace m with 1 in n + 2 * 1 + 1

snow sleet
#

on her way to showing it's greater than n+2

#

because m is at least 1

plucky wedge
#

oh ok I see

snow sleet
#

again it shouldn't be a strict inequality between n+2m+1 and n+2*1+1, but nevertheless ur teacher prolly already knows about that typo

#

since m could be 1

plucky wedge
#

hopefully this gets easier with practice

snow sleet
#

it will

#

different ppl prove things differently

#

everyone has their own flavor

#

sometimes it's hard reading other proofs

jagged grove
#

thats why reading different books makes things easier

snow sleet
#

I'm typing up a proof by induction for our problem rn

jagged grove
#

im doing the same thing

#

i think my idea has a hole

#

ill show u once im done

snow sleet
#

let's see who finishes first

#

I started after u so

faint sphinx
snow sleet
jagged grove
#

damn

#

give me a sec to show u how i was approaching it

#

ill finish the step where im at

snow sleet
jagged grove
#

i was thinking the exact same thing but was expressing it in a cumbersome way

#

let me show u

snow sleet
#

aight

jagged grove
#

idk if u get the idea

#

cause trying to write the next terms would be a pain

plucky wedge
#

why are we supposing n^3 + 5 is odd?

#

since its contradiction aren't we supposed to say n3+ 5 is even and n is odd

jagged grove
#

cause 5 is odd

#

ohh

snow sleet
# jagged grove

U could define T more concisely as $T={(a_i,b_j):i\in{1,2,3,\dots,n},\ j\in{1,2,3,\dots,m}}$

vital dewBOT
#

logician

snow sleet
jagged grove
#

it has to do with the way implication works

#

if a then b

snow sleet
jagged grove
#

but you proof that a then not b leads to a contradiction

#

then the case true then false disappears

plucky wedge
#

oh ok I'll write that down

jagged grove
#

so ur left with truth

jagged grove
snow sleet
jagged grove
snow sleet
#

done

jagged grove
#

are u a phd student by any chance?

snow sleet
#

almost

jagged grove
#

at masters?

snow sleet
#

@plucky wedge

snow sleet
#

But let me write a proof that more fits the structure of the statement you showed.

jagged grove
# snow sleet

doing it with no suprema and axiom of completeness

#

that is new

#

nvm

#

ur proving that is irrational

#

not that it exists

snow sleet
#

Given $x\in\mathbb R$, if $0\leq x<\epsilon$ for each $\epsilon>0$, then $x=0$

vital dewBOT
#

logician

snow sleet
jagged grove
snow sleet
jagged grove
#

nvm

vital dewBOT
#

logician

plucky wedge
#

also whats | in 2|p

jagged grove
#

divides

plucky wedge
#

oh ok

snow sleet
plucky wedge
#

oh

snow sleet
#

Are u looking at the first or second proof for the sqrt of 2 being irrational?

#

they're both by contradiction

#

but yea which one are u looking at

plucky wedge
#

first one

snow sleet
#

k

jagged grove
#

x and -x

plucky wedge
#

the math makes sense now but what is gcd(p, q)

jagged grove
#

greatest common divisor

snow sleet
snow sleet
snow sleet
#

GCD literally stands for that

#

it means p and q share no other positive divisor other than 1

#

gcd(p,q)=1

#

but I showed they share 2 as well

#

a contradiction

jagged grove
#

things like the limit of a convergent sequence is unique

#

and stuff of that nature

#

but he shows it using neighborhoods

#

idk why

#

like epsilon neighboorhoods

snow sleet
#

the definition says

plucky wedge
#

so it shows 2 is a common factor of p and q but why do we say that p and q share no other positive divisor other than 1?

#

is it implied in the proof somewhere

plucky wedge
#

or a definition of something

jagged grove
#

or relative primes

#

something along those lines

snow sleet
# jagged grove like epsilon neighboorhoods

let $(a_n)_{n=1}^\infty$ be a sequence in $\mathbb R$. Then we say the sequence converges to the point $L\in\mathbb R$ if for every $\epsilon>0$, there is a natural number $N$ for which $|a_n-L|<\epsilon$ for all $n\geq N$. In this case we say $a_n\rightarrow L$

vital dewBOT
#

logician

snow sleet
#

in other words, u can assume the fraction is a simplified as possible

jagged grove
#

wouldnt u have to add something like

snow sleet
#

that's an assumption u can make without losing cases in ur proof

jagged grove
#

withouth loss of generality

snow sleet
#

nope

#

not needed

jagged grove
#

ok

snow sleet
#

u could and u wouldn't be wrong

#

but it's not needed. If I give u a fraction u can assume it's in it's most simplified form, otherwise simplify it until u get gcd(p,q)=1

plucky wedge
#

oh ok so we are assuming that p/q is in it's most simplified form but since we can take out 2 it's a contradiction

snow sleet
#

yes

jagged grove
#

yes

snow sleet
#

I assumed p and q were relatively prime (meaning they share no other positive factor other 1), and yet I showed p and q are both even and hence divisible by 2>1

#

yup that's it

snow sleet
plucky wedge
#

oh ok I see

snow sleet
#

my second proof for that makes use of the fact that I can assume p is minimal

#

given a nonempty set of positive integers, the well-ordering principle allows me to make such an assumption

jagged grove
#

well cause we need any epsilon greater than 0

#

by def of convergence

#

we should probably tell ryx that we showed the problem suggested

snow sleet
#

yes and $|a_n-L|<\epsilon$ is equivalent to saying $L-\epsilon<a_n<L+\epsilon$

vital dewBOT
#

logician

jagged grove
#

yeah

#

theres a theorem that states that

plucky wedge
#

is proofs usually the first unit in discrete math

jagged grove
#

that can be shown using the properties of the absolute value

jagged grove
snow sleet
#

and the fact that epsilon was positive

snow sleet
#

and then logic

#

and then proofs potentially

jagged grove
#

and some colleges dont even emphasize proofs

#

like they mostly give u induction

#

and call it a day

snow sleet
#

in their defense

jagged grove
#

at least thats what they did in my college for SE majors

snow sleet
#

u can't bring someone from intro level to wizard level in even a semester

faint sphinx
jagged grove
#

but i took intro to mathematical thinking for math majors

#

so

snow sleet
#

proof theory takes time to learn

jagged grove
snow sleet
jagged grove
#

lol

#

is the math sorcerer in this discord?

#

guy is litt

snow sleet
#

and even profs aren't quite at the finish line of wizardly level. There merely much further along the math proof experience level than students are

snow sleet
jagged grove
#

at UCR where i did math (i can actually go back whenever i want i just dont have the money to. If i get a permanent position that might be different though).

#

every teacher needs a phd

#

to give a undergrad level course

#

its mandatory

#

idk how common that is

snow sleet
# jagged grove its mandatory

well yea because profs are representing the college and ppl pay a lot of money to go to universities/colleges. They want their profs to be experts in their fields

jagged grove
#

in UCR its barely paying i could take an entire undergrad semester for about 300 dollars

#

so

#

this is american mind u

#

and i had no scholarship

snow sleet
#

gotcha

#

UCR university of ?

jagged grove
#

let me send u a link

snow sleet
#

k

jagged grove
#

so this is the page for their grad curriculum

#

thats a little bit more expensive

snow sleet
#

costa rica

jagged grove
#

but it has all teachers that are working in there

#

yes

snow sleet
#

looks nice

#

I wanna live in costa rica lol

#

it's like the bahamas

jagged grove
#

those are the teachers

snow sleet
#

I mean think about it this way: If you're a prospective student looking to apply for colleges and one college has professors all with Ph.D.'s while another has only some with Ph.D.'s, that could be a deciding factor....so not to surprising to see colleges wanting profs with Ph.D's

jagged grove
#

yeah but look at the colleges though

snow sleet
#

of course

jagged grove
#

the ones from latin america are top latin american unis

#

and most of them are from france and the us

snow sleet
#

but yea aside from campus and such, I'd wanna be taught by an expert especially since I'm paying a lot for education

jagged grove
#

where are u at the moment?

snow sleet
#

I got a proof for u to try @jagged grove

jagged grove
#

sure

snow sleet
#

Show that there are infinitely many even numbers greater than two that can be written as the sum of two primes

#

prove this directly

jagged grove
#

isnt this a variation of the fundamental theorem of arithmetic?

snow sleet
#

not really. I made up this problem

jagged grove
#

ij

#

ok

snow sleet
#

Ryx let him think

faint sphinx
#

two cannot even be written as the sum of two primes kongouDerp unneeded condition

snow sleet
#

I wrote it like that for a reason.....

#

Goldbach's conjecture.....

snow sleet
faint sphinx
#

fair

snow sleet
#

I'm curious to see what dandida comes up with

#

U can assume there are infinitely many primes

jagged grove
#

so this is different from goldbachs cause of the infinitely many?

snow sleet
#

more or less yes

faint sphinx
#

goldbach is that every even > 2 can be writen like that

jagged grove
#

yeah

#

for all

faint sphinx
#

this just just infinitely many

jagged grove
#

basically

snow sleet
#

My hints for u @jagged grove are u can prove this directly and u may assume there are infinitely many primes

jagged grove
#

so would showing that there exists more than 1 be enough for this?

snow sleet
#

no

#

u need to show infintely many exist

jagged grove
#

this is what i dont get though

#

i dont recall being introduced to the infinitely many

#

concept

snow sleet
#

okay,

#

so

#

if I asked u to prove there are infinitely many odd numbers

#

u could state, let z be an integer then 2z+1. Moreover, 2z+1<2(z+1)+1.

#

There are infintely many integers

#

and I showed there are infintely many odd numbers I can construct

#

does that make sense?

jagged grove
#

yes

#

so basically showing that for any i can have another one

snow sleet
#

okay use a similar method of "construction" for when u show that there are infinitely many even numbers greater than two that can be written as the sum of two primes

snow sleet
#

So we haven't lost the infinitism so to speak

jagged grove
#

ok i got it sec

#

@snow sleet