discrete-math

[weary tiger]

going through textbooks is fun enough for me. dont know anything better than that

and there doesnt seem to be any division signs in r4 or r5

What is that though?

@weary tiger

3 is less than or equal to 4, but 4 is not less than or equal to 3

wait

meant to say less than lol

Lol

But what is the divison sign in here?

yeah the cross thingy is just saying it not

That means not?

yeah pretty much

its like negating it

So 3 is not greater than 4?

Like in python right?

With this thing? !

yeah

Ah thanks

also in this example it used the r1 r2 r3 r4 that we memorized?

To solve the question right?

those are examples

For what? So this wasn't a question that was answered?

oh wait

uhh

i think R1 and stuff are just example of relations containing the elements from A

the left side is the sets and the right side is just showing which properties they do and dont hold

So it wasn't answer for a question?

Then what is a question is supposed to look like?

this is what my questions looked like

you can give them a try if you want

though i gtg now

ttyl

[weary tiger]

Oh is this in other colleges interesting

[weary tiger]

@weary tiger

[weary tiger]

?

i got that from a textbook im going through for fun

idk what my uni uses

Oh ok

[urban cypress]

what is this called?

what kind of math solution is this

[chrome tree]

You have to translate it

[chrome tree]

I think it is: NotY is a element of the real numbers, or x is a element of the real numbers.

[chrome tree]

I can't remember the rest for the column

If xy is not equal to x then x must be zero

It requires you to think a lot, so just take your time to understand this.

[haughty garden]

Should be “there exist a real number y such that, for any real number x, (xy not equal to x) implies that x is zero”

[chrome tree]

My bad thanks for correcting me

I forgot the exist symbol xD

[urban cypress]

yeah exactly,

i just want to know what kind of math it is, so i can research it further

[haughty garden]

It’s first order logic (or predicate logic)

[sudden minnow]

well, do you know how to calculate $f \circ f (a)$ @hoary orbit

[vital dew]

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

[sudden minnow]

welp, shouldnt have pinged in same post as tex

,,f\circ f (a)

[vital dew]

lems

[hoary orbit]

thats just f composed of f right

but idk how to calc it

[sudden minnow]

since your question has function composition in it, surely you have a definition of function composition laying around somewhere

you say you dont know where to start, but in math there is always a clear place to start, making sure you know the definitions

[hoary orbit]

oh i mean ik

ff(a)

[sudden minnow]

ok and you don't know how to calculate f(f(a))?

[hoary orbit]

f(b)?

then it goes to a

[sudden minnow]

yes

[hoary orbit]

wait

is that it then

[sudden minnow]

so $f \circ f (a) = a$

[vital dew]

lems

[sudden minnow]

yeah what did you expect

[hoary orbit]

i thought it was more complexed

lmao

[sudden minnow]

the first 2 questions are extremely simple, the last 2 are marginally more difficult you just have to spot a pattern

[hoary orbit]

ok

thx

[sudden minnow]

np

[hoary orbit]

wait so do i have to do it for f o f(b) then f o f(c)

[sudden minnow]

well, yeah

[hoary orbit]

so for 3rd question f(a) ^(9) = b?

[sudden minnow]

should be

[hoary orbit]

alright thanks

[scarlet orchid]

hii does anyone in here know graph theory

[last flicker]

no sorry

[scarlet orchid]

.< as;ldkfjasl;dkjaf

i been on this one graph theory problemf ro like 5 hours and i got school in 4 hours

might be time to give up

[scarlet orchid]

omg not the leaugeueueue what rank r u

[last flicker]

uh

gold

[scarlet orchid]

oooo

[haughty garden]

Feel free to ask the question anyways and if someone can answer it, they’ll be able to help

[scarlet orchid]

ok

i am not sure about how to go about proving this

[fossil swan]

what topic is this? i might know this one @scarlet orchid

[scarlet orchid]

its graph theory

sry i tok a shower @fossil swan

[desert ibex]

Hi, you should put this in #combinatorial-structures

[desert ibex]

Okay this is pretty easy. A block is just a maximal connected subgraph without articulation vertices. So this problem is just asking you to prove that G does not contain an articulation vertex.

Every non trivial connected graph G contains a vertex v whose removal does not disconnect it (the leaf of any spanning tree works). Now, G-v is a connected graph. Since G is point symmetric, for all vertices u, G-u must be isomorphic to G-v. This implies that G-u is connected, which implies that u is not an articulation vertex.

Therefore, G is a connected graph without articulation vertices, which means that it is a block.

[reef dirge]

How can I use sets for q 1?

[grand totem]

The left side counts the number of subsets of {1, ..., n} whose cardinality is equal to a. Another way to count this may be as follows: Fix any element m in {1, ..., n} and consider all subsets of {1, ..., n} with cardinality a and that contain that element m (how many such subsets are there?). Similarly how many are there that do not contain m?

[hollow tartan]

If I'm talking about binary relations, how would I read aRb? Would it be read as "a relates to b"?

[ember obsidian]

“a is related to b (via R)”

[hollow tartan]

ah okay

and R is just some name of a set, correct?

[weary tiger]

does anyone know how to do logic gates

[quartz patio]

Do you know what each logic gate represents?

[pure star]

Can someone help me with this? How do I prove that this function assigns each x only one value?

for context, this is an exercise proving that R is the unique ordered complete field

up to isomorphism

[weary tiger]

yes

[weary tiger]

can you help me with it

[quartz patio]

sure

do you have values for x and y or are they just x and y

[ancient tide]

for all elements x of a symmetric group S_n, o(x) <= n right?

[unreal stump]

No, Take (1,2,3)(4,5) of S_5

Order of this is 6

[unreal stump]

If you don't know the notation,this is x where
x(1)=2
x(2)=3
x(3)=1
x(4)=5
x(5)=4

[ancient tide]

yeah ty

[unreal stump]

<@&268886789983436800>

[ember obsidian]

ty

[unkempt elm]

does n choose k have any interpretation when n is negative or a fraction?

[stone ridge]

I have finished parts a and B. Now I'm facing (c)(i), I don't know what it requires me to do?

Is simply (x1 < x2 and y1 > y2) or (x1 > x2 and y1 < y2) enough?

Do I need to add the "for all" or "for some" thing here?

[hollow tartan]

Anyone have any advice when it comes to doing truth tables?
specifically compound ones like
(P v Q) <---> (Q -> ¬P)

Any advice would be great. I have more trouble doing the reverse. What i mean by that is if Q is first and P is second

I'm find if it's p and then q is second but thinking of it the other way around is harder for some reason

[glacial flame]

A one-to-one relation can have multiple co-domain values for the same domain value, correct? An additional condition of domain values only having one co-domain value is part of the definition of a function, right?

Aka something like {(1,2), (1,3)} is one-to-one but not a function?

[twin basin]

does discrete math cover set theory?

I'm self teaching, and looking for good resources

NVM its in the subject line for the channel lol

damn discrete math is hella useful

How would I read this in plain english? also what's the middle term?

[glacial flame]

n choose r

It’s a binomial coefficient in the middle

https://en.m.wikipedia.org/wiki/Binomial_coefficient

[twin basin]

Thanks!

[wild cove]

hi, how do i prove that the set of partitions of a countably infinite set is uncountable?

knowing that the power set of a countably infinite set is uncountable, ive been trying to find a bijection from this power set to the set of partitions but currently am not able to find one

[wicked bolt]

what about an injection from the power set to the set of partitions?

[wild cove]

let say the countably infinite set is S
im thinking about mapping a subset of S, let say T, to the partition {T, Z\T}

but unfortunately this mapping is not an injection since both T and Z\T map to {T, Z\T}

however under this mapping, every partition has exactly 2 preimages, which makes it look like |S| is "twice" of |set of partitions|

which reminds me of the proof that the set of even integers and the set of integers have the same cardinality...

[little prism]

you could fix some element a in S and then do something different for T and Z\T depending on which one includes a

[quaint glacier]

Does anybody recognize the product (p^n-1)(p^n-p)(...)(p^n - p^(n-1))? I came across it in another context and wonder if it has a name or is a well known product? googling doesn't yield anything

[red nest]

Cardinality of GL_n(F_p^n)?

[quaint glacier]

I mean that is the context in which I came across it. But does this reduce to something else in number theory or combinatorics

[red nest]

Ah, I see. That is the only context i know it from

[chrome lily]

is it not 5.5?

[sudden minnow]

I would assume "div" rounds down to an integer value

[chrome lily]

You are right! Lol

I was sitting here confused as if I was doing something

but yeah its just 5 then

thanks man

[sudden minnow]

np

[wild cove]

i get it now, thanks a lot!

[unreal stump]

What's a vertex disjoint edge?
Context:

[pale epoch]

seems to be you choose n edges such that no two share a vertex

[tame bone]

HI Guys im currently studying in germany and there is this question. If the functions are surjective, bijective or injective or not. The second one is not surjective and not injective BUT What about the others? I hope u can help me with this thank you

[regal ice]

Can someone please explain this

[haughty garden]

Recall that the Cartesian product of m sets comprise of a tuple of m elements, say (a_1, a_2, ..., a_m), where a_1 comes from A_1, a_2 comes from A_2, etc. Each a_i in your tuple can be chosen independently and choosing these a_i terms independently give you a unique tuple (since A_i has no duplicate values). Therefore, the number of tuples that you obtain comes from making |A_1| many choices for a_1, followed by |A_2| many choices for a_2, ..., |A_m| many choices for a_m. So you obtain the product of the cardinality of individual sets

[blazing rose]

can someone help me understand this? I understand it to the point that the operations are +, - and * I guess? But I dont get what the set S is and how it is related to the Ring R

[stray reef]

S is just the set of solutions to the equation ax = 1 in your ring

it is a subset of R

@blazing rose this looks like the first half of a problem. can you show how it continues?

[opaque prawn]

can someone help me with this question

answer is c)

[blazing rose]

this is it

[blazing rose]

I understood the first part now and tried to transform the term with b and z to something where I can make it equal to az = 1

but I dont get there :/

[stray reef]

so you are trying to prove the first part? for any z in S, we have 1+b-za in S?

[blazing rose]

yes

[stray reef]

x is in S if and only if ax = 1

[blazing rose]

I said 1 + b - za = az = 1

[stray reef]

no

so your goal is now to check that a(1+b-za) = 1

[blazing rose]

wait no

yea

tat

that

I meant that

a(1+b-za) = az = 1

[stray reef]

no

[blazing rose]

but if z element S, isnt az = 1?

[stray reef]

yes but you equating a(1+b-za) to az is a bit out of nowhere

do not overthink this

[blazing rose]

okay

[stray reef]

a(1+b-za) = a + ab - aza

[blazing rose]

yes

but I can replace az with 1 here right

so a + ab + a?

[stray reef]

sure can.

but don't forget the minus.

[blazing rose]

oh yea right

so a+ab-a

oh

and thats ab which is 1

[stray reef]

yes

[blazing rose]

alright thanks a lot

[weary tiger]

(y – k) 2 = 4a (x – h)

[blazing rose]

how do I proof whether there exists an injection here?

or how do I even understand this? An injection from set S onto set S??

[weary tiger]

this this the equlation of parabola

(y – k) 2 = 4a (x – h)

[crystal torrent]

what is that letter?

the subject is sigma algebras

[grand totem]

$\mathscr{I}$

[vital dew]

Neverbloom

[crystal torrent]

thank you

[woeful idol]

Can someone help me with a? The answer sheet only gives the final answer and I don’t get how they came up with that

[swift kiln]

can someone help me with this : Prove that [0,1]~[0,1] × [0,1]

[woeful idol]

B x A =
${<\emptyset, 1>, <\emptyset, 2>, <{1}, 1>, <{1}, 2>, <{2}, 1>, <{2}, 2>, {1, 2}, 1>, {1, 2}, 2>}$

[vital dew]

Vemix

[lyric osprey]

is zero an integer

[fierce mason]

mathematical induction

[vale cairn]

Yes

[fierce mason]

i understand until the inductive step sos

[vale cairn]

Well, one way to make it easier to to note that this is equivalent to showing that $1 \le \frac{1\cdot 3 \cdot \dots \cdot (2n-1)}{2 \cdot 4 \cdot 6 \dots (2n-2)}$

[vital dew]

potato

[vale cairn]

And it's perhaps more obvious how you can prove this by induction

[fierce mason]

sorry could you explain how that works?

[vale cairn]

like why they're equivalent?

[fierce mason]

yeah

[vale cairn]

Just multiplying both sides through 2n, since this is a positive integer

[fierce mason]

ok thank you ill try it out

[woeful idol]

When we’re talking about the DPLL procedure to check satisfiability of a given CNF, what are “unit” clauses?

[haughty garden]

A unit clause is a clause that only has one (unassigned) literal. Unit clauses have an obvious assignment since it has to be satisfiable for the CNF formula to be satisfiable

[tame bone]

can someone help me with this? the task is to say if the funktions are bijective, surjective, injective or not. Number 2 should be not surjective and not injective but i need help with the other ones

[woeful idol]

So is the second p in $(p \land q) \lor p$ a unit clause?

[vital dew]

Vemix

[haughty garden]

Well this formula isn’t in CNF but yes that’s the idea

Turns out this is equivalent to $p \land (p \lor q)$. The first $p$ in this CNF formula is a unit clause

[woeful idol]

Thanks

[woeful idol]

Also one more thing

We have $\neg r$

[vital dew]

Vemix

[woeful idol]

Why not substitute with T here?

[haughty garden]

That would make the unit clause false

We want an assignment that makes our unit clause result to a true clause

[woeful idol]

Why do we want it resulting in a True clause?

[haughty garden]

Otherwise the entire CNF formula is false

[woeful idol]

Ah so I just kept substituting unit clauses with T

Like I can simplify with the dpll but I never picked the correct T or reverse T

[haughty garden]

Remember we have our CNF formula in the form: $Q_1 \land Q_2 \land \dots \land Q_n$. For this to be true, each individual $Q_i$ clause must be true. In the case where $Q_i$ is a unit clause, this forces our assignment such that $Q_i$ returns a true clause

[woeful idol]

That actually makes sense

Thank you once again

Logic is actually alright but I hate sets so much

[haughty garden]

Yeah it might take a while to wrap your head around but sometimes it’s useful to look at the bigger picture

[woeful idol]

So if you have

$p \land \neg p$

[vital dew]

Vemix

[woeful idol]

You can immediately fill in upside down T as this can never be true

If I am understanding this correctly

[haughty garden]

Yes

[tame bone]

😦

[wise quartz]

base cases are trivial (n=1,n=2)

you need to do them both because this is a second order linear recurrence

[wise quartz]

then use strong induction

[hoary orbit]

ok thx

[mystic nova]

Anyone know what the symbol in yellow means?

[sudden minnow]

I assume "defined to be" but I do not think this is standard terminology, at least uncommon

https://math.stackexchange.com/questions/944757/whats-the-most-right-symbol-to-use-for-defined-to-be-equal-to

seems like it is a thing, but I've always seen := or equality with def on top

[mystic nova]

ty

[worthy wasp]

can someone help me

[feral salmon]

Hii guys

There is no correct answer here right?

You'd do this right?

[opaque prawn]

Hi, I'm trying to proof this but got stucked in this step

I do not know how to proceed, can anyone help me pls!

[graceful drum]

well your almost done look what you have right now, you can drop the paranthesis for a start. Then you can use commutativity of logic and to reorder. using idempotence you can drop the duplicate $x \not \in Y$

[vital dew]

achilles199703

[opaque prawn]

OH

I'm looking at a solution

but i don't understand how this worked

[graceful drum]

Let A,B be sets then $A \times B$ denotes the cartesian product of the sets A,B. Now think about $X = A \times B$ as a new set called X. We would write X as $X= {(a,b) | a \in A, b \in B}$, which means X contains all Tuples consisting of a's and b's. If we now look at a second set $Y = C \times D$ and build the Union of $X \cup Y$ then all tuples $(c,d)$ get put also in this new set. We can now see that $(A \times B) \cup (C \times D) \subset (A \cup C) \times (B \cup D)$, this part is easy. Let $(x,y) \in (A \times B) \cup (C \times D) \rightarrow (x,y) \in (A \times B) \lor (C \times D)$
So if (x,y) is from either set $(A \times B)$ or $(C \times D)$ it is easy to see that $x \in A \lor C$ and $y \in B \lor D$. However the other direction doesn't hold, we can show this with a counterexample. Let $A = B = {0}$ and $C = D = {1}$ now $(A \cup C) \times (B \cup D) = {0,1} \times {0,1} = {(0,0), (0,1), (0,1), (1,1)} \not = {(0,0), (1,1)} = {(0,0)} \cup {(1,1)} = (A \times B) \cup (C \times D)$

So i dont know where this proposed solution is from, but if I see it right those sets are not equal, only the left is a subset of the right

[opaque prawn]

it's from this https://www.youtube.com/watch?v=j5fnaXLOkFk

12:59

[vital dew]

achilles199703

[sudden minnow]

yes

an element like (a,d) can't appear in the first set

can in the right

[opaque prawn]

fuck

it's wrong

the video's solution is wrong

this is not equal

[sudden minnow]

yes that is what we are saying

[graceful drum]

ok in the video he only shows the => direction which shows that left is subsetequal to the right, he doesn't show the <= direction. what i've written should be sufficient to show that there exists a (x,y) in the one set, which doesn't appear in the other, thus proving the two sets are not equal.
Taking this into account you get a for "=> subset" and "<= inequality" thus a proving a subset

[graceful drum]

yes and no, he never actually states explicitly that the other direction works only that this way of proving can be used, however this heavily implies that the backwards direction is working.

So yeah that is a problem

[opaque prawn]

this is true but not true for <=?

so he got this?

[graceful drum]

No this is exactly true

to prove for two sets A and B that they are equal, you first show that A is subset of B and then you show B is subset of A

however here the "<=" direction can't be shown to be a subset, with a counterexample we easily verify the inequality of the two sets

[opaque prawn]

right

if I'm trying to prove this

in exam

do I need to do it like this

or i can just do this straight away?

[radiant valley]

Both methods end up at the same place so in a good system you’d be able to do it either way

[distant glade]

the second way you did it is very confusing

[graceful drum]

$(x,y) \in (A \times B) \cup (C \times D) \Rightarrow (x,y) \in (A \times B) \lor (x,y) \in (C \times D)$ using the definition of cartesion product you get $x \in A \lor x \in C$ and same for y. Thus $x \in (A \cup C)$. then use definition again to get your tuple back. this should be sufficient

[distant glade]

i understand those are the two conditions to be in each set, but you didn’t really give any other info

[vital dew]

achilles199703

[opaque prawn]

I see, thanks!

[opaque prawn]

can anyone help me with ii)

I can't understand the question, what is it trying to say?

[stray reef]

you're asked for the number of poker hands that are ranked as two-pair by the rules of poker

@opaque prawn how familiar are you with poker and/or playing cards in general?

[opaque prawn]

i have no idea with poker

game

oh so

[stray reef]

a pair is two cards of the same rank

two-pair is when you have two pairs

[opaque prawn]

11 22 3 is classfied as two pairs?

[stray reef]

(and the fifth card doesn't match either)

yes, except there's no 1 in a deck of cards :p

there's an Ace

[opaque prawn]

A in this case XD

[stray reef]

but yes, AA223 is a typical two-pair

[opaque prawn]

oh I understand the question now

It's trying to ask how many 5 card hands has the AA BB C form?

out of the 52 cards

Can I do

AAA22

[stray reef]

no, that's a full house

it's a better combination than two-pair :p

[opaque prawn]

so strictly AA BB C in this case

[stray reef]

yes

the last card should not match with either pair

[opaque prawn]

I see tyy

is i) going to help me with ii)

[stray reef]

dunno

i don't think it will

[opaque prawn]

How do I write $x \notin (C - B)$ in english?

[vital dew]

Rmtc

[opaque prawn]

trying to prove this but got stucked

[sudden minnow]

if you arent in this set, you are in its complement

and consider (A\B) = An(B^c)

[opaque prawn]

like

[sudden minnow]

again

find the complement of A\B

and x is in that

[worthy wasp]

im not very good at these questions

[weary tiger]

I'm confused about mathematical induction. You prove p(k) for some function p. You can p(k+1). Surely there's some k that might break it? p(100) for example. What does proving p(k+1) really do?

[unreal stump]

Well you actually prove "if p(k) then p(k+1)"

So your base case is p(0)
(or p(start) or whatever) is true

[weary tiger]

yes but what about p(k+2)

[unreal stump]

Ok so suppose you know p(k) is true magically

[weary tiger]

surely there can still be an argument somewhere from 0 to infinity that might not hold?

[unreal stump]

Then p(k+1) is true because for x=k it's true

And p(k+2) becomes true because p is now true for x=(k+2)-1=k+1

[weary tiger]

right

that makes sense actually

[unreal stump]

Induction is like a stack of dominoes

The base case is the initial push

[weary tiger]

yeah that definetely makes sense now. that's how it was described in the book. dominoes.

[unreal stump]

The induction step is the "if this block falls,the next block also falls"

[reef dirge]

any suggestions on how to approach the subsets method to prove this?

[red nest]

A subset of {1,2,…n} consisting of a elements either contains n or it doesn’t. Now try to find formulas for both of these cases

[worthy wasp]

anyone? please help

[weary tiger]

https://youtu.be/j3URnNuC3AY

That would help

I'd try to help u step by step but it's 3 am rn

If ur still having an issue until tmrw hmu I'll try to help if i still remember how it works

[oblique rock]

Anyone able to help me here? I have no idea how to tackle this question. I'm staring at definitions but it's not helping

[grand totem]

Well, the question asks you to prove or disprove the claim. So before you start to actually do that, you should decide on whether you want to prove or disprove it (depending on what you think is true)

It may be a good idea to test some edge cases first (what's S × ∅ for any set S?)

[oblique rock]

I've seen a proof similar to it in another textbook that proofs the opposite, but I think it's false

[hollow tartan]

what is the best way to test if a function is well defined

for example if i have $f(x)=\frac{1}{(x-1)}$ the function is said not to be well defined but how do ik

[vital dew]

arrow891

[vale cairn]

Uhhh I don't think this question is well defined basically lol

[hollow tartan]

????

[vale cairn]

I mean basically typically given a function you want to give the domain and codomain

If you don't give the domain and codomain, then they are usually inferred from context

[vale cairn]

If the domain and codomain are ambiguous then I don't think it makes sense to call the functor well-defined or not really

Okay, yes, so here the domain and codomain have been specified so it's okay

[hollow tartan]

the answer is not well-defined

how

[vale cairn]

Well, does the inverse of x-1 exist for every real x?

[hollow tartan]

it's x=1

[vale cairn]

The point is that you cannot invert 0, so this definition doesn't make sense

[hollow tartan]

0

where did that come from

like what???

[vale cairn]

Well the point is you can only invert non-zero numbers

So it breaks down when x-1 = 0

Which corresponds to x =1

[hollow tartan]

which is x=1

okay

but to me

I'm thinking so what x=1

oh wait

if if say x is 2

2 doesn't eqaul 1

then it's not well defined

or did i just make up some logic?

[oblique rock]

okay so I think if either $A_1 $ or $A_2$ is the empty set we have that the equivalence relation $A_1 \times B \sim A_2 \times B$ doesn't hold since $f: \emptyset \rightarrow A_2 \times B$ is not 1-1

if $B=\emptyset$ then the equivalence relation above holds if $A_1, A_2 \neq \emptyset$

but then to show $f: A_1 \rightarrow A_2$ is 1-1 and onto, it depends on our choice of $A_1$ and $A_2$ right?

freak

how do I use this

[grand totem]

Maybe the bot is just down, it's alright though I can read it

[oblique rock]

okay thanks!

[grand totem]

It's still not clear to me if you're trying to prove the claim or if you're looking for a counterexample to the claim

[oblique rock]

hmm let me ask my peers

[grand totem]

Because it doesn't sound like you're completely one the wrong track here but the argument is a bit hard to follow without even knowing beforehand what your argument is showing

[oblique rock]

I think though if we find a counterexample that should suffice

If we find a counterexample, then if the first equivalence is satisfied, we should find a case that A_1 ~ A_2 doesn't hold to say that the implication doesn't hold for all cases

[grand totem]

Exactly, so can you think of some choices of A₁, A₂ and B such that A₁ ∼ A₂ does not hold, but A₁ × B ∼ A₂ × B does hold

[oblique rock]

I was thinking if B=empty set, then I can definitely choose A_1 and A_2 such that the second equivalence doesn't hold

because f: emptyset -> emptyset is bijective right?

[grand totem]

Yes

[oblique rock]

and if A_1 = emptyset, then we have f: emptyset -> A_2

which I think is not 1-1

[grand totem]

Unless A₂ is also empty

[oblique rock]

true, but I'm not sure is it onto? I don't think so right?

but then I have found my counterexample

[grand totem]

By the 1-1 above I meant that ∅ → A₂ is a bijection iff A₂ is also empty, it is always injective

So since you're looking for a choice of A₂ for which there is no bijection from the empty set, any non-empty set will do

[oblique rock]

Perfect, thank you ƒor this explanation and help!!

[hollow tartan]

I have to prove if the followin is reflexive, antireflexive, or neither
The domain of relation P is the set of all positive integers. For x, y ∈ Z+, xPy if there is a positive integer n such that x^n = y.

I say that it's reflexive because if every x is raised to the 1st power then x will always relate to itself.

However, my friend says it's neither becuase she says it only works for n=1. The book agrees with what i said

[tame bone]

?

?

[hollow tartan]

can Someone explain why it must be reflexive and that the answer cannot be niether nor antireflexive

nvm she got it

[dreamy fox]

Can anyone explain "logic laws," I just watched a 15min video about it,

My notes include indentity, domination, double negation, demorgan's, distrib, absorp, commutivity, inverse, associativity, conditional laws

Then I picked the discrete mathematics by johnsonbaugh

But I only have a 22% charge left on my cellphone

I wonder how someone could use logic laws in the context of a court room or crime scene.

[uncut bear]

I know one thing people mix up is that a false statement implying a true statement is not false

[chrome lily]

Im pretty sure our prof didnt go oveer this yet

but whats the trick here

"separating the final term"

[spare slate]

$\sum^{n+1}{k=1} t_k=\sum^{n}{k=1} t_k+t_{n+1}$, which kind of makes sense if you think about it \ \ idk how to go over it, it's kinda self-explanatory

[vital dew]

Civil Service Pigeon

[little prism]

Write out what the sigma notation means

On both sides. Then you'll see it's really the same thing

[spare slate]

^

[chrome lily]

following this would my answer by k^2+m+1 then?

[spare slate]

there shouldn't be an m

[jagged heath]

So for this problem how would the expected value theorem be set up? Would the first outcome be something like: (0.97)(600) + (0.03)(0). Where there is a 97% chance that the boat doesn't sink and Alice spent $600 with a 3% chance that the boat sinks with no damage
Image

[dreamy fox]

Thank you.

[icy snow]

I think the insurance becomes a viable choice from 100/1500% chance of capsizing

[jagged heath]

What do you mean by that? What did you get for the expected value of having insuarace vs not getting insurance

[icy snow]

Well, why would you even incorporate the 500 that will always be paid into the equation?
So should you not buy insurance when the expected value of not having insurance becomes bigger than the cost of the insurance?
That value becomes bigger than the cost of the insurace at 1/15 percentage chance of capsizing.

Of course I could be wrong

[worthy wasp]

what do i do for this question?

[hidden brook]

Hint: induction! Alternatively, think in terms of binary

[gritty crescent]

I don't think anyone is explicitly using mathematical logic in courtrooms; however, mathematical logic has attempted to formalise our intuitions about reasoning in daily life (it goes way beyond, but this was a historical starting point). In courtroom arguments there's almost always a component of subjectivity which is difficult, if not impossible, to address using hardcoded mathematical formalisms.

[dreamy fox]

Alright, alright, but if you use element/object/sub-set

[unreal stump]

Wdym

[chrome fossil]

For the second question, simply use 2 as the counterexample

For the first question, note that the there are 2^n - 1 nonempty subsets, the minimum of the sum of the numbers in the subset is 1 (created by the subset {1})and the maximum is 2^n - 1 (created by the subset {1, 2, 4, …, 2^n}) then show that non of any subsets has the sums of the numbers inside them equal to another subset

This can be shown by the following
Let A and B be the subsets of {1, 2, 4, …, 2^n} such that the sums of the numbers in A and B are equal.
Let 2^a and 2^b be the highest number in A and B
If a > b then the sum of the numbers in A is at least 2^a and the sum of numbers in B is at most 2^(b+1) - 1 <= 2^a - 1 < 2^a hence a <= b. Similarly for a < b we have that a >= b, so a = b.
We then remove 2^a and 2^b from these two subsets, as 2^a = 2^b, the sums of the remaining numbers if A and B must be equal. Repeat the same argument that the second next highest number in A and B are equal. Similarly, the third, fourth, … highest number of the sets A and B are equal. Hence A = B.

[boreal reef]

if a mapping is not a function, can it be classified as everywhere defined?

[unique karma]

Anyone know how I would get the answer for the last

[red nest]

It seems like the terms of the generating series are (-2x)^n making it a geometric sequence

[young field]

Is the t_n+1 inside the summation or outside it? It makes sense if it’s outside

[spare slate]

Outside

[red nest]

Hint: Countable unions of countable sets are countable

[little prism]

you can also try writing down an explicit bijection

there are a couple nice ones here

[wet flame]

what is a countable union?

[little prism]

a union of countably many sets

[wet flame]

ah

so if it is countable |N*| = |N| ?

so true?

[worthy wasp]

cant lie this went right over my head

[red nest]

Well sometimes countable means finite or countably infinite, but in our case N* is obviously infinite, so yes

[wet flame]

i see

Would you say N* is a subset of the power set of natural numbers?

[little prism]

yes

clearly all elements of N* are subsets of N

[wet flame]

yeah

[hidden brook]

Why is the step “show that none of any subsets ...” necessary?

Oh wait nvm I know why lol, it’s to show that each subset maps to a unique sum

Nice idea

[merry schooner]

How to answer this?

[worthy wasp]

i got this far

but idk what to do afterwards

[hidden brook]

so you know that [1, 2^{n+1} - 1] is achievable, then for n + 1, you want to show that [1, 2^{n+2} - 1] is achievable. how would you go about doing that?

[worthy wasp]

just sub it in?

[blazing rose]

could someone explain this to me?

I dont have problems with the structure of graphs and how they look like and how they work

but I dont get everything off this notation

[worthy wasp]

idk .-.

[hidden brook]

what happens if you add 2^{n+1} to every number in the range [1, 2^{n+1} - 1]?

[worthy wasp]

[2^{n+1} +1 , 2^{n+2} -1]

[pale epoch]

technically yes

but you wouldnt use them "the wrong way"

you can switch the notation if you want, its just that: notation

sure, those are just symbols

you can also write (R, , ) if you want

those are just symbols

well, uhh

$(\mathbb R, +, \cdot)$ is a ring but $(\mathbb R, \cdot, +)$ is not

[vital dew]

Lochverstärker

[pale epoch]

so if you talk about a specific + or · the order is important

but as abstract symbols it doesnt matter

yes, the order in the definition does matter (technically)

uhh

yes

ok, according to your definition you have to use + for the abelian group and · for the other operation

[pale epoch]

but according to your definition this isnt possible

well, your definition only defines rings as structured with an operation + and another operation ·

but uhh

it really doesnt matter

those are just symbols

its important how they behave

i.e. one of them is the operation of an abelian group and they interact according to distributive law

your definition never writes down a triple like that

or am i missing it

well

just use the only interpretation that makes sense tbh

and you will never see the meaning of + and · switched

because that would be unnecessarily confusing

if those two symbols are used as the ring operations its always like in your screenshot

(technically you can switch them, if you switch them everywhere, they are just symbols, but that would be insane)

it should be known based on placement

but i wouldnt bet on your professor (or anyone) not making a mistake

[merry schooner]

Guys do u know how to answer this?

[gray sun]

I found the answer to this problem through a script simulating it, but how would you do it through induction?

[weary tiger]

been stuck at this for few days , google gives much more simple questions, how can i find the formal language of this given automata?

[rustic harness]

Hey! Thanks for your answer that day, I'm almost done with the problem and wanted to share :)

[thorny jasper]

Please read the following:
"I submitted a result to Princeton's Annals of Mathematics journal!
Title. The paper is a few paragraphs long and deals with what makes mathematical thinking possible in the first place. Its title is, "The Principle of Structural Integrity and its Implications for Mathematical Problem-Solving." I argue that the principle of structural integrity generates every truth (and, by definition, cannot generate falsehood), and since everything can be represented mathematically, including our mental faculties, every mathematical theorem anyone has ever come up with is true on every level of mathematics at the same time. To drive the point home, I use as an example a certain extremely valuable conjecture that crackpots and hacks (but also, I presume, mathematicians -- I don't really know the specific details of the history of mathematics all that well) have tried to solve in endless ways and with infinitely variable methods, but which follows trivially from my axioms. I submitted it without a bibliography because I was too goddamn excited about finally solving a problem that tortured me for a full 8 years.

So yeah. Expect some major excitement very soon."

[foggy linden]

Is a single reflective vertex symmetrical?

my understanding is that it should at least have another vertex to connect to fulfill a symmetrical relation.

[winged kelp]

is the keyword 'binary relationship' makes me read a≤b as 'a precedes or equals b' and not a is less or equal than b ?

A binary relationship a≤b (read as a precedes or equals b) between two objects is said to be a linear ordering if:

For any a and b, either a≤b or b≤a,
If both a≤b and b≤a it follows that a=b, and
The relationship is transitive: if a≤b and b≤c, this implies that a≤c.
We will say that a<b (read as a precedes b) if a≤b and a≠b.

Given n objects which have a linear ordering, we may order them a1,a2,a3,…,an such that a1≤a2≤a3≤…≤an 

also "If both a≤b and b≤a it follows that a=b" is it necessary that it was written this explicitly, wouldn't a=b be the only option left, since a < b and b < a or a < b and a = b or b < a and a = b does not make sense .

[sudden minnow]

two elements in a binary relation are not necessarily comparable

well that wasnt an answer to this I just realized, but you can also have both a related to b and b related to a and a =/= b

using suggestive notation like < and "precedes" is making it look much weirder than it is

[winged kelp]

man , i think the overarching problem is, I'm very lost as to how these statements defines a linear order.

[sudden minnow]

do you know what a binary relation is

and an equivalence relation

idk what source you are using but it looks fishy

[winged kelp]

not formally, im reading information here and there - i probably take a lil more time into it.

https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Linear_ordering/ this is the source

https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Hierarchical_ordering/ they have one for hiearachical ordering as well

[sudden minnow]

okay using an engineering resource was your downfall

[winged kelp]

haha - yeah.. my main goal was to learn comp sci abstract data strucutre - but wanted make sense of the matheimatical models there

lol but im defeated.

[sudden minnow]

if you want to understand why those 3 things define a linear order for a binary relation, you need to understand what binary relations look like when you don't necessarily have those things

and for that you need to know what a binary relation is

and for that you need to learn it from a math textbook, or a wiki page or maybe a youtube lecture, but the way it is explained in that website is really bad

[winged kelp]

thank you for pointing out the prerequisites and that state of the definitions on the website. i will most likely take that course of action - was hoping for a quick search to wrap those statements around my head, but definitely not the case .

smol brain

[sudden minnow]

I did go on that website a bit too hard, anybody with a math background will know what it is talking about and those without one you can't explain to them any better, the core issue is that web page isn't about teaching you math it is about something else

so yeah if you want to actually learn the math, my point stands

[winged kelp]

mhm i agree- site just had expectations from readers. thanks again

[sudden minnow]

np

[gloomy lava]

PLEASE help

#help-4

is G+ just like the power set version for relation graphs

[weary tiger]

been stuck at this for few days , google gives much more simple questions, how can i find the formal language of this given automata?

[tight pebble]

I apologise for my poor notation but

[gloomy lava]

#help-1

[lofty hawk]

what are your to-go complexity theory resources?

[solemn zephyr]

how many permutations are there on the set {1,…,2n} such that no even number appears by itself?

[neon flower]

any idea how to prove the claim?

[formal palm]

can someone explain to me why 3a is isomorphic?

[viral crown]

is this a quiz or

[formal palm]

hw

[viral crown]

rotate H_1 180 degrees and you're allowed to turn the little egg a bit too since you're not actually fuckin with any connections there

then it's the same as G_1

if you need the functions you can just re-index either as long as it's symmetric (i think - dk for sure but ids y u cant) and just go n-->n

^not sure if that step with the reindexing is allowed but it should just be reversing which i think is okay

[formal palm]

ok

[fierce mason]

using permutation with repetition i can get that there are this many different strings, but thats only when all 9 letters are used

any ideas?

[stray reef]

well now count how many there are with 8 and with 7

gonna be a little laborious and involve a little casework based on which letters are missing

[terse kayak]

So given a generating function for a sequence a_n, a(x), I know that the generating function for every 2nd term of a_n, ie a_2n, is 0.5(a(sqrt(x))+a(-sqrt(x))),

but is there a general form for the generating function for every nth term, ie a_kn where k is a random integer?

Can't seem to find anything about it online

[terse kayak]

<@&286206848099549185>

[crystal sandal]

Is there a name for catalan numbers with upper bounds? (i mean, just like in catalan numbers you cannot cross x axis but you also cannot have y coordinate greater than some given k at any point)

[vital dew]

kunny

kunny

[cursive echo]

Kind of a little thing but can anybody tell me why axiom 4 here doesn't follow the same style as the one above (or any others) in its statement
Why is it just for all n and not for all n in N?

[wet flame]

n cannot be a natural number since there is no natural number whose successor is 0 so you wouldnt have n in N

[cursive echo]

that makes sense gang

[vital dew]

kunny

[sudden minnow]

I dont think you understand what a relation is

a (binary) relation on a set $A$ is a subset of $A \times A$

[vital dew]

lems

[cursive echo]

What is an axiom looking for in the case of zero

[cursive echo]

I thought a base case would just be using 2 variables ie n^m = (nxn)xm that would work for all values. But I'm not sure after this

[sudden minnow]

yes, you can have n-ary relations, those would be subsets of $A^n$

[vital dew]

lems

[sudden minnow]

are you trying to define exponentiation

[cursive echo]

Yes with a base case first, and then a recursive definition

I'm not trying to look for a straight up answer I'm just not sure on what a base case is

[sudden minnow]

do you know the base case for addition? multiplication?

[cursive echo]

Or in that case what differentiates a base case from a recursive definition

[sudden minnow]

a base case is how the recursion stops, base case is part of the recursive definition

[cursive echo]

We were just introduced to the recursives for addition and multiplication

[sudden minnow]

okay so? do you have their definitions with you?

[cursive echo]

Ignoring the middle one

[sudden minnow]

exponentiation is not so different, so you need to understand the examples you were given first

you probably also have a + 0 = a on AA6?

AA6 and AA8 are the base cases

[cursive echo]

Yes for adding zero

[sudden minnow]

AA7 and AA9 are the recursive steps

you only focused on 7 and 9

6 and 8 are equally important

[cursive echo]

Ohhh ok I see what you mean now by the base case being part of the recursive definition

thank you

[sudden minnow]

np

[vital dew]

kunny

[sudden minnow]

what is a partial relation of 2 elements

so, we have 2 elements in some set A

and presumably we have a relation, which is a subset of A^2

and you are saying (a,b) is an element of this relation?

please be more clear

[vital dew]

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

[sudden minnow]

no, you are confusing terminologies, your fundamentals are off

if you have a set A, a relation R is a subset of A^2

when we say aRb this is shorthand for $(a,b) \in R$

now that we have this down, we can state the anti symmetry property more clearly:

If A is a set and R is a relation on A, we say that R is anti-symmetric if
$(a,b) \in R \land (b,a) \in R \implies a= b$

[vital dew]

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

[sudden minnow]

in shorthand notation,
$aRb \land bRa \implies a=b$

[vital dew]

lems

[sudden minnow]

but don't use the shorthand until you are very clear what a relation stands for, because you still seem to be somewhat confused about it

there is book of proof by Hammack, which probably won't cover everything a discrete math course covers but it will cover most of it

in general, good textbook for getting better at more formal math

np

[verbal crystal]

Out of these four, is the top left one the only simple graph?

All of the others have loops or multiple edges if I am understanding correctly

Alright, I figured that was the case. I became thrown off because the following part of the question says to redraw them if they aren't simple to make them simple with "[3/ea = 6]" listed for the points

so I thought that there was at least another one that was simple, but I guess the points might be a typo

[verbal crystal]

Is this correct?

nice, thank you

[brazen blaze]

yes, infinitely many

that is assuming there is even elements to begin with

what are you measuring?

ok,

what is your basis?

what is your specialty?

what is your idea?

what is your thought process?

what are your implications?

because if you have nothing to say might aswell leave it like that

ahhh

that depends if your cartesian product can form a multiplicative ring

yep.

it's basically just a factor of how much your shift is

it's kinda like saying that the real numbers are dense in unique areas and that the further you go away from zero the less factors you can find

[sudden minnow]

are you trolling @brazen blaze

[brazen blaze]

I don't understand how I could be trolling

I'm obviously an expert in this subject

[sudden minnow]

okay so you are trolling

[brazen blaze]

I wouldn't say that

I just am not able to see the bigger picture

how would you know more than I do?

[sudden minnow]

<@&268886789983436800> might wanna take a lot at wtf this guy has been typing out the past hour or so

[brazen blaze]

I thought you were gonna @ the helpers 😆

[hazy pine]

Yeah we don't tolerate misinfo and bullshitting

Do this again and you'll be banned

[sudden minnow]

what do you mean by non strict order and strict order

okay, that is a strict partial order

no

a non strict partial order is reflexive, asymmetric, transitive

so just the irreflexive swapped with reflexive

when you have a non strict partial order, the equality is built in

when you take the equality out, it becomes strict

[placid token]

any math expert available for help in two hours pm me

[vital dew]

OptimisticPeach

[wicked copper]

Hmm perhaps this question would've more appropriate for #groups-rings-fields

[sudden minnow]

perhaps you say

[cold owl]

Is there a closed form for
$$\sum_i^n \binom{2i}{k}$$?

Possibly an easier question: is there a closed form for the same thing, but modulo 4?

[vital dew]

SomeGirlSofia

[somber heath]

i = ?

[primal sluice]

Excuse me but can anyone help me with proving the flow decomposition theorem? Basically given a flow in a flow network, you can decompose the flow into at most |E| source-to-sink paths where E is the set of edges in the network.

[cold owl]

Ahh sorry! i from 0

[hazy jetty]

Can some help me wth these questions

[wicked ruin]

Probably

I believe any sum can be written in closed form

[somber heath]

this isn't true

[somber heath]

probably not

[wicked ruin]

Give me a counterexample

[somber heath]

find a closed form of
$$1 + \sum_{i=1}^{2^n} \floor{\left(\frac{n}{\sum_{j = 1}^i \floor{\left(\cos{\frac{(j-1)! + 1}{j}\pi}\right)^2}}\right)^\frac{1}{n}}$$

[vital dew]

yes yes yes no

[somber heath]

or a more easy counter example: $$\sum_{n = 1}^k \frac{1}{n}$$

[vital dew]

yes yes yes no

[wicked ruin]

Idts im sure there is a way to express this in closed form

Why do you think that you can't?

[somber heath]

because people have tried for the past 2300 years

[wicked ruin]

Ofc there is no closed form for that bcz there is a floor there making it piecewise, if it wasn't then it probably would be possible

[wicked ruin]

Oui and they found a way to reexpress it without a sum

Admitted it isn't the best

[somber heath]

what?

show me one

[wicked ruin]

1 sec

[haughty garden]

Ain’t that ||Willan’s formula|| or something like that? 🤔

[wicked ruin]

This is the video i am referring to

[somber heath]

yes

give me a closed form

[somber heath]

...how is that a closed form?

it still has a sum and a limit

[blazing rose]

I think im p aware of what properties to prove, but I struggle a bit with the definition of this field

what is Z3? and do I do the x2 +x + 2 thing with every x of the set?

[somber heath]

I assume they mean $(\bZ/3\bZ)[x]/\gen{x^2 + x + 2}$

[vital dew]

yes yes yes no

[stray reef]

i think not

looks like a localization to me

at least that is how i would interpret it

[blazing rose]

so without the multiples of 3?

[versed matrix]

Find number of ways to write a set with $m$ elements as union of at most total $t$ subsets. where $ t \le m+1$ ( intersection of subsets not need to be empty)

[vital dew]

Helaplus

[versed matrix]

Can someone help me to solve this? Atleast a hint

[somber heath]

do you know group theory

[blazing rose]

yes

[brave condor]

do yall get this

to open it?

i found his theorems, im just not sure how im meant to apply

[regal gate]

What is it known about the chromatic number of the plane? i.e., the smallest integer n such that you can color each point of the plane with n colors so that no two points of the same colour are one unit apart.

I think it is known that n>=5

whats the smallest upper bound known? If any?

[civic horizon]

https://en.wikipedia.org/wiki/Hadwiger–Nelson_problem

[regal gate]

oh didntk now it under this name, so I ignored that entry (didnt search too hard I admit)

Thanks

[weary tiger]

you guys know whats the closed form of sigma(1) ?

start =1, end = h

[weary tiger]

yo guys know if i did this correctly? my answer returns correctly fir first 111 test cases(coding it) and after that there seems to be a problem

idk where the 4 number difference is going

you changed the lower bound from 0 to 1 mysteriously on the second formula

[weary tiger]

yeah made that mistake and changed it later on, the original function has lower bound 1

just wrote it wring

wrong*

since all the terms are constant you can factor it out

they all become multiples of n****

[weary tiger]

so instead of hnm it becomes nm?

i meant n

[weary tiger]

so nsigma(1) = nh? isnt that what i did?

[weary tiger]

if the upper bound is h, then yes

yeah so i did that for all those cases in the question

sorry i couldn't see the difference from h to n in your picture

[weary tiger]

thats my bad, sorry

could you use this website to type it out?
https://latexeditor.lagrida.com/

this is the original function

it has no bound variable?

[weary tiger]

normally it comes with a bound variable, like the "i" in this image

do you happen to have a copy of the original question

[weary tiger]

its a coding question

OH

ok the last line says: Sum((n+i)(m+i), (i, 0, h+1))

[weary tiger]

this is the equation i got from deducting and it works according to online sigma calculators but i just need to convert it into a non sigma equation

[weary tiger]

this is the original formula

[weary tiger]

how i check if this equation works tho? cause i think they just gave us an example of what an unclosed example means

[weary tiger]

well, the last example

[crystal oyster]

Given a0 = 2, and an+1 = 3 · an + 4, show that for every n we have
2 + an = 4 · 3n

[weary tiger]

so this is your model of the problem right

[crystal oyster]

Does anyone know how to explain how to do this to me

[weary tiger]

this is the answer im getting (according to test cases n = 3008356, m = 3408563 and h= 2881 and i should be getting 29568895967556908)

so i think the equation is wrong that is given in the question, its prolly just an example

[weary tiger]

yes

[crystal oyster]

Given a0 = 2, and an+1 = 3 · an + 4, show that for every n we have
2 + an = 4 · 3n

sorry for reposting

[weary tiger]

you switched the variables.

just give me a second lmao

[weary tiger]

@weary tiger the formula for the pyramid is this one. i know it's used as an example but it's also the solution for the problem.

[weary tiger]

ill try to find the closed formula for it and see if it works

[weary tiger]

def pyramid(n, m, h):
    sum = 0
    for i in range(h):
        sum += (n + i) * (m + i)
    return sum

def pyramid_closed_form(n, m, h):
    return n * m * h + \
        n * (h * (h - 1)) / 2 + \
        m * (h * (h - 1)) / 2 + \
        (h * (h - 1) * (2 * h - 1)) / 6

# these are the same
print(pyramid(23, 5, 10))
print(pyramid_closed_form(23, 5, 10))

[weary tiger]

ye i just got the same result, apparently the closed form returns a different answer for the same test case

off by one

rounding error

i got this : return int( n * m * (h) + (n * (h-1) * h)/2 + (m* (h-1)* h)/2 + ((h-1) * h * (2*h-1))/6) and even i tried urs they both produce same result as the other equation i had gotten

[weary tiger]

that may be it, do you know how to not make it rounded

try using round function

the sigma function seems to return the correct function

[weary tiger]

ok, is it like a math.rouund syntax or just round()?

sorry for bothering u with so much work, im just a first year uni student and no professor has taught me this

round is builtin

you can use it without importing packages

[weary tiger]

i got the same answer as before

oh wait it works, instead of one / like n/2 i did n//2

tysm for ur help

np

[mighty oracle]

can someone help with this

[last flicker]

That's not discrete math. You probably want #precalculus

[rancid relic]

https://truthtablemaker.com/

[night stream]

for the question below would i use n^r making it 5^2 = 25

[covert bolt]

why are both graphs not isomorphic?

[red nest]

In graph B, if you delete the edge between 9 and 8 one of the components of the resulting graph has 3 vertices. You can then check that no matter what edge of A you delete this can’t happen. Hence they are not isomorphic

[covert bolt]

ohh

you mean like deleting the edge between 8 and 9 from graph B will result in 2 graphs with 3 vertices each

which cannot be replicated in graph A

[red nest]

Yeah

Although I just used something even weaker, which was that one of the 2 graphs has three vertices. Either way works though

[covert bolt]

ooo

ok thancc

[shut lotus]

hey do you guys have methods of proofs questions

[chrome fossil]

Is "not not equal" here a typo or is it intended

[stray reef]

you could argue as follows: both graphs have exactly two vertices of degree 2, however they aren't adjacent in the top graph but are in the bottom

[hollow tartan]

I already have the solution to this problem, but I'm confused as to why Bayes theorem is the chosen method for this problem.

Could someone explain to me as to why Bayes' theorem is used here? Are there any key words or phrases that indicate to use this method?

[unreal stump]

If it's conditional probability, it's always Bayes'

[hollow tartan]

why is that?

[unreal stump]

Well what else can you do

[hollow tartan]

because the conditional probability of an event can be written as

[unreal stump]

Well That's Bayes yes

[hollow tartan]

???

[unreal stump]

You just shuffle around some terms

And you get Bayes

[hollow tartan]

then where did that interesection go

[unreal stump]

P(E|F)P(F)=P(F|E)P(E) = P(E \inter F)

[hollow tartan]

in the problem, he never solves for intersection

[unreal stump]

So you eliminate the intersection using this

[hollow tartan]

???

can u write that in latex because i don't see the cancellation yet

[unreal stump]

$P(E|F)=\frac{P(E \cap F)}{P(F)} \
\implies P(E|F) P(F) = P(E \cap F)$

[hollow tartan]

I kinda see it

[vital dew]

Drake

[unreal stump]

$P(F|E)=\frac{P(F \cap E)}{P(E)} \
\implies P(F|E) P(E) = P(E \cap F)$

[vital dew]

Drake

[unreal stump]

So you have
$P(F|E) P(E) = P(E|F) P(F)$

[vital dew]

Drake

[unreal stump]

And this is Bayes

[crystal oyster]

Given a0 = 2, and an+1 = 3 · an + 4, show that for every n we have
2 + an = 4 · 3n

Could anyone help with this this, sorry I couldn’t get the Sub-Numbers to text out right

[weary tiger]

can you confirm if by "a0", "an" and "an+1" you mean $a_0, a_n \text{ and } a_{n+1}$?

[vital dew]

arthur-caruso

[dull haven]

im not sure if this belongs here but how do I solve this

[tame bone]

has someone of you good knowledge about DFA ? Its part of discrete Maths and I really could need help

or languages and grammar?

[chrome fossil]

Probably compute a few terms then find a pattern then prove said pattern with strong induction

[tame bone]

Give the largest Chomsky type for the following grammars. Give also indicates which language the grammars produce.

1. Grammar G := ({S, B, C} , {b, c} , P, S) with
   P = {S → bB | cC | c,

B → bB | cC | c,

C → ccC | cc}.

2. Grammar G := ({S, T} , {a, b, c} , P, S) with
   P = {S → λ | T b | cSc,

T b → bT,

T → a}.

3. Grammar G := ({S} , {a, b} , P, S) with
   P = {S → a | aSbb}

for example with this

[little ember]

can anyone explain me venn diagram

[regal gate]

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

[vagrant iris]

hi guys
can you help pls
Suppose that each of the digits 0, 1, and 2 has exactly 100 occurrences in the decimal notation of a certain integer x. No other digit occurs there. Prove there is no such integer y that x = y^2

[weary tiger]

any hints on where to start for this?

[vale cairn]

contraposition

[weary tiger]

ty ill give it a shot

[chrome fossil]

x = (0+1+2)*100 = 300 = 3 (mod 9)

[hoary orbit]

how does 127^2 = 195?

[high carbon]

That reads that it’s equal to 195 (mod 257). What this means is that in terms of the division algorithm, the quotient of 127^2 by 257 doesn’t matter to us, but the remainder is 195.

[hoary orbit]

yh

but how do u work out 195 (mod 257)

[high carbon]

The division algorithm.

At least that’s one quick way. Euclid’s algorithm is a more hands-on method, but I don’t recall the details.

[hoary orbit]

ok ill check it out

thx

[high carbon]

[dense granite]

in a flow network, does the capacity of an (S,T) cut include the capacity of edges flowing backwards from T to S?

[haughty garden]

not in its original definition, no. You typically only take the capacity in one direction of the flow

[tawdry steeple]

does anyone know of any question banks of divisibility/gcd/integer congruence proofs?

im trying to get some extra practice in, but my text book doesn't have that many exercises

[sick copper]

(∃x, y : X × Y . P x ∧ x R y ⇒ Q y) ≡ (∃x : X . ¬(P x)) ∨ (∃y : Y . Q y) ∨ (∃y : Y . (∀x : X . x R y) ⇒ Q y)

X and Y are non-empty sets, both P is a predicate over X, Q is a predicate over Y, and R is a relation from X to Y.

Can anyone help me with how to start 🥲

[weak elk]

can yall help me understand, how does 25 | 9^n (9-1+1/3) ?

[pale epoch]

try to rewrite 9^n (9-1+1/3)

[weak elk]

9^n * 3/3 ?

then it becomes 9^n / 3 * (27-3+1)

or am i doing it wrong

[vagrant iris]

pls help, how can i find the remainder after dividing the number 3^3^3^3... (2020 occurences of 3) by 46 (look at the file)

[pale epoch]

huh

how is (9-1+1/3) = 3/3 = (27-3+1)/3 ?

[weak elk]

how would you rewrite it i dont understand

i just multiplied 9^n by 3/3

[pale epoch]

but why

[weak elk]

well, i dont understan

how would you rewrite it?

[pale epoch]

well, (9-1+1/3) = 8 + 1/3 = 25/3

[weak elk]

so it becomes 9^n * 25 / 3?

[pale epoch]

so if 9^n is divisible by 3, then the product is divisible by 25..

well, yes

[weak elk]

so its the same?

[pale epoch]

sure, but thats not helpful

you want to rewrite it in the from 25 * something

[pale epoch]

and if you realize that 9 = 3^2, you can do that here

[weak elk]

3^2n/3 * 25?

[pale epoch]

yes

[weak elk]

what about this problem

[pale epoch]

inspect for values smaller than 2020, observe what happens, try to explain it

[vagrant iris]

u mean 3, 3^3, 3^3^3...? or what

[pale epoch]

yes

[lusty flame]

can someone help me with this question

Please give a concrete example, in English, to show that is not equivalent to , where is a predicate.In other words, your example needs to make it concrete what is , what is and what is .∀x∃yP (x, y) ∃y∀xP (x, y) Px y

@pale epoch

[weak elk]

thanks man i finally understood it, since n is any natural number, it will always be divisible by 3!

[vagrant iris]

it doesn't work, there is no regularity between them as far as i know(

[pale epoch]

what did you get?

[vagrant iris]

Nothing lmao

[pale epoch]

i mean the sequence of numbers you calculated

3 mod 46, 3^3 mod 46, 3^3^3 mod 46, ...

[vagrant iris]

oh, 3 mod 46 = 3, 3^3 mod 46 = 27, 3^3^3 mod 46 = 13, 3^3^3^3 mod 46 is 19

[pale epoch]

the last one is wrong

but keep going

do like the first 10 or so before you give up with no pattern

[weak elk]

lochverstarker

is the answer on the article correct https://math.stackexchange.com/questions/3558102/how-to-compute-333-phantom-bmod-46-for-pow

[pale epoch]

probably

there are multiple ways to solve this

once you notice the pattern, you can probably just induct

but like, the solution doesnt matter; i dont know it

its more important how you arrive at it

and in this case you just start doing some work

[vagrant iris]

thank you very much

!!

[scarlet geyser]

Guys can anyone teach me how to simplify this? We basically just skimmed boolean algebra, took em like 5 minutes to discuss it, but I found this problem and I wanna learn how to simplify it further, can anyone teach me how?

[restive surge]

I’m not sure where to but this, but I assume here might be the best place.

Given some even n, how many different sets to two valid sequences of parenthesis exist where no two ordered subsets of the sequences with the same indices also form valid sequences.

A valid sequence being one where all parenthesis can be paired. Like “(())”, “()(()())”, and “((())())” are valid but “)())((“ and “)(“ are not.

and for example of the second part, {“()(())”, “(())()”} would be counted but {“((()))”, “(()())”} would not be.

[weary tiger]

you can simplify a logic equation the same way you do with a mathematical expression, but for that you need to have basic understanding of alternate representations of boolean terms AKA you search wikis on the "boolean algebra properties" topic

[restive surge]

Wait I might have to rethink this proof

[weary tiger]

you can represent an opening parenthesis as a positive value and closing parenthesis as the same value but negative. then it would be a matter of keeping the total sum of the sequence non-negative as the index increases.

that's how code compilers check if you missed closing/opening brackets in your source-code

[elder berry]

Can you clarify what "...where no two ordered subsets of the sequences with the same indices also form valid sequences." means?

for some reason I'm not understanding the example

(As a side note, the number of ways to arrange the brackets is just ||the catalan numbers, number of Dyck paths|| and perhaps it's easier to count all of the invalid sequences, and subtract from the total)

[weary tiger]

i think he meant that if you break a sequence into two subsets, both of them are also valid sequences (that's what i got from his second example)

which would turn my argument about the sum of positive/negative terms more general to something like "if the total sum is zero before the sequence is over, you can divide it into two valid subsequences"

[restive surge]

Yeah I made a mistake with my proof. I guess a way to rectify this could be that: If it is possible to take some pairs of parentheses from the first sequence and some pairs of parentheses from the second list and compare their indices in their respective lists and they’re the same, then it’s invalid.

[restive surge]

That’s not what I need.

I don’t know how to explain this.

take my example of {“((()))”, “(()())”}. The pairs of the 1st and 5th are both valid.

therefore that set of two sequences is invalid

or maybe {“((((())))(()))()”, “()((((())))(()))”} is also invalid because the pairs at 1/2/5/6/8/9/12/13 can be taken out to both form valid strings.

Huh. With all the invalid sequences I’ve tried I’ve noticed that it always comes in pairs.

even the converse set comes in pairs

[night stream]

in this question what would be f(n)?

[distant osprey]

hii can anyone help with this

@restive surge @weary tiger ^

[restive surge]

why tf do you think I would know?

[distant osprey]

LOOOOOL

[distant osprey]

bc youve been answering other ppls discrete maths questions, jeez😭

[restive surge]

When did I do that?

even if I was it's been over six hours.

[distant osprey]

okayy jeez, u can just chill out and say no

[sudden minnow]

and you can just not ping random people to help for your question in the future

[distant osprey]

noted💀

arthur u cn ignore it😭

[weary tiger]

for question number one you need to understand what an equivalence relation is. there are three prerequisites of a relation before it can be called an equivalence relation

[distant osprey]

ILYYY OMIGOSH

[distant osprey]

so to answer this question ill just say i cant find R because nothing is reflective to 6

[weary tiger]

not really. it is only said that these ordered pairs ARE in the relation, not that they are all the pairs

[distant osprey]

i would have to prove all the other relations?

[weary tiger]

so you must fill in the blanks, like how (8, 7) is present because (7, 8) is present and the relation is symmetric

[distant osprey]

ohh

[weary tiger]

it's a single relation. a set of ordered pairs

you must write out all the pairs, knowing the properties and just some of the pairs

for the second question you must equate both functions, like solving a quadratic

[distant osprey]

oh i got the second question already

[weary tiger]

f(x) = g(x)
=> f(x) - g(x) = 0

alright

[distant osprey]

can i show u my answer?

to double check

[weary tiger]

sure

[weary tiger]

you just missed the correct way to present the solution, that is, the set of solutions is S = {3, -1}

[distant osprey]

but it just wants what x is as a real number right?

[weary tiger]

3 and -1 solve for f(x) = g(x)

[distant osprey]

ohhh yeah

[weary tiger]

both are real numbers so all good

[distant osprey]

true true