discrete-math

[coral parcel]

Now we can pick points within this interval that are closer to a than to b and closer to b than to a. But this violates the uniqueness of p_x.
Wait, how does that work? Certainly p_x is allowed to depend on x.

[maiden drift]

We have a segment between a,b which is is disjoint from K. We then take an open ball around C disjoint from K?

[obtuse lance]

yeah sorry, I mean to say there are two points on the boundary we can find, and so we pick a point that's equadistant between them

[maiden drift]

ok, so we take c to be the midpoint from the line seg a,b and take an open ball around c disjoint from K right?

[obtuse lance]

I've left out details in that a,b are not necessarily going to be these points either

in case it seems I'm saying that too - I'm not haha

[coral parcel]

But there might be a third point in K that is closest-in-K to the midpoint.

[obtuse lance]

yeah this is what I was just trying to preempt with my statment

[maiden drift]

The easy example i can think of is some U shape thing

[obtuse lance]

like pick a, b on the boundary of K, there's a c not in K between them (because we assume it's not convex), now we know there's an open ball around c that's not in K because it's closed, then we can now walk along this open interval contained in [a,b] until we get to some edge points [r,s] in [a,b]

we pick the point in the center of [r,s]

r,s lie on the boundary of K

[coral parcel]

Um is what you're arguing here just that we can find r,s in K such the open interval (r,s) is disjoint from K, or is there more to it?

[obtuse lance]

the reason the open set matters is because we're trying to avoid a singleton which doesn't violate the uniqueness

[maiden drift]

What if for example X is an annulus

[obtuse lance]

works as it should, we know it's not convex so pick two points on the boundary of the inner circle

draw a line between them

pick the midpoint

ah it's not minimal

I guess this doesn't work

[coral parcel]

Okay, concrete example. Let's say that K = { (x,y) | y <= (x-1)(x+1)/10 } and pick r=(-1,0) and s=(1,0). Then what?

[maiden drift]

Im starting to doubt the idea of trying to go for a contradiction. Maybe there is something more direct. The siutation is this.

1. K closed in R^2.
2. I have the following unique projection, p_K onto K. For any point x in R^2, p_K(x) is the unique pt in K such that |x-p_K(x)|< |x-k| for all other pts in K.

WTS: K convex.

[coral parcel]

The points that fail the has-a-unique-closest-point condition start a bit up on the y-axis (and are only found on the y-axis), but it's not obvious how to see that they must exist, starting with this r and s.

[maiden drift]

What happens if I restict K even more and make it compact, is there any results in compact sets that seem fruitful?

[obtuse lance]

what if we slice it with a line, imagine the points not in K to project along that line onto its boundaries, do we only end up with intervals?

I'd think if yes, that means its convex

[coral parcel]

Can we force the projections to be along the line? I don't think so.

[obtuse lance]

yeah, probably not, I'm thinking maybe if the line pierced the centroid when it's convex maybe

[coral parcel]

The basic trouble as I see it is that if we have a figure that is very slightly concave along one side, the only points that fail to have a unique projection can all be very far from the shape, and certainly not on any of the line segments that violate convexity.

[maiden drift]

So if we take the line segment with boundary end points that violates convexity, and take the midpoint, and a orthgonal line through the midpt, every point on that orthagonal line is equidistant to a,b.

if we go far out enough along this orthogonal line, is there an idea there?

[coral parcel]

That's the case for the most obvious toy examples, yes. But if we wiggle the line segment just a little bit so its slope changes minutely, I think its midpoint-normal can completely miss the narrow curve of counterexample points.

Hmm, or perhaps not. I have trouble constructing any concrete example that misses.

[maiden drift]

examples of non convex sets just get too messy. I wish I could rephrase the question into something more analytic

[severe swan]

How do I calculate the number of elements in a set? If I have the set { {5, 9}, {1, 2, 3}, {3, 4, 5, 6, ...}, 1, null (zero with slash through it) } for example? Would there be 5 elements because there are 3 pairs of curly braces and 2 numbers without any curly braces, or would it be 6 because they are all included in the first large curly brace? Or would I count how many numbers there are in total?

[heavy tinsel]

5

[severe swan]

That is what I thought, thanks @heavy tinsel

[heavy tinsel]

count the elements to the left and right of the commas of the big curly brackets

[distant bobcat]

@coral parcel Yes, its assumed the graph is embedded in the plane

[hard yew]

Let us be given a relation $R$ on the set $\mathbb{R}$ s.t. $$R={(a, b): a\neq b}$$If I want to find the composition $$R \circ R$$ can I go by the definition of a composition of a relation, which gives me: $$\(a, b) \in R \land (b, c) \in R \Leftrightarrow a\neq b \land b\neq c$$, which basically allows a formation of a relation between any two real numbers, so $$(1, 1) \in R \circ R$$ and $$(1, 2) \in R \circ R$$ and $$(2, 1) \in R \circ R$$ or $\R\circ R ={(a,b): (a=b) \lor (a<b) \lor (b>a)}= \ ={(a, b): \forall a, b \in \mathbb{R}}=\mathbb{R}^2\$ Which means that $$R\circ R = \mathbb{R}^2$$ Is this valid or did I completely misinterpret the way to find the composition?

[vital dew]

Alter

[wide vine]

Do you think this has the same intended meaning as it was written in english. (Domain is the set of all real numbers)

The reciprocal of every number between 0 and 1 is greater than 1

$\forall{x}[(0<x<1) \longrightarrow (\frac{1}{x} > 1)]$

[vital dew]

Brandon7716

[hard citrus]

Yes

[wide vine]

okay thx

[heavy tinsel]

Shouldnt the number of solutions just be the number of elements in that congruent class?

Seems like there is no solution for the first one, and I think x = 6 and 14 are solutions to the second one by trial and error

But im not seeing a connection

[outer portal]

You're correct that there's no solutions to the first one, which you can prove since gcd(6, 16) does not divide 3. However, there are infinite solutions to the second one

Try converting the second one into an algebraic equation by introducing another variable k

[heavy tinsel]

16|6x-4 => 6x-4=16k

[outer portal]

Good, so now try factoring out a 2 from both sides, removing it, and converting back into a congruence equation

[heavy tinsel]

3x-2=8k =>3x congruent 2 (mod8)

[outer portal]

Good, and do you know solve this?

[heavy tinsel]

So, since gcd(3,8) = 1, there is a multiplicative inverse for 3 mod 8. I can do it this way?

[outer portal]

Yep I think that works

You could also keep adding 8 on the right side of the congruence until you get a number divisible by 3:
3x congruent 2 (mod 8)
3x congruent 10 (mod 8)
3x congruent 18 (mod 8)
and then since gcd(3, 8) = 1 you can divide by 3 to get
x congruent 6 (mod 8)

[heavy tinsel]

could you actually expand a bit on why the first one doesnt have solutions?

ok I think this is a better way

[obtuse lance]

I'd just brute force multiply, there are only 3 numbers to check

[outer portal]

part 1 of this theorem

[obtuse lance]

inverse can only be 3, 5, or 7

[heavy tinsel]

alright, Ill try to connect this to whats in my textbook

thanks

[heavy tinsel]

Im not entirely sure why,

[obtuse lance]

try to explain part of why and I'll fill in the gaps

[heavy tinsel]

So, it cant be 0, 1, 2 because those times 3 < 8

ok, i see its inverse is 3 now

[obtuse lance]

well can't be even because it has to be relatively prime to 8

that just leaves us with 1,3,5,7

but 1 is the identity, so doesn't make sense to check

fun fact, it turns out every invertible element is its own inverse mod 8

[heavy tinsel]

this is from the gcd condition right

[obtuse lance]

yeah

[heavy tinsel]

that makes sense

pretty cool to know

[obtuse lance]

so what do you get for your final answer for the second question you originally asked, there's a sorta "gotcha" aspect about it

[heavy tinsel]

thats what im trying to figure out lol

[obtuse lance]

oh ok cool, I thought you went back to part 1 cause you were done with it, didn't mean to rush you lol

[heavy tinsel]

Im actually not sure what the point of this question is

like the "gotcha" moment

[obtuse lance]

well what's your final answer

I'll tell you if you've been "gotten" or not lol 😛

[heavy tinsel]

Im stairing at this, still not sure lol

[obtuse lance]

well what do you have so far

[heavy tinsel]

that the first one doesnt have solution, the second one has solutions x =6, 14

[obtuse lance]

yeah that's it

[heavy tinsel]

oh ok lol

i just need a break then 🤣

[zenith valley]

Dunno which category this belongs to, so yeah.

[vital dew]

Jonathan Phan

[next sail]

Hello everyone! ☺️👋🏼 My name is Helen. It’s a pleasure to meet you all. I’m cohosting a hyrbid hackathon this spring & would like to invite you all to register for this special event. Such event will take place the last weekend of March (3/26 - 3/27).

For more information, please visit our website at http://www.beelikecoders.com (not mobile friendly) 🐝. If you’re interested in signing up please fill out this google registration form https://forms.gle/9Jy4D9oNxBzvz7KRA. 🙏🏼 And if you have any questions, regarding the event, feel free to message me privately! (:

This hackathon is also beginner friendly! 🙌🏼

[pallid lintel]

What's a good resource for learning about combinatorial order types?

im interested in line arrangements in R^2

[sleek loom]

try to draw ven diagramms

adding the sizes of 2 sets does not give the size of their union, unless they do not intersect

you have to substract from your result the size of $A \cap B$ because you counted it twice when adding their sizes

[vital dew]

Orian

[zenith valley]

Anyone?

[meager prairie]

identity weirdness?

does a have to be e?

id ask in abstract channel

theyre smarter

[weary tiger]

what textbook is this from?

[tall oxide]

¬p^(p->q)

can I conclude that ¬q ?

[hard yew]

No. p is false so p->q is true regardless of what q is.

[tall oxide]

thanks

[spare forge]

Hi, I have to explain a proof to another person but I not sure how to do that. Would someone give any tips (perhaps I can even link the proof and we can walk through a way of explaining it)?

The actual theorem (Hall's Theorem, a matching problem) is unchallenging but I am having trouble not plagiarizing the proof without just invoking the proof by example.

[coral parcel]

Do you have an actual person you're attempting to help, or are you trying to respond to a homework exercise saying "explain this proof to a (hypothetical) other person"?

In the first case, you shouldn't need to worry about "plagiarizing".

[spare forge]

It's for a directed reading group

The person I'm trying to explain to will be my superior too 💀

[coral parcel]

Presumably said superior already knows the proof, right?

[spare forge]

Yes

[coral parcel]

So either your real audience is the other group members, or your real task is to convince the superior that you know the proof.

[spare forge]

There were three proofs to Hall's Theorem. Each of us will explain one proof to our superior. So it might be both 😬

[coral parcel]

It still doesn't sound like plagiarism is a real risk. If your presentation is live, you should in any case be comfortable enough with the proof to respond to clarifying questions from the audience, so simply reading verbatim from your source material is not an option anyway.

Also, "explain the proof" would probably also need to identify the key ideas in the proof and point them out during the presentation, perhaps more explicitly than the source material does.

[spare forge]

I see, maybe I will try once and share an attempt at explaining it here?

[coral parcel]

Referring to a concrete example along the way is not a bad idea, by the way, as long as you keep connecting it to general reasoning.

[spare forge]

I have a really basic question. In this picture,

does the augmenting path show those paths that are not selected in the first paths selected in the alternating paths?

And since this is bipartite, should I be looking at paths starting from the part with smaller order? Yes.

Is it correct to say that if the M-augmenting path pictured above was instead labelled the M-alternating path, then the M-alternating path pictured above will be its augmenting path? Yes.

[coral parcel]

I'm not familiar enough with proofs of the marriage theorem to answer that.

[spare forge]

Oh, this is not related to the proof but just with the language in it.

I'm trying to discern the difference between alternating and augmenting path.

[heavy tinsel]

How do I prove this? I think I got it

Phi is Euler's totient function

[old mantle]

Is the term "strategy vector" common in game theory?

It seems to be an older term

I am writing something that involves a bit of game theory and I am not sure if I should introduce it or avoid it

[heavy tinsel]

How do I compute $6^{6777} \mod 667$ got it

[vital dew]

Kurama

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

[weary tiger]

Any hint how do I prove this with induction?

[uneven swift]

Hey, I pretty new here. I am trying to understand an algo and I came across this if condition and not able make sense out of it. Can someone please help me?

if ([c− : c+] ∩ [c1, c2]) != 0

if the color at point P in Grid is c, we allow that the actual color is in the range [c− : c+], where c ∈ [c− : c+]

For example,
c- = c - 0.5
c+ = c + 0.5

c1 and c2 are color at point p1 and p2 on grid

[outer portal]

Show the base case where n=2 using DeMorgan's law and try to get the inductive step from there

[outer portal]

It's saying that if c is some number representing a color, then the condition is true if the interval [c-, c+] overlaps at all with the interval [c1, c2], where [c-, c+] appears to just be some interval that contains c

At least that's what I think, but it's worded very weirdly

[weary tiger]

ok thank you!

[uneven swift]

Thanks. So it is just saying that if c1 and c2 lies in c-:c+ range?

[outer portal]

I think if either of c1 or c2 lies in the c-:c+ range it would be true

Because that would make the intersection nonempty

Sorry, I had assumed [c1, c2] was an interval but I think you're right that they're kind of using it as {c1, c2}

[uneven swift]

Thanks, @outer portal

[spring surge]

Is inverse function of cartesian product possible?

[stray reef]

what do you mean

[spring surge]

{1,2} x { a b } = { (1 a), (1,b), (2,a), (2,b) }

suppose i want to get the set {1,2} from the set in the right

cartesian product is like a multiplication, I wonder how does division looks like then

[stray reef]

there is no such thing as division of sets

the closest thing you can get is like... quotient by an equivalence relation

[copper ore]

I need help making a graph with only 1 odd cycle but that it could also have even cycles

I was thinking something like this

[copper ore]

this is the question

[spring surge]

How to check if your combinatorics solution is correct? Lecturer told that only way is to solve the problem the other way and check if the answers match. Is it the only way to be sure if I solved it well?

[pale epoch]

you have to be critical of your solution

and try to find holes

if you find two different ways to solve a problem and they match, thats good

personally i often had the problem that even wrong solutions can sound plausible, but you can find such mistakes with more experience

you can also do sanity checks on smaller examples or with the help of computers

[copper ore]

where can I find the proof for this ?

[pale epoch]

is this a cycle graph?

if yes, the proof is easy enough by doing the obvious thing

if you color a single vertex, it determines the colors of all of its neighbours

so in the even case you can alternate and in the odd case you run into a problem where at a point you need a third color

[copper ore]

yes cycle graph

ok thanks

[tidal tulip]

is it fair to say that a relation R on sets S and T is an set of tuples (s,t) in R subset S x T

[gritty crescent]

A relation from S to T is indeed a subset of S×T by definition

[tidal tulip]

is it correct to say R is a set of tuples the way i described above

book states or a bit differently and i want to make sure the way i’m thinking about the definition is correct

[weary tiger]

No, because not necessarily any (s,t) is in R

[tidal tulip]

that’s why i said “set of tuples (s,t) in R subset S x T”

so you’re saying that’s not correct?

is it fair to say that a relation R on sets S and T is an set of tuples (s,t) in R subset S x T

[weary tiger]

it is a subset of S x T

[tidal tulip]

why did you say it wasn’t correct?

[weary tiger]

I even explained why lol

[tidal tulip]

im confused - are you saying this isn’t correct

i’m interpreting your statement that this is false

[weary tiger]

I understood differentyl what you said

[tidal tulip]

ah i see no problem

so that is correct understanding yeah? because the book words it differently

and i interpreted it as what i wrote there

[elder berry]

Yeah, what you wrote is correct. To be even more precise, you could say that it is a set of tuples, possibly empty (just to include the empty set as well)

[tidal tulip]

oh yeah good point

ty for checking

[elder berry]

On the subject of relations, given alpha and beta, how did they show that this property is correct?

It is safe to assume the relations are symmetric and reflexive, but I am kind of skeptical of the above write-up

[tidal tulip]

testing for transitivity

let’s say you have a relation

(x,y) in W subset X x X

where

X:={A,C, P, T}

W:={(A,A), (A,C), (A,P), (C,C), (C,P), (P,C), (P,P), (T,C), (T,P)}

then is it valid to reuse the same tuple in W to check for trans or are you allowed to use the tuple only once?

eg

are these valid checks

(1)
(C,C) in W,
(C,C) in W,
therefore (C,C) in W

(2)
(C,C) in W
(C,P) in W
therefore (C,P) in W

?

[final cliff]

Do you consider it obvious that the implications "CWC and CWC implies CWC" and "CWC and CWP implies CWP" are true?

There's not just one correct test for transitivity. It might be inneficient to check those implications but it's not really wrong.

[tidal tulip]

ok so basically it’s correct to check for that but we can ignore it since it’s trivially true

[final cliff]

Yeah pretty much, doesn't hurt to check it if you feel you need to though.

[tidal tulip]

looks like W is transitive but not symmetric nor reflexive

[elder berry]

Anyone understands this write-up?

[livid minnow]

How would I go about proving that given 6 circles arranged on a plane such that no circle contains a common center point as another then they have no common intersection point

[stray reef]

what relations?

i'm seeing something being done with a binary operation that is assumed associative and commutative with both of these properties seeing extensive use

[elder berry]

Alpha and beta are relations on some set (not specified) and are equivalence relations (alpha and beta are transitive, symmetric and reflexive)

I guess it is safe to assume they are relations on AxA, for some set A

[stray reef]

and what is juxtaposing these relations supposed to mean?

[elder berry]

Just to make sure, you mean what does ab mean?

[stray reef]

yes

[elder berry]

it is a composition of relations, for example
if alpha = {(a, b)} and beta = {(b, c)}, we define the composition in a way so that
alpha ○ beta = {(a, c)} (connecting the end point of one relation, to the beginning of another

in reverse sorry, beta ○ alpha would be {(a, c)}

weird notation issues :(

Better definition

[stray reef]

okay, so it's a composition

composition of relations is associative

and what remains to be seen is that for equivalence relations it is commutative

[elder berry]

I can show that, both that ab is commutative and associative

ah wait

alright, got it then, I got confused since the solution never mentioned those properties

Thanks a bunch Ann!

[indigo tinsel]

Okay, so i know this is "there exist an x in D S.T for all y in d, if x != y, then x < y"

However, what can I imagine x and y to be?

Just elements inside of D?

[stray reef]

yes just as it says

[indigo tinsel]

Right. I'm a little confused as to why this says there is an element in D less than every other element. Like would I just assume that x = 0 in the set D = {0,1,2,3}, and y incremented to be 1, 2, 3? Sorry, I know that's probably a dumb question lol

[stray reef]

i mean...

what is D

yes, this statement says "there is an element in D that is smaller than everything else in D"

[echo raptor]

very quick question about sets: suppose you have a disjoint union $A_1 \cup A_2 \cup A_3 = A$ and another disjoint union $B_1 \cup A_2 \cup A_3 = A$; does it follow that $A_1 = B_1$, and how would you prove that?

[vital dew]

scorpio1147

[echo raptor]

like, would you go about showing $A_1 \subseteq B_1$ and the other way? i feel like it's almost by definition but i can't really figure out how to go about it

[vital dew]

scorpio1147

[heavy tinsel]

doesn't actually seem like a correct statement..

[echo raptor]

hm, how so?

and how about if you know that $A_1 \subseteq B_1$?

[vital dew]

scorpio1147

[heavy tinsel]

like A = {1,2,3,4,5,6}. You let A1 = {1,2} A2 = {3,4} A3 = {5,6}. They form partition of A. Now let B1 = {1,3} B2 = {2,4} B3 = {5,6}. It is a partition. But it certianlly doenst follow that A1=B1, etc

[echo raptor]

no, there is no B_2 and B_3

[heavy tinsel]

oh, my bad

[echo raptor]

it's A_1, A_2, A_3 and B_1, A_2, A_3

seems almost obvious but i can't figure out how to formally prove it

[heavy tinsel]

yeah, it does make sense. If they are not equal, then there is some x in A1 that is not in B1. But that is impossible since the union of A1 A2 A3 and B1 A2 A3 both form a partition of A.

So some sort of a contradiction ?

I think using the definition here, you can prove it

[tidal tulip]

i don’t understand what C_x means jn definition 5.11 or what statement 5.47 means, can someone explain it and sketch how to prove that statement

seems like C_x is a set of all the y’s in T related to x in S?

so if we had relation W:={(A,A), (A,C), (A,P), (C,C), (C,P), (P,C), (P,P), (T,C), (T,P)}

relation class of A is C_A = { A, C, P} ?

and is this saying if W were an equivalence relation (which it isn’t) then C_C, C_P both would equal C_A?

[weary tiger]

you can let x be an element of A_1, then it is an element of A

and use cases

use the fact they are disjoint unions to guide you

that's actually a nice question

[vivid bison]

Hi, I need to determine whether this statement is true or false:
There is a 3-regular graph G = (V, E) with exactly 2 sets Y ⊊ V , Y ̸= ∅ such that the cut induced by Y has exactly 1 edge in it; and with exactly 4 sets X ⊊ V , X ̸= ∅ such that the cut induced by X has exactly 2 edges in it.

However, I cant find a 3 regular graph that when we cut it, it has 1 edge. When we remove 1 vertex, it will have 3 edges, when we remove 2 vertex, it will have 4 or 6 edges...

[vivid bison]

nvm i figured it out

[feral osprey]

How do I calculate the numbers of ways to arrrange 20 students to 4 arrange groups of 5 students?

[stray reef]

as in, the number of ways to split 20 students into 4 groups of 5, with order within a group not mattering and the groups themselves being interchangeable?

[feral osprey]

pretty much

[stray reef]

20!/(5!5!5!5!4!)

[feral osprey]

how so? @stray reef

[stray reef]

20! ways to arrange the students in a row, with subsequent assignment of students 1-5 to group A, 6-10 to group B, etc.

divide out to account for rearrangements that don't affect the final grouping

[feral osprey]

(20ncr5)(15ncr5)(10ncr5)(5ncr5)

?

[stray reef]

if you insist... but also divide by 4! afterward

[feral osprey]

due to the groups being interchangeable?

[stray reef]

yes

[weary tiger]

i have to answer this question
"let E be a finite set of cardinal n ∈ N.
let A be subset of E of cardinal d. how many subsets B of E are there such that A ∪ B = E"
i find 2^d (all elements of E-A have to belong to B, but any (or none) of the elements of A can belong to B, so the number of subets of B isthe number of subsets of A which is 2^d ) but my friend find 2^n-d, who is right?

[weary tiger]

can someone teach me set

[keen drum]

set

[pale epoch]

consider reading #❓how-to-get-help to see what kind of help this server generally provides and how to get it

[feral osprey]

Thanks

[hard laurel]

Can anyone tell Me prerequisite for Studying Relations..?

[weary tiger]

intro logic/sets

[trim blaze]

is the difference between two countable sets still countable?

[gritty crescent]

Yes, you can prove why it must be so.

[inner beacon]

What does it mean if something is a divisor of another number?

i.e "both 1 and -1 are divisors of 1"

[ebon quest]

Can someone help with this question?

Not really sure how to start

[outer portal]

Have you noticed that if $(A \cup B) \subseteq A$ then $B \subseteq A$?

[vital dew]

mandelbruh

[outer portal]

If a and b are integers, a is a divisor of b if there exists an integer k such that ak=b

[ebon quest]

Yeah I did

I had this for the first part

Is that correct for p -> q?

But then idk how to prove q -> p

[outer portal]

You have the right idea but I would be more explicit that B being a subset of A follows from your assumption

For the second part notice that if $B \subseteq (A \cap B)$ then $B \subseteq A$ also

[vital dew]

mandelbruh

[outer portal]

Since every element of B is in the intersection of A and B then every element in B must also be in A

[iron hearth]

i have a quick question

so i already proved a abd b are false

but for c i dont how to solve it using set identities

i know its true but don't know how to prove it

[ebon quest]

How would I write that out in math terms

This is what I have now but I’m not done the second part

[outer portal]

Any set is a subset of itself, therefore $B \subseteq B$. Since $B \subseteq A$ we know that $A \cap B = B$. Therefore $B \subseteq (A \cap B)$

[vital dew]

mandelbruh

[ebon quest]

But aren’t we trying to prove (A u B) c A from B c (A intersection B)?

For q -> p

@outer portal sorry idk if I should @ you or not

[outer portal]

Oh lol you're right

whoops sorry

[ebon quest]

My tablet is gonna die soon so I wanna see if I can this last part

[outer portal]

Since $B \subseteq A$ then $A = A \cup B$. Any set is subset of itself therefore $A \subseteq A$ meaning $(A \cup B) \subseteq A$

[vital dew]

mandelbruh

[ebon quest]

So both of these look correct right?

Also, idk if you but can you see if these 2 questions are right too?

[outer portal]

Yeah maybe say something at the end of each like “since assuming p led to q then p—>q”

[ebon quest]

Ok, makes sense

[outer portal]

a. can’t be transitive because you have (a, b) and (b, c) but not (a, c)

[ebon quest]

Oh right, how about part b and c?

[outer portal]

b. looks right but I’m pretty sure c. is transitive

[ebon quest]

Just making sure, like this right?

[outer portal]

Pretty sure

[ebon quest]

Ok, and the other question looks good too?

[outer portal]

I’m a bit confused by the x operator

Is that Cartesian product?

Your second claim looks good and part ii. is good as well

[ebon quest]

I’m pretty sure it means Cartesian product

[outer portal]

Ok in that case first claim is good

[ebon quest]

Ok, how about the third one?

[outer portal]

If the Cartesian product is the empty set then A AND B are empty

So I think or would also be always true

[ebon quest]

Oh ok

So all my claims are good? No need to change anything?

[outer portal]

Seems good

[ebon quest]

Ok tysm for the help!

Perfect timing my iPad is at 1% ☠️

[severe swan]

I am wondering if someone can explain this to me.

I got this question wrong on my test and I don't know how to come to the correct answer.

What is the symmetric difference of sets {1, 3, 5} and {2, 3}?

I put that it is {1, 2, 5}

It says that the correct answer is {2, 5}

Can someone explain why the answer is {2, 5}

[iron hearth]

Can someone address this question plz

[olive wren]

A = (A U C) \ C U (A n C) = (B U C) \ C U (B n C) = B

[outer portal]

I think you're right since ${1, 3, 5} \Delta {2, 3 } \
= ({1, 3, 5} \setminus {2, 3 }) \cup ({2, 3} \setminus {1,3,5 }) \
= {1, 5} \cup {2} \
= {1, 2, 5}$

[wide vine]

I am looking at this and they use the word "increasing" but Idk why I think it should be "strictly increasing"

[vital dew]

mandelbruh

[severe swan]

Thanks

[wide vine]

Is this really what they use as far as this terms. "Increasing, Decreasing, non-increasing, non-decreasing"?

Not sure how the use here would be different than using the phrase "strictly increasing" as opposed to "increasing" and "strictly decreasing" as opposed to "decreasing"

[iron hearth]

is this using set identities?

[keen drum]

no it's used differently in different texts. So far, I've had increasing as <=, strictly increasing as <, nondecreasing as <=, but I think non-decreasing is better than just increasing

[wide vine]

how do you describe a sequence like this {-1,1,-1,1}

[keen drum]

nothing

bounded?

or oscillating

[wide vine]

well I thought non monotonic or something

[keen drum]

._.

sure

that works

[wide vine]

but

they never brought that up

so

so maybe

[keen drum]

yea it works

[wide vine]

neither non-decreasing nor non-increasing?

[keen drum]

yea

neither

[wide vine]

but I hate that so much

[keen drum]

ok stop killing my head with english

im sorry im sorry im sorry

i will stick to math symbol sorry sorry sorry

[wide vine]

the weird thing is they use "strictly increasing" to describe functions

which has the same meaning as what they used for sequences with "increasing"

[keen drum]

I mean sure

why wouldn't that work

[wide vine]

not that it doesn't work but like here...

[keen drum]

ask your instructor

[wide vine]

I am my instructor

[keen drum]

don't look into it too much it'll usually be really apparent if so

unless

[wide vine]

Just me and the book and hopefully a response for the prof if I do email her.

[ashen cloak]

I need help understanding why is this problem is true.
For all of x, there is y, x + y =0.

[outer portal]

Is there a particular set you are working with? For example, if x and y are integers, this is true, but it would not be if they were natural numbers

[ashen cloak]

My next question what are natural numbers?

[outer portal]

The set of natural numbers is {0, 1, 2, …}

The inclusion of 0 is debated though

[ashen cloak]

The book didnt really say but im assuming integers since my professor said true. He does a poor job explanning things

So how with integers is true?

[outer portal]

Look up additive inverses for the integers

[olive wren]

Idk what you mean by that
You can try proving every step of the equation, it shouldn’t be too hard

[tidal tulip]

i’ll give a concrete example and want to see how the definition i have a question on applies to this example

say
A={1,2,3,4,5}
R={(1,1), (1,3), (1,5), (2,2), (2,4), (3,1),(3,3),(3,5), (4,2), (4,4), (5,1), (5,3), (5,5)} = { (a,b) | a+b is even}

C1 = C3 = C5 = {1,3,5}
C2 = C4 = {2,4}

I = {1,2}

partition F = {C1, C2}

my question is would ~_F and U/~ be applied to this example as defined below in Note 5.62?

i don’t understand what the hook is saying ~_F nor U/~ is

[tidal tulip]

can anyone help me understand then notation

[weary tiger]

how is my proof?

oops, I made a mistake that should say g(y) <=> f(x)

oh wel I think I was on the right track

[stray reef]

no, you weren't

you talked about g^-1 without knowing that g^-1 even exists. which it may very well not.

and you concluded that f is a bijection, which it may very well not be.

would you like me to give an example of a pair (f,g) as given in the problem with f not a bijection,

or would you like me to give you pointers toward properly proving what is asked of you?

[weary tiger]

pointers please, I legitimately though I was on the right track

[tidal tulip]

is it saying U/~ is the relation each of the Cn’ are generated by so U/~ = F = the set of partitions of U defined by ~

?

i’m pretty confused by what it’s saying if someone could help me understand

i gave an explicit example and would like to see the notation applied to it to understand it concretely

[stray reef]

use the definition of an onto function. show that for every a in A there exists b in B such that f(b) = a

[tidal tulip]

can anyone help i don’t see “associated partition” as a term on google

to better understand this

i think it’s saying U/~ = F = { C1, C2 } and that F is generated by ~_F

where ~_F is an equivalence relation of a+b is even

how does that sound

[tidal tulip]

nvm i see it’s correct

[wide vine]

can someone tell me where this would be important

In working with summations, it is often useful to pull out or add in a final term to a summation:

[iron hearth]

can someone help me with this question

Let D be the set of BU dorms. Each dorm is a set of rooms. Each room is a set of students. For two students a, b, let F(a, b) be “a is friend of b.” Express the following
using quantifiers.

[wide vine]

so what sets do you have to work with? You set D = {dorm, dorm1, ....}, dorm = {room, room2...} , Room = {student1, student2, ... }?

[sturdy walrus]

I'm currently going through some practice problems, and I'm not really sure what " r' " and " rr' " means here. Could someone please help me out here?

[weary tiger]

This set contains every rational number such that there exists some other rational number where when we multiply it by our original number gives 1

basically think every rational number with a multiplicative inverse

[weary tiger]

^

[sturdy walrus]

Got it. Thanks!

[haughty garden]

If you’re trying to force a telescoping series, it might be useful to take out a few terms so that terms in the middle cancel out (or at least it’s easy to see that these terms cancel out)

[tall oxide]

if a conditional has "provided that" in the middle, is it p->q or q->p?

[outer portal]

q provided that p would mean p->q

[granite frigate]

j=1(j+2)?

[severe swan]

My calculator doesn't have the element of option

[sick meadow]

can anybody help me simplify this expression to n and q?

[severe swan]

How do I find the answer to this problem? Which of the following is equal to 1 + 2 + 3 + ... + 100?
Answers:

50(100)

100(101)

( 50(101) )/2

( 99(100) )/2

( 100(101) )/2

If I put all of these into my calculator I don't get the same answer as I do when I did 100! since that is the same as 1 + 2 + 3 + ... + 100.

[coral parcel]

No, 100! means 1 × 2 × 3 × ... × 100 -- factorial is a product, not a sum.

Your calculator most probably doesn't have a button for doing 1 + 2 + ... + 100 in a single step, since there are simple formulas for getting the result of that by basic arithmetic.

[severe swan]

Ok thank you very much

[coral parcel]

The sum of 1 + 2 + ... + 100 is the subject of a famous (apocryphal) anecdote about Gauss, so if you google for, say, sum of the first 100 numbers, you'll find lots of explanations of what the sum should be and why.

[severe swan]

Understood, I will do that

[manic zinc]

is this the right channel to ask about Master's theorem ?

[silent hinge]

Hello g

Guys*

Can anyone please explain to me how this numbers are being worked out

How the heck 92 turned into 2

77 and 62 into 2*2, 85 to 1 and 11 to 2

I know I could’ve asked in class but this professor gets so annoyed by anyone asking questions

[pale epoch]

when working modulo n you can replace numbers in sums and products by their remainder when dividing by n

92 divided by 3 is 30 remainder 2

the other stuff is similar

[severe swan]

How do I solve this? https://imgur.com/a/sZcxCCh

[coral parcel]

The first factor kills everything else.

[weary tiger]

How many auto morphisms? I count 48.

[coral parcel]

Sounds right.

[silent hinge]

oh i see, how about something like 7 * 3 + 4 mod 9

is equal 7

how so

[coral parcel]

No tricks there. Just calculate 7×3+4 first.

[silent hinge]

damn there it is

now i see it

[icy parcel]

hey

can someone check a dfa for me?

I have a question:
I had in my discrete exam a question that requires us to draw a dfa for [0,1]* that its binary representation is not a multiple of 3
lets say i want to check 110
do i start inputing in my dfa from 0 or from 1?
i did it from right to left (0) is it wrong?
(the exam was a week ago but i wanna check if i did it right)

all the inputs im trying are working even when i read the string from right to left

[coral parcel]

It actually works from either end.

A binary number is divisible by 3 iff the difference between the number of ones in odd positions and the number of ones in even positions is a multiple of 3.

Reversing the bits in a number either doesn't change which positions are odd or even, or swaps the odd positions for the evens

In either case the difference in the divisibility test is either the same or minus what it was before, which doesn't change whether it was a multiple of 3.

[icy parcel]

did that in my exam, is it correct?

tried many case it works

(just tried 333 somehow it says its acceptable but shhh i dont wanna overthink it) ugh

[coral parcel]

That doesn't look right. Inputs 11 (= 3) and 101 (=5) both end up in the same state.

[icy parcel]

fuck

thanks.

[inner beacon]

are proofs by contrapositive and contraposition the same?

[coral parcel]

Yes.

To the extent both mean "proving the contrapositive of whatever your goal is".

[severe swan]

If I have a summation problem and there is no numbers or variables at the top of the sigma in the problem is there a default number I should put?

[coral parcel]

Can you show what you're looking at?

[weary tiger]

Normally I'd go to infinity or the end of the set if I have that

[severe swan]

Ok Thanks

[cerulean wind]

composition of an integer n is just a way of writing n as the sum of strictly positive integers, correct?

right

this recurrence is incorrect then

the number of compositions of n into k parts is ||(n-1)C(k-1)||

when you sum from k = 1 to n, you get ||2^{n-1}|| total compositions

[vital dew]

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

[cerulean wind]

So, you're saying $$ a_n = \sum_{k=0}^n \binom{n-1 }{k-1}$$

[vital dew]

c squared

[cerulean wind]

yes, but in particular, that sum is equal to 2^{n-1}

by the binomial theorem

if you just want to partition n into k parts

strictly larger?

okay, then you just need to subtract 1 from 2^{n-1}

but anyway, imagine that we have n circles all lined up

so, o o ... o (n o's)

if we want to break this up into k parts, we need to choose k - 1 places to split the sum at (not at the end points), so there are (n-1) C (k-1) ways to do this

for n = 4, it should be 7

for n = 5, it should be 31

is that what you got?

no, the size of the parts need to be larger than one

not the number in the composition

wait am i dumb

im dumb

my bad

[coral parcel]

The a[n-2] term are for those solutions where the first part has size exactly 2. If the first part has size > 2, on the other hand, remove one from the first part and you have a valid solution with sum n-1, for which there are a[n-1] possibilities.

[cerulean wind]

if you want repeated underscore's, you can use \_ on each of them (just in case)

[coral parcel]

For example: two of the solutions with n=10 are 2+5+3 and 4+4+2.
Of these 2+5+3 starts with 2; it corresponds to the n=8 solution 5+3.
On the other hand 4+4+2 starts with something larger than 2; subtracting one from the first term gives us 3+4+2, which is a solution for n=9.
Every solution for n=10 arises in exactly one way from one of these principles, therefore a10=a8+a9.

[weary tiger]

hey

would someone be able to help me with my homework

I haven't been to class in 2 weeks because of health issues and it's due tonight

I have a good grade in this class and I want to understand but also I have no clue wtf is going on

I'm thinking I have to use the method of direct proof but I'm not really even sure how that idea works because I haven't been over it myself

and I don't know how involved that gets with multiple different variables

or like a youtube video or ANYTHING

I'm just completely lost and my teacher's notes are not legible

[wide vine]

How do you know it is A and (B or C)

and not

(A and B) or C

based on the sentence

For lunch you had a ham and cheese sandwich and an apple or an orange.

[wide vine]

my book has

so

[coral parcel]

That is not a matter of symbolic logic, but a matter of figuring out what the speaking of the English sentence must have meant by that sentence.

Only after you understand the meaning of the sentence can you start writing down a corresponding symbolic formula.

The order of operations is a convention for how to write down symbolic formulas. It cannot dictate the meaning of utterances in natural languages.

So in this case we can reasonably guess that the speaker is more likely to have meant "sandwich and (apple or orange)" than to have meant "(sandwich and apple) or orange" based on our real-world knowledge about the food items in question. It seems to be more likely that the speaker intended to describe one of two meals that we'd consider roughly equally filling. It would be an unusual in practice to need to describe a choice between sandwich+fruit and just fruit but which fruit it is depends on whether you also take a sandwich. So if the speaker had really meant the latter, one would expect them to use more words to make sure the unusual meaning got through to the listener.

[coral parcel]

Also, when you think about it, it's somewhat duplicitous of the book to pretend that any of the "and"s in that sentence really have a meaning that corresponds to logical conjunction. A native speaker of English would most likely understand the sentence to be making a claim about the listener's entire lunch (or at least the non-beverage items in it), not just "your lunch included a sandwich, and it also included an apple". The native speaker would probably find that the sentence was not a true utterance if the lunch actually consisted of a sandwich plus an apple plus a croissant. But the purported logical translation would be true in that case.

[spare orchid]

From Levin Discrete Mathematics 3rd edition page 28, just to check if I understand the question (pls give no answer yet, :)) we want to give the number of subsets that you can make from the set {1,2,...,10} with cardinality 2 right

so for example the set B2 contains the set containing the empty set and set A because this set has cardinality 2 and contains two subsets of A namely the empty set and set A

[gritty crescent]

No

[gritty crescent]

You were right here

B_2 is the collection of those subsets of A that have cardinality 2

Emptyset has cardinality 0 so it is not in A

[spare orchid]

nono I mean " the set B2 contains the set containing the empty set and set A because this set has cardinality 2 and contains two subsets of A namely the empty set and set A (edited)" among other sets

ah

[gritty crescent]

The elements of B_2 are subsets of A, not collections of subsets of A

For example {1,2} is an element of B_2

[spare orchid]

so 45

[gritty crescent]

How did you arrive at it?

[spare orchid]

10! divided by 2! and 8!

yes I need to learn latex one day :p

[gritty crescent]

[spare orchid]

but my mistake was also make combinations of empty set with the elments of A, and the set A itself with elements of A, and the set containing A and empty set + 45 combinations, to arrive at a wrong total of 66 but its clear now

because {empty set , 1} has cardinality 2, but it is no subset of A, i get it

thx

[vital dew]

Manan.

[gritty crescent]

No worries

[spare orchid]

yes my thought was a combination of subset, elements and pwoer sets, i should have rephrased it out loud

[noble wasp]

any book recommendations for discret math?

[spare forge]

What does the assumption for a graph $G = ({V}, {E})$ that $V \cap E = \emptyset$ mean?

[vital dew]

Qlinltiqor

[spare forge]

That no vertices or edge share something?

Oh, its likely vertices are just a set of singletons but edges being sets of 2-subsets (sets containing information of a connection between two vertices) will just have the intersection yield the empty set on outer comparisons.

[stray reef]

misplaced {}

also $V \cap E = \varnothing$ just means there's no such thing as an object that is an edge and a node simultaneously

[vital dew]

Ann

[spare forge]

Okay, that makes sense 👍

[sacred dune]

this is not so much a math question, but would anyone have a pointer as to why i only got half points for this exercise? It was a really easy one, super simple to intuit and I know the numerical answers are fine but i didnt want points getting taken off per lack of rigor so i tried to justify things a little more, and im guessing that's where i lost points in the second question, i just need someone to confirm

the questions were distributing postcards of 3 types to 12 friends, where in the first scenario we have as many cards as we want and in the second we have 4 of each type

omg nvm

i think i got a point taken due to a typo in the first one 😭 Edit: turns out I used the wrong equivalence relation in the second part of course: should’ve been mod 3

bruh i really ought to read over my work

[naive sonnet]

Any resources on natural deduction proofs, gentzen style specifically? They're incredibly hard to find, most of what I could find was fitch style. I honestly do not get it at all.

[fossil stump]

Can Someone Please Explain this?

[gritty crescent]

Do you understand what it means for the dice to be indistinguishable?

[fossil stump]

Well Not exactly.

[gritty crescent]

This means that for our consideration, when we roll the dice we can't "tell them apart". So there's no notion of "4 on dice 1, 3 on dice 2", but instead "one of the dice has 4, the other has 3".

[fossil stump]

I see.

So if 2 dies get same digits then they can not be distinguished.

[gritty crescent]

Even if they get different digits

Okay let's go back to the usual case where dice are distinguishable

[fossil stump]

Okay.

[gritty crescent]

You know there are 36 possibilities for rolling a pair of distinguishable dice, right?

[fossil stump]

Yes.

6^2.

[gritty crescent]

Now when the dice are indistinguishable, our ability to tell apart, say, (4,2) and (2,4) goes away.

[fossil stump]

Yes.

[gritty crescent]

Both the combinations correspond to "one dice has a 4, the other has a 2"

[fossil stump]

Yes.

[gritty crescent]

So we count in this spirit: first we count the number of ways of getting two distinct numbers on the dice from the six possibilities. Since the order doesn't concern us anymore, the number of possibilities is 6C2=15.

Does this make sense?

[fossil stump]

Yes.

Wait what?

6C2 = 15?

Oh Okay wait.

The Notation you are saying.

[vital dew]

Manan.

[fossil stump]

Yes Yes.

[gritty crescent]

6C2 tells us the number of ways we can choose two distinct values out of 6.

[fossil stump]

Yeah.

[gritty crescent]

But we also need to account for the cases where both dice turn up with the same digit

[fossil stump]

6!/2!(4!)

[gritty crescent]

And since there are only 6 digits

We have 6 such possibilities

[fossil stump]

Yes.

[gritty crescent]

Thus the total number of ways you can roll a pair of indistinguishable dice is 15+6=21

[fossil stump]

We Could have also done 36-15 right?

[gritty crescent]

Sure

Can you tell me why 36-15 works? 👀

[fossil stump]

Total Number of possibilities- uhhh wait let me name this.

Total number of possibilities- distinct Total possibilities.

[gritty crescent]

[fossil stump]

What Does this exactly mean?

[gritty crescent]

6C2 accounts for the cases where both dice have different digits

You could also have, say, 1 on both dice

So you need to account for them as well

You can only roll two dice with the same digits on both of them in 6 ways, one for each digit 1-6

[fossil stump]

Yes Okay.

[fossil stump]

So?

[fossil stump]

WhAt?

[gritty crescent]

You need to account for them if you want to count all possibilities

[fossil stump]

What Are you saying?

Mhmm This gets weird with all the combinations vs permutations and order or not and repetitions or not stuff.

[gritty crescent]

I think I don't understand your point of confusion here. You wish to count the total number of ways you can roll a pair of indistinguishable dice. There are two mutually exclusive and exhaustive possibilities: both dice show distinct digits, or both show the same digits. There are 15 ways in which the former can happen, and 6 ways in which the latter can happen. The total is thus their sum.

[fossil stump]

Oohh so same digits.

[gritty crescent]

Yes

[fossil stump]

Okay so See.

What we include-

1. Same digits in Both dice.
2. Different digits in both dice.

We we exclude -

1. Similar kinds of pairs coming from different outputs, like (4,1) and (1,4) are considered as the same output and hence not considered alone.

Right or Wrong?

@gritty crescent.

[gritty crescent]

Correct.

[fossil stump]

Yeee!

Neat.

[gritty crescent]

This is precisely what being indistinguishable means.

[fossil stump]

Oohh.

I see.

[gritty crescent]

If you assume your dice to be distinguishable, the table of possibilities can be enumerated like this. When the dice are indistinguishable, everything above the wiggly line is redundant since a pair below the wiggly line already accounts for it (say, (4,2) already has (2,4)).

[fossil stump]

Oohh.

You Wrote That xd?

[gritty crescent]

Yes

[fossil stump]

Damn Damn so fast.

[gritty crescent]

As you can see in the picture, the number of redundant entries is 15, out of a 36 total.

[gritty crescent]

Answering this

[fossil stump]

Hmmm.

Yes.

Why is There not an elementary Combinatorics channel Though?

[gritty crescent]

Elementary combinatorics is within the scope of this channel.

[fossil stump]

HmMm.

Okay I guess.

[spare forge]

Hey guys, what is ${a}$ in

[vital dew]

Qlinltiqor

[spare forge]

Is it all the vertices in the $A$ of a bipartite graph?

[vital dew]

Qlinltiqor

[spare forge]

Then is $A' \cup {a} = A?$

[vital dew]

Qlinltiqor

[spare forge]

Or is it just a single vertex $a \in A?$

[vital dew]

Qlinltiqor

[coral parcel]

{a} is the set whose only element is a.

A' cup {a} is the set whose elements are all the elements of A' and also a.

Presumably the letter "a" has been defined in the context to represent a particular vertex of the graph.

[spare forge]

Thanks for the clarification

I'm now confused in the part where it says $b \notin P$ when the preceding line stated a path $P$ being generated between vertices $v$ and $b.$

[vital dew]

Qlinltiqor

[spare forge]

I guess in the matching, $b$ isn't selected yet but lies ready to be augmented in the matching $M$ from the alternating path identified in a previous part.

So $Pvb$ denotes a future path that can become a matching.

[vital dew]

Qlinltiqor

Qlinltiqor

[stray reef]

no, P is a path between a and v. Pvb means the path that extends P by the edge vb

[spare forge]

Oh, damn.

That makes more sense now

I was getting confused with this in an earlier part of the book:

[coral parcel]

Dang, that's confusing notation.

[spare forge]

So $vb$ is meant to be a discovery in the bipartite graph

[vital dew]

Qlinltiqor

[spare forge]

I guess the mental hurdle can be removed by assuming an alternating path not be perfect walks through each partite such that there can be large skips between two vertices in $A$ or $B$ just that the path starts in $A$ and ends in $B$. But then, there's options of $B$ unselected that vertices starting in $A$ matched or unmatched can match in $B$ with.

[vital dew]

Qlinltiqor

[spare forge]

My notation is really imprecise but I think I am understanding the proof to the Marriage Problem a bit more now. Thanks for the help and until next time.

I guess just a little question now with this theorem:

Does $S$ just mean some subset of $A$ called $S$?

[vital dew]

Qlinltiqor

[spare forge]

And then the neighborhood is all possible matchings of degree one from a vertex $v \in S$ to some vertex in $b?$

And then $|N(S)|$ means the sum of the number of all those possible matchings for each vertex in that subset?

[vital dew]

Qlinltiqor

Qlinltiqor

[hearty furnace]

What is the negation of "1 < a < 5"?

[spare orchid]

This is another way of saying odd natural numbers in the interval [0,100]? so the cardinality of this set is 50?

[spare orchid]

I could be wrong, but I think a can be smaller than or equal than 1 or bigger than/ equal than 5,

[hearty furnace]

A is less than or equal to and or 5 is less than or equal to A?

I believe I said that right

[spare orchid]

https://www.khanacademy.org/math/algebra/x2f8bb11595b61c86:solve-equations-inequalities/x2f8bb11595b61c86:compound-inequalities/a/compound-inequalities-review

[spare orchid]

no I think a can be smaller than 1 or equal to 1 OR a can be bigger than 5 or equal than 5

[hearty furnace]

I'm just trying to prove the proper negation

Because the question is

The negation of "1 < a < 5" is "1 >= a >= 5."

[spare orchid]

i think thats wrong I think "1 < a < 5 can be written as (1 < a) AND (a < 5)

and if you negate that

you get

[hearty furnace]

yes it is 100% wrong

I need to prove why its wrong and give the proper negation

[spare orchid]

(a =< 1) OR (5 =< a)

well see my answer

[hearty furnace]

thank you sir

[spare orchid]

well I'm no expert, it needs confirmation from another discord guy

im just learning discrete math at my own pace :p

[hearty furnace]

oh

cause yea I've tried rewatching these lectures

many times

even looked through our book

I have no examples with numerical values

just words 😔

[spare orchid]

but if you see the khan link i send you, you can see how to write double inequalities as an AND clause of two inequalities

and then you can use the https://en.wikipedia.org/wiki/De_Morgan's_laws

so I think im right

[hearty furnace]

hey man it's more right than what my answer would've been 😂

thanks

[spare orchid]

np

[severe swan]

Can someone explain how to solve these problems? I got them wrong on my quiz and I have no idea how to do it. How do you calculate it if there is no number on the top of the sigma? How do you calculate the answer with the E at the bottom instead of an equals sign?

[stray reef]

$\sum_{x \in A}$ means you sum over the members of $A$

[vital dew]

Ann

[stray reef]

which are denoted by x

so the first problem would be "for each element of A, add 1"

and the second would be "add up all the elements of A"

[floral field]

I’m working with set partitions. For n=8, if I want to count set partitions with at least one of the blocks being size 2, would 8C2 count all of these or would it undercount?

The _ are slots for the integers, and the | are the “walls” between blocks.

[severe swan]

Thank you @stray reef

[ashen cloak]

so my professor went from x^2+3y less than/equal to 9
to -3 less than/equal x less than/equal 3
Can someone please how?

[floral field]

Solving for y might give intuition as to why

In the first inequality

[dire obsidian]

Is there anything wrong with my answer?

[coral parcel]

"n=k" and "n=k+1" are really confusing ways to state the induction hypothesis and conclusion.

And the p(n) you prove by induction should really be: n=1 or n=3 or there exits a,b such that n=2a+5b.

[dire obsidian]

Can you elaborate a bit more? This is really confusing to me

[coral parcel]

There are two additions.

[dire obsidian]

does proving p(k+2) not work?

[coral parcel]

You're stating p(n) as n=2a+5b, but that should really be there exist a,b such that n=2a+5b. The variables a and b are not constants that are defined externally to what you prove.

[dire obsidian]

Can you show me an example of how that would even look like? I don't think I've been taught about inductively proving anything other than p(k+C)

[coral parcel]

In addition to that, mathematical induction is for proving something that is true for all natual numbers n. The statement you've written down is not true for n=1 nor for n=3, so it shouldn't be provable by induction; you need to modify the statement into something that is always true.

Can you show me an example of how that would even look like?
I don't understand the question. I've just typed what it should look like twice.

[dire obsidian]

Here's the "official" solution to this question:

does this clear things up more

induction is so wack

[coral parcel]

The looks pretty sloppily written to me, too.

I surmise that "Alternative Form of Mathematical Induction" refers to long induction.

[dire obsidian]

This is also really confusing to me

[coral parcel]

Hmm, okay, so this does match the way the model solution is phrased.

It's valid too, but is not the way things are usually presented.

[dire obsidian]

It's confusing af to me

Quizlet gives more "clear" answer to this question but with less explanation

This is just extremely confusing to me in general

[coral parcel]

Okay, so to back up: I still maintain that you must have the words "there exist a and b such that" (or symbols to that effect) in your statement of what you're proving.

That is, if you use the letters a and b in the context n=3a+5b, of course.

[dire obsidian]

does this part of the solution satisfy this?

[coral parcel]

All the solutions we've seen here miss what I think is a crucial reasoning step, namely to state explicitly that if k+1 is at least 6, then k-1 is not 1 or 3.

[dire obsidian]

I think the quizlet solution makes more sense to me

That said I don't know why they are allowed to do this assumption

base case S(4) and S(5) are proven but that only allows you to use assumption of
S(k-1) and S(k)

[coral parcel]

That's basically the induction hypothesis in long induction: You assume that p(n) is true for all n smaller than the one that's your goal right now.

But again, it would be much clearer if we had defined S(n) to mean "n=1 or n=3 or n is the sum or twos and fives".

Then we could honestly assume that S(1), S(2), S(3), ..., S(k) are all known to be true.

[dire obsidian]

so when I assume S(k) I am automatically allowed to use S(k-1)

[coral parcel]

No, that's not what I say.

I'm saying you are assuming S(1) and S(2) and S(3) _ and_ .... and S(k-2) and S(k-1) and S(k).

The fact that you can use S(k-1) is because that is one of the things you assume, not because you're also assuming S(k).

[dire obsidian]

So I still need the S(4) and S(5) proven first before I can assume S(k) and S(k+1) ?

[coral parcel]

Depends on what k is, if course.

If k is 5 or more, then both S(4) and S(5) are part of what you assume.

In the step where you're provign S(4), however, you of course cannot assume that S(4) and S(5) has already been proved,

[dire obsidian]

so it follows the "ladder rung" mentality?

[coral parcel]

Hmm, yes I think so.

[dire obsidian]

"You assume that p(n) is true for all n smaller than the one that's your goal right now."
This is only applied when n is an exact number like 4 and 5?

[coral parcel]

Um, that is how the general proof step in long induction goes.

You're being told "I have an k, and I promise you that S(n) is true for every n<=k. Your task is now to prove S(k+1)".
You can choose to let your proof depend on whether k is larger than 5 or not, but that choice is part of your proof, not part of long induction.

[dire obsidian]

so in this case if I assume S(k-1), S(k)
I am not allowed to also assume S(k-2)

[coral parcel]

As I've said already, the only way I can see to get this to make principled sense is to change S(n) such that it means n=1 or n=3 or n is a sum of twos or fives.

Then you can assume S(1) and S(2) and S(3) and so forth all the way up to S(k), whatever k is.

[dire obsidian]

This is wack

so the textbook itself gave a really bad question

[coral parcel]

You have only assumed S(k-2) when k is at least 3, of course.

[dire obsidian]

"I have an k, and I promise you that S(n) is true for every n<=k. Your task is now to prove S(k+1)"
Doesn't this automatically allow me to also assume S(k-2)?

[coral parcel]

Only if you know that k-2 >= 1.

(Or k-2 >= 0 if your induction starts at 0).

[dire obsidian]

wait why is this needed?

oh assume n >= 1?

[coral parcel]

Because S(-1) might not be true!

[dire obsidian]

so I also have to set k >= 6 for this proof to work

and by extension I'm allowed to assume as much as needed from the following expressions:
S(k-5), S(k-4),...S(k)

[coral parcel]

So the induction step would be something like:

Now k is an arbitrary number in N0 and we're assuming S(1), S(2), ..., S(k). We have to prove S(k+1).
If k=0 then S(k+1) is S(1) which is true because S(1) means "1=1 or 1=3 or 1 is the sum of twos and fives".
If k=1 then S(k+1) is S(2) which is true because 2=1·2+0·5.
If k=2 then S(k+1) is S(3) which is true because S(3) means "3=1 or 3=3 or 3 is the sum of twos and fives".
If k=3 then S(k+1) is S(4) which is true because 4=2·2+0·5.
If k=4 then S(k+1) is S(5) which is true because 5=0·2+1·5.
Otherwise k>=5. We then know that k-1 >= 4, which means that k-1 is positive (so we actually have S(k-1) among our assumptions), but k-1 is neither 1 nor 3. Therefore S(k-1) tells us that k-1 is the sum of twos and fives. If we now add in another two to that, we'll have expressed k+1 as a sum of twos and fives, and therefore S(k+1) is true.
This completes the induction step, since we have handled every possible value for k.

[dire obsidian]

I thought n!=1, n!=3 ?

[coral parcel]

As I've said several times now, we need to make the claim we're proving something that is true for all n.

Therefore I'm correcting the solutions into something I actually think makes sense.

Saying "if n!=1 and n!=3 then such and such" is the same as saying "n=1 or n=3 or such-and-such".

[dire obsidian]

ok

[dire obsidian]

so you always have to provide a bound whenever you assume k?

[coral parcel]

Hmm? Not if the original goal you're proving is actually true for all the naturals.

[dire obsidian]

wait nvm

[coral parcel]

What exactly are you referring to with "bound" here?

[dire obsidian]

$n\in Z^{+}$

[coral parcel]

\in

[vital dew]

Salt

[coral parcel]

Yes, that's always part of induction.

[dire obsidian]

k range basically

[coral parcel]

(It differs from book to book whether 0 is included or not.)

[dire obsidian]

one more question, how do you know when to assume anything other than S(k)?

like in this instance assuming S(k-1)

[coral parcel]

You can always assume S(n) for all smaller n. Whether it helps you to do so depends on what it is you're proving, and must be figured out from case to case.

[severe swan]

Can someone explain why there are 2001 elements in the set? I don't understand how the math works.
-1000 + 1000 = 0 + 1000 = 1000 not 2000

[limpid fossil]

can we ask about algorithms here

[wide vine]

would g_0 be part of the sequence or only g_1?

for 2(b)

because they want the first 6 terms but say the sequences start with index 1

[severe swan]

You would use g0 to solve for the other numbers in the sequence

[wide vine]

what set?

[wide vine]

yeah I just didn't know if my first term was g_1 or g_0

[wide vine]

but I guess I should start with g_1, g_2, g_3, ....

[severe swan]

The first term would be g1

[wide vine]

{-10, -9,-8,-7,-6,-5,-4,-3,-2,-1 , 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9 10} Expand this idea but I think you are forgetting that you have the 0 term. You have [-1000,1000] so you have 1000 postive elemnts , 1000 negative elements, and one 0 element

like -1<=x <=1 would have 3 terms (assuming ints)

[-1,0,1]

[wide vine]

for (b) are they referring to the cumulative amount of just how much the cost would be for the last month

like are they just asking for the last month cost

or how much the person has spent in total over the 2 years

[static pond]

it would be cumulative i think
otherwise there would be no need to specify closed form

[wooden mason]

𝑝(6𝑛+0,3)=3𝑛2

𝑝(6𝑛+1,3)=3𝑛2+𝑛

𝑝(6𝑛+2,3)=3𝑛2+2𝑛

𝑝(6𝑛+3,3)=3𝑛2+3𝑛+1

𝑝(6𝑛+4,3)=3𝑛2+4𝑛+1

𝑝(6𝑛+5,3)=3𝑛2+5𝑛+2

I get that the constant terms are basically Pascal's, but why does it start at p(6n+3,3)

[whole hamlet]

Can someone please help me with this problem I’m really bad at factorials and word problems in general

[unreal stump]

So first you choose 4 spots to put 2,8 or 9 @whole hamlet

You have 6 spots left for everything else

So that would be 7^6*3^4 * C(10,4)

[whole hamlet]

Where did u get 7 and 4 from?

Oh nvm I got it thank you 🙏

[sick meadow]

∀x∃y¬M(x, y)

hey guys is this statement read like: For every value of x there is a y?

[ember obsidian]

yes, for all x there exists y where M(x,y) is false

[sick meadow]

M| 1 | 2 | 3|
1 T T T
2 T F T
3. T T F

Okay so with these values the statement would be considered false right ? since there is a negation all the Ts will become Fs and all Fs will become Ts

M| 1 | 2 | 3|
1 F F F
2 F T F
3. F F T

so with the new table the first value of "1" which is "x" does not have a value for y so that makes the statement false because not every x has a value for y right ? @ember obsidian

The domain of discourse for this problem is a group of three people who are working on a project. To make notation easier, the people are numbered 1,2,3.The predicate M(x, y) indicates whether x has sent an email to y, so M(2,3) is read “Person 2 has sent an email to person 3.” The table below shows the value of the predicate M(x, y) for each (x, y) pair. The truth value in row x and column y gives the truth value for M(x, y)

Heres the question if it helps

[ember obsidian]

yes, M(1,y) is true for all y, so the given statement is false

[sick meadow]

okay thank you ! just needed to make sure I was understanding this correctly

[simple nimbus]

Hey guys I’m new to this discord and have just started learning discrete maths. Would I be able to post screenshots of worksheets on here because I’m a little bit unsure of some of the answers

[hard citrus]

yes

[simple nimbus]

Can someone please help me answer these? I got the first one from b.) as a tautology and question 3 a.) I got (ii) as correct and (i) as incorrect. I’m unsure of the other ones

[simple nimbus]

Can someone explain how I would answer (b) and (c) without using truth tables please?

[pale epoch]

have you tried using what is mentioned?

[crude mango]

$~p\or (~q\or r)$

Try from there

[vital dew]

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

[crude mango]

Oh ok latex

Yeah idk how to get the symbol

[pale epoch]

$\neg$ for negation $\lor$ for logical or, $\land$ for logical and

[vital dew]

Lochverstärker

[crude mango]

Makes sense

[simple nimbus]

I’m trying it now, im trying to convert all the -> to what’s mentioned on the sheet

[pale epoch]

yes, do that

[crude mango]

$\neg p\lor (\neg q\lor r)$

[vital dew]

hiiistrex

[pale epoch]

report back with results

[simple nimbus]

Is this what it looks like when -> is converted to what’s mentioned?

Oh okay yeah I got that

I’m just wondering how to prove its logically equivalent to the right hand side

[simple nimbus]

This is what I got

[pale epoch]

looks good

can you pull the negation into the parentheses on the right hand side?

(to see that both sides are the same)

[simple nimbus]

This is what I got, but I’m only a bit confused because there’s an AND on the right hand side and none on the left

[simple nimbus]

^

[pale epoch]

oh, this isnt correct

pulling the negation into parentheses will 'flip' the connective

does "de morgan's law" ring a bell?

[simple nimbus]

Ohhh yeah I get it now!

[simple nimbus]

Can I get rid of the parentheses to make both sides the same?

[pale epoch]

good question

you also should have covered this

is $(a \lor b) \lor c$ the same as $a \lor (b \lor c)$?

[vital dew]

Lochverstärker

[simple nimbus]

According to my logic yes but I’m not 100% sure

[pale epoch]

you are correct

this is called associativity

tbf you have to verify this (and also de morgan's law) using truth tables

so the exercise is a bit misleading

i just assume you have verified both those things earlier in class

[simple nimbus]

I remember verifying de Morgan’s law but not associativity, however my memory is not the greatest and we most likely have covered this in class lol

[pale epoch]

you should have, but whenever you are unsure, you can verify it yourself

you will have to use truthtables though

its easier to just verify such small rules often though

and then use them repeatedly

instead of making giant truth tables

(which i think this exercise is trying to show you)

[simple nimbus]

Okay makes sense. Thank you so much for your help! I’ll be back on here tomorrow if I’m stuck with anything else. Have a good day/night!

[weary cobalt]

Can someone explain if there is any connection or similarity between a minor of a graph and a subgraph of a graph

for some reason I think that they should be closely related but I dont understand why they require separate definitions

I believe that any subgraph is a minor

but not every minor is a subgraph

[shadow geyser]

how would go about proving if there a second order logic statement that is true in Q + Q but not in Q?

also if anyone doesn't mind I would appreciate if they could explain what second order logic really means

[ebon quest]

Hi, I was just wondering if i did this proof correctly, if someone could check it over that would be awesome

[soft bobcat]

Hey! I wanted to ask a quick question, how would I prove that P(IN) is uncountable?

[crude mango]

Shouldn't you be using the definitions of subset etc

There's a bunch here that seems off

[ebon quest]

Really? Can you tell me how to fix it?

[crude mango]

$B\subset A \to A \intersect B = B$ needs to be proven

[vital dew]

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

[crude mango]

Pretend that's an intersection

Idk the latex for it

But that's not "immediately obvious"

[ebon quest]

I’m not sure I understand

[crude mango]

The 3rd line you wrote in the first proof

Have you justified that

[ebon quest]

“B is a subset of A implies A intersection B = B”?

That’s the line you’re talking about right?

[austere cedar]

its $A \cap B$

[vital dew]

Alexander42

[crude mango]

Hmmm ok

What's union

[crude mango]

Yes

[austere cedar]

$\cup$

[vital dew]

Alexander42

[crude mango]

$\cup$

[vital dew]

hiiistrex

[crude mango]

Good to know

[ebon quest]

Wdym by justify? Like I have to show that A intersection B equals B?

[crude mango]

Pretty much yeah

[ebon quest]

How would I do that?

[crude mango]

Idk exactly what level of rigor your class expects tho

[crude mango]

Basically use the definition of subset to derive the statement

[ebon quest]

Sorry, I don’t really get it

Would this correct? @crude mango

[crude mango]

But that lemma (fancy word for proof within proof in case you didn't know) is invalid

$(A\cup B)\subset A$
$\newline \forall x, x\in (A\cup B)\to x\in A$
$\newline\forall x, (x\in A\lor x\in B)\to x\in A$

[vital dew]

hiiistrex

[crude mango]

That's the fully expanded version of the left

Technically I skipped a step but it comes out the same

[ebon quest]

Sorry I still don’t really get what’s you’re saying

[rigid oriole]

What is invalid?

nvm nvm I see it

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

[crude mango]

Yeah

[rigid oriole]

a in B does not imply a in A n B
This is the main error

[crude mango]

This looks like law of explosion except it's not law of explosion

[crude mango]

^^^ if it was union that would be different

Not that union is particularly helpful

[rigid oriole]

This may be true under certain circumstances however.

You would need to justify why though.

[crude mango]

^

[rigid oriole]

Also, I would advise against using $\varepsilon$ for 'is an element of'. Write $\in$ instead.

[ebon quest]

Umm can you guide me through how to properly prove my 2 cases? I’m not really following what you’re saying

[rigid oriole]

https://images-ext-2.discordapp.net/external/2VwlIunlUns7UXrHDhGGOvFLNEgFNUHxiqyD7mm5d-g/https/i.imgur.com/e4Nv1xj.png

We are not following this argument.

How does this follow?

This is the issue. Can you explain this please

[ebon quest]

Yeah ok I see, that doesn’t make sense, kinda comes out of nowhere

[crude mango]

So you wanna try again to fix that?

[ebon quest]

Yeah, I’ll try in a bit, kinda busy rn

Will you be on later to help?

[crude mango]

Might be

[ebon quest]

Am I allowed to ping?

[crude mango]

Sure, can't guarantee a ping will get my attention immediately tho

Sometimes it does, not always

[ebon quest]

So I’m good now @crude mango but I’m not really sure how to prove this

[crude mango]

How much do you know about predicate logic

It's easier imo to do it like that but we can work around it if needed

[ebon quest]

Uhh I’m not sure what that is lol

[crude mango]

$\forall x,x\in A\lor x\in B$

[vital dew]

hiiistrex

[crude mango]

Does every part of that look familiar

[ebon quest]

Yeah, for all x, x is in A or x is in B

[crude mango]

Alright cool

[crude mango]

Does me expanding the statement like this all make sense?

[ebon quest]

When I asked for help a while ago, they told me this

[ebon quest]

Sorry, which statement were you trying to explain?

[crude mango]

I started with P and reexpressed it

[ebon quest]

Oh ok I see

[crude mango]

Also

$P\to Q \iff \neg P\lor Q$

[vital dew]

hiiistrex

[crude mango]

Is that familiar

[ebon quest]

Yeah

[crude mango]

Alright now try applying that to the expanded P then simplifying

[ebon quest]

So, for all X, x is not in A and x is not in B?

[crude mango]

Or x is in A

You can't drop that

[ebon quest]

Oh ok

Then where would I go from here?

[weary tiger]

When constructing an adiabatic hyperbolic holomorphism, does the isometry of the Gaussian distribution concatenate itself within a principal obduration?

[simple nimbus]

If I bring the negation into the bracket on the left will it become (p AND not q)?

[spark aurora]

i think so? because de morgans law

[simple nimbus]

Okay that makes sense

Can someone please help me with c? I’ve done a and b but I’m not sure how to prove c as a contradiction or prove it’s false without truth tables

[dry raven]

anyone know how to approach this?

[weary tiger]

They are simply proving one direction of the equals sign

wait hold up

their second line is only true if B is a subset of A, so they used the fact that B is a subset of A to reach that B is a subset of A, thats literally circular

oh my bad

i am