discrete-math

[brave lava]

or something?

idk

[pale epoch]

maybe

[brave lava]

https://i.imgur.com/KBHvlG3.png

it was the . lmao

he kept repeating it in his lecture

so I put that for multiplication

thanks though

that made a lot of sense

👍

[near root]

True or false:
B={1,2,3..., m}
C={m+1, m+2, m+3..., m+n}
A = B U C
Number of functions f:A->A that fulfill |f^-1[{1}]| = m and |f^-1[{2}]| = n is C(m+n, m).

I think that's true since after picking m amount of numbers you're left with an n amount of numbers to pick from that you pick n amount that comes to n over n aka 1 so it's C(n+m, m) * 1

[pale epoch]

is C binomial?

@near root

if yes, you are right, but your argument is a bit short

[near root]

Binomial? Lemme google that

[pale epoch]

eh

binomial coefficient*

[near root]

I think B is jut a group in this case

Just a group*

[pale epoch]

B is just a set

its just a weird way of saying that A is the set of the first n+m natural numbers

[near root]

I think C is just a group of natural numbers

Since B is natural numbers up to n

So...

[pale epoch]

wait what do you mean by group?

[near root]

I meant set

[pale epoch]

ok

[near root]

Forgive my poor math English

[pale epoch]

A, B and C are sets

[near root]

Yes

[pale epoch]

group is a very specific term in mathematics

and none of those are groups

[near root]

Is my explanation right?

[pale epoch]

it's not wrong

it's a bit short

you could/should add what are you choosing

why are those the only choices to make

[near root]

Because you already picked an m amount of numbers therefore you're left with an (n+m)-m numbers to pick from and you need to pick n amount of numbers

Is that not sufficient?

[pale epoch]

but what are you picking

when you pick m out of n+m numbers

what are those m numbers

[near root]

They're the numbers that are all sent to {1}

[pale epoch]

exactly

you first choose the m numbers that are sent to 1

and then choose the numbers sent to 2

and get that result

i would add that to the explanation, then its better

[near root]

x1+x2...+x7 = 10
The number of solutions that none of the numbers is a multiplication of 2 or 3 is the coefficient of x^10 in the opening(don't know the right term for it in English) of (1+x+x^5+x^7)^7

I have no clue how to use the generating function

[near root]

I know 1 is there because it's x in the power of 0, but isn't 0 considered to br a multiplication of 2 and 3 ?

[stray reef]

x1+x2...+x7 = 10
The number of solutions that in which none of the numbers is a multiplication multiple of 2 or 3 is the coefficient of x^10 in the opening(don't know the right term for it in English) expansion of (1+x+x^5+x^7)^7

hmm... you're right, this expansion does allow the x_i to be zero

and 0 is a multiple of 2 and also of 3

are you sure you wrote down the problem correctly tho

@near root

[near root]

It's true or false but yeaa

[stray reef]

why didn't you say it was a t/f question

[near root]

Mb

So that comes out as false because 0 is a multiplication of 2 and 3 right?

[stray reef]

multiple

[near root]

?

[stray reef]

i'm trying to correct you

you're using the wrong word

[near root]

Is it false though?

[stray reef]

yes, it is false

but you're using the word multiplication where you should be using multiple

[near root]

One more question if you don't mind, the x1+...+x7 = still stands. Number of solutions where exactly 3 unknown numbers are equivalent to 2 is C(7,3).
I pretty much just did D(4, 4), is it right ?

[stray reef]

equal*

also holy fuck how hard is it to acknowledge something when i point it out for the second time

also what's D?

[near root]

C(n-1+k, k)

[stray reef]

exactly three unknowns are 2... the other four are forced to be 1 since i assume they must be positive

[near root]

They could be zero

[stray reef]

oh they could? hold up

[near root]

No condition restricts you to fill every single one of them

Yea

[stray reef]

(2,2,2,0,0,1,3) would be a valid solution but it doesn't get included in the C(7,3) count

[near root]

Why isn't it included there?

[stray reef]

because C(7,3) counts the permutations of (2,2,2,1,1,1,1)

looks like you want the coefficient of x^10y^3 in (1+x+x^2y+x^3+x^4)^7

[mint bane]

can someone help me with this proof please

i have predicate and base case set up ofc

this is what i got so far

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞:

[nova pewter]

There : p

[pale epoch]

exactly what confuses you?

[nova pewter]

I don't know if you're allowed to have a compliment of the union sign

[pale epoch]

$\overline{\cup}$?

[vital dew]

Lochverstärker:

[nova pewter]

yes, is that allowed?

[pale epoch]

what is it supposed to mean

[nova pewter]

I don't know either

[pale epoch]

is there an example where this actually appears?

[nova pewter]

well, I was thinking the last example in the image there

because it double negates

[pale epoch]

but

$C\coloneqq \overline{A} \cup \overline{B}$, then this is just $\overline{C}$

[vital dew]

Lochverstärker:

[pale epoch]

which is perfectly fine

or maybe $\overline{(\overline{A} \cup \overline{B})}$ makes it clearer

[vital dew]

Lochverstärker:

[nova pewter]

Ok, that makes sense. I think it's just that sets confuse me

thanks for the help

$ \langle 3,1 \rangle \in (A, \geq) $

[vital dew]

Larz:

[nova pewter]

is this correct notation?

Because after my understanding, (A, greater or equal) is a set?

[pale epoch]

is it?

what is this supposed to mean in words

[nova pewter]

Oh, I struggle with translating math to english, but I can try

[pale epoch]

i mean right now this makes 0 sense to me

so it's better you tell me what you want to say, to see where this goes wrong

[nova pewter]

So I'm basically saying that (3,1) which is a 2-tuple, is part of the ordered set of (A, greater or equal)

Let's say, A = {-3, -2, -1, 0, 1, 2, 3}, then (A, greater or equal) is the ordered set. Does it make sense? ^

[pale epoch]

ok

what you want to say makes sense, it does not correspond to the notation above

the easiest way to write that down is just $3 \geq 1$

[vital dew]

Lochverstärker:

[nova pewter]

Well, yes that's true haha

[pale epoch]

depending on how you formalize what exactly an order (or a function for that matter) is, you can say other things

but that's really obfuscating things

[nova pewter]

Thanks though, I am totally overcomplicating things

[pale epoch]

in general, don't use \langle, \rangle for tuples, it's just (,)

and (A, >=) is technically a set

[nova pewter]

Really? I've seen they've been used elsewhere.

[pale epoch]

or any tuple is

but we dont talk about elements in tuples

[nova pewter]

Okay, thanks.

[pale epoch]

depending how you formalize mathematics, everything is a set

but in this example, you could probably not tell me how an element of $(A, \geq)$ even looks like

[vital dew]

Lochverstärker:

[pale epoch]

so better not talk about them

[nova pewter]

I suppose (A,>=) just gives you the relation between elements

[pale epoch]

it just tells you that we have a set A and some kind of relation called >= on A

just a convenient way to group information

in most contexts you would not even mention >= and just talk about A

[nova pewter]

Riiight right.. That makes a lot of sense actually.

But it suddenly makes sense WITH context.

[swift agate]

Prove that the following wff is a valid argument: (∀x)[S(x)→(∃y)(P(x,y)∧T(y))]∧(∃x)(C(x)∧S(x))→(∃x)(∃y)((C(x)∧T(y)∧P(x,y))

Could someone help me with this problem?

[lyric pumice]

@swift agate It looks like a parenthesis is missing at the end.

[swift agate]

it is a difficult problem for me ... i had one other one i was having trouble with that might be easier.... either prove that the wff is a valid argument or give an interpretation in which it is false: (∃x)[R(x)∨S(x)]→(∃x)R(x)∨(∃x)S(x)

so for the second problem I have 1. (∃x)[R(x)∨S(x)] Hyp 2. (∃x)R(x) Hyp by deduction 3. R(a)∨S(a) from 1 by ei 4. R(a) from 2 by ei

[nova pewter]

$ \emptyset \cap \overline{B} = U \cup B $ ?

[vital dew]

Larz:

[nova pewter]

This just looks wrong, what am I doing

[pale epoch]

no

no idea

[nova pewter]

haha

[pale epoch]

$\varnothing \cap A = \varnothing$ for every set A

[vital dew]

Lochverstärker:

[nova pewter]

Oh, right that makes sense

[pale epoch]

so that is true iff U is the empty set i guess

[lyric pumice]

@swift agate The second statement is clearly valid.

@swift agate The first statement is clearly valid.

Let a be such that C(a) and S(a). Then using the universal instantiation, S(a) implies P(a,b) and T(b) for some b. So, a and b are such that C(a) and T(b) and P(a,b).

[swift agate]

@lyric pumice thank you I am still having trouble with it but thanks for responding..I sent email to professor so hopefully I will understand soon

[bronze wagon]

How would I solve this problem?

[last timber]

use truth tables

draw table for p iff q and for (if p then q) AND (if q then p)

[bronze wagon]

yeah Im kinda confused on how to make the truth table

[wintry schooner]

hey, could anyone show me some guidance on how to solve this problem, new to discrete maths so mind if its very basic to you 😛

[unreal stump]

Don't ask whether someone will help. Just ask

[wintry schooner]

For each of the following binary relations, determine whether it is
reflexive, symmetric, antisymmetric or transitive. For each point, state your reasoning in
proper sentences.

I have a feeling it may be antisymmetric but im not sure if Im on the right track

or how I could explain my reasoning

[stray reef]

it's vacuously asymmetric because it's impossible for two parties to both have more seats than the other

[wintry schooner]

oh okay thanks

i see now

so it would not be either one of these? reflexive, symmetric, antisymmetric or transitive

because my question asks to whether it is either of them

[stray reef]

it is transitive

seats(N) > seats(L) and seats(L) > seats(M) implies seats(N) > seats(M)

[wintry schooner]

so its transitive because you cannot have two parties where both have more seats than the other?

ahhhh yes

ahh okay thanks bro

[stray reef]

please don't bro me

[wintry schooner]

understand a bit better now cheers

[stray reef]

but yw

[wintry schooner]

oh

soz

[gritty crescent]

Let $A$ be the set ${1,2,...,20}$. Fix two disjoint subsets $S_1$ and $S_2$ of $A$, each with exactly three elements. How many 3-element subsets of $A$ are there, which have exactly one element common with $S_1$ and at least one element common with $S_2$?

[vital dew]

TedNotKaczynski:

[gritty crescent]

I would like to know what is meant by 'fixing two subsets'-I'm guessing it means I first choose 3 elements from those 20, then 3 more from the remaining 17, and then proceed?

[stray reef]

no

S1 and S2 are predefined

[gritty crescent]

Oww, I see.

[stray reef]

the answer is actually just ||3 * 3 * 14||

(open at your own risk)

[gritty crescent]

Hmm, I wouldn't see that spoiler yet.

[stray reef]

wait no

i misread

that there is wrong

[gritty crescent]

So I choose any one of the three elements of S1, then choose 1/2/3 elements from S2

?

[stray reef]

you can't have three elements of S2

you'll run out

[gritty crescent]

Oh, right, I need a 3 element subset.

So I'm supposed to choose 1 out of S1(3 choices), then select either 1 out of S2(again, 3 choices) and 2 out of the remaining 14 elements, or 2 out of S2 and the remaining element from the 14 elements?

[stray reef]

1/1/1 or 1/2/0 lol

not 1/1/2 or 1/2/1

[gritty crescent]

I don't understand your notation.

Oh

Got it. Thanks.

[weary tiger]

@bronze wagon

did you get the truth table question?

[prisma osprey]

I'm trying to come up with S and T such that f:S->T, g: T->S are both injections or surjections but f != g^{-1}, where S and T are finite sets

I've tried a few dfiferent sets for S and T such as like even and odd numbers between 0 and 10, or like pairs of numbers

But I ca'nt come up with any f and g that are'nt just inverses of each other?

err is this a discrete math question even?

[pale epoch]

let one function be the identity the other not?

for T = S

[quaint star]

@prisma osprey Let S = T = {1,2,3,4}. Let f map 1 to 2, 2 to 3, 3 to 4, and 4 to 1. And g map 1 to 3, 2 to 4, 3 to 1, and 4 to 2.

[prisma osprey]

Oh wait

Oh

I did nto see that lOL

thank you

[weary tiger]

Various keywords are used to specify this statement: descendants of ALGOL use "for", while descendants of Fortran use "do".

its heating up here

[sleek island]

Does anyone have any idea how to solve this?

[sleek island]

<@&286206848099549185>

[spring mica]

Does anyone know why there are parenthesis around the second part?

[pale epoch]

to tell you how to read that statement

implication is not associative

[spring mica]

@pale epoch but in my proof, where do i put parentehsis

[pale epoch]

in the last step you are transforming $(p \lor r)$ to $(\neg p \implies r)$

[vital dew]

Lochverstärker:

[pale epoch]

so there

[spring mica]

why do i put parenthesis around it

as opposed to leaving it without parenthesis

@pale epoch

[pale epoch]

because implication is not associative

$$(0\implies 0)\implies 0 \equiv 1 \implies 0 \equiv 0$$ but $$0\implies (0\implies 0) \equiv 0 \implies 1 \equiv 1$$

[vital dew]

Lochverstärker:

[pale epoch]

so without parenthesis its not clear how the statement is to be interpreted

[weary tiger]

I think that the first set of quantifiers is false, and the second is true. But I keep overthinking it, can anyone confirm?

[pale epoch]

the first statement is false, the second is true

it suffices to give a single counterexample to disprove the first

[weary tiger]

@pale epoch Phew thanks, for some reason two quantifiers of the same type keep messing with me

[pale epoch]

and it suffices to give a single example to prove the second

[weary tiger]

Would the reasoning behind the first one being false be that one could choose a y value that could be lower than x?

And the reasoning behind the second one being that there is a definite set of values x and y that make the statement true?

That's my logic^

[pale epoch]

you are correct on the second

on the first you probably think the right thing, but the argument is sloppy

for example -10 < 1, but 1^2 = 1 <= 10000 = (-10)^4

[weary tiger]

Oh shoot lol

[pale epoch]

i say "but" even though the statement is true

i.e. this is not a counterexample

but as i said, it suffices if you find any counterexample

[weary tiger]

@pale epoch Thanks, i'll try to practice more proof by contradiction. Once again appreciate the help

[weary tiger]

doing this problem

I think that this is basically the cartesian product of (1,0), (-1,0), (0,1), (0,-1) and [0,1]

I also have to sketch the cartesian coordinates, so does that mean this is a 3 dimensional graph of a cyclinder?

I was trying to find easy plots to point so I ended up doing the cartesian product between the radius and the points

sorry about that

if it was x^2 + y^2 < 1 the line would be dashed instead of solid right?

when drawing the cyclinder?

a shaded circle

ah that makes sense

because [0,1] is 0..1

makes it a lot easier to visualize that way thank you

that's pretty interesting

a donut?

also and elipse

[daring beacon]

(b(a\c) is always b right?

and does A^c means everything that is not in a

[daring beacon]

Does set A^c means every set considered

[shut sundial]

i thought it meant the complement of A, so everything thats not A?

How do I read L = { x : ∃yℇ{a,b}*(x=ya)} and also what does it mean?

Also is there a good refresher pdf or something I could use to review all the symbols used in Discrete Math?

[daring beacon]

Wikipedia has a page on it for basic ones

Thanks it is the compliment but I was wondering if it means that every other set that isn’t A. So if there is set A,B,C than than A^c means set B, and,C

[shut sundial]

yes I think you are correct

[honest barn]

Who needs a superset, just take its complement in the entire universe of objects

[shut sundial]

oh yeah gotta consider the universe

[spring mica]

@pale epoch is this the same as x<0 ---> x^2 > 0

[weary tiger]

i think theyre just pointing out that the square is gonna be positive

[spring mica]

yeah it is

but is that equivalent notation @weary tiger

this is what it says in my textbook

[weary tiger]

yes that notation is equivalent

i dont think it was intended to be super formal though lol

looks more like just pointing out a hint to the reader to me, but i dont know the context

[woeful galleon]

can i get some help on here ? i am a little lost

[weary tiger]

consider the hint and the power rule of exponents

it might also be more obvious if you consider a simple base like 2 instead of e

[woeful galleon]

struggling to understand lol

[weary tiger]

2^(2x) can be written as (2^2)^x, which is 4^x

which grows faster than 2^x

[spring mica]

The textbook did S(m,y)

but i just did S(x) where x is the mail message

how do i know when to get more specific @weary tiger

[weary tiger]

is that the full answer?

[spring mica]

no

hold on

this is the full answer

This is what i did

where S(x) x = any mail message and s(x) is when its larger than 1 megabyte

@weary tiger

[weary tiger]

i wouldve done the same i think, since our number of megabytes wont vary

maybe its more formal to attach a variable to every number mentioned

[spring mica]

thank you so much!

[spring mica]

@weary tiger do you know what the A means here

in question 46

I can't see how its a predicate

since it dosen't take anything as input

[weary tiger]

u dont need to know what it is, just know that it holds some variables, just like P(x)

it just doesnt take input

[spring mica]

wdym by holds some variables

how can something hold variables but not take in input

A = x + y + z

[weary tiger]

A can be a list of numbers from 1 to 10, or the name of every person in group A, for example

[spring mica]

oh gotcha

@weary tiger why is the middle quantifier an exists

while the outer two are for all

i'm so confused

also why does the limit definition account for error

[weary tiger]

error?

[gritty crescent]

I guess you mean that for a given choice of delta, there will be some tolerance range in terms of epsilon(I've seen that being used as error margin in Thomas' Calculus in an engineering context)

[bold schooner]

Hey guys, Ive been struggling trying to get this question, could someone please help me out with this?

[pale epoch]

what's the problem?

[bold schooner]

I'm not really understanding the use of quantifiers here, and tbh im not sure how to approach this question at all

[pale epoch]

just read as "there exists a y in Z, such that ..."

(a) is just plugging in values

(and some algebra)

[bold schooner]

(a) makes sense, I set the equation to 19 and 11 and i solved for y and I saw whether they were integers to see if they were true or false. but b and c arent making any sense to me

[pale epoch]

what is the definition of "open sentence" and "mathematical statement"

[bold schooner]

Open Sentence: A sentence that contains a
variable, where the truth of the sentence is determined by the value of the variable chosen
from the domain of the variable
Mathematical Statement: A statement is a sentence that has a definite state of being either true or false

Taken straight from the textbook^

[pale epoch]

then just plug in P(x, n) into the respective statements and see if the truth value still depends on a variable

i.e. if there is a variable not bound by a quantifier

[bold schooner]

well the one thing i did notice was that in b there were more variables than quantifiers

and n was not bound by a quantifier, whereas in (c) all the variables were bound on a quantifier

[pale epoch]

exactly

this makes (b) an open sentence according to your definition (its truth depends on the value of n chosen)

and it makes (c) a mathematical statement

namely "for all positive integers n, there are integers x and y, such that x^2 - xy + y^2 = n"

[bold schooner]

ur last statement is for c im assuming?

[pale epoch]

yes

[bold schooner]

thank you so much @pale epoch ! is my method for (a) correct as well?

[pale epoch]

yes

plug in values, solve for y

[bold schooner]

alright thanks alot man!

[weary tiger]

$S:=:\left{1,2,3,4\right}$

[vital dew]

The-Elite:

[weary tiger]

$S\backslash 4$

[vital dew]

The-Elite:

[weary tiger]

are you allowed to do this for set complement?
like use a single value (i.e. 4 in this case)

or are you only allowed to use two sets for complement

[pale epoch]

only sets

[weary tiger]

oh

[pale epoch]

try $S\backslash {4}$

[weary tiger]

so i let E = {4}, I can do S\E?

[vital dew]

Lochverstärker:

[weary tiger]

is that correct notation?

the one you did

[pale epoch]

why not?

[weary tiger]

just curious

thank you for the help

[pale epoch]

yes, it is correct

[weary tiger]

ok 🙂

[weary tiger]

A little confused on this homework question, I tried putting 4=7 as a statement as one in the last instance and said i was incorrect

I thought statements just have to have true/false values?

[pale epoch]

i would agree

[weary tiger]

With what I put?

Or the 4=7 logic?

[pale epoch]

with

I thought statements just have to have true/false values

[weary tiger]

Yeah exactly

[pale epoch]

4=7 is a statement to me

(that happens to be false)

[weary tiger]

Me too, but perhaps its just looking for statements that are true?

Which in the case would be what I put?

[pale epoch]

the statements you checked are true

do you have notes that define the term "statement"?

[weary tiger]

I do actually

Here:

"An expression that has a definite state of being either true or false"

[pale epoch]

then 4=7 is a statement

[weary tiger]

Exactly

The module isn't being too helpful with saying which ones are incorrect tbh

just saying im flat out wrong instead of which specific ones

I guess ill go with this?

[pale epoch]

the rectangle one is a statement, if A, B, C, D are fixed 🤷

[weary tiger]

Hmm, i said that in the last one too

Let me put the four then

And just see i gues

[pale epoch]

i would put the 3 you had in pic

but like, this is ambigious

[weary tiger]

True true

Ill just try the three then since they're definite

[pale epoch]

i mean, the line and rectangle one

are statements when the variables are fixed

[weary tiger]

they're technically true

that was my thought as well

but perhaps they're looking for a sentence which provides a true or false answer immediately

[pale epoch]

but i can't read your teachers mind

[weary tiger]

me neither man

thanks for the help you're saving me once again

[pale epoch]

it could also be that your teacher thinks the term "some" is not well defined

but in mathematics it usually means "at least 1"

[bold schooner]

can someone explain to me why this is a false statement?

[unreal stump]

"There exists a x in Z,such that y=x^2 for all y in Z"

[bold schooner]

i dont get it

[unreal stump]

The statement is saying if we choose one particular value of x

Then for whatever y we choose,y will be x^2

[bold schooner]

so if i choose lets say 1 for x

to be tru then all integer values of y have to be equal to x^2

[sick swallow]

bruh it is basically saying 1=2

[unreal stump]

The Statement says such a value of x exists

[gusty crag]

https://discordapp.com/channels/268882317391429632/496785905474994186/754745554893930516

all of these are statements except for the one with theta

that's probably why you were marked wrong before, you were missing some of the statements

@weary tiger

[marble haven]

if something is an element of a set, doesnt that imply that it is also a proper subset of that set?

[pale epoch]

$1 \in {1, 2, 3}$, but $1 \not\subset {1, 2, 3}$

[vital dew]

Lochverstärker:

[marble haven]

oh that makes sense

[pale epoch]

however ${1} \subset {1, 2, 3}$

[vital dew]

Lochverstärker:

[pale epoch]

also notice that 1 is an element of {1}, but {1} is not a proper subset of {1}

@marble haven

[marble haven]

oh

I was working with the possible existence of

if G is a subset of P(G), does G exist

(powerset of G)

[pale epoch]

the powerset is the set of all subsets

and every set is a subset of itself

oh

[marble haven]

yeah that;s what I was thinking

@weary tiger

[pale epoch]

wait, yes

the elements of the powerset are the subsets

[gusty crag]

if you allow something like "the set of all sets", then the power set of that set should be the set itself, so if such a set were to exist it would be both an element of and a subset of its power set

but that's putting no restrictions on what a set is allowed to be

I believe ZFC's axioms stop such a set from existing because it leads to contradictions (thank you russell)

[weary tiger]

Anyone familliar with falsifiability of disjunction normal form?

[weary tiger]

what does this C mean?

[pale epoch]

probably complement?

[weary tiger]

it is complement

[signal basin]

$D^c:=X\setminus D$, in which $X$ is the "univers".

@weary tiger

[vital dew]

Schuams:

[signal basin]

Means "all the elements in X but not D".

[weary tiger]

how would i prove this?

[pale epoch]

using the definition of subset

[sick swallow]

this is assuming C is a subset of B right?

[naive saffron]

I feel like they are the same set

[sick swallow]

i think so

[naive saffron]

If you choose some universal set X, say X=A U B U C, and use the fact that B-C = B intersect C^c

and distribute intersection over union

[weary tiger]

what if hypothetically, $B - C$ but B and C do not share any of the same elements?

[vital dew]

maddog:

[weary tiger]

what would $B - C$ be equal to?

[vital dew]

maddog:

[naive saffron]

B

C doesn't need to be a subset of B for B-C to make sense

[weary tiger]

oh

[naive saffron]

Sorry it should be B

[weary tiger]

no worries

i can see why this is true through boolean algebra

but i don't think you can carry over boolean algebra laws with set theory

and i can't speak in the language of proof

[naive saffron]

Well some properties of boolean algebra are similar to those in set theory

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

[vital dew]

Whoever:

[naive saffron]

and $A\cap A=A\cup A=A$

[vital dew]

Whoever:

[naive saffron]

Also $A\cup\varnothing=A$ and $A\cap\varnothing=\varnothing$

[vital dew]

Whoever:

[weary tiger]

$G\backslash \left(T:∪:I:∪:P\right)$

[vital dew]

The-Elite:

[weary tiger]

i'm trying to word this in english. Is it right to say we are removing elements from set T, I and P from set G?

[naive saffron]

Yeah

and you can write

$G\setminus(T\cup I\cup P)$

[vital dew]

Whoever:

[weary tiger]

ok

but would I use OR or AND

we are removing elements from set T, I or P from set G?

we are removing elements from set T, I and P from set G?

[signal basin]

@weary tiger If you are the CS type, then just reduce it to logical statements. That might be easier.

[weary tiger]

CS as in computer science?

[signal basin]

yes

[weary tiger]

ok

that's me

[signal basin]

thought so

[patent fable]

Would anyone be able to help me to understand transitive closure?

If I have the set {1,2,3,4,5} and R={(1,3), (2,4), (3,1), (4,2), (5,4)}, what would be the best technique I can use to solve this?

I understand I can look at the vertices (1,3) and (3,1) to create the point (1,1) or (2,4) and (4,2) to make (2,2) by combining the a of the first vertex and b of the second vertex (after identifying b of the first vertex = a of the second).

Guess the two questions I have are: How can I better understand transitive closure?
What is the best way to resolve this problem?

[naive saffron]

Transitive closure is just the smallest transitive relation containing your original set

and what you did is the best way

Just continue doing so until you can't add any more elements

[patent fable]

the vertices I added were (1,1), (2,2) and (4,5)

are those the only possibilities?

[naive saffron]

Well see if (1,1), (2,2) and (4,5) with what's originally in the set can create more vertices

[weary tiger]

$x_1:+x_2+x_3:=80$

[vital dew]

The-Elite:

[weary tiger]

it could be easier if you write it up and look for potential patterns if thats what you did, i find it easier than just doing all the calculations in the head

like write a directed graph

$0\le x_1\le 40$

[vital dew]

The-Elite:

[patent fable]

ah, duh. (4,5) and (5,4) = (4,4) as well

[weary tiger]

$0\le x_2\le 32$

[vital dew]

The-Elite:

[weary tiger]

$0\le x_3\le 64$

[vital dew]

The-Elite:

[naive saffron]

Yeah

and you can add more

[patent fable]

so, everytime I add a new vertex, check to see if there are any other vertices I can add?

[naive saffron]

Yeah

You need to keep doing so until you can't add anymore

i.e. until you have a transitive relation

[patent fable]

Perfect. So i'm assuming there's no perfect algorithm to find all possibilites. just trial and error

[naive saffron]

Well, you can't say for certain that there is no perfect algorithm

But I don't see any obvious way to speed up the process when the initial set is large

[weary tiger]

$x_1 + x_2 + x_3 = 80$

$0\le x_1\le 40$

$0\le x_2\le 32$

$0\le x_3\le 64$

if i wanted to find B∩C, I do

$x_1 + x_2 - 32 + x_2 - 64 = 80 - 32 - 64 = -16$

which is -14 choose 3

so does that mean that B∩C is just the empty set?

can't get this ever

there

[naive saffron]

@patent fable it turns out you can use Floyd-Warshall algorithm to compute the transitive closure by representing your initial relation as a directed graph: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/Warshall.html, but I think that's much more work than doing it by hand in this case

[vital dew]

The-Elite:

[weary tiger]

I personally find it easier if you represent it with a directed graph, that was what i was taught in my course

it's easier to see patterns that way

for simple problems

[naive saffron]

Hmmm maybe yeah

[weary tiger]

for instance

you will see that (4,5) that u added is too much

[patent fable]

@naive saffron appreciate the algorithm. I'll look into that. I tried the digraph, I just think I'm terrible at drawing paths, so I tried to do the brute force method. I ended up with:
(1,1) (2,2) (4,5) (4,4) (2,5)

Ah, is (4,5) not to be added?

[weary tiger]

dont think so

ill double check

i got (1,1),(2,2),(2,5)

[patent fable]

How do you get (2,5)? The only way I found it was through (4,5)

[weary tiger]

so we have 5,4 and 4,2

which implies 2,5

according to transitive property or w/e its called

R had (5,4) and (4,2) if i recall correctly

but if u write it as a directed graph it would be very easy to see that

[patent fable]

Ohhhh I see it now

[weary tiger]

it's a good way to spot the minimum set to make it fulfill whatever property you want

the directed graph approach

[patent fable]

I see it much clearer now. The brute force method is a bit confusing since you have to keep adding vertices. Does the diagram in anyway show how you can get (2,5) without needing to find (5,4) and (4,2) together?

[weary tiger]

the blue color in the picture i sent shows that thing i talked about i.e 5,4 and 4,2 -> 2,5

okay

so the pattern u need to know

in order to fulfill transititve property

is uh

ill write it

whenever you have 2 vertices like this

i mean 3

then by transitive property it implies that

so thats the pattern u want to look out for

in the directed graph

[patent fable]

So the property states that even if all the paths go in 1 direction, the last vertex can reach the first?

[weary tiger]

ye

[patent fable]

Wow that's nice

I had no idea, that makes it a lot simpler. I didn't see that property in our notes at all

[weary tiger]

ye its nice for simple problems

[patent fable]

I was under the assumption that there was no way back. Thank you

[weary tiger]

idk about if there are more than 3 vertices though

but if there are 3 like the pic

then it works definitely

more than 3 idk

was a time ago i did this

i dont remember fully hehe

[patent fable]

I see, thank you

[weary tiger]

but just learn the directed graph approach and it will be easier

for other properties as well

to spot symmetry, anti-symmetry, reflexivity etc

the directed graph helps in that

the one i showed is for transititve, for reflexivity its easy just self loops

[patent fable]

Okay, I will have to find further instruction on digraphs so I better understand then

I saw reflexive in our text, all vertices must have self-loops to be reflexive

[weary tiger]

ye

[patent fable]

Awesome

[weary tiger]

and then

for symmetry

(y,p) => (p,y) i think thats the definition for symmetry

well probably more like y R p => p R y

uh my memory

😄

[patent fable]

Yes

that's how it's stated, so that's right

[weary tiger]

ye

but that picture is for symmetry

so its very intuitive

[patent fable]

Perfect, and I know there's no way to tell for antisymmetry for the most part based on the graph

[weary tiger]

the arrows just implies a relation between the 2 elements

u can with directed graphs

but i dont remember fully

i mean definitely for simple problems

[patent fable]

Ah, okay I'll look that up then

[naive mural]

I think you did the transitivity thing wrong

[weary tiger]

ye u are right

[naive mural]

An equivalence relation looks like a disjoint union of complete graphs

[weary tiger]

so thats for transitivity

as i said my was a time ago i did this

sorry hehe

but @patent fable u can easily google this

[patent fable]

even then, (2,5) still should exist I think

[weary tiger]

it's 5,2 then i think

[naive mural]

Identity means it’s related to itself so it’s not really a graph

[weary tiger]

i just did it opposite

[naive mural]

Or a simple graph

[patent fable]

Can I ask how you would construct this digraph? @naive mural

Also, @weary tiger, I think because the set is {1,2,3,4,5} and R={(1,3), (2,4), (3,1), (4,2), (5,4)}
(5,4) (4,2) = (5,2)

[weary tiger]

(5,4), (4,2) => (5,2)

ye

[naive mural]

Is it meant to be a transitive relation?

[patent fable]

So the full transitive closure is R = (1,1), (1,3), (2,2), (2,4), (3,1), (4,2), (5,2), (5,4)

[naive mural]

Yeah then just draw all the lines in

[patent fable]

The question in the book is asking for transitive closure of the set {1,2,3,4,5} on the relation R={(1,3), (2,4), (3,1), (4,2), (5,4)}

[naive mural]

And (3,3)

Yeah, so you draw 5 on each side

Label them 1 to 5

And connect them all up that should be connected

[patent fable]

Ahhh, I didn't see (3,3) because (3,1) (1,3) = (3,3).

Alright, so the graph I can utilize when I see 3 vertices connected in 1 path that vertex 1 must always have a connection with vertex 3

1 directed path*

[naive mural]

Just keep updating till you can’t anymore

And draw the final picture

[patent fable]

think I got it. I can't send a picture unfortunately, but I can see now how the paths help determine the links. I got (1,1) (2,2)(3,3)(5,2) for the values not currently in the relation that are needed for transitive closure. I'm not seeing any other paths

[weary tiger]

Use the Principle of Inclusion and Exclusion to determine the number of solutions of
$x_1 + x_2 + x_3 = 80$

$0\le x_1\le 40$

$0\le x_2\le 32$

$0\le x_3\le 64$

[vital dew]

The-Elite:

[weary tiger]

So i'm having trouble with doing (B U C)

where B is the solutions to x2 >= 33 and C is the solutions to x3 >= 65

[hearty stag]

how would you rewrite the power set

would it be x: x subset A * P(B)

which become x: x subset A * x: x subset B ?

the cardinality of this would just be the number of subsets

and the amount of subsets is denoted by 2^ cardinality of a set or |A|

would the answer be 2^m * 2^n ?

[errant bear]

what

|X x Y| = |X| * |Y|

dont think of subsets

(your answer is wrong btw)

[hearty stag]

is it just m*n

[naive saffron]

You need parenthesis

[weary tiger]

Use the Principle of Inclusion and Exclusion to determine the number of solutions of
$x_1 + x_2 + x_3 = 80$

$0\le x_1\le 40$

$0\le x_2\le 32$

$0\le x_3\le 64$

[vital dew]

The-Elite:

[weary tiger]

So i'm having trouble with doing (B ∩ C)
where B is the solutions to x2 >= 33 and C is the solutions to x3 >= 65

cause if x2 >= 33 and x3 >= 65, itll be greater than 80

which will give a negative solution

[lyric pumice]

What is the question?

@weary tiger

[weary tiger]

@lyric pumice i put it in the texit bot

#discrete-math message

[lyric pumice]

You should think of distributions under different restrictions.

[weary tiger]

@lyric pumice

I'm taking a Set S which contains all possible solutions any any restrictions

then i'm taking
set A which is the set of all solution to x1 >= 41
set B which is the set of all solutions to x2 >= 33
set C which is the set of all solutions to x3 >= 65

then S\(A u B u C)

was wondering if i was doing this right

[vital dew]

mathew_soto78:

[hearty stag]

oh how would I do that

[gusty crag]

before I answer that, do you go to hunter

[hearty stag]

yeah lmao

[gusty crag]

aye

a friend of mine literally just asked me for help on that

Are you taking it with cherkas?

[hearty stag]

ohh does he take math 156

[gusty crag]

this is awesome

[lyric pumice]

@weary tiger You need to count.

[gusty crag]

and yeah my friend is also taking 156

[hearty stag]

i got the other professor

[weary tiger]

? @lyric pumice

[hearty stag]

x. huang something

[gusty crag]

ah, when I took 156 I had it with cherkas

[hearty stag]

xiayou

wait do u know henry

[gusty crag]

that name doesn't sound familiar

[hearty stag]

aight but u are in the cs major for fact

ive seen u alot of times

[gusty crag]

I'm a double major, cs and math

[hearty stag]

mashallah

i have no clue what im doing in the class rn we had that class once

[lyric pumice]

You should consider consider cases of xs individually.

[hearty stag]

and then we had a break and she sent us a video

[weary tiger]

hmmmmm

[hearty stag]

ah fuck isubmitted that shit with the wrong answer

[gusty crag]

rip

for this problem I recommend working from the outside in

[lyric pumice]

Then you must consider combinations of the xs.

[gusty crag]

what I mean by that is that if a set has k elements, then the size (cardinality) of the power set is 2^k

so the cardinality of that set is $2^{|A\times P(B)|}$

[vital dew]

mathew_soto78:
Compile Error! Click the reaction for details. (You may edit your message)

[gusty crag]

if set C has s elements and set D has t elements, then the cardinality of $C\times D$, the cartesian product of C and D, is s times t

[vital dew]

mathew_soto78:

[gusty crag]

so the cardinality of $A\times P(B)$ is $m2^n$

[vital dew]

mathew_soto78:

[gusty crag]

putting it all together gives you what I said earlier, $2^{m2^n}$

[vital dew]

mathew_soto78:

[weary tiger]

how come what i'm doing is not right ? @lyric pumice

[hearty stag]

wait a min

wasnt it |P(A*P(B)|

where |A| = m and |B| = n

|P(A) | is the amt of subsets

so that would be 2^m

[tame hound]

Hello

[gusty crag]

hello

[carmine vine]

hello

[lyric pumice]

Hello.

@weary tiger Use multisets.

[tame hound]

hey can anyone help me out.

I have been working all day and i am so tire that i can't finish my work. I need help with a couple of questions asap

[weary tiger]

What is K3,3?

What are stuff with K in it in graph theory?

And how is K3,3 complete if it doesnt have all vertices touching each other?

[stray reef]

K_3,3 sounds like the notation for the complete bipartite graph on 3 and 3 nodes

(ie the two parts are 3 nodes each)

ie the graph in the utility problem

[weary tiger]

I am trying to prove that it is nonplanar.

Someone told me that i should use that “each region is bounded by at least four edges in K3,3”

but IDK why that is true.

@stray reef Like how is each region bounded by >= 4 edges In K3,3?

[stray reef]

what face

[weary tiger]

See edit @stray reef

face == region.

[stray reef]

oh so you're starting with the assumption that K3,3 is planar

[tame hound]

12. Prove that there exist two integers a and b such that a + b > ab
20. Let m and n be integers. Prove that if m + n ≥ 10, then m ≥ 5 or n ≥ 5.
26. Let x ∈ R. Prove that if x
3 = x, then x
2 < 2
36. Prove the following De Morgan’s law for sets:
For every two sets A and B, A ∪ B(bar on top of them) = A ∩ B.(Bar on top of them)``` if anyone could help with this i would greatly appriciate it

[weary tiger]

Yes contradiction.

[stray reef]

K3,3 is bipartite by construction so all cycles in it have even length

[weary tiger]

All cycles have even length implies each region is bounded by >= 4 edges?

[stray reef]

≥4

[weary tiger]

Oh my bad.

[stray reef]

you can't have a region bounded by two edges since thatd require the two edges to connect the same pair of vertices

which is impossible

[weary tiger]

Like a loop?

I see.

[stray reef]

no like

two edges between the same two vertices

since in your defn of a graph an edge is identified exclusively by the nodes it connects

[weary tiger]

K3,3 is bipartite by construction so all cycles in it have even length
@stray reef What do you mean by cycles have even length?

[stray reef]

i mean exactly what i said

every cycle in K3,3 (or in fact, in any bipartite graph) has an even number of edges

[weary tiger]

That makes sense.

How does even imply at least 4 edges though? @stray reef

[stray reef]

every region in a planar graph has at least 3 edges

but you can't have exactly 3 since 3 is odd

[weary tiger]

OH TYSM.

every region in a planar graph has at least 3 edges
This was the piece i was missing.

[marble haven]

guys im stck, how do I prove that (n+1)=(m+1) implies n=m

given that n and m are natural numbers

constructed from sets

[stray reef]

isnt that one of the peano axioms? or are you specifically trying to prove it for your construction

[gritty crescent]

Isn't this one of Peano's Axioms?

[stray reef]

if so then what is your construction

[marble haven]

i have to prove it only knowing the first three peano axioms

[gritty crescent]

"The first three" could vary from book to book; maybe you could tell which ones they are?

[marble haven]

oh my god i just got it

i was just being silly and didnt read the axioms thoroughly enough, thanks for the reminder lol

basically I'm going to say that (n+1) -> n U {n} -> S(n)

and then show that both sides are the successor, therefore n and m have to be quivalent for their successors to be equivalent

[gritty crescent]

Yes, in fact the statement itself is an axiom, I'm not sure why you've been asked to "prove" it.

[marble haven]

:/ weird class

[weary tiger]

@lyric pumice Sorry but these hints are not making sense to me

Use the Principle of Inclusion and Exclusion to determine the number of solutions of
$x_1 + x_2 + x_3 = 80$

$0\le x_1\le 40$

$0\le x_2\le 32$

$0\le x_3\le 64$

[vital dew]

The-Elite:

[weary tiger]

I have X and Y, Z has to be X and/or Y. Is there any established symbol for this?

[gritty crescent]

Are you looking for this? $$(Z=X)\lor(Z=Y)$$

[vital dew]

TedNotKaczynski:

[weary tiger]

nice one, thank you

wherever that one now is located on the keyboard 😄

[weary tiger]

Really confused how i got partial marks for this

[stray reef]

was that all of the options?

on a first read it feels like you've got it all down correctly

[mint bane]

in this question is 0 the base case or would 2 be the base case and 0 and 1 special cases instead

[stray reef]

you'd need 0 and 1 as base cases

[weary tiger]

@stray reef yeah

[mint bane]

oh so it's possible to have more than one base case

cool

[weary tiger]

what is the answer for this?

[left kindle]

I think it's .a

[gritty crescent]

@weary tiger Where are you stuck in this problem?

[weary tiger]

i dont understand how to get the answer

[mint bane]

i think what they mean is what line of reasoning have you tried that didnt yield the answer

[weary tiger]

H1 is a also a sub statement of H2 that's where i get confused

[mint bane]

make a truth table and treat each side as separate

assign "ram is mathematics major" to some arbitrary letter Q, so H1 is just Q and H2 is Q or K, where K is "ram is a computer science major"

[weary tiger]

H2 contains two cases either or

[mint bane]

yes and you can treat the result of that "or" as one value on your truth table

[weary tiger]

okay , then if i take truth table for h1 and h2 it will the same answer for "and"

i feel dumb

[mint bane]

shit takes time dont worry

im still very much learning as well

i meant something like this

[weary tiger]

oh okay

then ,how can i arrive to the statement?

they didnt mention either it is conditional or biconditonal

[mint bane]

from here you need to sort of combine this with the truth table of an implication

[weary tiger]

i dont understand

[mint bane]

@gritty crescent maybe you can explain this better

[weary tiger]

i am fine with truth tables , i dont understand how to arrive to the statement

[left kindle]

you can go from his note to this

try plug Q and K truth values to the C column

[weary tiger]

C is tautology?

calculus and linear algebra was way better

[mint bane]

discrete is big fun :)

just try plugging in and you should get the statement/value

[weary tiger]

i am not getting anything , i feel so dumb

[mint bane]

getting stuck is the most important part of learning, be patient with yourself

[weary tiger]

okay

[pliant horizon]

What would be the domain and codomain of the function 1/x?

Just R->R?

[pale epoch]

definitely not that

[pliant horizon]

Since 0 is not in either?

[pale epoch]

yes

[pliant horizon]

So what would we call it then?

[pale epoch]

call what?

[pliant horizon]

The domain and codomain

[pale epoch]

well, what values can you not plug in?

[pliant horizon]

I mean i get that its the real numbers without zero but what would we call that

[pale epoch]

??

$\bR\setminus{0}$?

[vital dew]

Lochverstärker:

[pliant horizon]

So $\bR\setminus{0}\to \bR\setminus{0}$?

[vital dew]

nix:

[pale epoch]

sure

R\{0} is the largest possible domain

(ignoring complex numbers)

you can ofc always restrict the domain

the codomain can also be bigger than the range

[pliant horizon]

So then we could do R \ 0 -> R

[pale epoch]

ye

[pliant horizon]

and how could we restrict the domain in symbols?

[pale epoch]

dont forget the curly braces

[pliant horizon]

Ah

[pale epoch]

just define it as a function from whatever you restricted it to

like, defining it as a function ${1, 2} \to \left{{1, \frac{1}{2}\right}$ is totally fine

[vital dew]

Lochverstärker:
Compile Error! Click the reaction for details. (You may edit your message)

[pliant horizon]

alright cool thank you

also just to make sure im understanding partitions and equivalence relations, could we partition N with the even and odd positive integers, and would that be an equivalence relation?

[pale epoch]

you can partition N into even and odd numbers, yes

as every number in N is either even or odd

every partition induces an equivalence relation and vice versa

[pliant horizon]

Alright thanks again

[fallow raft]

would x $\notin$ (x $\in$ A $\land$ x $\notin$ B) be equivalent to (x $\notin$ A $\land$ x $\notin$ B) or (x $\notin$ A $\lor$ x $\in$ B)?

My question is if you have the not in before the parentheses does it act like a negation or would it just extend to the others somehow?

[vital dew]

Swagger:

[pale epoch]

the first statement makes no sense

the thing in parenthesis is a truth value, what does x in that mean

[fallow raft]

X would be an arbitrary but particular value in a set

Im trying to simplify C - (A - B) so I can prove something

But i cant figure out how to simplyify the C - (A - B)

[pale epoch]

ok, but

wtf is x $\notin$ (x $\in$ A $\land$ x $\notin$ B)

[vital dew]

Lochverstärker:

[pale epoch]

supposed to mean

[fallow raft]

The way I simplified it was C - (A - B) turns into x $\in$ C $\land$ x $\notin$ (x $\in$ A $\land$ x $\notin$ B)

[vital dew]

Swagger:

[pale epoch]

you are ignoring my point

x $\notin$ (x $\in$ A $\land$ x $\notin$ B) makes no sense

[vital dew]

Lochverstärker:

[pale epoch]

the thing in parenthesis evaluates to a truth value

it's a statement

it's either true or false

what does $x \notin \mathrm{TRUE}$ mean

[vital dew]

Lochverstärker:

[fallow raft]

I was trying to simplyify the set differences that are in the equation

[pale epoch]

ok, i understand what you tried to do

but do you see, that what you wrote down does not make sense?

[fallow raft]

I see what you mean, I just had no idea how to prove this thing so I was tying to get it into simplest form I could

Yeah I understand

[pale epoch]

it would be something like $x \in C \land \neg(x \in A \land x \notin B)$

[vital dew]

Lochverstärker:

[fallow raft]

Yeah that's what I was trying to express in the second option I listed

[pale epoch]

you can logically manipulate that

not sure you get anything "simpler"

[fallow raft]

So based off that if I have (C - A) - B could that be expressed as $(x \in C \land x \notin A) \land x \notin B$

[vital dew]

Swagger:

[pale epoch]

yes

[fallow raft]

@pale epoch Thanks man, I really appreciate the help!

Are logical opperations communitive? As in if I have $x \land (y \lor z)$ and I distribute that, would it be distributed the same as $(y \lor z) \land x$

[vital dew]

Swagger:

[pale epoch]

depends on the operation

OR and AND are commutative (check truth tables)

implication is not

[fallow raft]

Yeah luckily I'm only working with OR and AND right now, so this one should be communitive. Thanks!

[weary tiger]

what does it mean when it says find the best possible lower bound

specifically lower bound

[marble haven]

of what

[pallid lintel]

late to the convo, but to prove K,3,3 is not planar, try drawing the graph in a different way than normal. BY the Jordan curve theorem you can make a cycle that partitions the plane, with 6 edges. then you have 3 remaining edges, one has to go inside the cycle. the other has to go outside the cycle. The remaining edge will cross an edge if its inside our outside the cycle.

[marble haven]

is it not possible to create transcendental numbers out of dedekind cuts because they cannot be expressed algebraicly?

ik this isnt a question for discrete but idk how to get into the category theory channel

[pale epoch]

its not category theory either

dedekind cuts give you transcendental numbers

what do you even mean by "expressed algebraically"?

[marble haven]

like you cant just use algebra to show that they exit

exist

you have to create a infinite sequence

[pale epoch]

you cant do that with irrational numbers either

like, sqrt(2) is defined as the root of some polynomial

and pi is also defined as the root of some function

[marble haven]

hmm ok i'm just gonna keep reading from another document and see what comes out of it

but that makes sense i think

[pale epoch]

dedekind cuts give you all the transcendentals

completeness gives you intermediate value theorem and then you can define pi as the smallest positive root of sin(x) or something

so its a real number

then you need to put in more work to show its transcendental (i.e. not the root of a polynomial with rational coefficients)

[marble haven]

but is it possible to construct like pi only from a dedekind cut

yes, because it is a real number, right?

[pale epoch]

"only"?

there is a dedekind cut for the number pi, yes

but its harder to write down than the one for, lets say sqrt(2)

well, writing it down is just $({x\in\bQ\mid x < \pi}, {x\in\bQ\mid x > \pi})$, but that's unsatisfactory i guess

[vital dew]

Lochverstärker:

[marble haven]

doesnt that just show that it exists, not that we can construct it?

[pale epoch]

what do you mean by construct?

[marble haven]

idk there is just a conceptual question that says "Can you construct the real number, pi, as a Dedekind cut"

[pale epoch]

i mean you can define the sine function or wtv

and then build a dedekind cut using that

by like making one partition all the non positive numbers and those x, such that x < 4 and sin(x) is positive

[pliant horizon]

Would someone mind giving me a hint for how to proceed with this proof?

`Prove $\mathcal{P}(X\cap Y)=\mathcal{P}(X)\cap\mathcal{P}(Y)$'

[vital dew]

nix:

[pliant horizon]

Not entirely sure where to start

or i guess what exactly im trying to show

[naive saffron]

Show both are subsets of each other

[pliant horizon]

Alright so its not too bad to show that $\mathcal{P}(X\cap Y)\subseteq \mathcal{P}(X)$ and $\mathcal{P}(X\cap Y)\subseteq \mathcal{P}(Y)$

[vital dew]

nix:

[naive saffron]

that is a subset of both P(X) and P(Y) then it is a subset of the intersection

[pliant horizon]

Right

So that's basically half of the proof right?

[gusty crag]

does $\mathcal{P}$ denote the power set?

[vital dew]

mathew_soto78:

[pliant horizon]

Yes

[delicate ridge]

i am trying to enumerate all numbers of the form 2^n * 3^m in order of size

is there a "smart" way of doing this?

[pliant horizon]

So then I'd want to show that $\mathcal{P}(X)\cap\mathcal{P}(Y)\subseteq \mathcal{P}(X\cap Y)$

[vital dew]

nix:

[naive saffron]

Well

Let an element be in P(X) intersect P(Y)

what can you say about the elements inside this element

[pliant horizon]

they must be in both X and Y

[naive saffron]

Yes

So that means that this element is a subset of X and a subset of Y

So a subset of X intersect Y

so it is an element of the power set of X intersect Y

[novel lance]

hey can someone look at these and let me know if im correct?

[fallow raft]

I'm not sure if this is more discrete math or more for the proofs and logic channel but can someone help me out really quick? Say you have 10 unique marbles and 5 unique bowls, how many ways can you arrange the marbles in the bowels? My thought was to take the # of total ways - # of invalid ways and that will return the number of valid ways, but I have no ieda how to actually calculate either of those two. Anyone have any ideas? I don't want a solution but somewhere to get started with figuring these values out.

[analog sonnet]

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)?wprov=sfla1

Theorem 2

[fallow raft]

@analog sonnet Hey, would you mind explaining a bit either here or in PMs? I read through it but I thought that it said that the stars needed to be indistinguishable and the bins distinguishable. Would this still apply for my question even though the marbles AND bowls are distingishable? I'm confused by the theorem itself, but would it even apply here?

[analog sonnet]

I understand your point

This theorem doesn't seem to apply

[fallow raft]

Yeah, darn. Anyone else have any ideas? Ive been hard stuck here for a few hours tbh.

[crimson apex]

can someone help me with this proof pls

i know that we have to prove they are subsets of each other

but idk how to do that

[weary tiger]

i suck at counting, but is it maybe as easy as 5^10? For each marble, and there are 10 marbles, you can choose any box and there are 5 boxes, and every choice is distinguishable at any time? @fallow raft
So u get like 5*5*5*...*5 = 5^10

[fallow raft]

@weary tiger I'm not sure if this is correct since you have to assume that the number of marbles per bowl can fluctuate with at least a minimum of 1 per bowl. I know for a fact from other convos I get the correct answer if I can do # of combos - # of combos where its broken (ie 1 or more bowls is missing any marbles), I just have no idea how to calculate those.

[weary tiger]

what do you mean by "the number of marbles per bowl can fluctuate with at least a minimum of 1 per bowl"?

[gusty crag]

I think Rubik's cube is right (5^10) as long as there's no minimum number of marbles in the bowl

@fallow raft were there any additional constraints on the problem other than 10 unique marbles in 5 unique bowls?

[lyric pumice]

@weary tiger What kind of non-negative integer solutions are possible for x_1+x_2+x_3=80?

Deconstruct the numbers of a solution so that they are made up of 1s.

And then look at how another solution is obtained by transferring 1s from one variable to another.

[fallow raft]

@weary tiger Each bowl HAS to have at least 1 marble in it, but it can have more than that

[weary tiger]

this is a stab in the dark since I suck, but i would think the strategy would then to be to give each bowl 1 marble, that way you will always satisfy the condition and then count for the remaining marbles.

So

1. how many ways are there to give 1 marble to each bowl from a set of 10 distinguishable marbles?
   I think it's 10*9*8*7*6
2. Then for each such case multiply by the ways to give the remaining marbles to 5 bowls which with earlier approach 5^(10-5) = 5^5

The final count is then:
10*9*8*7*6 * 5^5

perhaps mathew or someone else can correct me because I'm not 100% sure either hehe

[fallow raft]

Tom has 10 distinguishable marbles ad 5 (distinguishable) bowls. Tom wants to put at least one marble in each
of bowl. How many ways can Tom place marbles in his bowls? Remember! All marbles must be in a bowl. see if you can use inclusion-exclusion in your solution... @gusty crag There is a minimum and not too many constraints

[fallow raft]

I got confirmation the total # of possible assignments would be 5^10. Then using Inclusion-Exculsion I can find the total # of incorrect permutations (4^10 for all 5 bowls), and subtract this from the total # of permutations which returns the number of correct permutations, but I don't know how to do tis since I dont know where the intersets between the incorrect ones would be.

Like I have no idea what value the intersections would hold.

[lyric pumice]

@crimson apex Show that an arbitrary element of one side of the equation is an element of the other side of the equation.

[fallow raft]

@gusty crag @weary tiger if either if you have any ideas^

[crimson apex]

thanks

@lyric pumice

[lyric pumice]

@fallow raft Using the principle of inclusion-exclusion, the result is

.

[fallow raft]

@lyric pumice are you able to explain it any further in PMs?

[lyric pumice]

Yes.

[gusty crag]

@weary tiger that expression definitely overcounts. If a placing of marbles into bowls ends up with marbles 1 and 2 in bowl 1, in the first phase of counting you could have assigned marble 1 to bowl 1 and in the second phase assigned marble 2 to bowl 1, or you could have assigned marble 2 to bowl 1 in the first phase and marble 1 to bowl 1 in the second phase

ignoring what happens with the other marbles, this counts any 'distribution' of marbles into bowls where one bowl has two marbles at least twice

I have no idea if millenial's answer is right but it definitely could be