discrete-math

[brave rock]

If you're not thinking of ordinary generating functions (for example, you may be thinking of exponential generating functions) this won't be the case.

[compact owl]

@brave rock I am first multiplying the binomial by 5, resulting in (15 - 10x). If I then apply the geometric series formula I get 15 to be the start term. There doesn't seem to be a common ratio in this case.

[vestal dagger]

A question on basic combinatorics. Can I get a hint on how to find the cardinality of the set below? Namely,
[\left{(x_1,x_2,\dots,x_k) ,\middle\vert, \sum_{i=1}^{k} x_i=m\right},]
where (k), (m), and all (x_i) are positive integers.

[vital dew]

grass

[brave rock]

Imagine a sequence of m stars. Let's say 10:

★★★★★★★★★★

Now having a sequence x_1, ..., x_k is the same as choosing k-1 positions to split this at. For example, here's (3, 3, 4):

★★★|★★★|★★★★

Now think about this: how many ways are there of placing these bars? Hint: this is the same as 'choosing' positions for each of the bars.

(Why do I say stars & bars? This is the classic name for this problem)

[vestal dagger]

I think there are 9C3=84 ways right? There are ten stars, there are 9 slots, of which we choose three to place bars in.

[brave rock]

I only see 2 bars in my diagram

But in any case, it seems you see the approach.

[dire stag]

I've spent 2 hours , and it's still wrong

I don't know what I did wrong

[vestal dagger]

Yeah thanks!

But I realised that wasn't actually the combinatorics I needed to answer my own question 😆

[limber burrow]

Does anyone have an intuitive approach as to why the neutral element of a Group is always part of the kernel (phi) (phi being an homomorphism)? -> I get the proof, but I dont really understand the concept behind it

[stray reef]

all homomorphisms send the neutral to the neutral

there is almost nothing to intuit here

if you know what the neutral element is and you know what the kernel of a homomorphism is, it's immediate

[gritty garnet]

Suppose ( G ) is a graph such that all its vertices have degree greater than or equal to 3. Show that ( G ) has at least one even cycle.

[vital dew]

renato

[gritty garnet]

how do I start this?

[calm chasm]

Do I just need algebra to proceed?

I know what my goal is. It's to get n = n' right?

[gritty garnet]

help

[haughty garden]

Look at a maximal path and say that v is an endpoint of the path, use the fact that v has degree >= 3 to suggest that v has at least three neighbours on the path (this is where the maximality of the path comes from). You can then apply PHP to show the result

[gritty garnet]

how does pidgeonhole apply to this?

mmm

[haughty garden]

Say that x, y, z are neighbours of v on the maximal path. Consider three (v, y) paths

you firstly have the edge v - y
you also have the path formed by the edge v - x and then the path from x to y
you thirdly have the path formed by the edge v - z and then the path from z to y

any pair of these paths only share vertices at their endpoints so the union of any pair of such paths form a cycle

you can then argue by PHP that at least two paths share the same parity in length

(aka the union forms a cycle of even length)

[lone verge]

hi

just want to confirm something

this means x can be between 1 and 4, while y can be between 1 and 4 right

[errant bear]

if by "between", you mean they can be any of 1, 2, 3, or 4, then yes

[foggy cipher]

would some1 mind explaining where the -C(4,1) comes from in the solution?

[umbral glen]

How would I go about proving this? I'm trying to do it by lim(n->inf)(f(n) / g(n)) but it can't seem to simplify it even though I'm sure that's how it's done

[haughty garden]

They subtracted the case where x_1 > 4, x_2 > 5

You end up getting C(1 + 4 - 1, 4 - 1) = C(4, 3) = C(4, 4 - 3) = C(4, 1)

[haughty garden]

Hint: for n > 1, n > sqrt(n). So firstly, g(n) <= nlog(n + n) = nlog(2n) = nlogn + nlog2 < nlogn + nlogn (n > 2) = 2nlogn <= 2(n + sqrt(n))log(n)

you should be able to do something similar for the reverse direction

(n + sqrt(n))logn < 2nlogn < 2nlog(n + sqrt(n))

[umbral glen]

Wow, thank you so much! I'll try doing thing

this*

[umbral glen]

So what exactly does this prove?

It looks like the first statement g(n) is the lower bound for f(n), but it looks like in the reverse it looks like f(n) is the lower bound for g(n). Does this mean they are theta of each other?

Does the 2 affect anything at the end of the evaluation or can I just divide it out?

After finishing this work, what kind of text should I write to finish the proof?

[haughty garden]

Indeed. They are Theta of each other

The first half of the proof shows that g(n) = O(f(n)) while the second half of the proof shows that f(n) = O(g(n))

[umbral glen]

Thank you so much! you're a lifesaver

[umbral glen]

one last thing. Why is it that in this first half uses '<=' while the 2nd half uses '<' exclusively

[foggy cipher]

Could u perhaps expand on how u got that?

[haughty garden]

Ehhh doesn’t make a difference; the first half could also be < as well if you wanted to

[haughty garden]

Set x_1 >= 5, x_2 >= 6 and solve it normally with this constraint

[foggy cipher]

yeah that was my thougt process too but i could only think of x1 = 5 x2 = 7 and x1 = 6 x2 = 6 but thats only 2 instead of C(4,1) = 4

oh wait

i see what u mean

LOL

thanks 🙏

[sinful niche]

for dilworths theorem what does it mean by minimum number of partitions of a chain

[haughty garden]

we want to partition a partially ordered set into a collection of chains

[ruby valley]

Hi could someone explain how to determine if this is true? I have done all the truth tables for all four statements but idk how to validate it

I have been stuck for a day now🫠

[stray reef]

make a truth table with columns for all the premises and for the conclusion

as in one big truth table

with cols for p, q, r, then q -> (p & ~r), ~p v q, etc.

[ruby valley]

I have done that. But what am I looking for? The conclusions to be all true in a single row?

<@&286206848099549185> 🙏🏼

There’s like only one row where the conclusions are true for all four statements and that’s when P=false and q=false.

Is that the validate part???????

[stray reef]

sorry for the late reply on my part

@ruby valley you're looking to verify that in all rows where all the premises are true, the conclusion is true as well.

[ruby valley]

So I’m suppose to be looking for P,Q and R to be true and then the premises( the four columns) to be true?

I’m confused

[ruby valley]

It’s not a problem. I’m the one asking for help after all

[ruby valley]

So the top row??

It’s the only row where p,q and r is true

[stray reef]

no

[ruby valley]

What do you mean by premises?

[ruby valley]

Isn’t it P, Q and r

Ohhhh

[stray reef]

no. p, q and r are the variables.

a premise is something "assumed true" for the sake of the argument.

[ruby valley]

Ohhhh

So this statement is true when P&Q is false but r is true.

Am I right?

Do the variables being true or false matters?

[stray reef]

...

"this statement" could refer to like

4 things

[stray reef]

you say you've made this table that i asked for

can you show it to me

[ruby valley]

There’s like only one row where the premises and conclusion is true

Is it that row that makes this validated?????

🫠

[stray reef]

this table is incomplete

the last four columns are missing half of their symbols

make it tidier and make it full

[ruby valley]

Wait but aren’t the remaining spaces suppose to be empty?

Like all the cases are accounted for?

Like second premise column doesn’t require r to be true or false ?

[stray reef]

no, they are not

"empty" is not a truth value in our system

[stray reef]

ok but why did you only fill in the ones where r is true

why, when r is false, does ~p v q not deserve a truth value?

[ruby valley]

Cos I’m not sure what to put🥲

Like how does r influence the truth or false of that statement?

[stray reef]

it doesn't

[ruby valley]

Then isn’t it an empty space???

[stray reef]

no it's not

[ruby valley]

What am I suppose to put? I’m confused

[stray reef]

well

[fossil mural]

...but if r is true, then you apparently know exactly how r influences the truth value of ~p v q?

[stray reef]

for pqr = TTT, the value of the second premise is T

the value of r doesn't affect the second premise

this means that for pqr = TT_, where the _ can stand for either T or F, the second premise will still be T

[ruby valley]

I just did the table for each individual statement and then combine them into the big table😩

[stray reef]

do you agree or disagree with this

[ruby valley]

Might be because I combine the table🫠

[ruby valley]

Ohhhhh

I think I get what you are trying to say

Only look at P and q values?

So if P and Q are both true, regardless of what R is, the premise is still true?

That’s what you are saying?

[stray reef]

that is exactly what i have been saying, yes.

so what should go in the TTF row for the 2nd premise?

[ruby valley]

Ohhhhhhh

Ok ok

[ruby valley]

True because p and q are true

And second premise only require q to be true for the premise to be true

Yes?

[stray reef]

overthinking

[ruby valley]

🫠

[stray reef]

the value of the second premise is the same for the TTT and TTF rows

and you have already established that in the TTT row it's T

therefore in the TTF row it is also T

[ruby valley]

Ohhh ok ok

Let me do up the full table with all the values now

[stray reef]

yes

and please make it tidy

[stray reef]

as tidy as these

could do it in Excel or some similar tool

[ruby valley]

Ok ok

Ok! I got it!

The last two rows are all true

What’s the next step?

What makes an argument valid in this case??????

[stray reef]

let me just doublecheck that you didnt mess up the table.

ok, you did indeed construct the table correctly.

[ruby valley]

Yeah

Thank you!!

[stray reef]

you're looking to verify that in all rows where all the premises are true, the conclusion is true as well.

[ruby valley]

I’m not even sure myself

This is my first time doing discrete math and it’s hard🤯🫠

[ruby valley]

So that would be the last two rows right?

[stray reef]

not just those, no.

[ruby valley]

What makes an arguement valid first?

[stray reef]

should i repeat myself a third time

i already told you what to verify

[ruby valley]

You mean this?

[stray reef]

yes

[ruby valley]

Ohhhh

[stray reef]

your issue now is you have not located ALL the rows in which every premise is true at once.

this is not about math, this is about reading.

[ruby valley]

Huh?

Isn’t that just the last two rows?

[stray reef]

row 2 must have been in your blindspot

[ruby valley]

Wait why row 2????

[stray reef]

do you think row 2 should be excluded

if so why

[ruby valley]

Isn’t the premises must be true then the conclusion is true is what I’m looking for?

[stray reef]

aaarhuahah.

[ruby valley]

^this?

[stray reef]

yes

so you look at the truth table

you mark the rows in which all premises are true

you mark all such rows, not omitting any

[ruby valley]

Ohhhhhh

I thought you meant true literally…

Sorry

[stray reef]

THEN you check, for each marked row, whether the conclusion is TRUE in that row.

[ruby valley]

Yeah 👍

Ok

[stray reef]

i did mean it liteerally

how else could i have meant it

tll me

how tf else could i have meant it

you read something into my words THAT WASNT THERE

that is very frustrating

[ruby valley]

Like the last column is “TRUE”

Sorry

Is marking down the columns the solution to it?

[stray reef]

h

the marking carries no sacred meaning whatsoever

it was ONLY my attempt to unfuck your misreading/misunderstanding of my words, nothing more

if you dont want to place any marks you dont need to

[ruby valley]

Ohhhhhhh ok ok

[stray reef]

im gonna go

[ruby valley]

Ok thanks for your help!!!😅😅

Sorry but I’m new to this so I’m not sure how this works

But thank you!!!

[silent tree]

is wolfram any good ?

[left wren]

what a strange question

[cerulean radish]

Yes

[spark gazelle]

is there some simpler way of solving non-homogenius recurence relations that doesn't involve a 30 step process

[distant otter]

My reasoning to this was:

For any distribution of white balls, adding all black balls to the box with more white balls is optimal (maximizes probability of living). Removing a white ball from the box with less white balls and adding it to the box with more white balls increases the probability of living monotonically (assuming black balls are always optimally allocated). This proves that the optimal strategy is 1 white ball in one box, and 14 white balls + 15 black balls in the other box. The probability is roughly 74%.

Was curious if anyone knew of different approaches to this problem?

[gritty breach]

Hi, for this q i'm trying to compute N,p from the defs <k> = (N-1)p, sigma^2 = (N-1)p(1-p).
Then, 100 = (N-1)p(1-p) -> 100 = 40(1-p). But then p not in [0,1]

[spark gazelle]

nvmd I got it

[stray reef]

@ember marsh so to move us here you're asked to prove A - (B ∩ C) = (A - B) ∪ (A - C)

[ember marsh]

yes

[stray reef]

two questions for you, so that i know how to approach explaining this:

[ember marsh]

i know boolean thing

like or , and , not

[stray reef]

1. have you done any other set theory proofs before?
2. is the use of venn diagrams ok?

no wrong answers to either of those

[ember marsh]

1. i have the first proof of the first De Morgan's law

2. yes

[stray reef]

these questions are only for me to determine what angle to approach this from as far as explanations go

[ember marsh]

thats ok

[stray reef]

ok right

well then

draw a bunch of 3-set venn diagram templates

on one, shade in A - (B ∩ C)

on another, shade in A - B

on a third, shade in A - C

all shall be laid bare

[ember marsh]

this is A - (B ∩ C)

right?

[stray reef]

no

you're only supposed to use one color, for one.

also, im a little suspicious.

let's set aside the problem for a second.

get a blank venn diagram template and shade in A.

btw you can use the circle and bucket tools.

[ember marsh]

like this?

[stray reef]

ok right that's correct for A

now subtract B ∩ C from it

i.e. over this picture, color B ∩ C back into white

[stray reef]

yup great

that's your A - (B ∩ C)

[ember marsh]

yes

and now?

[stray reef]

here's a neater version btw

anyway

now get a fresh venn diagram, and on it, shade A - B

[ember marsh]

but should I also use the set C?

[stray reef]

wdym by "use the set C"

[ember marsh]

drawing it

[stray reef]

you should still draw it on the same 3-set template yes.

you can take mine and un-color it

[ember marsh]

like this?

[stray reef]

this is not A - B.

[ember marsh]

and what is

?

[stray reef]

as in "what did i draw?" or "how do i draw A - B correctly?"

[ember marsh]

what did i draw

[stray reef]

you drew (A ∪ C) - B

[ember marsh]

where i did wrong?

[stray reef]

well the bit at the bottom is outside A

a point that doesn't belong to A cannot belong to A-B

A - B is literally just this

do you undestand this? Y/N

[ember marsh]

but its A ∩ C ?

[stray reef]

no, what i just drew is not A ∩ C.

[ember marsh]

why?

[stray reef]

A ∩ C is the set of all points that belong to both A and C at once.

the big top-left region lies outside C.

[ember marsh]

i mean this anyway

[stray reef]

bruh

that's not A ∩ C either, and it also is only PART of what i shaded.

the bit you just circled in red is A ∩ C - B.

[ember marsh]

aaah ok

ye

[stray reef]

just saying

if you're gonna talk about something OTHER than what i drew

then you have to make it clear what you're talking about

otherwise you WILL be misunderstood and it will not be good for me and also not be good for you.

ok, so coming back to this

this is A - B. do you agree or disagree?

[ember marsh]

yes

agree

[stray reef]

ok

now draw A - C for me.

[stray reef]

ok great

so to sum it up

[ember marsh]

yes

[stray reef]

we are done

[ember marsh]

? wait

so now I just have to write the proof following these diagrams?

[stray reef]

i mean the proof can be just one word

"Behold!"

the diagrams speak for themselves

you've got your A-B, you've got your A-C; their union produces the same picture as the one for A-(B ∩ C)

[ember marsh]

okay!

the first De Morgan's law was written like this

We proceed by demonstrating the double inclusion, namely proving:

[ A - (B \cup C) \subseteq (A - B) \cap (A - C) ]

[ (A - B) \cap (A - C) \subseteq A - (B \cup C) ]

Let's consider an element ( x ) in ( A - (B \cup C) ), then:

[ x \in A ] and ( x \notin B \cup C ) ( \Rightarrow ) ( x \in A ) and ( (x \notin B ) and ( x \notin C) ).

This implies that the element ( x \notin B ) and ( x \notin C ), thus it is an element both of the set difference ( A - B ) and ( A - C ), i.e., ( x \in (A - B) \cap (A - C) ).

Let's consider an element ( x \in (A - B) \cap (A - C) ), then ( x ) is an element of set ( A ) which is simultaneously not present in sets ( B ) and ( C ). Thus ( x ) is an element of set ( A ) such that ( x \notin B \cup C ), i.e., ( x \in A - (B \cup C) ).

[vital dew]

alee

[stray reef]

well, you're the one who said using venn diagrams was ok.

so i walked you through a proof via venn diagrams.

you could also do element chasing instead.

[ember marsh]

yes

[stray reef]

it's kind of routine and not too enlightening.

[ember marsh]

I will write the proof myself

thanks!

I needed the diagrams to understand better

[weary tiger]

Can some explain this better, this explanation in the book is a bit confusing. What is meant by "reduce modulo m after each multiplication? " Is there a rule that allows you to find b mod m, b^2 mod m, ... b^(2k-1) mod m first and then multiply the results together to get b^n mod m, instead of doing b*b^2 *b^4 ... b^(2k-1) first and then mod m?

[stray reef]

reduce modulo m = take the remainder modulo m

also the last one you find is not b^(2k-1) but b^(2^(k-1))

would you like it explained on the 3^644 mod 645 example? Y/N @weary tiger

[weary tiger]

Yes please, I dont know how all the variables relate to the theory given above

[stray reef]

ok right so

your goal is to find 3^644 mod 645

,w 644 to binary

[vital dew]

Results provided by WolframAlpha

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

Requested by ann_dec

[stray reef]

644 = 512 + 128 + 4

so 3^644 = 3^512 * 3^128 * 3^4

with me so far?

[weary tiger]

yeah

[stray reef]

ok

so if we knew the values of 3^512, 3^128 and 3^4 modulo 645,

we could multiply those together and take the remainder mod 645

and that would be our answer

does this make sense to you?

[weary tiger]

So find 3^512 mod 645, 3^128 mod 645, and 3^4 mod 645. These all represent remainders. Multipy these remainders together and then mod 645 again to get the answer ?

[stray reef]

that's the idea, yes.

for more efficiency (and less working with big numbers), you'd reduce mod 645 after each of those multiplications. but that specifically is a minor detail.

ok, so do you follow thus far

[weary tiger]

yeah... hold on so it is basically applying the above in that step ?

[stray reef]

yes

ok so then to continue

[stray reef]

the natural question that should arise is: how do we get THOSE values?

[weary tiger]

Yeah because they are still very large

[stray reef]

and to that, the answer is simple -- consider this sequence:

3^1 mod 645
3^2 mod 645
3^4 mod 645
3^8 mod 645
3^16 mod 645
and so on.

the neat thing about it is that it can be calculated recursively!

each of its terms equals the square of the previous, modulo 645.

and the starting term is obviously just 3.

do you understand this?

@weary tiger

[weary tiger]

When you say this you are saying 3^2 mod 645 = (3^1 mod 645) ^2?

[stray reef]

[(3^1 mod 645)^2] mod 645 more formally

[weary tiger]

So to get 3^512 modm you do this process recursively starting from 3^1 ?

[stray reef]

yes

the point is: after you have calculated as far into this sequence as you need, you take just the terms that you want, and multiply THOSE together.

[weary tiger]

ok i see, thank you much

[weary tiger]

i understadnt he range when the sets of numbers are the same

such as Z to Z or R to R

but when they are different I cant wrap my mind around whats happening

the way i understand it is that "pick any x, x ∈ R, that gives a Z"

[sharp mauve]

That's not exactly it. It is implicitly given that for any x in R, f(x) will actually be a number in Z

[weary tiger]

How do I do 10b

Specifically evaluating X to show that it is not (or is) equal to the set {1.2, -2.5}

By the definition of a proper subset.

[shadow lion]

show that every element in {1.2, -2.5} is also in X, but not every element of X is in {1.2, -2.5}

[weary tiger]

right...I got that concept down, but not sure how to implement it. Do I have to just show all the solutions of the function given in X?

[fringe turret]

Is p V T a tautology or not?

I believe it should, because no matter what is the value of p the output of truth table is T and this is the bare minimum requirement of tautology

[shadow lion]

Q: how would you show that an element from one set is in another?

for instance, how would you show that 1.2 is in X?

[weary tiger]

in this case, you plug the element in as x

[weary tiger]

yeah

plug it in

[shadow lion]

plug it into what?

(you're essentially correct, btw)

[weary tiger]

well I did that work to prove that {1.2, -2.5} is a subset of X

[shadow lion]

an element is in a set if it satisfies the condition needed to be in the set

[shadow lion]

okay, so it's the other way around that's the issue?

[weary tiger]

the top is from 10a

and then...

[shadow lion]

okay good

[grand totem]

It is, yes

[weary tiger]

hmm

wait

[fringe turret]

And my reasoning is also correct, right?

[weary tiger]

do I have to show that the values I got from plugging in the X are in the other set?

like for instance, the 0.288 and 24.375 that I found?

[grand totem]

Yes

[shadow lion]

no, you dont

to show that {1.2, -2.5} is a proper subset of X, you have to show that all elements in {1.2, -2.5} are in X, but there exists at least one element in X which is not in {1.2, -2.5}

does that make sense?

[weary tiger]

yes, but I don't know how to do that ;-;

[shadow lion]

your goal now becomes "find just one element in X which isnt in {1.2, -2.5}"

i.e. one element k which satisfies k^3 - 6k^2 - 19k + 30 > 0

but is not 1.2 or -2.5

[weary tiger]

OHHHHHHH

and it has to be a real number, I assume

bc of this

part

[shadow lion]

mhm

[weary tiger]

thank you sm

[crude shore]

Hi folks 🙂 Let $f(n) = n + n * (n-1) + n * (n-1) * (n-2) + \dots + n!$. Why is it true that $f(n) = \lfloor e * n! \rfloor$ for $n > 1$? (https://oeis.org/A000522, one of the Pari formulas)

[vital dew]

flebron

[crude shore]

(I'd be happy with an argument for why it's < 3 n!)

[crude shore]

Oh of course, $e = \sum_{k=1}^\infty \frac{1}{k!}$ , so $e n! = e \sum_{k=1}^\infty \frac{n!}{k!}$ which is of course greater than just truncating when k gets to n.

[vital dew]

flebron

[odd prism]

I am supposed to do this with a sign reversing involution

[weary tiger]

Ok so...

I'm doing #13

I provided examples but that's not a proof, right? How do I actually prove it

[weary tiger]

i thought it would be that but that deosnt make sense. if x=1.1 then f(x) wont be in Z.

or does the statement R->Z force you to choose an x that would make f(x) belongs to Z

[sharp mauve]

if x=1.1, then f(x) = 1

Are you familiar with the floor function?

[sharp mauve]

Indeed this is not a proof. Are you familiar with proofs involving showing that two statements are equivalent?

[spark gazelle]

I am still so lost on how to find An^(p) in a non-homogeneous recurrence relation, can anyone help me out?

[weary tiger]

never heard of it. Google says basically just round f(x) down to the nearest integer?

[stray reef]

x, not f(x).

but yes, rounding down to the nearest integer is exactly what the floor function does.

for example, $\floor{\pi} = 3$

[vital dew]

Ann

[weary tiger]

ohhh

so if i map it, all the A values get rouded down first before going through f(x)?

or does it go through f(x) then get rounded down

[stray reef]

what is an "A value"?

i think you're monumentally confused. or maybe i am instead.

please repost the original problem.

[fossil mural]

(also what's f?)

[weary tiger]

when we were taught mapping

the left side is "A" and the right side is "B"

and the arrow is the function

[stray reef]

"the arrow is the function" is certainly one way to look at it...

but ok

so f is the floor function.

[stray reef]

domain and codomain respectively.

[weary tiger]

yeah

[stray reef]

so if i map it, all the A values get rouded down first before going through f(x)?
or does it go through f(x) then get rounded down

this just makes no sense

rounding down is what f does.

[weary tiger]

say i take x=1.4

is it then f(1)?

[stray reef]

no, you have it backwards.

[brave rock]

f(1.4) = 1, if that's what you mean

[stray reef]

f(1.4) = 1

[weary tiger]

ohhhh

[brave rock]

But also f(1) = 1, if that's what you mean

[weary tiger]

okok thank you

[cursive nymph]

I was wondering... is it guaranteed that an infinite union of ZFC sets (suppose there are countably many of those) ${\mathcal{F}i}{i=1}^{\infty}$ will be a ZFC set? \

Like, in ZFC, with the help of Axiom of Pairing and Axiom of Union, we can always construct unions for any finite number of sets. But what about infinite?

[vital dew]

Sweet Tea 🧋

[cursive nymph]

in other words,
$$
A_1, A_2, \ldots - \text{ sets } \stackrel{?}{\implies} \bigcup_{i=1}^{\infty} A_i - \text{ set }
$$

[vital dew]

Sweet Tea 🧋

[grand totem]

For $(A_i){i\in I}$ an $I$-indexed family of sets, we have $$\bigcup{i\in I}A_i=\bigcup{A_i\mid i\in I}.$$

Now if $I$ is a set, then so is ${A_i\mid i\in I}$ (by replacement). And so would be $\bigcup{A_i\mid i\in I}$ (by union).

[vital dew]

Neverbloom

[grand totem]

And of course this still holds if I happens to be infinite.

[cursive nymph]

gotcha, thanks!

[twilit sundial]

what would be the loop invariant here? would it be "if x is in a, then the search space in each iteration will always contain a"?

[neon harbor]

Yeah, if x is in a, then it is between L and r inclusive

[twilit sundial]

aight aight

[weary tiger]

im having trouble with this problem

the internet says the answer is 15

but

at the bottom i have 15 numbers and none of them can add up to 110

I would need a 16th number in my case to make this true.

is the internet wrong or is tehre something flawed with what im saying

[fossil mural]

34, 37, 41, 44 all aren't in the set

the correct list is 3 7 11 15 19 23 27 31 35 39 43 47 51 55 and that's only 14 numbers

[weary tiger]

bruh how did i not see that

ops

LOL

thx

[graceful hamlet]

HI Everyone!

🙂

[upbeat mango]

Q4

How do I go about it ?

[agile salmon]

I'm having trouble what to use law of replacement on logical equivalence

[fresh hull]

is there a general formula for the substitution you need to make for the non homogeneous part of a recurrence relation?

[grizzled storm]

Anyone knows a book or resourse on first order logic that uses a notation similar to this?

I'm struggling a lot to understand this with from the given materials..

[grand totem]

There are so plenty of appropriate books and essentially any introductory logic textbook should do the trick. One concrete example would be Ebbinghaus & Flum whose notation looks quite similar to the notation in your screenshot.

[grizzled storm]

Thanks for the suggestion. Any tips on working through this? I can get most of the stuff intuitively but the formalism is pretty heavy

[grand totem]

Just like with any other subject, I'm afraid the only thing that helps in that situation is to push through the struggle and practice

[grizzled storm]

The answer never changes ahah

Thanks!

[chilly hemlock]

How is A_2 a countable set??å

I can let f(x) = 1/2 for all x, thus no inverse exists so it cannot be a bijection

[fossil mural]

1/2 is not in {0,1}

[chilly hemlock]

oh

[fossil mural]

...also what do you mean by "thus no inverse exists"?

[chilly hemlock]

they meant 0 or 1

?

[fossil mural]

it's true that f doesn't have an inverse, but the question isn't "is every element of A_2 a bijection", it's "is there a bijection between A_2 and N"

[fossil mural]

yes

[chilly hemlock]

yes yes ok i understand

[stray reef]

are we supposed to take the condition inside the defn as holding for all n

[chilly hemlock]

sorry i did not understand thi

[stray reef]

should the definition of $A_2$ be written like this? $$A_2 = { f : \bN \to {0,1} \mid f(n)\leq f(n+1) \text{ for all }n}$$

[chilly hemlock]

doesn't say but i think so

[vital dew]

Ann

[brave rock]

I would imagine that’s the intended quantifier, yes.

[chilly hemlock]

ok if anyone is curious i did this:

since f(n)<=f(n+1), then all functions are one of these:

f_k(n) = {1 if n<=k, 0 else}

and because there is a bijection from N to k we are done.

[muted bear]

Given 17 points inside a 2 ft x 2 ft square, there must be a pair of points within x feet away from each other, what would the smallest distance be?

the given answers are 1 ft, root 2 ft and 2 ft, am i tripping or are all of these wrong

[rapid spire]

having trouble translating the first premise in terms of p and q. If p is a good car and q is cheap would it be p implies not q? Or is it not q implies p?

[lethal prairie]

Just my two cents this argument is a contra positive making it a valid argument. P=good car is cheap and Q= Simbaru is cheap

[lethal prairie]

~Q->~P

[weary tiger]

1.) Why are they allowed to subtract b from both sides?

[stray reef]

why wouldn't they be

it's a property of modular congruences

x = x' (mod m) => x + y = x' + y (mod m), for any x, x', y ∈ Z

@weary tiger

[weary tiger]

ok, then the part that says because gcd(a, 26) = 1, then there is an inverse a'. Im sorry if this is trivial but whats the reason

And everything after that i dont understand

[stray reef]

ok first off do you know what a modular inverse is

[weary tiger]

I dont remember even coming across that

so no

[stray reef]

ok right

then let's forget about modulo rn

do you know what the multiplicative inverse of a real number is

[weary tiger]

what you multiply a real number by to get 1?

[stray reef]

yes

the same idea goes here: given an integer x, its inverse modulo m is the integer y s.t. xy = 1 (mod m)

this should probably appear somewhere in your book as a definition

probably in the first chapter where it talks about modular arithmetic

[weary tiger]

There is something at the end of the first section that says... multiplicative inverses do not always exists modulo m. Thats it

[stray reef]

that's it? so it says THAT but it does NOT even tell you what a multiplicative inverse is?

can you maybe send me a copy of the book

[weary tiger]

The very last sentence says we'll return to the question of when an integer has a muliplicative inverse later in the chapter. Im sorry, Ill just look and see if I can find it

I dont actually have the book on my computer. Its on a school site. But its from the rosen discrete math book

[stray reef]

ok fine whatever

now the stmt you were asking about is: a has an inverse mod m iff gcd(a,m) = 1, and specifically the <= direction of that equivalence

do you know Bézout's lemma?

feels like a shot for the moon at this point but i gotta ask

[weary tiger]

There is Bézout's Theorem... If a and b are positive integers, then there exists integers s & t such that gcd(a,b) = sa + tb

oh nvm there is a lemma that follows... If a, b, c are positive integers such that gcd(a,b) = 1 and a | bc, then a|c

[stray reef]

this one is what we want

gcd(a,m) = 1 => exist s and t such that as + mt = 1 => as == 1 (mod m)

for you m=26 but the number twenty-six holds no sacred meaning

[late goblet]

is there sombody that could help me out

[stray reef]

gonna need a translation here

also looks more like #probability-statistics but whatever

[late goblet]

Oh yea sorry I will translate it

[stray reef]

...

this is less helpful than the original, sorry

you did not need to delete that

[late goblet]

"We concider a probabiliy measure P and events A,B,C for which we know that: P(C^c) =1/2 (C^c = complement of C)

P(A∩C|B)= 1/10

P(B∩C^c) = 1/6

and P(A∩B∩C^c) = 1/10

further we know that the events are pairwise independent

Wich of the following statements is true?

the second statement = " None of these statements is true"

[stray reef]

well ok

now it is clearer

have you made any progress so far?

[late goblet]

yea, i have put the conditions to other forms by using some rules

but i don't really get what they mean by A,B and C are pairwise independent

are they not just al 3 independent of eachother?

so that we can say this P(A∩B∩C)=P(A)⋅P(B)⋅P(C)

[stray reef]

no

pairwise independence doesn't imply three-way independence

i can give you an example of a trio of events that aren't independent all together, but pairwise they all are

[stray reef]

it means P(A&B) = P(A)P(B), P(A&C) = P(A)P(C) and P(B&C) = P(B)P(C)

[late goblet]

oke thanks

i will try solving it again

[late goblet]

i found that P(C)=P(C^c)=1/2 and P(B)= 1/3 and P(B^c)= 2/3

but i don't see how to find A

i have triend multiple things but i always find what was given

[stray reef]

hm

im on the move rn so cant really reproduce my idea

but if you haven't already i would try to make a Venn diagram

[late goblet]

good idea i will try it

[lyric quartz]

Is there a naming for periodic functions in which all fibers are empty or singleton(/propositional) for some subset in the domain?

Uh wait, I guess that is an injection. Some "periodic injective" function...?

[late goblet]

i just found that P(A) = 1/3 could that be right?

[hard citrus]

Can someone help me understand how to use inclusion exclusion to solve this problem from my combinatorics class?

What is the number of permutations of the numbers from 1 to n in which no even number is a fixed point? (The odd numbers can be anywhere)

[cursive nymph]

why do we need linear order here?

like, we didn't use it (yet)

or so it seems

nvm. probably cause in the definition we say that the arrangement is of type $(k_1, \ldots, k_m)$ – to avoid ambiguity

[vital dew]

Sweet Tea 🧋

[cursive nymph]

why can't I solve this with
$$
\binom{15}{1} + \binom{15}{2} + \ldots + \binom{15}{15}=2^{15}-1
$$
?

Author provided a solution with "each basket is determined by the amount of apples and oranges we put into it". Hence we can just take the cartesian product (and substract the case when the basket is empty later) \
And it does make sense! \
I just can't see where my solution is wrong... (obv they can't be both right)

[vital dew]

Sweet Tea 🧋

[fossil mural]

well your solution treats (for example) "the fourth and fifth apples" and "the first and seventh apples" as different baskets

their solution says that both of those are "two apples", the only thing that matters is the number of each type of fruit

so you are both right, you're just counting different things

[cursive nymph]

ohhh, I see. thanks!

||maybe the first and seventh are more juicy than fourth and fifth xDD||

[restive topaz]

if,
$\sum_{n=2}^\infty a(n) \phi(s,n) = \sum_{n=2}^\infty b(n) \phi(s,n) =$
for all s in some region, can I conclude that a(n) = b(n) for all n>=2
also to mention both these summations are absoutely convergent

[vital dew]

Akhil Rao

[cursive nymph]

we can't count the problem highlighted in red with the same method as outlined above, right?
I'd then argue that to each permutation of non-unique digits
$$
{ (a_1, a_2, a_3, a_4, a_5) , | , \text{"three 1's and two 3's"} }
$$

we assign precisely $3! \cdot 2!$ configurations of the same digits but being unique (by multiplication rule and the number of permutations of $n$-set) \
therefore
\begin{align*}
|\text{Non-Unique}| &=3! \cdot 2! |\text{Unique}| \
5! &= 3! \cdot 2! |\text{Unique}| \
\frac{5!}{3! \cdot 2!} &= |\text{Unique}|
\end{align*}

[vital dew]

Sweet Tea 🧋

[cursive nymph]

can u please give me a small hint? (I know this is an example and I can just flip the page and see the solution – but I'd like to try to come up with it myself)

[stray reef]

try first counting how many ways there are to pick 5 non adjacent spots for the vowels to go in

[fresh hull]

they can be adjacent as well

[fresh hull]

choose 5 spots for these letters

but do not arrange them

as we need to maintain the order

[stray reef]

no, they can't

problem says they can't

[fresh hull]

oh mb

how would it work then

inclusion exclusion?

or just multiple excliusions

[stray reef]

there's a trick for non-adjacent selections that i don't remember fully bc i don't wanna be off by 1 accidentally

[cursive nymph]

hmmmm. well, the total number of those spots seems to be
$$_b _c\ldots_z_$$
the number of letters plus one. i.e. 22\
so probably
$$
\binom{22}{5}
$$

[vital dew]

Sweet Tea 🧋

[stray reef]

oh yeah that would do it

[cursive nymph]

for for any such combination of adj spots we can pick precisely $5!$ different arrangements of those letters

[vital dew]

Sweet Tea 🧋

[cursive nymph]

hence
$$
\binom{22}{5} \cdot 5!
$$
?

[vital dew]

Sweet Tea 🧋

[cursive nymph]

those letters – i meant vowels in this texit snippet

[stray reef]

this times 21! i think

to order the consonants as well

[cursive nymph]

oh yeah, forgot abt that. thanks!

[cursive nymph]

what did I do wrong here? :((
Here I've massively overcounted. The book says it should be only |S|=151'200

oh, I'm also blind lol. I under counted it

[fossil mural]

We first arrange the 5 digits
which 5 digits though?

[cursive nymph]

ohhhhhhhh. it should've been 7•6•5•4•3
thanks!

lemme recount

now it's 236'880 >>> 151'200

[fossil mural]

well that's weird given that i calculated it and got 161280

which is also wrong but it's also different

[cursive nymph]

,w 7!+8! * 2 + 7! * 6 * 5

[vital dew]

Results provided by WolframAlpha

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

Requested by sweet.tea3

[fossil mural]

why 7!

that overcounts because it includes which way round you put the 5 and 6

[cursive nymph]

it's 7!/2! and eiher way at the end we multiply by 2, so it just becomes 7!

[fossil mural]

ok but then why 6 * 5

[cursive nymph]

yeah, exactly

[fossil mural]

that should be 6 choose 2

[hard citrus]

Btw guys can anyone give me a good way to solve it? I believe It can't be inclusion exclusion and My initial take was wrong as well

Like just the way/train of thought and I'll try to get it

[cursive nymph]

whut

they count it as 7*7! and not 8!

[fossil mural]

...oh i see

if you view it as 8!

you might just end up with 7 digits that all aren't 5 or 6

so yeah 7*7! does work

you can equivalently view it as

pick one digit, out of the digits that aren't 5 or 6, that you're going to exclude

7 choices

then order the 7 digits you're keeping

7! choices

[cursive nymph]

goootcha. thanks!

but even with that it still overcounts lol

,w 7!+7*7! * 2 + 7! * 6 * 5

[vital dew]

Results provided by WolframAlpha

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

Requested by sweet.tea3

[fossil mural]

7! * 6 * 5 is still wrong

6 * 5 should be 6 choose 2 = 6 * 5 / 2

[cursive nymph]

OHHYEAH

finally

thank you!

here's an alternative solution to that exercise, and I don't understand why $S^c$ must contain 5 and 6's consecutively. shouldn't it be «if $5$ and $6$ are both in some number $n \in S^c$, then it must be the case that they are placed consecutively» \

i.e. this complement $S^c$ may not contain 5's and 6's in ALL of its numbers

[vital dew]

Sweet Tea 🧋

[cursive nymph]

nvm. not possible. for example 1234789 (no 5 and 6) does belong to $S$, hence it won't belong to $S^c$

[vital dew]

Sweet Tea 🧋

[cursive nymph]

same for the case if we have only one 5 or only one 6

[wintry pier]

Hi, Im having some trouble finding the complexity of this code with Big-O notation:

        if (array == null || array.length == 0)
            throw new RuntimeException("Empty array");

        int candidate = array[0];
        for (int rec = 1; rec < array.length ; rec++)
            if ( candidate < array[rec] )
                candidate = array[rec];

        return candidate;```
I thing I have two comparissons at if, then the if inside the for loop that is executed N+1 times (with array.length = N), so 2 * O(1) + O(1) * (N+1) < O(N)

but Ive seen my prof. powerpoints that basically says I have 3 operations at the first if, then 1 comp + 1 sum + 1 comparisson, and that is done N-1 times

so T(the algorithm)=3+3*(N-1)=3*N

[agile magnet]

what are you lost on?

you seem to have O(N) figured out

Are you looking for big O or an exact number of operations?

You say big O but then your calculations seem to imply you want an exact bound of some sort

[wintry pier]

nope, just want big O

like, big O is also calculated with the number of operations

but Im kinda lost with the calculation of the code

nvm it was just some weird thing we were asked

thxx

[prisma jolt]

i dont get how this is true: $A\cup B \subseteq X \text{ if and only if } A \subseteq X \text { and } B \subseteq X$

$A\cup B \subseteq X \text{ if and only if } A \subseteq X \text { and } B \subseteq X$

[vital dew]

looksing

[prisma jolt]

its been a while since ive looked at discrete and checking my notes my proof wasnt a proof at all

so im wondering how thats true since couldnt
$A\cup B = {1,2,a,b} \text { and } X = {1}$

[waxen rivet]

for if i think we can say that there does not exist elements in A which are not in X and there doesnt exist elements in B which are not in X so when we take the union of both we won't get an element not in X hence A U B is a subset of X

idk how rigoruous this is but it can be a starting

[prisma jolt]

$A\cup B = {1,2,a,b} \text{ and } X = {1} \text{ then } A\cup B \subset X \text { but } B \nsubseteq X$

[vital dew]

looksing

[prisma jolt]

right?

[prisma jolt]

uh i dont really understand

waitttt im dumbbbb

i forgot the symbol meant A u B are subsets of X not the other way around lmao

[waxen rivet]

Something like that help?

[prisma jolt]

thank you i already figured it out tho

my notes were right i just forgot the symbol worked like that

[waxen rivet]

ah ok

[prisma jolt]

$A \cup (B \cap C) = (A \cup B) \cup C$

[stray reef]

you sure you didnt mistype anything there

[prisma jolt]

yeah

[vital dew]

looksing

[prisma jolt]

chatgpt bruh

[stray reef]

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[prisma jolt]

i mean for latex

$A \cup (B \cup C) = (A \cup B) \cup C$

[vital dew]

looksing

[stray reef]

you're still typoing it

there's a \cap where a \cup should be

[prisma jolt]

no?

the cap is supposed to be there

wait

no i was right

[prisma jolt]

no i was wrong

[hard citrus]

How to find the coefficient of any term in a polynomial of the form (a1+a2+...+an)^k

I know how to do with 2 terms but never heard of a way with more than 2

[golden fossil]

This might be a better channel to put this in. I’ve been asking in the help channels but no one has responded, so maybe someone here could help?

Let $f$ be a function from a finite set $A$ to itself. Prove that $f$ is injective if and only if $f$ is surjective. $\$

I understand why this must be true. in the direction injectivity implies surjectivity: $\$

Assume the function is not surjective. This means $|f(A)| < |A|$. $//$

The codomain and domain are the same set, so $| \text{codom} f | = |A|$. Since injectivity implies that $|f(A)| \ge |A |$ and $f(A) \subseteq A$, we know $|f(A)| \le |A|$. Consequently, $|f(A)| = |A|$. This contradicts with $|f(A)| < |A|$, and thus $f$ must be surjective. $\$

I qualitativly understand the reverse, but am even less sure how to write it out. $\$

Is my reasoning ocrrect, and how can I turn it into a proof? Thanks!!

[vital dew]

Nameless

[wet sedge]

Your proof for the forward implication seems fine enough (assuming you have proved those inequalities with the definition of cardinality and PHP), for the reverse try thinking about the same reasoning on the size of the inverse image

[ashen bane]

Is anyone here familiar with Hierholzer's algorithm(euler circle)

[cursive nymph]

i have an elementary question. I tried to apply multiplication principle to reason about the number of circle permutations (where 123 and 231 and 312 are the same thing, for example)\

so, to each circle 3-permutation we correspond exactly 3 different linear 3-permutations. hence it should be (by multiplication principle)
$$
\left|\text{CirclePerm}\right|=3\cdot\left|\text{LinePerm}\right|
$$

but it can't be true. intuitively, $$\left|\text{CirclePerm}\right| << \left|\text{LinePerm}\right|$$ So what's wrong in my reasoning / application of multiplication principle?

[vital dew]

Sweet Tea 🧋

[cursive nymph]

if to every element of set $S$ we can correspond $n$ elements from a set $T$, then \
ohhh. yeah. lol. nvm

[vital dew]

Sweet Tea 🧋

[cursive nymph]

how could this be right? (highligted in red)
like, if we fix A (in the line I presume), doesn't this completely determine the positions of other letters?

if
_ _ _ A _ _
then the only way to fill in the blanks is as follows
D E F A B C
no?

(I'm 100% this is wrong; I just can't figure out why)

[weary tiger]

The position of A is fixed, you have to fill and permute the other 5 gaps in this, so 5!

Since A is out of the game beforehand, no need to include it and it's equivalent to just linearly permuting B, C, D, E, F, so yes you are correct in this one.

Another way you can think of this is as follows:
Consider four people: A, B, C, D (for simplicity), sitting around a table.
How can you straighten out ABCD, who are sitting on the table, in a line?

Well, we can start with A:
ABCD
Or from B:
BCDA
Or from C:
CDAB
Or finally, from D:
DABC
And we still haven't changed the initial arrangement of ABCD sitting around the table.

And linearly permuting any one of them yields 4! ways

So if you want the distinguishable circular permutations (since ABCD, BCDA, CDAB and DABC counts the same; equivalently being invariant under rotation), it is 4!/4 = 3! = (4-1)!

and you can generalise this argument in a similar fashion to n people.

Note that this logic fails completely when we are counting with respect to objects in the room (not rotationally invariant), or counting the circular permutations of beads on a bracelet for example (not invariant under flipping).

[cursive nymph]

gotcha, thank u!

[cursive nymph]

what went wrong?

it clearly isn't «n!»

oh yeah, forgot «n_i!» in each denominator. now it works

[stray reef]

denominator*

[chilly hemlock]

does anyone know why the number of surjective maps from A to B is

S(kard(A),kard(B)) * kard(B)! ?

[stray reef]

what is S()?

[chilly hemlock]

stirling number

S(n,k) = S(n-1, k-1) * k * s(n, k-1)

[stray reef]

are you sure you did not mistype anything...

[chilly hemlock]

yes i am sure

[stray reef]

$S(n,k) = k S(n-1,k-1) s(n, k-1)$

[vital dew]

Ann

[stray reef]

correct?

[chilly hemlock]

https://math.stackexchange.com/questions/2793311/why-is-the-number-of-surjective-functions-from-an-n-element-set-to-a-k-eleme

no don't think so

[stray reef]

$S(n,k) = k S(n-1,k-1) s(n, k-1)$ differs a lot from the definition of stirling numbers (of both kinds) that i know about. also what's $s$?

[vital dew]

Ann

[chilly hemlock]

oh sorry

S(n,k) = S(n-1, k-1) + k * s(n, k-1)

[stray reef]

WHY DID YOU SAY YOU WERE SURE

[chilly hemlock]

because i thought u meant the other one 😭

[stray reef]

your math SE post contains a lemma with proof

did you read it? Y/N

@chilly hemlock

well i guess more like "yes i read it / no i didn't read it / reading it right now"

[chilly hemlock]

@stray reef i just found it when i was writing it in the server

im reading it after i

ve eaten

sorry wasnt online when u wrote

[wintry pier]

Hi, does anyone have an idea of how to prove that given a finite, non empty set called A and S=$\bigcup_{m\in \mathbb{N}_{>0}}A^m$, then $#S=\aleph _ 0$

[vital dew]

Neo

[wintry pier]

I thought about the definition of finite sets so there must be a function $f_m: A^m\rightarrow I_{#A^m}$ bijective function with $I_n={1,2,...,n}$

[vital dew]

Neo

[stray reef]

do you not have the result of "countable union of countable sets is countable"?

[wintry pier]

Let me check the theorical part I was given

nope

Just that A, B countable set, then AuB is countable, but I know I can do something with that, and prove that countable union of countable sets is countable

is that the only path?

[stray reef]

anything else is just unnecessarily painful imo.

i mean like ok

you could describe it informally

[wintry pier]

wait

here we have a cardinal

I need to prove that the union's cardinal is aleph zero

[stray reef]

yes

you need to prove it's countably infinite

[wintry pier]

but union of countable sets doesnt mean the union cardinal will be aleph zero

[stray reef]

it's a union of countably many at-most-countable sets.

[wintry pier]

but if I have a set A={1} and B={3,4}, both are countable sets, but the unions cardinal is 3, not aleph

[stray reef]

ok let me be more precise then

it is obvious that the cardinality of your union is at least aleph-null.

if it is not obvious, say so now, because otherwise i'll assume that it is.

[wintry pier]

its not that obvious for me, but we can assume that

oh wait

nvm

[stray reef]

each A^m has cardinality at least 1

[wintry pier]

yes

[stray reef]

and they are all disjoint and there is countably many of them being unioned

anyway ok like

there's an explicit-ish bijection that can be constructed

which i will NOT be writing down an "explicit formula" for

[wintry pier]

np, any hint is ok

[stray reef]

so first im gonna take A as {1, 2, ..., n} bc by assumption it is in bijection with such a set (being finite and nonempty)

then you can make a list that looks like this:

1
2
...
n
(1,1)
(1,2)
...
(1,n)
(2,1)
(2,2)
...
(2,n)
... ...
(n,n)
(1,1,1)
(1,1,2)
...
(1,1,n)
..........

do you get the idea

[wintry pier]

yup

[stray reef]

yeah thats how you do it

[wintry pier]

ok I think I got it

[wintry pier]

its kinda a function that mixes the idea of that latex?

[stray reef]

... i guess

[wintry pier]

kk Ill try to put it formally, tyyy

[distant otter]

Do you guys know how to approach the proof of (iii) here? I was able to prove (ii) using limit ratios for subsequent values: $\lim_{n\to\infty}a^{n+1}/a^n=a > \lim_{n\to\infty}(n+1)^C/n^C=1$ since we know $a>1$. Any thoughts on how to do (iii)?

[vital dew]

SteveArwen

[twilit sundial]

l'hopital's rule should work

[distant otter]

Is it necessary to assume $\alpha>C$? So you could reason that you would apply L'Hôpital's many times until you get something of the form $1/n^{\alpha-C}$. I feel like it should also work for $\alpha\leq{C}$ but it's still confusing me...

[vital dew]

SteveArwen

[weary tiger]

I think the reasoning here has to do with transitivity of congruences, but the explanation is still somewhat unclear. Whats the reason why you can say "if x is a solution, then x ≡ -8 ≡ 6 mod 7?"

[tame bronze]

,iam dying

[vital dew]

Removed the studying! role from you.

[tame bronze]

How exactly can you use Schr¨oder-Bernstein Theorem for this?
The solution I got for (a) is attached

[stray reef]

from $3x \equiv 4 \pmod{7}$ you get $-6x \equiv -8 \pmod{7}$, and then you replace $-6$ with $1$, and $-8$ with $6$, to end up with $1x = 6 \pmod{7}$.

[vital dew]

Ann

[weary tiger]

Ty, I’ve got another question…if x ≡ 4 mod 5. What makes it x ≡ 4 mod 15, ≡ 9 mod 15, and ≡ 14 mod 15 and only these for this problem? @stray reef

[stray reef]

or, not and.

write out all the possible remainders of x modulo 15, see which ones of those give 4 when divided by 5.

[vapid oxide]

Best guess is to construct two injective functions in each direction. One direction follows by inclusion. For the other direction, think piecewise.

[ancient ermine]

Does anyone know how to use Wolfram to generate truth tables for prediacte logic such as (∀x∃y∃zS(x,y,z))→(∀x∀y∃zS(x,y,z))

[tame bronze]

thanks

[ancient ermine]

or symbolab?

[stoic axle]

If I have a set of points on a circle. How many triangles can I draw such that the vertices of the triangle must be elements of the set

[brave rock]

Think about what you need to choose from a set to define a triangle.

[stoic axle]

A triangle need three points

So each point need to choose 3 points

so it's either nP3 or nC3

I feel like it's nP3 because arrangment is necessary

But when I tried it with 4 points it resulted in 4 different triangles not 6

Idk why

[stray reef]

why? does it matter if we pick our three points in the order A, B, C or the same three points in the order C, B, A?

does this give us two different triangles?

[fringe turret]

Suppose that SmartphoneA has 256 MB RAM and 32 GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of "If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera."
A naive question, what will be the output of "Smartphone B has more RAM and more ROM than Smartphone C". I believe it will be False, because no doubt the RAM of the Smartphone B is the highest, but the ROM of both of them are same, and we are talking about more than, which indicates inequality and because of AND connective the whole proposition is False.

Am I right?

[stray reef]

do you mind organizing the data of the smartphones into a table

cause it's kind of hard to read in prose

[stray reef]

@ember marsh so as far as i understand, here is our setup:

we have the sets A = [0,1], S = R, T = R

we have the function g: A -> T given by g(x) = 47 for all x ∈ A

i have additionally defined two functions f_1, f_2 : S -> T as follows:

$f_1(x) = \begin{cases} 47 & x \in A \ 420 & x \notin A \end{cases}, f_2(x) = \begin{cases} 47 & x \in A \ 69 & x \notin A \end{cases}$

[vital dew]

Ann

[stray reef]

as i understand it, your question is: why are f_1 and f_2 extensions of g?

did i understand your question correctly?

[ember marsh]

yes

yes

[stray reef]

well

if x ∈ A, what is f_1(x)?

[ember marsh]

If $g : A \to T$ is a map of $A$ in $T$, every map $f : S \to T$ such that
$$f(x) = g(x) \quad \forall x \in A$$
it is called a prolongation of $g$ on $S$

[vital dew]

alee

[ember marsh]

i didnt understand this very well

[ember marsh]

47

[stray reef]

is "prolongation" a translation from a different language?

[ember marsh]

yes

[stray reef]

from what language?

[ember marsh]

italian

wait

extension

[stray reef]

ok, i don't speak that unfortunately

[ember marsh]

is = prolongation

[stray reef]

but yes extension is the usual word for this in english

[ember marsh]

i checked

yes

[stray reef]

exactly.

so f_1(x) = g(x) for all x ∈ A, yes?

[ember marsh]

yes

[stray reef]

so then do you agree that f_1 is an extension of g?

[ember marsh]

actually I'm kind of doubtful, why $f_1x = 47, \quad \forall x \in A$, how can you tell it's $47$?

[vital dew]

alee

[stray reef]

i declared it so.

$f_1(x) = \begin{cases} 47 & x \in A \ 420 & x \notin A \end{cases}, f_2(x) = \begin{cases} 47 & x \in A \ 69 & x \notin A \end{cases}$

[vital dew]

Ann

[stray reef]

look at these definitions.

do you understand them?

[ember marsh]

yes

[ember marsh]

yes

[stray reef]

ok

do you agree, by the same reasoning, that f_2 is also an extension of g?

[ember marsh]

yes

[stray reef]

ok

and do you agree that f_1 ≠ f_2?

[ember marsh]

yes, becauseo the two functions take on different values ​​when x does not belong to A?

[stray reef]

exactly

[ember marsh]

ok

but is the extension a subset of x?

@stray reef

[stray reef]

????

that doesn't make any sense

at no point did we ever use the letter x to denote a set of any kind,

so your question is purely nonsensical

[ember marsh]

If $g : A \to T$ is a map of $A$ in $T$, every map $f : S \to T$ such that
$$f(x) = g(x) \quad \forall x \in A$$
it is called an extension of $g$ on $S$

[vital dew]

alee

[ember marsh]

i still dont understand this

😢

[stray reef]

didnt we just walk through an example of this definition in action?

so like

ok let me try to explain this informally then

[ember marsh]

without example pls

[stray reef]

we have a function g: A -> T defined on a "small" set A

we have a different function f: S -> T defined on a "bigger" set S (which contains A as a proper subset)

when we say "f is an extension of g" we mean that f agrees with g at all points where that's possible to talk about

(i.e. all points of A)

[ember marsh]

?

[stray reef]

what's unclear?

[ember marsh]

this part

[stray reef]

what part of this sentence:

when we say "f is an extension of g" we mean that f agrees with g at all points where that's possible to talk about

is unclear to you?

[ember marsh]

that f agrees with g at all points where that's possible to talk about

[stray reef]

to agree means to have the same output.

for functions, specifically.

i dont know how else to explain it lmao

[ember marsh]

im thinking

[stray reef]

i think you might be OVERthinking.

this isnt a complicated concept.

[ember marsh]

that is, if I calculate f in the domain of g (f is different from the function g), do I find that the values ​​of f are equal to those of g (the output values)?

[stray reef]

yes that is what it means

[ember marsh]

ah ok

So going back to the two examples, those were extensions of g , because in the range of g (f_1 and f_2 calculated in the domain of g) did they have the same output value?

so f_1=f_2=g=47 for all x in A

[stray reef]

yes

that's a repeat of what i walked you through

we can repeat it another nineteen thousand times if you want

[ember marsh]

i understand

thank you

[fringe turret]

Sure,

Given question

Let p and q be the propositions
p : It is below freezing.
q : It is snowing.
Write these propositions using p and q and logical connectives (including negations).

• It is either snowing or below freezing (or both).
• Either it is below freezing or it is snowing, but it is not snowing if it is below freezing.

In the first proposition $p \wedge q$ makes sense because it is mentioned to include "both true" case.

[vital dew]

ĐARK々MÁTTER

[fringe turret]

In the second one, there is no such condition, why the answer use $(p \vee q) \wedge (p \to \neg q)$, instead of $(p \oplus q) \wedge (p \to \neg q)$

[vital dew]

ĐARK々MÁTTER

[fringe turret]

I found something on this https://math.stackexchange.com/questions/2130327/does-either-make-an-exclusive-or But the link to English SE says otherwise.

Does this article means https://english.stackexchange.com/questions/40950/is-either-only-used-with-two-options what the accepted answer in the maths SE mean?

[gritty garnet]

mmm how to get this started

[stray reef]

don't post the same problem in multiple channels.

[vital dew]

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

[solar gazelle]

Hey, I'm not sure if I am getting this question or even the right answer the question is:

You are an elementary teacher who has a class of 9 students. Every day when it is time
for recess your class lines up to go outside. There are two problem students in your class,
Smith and John, who each will cry if they are not in the first 3 or last 3 spots in line.
How many ways can the students line up to go outside such that both Smith and John
will not cry?

The way how I am thinking of this is there is in total 9! permutations but im not sure where to go after that, im not sure if we can use the division rule here as my understanding of it is you can use it when you have multiple preimages for 1 image and you divide it by how many images each preimage has. Assistance is greatly appreciated.

[twilit sundial]

proceed constructively

how many ways are there to place smith and john

assuming nobody else has been placed at that point yet

[solar gazelle]

sorry im not sure if I understand but if I understand correctly John and Smith can only be placed in either the first 3 or the last 3 so you can have JXS,SXJ,XSJ,XJS,SJX and JSX which is 6 for both first 3 and last 3?

[stray reef]

JXS,SXJ,XSJ,XJS,SJX and JSX
this is strange

there are 6 spots that the problem kids can go into but it isn't because of this

_ _ _ x x x _ _ _

j and s can go into any of the spots marked with _ and ONLY in those spots.

[rare minnow]

how does one not hate modular arithmetic

[cerulean radish]

Why would one hate modular arithmetic

[rare minnow]

i hate all math except graph theory

maybe i just like drawing stuff

i find math i can draw more fun

[cerulean radish]

Why would one hate all math except graph theory then; That didn't really answer my question

[rare minnow]

cause i feel like ur just writing paragraphs of symbols

no fun

time consuming

u learn smth then u suddenly forget it

• very lonely subject

also rip the TA reading my shit

[cerulean radish]

You are writing a paragraph of symbols right now too is it fun

[cerulean radish]

If so, then there's a detail you missed here

[rare minnow]

yea but the difference between writing symbols here is that it does not take 6 hours to come up with shit

or even longer

[cursive nymph]

I mean, you can write without math symbols (ie in plain English) if that is more comfortable for you

instead of
$$
\forall \varepsilon > 0 , \exists N \in \mathbb{N} \text{ s.t. } d(a_n, L) < \varepsilon \text { if } n \ge N
$$

u can just say the sequence will be eventually eps-close

[vital dew]

Sweet Tea 🧋

[cerulean radish]

The problem rather seems to be the number of hours and them being unawarding

[rare minnow]

im comfortable with latex, in fact i take lecture notes with them, it's more about the amount of time required to come up with solutions to certain problems, or understand concepts, and the lack of visuals

graph theory, and sometimes combinatorics things are fun

since u can draw stuff

like slots

dots

circles

visually more intuitive

[rare minnow]

u got that right

[tribal wasp]

I'd really appreciate any help with this problem. I tried splitting it up into two conditional statements, then I proved each one, by basically arguing that there aren't common elements in each. I feel like this isn't enough though.

[stray reef]

I tried splitting it up into two conditional statements, then I proved each one, by basically arguing that there aren't common elements in each. I feel like this isn't enough though.
show us your proof in its entirety

[tribal wasp]

Okay

Here it is

[stray reef]

this line is icky

i guess your idea's kind of there, but it's buried under some layers of bad wording.

what you're using isn't the definition of cardinality -- at least, not directly -- but rather the inclusion-exclusion formula for 2 sets:

|A ∪ B| = |A| + |B| - |A ∩ B|

[tribal wasp]

The inclusion exclusion principle?

[stray reef]

yes

and once you namedrop that one, it becomes clear that |A ∪ B| = |A| + |B| <=> |A|+|B|-|A∩B| = |A|+|B| <=> |A ∩ B| = 0

[tribal wasp]

Could the inclusion exclusion principle be proven too?

[zealous oracle]

anybody up for discussion on this

#combinatorial-structures message

[tribal wasp]

Could I use the inclusion-exclusion principle to prove this:

[brave rock]

No, it's false.

[tribal wasp]

Yea that's what I thought too, thank you, I'll try use a counter-example.

[ember marsh]

Consider a relation $R \subseteq A \times B$, then:
$$R = G(f) \Leftrightarrow \forall x \in A, \exists !y \in B : xRy$$
with $f : A \to B$ application and $G(f)$ graph of $f$. \ $$PROOF$$
$\Rightarrow$) The application $f : A \to B$, by definition, associates with each element $x \in A$ and only one element $y \in B : f(x) = y$. Then it follows that:
$$(x,y) \in G(f) \Rightarrow (x,y) \in R \Rightarrow xRy.$$
$\Leftarrow$) We define a map $f : A \to B$ which makes every $x \in A$ correspond to the unique element $y \in B$ such that $xRy$. Therefore $y = f(x)$ is equivalent to $xRy$ and therefore $R = G(f).$

[vital dew]

alee

[ember marsh]

I dont understand the proof 😦

[tribal wasp]

@stray reef Do you mind helping me understand what part 2 is asking in this question? Or anyone else too.

[stray reef]

!noping

[lofty cloud]

Please do not ping individual helpers unprompted.