discrete-math

[twilit cloud]

She wants us to find the number of spanning trees that exist while still connecting all vertices

She didn't specify that!

[stray reef]

spanning trees have to connect all vertices by definition

[twilit cloud]

The actual question is "How many spanning trees that touch all the given vertices can be made"

That's dumb

[coral raven]

what does 'spanning' mean to you

oh i'm late

[fossil stump]

Is it yes or no and why?

[coral raven]

bruh

[fossil stump]

Read username before bruhing.

[stray reef]

can perfect squares be divisible by 3 but not by 9?

[fossil stump]

Nope.

Okay that 1 short message made me understand everything. Thank You Ann!

Also.

"Prove that if a number has an odd number of divisors then it is a perfect square.".

Can you explain this solution?

[stray reef]

the divisors pair up

if the square root is present among them it is the only one unpaired

[fossil stump]

Huh?

[fossil stump]

Yeah.

[stray reef]

the divisors arrange themselves into pairs

[fossil stump]

Oohh.

So coincide means the root one?

[stray reef]

"coincide" means "be the same"

[fossil stump]

Yeah.

[stray reef]

the only time a divisor gets paired with itself is when it is sqrt(n)

[fossil stump]

Oh WOOOW.

This is so cool I did think the proof would be like this at all!

Thank You Ann!

[weary tiger]

is there a practical scenario where sup(AB) is actually less than (sup(A))(sup(B))

I think sup(AB) is guaranteed to be equal to (sup(A))(sup(B))

since the real numbers is totally ordered, the chains are too meaning all the chains have a maximal and therefore sup(chain) = maximal

say sup(chain1) = 2 and sup(chain2) = 5 then sup(chain1chain2) = 10

set builder used for the “multiplication” of two sets

[obtuse lance]

that's what the last line is trying to say

it's equality for positive numbers

[weary tiger]

OHH wow I’m dumb

🤦

[obtuse lance]

🤣 happens to everybody

[quaint pulsar]

hi anyone has good tutorial video for this chapter ? I have trouble with reading, I need videos. thanks!

[jagged junco]

@quaint pulsar maybe this can be good https://www.youtube.com/watch?v=WW-NPtIzHwk they have more chapters in the series

[jagged junco]

Any clue?
How many undirected graphs on vertices {1,2,...,2n}, the degree of each vertex is 1, and for every 1≤i≤n: {i, (n+i)} isn't an edge

[vital dew]

Iol

[coral parcel]

n is the variable that goes to infty, and r is a constant -- right?

[shrewd birch]

Yeah

[coral parcel]

(As an aside, it would probably fit better in #calculus, by the way -- limits are kind of the antithesis to "discrete".)

[shrewd birch]

Ah sorry, I didn't know where to post it. I'll move it there

[sudden osprey]

Does anyone know, how this problem/solution works. Find a number that is 57 times smaller when the first digit is removed.

Here is the formula/solution that was used. The answer is 7125 which makes sense.

But what if I were to try for another example where I want the number that becomes 4 times smaller when the first digit is removed? Is this a scenario that has no solution?

[coral parcel]

Yes -- let the small number be a, then we're looking for a situation where 4a = a + b·10^n for some n and some b in {1,2,3,...,9}. But that means that 3a = b·10^n, so b is one of 3, 6, 9 and in each of those cases a ends up being at least 10^n, so it doesn't produce a solution.

[sudden osprey]

Meaning no power of 10 is divisible by 3?

[coral parcel]

Right, due to the fundamental theorem of arithmetic.

[sudden osprey]

@coral parcel Thank you so much!

[turbid swallow]

How to generate all possible stable matchings? One way for producing a stable matching is mating ritual, another is mating ritual but the girls are serenaders. So these are two stable matchings. Are there any way to find other stable matchings?

[coral parcel]

I don't think there are any other well known algorithms (better than generating all matchings and filtering for stability).

If you just want a few other examples I think you you could start with a random match and iterate possible breakages until you reach a stable point, but that's hardly a way to generate all of them. (And I can't even immediately come up with an argument that it will terminate).

[robust goblet]

Does anyone know when we use Generating Function or Exponential Generating Functions to find a_{n} in recursion formula? My lecture don't mention that 😦

[stray reef]

@robust goblet there is no one-size-fits-all rule

it's just whichever one works in your case

[weak sand]

can someone please tell me what's wrong with this answer and what's the correct answer?

[stray reef]

missing 7:3 and 17:13

[weak sand]

great! Thank you 🙂

[weary tiger]

Hey everyone, I was wondering if anyone could give me an idea of how hard these semesters will be based on your own experience.

[heavy tinsel]

Four friends (Erin, Jagmeet, Yves-François, and Annamie) are planning a trip to Ottawa, and they need to assign tasks (booking flights, booking hotel rooms, and making an itinerary) to three people. Erin cannot be trusted to make an itinerary; also, either Jagmeet or Annamie must book hotel rooms. How many ways can they assign tasks?

I think its just (number of ways to book room) * (num ways to book itnerary) * (num ways to book flights) = 222?

[haughty garden]

Assuming that your answer is 2 * 2 * 2, yes

[coral parcel]

(It sounds like a quite inefficient way to plan travel. You'll need an itinerary before you know for sure where and when to book flights and rooms, and the availability of affordable bookings may in turn influence which itinerary you pick).

[heavy tinsel]

Yeah sorry I should’ve checked

[coral parcel]

I assume you're not responsible for the bizarreness of the problem statement.

[heavy tinsel]

Nah it’s some exercise from the end of this section I have to read for this week

[heavy tinsel]

Oh this was supposed to be for opengangs lol

[weary tiger]

how is it 26+ 26(36)+...?

[stray reef]

and a variable name consisted of a single letter followed by at most five characters (letters or digits)

how many names are there consisting of just one letter?

and one letter followed by one character? one letter followed by two characters? etc.

[weary tiger]

a character can be letter or digit right?

so fo first first letter is 26

for the second letter it can be one out of 36 choices

26 letters and 10 digits

[stray reef]

you're not answering my question here

[stray reef]

but this is true and has even been explicitly stated in the text

[weary tiger]

how many names? I guess

26?

[stray reef]

what is 26 the answer to?

[weary tiger]

how many names can be made of 1 letter

[stray reef]

okay

and how many names are there that consist of one letter followed by one character?

[weary tiger]

26(36)

[stray reef]

and how many names are there that consist of one letter followed by two characters?

[weary tiger]

yeah I see the pattern

my problem was

I was looking at it

as if the letetrs were independant

so we would have 36 choices for each

slot basically

[weary tiger]

thank you that cleared it though

[turbid swallow]

Thank you, this was really helpful. I only need a few examples, will try to find them in my free time.

[mental nimbus]

Hi, Im trying to understand Principle of Inclusion Exlusion and as an example will take this exercise:

A certain class has 20 students, and meets on Mondays and Wednesdays in a classroom
with exactly 20 seats. In a certain week, everyone in the class attends both days. On
both days, the students choose their seats completely randomly (with one student per
seat). Find the probability that no one sits in the same seat on both days of that week.

Am I correctly understand that we need to take here Intersection of sets that students sits on the different seats?

[languid ether]

hi all was wondering if someone can explain something to me about cartesian products. a book i'm reading confuses me, because it asserts you can construct a cartesian product RxN or NxR. but i thought the meaning of a cartesian product is a set containing all ordered pairs of the form (lets say) (N, R). So one has to produce a set of all sets that match every natural number to every real number. but isn't the point of cantor's diagonalization argument that one cant produce a list like this, because there is no one to one correspondence between N and R (R is uncountable)?

or is it that for every natural number there are just 'uncountably infinitely more' elements per natural number than naturals vis-a-vis reals

[stray reef]

you're overthinking it

have you ever played cards?

a deck of cards is kind of like a cartesian product between the set of suits {spades, hearts, clubs, diamonds} and ranks {A, K, Q, J, 10, ..., 2}

[final cliff]

Might be worth looking at simple examples of functions, bijections and cartesian products to work at the differences between those three things.

[languid ether]

for those cases its pretty clear

[final cliff]

For example what is {1,2}x{3,4}?

Can you give a bijection from {1,2} to {3,4}?

Etc

[languid ether]

the finite cases are easy to grasp

[final cliff]

My point is mainly that the cartesian product of two sets and a bijection between two sets are two different concepts.

[languid ether]

ah I see

[final cliff]

So like, if you take NxR, it's not even a function, let alone a bijection

[languid ether]

okay that's the kind of answer i was looking for

thanks

[final cliff]

It's still technically a relation though lol

No problem

[weary tiger]

whats the difference between an implication

and a logical implciation? -> and =>

[pale epoch]

in (most) undergrad classes there is no difference

a logician might use => to talk in the metalanguage and -> to talk in the formal language

[weary tiger]

I see thanks

[hollow ferry]

isnt this infinite sum supposed to equal ((n^2)(n+1)^2)/4 ?

i know how to show it with induction if it is equal to that but the way they have it written here is throwing me off.

[weary tiger]

I believe the statement is also true

[hollow ferry]

how to i go from the induction hypothesis to that then?

[olive wren]

First off, it is obvious for $n=1$.

Notice that:
[ (1+\cdots+n+n+1)^2 = \left((1+\cdots+n)+n+1\right)^2 = ]
[ (1+\cdots+n)^2+2(1+\cdots+n)\cdot(n+1)+(n+1)^2 = ]
[ 1^3+\cdots+n^3+2\cdot\frac{n}{2}(n+1)^2+(n+1)^2= ]
[ 1^3+\cdots+n^3+(n+1)^2(n+1)= ]
[ 1^3+\cdots+n^3+(n+1)^3 ]

[vital dew]

Slurp

[north ruin]

Hey, so I'm currently doing homework related to the Pigeonhole Principle and I don't know how to solve the second question. Does anybody have any ideas?

[coral parcel]

Which reasoning led you to 169?

There's a nice hint too.

[north ruin]

H(N-1)+1
idk why I just can't understand what it's asking

[coral parcel]

What are H and N if that gives 169?

[north ruin]

So H = 26 and N = 7 in the first question, giving us 7(29 - 1) + 1 = 176
In the second question, would H = 29 and N = 7?

[coral parcel]

Yes, except that it's asking for "the largest number the property doesn't hold for" rather than "the smallest number the property does hold for".

[north ruin]

so that would mean N = 1?

[coral parcel]

Not "the largest number of colors in the rainbow" but "the largest number of voting members in the club".

[north ruin]

so are we finding N?

[coral parcel]

I'm sort of getting the impression that you don't really understand what the first question is asking for either? (But just made a lucky guess at which formula to plug some numbers from the problem into so the website would accept the answer)?

[north ruin]

I understood the first question was asking for P but I don't know what to do with the second question

[coral parcel]

Try to state your understanding using something more wordy than simply the name of a variable in your formulas.

[north ruin]

What I mean was it was asking for the total number of people, which would be P

[coral parcel]

That's not actually what it's asking for. I can see it's a bit sloppily worded -- but when the problem says

how many people can you guarantee will be in the club?
it really means
at least how many people does the club need to have for my [the fictional narrator of the question] claim above to be true?

[north ruin]

ah ok

[coral parcel]

So there are some club sizes where one can guarantee the winning color has at least 26 votes, and other club sizes where one cannot guarantee that.

You were asked to find the smallest possible club where the guarantee can be given.

In the second question you're asked to find the largest possible club where a similar guarantee (but with different numbers) cannot be given.

[north ruin]

oh

[hollow ferry]

is b asking me to show it with induction? because the wording of part c makes me think i am intended to show b without induction.

or do i just manipulate it using algebra

[coral parcel]

It pretty expressly asks you to use mathematical induction.

Whoops, no, I can't read.

C asks you to use induction.

[hollow ferry]

for part c lol

[coral parcel]

B doesn't care about your method.

I bet the problem setter decided not to have an (a) just to confuse me.

[hollow ferry]

oh there was an a hahah

had to verify the binomial theorem for n = 1, 2, 3

[viscid escarp]

I think this goes here

Could someone show the intermediate steps for this index change

I haven't been able to figure it out

[haughty garden]

j = i - n^2 + 4 which means that i + 4 becomes n^2 + j and j ranges over from 1 to n.

You can verify that this is right because, if i = n^2 - 3, then j = (n^2 - 3) - n^2 + 4 = 1 and, if i = n^2 + n - 4, then j = (n^2 + n - 4) - n^2 + 4 = n

[viscid escarp]

ahhh

thank you that was very informative

[pearl lodge]

Question about topological ordering (specifically total order) from my textbook, a picture is included. We have a diagram of the relation for ‘divides’ in set A. For clarity call the divides relation R. A has partial ordering with respect to R, as every element is reflexive, antisymmetric and transitive. (2 divides 6, 6 divides 18, 2 thus divides 18). My understanding of total order relations, is that R is not total order, as 2 and 3 do not divide. So, set A is a partially ordered set. [i believe this is correct so far, but feel free to correct if wrong]. My confusion arises when I ask myself what the book means with the term “total order”. I don’t understand if this is a set, a relation, or some other object. My money is on relation with the special caveat that all elements further right from some element in the total order, if the original relation held for those elements the total order also holds. So is it just a specific listing of the elements in A?

[coral parcel]

small terminology quibble (which might actually be relevant for your confusion): We don't say "A has partial ordering with respect to R", we say "R is a partial ordering of A".

You're correct that A is a partially ordered set, but you should beware that calling R a "partial order" doesn't require us to find a set of elements that don't compare -- "partial order" just means a reflexive antisymmetric transitive relation and does not make any claim about whether or not it is total. So a "total order" is a special kind of "partial order" -- and for example ≤ is _both a total order and a partial order.
(This does sound daft if you go by the everyday meaning of "partial", but mathematics has a quite firm tradition for using the word in this way, which we just have to deal with).

A "total order" is a relation that is reflexive, antisymmetric, transitive and total (that is, for every pair of x and y in the domain either x R y or y R x holds).

A "totally ordered set" is a set together with a total order on it.

[pearl lodge]

Okay so when you say "a totally order set is a set together with a total order on it", How does this appear? [If R is a total order of A, then A is a totally ordered set?] For general relations between two different sets, say X and Y, I understand the relation is a subset of the cartesian product between the two, [my understanding is that the rules put in place to define the relation create the tuples in the relation] and R appears as a set of tuples for the elements that follow the rules of the relation. For a set together with a total order on it, sets themselves are the same irrespective of the order of the elements, so a total order is not a rearrangement of the elements themselves, but instead a relation that defines the relationship between each element using transitivity? (As an example of what I mean, a subset of the example in the text might be the graph of 2,3,6 and 4. A total order for that subset could be 3 < 2 < 4 < 6. Is this the same as R = {(2,4),(2,6),(3,6)}?)

For your point about partial orders vs total order, this is a similar argument to all thumbs are fingers, or all functions are relations, but not all relations are functions?
[I rewrote this a few times with certain sentences boxed as what I believe is a reasonable line of thinking, but they could be wrong, and just serve to separate my thoughts]

[coral parcel]

If R is a total order on A, then formally we should say "(A,R) is a totally ordered set", but when it is clear from the context which R we have in mind it is traditional to get away with just saying "A is a totally ordered set" instead.

I think your second question is, why do we say the "total order" means the comparison relation rather than just the sequence of elements? This is because sometimes there are too many elements to list in a sequence. For example, ≤ is a total order on the set of real numbers -- there are too many real numbers to arrange them all in a sequence in a meaningful way, but we can still speak of the relation that compares reals as a definite mathematical object.

I think there's actually a bit of controversy in English about whether a thumb by itself can also be called a "finger" (despite everybody agreeing that most humans have ten fingers, in plural). Perhaps that makes it a particularly good analogy for the situation here. 😛

A total order for that subset could be 3 < 2 < 4 < 6. Is this the same as R = {(2,4),(2,6),(3,6)}?
No, because {(2,4),(2,6),(3,6)} does not tell us that 3 comes before 2.

[pearl lodge]

I guess my confusion boils down to what the last section of the textbook is actually telling me. A total order sequence is found, and the relation between elements in that sequence is the total ordering relation?

So then you would need an additional element {(2,4),(2,6),(3,6), (3,2) }

How does the object (A,R) appear? Is it just A with the knowledge that A is a totally ordered set? (sorry that'll be my last question for the night I promise lol)

[coral parcel]

The textbook is being a bit coy about what the total order it constructs really is. By its own definition it should have produced an transitive (etc) relation, but it's actually just writing a sequence.
So you'll need to understand that 3 < 2 < 4 < 6 should actually refer to the set {(3,2), (3,4), (3,6), (2,4), (2,6), (4,6), (3,3), (2,2), (4,4), (6,6)}.
You can perhaps view "3 < 2 < 4 < 6" as a horizontally written Hasse diagram for the set of pairs.
When the sets are finite, you can always write a total order like that, and as you see it's considerably shorter. Just be aware that it's not what the formal definitions say we "should" be talking about.

How does the object (A,R) appear? Is it just A with the knowledge that A is a totally ordered set?
(A,R) is an "ordered pair" -- which is to say, some kind of mathematical "thing" that knows it has a first element that is the set A and a second element that is the relation R, and which we can ask what its first and second elements are.
You will almost never see the ordered pair written out explicitly for purposes like this -- and perhaps I caused more confusion than understanding by doing so. Usually we use words instead to specify the two components separately and that we're thinking of the combination of them as an ordered set. Something like "A with the knowledge that we're using R to order it" might be a better representation.

[pearl lodge]

Okay that makes sense I think. I'll read through the section again and see if my understanding of it improves. Thank you very much for all the help

[haughty magnet]

Is this the right place for help with the master thm?

I think the answers here are (d) and (c) but I am struggling to find similar examples

[haughty garden]

f(n) is polynomial since 8^(log_2(n)) = 2^(3log_2(n)) = n^3 so pretty sure the Master Theorem is okay for Q7

[haughty magnet]

Okay and for Q8, is n^3sin(n) not a polynomial ?

I thought sin(n) can just be counted as an upperbound of 1

[haughty garden]

I think there's a condition that is violated because of sin(n)

I think f(n) needs to be monotone

(at least on n > 0)

[haughty magnet]

ok thanks a lot

[thick nacelle]

need help, using the pigeonhole principle

for 1) and 2)

[haughty garden]

1. If you have two of the same colour for each of the sweets, then the next one you pick guarantees that one of them will have three sweets.

2. Hint: If x - y is a multiple of 7, then x = y (mod 7). How many equivalence classes do you have in modulo 7?

[thick nacelle]

how can I use the actual formula for the principle?

10n + 1?

but its not intuitive...

[haughty garden]

Well, the first part of the problem in Q1 is to figure out how many "pigeons" there are, and the second is to prove it using the ph principle

Suppose you have 10 sweets. Can you guarantee that you have three of the same colour?

[thick nacelle]

ah I see

that makes sense

what about question 2?

[haughty garden]

You only have 7 possible remainders when you take everything modulo 7 (0, 1, 2, 3, 4, 5, 6). So, among 8 integers, two must land in the same remainder class. This is precisely what it means for x - y to be divisible by 7.

[serene glacier]

Is there no general chat? (sorry for off-topic)

[haughty garden]

there's #discussion, #math-discussion if you want to discuss math, and #chill

[serene glacier]

I can't see those channels

[haughty garden]

can you see them if you click on those links

[serene glacier]

Nope, they just show as plain text, not links

Because of this?

[haughty garden]

it might be because you have the studying role

yeah

[serene glacier]

No idea how I got that...

[haughty garden]

,iam studying or something like that probably

[serene glacier]

I just joined the server about 30 seconds ago

[haughty garden]

I don't remember the actual command

[serene glacier]

Oh shit nvm I got it

sorry

[haughty garden]

all good

[wide vine]

pretty basic question but im new to the notation and not sure if this is valid

woudln't you use the subset notation

[stray reef]

the text here is kinda hard to read

[wide vine]

is that valid way

hang on

A = { x ∈ Z: x is an integer multiple of 3 }
B = { x ∈ Z: x is a perfect square }
C = { 4, 5, 9, 10 }
D = { 2, 4, 11, 14 }
E = { 3, 6, 9 }
F = { 4, 6, 16 }

(g)
E ∈ A

[stray reef]

right

E ∈ A is valid notation - sets can, in principle, be members of other sets - but in your case E ∈ A is of course false

[wide vine]

oh

like if you have a set in a set?

you would use that?

[stray reef]

...yes

[wide vine]

okay

[sleek rampart]

@wide vine {{3,6,9}} != {3,6,9}

but {3,6,9} ∈ {{3,6,9}}

[wide vine]

I see

haven't got to set of sets which looks like it is the next section but makes sense.

[wide vine]

Is the following notation proper to express the set I'm interested in

C = { x ∈ Z : P(x)= 2x-5, 1<=x<=7}

The set should be

{-3,-1,1,3,5,7,9}

Idk about the P(x) part after the :

I just don't know if I have communicated what I want correctly through "set builder notation"

[wide vine]

I feel like maybe I need to say something about the domain of P(x). It seems wrong

[olive wren]

wdym by P(x), and how are -3,-1,9 in the set if 1<=x<=7?

[wide vine]

That was my issue. My idea on the right was basically that is the domain of P(x)

[olive wren]

But what is P(x)?

[wide vine]

2x-5

[olive wren]

Oh I see

How about

[wide vine]

Idk how I wrote it is valid

[olive wren]

${2x-5\mid 1\leq x\leq 7\in\bN}$?

[vital dew]

Slurp

[olive wren]

The left side of the set builder notation is what is actually in the set, the right side is the condition

[olive wren]

So what you wrote here doesnt make much sense, because P(x)=... doesnt affect what is in the set

[wide vine]

I see.

[slow jewel]

Any ideas guys

How did they get this answer

[coral parcel]

Didn't we see that problem posted fairly recently?

[slow jewel]

Two weeks ago

i dont think i got a response

[coral parcel]

Do you know how to count spanning trees in a complete graph?

[slow jewel]

n^(n-2)

[coral parcel]

And if you have two graphs joined at just a single vertex, then a spanning tree for the whole thing is made up of a spanning tree for one side of the graph and a spanning tree in the other side in the graph.

[slow jewel]

i dont understand

[coral parcel]

Can you be more specific about what it is you don't understand?

[slow jewel]

The answer should be 2*5^3

right

[coral parcel]

Why?

[slow jewel]

I dont know

its wrong

[coral parcel]

Why?

[slow jewel]

Spanning tree of the first half plus the spanning trees of the second half?

5^3

+5^3

[coral parcel]

But if you just choose one of the halves and pick a spanning tree in just that half, you're not going to reach the vertices in the other half.

[slow jewel]

yes

[coral parcel]

You are? How?

[slow jewel]

but how to you get 5^6

Its like being disjoint

[coral parcel]

I explained that.

[slow jewel]

Is this meant to be simple?

[coral parcel]

Yes.

If I were asking you how many two-digit numbers exist, would you answer "twenty, namely ten for the first digit plus ten for the second digit"?

[slow jewel]

Im not following

hold on

nah

i dont get it

One section of the graph has 5^3 spanning trees, yes?

[coral parcel]

Right.

[slow jewel]

so does the other

[coral parcel]

Right.

[slow jewel]

Where do i got from there?

[coral parcel]

Do you agree with the claim I made here?

[slow jewel]

yes

i agree

[coral parcel]

Do you also agree that a number with two digits is made up of a digit that goes on the left and a digit that goes on the right?

[slow jewel]

yes

[coral parcel]

So how many two-digit numbers are there? 10+10?

[slow jewel]

indeed

but how has this got to do with the question?

[coral parcel]

Are you sure there are only twenty different two-digit numbers possible?

[slow jewel]

no

there is 10*9

wait

10*10

[coral parcel]

Right, if we don't accept a leading zero.

Or 10×10 if we don't.

[slow jewel]

ahh f*ck

i aint good at combinatorics

thats why i added them

[coral parcel]

So you get it now?

[slow jewel]

yes, because if you fix a spanning tree for the first section there are still 5^3 different combinations for the second section

[coral parcel]

Exactly.

[slow jewel]

Graph theory is hard

[gilded marsh]

Hello, I am having trouble rewriting statements by filling in the blanks.

Sorry for the sideways photo

[coral parcel]

,rotate

[astral creek]

a) x^2 = -2
b) a real number r such that ____
Not too sure about the second one tho

[gilded marsh]

I got the answer but thanks that was what I got as well!

And wouldn’t it be x^3 since it’s cubed?

[distant bobcat]

$x= - \sqrt{2}^3$ would work as $-( \sqrt{2}^3)^3=-2$

[vital dew]

Fredrikpiano

[stray reef]

@distant bobcat did you try to write the cube root of 2

cause that'd be $\sqrt[3]{2}$, not $\sqrt{2}^3$

[vital dew]

Ann

[distant bobcat]

yes, thats right

now I know how to write it in latex thanks

$2 ^{\frac{1}{3}}$

[vital dew]

Fredrikpiano

[distant bobcat]

could write this also

[wide vine]

∅ ⊆ P(X)

this is false right?

P(X) = { ∅ , {1} } for example

but

[pale epoch]

check the definition

[wide vine]

{ ∅ }

would be

[pale epoch]

is every element of the empty set in P(X)?

[wide vine]

well it is empty so i guess so?

[pale epoch]

asking the other way around

can you give an element that is in the empty set but not in P(X)?

[wide vine]

no? there is no element in the empty set to give

[pale epoch]

yes

in fact it doesnt depend on P(X) at all

the empty set is a subset of every set

[wide vine]

oh yeah true

hmm

i see

wait

so it is an element and a subset?

[pale epoch]

in the case of the powerset, yes

[wide vine]

okay

[slow jewel]

Anyone know how to do part b or c

[austere cedar]

The easiest way for b) is probably to write down an Hamiltonian path (try to first go through the vertices of the type (0,y), then trough them of type (1,y), them (2,y) etc). For c), you need to write down appropriate Graph automorphisms (here you can use the fact, that the graph definition is already symmetric in the numbers 0,1,2,3)

[slow jewel]

thanks

Here is the solution (path) but it doesn't include the vertex (0,2)

[pale epoch]

it does in the first step

they want to go from 0,0 to 0,1 to 0,2 to 0,3, then 1,3 to 2,3 to 3,3

but just draw the graph there are many ways

for (a) also draw it, it you cant see it

you can just write down every neighbour for a given vertex and count how many there are

[slow jewel]

thanks

i see

[distant bobcat]

Is Eulers theorem called a generalization of Fermat's little thm. because we do not require n to be prime in $\alpha^{\phi(n)} \equiv 1 modn$ where as we require n to be prime in Fermat's little thm. ?

[vital dew]

Fredrikpiano

[pale epoch]

yes

[distant bobcat]

And re replaces p-1 with the phi function for Eulers thm. Im wondering about the intuition behind this. Perhaps I will get a better feel after going through the proofs for both thm's.

[uneven violet]

It's because Euler's theorem is straight-up a generalization of Fermat's little theorem. If you put $n=p$ in Euler's theorem for some prime $p$, then since $\phi(p)$ counts the numbers less than $p$ that are relatively prime to $p$, you get $\phi(p) = p-1$ (remember $p$ is prime, all numbers less than $p$ are relatively prime to it). So Euler's theorem reduces to $\alpha^{p-1}\equiv 1\pmod p$.

[vital dew]

TimeTravellerOne

[distant bobcat]

That makes a lot of sense. Thanks

[wide vine]

do these look good?

a b c that is

[coral parcel]

Yes.

[wide vine]

thanks

[wide vine]

would the answer to this be {x∈ Z+: x is a positive integer multiple of 120} solved

[olive condor]

Why is it “multiple of 120”?

LCM of 1,2,3,4,5 = 60

So it should be “multiple of 60” instead

[wide vine]

Yes, I got help in one of the channels but guess I never changed my answer here

[astral creek]

ye mb

[marsh agate]

Hello, i have a question on logic equivalences - discrete mathematics. The problem is to prove (p then r) or (q then r) = p then (q then r). On trying to use the laws there was a similar problem that one of the steps of the solution was p → (q ∨ r) ≡ ¬p ∨ (q ∧ r). Is it using conditional-disjunction equivalence? If so, why did the OR change to AND. Is it an error?

[haughty magnet]

I’m writing quizzes for an algorithms class next semester. I’m having trouble coming up with multiple choice questions about FFT. Anyone out there have some good questions?

[final cliff]

Looks like a typo to me since P->Q is equivalent to ~P v Q. You can always double check with a truth table.

[outer kiln]

Hello everyone

[haughty garden]

It depends. Some people include 0 as part of the natural numbers and some people exclude it

Seems like your professor includes 0 as part of the natural number set

[outer kiln]

Lets assume 0 is excluded. Under this scenario, would the question be considered wrongly framed?

[haughty garden]

It would just start at 16 and not 4

So you’d have a different starting value

[outer kiln]

Everywhere i searched they didn't include 0 in natural numbers weird lol

[haughty garden]

Ideally your professor should make it clear which convention of the natural numbers they refer to

[outer kiln]

I just read this

Lol we all know our education system in the whole world is broken and the people who are teaching should not be teaching most of them :p

[haughty garden]

I’d prefer to use positive integers or non-negative integers to specify which set we’re talking about

But meh, as long as the professor makes it clear what they mean by the natural numbers

[outer kiln]

How would i solve that question then lol

n = 0 , f(0) = 4

n = 1, f(1) = 16

n = 2, f(2) = 36

n = 3, f(3) = 64

[haughty garden]

f(1) would be 4 + 16

You’re adding all of the previous terms

[outer kiln]

Recursive case means to denote the next value of function using the previous term as function right

[haughty garden]

You’re adding all previous terms up to and including (2(n + 1))^2

[haughty garden]

Yes

[haughty garden]

So it’ll be something like f(n) = f(n - 1) + blah or something like that

[outer kiln]

Hmm i am so tired at this point lol i cant even think haha

Are you a graduate student?

[haughty garden]

Nah undergrad

But yeah, take a few moments to ponder about it

[outer kiln]

Did you figure it out lol?

[haughty garden]

1. f(n) is the sum of all previous values up to and including (2(n + 1))^2
2. f(n) being recursive means you use the previous results to define f evaluated at n

So play around with a few values of n and it’ll become a bit clearer

[outer kiln]

I understand what you mean by 2) but unfortunately didn't understand what 1) means.

[haughty garden]

[ f(n) = \sum_{i = 0}^n (2(i + 1))^2 ]

[vital dew]

opengangs

[haughty garden]

So for example, f(1) would be 4 + 16 since you compute (2(0 + 1))^2 + (2(1 + 1))^2 = 4 + 16

f(2) would be (2(0 + 1))^2 + (2(1 + 1))^2 + (2(2 + 1))^2

And so on

[outer kiln]

I actually was so confused, thank you for this, i initially thought that f(1) was just 16 and f(2) was just 36

Does induction have to do with findin recursive

[haughty garden]

No need for induction; though you might want to prove that your recursion is correct by induction

[outer kiln]

maybe later the proof another day

[haughty garden]

Think about what the difference between f(1) and f(2) is. Then the difference between f(2) and f(3) is

See if you can spot a general pattern for f(n) and f(n - 1)

[outer kiln]

f(0). = 4

f(1) =20

f(2) =56

f(3). = 100

f(4) =200

f (5) =344

[haughty garden]

You might want to write it in (2(i + 1))^2 form if that’s easier

[outer kiln]

so it is

(2(i + 1))^2 ) + the previous one

[haughty garden]

Yup

[outer kiln]

so it would be f(n) = n +

f(n-1)

[haughty garden]

\begin{align*}
f(n) &= \sum_{i = 0}^n (2(i + 1))^2 \
&= \sum_{i = 0}^{n - 1} (2(i + 1))^2 + (2(n + 1))^2 \
&= f(n - 1) + (2(n + 1))^2
\end{align*}

[vital dew]

opengangs

[outer kiln]

How did you derive this

[haughty garden]

You can split the sum up by discarding the n term and then looking at the (n + 1)th term separately

It’s the same as saying (2(0 + 1))^2 + … + (2(n - 1 + 1)^2 + (2(n + 1))^2

[outer kiln]

I am really tired i think when i come back to read it fresh i will underrstand it thank you very much

You'rer a samrt guy, are you math major

[haughty garden]

Yeah math and computer science

[outer kiln]

Forr this i got [C-(A union B)] union [ (A intersection C) - B) union [ (A interrsection B) - C] union (A intersection B intersection C)

Its the last one lol, i think i got it right, but it might have a more compact final answer more simplified

[haughty garden]

That looks right from a glance

[olive condor]

Do you accept “(C - B) union (A intersect B)”?

[wide vine]

If A = B would the result just be the empty set?

for the Difference and Symmetric difference operation

my book has these as defintions

and that is about it

so im not sure what the result would be

Q: Let A and B be equal sets, what is A-B and what is A ⊕ B ? (This is my question I am not sure on)

[olive condor]

Ya, A-B is an empty set if A = B

You can see this by substituting A for B in the set notation

[wide vine]

okay Thanks 🙂

[olive condor]

You can do the same for the symmetric difference

[wide vine]

Yeah I see now

[outer kiln]

im confused lol

you guys got a final answe

[cerulean wind]

technically... should be {x in A : x not in A}

[coral parcel]

Both are valid ways to write it.

[outer kiln]

which is the final answe lol

[wide vine]

these past few messages I believe were not relevant to what you posted btw

I asked a question after

so sorry if there was some confusion

[weary tiger]

how many triples (A, B, C) of subsets of {1,2,...,n} exist such that A ∩ B ∩ C = ∅; A ∩ B ≠ ∅; A ∩ C ≠ ∅?

is this the answer?

$\binom{n}{6} - 2\binom{n}{5} + \binom{n}{4}$

[vital dew]

Mofumofu

[weary tiger]

nevermind

it's to the power of, not choose, and i forgot you can put something outside the set as well

fun question tho

[pearl bronze]

can someone please how to get x

[prime parcel]

Wdym?

[rigid oriole]

@weary tiger What's your answer

[rigid oriole]

this?

My answer is

$$7^n-2\cdot6^n+5^n$$

[vital dew]

Shuri2060

[rigid oriole]

im not confident D:

[weary tiger]

7^n - 2*6^n + 5^n i think it was

[rigid oriole]

oh it is?

[weary tiger]

yep

you got it ❤️

[rigid oriole]

😅

[weary tiger]

i'm proud of you, shuri ❤️

https://cdn.discordapp.com/emojis/858797040804298782.webp?size=48&quality=lossless

sorry if i made you spend a long time on it

[rigid oriole]

no

i like problems

this was the only one i could do today

[weary tiger]

do you wanna try a different problem?

[rigid oriole]

i tried a bunch i couldnt lol

sure

I've been getting better at counting recently 👀

[weary tiger]

Emerald walks through the entire integer coordinate points of the plane. If, at a given moment, she is at point (a, b), with one step she can go to one of the following points: (a+1, b), (a-1, b), (a, b+1) or (a, b-1). In how many ways can Emerald get out of (0, 0) and walk 2008 steps and ending in (0, 0)?

btw idk the answer so you have to hope you get it right

[rigid oriole]

👀

Emerald has been walking for 14 years and can't find it

[fossil laurel]

just to confirm, this is the place to ask about fast-growing-hierarchy questions, correct?

because i have no idea where to go for that type of question

[craggy juniper]

isn’t fgh something to do with set theory

i vaguely remember what it is

only thing i remember is big numbers

[fossil laurel]

all i know it for is that it make big number very fast

no clue what set theory is, i assume i learn it next quarter (if not then, then never cause that's my last math class)

[fossil laurel]

I'd ask my question directly but I need to convert my program into mathematics

[craggy juniper]

@fossil laurel you can ask in #math-discussion where the question should go

[fossil laurel]

kk

[craggy juniper]

since you’ll get a response quicker there

[fossil laurel]

makes sense

[rigid oriole]

I reckon its ||(2008c1004)^2||

[weary tiger]

i hope you're right. i'll tell you in dms sometime if you are x)

[stray wasp]

How do we find combinations with multisets such as in the example where we have 1 apple, 2 bananas, 4 grapes, and 8 cherries and we want to choose 4 fruits from them - how many ways are there to choose fruits?

like I'm pretty sure this is stars and bars with restriction but is there a somewhat closed form/not casework method to solve these type of problems?

[minor peak]

i found i 5

[rigid oriole]

forall a:
a = a
=> a < a or a = a
=> a leq a

?

its that simple isnt it?

utilise definition

forall a, b, c:
a leq b and b leq c
=> (a < b or a = b) and (b < c or b = c)
=> ((a < b or a = b) and b < c) or ((a < b or a = b) and b = c)
=> ((a < b and b < c) or (a = b and b < c)) or ((a < b and b = c) or (a = b and b = c))
=> (a < c or a < c) or (a < c or a = c)
=> a < c or a = c
=> a leq c

---

if i didnt expand wrong

[rigid oriole]

what definition

You gave me this to use
x <= y <=> x < y or x = y

the 4 written aren't properties but axioms

in wikipedia

The 2 defns likely turn out to be equivalent

no, the 2 in stack

the answer shows they are

????

The question in stack literally asks if both are the same

and the answer shows they are equivalent

what?

Check the answer

It proves equivalence

both definitions imply the axioms of the other

forall a, b:
a leq b and b leq a
=> a leq a (by 2)
=> a < a or a = a
=> a = a

[rigid oriole]

maybe inclusion exclusion

count for 4 4 4 4 fruits, then subtract

xor

^ write out xor by its defn with not, and, or if necessary

The relations are not the same.

However, if < (rubin) is an order, then <= (wiki) is an order

and vice versa

Think carefully

< is an order iff leq is an order

NOT a < b iff a leq b

[rigid oriole]

???

the set difference would be all the pairs (x, x)

Convention?

It doesnt really matter which you take

because they turn out to be equivalent

isnt rudin === strict

strict

never has (x, x)

non-strict

always has (x, x)

Whichever definitions u take

what

to be put things clear

can u write down the 2 diff defns here

screenshot

i dont do names zzz

bruhhhh

screenshot pls

ok.

So we are defining <

I claim that these 2 are the same relation

What do u doubt?

sorry im back

ok so

the first definition

I will call A and B

for the bullet points ok

and compare with 1 2 3

Claim: A equiv 3

A says

x = y or x < y or y < x

3 says

x neq y implies x < y or y < x

yes?

but if you use the logical definition of implies

'p implies q' is 'not p or q'

Hence these 2 are equivalent

oops

Let me think for a sec

i missed something

A equiv (1 and 3)

I think I need to use a < a false

can u see?

[rigid oriole]

The cases when more than 1 is true. Is made impossible by (1)

My brain is being bad

you have to use rule 2 as well

10 < 2 and 2 < 10 implies 10 < 10

Sorry lol.

Let me think carefully

suppose a < b and a = b

then what is issue?

ok then u have a < a

sorry yes that is it lolol

This is better definition imo

exclusive or 🤮

just how i prefer at least

yes

and then

dont write that

proper notation is := for define

x leq y := x<y or x=y

Then for the other way round we have

x<y := x leq y and (not x=y)

equal probably

my terminology isnt great

R1 = R2

if u write them as set of ordered pairs

wait no

you are talking about the definition of order

i was talking about that

the 2 definitions of order are equivalent

it doesnt matter which u use to define it

S is ordered (<) <=> S is ordered (leq)

[wide vine]

I understand that the elements that would be in would be in the A1 ⊕ A2 ⊕ … ⊕ An. would at least be some element x that was only in 1 of the An sets

but im not sure what would be the case if an element was found in all sets A1 until An

[pale epoch]

how is $\oplus$ defined

[vital dew]

Lochverstärker

[wide vine]

like says say A1 = {1} , A2 = {1}, A3={1}. Then A1 ⊕ A2 ⊕ A3 = {1}

right?

but I dont know about some An case

and also

[obtuse lance]

I would think about the parity of how many times an element appears

[wide vine]

parity? Is that like how many times an element would have been repeated among An?

[obtuse lance]

yeah, by parity I just mean even or odd

[wide vine]

An element of the set must show up an odd amount of times between the A sets?

for it to be in the final A1 ⊕ A2 ⊕ … ⊕ An set

[coral parcel]

Right.

[wide vine]

Thanks!

[obtuse lance]

you're welcome 👍

[coral parcel]

1/2 and 2/4 are two ways to write the same rational number.

So the ordered pair (1/2, 2/4) is the same pair as (1/2, 1/2), which cannot appear in an irreflexive relation.

[obtuse lance]

I think you misread what they said

1/2 = 2/4 @barren granite

[weary tiger]

The set of rationals doesnt contain any fractions. The fractions 1/2 and 2/4 refer to a specific rational number, which is the same for both

[coral parcel]

I don't think it's standard to distinguish that strictly between "rational number" and "fraction". It's good and necessary to be aware that there is a difference between notation and underlying concept, but it doesn't feel helpful to assert that "fraction" can only mean a piece of notation. That simply doesn't seem to be true, as a claim about how actual mathematicians use the word when speaking to other mathematicians.

[outer kiln]

I think it works, but i think the red box, has been counted twice this way... I think this is not allowed right? What can we do to fix it?

As suggested by @olive condor (C - B) union (A intersect B) might work as well but it counts the red box twice. Not sure how we can fix that...

[turbid swallow]

https://math.stackexchange.com/a/522574/455531

In this line, "Then it has odd number of edges, so some pair of two neighboring ones has to be in either M1 or in M2" what does "some pair of two neighboring ones" mean?

[coral parcel]

One edge plus another edge that shares an endpoint with the first?

[turbid swallow]

Meaning two edges at the same point?

[coral parcel]

Two edges that share one endpoint.

[turbid swallow]

Okay, nice.

[tranquil vector]

Can someone let me know if my solution makes sense

I said R(s,2) = s for any s=>2 because you only need to look at the highest number, which will always be s as s is always at least 2

[coral parcel]

How does that explanation even relate to the definition of R(s,t)?

[stray reef]

no @tranquil vector your solution does not make sense in the slightest

as troposphere said, you make no reference to the definition of R(s,t), therefore you cannot claim to have proven anything about R(s,t)

[tranquil vector]

How would one go about explaining it then I’m like completely lost in this class

[coral parcel]

It sounds like you think R(s,t)=max(s,t)? That is definitely not true in general; for example R(3,4)=9 and R(4,4)=18.

[tranquil vector]

how do you know R(4,4) is 18

That’s where I’m lost

[coral parcel]

I looked it up at https://mathworld.wolfram.com/RamseyNumber.html

[stray reef]

you see where it says "Let R(s,t) be ..."?

that's the definition of R(s,t)

you may have seen the problem "Find the minimum number of guests at a party such that there either exist three people who all know each other or three people who are strangers to each other"

[coral parcel]

There's no good known way to compute this function in general, except in the simple case that one of the inputs is 2 (or 1).

[stray reef]

to which the answer is R(3,3) = 6

[tranquil vector]

But I don’t understand how R(s,2)=s

[coral parcel]

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find R(5,5). We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded R(6,6), however, we would have no choice but to launch a preemptive attack.

• Erdős

[tranquil vector]

If R(3,3) = 6

[stray reef]

R(3,3) = 6 has no direct bearing on the values of R(s,2).

to understand why R(s,2) = s, think about the definition of R(s,2).

[tranquil vector]

Is it something related to a whole graph being coloured red

[stray reef]

can you prove that for any coloring of the edges of K_s into two colors, there is either a red clique of size s, or a blue clique of size 2?

"what even is a clique of size 2?" might be a good question to think about.

[tranquil vector]

is a clique of size 2 just 2 connected points

[stray reef]

what do we call a thing that connects two points?

[tranquil vector]

A vertece?

or an edge I’m not sure lol

[stray reef]

you don't know the difference between a vertex and an edge?

[tranquil vector]

i know one is the connection the other is the point

[stray reef]

that sounds like not knowing your head from your ass, to put it bluntly

[tranquil vector]

😭

honestly I just want to get this course over with

[stray reef]

it should not be a matter of contention to you that the word vertex refers to points

and the word edge refers to connections between those points

say, how come you have the Russian flag as your pfp?

[tranquil vector]

unrelated it’s just an inside joke with my friends

[stray reef]

ah, and here i thought we could switch to Russian to make things easier.

[tranquil vector]

I’m taking this course in english so yes I should know what an edge is

[stray reef]

but ok

yes, a clique of size 2 is just a single edge

[tranquil vector]

When you word it like that it makes a lot more sense thank you

i just have trouble understanding the way they write the questions

[stray reef]

i didn't word it in any way not already written in the question

though of course, proving what i told you to prove actually only gives you $R(s,2) \leq s$.

[vital dew]

Ann

[stray reef]

there's another part to it: to show that no smaller graph will work.

for this it's enough to come up with a way to color K_(s-1) in a way that avoids both kinds of cliques

i.e. no red cliques of size s and no blue cliques of size 2

should be very obvious how to do that

[tranquil vector]

yeah I think that’s the second part of the question

I just didn’t understand what was being asked of me at first

thanks for the help

[olive condor]

Erm… (C - B) covers the yellow and pink areas. (A intersect B) covers the red and green areas. Together, they cover the required four areas. Why do you say that the red box has been counted twice? Moreover, in set, everything is “counted” once, i.e. {1,2,3,4,4,1,2,0} = {0,1,2,3,4}.

[median mica]

if A = {1, 2, 3}, and B = {∅}, then what would be A x B ?

would it be {(1, ∅), (2, ∅), (3, ∅)} ?

[haughty garden]

yeah that looks right

[median mica]

nice

[agile kernel]

I'm rather at a loss here for how to begin this proof

I'm assuming I need to use the deductive method to create a conjunction on the left side, but I'm not grasping how

[coral parcel]

Do you have an inference rule that allows you to conclude a -> ?

[agile kernel]

I know modus ponens/tollens and the disjunctive equivalency of implication

[coral parcel]

Hmm, that makes it more complex. I hoped you had implication introduction ...

[agile kernel]

Oh yes! Sorry, she never defined it as such but looking at the definition that's the basic idea

We can assume the hypotheses to be true

[bold bone]

How do i do 3n^2 + 4 ≡ 1 mod(2).

i subract 4 from both sides but then get stuck

[coral parcel]

Alternatively, unfold all the implications except the outermost one using disjunctive equivalence, and use De Morgan's law on not(P and Q).

[agile kernel]

That was the path I was taking initially. It seemed messy but perhaps that's the expectation

[coral parcel]

The way using implication introduction goes: Assume P and Q implies R. Assume P. Assume Q. Since you know P and you know Q, you now know P and Q. Modus ponens. Then discharge all of the assumptions.

[agile kernel]

Oh that's a clever shortcut

[coral parcel]

Note that 3 == 1 (mod 2) and 4 == 0 (mod 2), so what you really need to solve is just n^2 == 1 (mod 2).

[bold bone]

oh u can do that, just take the innate properties of individual elements and redefine them

good to kow

know

[obtuse lance]

also might even simplify with $n^p=n \mod p$ in this case as well

[vital dew]

Merosity

[foggy canyon]

What does this mean?
"It is an immediate consequence of the axiom of extension that the axiom of specification determines the set B uniquely."
'determines uniquely' is the part throwing me off.

Like, to me, that sentence means "because sets with the same elements are equal, a set built from a condition on another set can only be determined one way."

[stray reef]

to say it very generally, "<object> is uniquely determined by <data>" means that there is only one object in existence which matches the data

[foggy canyon]

Then why not write it like "It is an immediate consequence of the axiom of extension that the axiom of specification determines a unique set B."

[stray reef]

that's synonymous to what was written

[foggy canyon]

Ok, thanks for clearing that up.

[wraith harbor]

Would someone tell me what the , refers to in the equation?

[foggy canyon]

[#,#]?

Like a vector/matrix

[wraith harbor]

what am I supposed to do with it though

lets say I worked out the first half and second half

[foggy canyon]

Need some context

[wraith harbor]

to find a confidence level

for a simulation

[foggy canyon]

That's the confidence interval

[wraith harbor]

yeah

[foggy canyon]

Oh, so you need the percentage of points that lie within that interval

[wraith harbor]

hmm makes sense

ty dude

[foggy canyon]

Wait, that's wrong

Goggle is failing me, and I missed the word misconception

Found it
Take half of the size of the confidence interval, multiply it by the square root of the sample size and then divide by the sample standard deviation

@wraith harbor

https://sciencing.com/calculate-confidence-levels-2844.html
I don't know. At this point I would use a text book for how to get the confidence level. Google seems to think I only want the interval.

[wraith harbor]

ty i will look at it

[foggy canyon]

Kind of looks like you need to get the interval from the level
http://amsi.org.au/ESA_Senior_Years/SeniorTopic4/4h/4h_2content_11.html

[wraith harbor]

the picture I linked

is the interval level

supposed to give it*

[foggy canyon]

Probably have to work backwards
Found a decent source
https://www.mathsisfun.com/data/confidence-interval-calculator.html

[outer kiln]

anyone can help with this please

[foggy canyon]

What are you trying to get?

[foggy canyon]

Yea, so plug your numbers into the confidence interval equation and solve for Z, then use the table in the link to get the confidence level

[foggy canyon]

Counting the red box twice doesn't matter. Sets can't contain the same value more than once. Like {a, b} union {a, c} is {a, b, c}, because {a, a, b, c} is just another way to write {a, b, c}. A crisp set either contains a value or it doesn't.

Also, it doesn't count the red box twice

[outer kiln]

Hey thank you for the relpy so i guess its just (C-B) union (A intersect B)

[dense scroll]

Would a set B = {R, Z} (meaning real and integer) be an infinite set or a finite set because the set B has a finite number of elements?

[coral parcel]

It's a finite set because it has two elements.

[dense scroll]

Thank you!

[gilded marsh]

Having a hard time understanding how I am meant to rewrite this.

[olive condor]

Simply rephrase the given sentence “For every function f(x), if f(x) is quadratic, …” to answer the question? E.g. (a) All quadratic functions have at most two roots.

[iron bramble]

Can someone solve this puzzle. I am doing this from past 2 days. Anyone knows the answer?
U can only move top cube it means u are not allowed to move two cubes simultaneously or cubes below the top cube. Just top one on the stack you can move. Also you have to find number of moves.

[obtuse lance]

,rotate

[olive condor]

What have you tried?

You can solve by drawing the trees out

Maybe the answer is the number of leaves in a full/perfect(?) binary tree. So f(x) = 2^(x+1) - 1.

[floral abyss]

Bit of a simple question but I’m struggling to wrap my head around this.
Q: Determine wether it is an equivalence relation or not
S=R, xRy if x<y+1

So from what I understand for it to be an equivalence relation it needs to satisfy the 3 conditions ; Reflective, symmetric and transitivity

So for reflective
xRx so x<x+1 which is true so it’s reflective?

[stray reef]

reflexive

but yes, your relation is reflexive.

[floral abyss]

And for symmetry
xRy so x<y+1 > y<x+1

Which isn’t true?

Or do we assume it’s true because of the original question?

[stray reef]

misuse of >

also no we do not assume anything

nothing in the question says "yes this relation is definitely symmetric"

and indeed it is not

[floral abyss]

What do u mean by this

As in I should’ve used an arrow?

[stray reef]

i tend to say exactly what i mean, no more and no less.

when i tell you that you're misusing a symbol, it means that you're misusing that symbol.

if you wanted to say "implies", the symbol for that is =>, not >.

[floral abyss]

Oh ok

And for transitivity
x<y+1 and y<z+1 => x<z+1

Which is true?

[stray reef]

you don't need to check transitivity.

you already know the relation is not symmetric, so it cannot be an equivalence relation.

[floral abyss]

Yes I understand that

But is what I done for transitivity correct?

[stray reef]

you just stated it outright

which can hardly be called a proof

[floral abyss]

Then how would you do it

[stray reef]

write out a proof lol

if you think the relation is transitive then prove it's transitive

[floral abyss]

I don’t understand how to

[stray reef]

explain why x < y+1 and y < z+1 implies x < z+1

[floral abyss]

How would u explain it tho? Its self explanatory 🤦‍♂️

[stray reef]

i don't think it is

explain to me why it's true, then we'll talk

[prisma breach]

Hey everyone !
could anyone help me figure out a graph theory problem?
I am required to find the amount of possible walks from a given point on a graph of length 9

that's the graph in question
the given point is (1,1) top left , i've written the degree of each vertex next to it
so that the edge vertices are of degree 5
the mid points are of degree 7
and the middle point, (2,2) is of degree 8

now my 1000th intuition was to define a recurrence relation, forming sequences of available walks from a 5th degree vertex (An), a 7th degree vertex (Bn) and an 8th degree vertex (Cn), n being the index of the walk
so if im at a 5th degree vertex im able to either walk to one of 4 available 7th degree vertex or an 8th degree vertex, which is true for any 5th degree vertex, yielding An=4*Bn-1 + Cn-1
for a 7th degree vertex I get Bn=2Bn-1+4An-1 +Cn-1
an the 8th degree vertex : Cn=4An-1+4Bn-1

but im not sure how to proceed from here
not only am I not sure if my strategy is correct
defining Cn-1 and plugging in the other relations gets me to a dead end which leads to 3rd/4th degree polynomials with 2 variables with no apparent solutions....

Is there anything im missing perhaps ... ?

[turbid swallow]

I still have confusion about one thing: "Then it has odd number of edges, so some pair of two neighboring ones has to be in either M1 or in M2"
Does this mean in every vertex of two degrees, one edge is from M1 and another is from M2? It seems like so but I don't understand how I can write this clearly.

[turbid swallow]

Referring to this

[turbid swallow]

I think I figured it out. Will post the whole proof in a while for feedback

[thin furnace]

I got “For every x, x is prime and is an integer between 0 and 1000 and there is a k such that for every x x=4k+1 → ..."
But I am not sure about how to translate the "→∃(a,b)" part into plain language

[stray reef]

for every x SUCH THAT x is a prime between 0 and 1000 and is of the form 4k+1, there exist a and b such that x = a^2 + b^2

[thin furnace]

Oh thank you!

Oh yeah I think I get it, thanks!

[tight summit]

Does anyone have a pdf copy of Discrete Mathematics: An Introduction to Mathematical Reasoning, Brief Edition by Susanna S. Epp

[gilded marsh]

Search it up online and add pdf at the end

If you can’t find it I have it

[turbid swallow]

This is the question:

Lemma 1: A graph is bipartite if and only if it contains no odd cycles.
Proof: If G is bipartite with vertex sets V1 and V2, every step along a walk will take us either from V1 to V2, or V2 to V1. Therefore to end up where we started, we must take an even number of steps.

Conversely, suppose that every cycle of G is even. Let v0 be any vertex. Let’s call the Component containing v0 is C0. For each vertex in C0, let d(v) be the length of the shortest path from v0 to v. Every vertex in C0 whose distance from v0 is even, is colored red. Every vertex in C0 whose distance from v0 is odd is colored blue. This is done for each component in G. G doesn’t have any edge between two blue vertices because if there were an edge between two blue vertices, let’s call them b1 and b2, then going to b1 would require odd length, b2 would require even length, then back to v0 from b2 would require odd length and we would have an odd cycle which contradicts our initial assumption. The same happens for red vertices. Therefore, G is a bipartite graph with red vertices being one side and the blue vertices the other.

Theorem: The union of two matchings is bipartite.

Proof: A graph constructed by a matching has a maximum degree of 1, and a graph whose edges are formed by union of two matchings M1 and M2, has a maximum degree of 2. If there is a cycle of odd length, since each vertex has a maximum degree of two, one edge is from M1 and another is from M2. Marked in this way, there is one pair of edges in one vertex of the cycle which will be from either M1 or M2, but this contradicts that M1 and M2 are matchings. This means that there are no odd cycles in the graph G’.
Therefore from lemma 1, the union of two matchings is bipartite.

I have rewritten some lines from the Math Stackexchange questions, to be clear that I understand the reasoning. Can you kindly verify the proof and tell me if there are any flaws in my reasoning?

[fierce jungle]

Hey guys can someone tell me what these mean

the line above the set

[mint bane]

assuming A is a set, A-bar is everything outside of the set

formally known as the complement

https://math.stackexchange.com/questions/1854491/in-set-theory-what-does-it-mean-for-a-variable-to-have-a-bar-symbol-above-it

[fierce jungle]

oh ok thanks

[iron bramble]

Thanks

Any books that you would recommend on discrete maths and any other imp topics which would be useful.

Btw how did you draw that ?

[olive condor]

Erm, no recommendation from me. It all depends on your goal!

That is called a game tree, which is commonly introduced in an AI (programming) class. Or you can study more into game theory if you’re interested 😄

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

[wide vine]

Can someone help with this question

I have done this so far

nvm

I figured it out

I think I applied the laws correctly to show how the LHS = RHS

[wide vine]

when am I able to remove parenthesis with set operations?

like what operations can I think of Union and intersection as being similar to?

I have to distribute this correct?

Which means it doesn't behave like addition

[ember obsidian]

multiple unions/multiple intersections but not when mixed

$A\cup B\cup C$

[vital dew]

RokettoJanpu

[ember obsidian]

$A\cap B\cap C$

[vital dew]

RokettoJanpu

[wide vine]

okay

[ebon quest]

Am I allowed to ask questions in this channel?

[ember obsidian]

both operations associate, ie order of evaluation doesnt matter

thats why parens can be removed

in fact it lets us unambiguously define big unions/intersections

$\bigcup_iA_i$ and $\bigcap_iA_i$

[vital dew]

RokettoJanpu

[wide vine]

This would just be a series of Unions or intersectiosn, right?

where would I prove the distributive law on sets?

I am taking some discrete math course and it just was one of the rules.

[ember obsidian]

these are union/intersection of family of sets

wdym where

[wide vine]

like do you normally show that in discrete?

I never seen anything about it

maybe I missed it

[ember obsidian]

its reasonable to be asked to prove it in discrete

bc it often includes intro to proofs

[wide vine]

I guess I will have to look it up

or maybe follow defintions and arrive at it

[ember obsidian]

its not terrible, just recall defs of union/intersection & work cases

[wide vine]

okay

[ebon quest]

Can one of guys help with me with this question?

[coral parcel]

Whenever anyone on one of those islands (where knights and knaves are the only population groups) says "X if and only if I am a knave", you know X is false. So we'll need to wonder whether it's deliberate that B said "only if" instead of "if and only if".

However, your answers cannot all be true. If it is true that B is a knight and A knows where the gold is hidden, then B said "something-true only if something-false", which would make him a knave.

We might also need to decide whether a knave is able to say "something-true but something-false" or "something-false but something-true".

[ember obsidian]

man they multiposted

theyre in #help-5

@ebon quest for future reference pls dont multipost

[coral parcel]

Bah.

[ebon quest]

Sorry about that

[wide vine]

How do I know what my Universal set would be if I am given a set that is written in roster notation?

for example if we have the set S = {1,2,3,4,5}

how would I know what my universal set is

My book defines it as

So I guess if I have any problems related to finding universal set or using it then I would be given the context?

[coral parcel]

Yeah, despite what it can look like in a first introduction to set algebra, it is quite rare for a "universal set" to have significance in practical mathematical use of sets -- except in some where specific applications where it is stated explicitly what it's taken to be.

The only operation you need a universal set for is complement, and for many "casual" instances of complements, one simply writes it as X\A where X is what we might otherwise call the universal set. Then it is unambiguous in the notation itself what to complement with respect to.

[wide vine]

what does the A mean in this context?

[coral parcel]

Some set.

[wide vine]

so X\A means what?

[coral parcel]

I meant, instead of $A^\complement$ or $\overline A$ it is more common to write $X\setminus A$ to make it explicit what it is one speaks of complementing A with respect to.

[vital dew]

Troposphere

[wide vine]

oh so you must also know what X is right?

and you are just saying X\A meaning A has a universal set defined by the set X?

[coral parcel]

There's no such thing as "has a universal set".

[wide vine]

A is contained in a "universal set" defined as X

[ember obsidian]

$X\sm A=\brc{x\in X:x\notin A}$

[vital dew]

RokettoJanpu

[cosmic quiver]

How can I show that:
[
T(n) = T\left(\frac{n}{2}\right)+T\left(\frac{n+1}{2}\right)
]
where (n\in\mathbb{N}) is monotone?

[vital dew]

Victor H

[sly sonnet]

Hello. I need help. My task is to find out how many combinations there are to arrange beads in the same way as in the image

12 beads ( 6 white , 4 black , 2 blue )

[sly sonnet]

Pls

<@&286206848099549185>

[wide vine]

Not that I can help much but the actually bead doesn't matter if the say 2 white beads next to each other swap

right?

so if I swap those 2 beads it is still the same thing?

[sly sonnet]

Yes

So i have to find out how many combinations are possible

With the same colour pattern being there

[wide vine]

I feel like somewhere you divide by 12 or something

At least if I am thinking about it like permutations which I guess it is not

Because the one you wrote on your paper could be shifted 11 times?

But would technically still be the same thing

[dry raven]

I am in a algorithms class and have a few questions... would this be the best place to ask?

[wide vine]

probably

[dry raven]

So I was given a bunch of summation formulas and told to memorize them and to figure out what theyre used for in each case. I am very confused as I don't know when to use each one. Ill send the picture so yall can get a better idea of what I mean.

[wide vine]

Maybe seeing you are in an algorithms class I assume programming right?

Might these could be used to reduce having to compute multiple for loops and or simpler and faster methods to evaluate some quantity

Maybe you are also given more complex summation and you can break it up and reduce it using these rules/formulas

[gilded marsh]

I’ve been going at this for a while and I’m not certain on what to write for the last two.

[wide vine]

Am I crazy or is this asking the same question 3 ways.

[gilded marsh]

it seems like it

[wide vine]

Might be better with context of your class but seems that way.

[gilded marsh]

like the subject?

[wide vine]

Yes

[gilded marsh]

Variables

[silent hinge]

assuming that p = the user violated the terms of service; q = the user is banned.

the user violated the terms of service but is not banned ==

P -> ~q

is this correct ?

[haughty garden]

p -> ~q would still be true if p is false (i.e. the user did not violate the terms of service)

So it seems like it captures the statement: if the person violated the terms of service, then the user is not banned

If you want to say "the user violated the terms of service but is not banned", then you require two things to be true: the user violated the terms of service, the user is not banned

[dry raven]

@wide vinesorry for the late response but we have to apply these to problems tomorrow on a quiz. Im just confused on how to know when to use each one

[wide vine]

what exactly have you done up to this point?

[dry raven]

honestly mostly 2,3b and 3c

Im mostly lost on the geometric ones

[wide vine]

i mean what have you previously done in the class

might give me better context as to why these were just "given to you to study"

[dim hemlock]

would something always be considered a subset of itelf? e.g. A={1,2,3}, would A therefore be a subset of itself?

[final cliff]

Yes. Every set is a subset of itself follows from the definition of a subset.

[wide vine]

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

The more you know

[cosmic quiver]

How can I solve a recurrence relation such as:
[
T(n)=2T\left(\frac{n+1}{2}\right)
]

[vital dew]

Victor H

[cosmic quiver]

I can guess the solution, and prove it's right and it's unique lol

But idk how to arrive it nicely from just this with some kind of method

[placid thistle]

If i have a function f(n) and a function g(n) and if f(n) grows much faster than g(n), how can i write this out using Big-O?

[pale epoch]

i dont think there is a way to quantify "much" (unless you can more rigorously state what this means)

but knuth uses the notation $f\in \omega(g)$ for "f dominates g asymptotically"

[vital dew]

Lochverstärker

[pale epoch]

or f = \omega(g) using a bit abuse of notation

[obtuse lance]

sounds roughly like there exists some $x_0$ such that $x>x_0$ implies $|g(x)|\le |f(x)|$, this can be written as $g(x)=O(f(x))$

[vital dew]

Merosity

[placid thistle]

i gave up on this. i have no idea#

[silent hinge]

thanks man

[silent hinge]

hello again, quick question

~q -> ~p would this be true if p = T and q = T as well?

[weary tiger]

Yes

[silent hinge]

Heres my table

how can i get good at this i am honestly guessing

[weary tiger]

You just need to remember tables for implication,or and

[silent hinge]

i am assuming that if p = t and q = f, ~q -> ~p then its false

[coral parcel]

You're missing the table for ->.

[silent hinge]

oh thanks

ill take a look at the tables for implication and also fix my truth table