discrete-math

[heavy tinsel]

oh ok. It kinda make sense

[lavish zephyr]

can someone explain regular expressions to me? I understand them for the most part but I feel like the * operator breaks rules to me. how can (aUb) only be a or b but (aUb)* can have combinations of the two? I thought they had to be kept seperated?

[coral parcel]

In general if L is some expression then L* matches anything that can be split into substrings that each match L separately.

There's no requirement of keeping anything separated, and it's not clear to me where you would get that impression.

[lavish zephyr]

isnt in this case (aUb) or? meaning a or b?

and since its one or the other they have to be seperated

[coral parcel]

a U b matches a and also matches b.

(a U b)* matches abba because abba can be split into the substrings a, b, b, and a which each is one of the strings that (a U b) match.

The meaning of a regular expression is quite simple: Which strings does it match, and which strings doesn't it match? It is not part of the meaning of the expression how it matches them.

(Except in the practical computing variant of "regular expression" where you have capturing groups and whatnot -- but those don't exist in the mathematical sense of "regular expression").

[lavish zephyr]

im sorry i think im a tad lost

so strings aren't individual combinations of them

[coral parcel]

What?

[lavish zephyr]

im sorry I'm not sure how to explain it

i thought each string from an expression was a combination that fit it

like

a(aUb) would either be ab or aa because it has to start with an a and then what comes next is either an a or a b

[coral parcel]

Yes.

[lavish zephyr]

is there like a way I can see something like (a+b)*? like a punnett square or something I can do for it?

[coral parcel]

Hmm, your phrasing is a bit odd, though. It is not that a(a+b) is either ab or aa. It is that a(a+b) mathces each of the two strings ab and aa.

[lavish zephyr]

because the way I was viewing it orignially i thought that the correct answer for (aUb)* would of just been any list of an amount of a's or an amount of b

[coral parcel]

That sounds like it's related to your wrong use of "is".

[lavish zephyr]

oh okay

so then

when it comes to regular expressions

its that each combination matches the definition for the language right?

im sorry im really bad at explaining but you might be right that I view the definition wrong

[coral parcel]

Hmm, let me try how to explain it.
Regular expressions are not a rewriting system.
You don't do anything like this:

[WRONG!] (a+b)* becomes a* becomes aaaaa

[lavish zephyr]

isnt it more like what combinations fit the definition?

so what combinations of a and b fit the definiton of (a+b)*

and that would be why a is allowed but C isnt because c doesn't fit that definition

[coral parcel]

You say:

The meaning of the regular expression a is the set {a}.
The meaning of the regular expression b is the set {b}.
The meaning of the regular expression a+b is the set {a,b}.
The meaning of the regular expression (a+b)* is the set {"", a, b, ab, aa, ba, bb, aba, ...}

[lavish zephyr]

okay

i understand that

[coral parcel]

Or in other words, the star operation is something that works on the entire set {a, b} at once, not on the individual members of it separately.

[lavish zephyr]

wait so

what does the + mean

it isnt or?

i know + and U are the same

[coral parcel]

The + is the operation that takes the union of two sets of strings.

[lavish zephyr]

but i feel like i might be confused by what they represent

isnt union both?

[coral parcel]

a describes the set {a}; b describes the set {b}`. So a+b describes the union of these two sets, which is {a,b}.

[lavish zephyr]

like a and b?

[coral parcel]

You can say "a is in the set, and b is also in the set". But you can also say "a string is in the set iff (it equals a or it equals b)".

[median forum]

does anyone understand these examples, i'm not quite sure how they're evaluating the answers that are getting

[coral parcel]

so distinguishing between "and" and "or" is more a question about which context you're going to use the words in, than about which operation it is. "Union" is unambiguous, on the other hand.

[lavish zephyr]

okay so i feel like i dont understand union now.

i thought for union to be true it had to contain both elements

so for example

aUb would have to contain both a and b to be true

it can't just be one

if only one is present then it cant be true

[coral parcel]

"Union" is not something that can be true or false. it is an operation that combines two sets and produces a third set.

[lavish zephyr]

is this union not the same as the set of elements union?

[coral parcel]

In this case one of the inputs is {a} and the other input is {b}. The output of the union operation is the set {a,b}.

The output here has two elements. One of those elements is the string "a", and the other is the string "b".

Perhaps you're confusing it with intersections? In an intersection, the only elements of the output set are those that appear in both input sets.

[lavish zephyr]

uh do you think you could hop in voice for a bit? theres a couple of things I want to show you that I think might explain why im confused by it like stuff i did from previous sections

[coral parcel]

I don't voice.

[lavish zephyr]

oh okay

is it okay to share a screenshot of it then?

[coral parcel]

Sure.

[lavish zephyr]

ok so when i hear things like union and and or

i think of this

to me the left one is union

where both the left and right have to be true

i view the right one as or where only one has to be true

so when i see a+b i see that its a or b

[coral parcel]

These are conjunction and disjunction, not intersection and union.

You may be thinking of $$ A \cup B = { x \mid x\in A \lor x \in B }$$ but even so you seem to have the wrong correspondence -- $\cup$ is much more analogous to $\lor$ than to $\land$.

[vital dew]

Troposphere

[coral parcel]

Or perhaps you're thinking of it as $$ x \in (A \cup B) \iff (x\in A \lor x \in B)$$

[vital dew]

Troposphere

[lavish zephyr]

i can see that theres a difference between the first and the second

but I cant tell you what that difference is

they are the same to me

[coral parcel]

The formulas I posted say the same thing just in slightly different ways.

[lavish zephyr]

oh okay

well yeah thats how I view it

is there a way to explain this union stuff in the same way as that

or is it too different?

[coral parcel]

Um, what I explained was how union works.

[lavish zephyr]

wait

so union does work

like aVb

[coral parcel]

Yes.

[lavish zephyr]

thats what I thought

so why isn't abba treated as something of its own

like in (a+b)* you said abba is a match

[coral parcel]

Here you said you identify it with a∧b which would be wrong.

[lavish zephyr]

yeah I was describing it wrong im sorry

I view the way of doing the equation with the right side

but I don't call the + sign union

I call it or

[coral parcel]

Okay then.

[lavish zephyr]

calling it union wasn't something I did until i started talking to you sorry

[coral parcel]

Back to regular expressions.

[lavish zephyr]

why in (ab+c) the ab is treated as a pair but abba isn't a pairing similar to that? I can't take away the individual elements from the ab so why can i do it to abba?

[coral parcel]

Here are a series of facts:

1. By definition, the regular expression a matches the string "a".
2. By definition, the regular expression b matches the string "b".
3. because of (1), the regular expression a+b matches the string "a".
4. because of (2), the regular expression a+b matches the string "b".
5. because of (3), (4), (4), and (3) the regular expression (a+b)* matches the concatenation of "a" with "b" with "b" with "a", which makes "abba".

[weary tiger]

Umm can someone help me with my math I'm really bad at it ( sorry for the bad English )

[coral parcel]

What is it you would expect (ab+c) to match that it doesn't? I'm not sure I fully understand your objection.

[lavish zephyr]

its not exactly the match part

its that in (ab+c)

ab is one thing

I cant seperate the a or the b

[coral parcel]

But the only thing that matters for regular expressions is what they match.

[lavish zephyr]

so does that mean the definition for (a+b)* is any combination of a or b? and that as long as the combinations only contains those two letters then its right?

[coral parcel]

Yes, that is what it works out to.

Similarly, if you had (ab+c)* you would get the set of all combinations of ab and c.

[lavish zephyr]

can i know why ab isn't a match for (a+b)?

is it because i can only take one element from it? so either the a or the b

but not both?

[coral parcel]

Because by definition, the only way a string can match (a+b) is if it matches a or it matches b (or it matches both, which in this case is impossible).

[lavish zephyr]

why is it impossible? is it the reason I said before?

[coral parcel]

Try #❓how-to-get-help

Why is what impossible?

[lavish zephyr]

why is it impossible for ab to be a match for (a+b) ab is both a match for a and b

im really sorry i just am having a really hard time understanding this i don't mean to try to be difficult or anything

[coral parcel]

No. The string "ab" is not a match for the expression a, and the string "ab" is not a match for the expression b either.

Because "ab" matches neither of the expressions a and b, it doesn't match a+b.

The only string that is a match for the expression a is the exact string "a". That's how single-symbol expressions work, by definition.

[lavish zephyr]

okay I understand that part

so I know that the only possible matches for (a+b) is a and b

but I can't explain how I know properly

a or b i mean

sorry

[coral parcel]

I'm really not sure what else to say here.

[lavish zephyr]

the way i thought it worked was that from this expression (a+b) I can only take one of the elements. so I can only have either an a or a b but I can't take both from (a+b) is that incorrect

[coral parcel]

That's why I started talking about sets.

[lavish zephyr]

so is it just that in (a+b)* i can repeatedly take one of the elements from each expression? for example to get to abba being a match for it I'm just doing (a+b) (a+b) (a+b) (a+b) and im just choosing a, b ,b, a respectively?

[coral parcel]

Yes, that's one way to think of it.
Suppose we have a machine that eats regular expressions and produces their meaning. The input is a regular expression, the output is a big bag where all the strings that match the expression are written down on little pieces of paper. Now each paper in the bag has a string written on it that matches the expression once, but all the papers are in the bag at the same time.

So when we feed (a+b) into the machine, out comes a bag that contains both "a" and "b".

If we pick apart the machine to see how it works, let's observe the module that deals with the star operator.

The input is an expression L*.

First the machine feeds L (without the star) into a smaller version of the same machine. Out comes a bag.

We now create an infinite number of identical copies of that bag and start scribbling.

All the myriad ways of doing the following operation: Pick some number of the copies of our bag -- zero or more. Then pick one piece of paper from each bag and burn the rest. Glue the papers you found together. Put them in your output bag and start over.

[lavish zephyr]

okay I think i get it for the most part

would (c+b)a* have a match?

no right

[coral parcel]

(c+b)a* matches strings such as "c" or "caaaa" or "baa".

[lavish zephyr]

thats what i thought

and (a+b)c* would be things like ac acc, bc ,bcc?

[coral parcel]

Yes.

[lavish zephyr]

okay

I think i understand it now

i really appreciate you taking time to help me understand

[coral parcel]

Good.

[lavish zephyr]

tysm

[median forum]

for this one

why is the intersection

{1,2,3}

i mean

any Bi should be = {1,2,3,4,5,..., 3i} right

so wouldn't it just be N

why is 4,5 ... excluded

[robust mango]

B_1 = {1,2,3}, B_2 = {1,2,3,4,5,6}, B_3 = {1,2,3,4,5,6,7,8,9} and so on

[median forum]

oh

that makes sense to me

but

how are you getting that form

or well i get the intersection and union

now

shouldn't it be like

[robust mango]

B_i = {1,2,...3i} means you have 1,2,...upto 3i in your set

[median forum]

mmhm

OH

so

ok

i get that

i thought it was saying

N, and then 3i would be some extraneous value at the end

as opposed to being a limiter

thanks

for 2) then

for the union

i get why its (0

since 0 can only exist when k is inf

but why is it 8)

i mean 11)

shouldn't 11 exist when k =1

so Fk = (1, 11)

OH

WAIT

IS IT BECAUSE

Fk = (values in here)

which are inherently excluded

so the max value

would necessarily be excluded as well

[robust mango]

You should draw a number line and highlight the given the intervals F_i

[median forum]

Suppose A is a subset of B, and that A and B are non empty families of sets
Prove that Intersection(Y ∈B) Y ⊆ Intersection(X∈A) X”.

can anyone help me approach this?

i fell like this just doesn't make sense to me

for example

if B was

(1,4i)

and A was

(1,2i)

or something like that

wouldn't inter(B) be = (1,4)

and inter(A) be = (1,2)

thus inter(B) is not a subset of inter(A)?

[tough abyss]

do you guys think my proofs are correct?

[fading abyss]

?

is this complexity theory @tough abyss

in the direct proof , this might just be me but you may want to add

$\forall a \in A, b \in B$

[vital dew]

suck2015

[quaint notch]

Hey guys, hopefully this is the correct place.
I need to prove the following statement.

Let {${A_i}i\in I$} family of sets so I is sorted. Prove that there exists sets $B_i {\subset} A_i$ foreign in pairs so $\cup B_i=\cup A_i$

Sorry, no idea how to use the math statements

[fading abyss]

put $ around the math stuff

so $x^2$

[vital dew]

suck2015

[quaint notch]

Yeah but I got it all wrong I guess

[fading abyss]

Let ${A_i}_i\in I$ family of sets so I is sorted. Prove that there exists sets $B_i<A_i$ foreign in pairs so $\cup B_i=\cup A_i$

is that supposed to be a union?

[quaint notch]

Yeah lol

😓

[vital dew]

suck2015

[quaint notch]

Also it should be {A_i}

[vital dew]

meitar5674

[quaint notch]

I think this is fine now, thanks a lot 🙂

Anyway my idea was to use axiom oh choice to get a single element from $A_i$ and do that by induction but I believe it works only for sets whose size is less then $\aleph_0$

[vital dew]

meitar5674

[wheat grove]

sorry for bumping a really old thread, but if delta = 1/3, wouldn't O(2^(m·sqrtn)) be slower than Omega(2^(delta·n))?

[coral parcel]

No, because n/3 will be larger than m·sqrt(n) as soon as n > 9m².

[wheat grove]

thanks 👍

[muted gate]

can somebody help? I don't understand the difference between the $<$ and the $>$

[vital dew]

texaspb

[muted gate]

why does this matter

that's how it's written in the book

[coral parcel]

x>y is just another way to write y<x.

[muted gate]

oh

HAHAHA

true

lmao

ok, thanks.

[coral parcel]

This is a common convention when working with order relations, but some books don't explain it explicitly.

[lavish zephyr]

I asked a question in one of the help channels and didn't get a response even after pinging. Would it be because there was a rule I missed or just nobody knows how to help/ is busy

it was related to discrete math so I was wondering If i was supposed to ask it here instead

[tough abyss]

Theoretical computer science

[coral parcel]

Probably just nobody who saw it could help. The numbered help channels are mostly frequented by people who feel competent to help with usual high school topics, simple calculus, or the like.

[lavish zephyr]

oh should i ask it here then? or continue to wait?

and also if I just wanted my work checked would I use a help channeel for that as well? that isn't the case now but in the future i was wondering

[light heath]

Could you guys examine my solution to number 46 please.

[coral parcel]

Asking in the topic channels is fine for university-level topics.

[coral parcel]

There's no rule against asking for solution checking, but you may or may not get a reply -- such requests are more tedious and less interesting/rewarding to answer than more conceptual questions, so fewer readers will bother.

[lavish zephyr]

okay. i was asking because I wanted to check to make sure I understood the stuff you told me about earlier but when I tried to put it in a calculator i got confused and when I used the help channel nobody said anything and I just thought I didn't post it right

[lavish zephyr]

do you think you could help me with summation and induction when you get a chance? it shouldn't be like helping me before I just am confused a bit because theres 2 variables

[coral parcel]

Yeah, the server has no mechanism that even attempts to ensure all questions get responses. (It's hard to imagine what such a mechanism could be when everybody around are just hanging out in their spare time, not even "volunteering" to satisfy any definite expectations).

Just ask your question, and it might either get a taker or not, is the best strategy available.

[lavish zephyr]

okay so this is the problem Im working with. I don't have to solve it fully. I only need to get in the form of (k+1)

what I dont understand is when I replace n with K do i replace I with k?

or do i just leave the I as is? and how does that affect the problem going forward?

[coral parcel]

The $i$ is a dummy variable that's not "visible" outside the summation. So for
$$ \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}$$
the induction step would assume
$$ \sum_{i=1}^k \frac{1}{i(i+1)} = \frac{k}{k+1}$$
and need to show
$$ \sum_{i=1}^{k+1} \frac{1}{i(i+1)} = \frac{k+1}{k+2}$$

[vital dew]

Troposphere

[lavish zephyr]

okay so for the most part that makes sense

so what would be the step of doing it with i?

or this problem rather

[coral parcel]

You can rename the i in one or both summations to something else if you want, but that is not an inherent part of substituting k or k+1 for n.

The natural way to use the induction hypothesis here would be to write
$$ \sum_{i=1}^{k+1} \frac{1}{i(i+1)} = \Bigl(\sum_{i=1}^k \frac{1}{i(i+1)}\Bigr) + \frac{1}{(k+1)(k+2)}$$
after which the induction hypothesis tells you what the sum up to $k$ is.

[vital dew]

Troposphere

[lavish zephyr]

okay

and to get that last part

its hte same as replacing the I's with k+1 right

[coral parcel]

Right.

[lavish zephyr]

and then on the right side we would get that its equal to = K+1/K+2 + 1/(K+1)(K+2)

i don't know how to write it the same way you do with the bot im sorry

[coral parcel]

Yes. But note that you want parentheses when you write the division as / instead of a horizonal bar: (k+1)/(k+2) + 1/((k+1)(k+2)).

[lavish zephyr]

oh yeah

[coral parcel]

The bot uses LaTeX format -- there's an extensive tutorial at https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

[lavish zephyr]

I have one more I need to do so I'm gonna try to do it on my owna nd Ill come back and just check to see if I did it right and Ill try to learn the syntax for the bot too

wait

i have one more question

when at the bottom the definiton for I changes to something like 0 or 2

does i adopt the definiton at the bottom still for when we set the top to 1

so for example lets say its the exact same problem we have

but instead of i= 1 its i=0

when your on the step of just setting n=1 does i=0 still or does it get set to 1 too

i wanna say 0 but im not 100% certain

[coral parcel]

Umm. I'm afraid I don't entirely grasp the question.

In general the summation notation works like
$$ \sum_{i=a}^{b} (...i...) = (...a...) + (...(a+1)...) + \cdots + (...b...)$$

[vital dew]

Troposphere

[coral parcel]

So you replace the i with each integer from the lower limit to the upper limit in turn, and add up what you get in each of the steps.

If there's not already an n in the lower limit, the lower limit stays the same when you change n.

[lavish zephyr]

$$\sum_{i=0}^{k+1}(i^3) = \sum_{i=0}^{k}(i^3)+(k+1){^3} = \frac{(k+1)(k+2)}{2}$$

[vital dew]

Jada Stop

[lavish zephyr]

so this was the one i was doing and that was what I got

oh

wait

i forgot one part with this one

$$\sum{i=0}^{k+1}(i^3) = \sum{i=0}^{k}(i^3)+(k+1){^3} = \frac{(k+1)(k+2)}{2} + (k+1)^{2}$$

[vital dew]

Jada Stop

[lavish zephyr]

okay thats what I wanted

except the fraction is squared

i don't know how to do that part yet

oh wait

my E got messed up

[coral parcel]

(The summation sign is capital Greek letter Sigma, not an E).

[lavish zephyr]

oh yeah i know that

but i don't think i have that as a thing on my keyboard

and I don't know if theres a shortcut to it

[coral parcel]

Ah.

[lavish zephyr]

i didn't know it was named sigma though

i just called it sum of all

[coral parcel]

One does usually say "sum" instead of "Sigma" when reading formulas aloud, yes.

[lavish zephyr]

would what I wrote be correct for what I'm trying to do? aside from the syntax errors?

and the missing square on the fraction

[coral parcel]

I don't immediately spot any further problems.

[light heath]

is it true the fact that disjunction, conjunction and negation are functionally complete because knowing that every compound preposition can be written in disjunctive normal form and still be logically equivalent means that negation, conjunction and disjunction are functionallity complete

[lavish zephyr]

tysm! your the best!

[coral parcel]

That sounds right, though I suspect you didn't intend to repeat "are functionally complete" twice there.

[light heath]

yea i worded it much better in my answer. Thanks for clarifying

[coral parcel]

No, actually ...

It looks like it's a bit circular reasoning.

[light heath]

wait

heres what i actually said

[coral parcel]

Rewriting a compound preposition to disjunctive normal form generally assumes that you already have an expression that's built from disjunction/conjunction/negation.

[light heath]

Since every compound preposition can be written in disjunctive normal form which contains only disjunctions, conjunction, and negations and knowing that they are logically equivalent means that conjunction, disjunction and negation are functionally complete

[coral parcel]

Yeah, that looks like a problem.

It might be right, but only if you have a somewhat unusual definition of what a "compound proposition" is.

[light heath]

number 47 is the actual question

[coral parcel]

Um, okay then. I stand corrected.

[light heath]

this is number 46 that the hint is referring to

[coral parcel]

Usually the definition of "functionally complete" requires you to be able to express any boolean function even one that is just given by randomly filling in a truth table. With the standard definition, you wouldn't get away with assuming that you already have a formula, but it looks like your exercise is deliberately setting lower goals than that.

Ah, I see -- if you put that together with exercise 46 you do in fact learn that every random truth table can be expressed.

[light heath]

ah ok great and also is my number 46 correct? I just want to be sure because the rest of the exercises in this section build off this . Is my answer to number 46 rigorous or does it leave ambiguity?

[coral parcel]

You might have noticed what I wrote to Jada about solution verification. :-)
There's a reason why teachers hate grading that kind of homework. When you know how the solution is supposed to go, it can be extremely hard to avoid skipping ahead past stuff you instinctively feel you can already predict. So it is very hard and tedious to positively verify that all of the details are actually written down right. And with just a photo of a handwritten sheet to go by, it just gets less appealing to dig into.

[light heath]

what do you recommend?

[coral parcel]

I don't have any concrete recommendation.

Except try to come to terms with the fact that what you want to have done is tedious, boring, unrewarding work that your teachers are actually paid money to do, in contrast to us randos on the internet -- so you may need to want for them to do it.,

[light heath]

fair enough thanks for your help though

[quaint notch]

Guys, any help regarding this?

[pastel hollow]

My book says that if $f$ is the generating function of $a_n$, then $xDf$ is the gf of $na_n$, which makes sense. Then it says that $(xD)^2f$ is the gf for $n^2a_n$, which doesn't make sense bc it should be $x^2D^2f +xDf$ by my calculations. And then it says that if $P(x)$ is any polynomial, then $P(xD)f$ is the gf of $P(n)a_n$ and I don't even understand what that means because they're evaluating a polynomial at the derivative operator??? So what is happening?

[vital dew]

EdgarAlnGrow

[coral parcel]

But (xD)²f is equal to x²D²f + xDf, if you write it out and use the product rule for D(xDf), so your calculations are not in conflict with the book.

[idle hazel]

yo how does this make sense

you have two sets, they have the same elements

but another has one more

random one

their number of subsets is the same

am i missing something

[coral parcel]

I don't even understand what that means because they're evaluating a polynomial at the derivative operator?
This happens in the noncommutative ring of functions (R->R)->(R->R) with composition as multiplication. R embeds in the ring (namely, a real number r is represented by the function that just scales its input by r), so you can evaluate a real polynomial in it, plugging in xD for the unknown.

[pastel hollow]

|B| = |A| + 1 ==> |P(B)| = 2^{|A|+1} \neq 2^|A| = |P(A)|

[coral parcel]

This will happen if the sets are infinite.

[pastel hollow]

so something doesnt seem right

oh

idk anything about infinity so ignore me

[idle hazel]

so | A | = k

| B | = k + 1

they both have 2^k subsets

how?

[coral parcel]

Yes.

[idle hazel]

cant you just make a subset with the new element B has

[coral parcel]

k+1 = k when k is an infinite cardinal.

[pastel hollow]

this is so confusing

[idle hazel]

i agree

as in it literally has one more

[pastel hollow]

i was talking about the gf thing

[idle hazel]

cant you make a subset with just that element

[pastel hollow]

but yeah infinity is weird and fake too

[coral parcel]

Perhaps a concrete example will help here.

[idle hazel]

id appreciate it

[coral parcel]

Suppose A = {1,2,3,4,...} and B = {0,1,2,3,4,....}.

Then for each subset S of B we can consider F(S) = { x+1 | x in S } which is guaranteed to be a subset of A. And every subset of A arises in exactly one way through this process, so F is a one-to-one correspondence between the subsets of B and the subsets of A.

Oh, perhaps you also wanted a concrete example of the generating-function thing? :-)

[idle hazel]

i understand but

why not make a subset with {0}

and you have one more

like

[coral parcel]

Suppose p(t) = t³ + 2t - 1, and f is a generating function for a_n.
Then the generating function for (n³+2n-1)a_n is xDxDxDf + 2xDf - f.

[idle hazel]

im lying to myself

[coral parcel]

${0} \subseteq B$ corresponds to ${1} \subseteq A$.

[vital dew]

Troposphere

[idle hazel]

ohhhhhhh

yeah i get it now

theyre both infinite

so like

one will always correspond to the other

thanks for the help

[coral parcel]

Infinite sets have the same size if it's possible to pair their elements up one to one. It doesn't matter that there are also other way to pair up the elements that leave some of them unpaired.

[idle hazel]

thanks for making me understand

would you mind if i asked you a career-related question btw?

[coral parcel]

You can ask; I might not have an answer.

[idle hazel]

allright so i have mild schizophrenia and im on the autism spectrum. do you think that will impact my career in math if it doesnt affect my ability?

im legally required to disclose that to any employee and stuff

[coral parcel]

Lots of people in math are on the spectrum, so that shouldn't be a big problem, as long as you're prepared to make a conscious good-faith effort try to adapt to social norms that don't come naturally to you. I'm less than qualified to speak about schizophrenia, but if you have it managed to a state where you can still get work done (note that "work" in a math career almost invariably includes teaching), then I'd expect it would be okay.

[idle hazel]

My schizo only goes as far as to hallucinations that I can distinguish are not real so its not a problem in that sense

I have a lot of nervous tics and Im eccentric to say the least but if I want to I can control myself

Its just that when people hear schizophrenia they think I hear voices and Im a psycho of some kind

[coral parcel]

Good luck!

[idle hazel]

Thanks, same to you

[wide vine]

In general, there is no known algorithm that can solve the factoring problem efficiently for any input integer. In the context of factoring, an "efficient" algorithm would be one whose running time is bounded by a polynomial function of the number of digits in the input number, not the value of the input number. How would I express this in BIG O notation?

so like if you had number = 1000, #digits= 4 and your your big O of this should be what?

it would still be O(n)?

but just that it would scale by digits rather than value

[pale epoch]

always depends on context, what you consider the input, and more specifically the size of the input, to be

also a number n has ~ log_10(n) many digits

so you can "translate" between contexts

[wide vine]

oh true

but doesn't the base not actually matter also

so you could just say log(n)

?

or in this context does it have to be log_10(n)

[pale epoch]

in big O notation it wont matter

[wide vine]

which I mean does make sense but I thought the whole log base didn't matter

okay

because you can always multiple it by something

[pale epoch]

logarithms to different bases only differ by multiplication with a constant

[wide vine]

yeah

[wide vine]

is the prime number theorem "proof" or how the approximation is found beyond the scope of a discrete math course?

The book just kinda mentions

and doesn't really give any about why this is true or whatever

[civic horizon]

Yes

The standard proof is using complex analysis, and the only elementary proof i know of isnt very nice

https://mathoverflow.net/questions/36897/probabilistic-interpretation-of-prime-number-theorem#:~:text=The intuition here is that,1−1%2Fp).&text=%E2%89%88f(n)%E2%8B%85%7B,if%20n%20is%20not%20prime.

I found this thread where the first answer might be somewhat interesting

[wide vine]

Ill just blackbox this one for now

[final cliff]

There might be a simpler way but there is a map called the stereographic projection that maps the unit sphere to the xy-plane plus a point at infinity. For S the unit sphere, that map will give you $|S|=|\mathbb{R}^2 \union{\infty}|=|\mathbb{R}^2 |=|\mathbb{R}^3|=|[0,1]^3|$ though it might take a bunch of work depending on your prev thms to fill in some of these gaps.

[hardy yoke]

Ah

How can I prove that the infinite set of points on the surface of sphere is the same size as the infinite set of points in it's volume given that the radius is 1. The way "probably" is doing it with bijection where you take the coordinates of surface and try to correspond them with volume coordinates. I just have no idea how to define the bijection function.

Yeah, I was just thinking about the task, and perhaps it was "compare the sets" aka bigger or smaller.

[vital dew]

DootDooter

[final cliff]

That's the only way I know how. It requires you know a bunch of stuff involving cardinality you might not already have?

Oh wait. 🤔

Shit I was assuming you meant the volume for the unit cube lol.

Idk why I misread it like that. :/

[hardy yoke]

I would assume infinite points on surface is "smaller" set cause you can't create function to biject it to it's infinite points in volume set and I have kinda an idea how to explain it with lines and stuff. No direct proof needed.

[final cliff]

The sets should have the same cardinality.

For example I just explained to you a method to show the cardinality of the set of points on the surface of the unit sphere is the same cardinality as the set of points in the volume of the unit cube.

[hardy yoke]

Right

[quaint notch]

Any help about this? 🙏🙏

[final cliff]

Shit this was supposed to be R^2 U{infty}

[final cliff]

I think I know a kind of shitty way to do the rest. The mobius transform f(z)=(z-1)/(z+1) is a bijection from the right half plane along with a point at infinity to the unit disk. So, you should be able to show via this map that a disk at the origin has the same cardinality as a plane. Taking cross sections of your unit sphere and mapping them to the planes containing those cross sections using the maps I just described should show the unit sphere has cardinality |R^3|.

So, then if T is the points in the volume of your unit sphere we should be able to show from our prev work that |T|=|R^3|=|S|.

There is probably an easier solution. Hopefully I'm not doing something too stupid either.

[coral parcel]

Did I miss what the question was here? The discussion sounds like it's something one would just hit with the Schröder-Bernstein hammer.

[final cliff]

It probably is lol

It's mapping the surface of the unit sphere to its volume

[coral parcel]

It will be easier to motivate people to write helpful responses if you actually write some text about how much you understand of the exercise, what confuses you, or where you run out of ideas.

[wide vine]

Just looked up Schröder–Bernstein theorem and seems logical. Is there something I am missing about it?

[final cliff]

I was thinking: stereographic projection -> shows surface has cardinality |R^3|. Mobius transform: can show disks have cardinality |R|. Taking cross sections of the unit sphere: can show the volume of the sphere has cardinality |R^3|.

[coral parcel]

Doesn't stereographic projection map the surface to R² rather than R³?

[final cliff]

Yeah but R^2 and R^3 have the same cardinality right?

Maybe I'm being dumb lol

[coral parcel]

Sure, if we already know that, it's easy.

[wide vine]

I assume this is more interesting with sets that are not finite? Not very familiar with dealing with sets that are infinite.

[final cliff]

I guess it's not exactly obvious that it works for infinite sets? The proof in Intro to Set Theory by Hrbacek/Jech is kinda nifty. 🙂

[coral parcel]

With Scröder-Bernstein, we need to
a) map the surface injectively to the inside: just move each point halfway towards the center of the ball.
b) map the inside injectively to the surface: the inside is a subset of R³; since |R³|=|R²| this injects to a subset of R², use stereographic projection (or whatever) to wrap it around the sphere.

[final cliff]

Ooh I like that a lot better lol

[wide vine]

Yeah I really need to look on how cardinality is defined for infinite sets.

And how you compare them. Any good resource?

[final cliff]

The book by Hrbacek/Jech I mentioned is nice so far. I haven't finished it yet. Enderton has another set theory book that is supposed to be good.

Intro to proofs books touch on this stuff too.

I remember it was in Book of Proof by Hammack.

@hardy yoke in case you missed it Troposphere pointed out a much simpler way using Schroder-Bernstein.

[coral parcel]

The nice thing about Schröder-Bernstein is that 90% of the time you can just wing it in both directions, because you're allowed to miss points with impunity.

[wide vine]

R^2 and R^3 have the same cardinality?

[final cliff]

I feel kinda silly not noticing such a simple solution.

[final cliff]

Yes.

[wide vine]

What about R?

[coral parcel]

R has the same cardinality as R^n for every n>1.

[weary tiger]

thats interesting do you know of an explicit injection from R^n to R?

[wide vine]

So there is a bijection between any R^n or was it just injection?

[coral parcel]

The most famous proof of this, by Cantor, goes: If you have n reals and want to map them injectively to a single one, write each of them in decimal, line them up so the decimal points match, and read out the digits alternatively from each line so you get a single sequence of digits.

[weary tiger]

if theres injections in both directions its a bijection by schroder burnstien thm, and theres a pretty straight foreward injection from R to R^n

[coral parcel]

There's some pedantic points to deal with about numbers whose decimal expansions might end with either recurring nines or recurring zeroes, but they can all be dealt with by hitting them with the Schröder-Bernstein hammer.

[wide vine]

Oh yeah lol. Thats interesting 🤔

[weary tiger]

and bijectivity is an equivalence relation so it reduces to showing injectivity from R^n to R

[final cliff]

If you have an injection from A to B and an injection from B to A then a bijection exists between A and B by Schroder Bernstein but neither of the two injections you use has to be onto or anything.

[weary tiger]

yeah exactly

[wide vine]

So does this start to tie into linear algebra? Like for finding / showing if you can invert some transformation?

Is there such thing as a cardinality regarding vector space or span whatever you call it

[weary tiger]

its not a linear transformation for one so id say no

[final cliff]

Isomorphisms in linear algebra (or just algebra in general) are bijections.

[weary tiger]

the natural measure of the "cardinality" of a vector space is its dimension

[final cliff]

Like, by definition an isomorphism is a bijective homomorphism.

I think isomorphisms get taught kinda late if at all in linear algebra.

[coral parcel]

Yeah, dimension is a finer distinction than cardinality: All finite-dimensional real or complex vector spaces except {0} have the same cardinality.

[wide vine]

I'm only familiar with isomorphism from graphs. Bijections between 2 sets are a form of isomorphism?

[coral parcel]

Bijections between two sets are the "isomorphisms" in the category of sets and functions, but nobody calls them that except to flex their knowledge of category theory.

[wide vine]

Like you are just relabeling the numbers? Idk maybe that is a bad

[coral parcel]

Isomorphisms of vector spaces are just the linear transformations that are also bijections.

[final cliff]

Brandon you know partial orderings right?

[wide vine]

Yes

[final cliff]

Because if you have two posets (A,R), (B,T) a bijection from A to B that satisfies aRb iff f(a)Tf(b) is sometimes called an order isomorphism I think.

[wide vine]

What does f(a)Tf(b) mean?

[final cliff]

Usually when people introduce the word isomorphism they want a bijection that preserves some other property.

T is the order relation for B.

f(a) and f(b) will be elements of B.

[coral parcel]

Indeed, "just relabeling" is a good way to think of isomorphisms in general. With the addendum that all the structure we care about is unaffected by the relabeling.

Different kinds of isomorphism are separated by which structures it is we care about.

[wide vine]

Oh yeah nyann was telling me about this. the prefix or word before is important

In telling you what I guess structure you are referring to. Isomorphism by itself I guess doesn't tell you much about what might be preserved

[wide vine]

Okay yeah this makes sense.

[final cliff]

It doesn't necessarily have to be T and R partial orders either they could just be any old relation I think. Like what you and troposphere were talking about.

[wide vine]

$Formally, given two posets {\displaystyle (S,\leq _{S})}(S,\leq _{S}) and {\displaystyle (T,\leq _{T})}(T,\leq _{T}), an order isomorphism from {\displaystyle (S,\leq _{S})}(S,\leq _{S}) to {\displaystyle (T,\leq _{T})}(T,\leq _{T}) is a bijective function {\displaystyle f}f from {\displaystyle S}S to {\displaystyle T}T with the property that, for every {\displaystyle x}x and {\displaystyle y}y in {\displaystyle S}S, {\displaystyle x\leq _{S}y}x\leq _{S}y if and only if {\displaystyle f(x)\leq _{T}f(y)}f(x)\leq _{T}f(y). That is, it is a bijective order-embedding$

[vital dew]

Brandon7716

[wide vine]

Oof it broke

I was copying the wiki definition. Is the

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

Not sure of the <= is required

Or what the correct notation is. Guess it doesn't matter as long as you communicate it

[final cliff]

Strict vs nonstrict partial orders are a thing I think. Any time you have one you can come up with the other by choosing to include/exclude equality.

The rules for them are slightly different but where you have one you can come up with the other easily enough.

[wide vine]

Oh like < vs <=

No reflective property

I suppose?

[coral parcel]

Either irreflexive or reflexive.

[wide vine]

Okay yeah so x < y would be irreflexive but x <= y would be reflective, right?

[coral parcel]

Yeah. Since the two forms convert trivially (and reversibly) to each other, it's more of a style distinction than a substantive one, controlled by what makes it easiest the express whichever use you're making of them.

[wide vine]

Got it

[lavish zephyr]

how do you properly write a finite state machine for something like (a+b)* c

I understand how to read them. but I struggle when I have to make my own

is there a graphing tool or osmething I can use to make an example of what I think it looks like?

[unreal stump]

a,b,c are expressions?

[coral parcel]

{a,b,c} is the alphabet. It's a regular expression.

[unreal stump]

https://cyberzhg.github.io/toolbox/regex2nfa?regex=KGF8Yilj

[lavish zephyr]

Okay I’m gonna try to make what I think it looks like with this and see where I went wrong

[fading abyss]

I'm surprised we don't have. a channel for complexity theory and tcs

[unreal stump]

Doesn't seem like that important to warrant it's own channel

[fading abyss]

actually, i stand corrected.It seems #foundations is the correct channel

[unreal stump]

There's #numerical-analysis

I thought complexity theory was finding complexities of algorithms

[fading abyss]

that channel is probably for like stat learning theory or something

[fading abyss]

classifying problems and their solutions

stuff like P vs NP, PSPACE

[unreal stump]

Isn't that computability theory?

[fading abyss]

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

hmm i guess some people call it computability theory

[unreal stump]

Ok, I just don't want to fall into this cs rabbithole

[fading abyss]

i thnk computability theory is like a proper subset of computational complexity

[zenith oyster]

I think I'm stupid but I don't understand why the largest is 5? Can someone make me understand why the longest here is 5? To me the answer is 2

[unreal stump]

0,2,3,7,8

That's the longest subsequence

[zenith oyster]

why? why isn't 1 included? Oh I see now. Why don't I understand that from the explanation?

[unreal stump]

Well maybe you got confused between subsequence and subarray?

[zenith oyster]

what determines a subsequence is just like items in order with some ignored

[unreal stump]

Yea

[zenith oyster]

so that's what consecutive would mean like they have to be next to each other?

[unreal stump]

Yes

[zenith oyster]

Thank you

[pastel hollow]

if $A$ is the gf for a sequence $a_n$ and $B$ is the gf for $b_n$, how can i find the gf for $\sum_{k = 1}^na_kb_{n-k}$? it's not just the product of $A$ and $B$ because the index on the convolution sum starts at 1 instead of 0

[vital dew]

EdgarAlnGrow

[quaint notch]

You are right, sorry, I'm just way too confused with that but will give it a shot.

According to our class definition 'ordered relation' means that '<' is reflexive, antisymmetric and transitive. But here as far as I can tell none of the 3 are reflexive?
Now I've found online that there are more definitions for 'ordered relation' where '<' is irreflexive and such. so I believe this solved that.

According to that:

1. has a minimum and thus sorted.
   2 + 3, no idea how to reach those, any idea regarding that would be helpful!

[coral parcel]

Does "well sorted" have a technical definition in your context?

I suspect it's the same as what is usually called "well-ordered", but I'd like to be sure.

[weary tiger]

well ordered I suppose?

since meitar was talking about a minimum so yea

[quaint notch]

Yeah sorry

my bad

[coral parcel]

Can you give that definition?

[quaint notch]

Hopefully I'm translating right,
'Ordered relation' above A is a subset of AxA which is 1. reflexive. 2. antisymmetric. 3. transitive.
'Well Ordered set' - if < is 'ordered relation' and for each Subset B of A which is not empty, B has a minimum

my intuition is 2 should be well ordered, and 3 not

but really not sure about that, nor about proving that

[coral parcel]

That's right.

However, then when you write

1. has a minimum and thus sorted.
   you only seem to assert that A has a minimum, not that an arbitrary subset has it.

[quaint notch]

Yeah but can't I say that for each m,n m-1/n belong to Q and since Q is well ordered, our set is well ordered as well?

[coral parcel]

Q is not well-ordered.

The positive rationals don't have a minimal element.

[quaint notch]

Yeah right, my bad

[coral parcel]

Actually I take my "that's right" back. Ordering 2 is not a well-order either.

[quaint notch]

1 + 2 aren't well-ordered?

[coral parcel]

But ordering 3 is.

1 is a well-order. It's just your argument doesn't do all of the footwork of proving it.

[quaint notch]

oh, ok I'll give it a shot but would appreciate a hint in case I won't succeed 🙂
I'll ask later I guess

but according to you, final result is -

1. well -oredered
2. not well ordered
3. well ordered

[coral parcel]

Unless I suddenly discover I'm an idiot and have switched something around again, yes.

[quaint notch]

alrighty, thanks a lot!

I'll msg you later if it's ok 🙂
In the public chat

[coral parcel]

You can try; I may or may not be in a position to engage then.

[quaint notch]

of course

[quaint notch]

Just got no clue how to prove it, I tried taking, two numbers from a subset, say $m - \frac{1}{n+2}$ and $a - \frac{1}{b+2}$ but nothing to do with that

[vital dew]

meitar5674

[quaint notch]

also, can't I create some sequence that converge to some number but that number ain't part of the sequence?

[tidal tulip]

how can i read “iff” in the following sentence: a number n is even iff there exist k in Z such that n = 2k

is it correct to read it in the following directions

->
a number n is even if there exist a k in Z such that n = 2k

<- if there exist a k in Z such that n = 2k then n is even

eg A iff B

means if A then B

and

if B then A?

[coral parcel]

Convergence (in Q) is actually irrelevant here. You could take the sequence 3-1/10, 3-1/11, 3-1/12, 3-1/13, ... which converges to 3 which is not in the sequence -- but that doesn't matter: the set of numbers in the sequence has the minimal element 3-1/10.

The way we do it for (1) is that we get a nonempty subset S. Then we first ask: what is the smallest m such that some number of the form m+1/(2+n) is in S? And once we know that, what is the smallest n among those that go with the m we've already chosen. Then m+1/(2+n) is the smallest element in S.

This works because a - 1/(b-2) can only be smaller than m - 1/(n+2) if either a<m or (a=m and b<n). Either of those possibilities means that a - 1/(b-2) cannot be in S because if it were, we would have chosen different m and n.

(The 1/(n+2) offsets are always strictly smaller than 1, so it never affects the sorting of two elements with different integer parts).

[tidal tulip]

@coral parcel can you help me understand if and only if in the eben example above

[quaint notch]

Cool that’s settle this one

[coral parcel]

Yes. Or in other words: "n is even" and "there exists k with n=2k" are either both true or both false, no matter what n is.

[tidal tulip]

okay, awesome ty

[coral parcel]

For a definition it's more direct than that, though: "n is even" means "there exists ...", and that is why they always have the same truth value.

[oak notch]

How do you read this? This is under the topic "Indexed Collection of Sets"

And this?

[wide vine]

im confused what exactly does the inverse mod have to do with the standard mod operation

it isn't like the actual inverse of the mod operation is it?

like f(x) and f^-1(x)

Like I read the definition and I am just not really seeing the importance.

so like 8 mod 11 has an inverse of 7 because 7*8 mod 11 = 1

[coral parcel]

It is more 1/x but evaluated in modular arithmetic.

[wide vine]

I am thinking of an inverse like + and - or * and /

[coral parcel]

"multiplicative inverse".

Basically, division is "more often possible" on congruence classes than would seem if you just look at standard representatives.

When working mod 11 you can divide anything by 8 by instead multiplying it by 7.

[coral parcel]

Here S is secretly a function from I into some unspecified universe of set, but written with its input as a subscript rather than in parentheses.

[wide vine]

how does that work for non integer results. You are saying (x/8) mod 11 = (7*x) mod 11?

[coral parcel]

$\bigcup_{\alpha\in I} S_\alpha$ is the union of all the sets in the range of $S$; ${S_\alpha}_{\alpha\in I}$ is a verbose way to speak of either S or its range.

[vital dew]

Troposphere

[wide vine]

nvm that doesn't work :v

[oak notch]

I see

[coral parcel]

Almost by not quite. I'm saying we can make a division operator $\div_{11}$ that works on congruence classes instead of integers. So you don't apply "mod 11" to the rational number 3/8 = 0.375 -- instead you have $[3]\div[8]=[10]$ or $3 \div_{11} 8 \equiv 10\pmod{11}$ because $10\cdot 8\equiv 3\pmod{11}$.

[vital dew]

Troposphere

[coral parcel]

And $3\cdot 7 = 21 \equiv 10 \pmod{11}$.

[vital dew]

Troposphere

[oak notch]

Thanks, Tropo!

[wide vine]

what is a congruence class? Im just a bit confused because this was just kinda introduced right after ecludian algorithm and doing the whole mod stuff

but im not seeing any connection to that previous stuff

they just say Finding the inverse of a number mod n is a key step in the RSA cryptosystem covered later.

[coral parcel]

"Congruence class" is the conventional word for an equivalence class under the $\cdots\equiv\cdots \pmod{n}$ relaton.

[vital dew]

Troposphere

[wide vine]

and looks like they are discussing about private and public keys

[coral parcel]

Typically the inverse would be introduced after an explanation of how we can derive addition and multiplication operations on the set of these equivalence classes from addition/multiplication of the underlying integers.

It sounds like you have not seen that, though?

[wide vine]

Nope

[coral parcel]

Hmm, okay. Then you'll have to make do with a less fancy understanding.

[wide vine]

just learned about some basic mod aritmetic and the whole lcm and GCD

and prime factorization

[coral parcel]

For ordinary numbers "3/8" means "the unique solution to 8·x = 3", right?

[wide vine]

yeah

15 * x = 1, x = 1/15. is what I seen when I looked up normal "multiplicative inverse"

[coral parcel]

Similarly, in modular arithmetic we can speak about "the unique solution to 8·x == 3 (mod 11)", where of course it is only unique up to a multiple of 11.

Which turns out to be 10.

And the unique solution to 8·x == 1 (mod 11) is 7.

This operation behaves sufficiently like division that we declare it to be the way to divide numbers modulo n.

It turns out that a·x == 1 (mod n) will always have a unique solution if a and n are coprime.

Actually finding that solution seems to be postponed to "later".

[wide vine]

actually um

the solution they said was something regarding "extended ecludiean algorithm"

and the thing about The condition is that x has an inverse mod n if and only if x and n are relatively prime.

so I guess I have to do that

I just wasn't seeing the bigger picture of use but I think I got it

[coral parcel]

For RSA the context is that you need to find numbers d and e such that their product == 1 (mod phi(m)). The way to do that is to pick one of them out of thin air and then use the inverse operation to calculate the other.

[forest saddle]

This is a computer science question but I think it falls in the realm of discrete math

I got a different result than part (a) is trying to get me to prove and I'm not sure where I'm going wrong

[crude garnet]

how to do d?

[brave trout]

Hi what was used here to go from second to third equality?

[civic horizon]

i assume the base of your logarithm is e but it doesnt really matter

you can write $3^{\frac{\log n}{\log 2}} = \left(e^{\log 3}\right)^{\frac{\log n}{\log 2}} = e^{\frac{\log 3 \log n}{\log 2}} = n^{\frac{\log 3}{\log 2}}$

[vital dew]

Pappa

[hardy yoke]

"F is function from set X to set Y" (f: X → Y) And I have to write it formally in set theory. So I tried to write it as this, but I'm not sure if it's close to being correct? ∀x(x ∈ X → ∃y(y ∈ Y ∧ f(x) = y ∧ ¬∃k(k ∈ Y ∧ y = k))) (Something like, If x belong to X, then there exists y such that f(x) = y and y ∈ Y and then there shouldn't exist no other y = f(x)

[muted gate]

guys, can you confirm this for me? the height(P) of a poset \textbf{P} = (X, P) is just the largest chain in P? that is, the largest $C \subseteq X$

[vital dew]

texaspb

[muted gate]

the book I'm using defines height as "the largest h for which there exists a chain of h points in P" but I came to the conclusion that the height will just be the largest subset C of X, easier wording for me to understand

[little prism]

well the height is a number, a chain is a subset

if you say "size of largest chain" then yes

[muted gate]

yeyeye

should've been more clear

my bad

I meant the size

ok, thanks

now, what does it mean when I'm talking about the height of a particular element x of X?

[round sable]

Can someone help me with this

[muted gate]

I'm talking about this particular case where the author uses this as a way to prove the dual of dilworth's theorem, for more context: (I specifically don't get the part where he writes height(x) where x is in X.

don't quite get what he means with "let height(x) be the largest integer t for which there exists a chain[...]"

[little prism]

essentially how many other elements in P there are which are in a sense all "lower" than x and comparable to each other

not really sure how else to rephrase it

[muted gate]

ok! got it 😄

he just didn't specify this part

ty again!

[muted gate]

can somebody help me understand what this $x||y$ notation possibly means?

[vital dew]

texaspb

[hot canyon]

could be an OR symbol

[coral parcel]

From context it seems likely that "x||y in P" is a way of saying "x and y are incomparable".

^ @muted gate

[muted gate]

that would make a lot of sense

thank you

[light heath]

hello guys im doing a problem involving the n queens problem and the problem is asking using the compound preposition from example 10 construct a compound preposition that will give all solutions to the n queens problem if the queen in column one is in a odd numbered row

[next halo]

Hello, I wanted to ask if my notation makes sense. Like, is what I wrote readable and understandable, and enough proof? Not asking anyone to solve and see if its right, just if the notation is fine

[coral parcel]

Needs more words.

[stray reef]

but tropo don't you know real mathematicians make sure to use as few words in their papers as possible to maximize the amount of symbol-soup to be spilled on each page?

[lean stratus]

hello. I have some questions about induction if someone can point me in the right direction that would be great.
The sum of i^2 I from 1 to n is equal to (n*(n+1)(2n+1))/6
the first step is easy since we will asume that this holds true for n=1
it's the next step that i'm having issues with. I have the following:
the following is true for p:
sum{i=1, p; i^2=(p(p+1)(2p+1))/6}
now let's proov that this holds for p+1
sum{i=1, p+1; i^2=((p+1)(p+2)(2(p+1)+1))/6}
= sum{i=1, p; i^2+((p+1)(p+2)*(2(p+1)+1))/6}
we change out i^2 to the right hand side expression for p that we saw above

=(p*(p+1)(2p+1))/6+((p+1)(p+2)*(2(p+1)+1))/6
first of all am i right so far? and what should i do in order to make the left and right hand side of p+1 equal? i've tried but can't seem to make it work

[mild temple]

,,\sum_{i=1}^p i^2+\frac{(p+1)(p+2)(2(p+1)+1)}{6}

[vital dew]

vin100

[mild temple]

,,=\frac{p(p+1)(2p+1)}{6}+\frac{(p+1)(p+2)(2(p+1)+1)}{6}

[vital dew]

vin100

[mild temple]

take out the common factor $\frac{p+1}{6}$ in both terms

[vital dew]

vin100

[mild temple]

then expand, regroup and factorize the rest

[muted gate]

what does the notation $\textbf{2 + 2}$ mean when talking about posets?

and specifically interval orders

[vital dew]

texaspb

[coral parcel]

2 is order type of {a,b} with a<b.
2+2 is two such orders next to each other, that is {a,b,c,d} with a<b and c<d but no comparability between the two sides.

[muted gate]

oh alr

thank you so much

when I say it excludes, is it just meaning that it's not ordered by inclusion?

[coral parcel]

My immediate guess would be that "excludes 2+2" means there is no set of four elements that are ordered like 2+2 between each other.

The sidebar on https://en.wikipedia.org/wiki/Interval_order seems to describe the property in that sense too.

[muted gate]

hey thanks again

you've been really helpful

[lyric osprey]

hello, does anyone know when to use induction vs when to use strong induction?

[stray reef]

whichever's most convenient

strong induction is for when you need to refer to statements more than one step back, weak induction is for when you don't

[pastel hollow]

This book im reading is talking about a "linear" function f:R^2 -> R where f(0, 0) isn't necessarily 0. what does linear mean here?

[little prism]

maybe just affine?

commonly functions of the form ax+b are called linear in school

[unreal stump]

Yea probably affine,in context of engineering and such affine is what we care about ig

[light heath]

is this a valid way to denote x is in a certain domain?

[coral parcel]

No, it should be $\exists x,(C(x) \land L(x))$.

[vital dew]

Troposphere

[light heath]

this problem wants you to write the statement twice one for when the domain is people on your class and one where the domain is all people

why would I need to check C(x) if the domain is all people in my class wouldent that imply C(x) ?

[coral parcel]

Hmm, then perhaps what you want is $(\exists x \in C), L(x)$. A prose annotation with an arrow pointing to the quantifier is definitely not the way to do it.

[vital dew]

Troposphere

[light heath]

ah i see

thanks

ill correct this now

[coral parcel]

In either case $\exists x( C(x) \to L(x))$ is almost certainly not anything you want to write.

[vital dew]

Troposphere

[coral parcel]

I've written an exposition of why ∧ goes with ∃ and 🡒 goes with ∀, here https://math.stackexchange.com/questions/48161/in-classical-logic-why-is-p-rightarrow-q-true-if-both-p-and-q-are-false/4385559#4385559

[light heath]

but how would I express the statement if it applys only to my class but the domain is all people

[coral parcel]

I don't know which statement it is you want to express...

[light heath]

oh I see now

I totally messed up

if domain is all people

i should use a conjunction with C(x) to make sure they are in my class

[light heath]

their in general any statement

x has a shark

x cant swim

etc

[coral parcel]

I'll recommend the explanation I just linked to -- I wrote it such that I wouldn't have to keep typing it out here :-)

[light heath]

alright Ill read it, thanks

[trail stirrup]

hi guys, any idea to prove this equality :?

[stray reef]

@trail stirrup you could always try to do it by factorial-bashing if you're fine with an algebraic proof

[weary tiger]

best to do an induction

[little prism]

there is probably a smart way to see this as two ways of counting the same thing. but I'm not good at that type of argument

[pastel hollow]

how can i show that rs <= (r + s)^2 / 4?

[little prism]

multiply by four, rearrange to get something involving (r-s)^2

[pastel hollow]

ah nice

thank you

[lyric osprey]

this statement is incorrect right?

since the quantifiers for x and y are in a different order?

[coral parcel]

Yes.

[lyric osprey]

so for this set of review questions, I got

b) False since it should be less than or equal to

c) false since its all integers times 0 making it infinite

d) false since B and C could be different sets sharing some things with A

e) true

can someone verify if these are correct/ incorrect?

[obtuse lance]

why is e true

[lyric osprey]

because for both negative and positive numbers like for -1 to -5 or 1 to 5 the numbers on the edge always have the same remainder

idk how to make a formal proof of that tho

[coral parcel]

I suppose "remainder" needs to mean something that is always non-negative.

[lyric osprey]

yea

[coral parcel]

The question doesn't seem to say that the five integers are consecutive, though.

[lyric osprey]

oh shoot

youre right

[obtuse lance]

are you familiar with the pigeon hole principle concept? that's my hint to you

[lyric osprey]

kinda

[obtuse lance]

well how many distinct remainders can you have when dividing by 4?

[lyric osprey]

4?

oh so since you can only have 4 distinct remainders when dividing by 4, if you have a group of 5 numbers the fifth one has to be one of the 4 again?

[coral parcel]

Yes.

[lyric osprey]

do we consider 0 as a remainder tho?

[coral parcel]

Yes.

[lyric osprey]

ahh ok

[coral parcel]

Beware that the argument only works if, say, -5 divided by 4 makes -2 with a remainder of 3 (rather than -1 with a remainder of -1).

[lyric osprey]

since remainders are always positive right?

[coral parcel]

Depends on who you ask, unfortunately.

[lyric osprey]

but the rest of my answers are correct?

[coral parcel]

Yeah.

[lyric osprey]

kk, thank you!

[little prism]

Well, nonnegative

[gusty mortar]

How much computer science do you guys know because I’ve heard that computer Science is mostly just applications of discrete math?

I’m just asking out of curiosity, I don’t actually want help with computer science.

[nova furnace]

a wee lil bit

[coral parcel]

I’ve heard that computer Science is mostly just applications of discrete math
That's overstating it -- there are plenty of topics in CS that can't really be describes as "just applications of (any kind of) math". However, at many universities "discrete mathematics" is the name of a service course for CS majors, being defined as "whichever mathematics a computer scientist needs to learn if they're not taking other math courses", which to a certain extent makes the description self-fulfilling.

[gusty mortar]

@coral parcel What’s ironic is that this statement of “computer science is just discrete math” is something I’ve mostly heard from Math majors.

[unreal stump]

Computer science is mostly "designing stuff" like how you would design like a cpu etc. The finer details are what you care about and math is just a tool to do that

Study of algorithms came into existence because people in the 60s really sucked at writing code and the efficiency was horrible

[autumn ember]

That's just false. Computer science incorporates much more than simply architectural design.

[unreal stump]

Well computer science is also improving/optimising those designs no? What else can you have

Like we have advanced data structures because they make a particular operation faster

[autumn ember]

Sure that's a component of it

But to say CS is "mostly" architecture is just incorrect

Computation and information theory, for example, broadly have very little to do with specific computing architectures or paradigms

[unreal stump]

Ok fair point

[strange peak]

Totally clueless on this one, how should I think?

Same with this one

[obtuse lance]

use Euler's formula for polyhedra and the formula for sum of degrees of vertices relating to the number of edges, that's enough to determine everything

[strange peak]

V + F - E = 2 but the problem is I only have the faces in this formula

The degree formula you are talking about, which is that?

@obtuse lance

[obtuse lance]

you can write this sum in terms of the number of edges of the graph, $$\sum_{v \in V} \deg(v)$$

[vital dew]

Merosity

[strange peak]

Hmm, really need to read something about it, don't totally get it. Do you have any good explanation of it from a web page or so?

My thinking is that 8 nodes, 18 faces and 24 edges are the right one, is that correct or am I wrong on this one

[obtuse lance]

well give it some time to think about it first before giving up and looking up the answer

[strange peak]

not sure if im doing it right but getting b now if i'm interpreting your tips correct

9 nodes, 25 edges

@obtuse lance

[signal goblet]

Hey, I was wondering if anyone had any ideas for an algorithm that solves the problem while satisfying the O(n + m) time complexity requirement. I've tried many different approaches, and I don't really know what else I should try.

Question Context:
Each Bitcoin transaction, in its simplest form, has one
input coin and several output coins (see Fig. 3). The input coin is genuine in the sense
that it is spent by the transaction. This creates the issue of traceability for Bitcoin, that
is, the entire history of each coin can be traced, e.g., how it was created, split, spent, and
by which users, etc., which can sometimes be too revealing and undesirable for the users.
To make the cryptocurrency untraceable, it has been proposed that instead of using only
genuine inputs, the cryptocurrency wallet should also include other fake inputs so that
an observer won’t know which input is the genuine one for that transaction. We will
ignore the fact how this can be done technically and only focus on the mixing part where
genuine and fake inputs are mixed in the transactions to provide untraceability. Assume
that each coin can be used as a genuine input for exactly one transaction and that the
number of coins is the same as the number of transactions in the system.

Apologies for the two pics, its awkwardly placed between multiple pages

The problem is basically this:

I need to design an algorithm that can find a unique mapping for a coin (vertex Ci) to a transaction (vertex Ti), and it needs to output that mapping. If it cannot, just output an empty map or null ig (doesn't really matter - its language independent). So, to find a unique mapping I need to essentially find a vertex (can be coin or transaction vertex) that has one incoming edge (ignoring the edge directions), then follow that edge to the other vertex, then remove all edges from those two vertices, then find the next vertex with one incoming edge, follow that incoming edge, map those two vertices, and repeat the above process until all the unique mappings can be found.

Also, if the input isn't well explained, this is what the algorithm receives as input (using figure a as the example):

n = no. of coins/transactions
m = no. edges
two adjacency lists representing the bipartite graph's vertex and edge relationship

n=4: #coins = #transactions

m=9m=9m=9: #edges

Coins adjacency lists: [C1: T1->T2->T3, C2: T3->T4, C3: T4, C4: T1->T3->T4] (C1 corresponds to the index 0 in the array, etc.)

Transactions adjacency lists: [T1: C1->C4, T2: C1, T3: C1->C2->C4, T4: C2->C3->C4]```

As the question states, I can find a unique mapping in figure a), which is:
C1 -> T2
C2 -> T3
C3 -> T4
C4 -> T1

Sorry for the massive walls of text. Just wanted to explain it properly, so that it is easily (hopefully) understood. But yeah, this is mostly a computer science graph theory question. All I want to achieve is to write the pseudocode of the algorithm (which is bounded by, in the worst case, O(n + m)), so you really don't need to know much about computer science to do this one (except for the time complexity constraint), so if any of you more math-oriented people have a good understanding of algorithms and bipartite graphs, you can definitely help out too (if you wanted to ofc).

Any and all help would be greatly appreciated, because I'm pretty stumped and feel very close, but not quite. I can share the solutions I have come up with, but they are not in order O(n+m), hence why I'm not too sure how to approach this. Thank you :)

[pale epoch]

hm

thats a lot of text for little mathematical content

so you are given a bipartite graph and i think you want a good mathematical description of what it means to have a bad mixing

this can be described by a large matching im pretty sure

[signal goblet]

Well I wasn't sure what the right amount of detail was considering this is predominantly a maths based discord and not comp sci

[pale epoch]

a maximum matching

[signal goblet]

But yeah, its pretty much maximum matching

Except that it needs to be done in O(n +m) time

[pale epoch]

so the problem is how to compute a maximum matching in a bipartite graph

ye, sure

what the running time of your algorithm?

[signal goblet]

Mostly, except every vertex must be connected to at least another (so a coin must be connected a transaction - can't leave any out). It's also similar to the minimum edge cover problem (less well known).

[signal goblet]

Well, my most recent one is O(n^2)

The standard transform and conquer approach where you transform it into a max flow problem and use ford fulkerson's algorithm still doesn't cut it

[pale epoch]

this just means no isolated vertices, right?

[signal goblet]

I've read about 4-5 papers on similar problems, and I encountered one which was really interesting (interesting in the sense that it is similar to this one), but I don't quite understand it entirely - its on the maximally-matchable edge problem

[signal goblet]

Yep

[pale epoch]

you can assume this when solving maximum matching anyway

so this should just be that

no idea if a O(n+m) algorithm exists

[signal goblet]

Apparently it does

And I've tried so many damn things

And I'm just not even sure how to get it down to that

I just feel like nesting of some sort (in regards to looping construct) is a necessity

I can't imagine doing some processing in relation to the edges, then moving onto some more processing with the vertices

Then again, what the hell do I know man

[pale epoch]

hm

the best algorithm i know of does matchings in bipartite graphs in O(sqrt(V)*E)

[signal goblet]

I think I've seen that one before, on one of the papers I read

Perhaps a matching approach is the wrong take?

I've tried thinking of other ways outside of matching, but as expected, not much luck

[pale epoch]

but

i think you can model a matching problem as this

so if you can solve this you can find a maximum matching in a bipartite graph

[signal goblet]

Wdym by "solve this"?

[pale epoch]

your bitcoin problem

[signal goblet]

Like, if this problem is solvable, you should be able to do it via a maximum matching?

[pale epoch]

determining whether a mixing is bad

ye, if i can determine whether a mixing is bad i can determine a maximum matching in any bipartite graph (if one exists)

[signal goblet]

Only problem is how to determine a maximum matching in O(n + m) worst case 😔

[pale epoch]

i am unsure this is possible

my first guess would be this is a typo and should be O(n*m) lmao

then ford fulkerson or whatever would work (?)

[signal goblet]

I asked that at first and professor said no, it is O(n + m)

Either he's a genius, and I'm just too stupid, or he made a mistake and hasn't bothered to pay attention to it to realise

I'm putting my money on the former, considering his background

[pale epoch]

i dunno it would seem weird to ask that much in a homework problem

[signal goblet]

It's not homework

It's advanced practice questions

For our upcoming exam

We don't have to do them, but I wanted to and now I partially regret it because its stumped my confidence

[pale epoch]

maybe i dont see something in the original problem but to me it seems equivalent to maximum matching (with small extra conditions like both independent sets have same size and no isolated vertices, but i dont think this changes anything)

my next approach would be to look at problems/algorithms on bipartite graphs

see which run in that time

and check whether you can solve your problem with those

[signal goblet]

That's everything there is to see, next page is next question

Yeah I'll keep looking

[pale epoch]

i mean maybe im wrong about it beign equivalent to maximum matching

but i honestly dont think so

and in this case im not aware of any such solution in literature even

[signal goblet]

Well my luck so far is having me doubt that this is the way to solve it

Maybe there is a more naive approach that actually works better

[pale epoch]

ok sure but

say you have a bipartite graph

[signal goblet]

No yeah I agree with you

But, I just dont know anymore at this point

[pale epoch]

if the independent sets are not the same size, you add vertices so that they are

you give them maximum degree

and then interpret it as this bitcoin thing

then check whether mixing is bad, it gives you a maximum matching

you delete the added vertices and edges connected to it

this is now a maximum matching of the original graph

and the "extra work" is negligible

so you just solved maximum matching

so if another approach works, it also works for maximum matching

and i think maximum matching is very well studied

so this would be the way to go in my mind

[signal goblet]

Dude I think I solved it, right before I was about to throw in the towl. I used a combo of my previous algorithm and a system similar to djikstra's algorithm, and it seems to hold up really well and it is exactly in O(n + m). I need to prove it first and write the pseudocode to be certain, but I am very, very hopeful, but also in disbelief

I will keep you updated (if you're interested ofc)

I'm going to take a break now, since I've been at it non stop for past few days and its very late. But tmr, I will scrutinise it and flesh it out properly. I'm praying it is indeed the solution. Would be so satisfying

Thanks for all your help though man (it was great to get a second opinion), I really appreciate it ❤️

[pale epoch]

very nice

if you write it up, you can ping me

can you get feedback from your professor too?

[spring surge]

I cross two sets I get 3 subsets.
I cross three subsets I get 7 subsets.

In what way to approach this in order to make it general for any N sets?

[weary tiger]

i need a hint halp

Prove that in any group of 6 people, there are 3 people that know each other or 3 people that do not know each other. [In this problem we assume that knowing someone is symmetric, that is, if person A knows person B then person B knows person A.]

anyoneee?

[weary tiger]

cmon

plsplspls

[unreal stump]

So if 1 knows 2 and 1 knows 3 but 3 doesn't know 2 ,would that come under the "3 people do not know each other" case

[weary tiger]

right?

let me think about it

ye i would think so

[unreal stump]

I mean then isn't it obvious?

If you take the subgraph with any 3 points, it's either complete or not

If it's complete there are 3 people who know each

If not, there are 3 people who don't know each other

[placid mason]

No Drake your scenario didn't count

This problem essentially asks you to prove that a complete graph on six vertices always has a single coloured triangle when you colour the edges with 2 colours

Blue for don't know each other, red for know each other

[unreal stump]

I see

Right that makes way more sense

I don't know what I was doing

[placid mason]

Np at all

This is a very classical and nice problem

[weary tiger]

oh this is a graph problem

[weary tiger]

and how do we prove it

[placid mason]

You can start by considering a single vertex. There are a few cases: it has 3 red edges coming out and 2 blue, or 4 red and 1 blue, or 5 red (by symmetry we don't care about 2 red and 3 blue etc. since we can swap the colours if need be).

Get some paper and check out each of those cases. What goes wrong when you try to colour the other edges (pay attention to what edge colours are forced by each of these cases)

[weary tiger]

what about 5 blue

[weary tiger]

and what do red and clue mean

why are we considering this

can you elaborate?

[coral parcel]

Each vertex is a person. Red edge for "these two persons know each other", blue edge for "they don't know each other". Or vice versa.

[coral parcel]

You get that by swapping the colors in the "5 red" case.

[weary tiger]

hm

[coral parcel]

This kind of problems belong to Ramsey theory, and they get extremely difficult when the numbers become larger.

[weary tiger]

oh

[coral parcel]

"There are 43 people at a party. Are there necessarily 5 of them who either all know each other or are all strangers to each other?" Answer: nobody knows! If you manage to answer either yes or no, with work shown that checks out, you'll have a publication.

[weary tiger]

oh wow

@coral parcel

what next?

[coral parcel]

Consider the three points at the ends of the blue edges. Which colors can the edges between those three points have?

[weary tiger]

blue or red?

oh wait

they have to be blue

right?

[coral parcel]

If even one of them is blue, then you have a blue triangle.

[weary tiger]

how can we show one of them is blue

[coral parcel]

You can't. But on the other hand, if none of them are blue, then they're all red ...

[weary tiger]

oh right

[lyric osprey]

so a function has to be 1-1 to be considered a function right?

and a function will still be considered a function if it is not onto

[coral parcel]

No. Most probably you're misunderstanding what "1-1" means.

[lyric osprey]

so 1-1 and onto don't have anything to do with a function being a function?

only the vertical line test?

[coral parcel]

Right, they are properties that a function may or may not have.

[lyric osprey]

ahh I see

[coral parcel]

Together they can be considered a "horizontal line test", so if you have both, an inverse function will exist.

[pastel hollow]

I'm reading a book that says there is one labelled, connected graph with 2 vertices. How are there not 2?

if the vertex set is {a, b} and the edge set is {{a, b}}, then the functions defined by
f(a) = 1, f(b) = 2
and
g(a) = 2, g(b) = 1
are clearly distinct

[unreal stump]

well if you label 1 and 2. there is only one way to connect them

1 will always be connected to 2

all graphs obtained by labelling are isomorphic here

[coral parcel]

"Only one" must be interpreted as "up to isomorphism".

[pastel hollow]

No because these graphs are listed as distinct but they’re isomorphic

[coral parcel]

Apparently it's "up to isomorphism that preserves the labels".

And "only one" seems to require that a "labeled graph with two vertices" must have label set exactly {1,2}.

Then, however, your two examples are related by the isomorphism that interchanges a and b.

[pastel hollow]

i dont get this at all

[coral parcel]

An isomorphism of labeled graph is (apparently) allowed to switch to another vertex set as long as it preserves the labels.

So your example graphs are both isomorphic to the graph with vertex set {c,d}, edges {{c,d}} and labeling function defined by h(c)=1, h(d)=2.

Your two representations with f and g can be considered intuitively to be related by an isomorphism that "changes the vertex set from {a,b} to {b,a}".

[pastel hollow]

what does it mean for labelled graphs to be isomorphic

[unreal stump]

so if 1 is connected to 2,in the isomorphic copy, the vertex getting label 1 is connected to vertex getting label 2

[pastel hollow]

whatever im too dumb for math

[unreal stump]

This is how I understand it
so let's say I give a set of "connections"
Say I have {{1,2},{2,3}} 1 is connected to 2 and 2 is connected to 3
If a second graph also has the same set of connections, those 2 are the same graph

I guess can be seen as "same adjacency matrix" as well

[coral parcel]

IF a graph is (V,E,L) where E is a set of edges and L is a labeling function V -> {1,2,..,n}, then an isomorphism between (V1,E2,L1) and (V2,E2,L2) would be a bijective map f: V1 -> V2 such that for all x,y in L1 we have {f(x),f(y)} in V2 iff {x,y} in V1, and also L2(f(x))=L1(x).

[formal flicker]

Guys is the only way of answering question 11 is by using truth table?

[coral parcel]

No. Any proof system for the propositional calculus should work.

If truth tables are the only proof system you've learned, then that more or less settles which method to use.

But we can't know that, of course.

[distant bobcat]

Would a single vertex generally be regarded as a complete graph as it satisfies n(n-1)/2 number of edges which complete graphs must contain?

[coral parcel]

Yes. E.g. it's the first example at https://en.wikipedia.org/wiki/Complete_graph#Examples

[distant bobcat]

But would one view it as connected?

[formal flicker]

Like what are the other proof systems?

[coral parcel]

There are Hilbert systems, natural deduction, sequent calculus, equational theories for Boolean algebras, resolution, ...

I think that spells "never gonna give you up" in Georgian.

[pastel hollow]

no it's not, it's literally for math

[mighty dust]

one thing i find quite fascinating is, the sum of 1 over the nth prime increases logarithmically

that is pretty cool tbh

exactly

🤦‍♀️

[mighty dust]

one thing i am interested in doing, is seeing if there is a possible conjecture for prime numbers OTHER than the reimann hypothesis, and only one of them is true, if both turn out to be true, then they must be merged to to create an even larger theorem

[weary tiger]

Hello

can I get help with this

I don't understand how am I supposed to prove it

[mighty dust]

u talking to me?

[weary tiger]

me?

no I am posting my question to see if someone is available to help me with it