discrete-math

[keen flower]

no but im thinking of using using elimination

using contropositive

but im having hard time coming up with the contropositive

[spark field]

Well what is the statement in logical form

[keen flower]

for all real number r and s, radical r+s = radicl r plus radical s

[spark field]

Well I guess I should ask how you all usually find contrapositive

For us we usually write using variables for the propositions, so that once we have p -> q, we know the contrapositive is (not q) -> (not p) based on whatever p and q were

[keen flower]

ok

so

im lost

the radicals are messing me up

[spark field]

How about if I asked you this then

For all positive real numbers $a$ and $b$, $2ab \neq a + b$

[vital dew]

Coolempire93

[spark field]

Can you tell me what the contrapositive of this is

[keen flower]

ok maybe negating would be easier

[spark field]

(yes it will be)

[keen flower]

lol

nice

so basically there exists r and s, that radical s+r does = to radical r and radical s

[spark field]

Correct!

It turns out this proof is a one-liner

[keen flower]

i can think of 2 + 2

which is 4

wait

no no

[keen flower]

how so?

[spark field]

Ah no I read it as r^2 and s^2

[keen flower]

yeah

[spark field]

So work from here

[keen flower]

4 and 0

gets you the answer

any perfect square and a 0 does

i think?

[spark field]

0 isn't positive, thankfully

[keen flower]

brb dog barking

back

[spark field]

Like it says in the sheet, it's about algebraic manipulation

We want to show that $\sqrt{r+s} = \sqrt{r} + \sqrt{s}$ is a contradiction

[vital dew]

Coolempire93

[keen flower]

square both sides

[spark field]

Good

[keen flower]

btw lets get 100/100 on this cuz the last proof i did i got 80%

and hw is easy points haha

[spark field]

\begin{align*}
\sqrt{r+s} &= \sqrt{r} + \sqrt{s} \
r + s &= (\sqrt{r} + \sqrt{s})^2
\end{align*}

[vital dew]

Coolempire93

[spark field]

Then what

[keen flower]

right

damm

radical messing me up

[spark field]

Like I did here

Think about it as a and b

What is $(a + b)^2$

[vital dew]

Coolempire93

[keen flower]

(a+b)(a+b)

[spark field]

(In general when working with radicals we want to treat them as regular numbers)

[keen flower]

a^2 + 2ab + b^2

[spark field]

Nothing is special about radicals until we square them

Good

[keen flower]

ohh

so

radical r squares + 2radical r and s and radical s squared

[spark field]

\begin{align*}
\sqrt{r+s} &= \sqrt{r} + \sqrt{s} \
r + s &= (\sqrt{r} + \sqrt{s})^2 \
&= (\sqrt{r})^2 + 2\sqrt{r}\sqrt{s} + (\sqrt{s})^2 \
&= r + 2\sqrt{r}\sqrt{s} + s
\end{align*}

Very good

[vital dew]

Coolempire93

[keen flower]

right

[spark field]

What can I do now

[keen flower]

holy cow you're fast dude

radical r and s = that

rad r plus rad s = that

i think?

[spark field]

Hint: $r + s = r + x + s$

[vital dew]

Coolempire93

[spark field]

How can I simplify this equation

[keen flower]

subtract r and s

i think?

[spark field]

Exactly ✅

Don't get too focused on the radicals, the idea is always the big picture

[keen flower]

got it

[spark field]

\begin{align*}
\sqrt{r+s} &= \sqrt{r} + \sqrt{s} \
r + s &= (\sqrt{r} + \sqrt{s})^2 \
&= (\sqrt{r})^2 + 2\sqrt{r}\sqrt{s} + (\sqrt{s})^2 \
&= r + 2\sqrt{r}\sqrt{s} + s \
0 &= 2\sqrt{r}\sqrt{s}
\end{align*}

[vital dew]

Coolempire93

[spark field]

Now what can I do

[keen flower]

im kinda confused broski

[spark field]

Which part confused you

[keen flower]

i wish i knew

so basically

on the 2nd to last line

r+s = that

and u subtracted r and s right

[spark field]

r + s = r + something + s
so
0 = something

[spark field]

Yes

[keen flower]

ok ok i got it

[spark field]

Keeping in mind our final goal is to derive a contradiction

So we are just working through the expression

[keen flower]

right

[spark field]

Hopefully reaching something that can't be true once we reach most simple form

We are almost there

I have 0 = 2*radicals

What did you do when you had a radical on one side of the expression before

(the first step)

[keen flower]

squared it

[spark field]

Good 👍

[keen flower]

ohh so now we square everything

dude i wish u were my professor lmaoo

[spark field]

Basically, we're taking all the easy to think of steps here to simplify

so whatever feels natural

[keen flower]

ok

got it

[spark field]

0^2 is 0, how about 2sqrt(r)sqrt(s)

[keen flower]

4rs

[spark field]

Recalling that $(xy)^n = x^ny^n$

[vital dew]

Coolempire93

[spark field]

Good

\begin{align*}
\sqrt{r+s} &= \sqrt{r} + \sqrt{s} \
r + s &= (\sqrt{r} + \sqrt{s})^2 \
&= (\sqrt{r})^2 + 2\sqrt{r}\sqrt{s} + (\sqrt{s})^2 \
&= r + 2\sqrt{r}\sqrt{s} + s \
0 &= 2\sqrt{r}\sqrt{s} \
0 &= 4rs
\end{align*}

[keen flower]

https://tenor.com/view/chinchilla836-gif-16589048905580572153

[vital dew]

Coolempire93

[spark field]

This is about as simple as it gets, is there anything else we can do

[keen flower]

divide by 4?

[spark field]

Okay, and now we have 0 = rs

What does rs = 0 tell us about r and s?

[keen flower]

that either r or s is a 0

[spark field]

(We are at simplest form, so now we want to see what we learned from it)

Right

And what was the definition of r and s

[keen flower]

all positivie real numbers

[spark field]

.

Contradiction!

neither r nor s can be 0, so rs = 0 is impossible 👏

[keen flower]

so the original claim is true

[spark field]

Exactly 👌

[keen flower]

how would you write this as a proof though? i wrote a proof last time and this is what he said

wanna see?

[spark field]

In a proof, we have shown that $\sqrt{r+s} = \sqrt{r} + \sqrt{s}$ means that $rs = 0$, but that is impossible since both $r$ and $s$ are positive. Therefore we must have $\sqrt{r+s} \neq \sqrt{r} + \sqrt{s}$ for all positive real $r$ and $s$.

[vital dew]

Coolempire93

[spark field]

Sure

[keen flower]

wait ill dm you

[spark field]

Well, try formalizing the steps we've done into a proof and then I'll point out anything that I would change

[spark field]

It will follow this structure, essentially

[keen flower]

bet

[spark field]

just with all the details about how each step happened and why

Also since 4.1 was mentioned if that includes algebraic simplification I would follow the style used there

[keen flower]

its basically what we did i believe

[keen flower]

lemme know what u think

[spark field]

I suppose i'll annotate like your professor

[keen flower]

ahaha ok

[keen flower]

Shii

😭😭😭

What would u add

Im late for bed I'll work on it tmr afternoon

I appreciate your help as always broski

[spark field]

I just pointed out all the things that need to be clear

You have to imagine that someone who doesn't know the concepts is reading your proof

[keen flower]

Thats valid

[spark field]

They can't read your mind, so your reasoning for doing each step needs to be clear

[keen flower]

I hate this emoji

[spark field]

Why 😂

[keen flower]

My group chat spams it and there's smth odd about it

Hilarious though

Maybe cuz it depicts me doing math

[chilly cobalt]

Why do inference laws can be used to prove the statement below? like in this example

It kind of goes over my head

[spark field]

What do you mean by why exactly

[chilly cobalt]

I think it should be intuitive but it's just not intuitive for me

like, you take two premises, apply an inference law, and the implication is true

take another two premises and do the same

ohhh waaiit

[spark field]

Mmmm I would note that most mathematical intuition is only developed through practice, so you gain the ability to intuit through experience

ah maybe you just had that experience 😂

[chilly cobalt]

so

take any two premises and it's implication it's true right? do the same for any other two premises and it's implication is true, let's suppose the implications are s and r

since s and r is true, whatever comes from it must also be true, right?

[spark field]

Exactly

[chilly cobalt]

ohhh, so you can keep doing exactly that

[spark field]

I would be careful with the word "true" here (although it does mean what you intend it to mean)

But essentially

In any case where the premises are true, then what follows is true

(follow is the mathematicla word for what you are describing)

[chilly cobalt]

oh right

[spark field]

This is what allows us to apply a proof to any scenario

If [(p -> r) and (r -> s) and blablabla], then not p

The conclusion of the proof you gave

Probably the one time I would not use the implication symbol, and write if-then for clarity 😆

[chilly cobalt]

yeah right

and since the premises you took at the start are true and you end up with something that it's true then you end up with this right?

[spark field]

Yes, if the premises you took at the start are true, and you can show that that means that what comes after is true, you end up with something that is also true 👌

[chilly cobalt]

ohh, it all makes sense

just as they say "Take a nap and come back"

[spark field]

https://tenor.com/view/eureka-john-barrymore-the-invisible-woman-i-have-an-idea-a-ha-gif-18790999

[chilly cobalt]

fr My teacher just told us "just use it"

[spark field]

Yeah, that's the standard approach

[chilly cobalt]

the book just says "use it so you don't do large truth tables"

[spark field]

tbh usually I say that math is the art of not asking 'why' and just doing until you figure it out

[chilly cobalt]

Loool

fr

My intro to analysis class is just all

[spark field]

yep, as you work with more and more propositions truth table becomes too much

[chilly cobalt]

"figure it out on the problem set"

[spark field]

You end up needing smaller truth tables to figure out values to put in your truth table

Everything gets messy

[chilly cobalt]

maybe the keyword here was "logical implication"

and logical implication is that p->q is a tautology

oh lol

I don't know how to read

[spark field]

teehee

[chilly cobalt]

Thanks tho

[spark field]

No problem

[warm coyote]

How can i solve this?

[chilly cobalt]

that "y" means and

[spark field]

$\lor$ is or

[vital dew]

Coolempire93

[chilly cobalt]

oh it's an or

i thought it was y in spanish

$z$ $\iff$ $\not F$

[vital dew]

YuyuHenry

[chilly cobalt]

oh what

[spark field]

$Z \iff \neg F$

[chilly cobalt]

oh ty

[vital dew]

Coolempire93

[chilly cobalt]

$(Z \iff \neg F)\iff [(\neg Z \lor \neg F) \land (\neg \neg F \lor Z)]$

[spark field]

lor not or

[chilly cobalt]

oh okay

[spark field]

land not and

👍.

[vital dew]

YuyuHenry

[chilly cobalt]

let me try to solve it

by law of double negation $\neg \neg F \iff F$

[vital dew]

YuyuHenry

[warm coyote]

How can i derive it to f?

[scenic mesa]

looks like it has its own rule

[spark field]

me when I assume law of excluded middle but don't tell anybody

[chilly cobalt]

i got stuck here lol

[warm coyote]

Me too

[chilly cobalt]

wait

I misswrote the step 7

nah

mmm

I need z as premise

[chilly cobalt]

got it

want a hint?

what do you have

[warm coyote]

Really?

Wait

[chilly cobalt]

yeah

[warm coyote]

Oh it got erased

[chilly cobalt]

forget what I sent earlier

it ended up on nothing

[warm coyote]

Really i think i did the same thing

[chilly cobalt]

oh

[warm coyote]

Almost i think

[chilly cobalt]

you have the equivalence of the iff right?

[warm coyote]

Wait lemme solve it

[chilly cobalt]

okay

[warm coyote]

This is our latest attempt

Ughh

[spark field]

Okay I'm back

[spark field]

Reason why I hate working off of inference since this is clearly true

[warm coyote]

We tried simplifying it but it cannot be

[spark field]

If Z then you have a contradiction, therefore not Z and thus F

Let me see if I can apply rules of inference and simplify

[warm coyote]

No this is assuming all of it is true

[spark field]

Yes, that is assuming it is true

If Z then not F by (1) and if Z then not not F by (2)

[chilly cobalt]

Marked it as a spoiler for Arze, I have this after some time

it's my sol

[chilly cobalt]

from 5 and 3, you ca write 3 as the equivalence

[warm coyote]

Ohhh

[chilly cobalt]

and use a rule there

[warm coyote]

Damn never thought to use hypothetical

[chilly cobalt]

i was trying to use it all the time because of the iff and the equivalence of the proposition below

but took some time

[warm coyote]

Sighh

I feel so stupid doing all this

I was stucked on this single problem

[chilly cobalt]

I want to see coolempire sol

[warm coyote]

Btw what is equivalence of => we use different wordings

[chilly cobalt]

when you say if Z you're assuming Z is true?

this is the def

[warm coyote]

The professor said all of it is true

[spark field]

Yes

[chilly cobalt]

srry, I have the bad custom of writing => instead of ->

[spark field]

But Z cannot be true, therefore not Z and blabla

[warm coyote]

Ohh okay

[chilly cobalt]

bc of a mini logic course i took b4 euclidian geo

[warm coyote]

I thought it was a word or something

[spark field]

Regardless I'm writing via deduction now

[chilly cobalt]

okay

[spark field]

Unfortunately I don't have my nice package here that I normally write with

So I guess I'll have to write it the long way like you all

[chilly cobalt]

okay

if z then f, so f must be true, and z iff not f implies there's a z then -f which is false and then contradiction? so z must be false and then it all depends on the truth value of f?

[spark field]

So Z must be false, meaning that F is true since Z iff not F

But yes

[chilly cobalt]

and f must be true

oh right

[warm coyote]

Damn its l
Slowly pouring to me the realization

Thank you thank you

[spark field]

\begin{enumerate}
  \item $Z \iff \neg F$ \qquad Premise
  \item $\neg Z \lor \neg\neg F$ \qquad Premise
  \item $Z \implies \neg F$ \qquad (1)
  \item $Z \implies \neg\neg F$ \qquad (2)
  \item $\neg Z$ \qquad (3,4) by reductio ad absurdum
  \item $\neg Z \implies \neg\neg F$ \qquad (1)
  \item $\neg\neg F$ \qquad (5,6) modus ponens
  \item $F$ \qquad (7) double negation
\end{enumerate}

[vital dew]

Coolempire93

[chilly cobalt]

oh lol

[spark field]

It can definitely be written more elementary

but I am too far removed from fundamentals of logic

Last time I did this type of thing was 2 and a half years ago

[chilly cobalt]

are you in posgrad on logic?

[spark field]

In combinatorics

[chilly cobalt]

Goat

[spark field]

I would be interested in type theory but that's about as close to logic I'll probably ever get again

[chilly cobalt]

lol

[warm coyote]

You guys are the goat thank you again

[spark field]

haha yuyu did all the work, I'm just here to have fun

[chilly cobalt]

tbh I'd like homework like yours

this is my homework of dicrete math

look at the exercise

[spark field]

similar to our work

ah pero xq esta en español xd

[chilly cobalt]

Sí xd

let's keep it in english, but I use the english book because it looks better

[spark field]

real

[chilly cobalt]

I think a lot faster than I write so I have to keep editing comments lol

[spark field]

our participation activity

[chilly cobalt]

oh lol

where did that r come from

oh addition

[spark field]

homework

plus like 50 million activities at the end of each thing

[chilly cobalt]

oof

[chilly cobalt]

I feel like you can do this by looking at the numbers only

take the max of each number and then the answer will be most likely >= max

[spark field]

Yeah the participation activities are meant to be easy

[chilly cobalt]

0% in final grade?

[spark field]

Things we did in class, meant for you to learn from rather than game

[spark field]

I like like 10%, intended to boost your grade if necessary since you can get 100% in the category easily

[chilly cobalt]

oh that's pretty generous

[spark field]

But I mean if you choose to game it and not learn and then do worse later I guess that's the student's prerogative

[spark field]

Yeah

But our students are also stupid so

[chilly cobalt]

my teachers reduct points for punctuation in spanish

xd

[spark field]

typical

[chilly cobalt]

are u a teacher?

[spark field]

Speaking back from when I took the class

[chilly cobalt]

oh

that makes sense

leaving logic aside, I really hate generative functions

[spark field]

me when ésta and not esta:

[chilly cobalt]

frfr

[spark field]

Generative functions? 🤔

As in generating functions?

[chilly cobalt]

generating functions

I miswrote it

[spark field]

Why

[chilly cobalt]

do you care about whether it converges or not?

it feels like dark magic

[spark field]

@wicked bolt we have someone in need of convincing that gfs are good

[chilly cobalt]

frfr

[spark field]

As if abuse isn't common in a lot of math 😆

[chilly cobalt]

it's like doing combi the weird way, from a combi olympiad viewpoint

and making it an algebra problem about finding coefficients

[spark field]

But I think that the fact that some things have a native representation as generating functions makes it quite mathematical

I agree that working coefficientwise is feels ridiculous

[fossil mural]

...seeing that notification out of context my brain expanded the acronym as "girlfriends" instead of "generating functions" and i was so confused about what context could possibly have led to this message

[spark field]

But finding equivalences by gf is just math

[wicked bolt]

i don’t want a gf i want a bf

[spark field]

benerating function

[wicked bolt]

no

[chilly cobalt]

i mean yeah it kind of makes sense using generating functions, but most of the times is equivalent of working a problem with stars and bars in my experience

[spark field]

layla would have more to say about that than I can

[wicked bolt]

just wait until you see my white magic

[chilly cobalt]

show me

[wicked bolt]

i have to walk to my car

[chilly cobalt]

okay

this way of finding coefficients feels like dark magic

[winged delta]

The first 3 are just the binomial theorem, and 4 + 5 are classic series

[chilly cobalt]

and then defining the binomial coeff for neg numbers seems so weird

[winged delta]

6 and 7... now we're getting spicy!

[wicked bolt]

those are just stars and bars

[chilly cobalt]

the coefficients?

for like 6 and 7?

[wicked bolt]

why the equalities in 6 and 7 are true

well it’s (one reason) why 7 is true.

and 6 and 7 are consequences of each other

[spare slate]

[chilly cobalt]

The book says maclauring series

[wicked bolt]

that’s kinda cringe

[spark field]

I mean all basic gfs are just mclaurin series xd

[chilly cobalt]

I don't even know what that is

[spark field]

Calculus

[chilly cobalt]

I'm still doing integrals

haven't seen series and sequences

[spark field]

It's my quick trick on how I generate gfs easily in front of my classmates

[spark field]

should be next topic then

[chilly cobalt]

yeah, next topic on spivak

[wicked bolt]

it’s morally correct to do all this stuff combinatorially when working with generating functions

[spark field]

this is true

[chilly cobalt]

but like deducing the coefficients via combi?

[wicked bolt]

sure

[chilly cobalt]

mmm

letme think

[wicked bolt]

like for 7… ||the coefficient of x^i in 1/(1-x)^n is the number of nonnegative integer solutions to x_1 + … + x_n because each solution corresponds to a selection of one x^k term from each 1/(1-x). and that is findable easily with stars and bars||

[chilly cobalt]

like this right?

I wrote it in spanish, but the figure speaks Ig

[spark field]

Oh this is one I did the other day

[chilly cobalt]

so it's (n-1+j) C (j)

[wicked bolt]

i can’t read it but probably

[chilly cobalt]

I wrote: "Ways of adding j with the numbers from 1 to j-1 and each number can be counted n times as maximum"

oh, it isn't j-1

it's j

adding j

with numbers from 1 to j

[warm coyote]

Its really quite a headpincher to be honest but yeah our prof is such a sadist when it comes to math questions really tho goated

Slr i attended my calc class

[chilly cobalt]

I think I faked mine, why up to x_n?

[wicked bolt]

you’re multiplying n copies of 1/(1-x) together

[chilly cobalt]

but it's an infinite summ isn't it?

[wicked bolt]

sure

if n = 3 let’s say, how do we make a x^6 term?

we might multiply x^3, x and x^2 together

[chilly cobalt]

you split the 6 into 1's and the stars and stripes?

oh wait, yeah that doesn't work

[wicked bolt]

just think about all the ways you can take a term from each 1/(1-x) and multiply them together

you’ll find that the ways to make an x^i term is a stars and bars problem

[chilly cobalt]

oh right so it's a finite number of exponents that you have to check

[wicked bolt]

yea, if you pick something like x^m with m > i, you wont get an x^i term

[chilly cobalt]

yeah

so you can put split the number i into 1's and place the 1's into containers, n containers since you can choose n different x^{x_j}

and then that's just (n-1+i) C (i), because n-1 dividers and i stars

okay

seeing it like that it's fun

doesn't seem like dark magic anymore

what was the white magic you were talking about?

[hollow blaze]

Are "injective and surjective" and "has a two-sided inverse" (for functions between sets) equivalent without the axiom of choice?

If $f : X \rightarrow Y$ is injective and surjective, I want to define $f^{-1}(y)$ as the element in $X$ with $f(x) = y$, but I'm not sure if I'm allowed to do so without the axiom of choice

[vital dew]

bvghfgjfg

[fossil mural]

yes

the important thing is that it is the unique x satisfying f(x) = y (because f is injective)

[storm violet]

when you drop some conditions you begin to make choices

[fossil mural]

more concretely, the function $f^{-1}$ (using the coding where a function from $Y$ to $X$ is a subset of $Y \times X$) is just the set ${\langle y, x \rangle : f(x) = y}$

[vital dew]

bee [it/its]

[fossil mural]

this is a function from $Y$ to $X$ if for every $y$ there is a unique $x$ satisfying that condition, which is exactly what we have from the fact that $f$ is both injective and surjective

[storm violet]

for example showing surjective functions have (right?) inverses because u have to pick an element from fiber f^-1({b}). the statements u wrote should work under ZF though so aoc is unnecessary

[vital dew]

bee [it/its]

[fossil mural]

if you had multiple possible choices, that's where you start needing AC

although even then you can sometimes get around it by just coming up with some explicitly definable way to make the choices, for instance if the things you're choosing between are all natural numbers you can pick the smallest one

[hollow blaze]

thank you

[elfin crown]

why is every tree bipartite

ok ok this is trivial

start with any red or blue then switch it every time you make a new edge

[haughty garden]

you can basically pick an arbitrary root and then it forms a bunch of layers/levels; even layers/levels form one side of the graph and odd layers/levels form the other side

[elfin crown]

ok guys

imagine you have this infinite binary tree where each node has 2 leaves
what is the radius and diameter of this graph?

[spark field]

I assume both infinite(?) idk about the subject though just reading the definitions

I assume if you have a standard full binary tree with n levels then its diameter is 2(n-1) and radius is n-1

[elfin crown]

hm

[grand crown]

you can also use the stronger theorem that an undirected graph is bipartite if and only if there are no odd-length cycles, and a tree is acyclic by definition

[flat lintel]

What symbol is this ::=? I only know := which I think it's attribution, is it the same thing?

[spare slate]

https://www.geeksforgeeks.org/compiler-design/bnf-notation-in-compiler-design/

[patent marlin]

is this for the most part correct

[spark field]

for the most part yes

[snow hamlet]

In my class our proofs are purely symbolic

idk if thats strange or not

[robust thunder]

Is this all good, specifically for proving transitivity, or could I do it better?

[spark field]

Looks like it should be $v \leq v$ for reflexivity

[vital dew]

Coolemπre93

[spark field]

For anti-symmetry, it should also be stated that $x < u$ and $x = u$ (and vice versa) are incompatible before we can throw away the $x < u$ and $u < x$ cases

[vital dew]

Coolemπre93

[spark field]

Otherwise you've only tested 2 out of 4 possible case combinations in your proof

The same applies for transitivity. What if $u < x$ and ($x = a$ and $y \leq v$)

[vital dew]

Coolemπre93

[spark field]

You have only shown what happens in 2 of 4 possible cases

[spark field]

Always be careful when showing things that have multiple pathways of occurring

[robust thunder]

So for anti-symmetry and transitivity, I have to show 2 more cases?

Let me give it a crack

[spark field]

Should be straightforward but yep 🙂

[robust thunder]

You're saying to state that x < u and x = u are incompatible. Why do we have those as cases for anti-symmetry, as I thought they are separated by OR?

[spark field]

You assume $(u,v) \preceq (x,y)$ and $(x,y) \preceq (a,b)$

[vital dew]

Coolemπre93

[spark field]

Who says that both have the same condition

We could have $(u,v) \preceq (x,y)$ because $u < x$ and $(x,y) \preceq (a,b)$ because $x = a$ and $y \leq b$

[vital dew]

Coolemπre93

[spark field]

Basically, choose u = 1, v = 2, x = 1, y = 3, a = 2, b = 1 and note that that case is not covered in your proof

You suppose u < x, okay well it's not that here so it's not that section of the proof, what's the other case

The other case you have is u = x and v <= y, and x = a and y <= b (at the same time)
Well the first half is true but x != a

But there's no other cases in your proof

Oh sorry that was the transitivity section

[spark field]

Actually for anti-symmetry you assume the same thing and go via the same route

I'll use variables to the propositions are clearer: Let $P: u < x$ and $Q: u = x \land v \leq y$, let $R: x < u$ and let $S: x = u \land y \leq v$

You assume $(P \lor Q) \land (R \lor S)$
Meaning that you have 4 cases to consider
$(P \land R) \lor (P \land R) \lor (Q \land R) \lor (Q \land S)$

[vital dew]

Coolemπre93

[spark field]

Basically we consider how we can have (1): $(u,v) \preceq (x,y)$ and (2): $(x,y) \preceq (u,v)$.
\newline

Here are the cases:
\begin{itemize}
\item Suppose that (1) is because $u < x$.
\begin{itemize}
\item If (2) is because $x < u$ we have a contradiction.
\item Otherwise (2) is because $x = u$ and and $y \leq v$. But $x = u$ contradicts $u < x$.
\end{itemize}
Therefore (1) cannot be because $u < x$
\item That means that (1) is true because $u = x$ and $v \leq y$.
\begin{itemize}
\item If (2) is because $x < u$ we have a contradiction with $u = x$
\item So that means that (2) must be because $x = u$ and $y \leq v$
\end{itemize}
So $u = x$, $y \leq v$ and $v \leq y$, i.e. $v = y$ and you are done.
\end{itemize}

[vital dew]

Coolemπre93

[robust thunder]

Thanks mate, that makes a lot of sense now that you put it like that

[spark field]

Glad to hear it

[spare slate]

I made yap

[spark field]

Yap indeed

To show that x has a y, it suffices to construct a y between them 😂

Almost as bad as "to show that objects A and B are in bijection, it suffices to define a mapping from one to the other and show it is bijective"

[flat lintel]

How do you people write cardinality? Like |A| or #A?

[little prism]

either works

[modest urchin]

i tend to see |A| more often and personally prefer it

[spark field]

I saw # for the first time when working with an older mathematician and it threw me off

But I like to use it when writing brackets

Because $|{a}|$ is weirder in my eyes

[vital dew]

Coolemπre93

[spark field]

Mostly for set builder notation and when the set is really wide

One element here actually isnt bad

$|{c \in SP : c^2 = -1}|$ I take a second to parse though

[vital dew]

Coolemπre93

[hexed axle]

quick question: does this look like n^{(-1) \frac{n(n+1)}{2}+1} to you guys? How do I read this correctly?

[spark field]

Evil

But I think it's a power

Because the bottom of the 2 is above the level of the +1 and the (-1)

,texsp ||$a_n = (-1)^n \cdot n^{(-1)^{\frac{n(n+1)}{2}}+1}+\cos(\frac{n\pi}{2})$||

[vital dew]

Coolemπre93

[spark field]

idk why my parentheses on the cos expanded in size

but that as opposed to

,texsp ||$a_n = (-1)^n \cdot n^{(-1){\frac{n(n+1)}{2}}+1}+\cos(\frac{n\pi}{2})$||

[vital dew]

Coolemπre93

[fossil mural]

${\cos}(\frac{n\pi}2)$

[vital dew]

bee [it/its]

[spark field]

I was gonna say maybe a mathjax thing but it's gotta be that in my preamble the ()s were made into paired delimiters

[fossil mural]

i think it's actually a side effect of the $\cos$, somehow

[vital dew]

bee [it/its]

[fossil mural]

$(\frac{n\pi}2)$, $\cos(\frac{n\pi}2)$, ${\cos}(\frac{n\pi}2)$

[vital dew]

bee [it/its]

[spark field]

that's weird because normal mathops don't do that

[fossil mural]

$\sin(\frac{n\pi}2)$

[vital dew]

bee [it/its]

[fossil mural]

hmm

[spark field]

,tex
\DeclareMathOperator{\cop}{cop}

$\cop(\frac{n\pi}{2})$

[vital dew]

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

[spark field]

oh right you can only do that in premable

useless

[fossil mural]

$\text{hmm}(\frac{n\pi}2)$

[vital dew]

bee [it/its]

[little prism]

iirc its the physics package

[spark field]

Okay that makes sense

[hexed axle]

thank you good sir

[cloud rampart]

physics redefines common operators like \sin to add auto parentheses (just specific ones, not user defined ones). you can access the unmodified ones with \sine, \cosine etc (or disable it entirely by loading with the notrig option)

[spark field]

$\cos x$

[vital dew]

Coolemπre93

[spark field]

[cloud rampart]

by automatic bracing i mean \cos(...) will act like \cos\left(...\right), same with other types of bracket like [] edit: [] is used as an optional argument for specifying powers

[hexed gust]

is there a name for the property of a predicate p where the collection of sets x such that p(x) is true is set sized?

basically predicates where {x in Set|p(x)} is valid

[spark field]

'set sized'?

[hexed gust]

you can have a set of the elements of that collection

[patent prairie]

"small"

as opposed to a proper class

[hexed gust]

yeah

[patent prairie]

useful criterion: p is small iff there exists a set x such that if x embeds into y, then ¬p(y)

(i.e. bounded cardinality)

[hexed gust]

so it would just be called a small predicate?

[grand totem]

More commonly you'd call a class small or large depending on whether that class is set-sized or a proper class. You might identify classes with predicates but you'll hardly ever see people call a predicate small or large in that manner

[patent prairie]

people usually use the word "class" to refer to a predicate that way

a class is defined as a unary predicate

so it's sorta a concept with an attitude

as they say

[grand totem]

The small/large terminology is a bit more common when working with universes. Probably the more common way to say that a class is set-sized is to literally just say "(...) is a set"

As in "the intersection of an inhabited class is a set" for example

[fresh siren]

Let (A) be the statement that the weight function is injective, and (B) that there is a unique minimal spanning tree. Does (A) => (B) or the other way around?

[spare slate]

A implies B.

[hexed gust]

how do you prove the cartesian product of any set with the empty set is the empty test

[spark field]

Did not know that

[quick folio]

no I was thinking of something else

[spark field]

Oh okay

[quick folio]

post your proof I want to see it

[spark field]

If you define the empty set as $\emptyset := {x : x \neq x}$ and cartesian product as $A \times B := {(a,b) : a \in A, b \in B}$ then you should be able to do contradiction

Suppose $(a,x) \in A \times \emptyset$. Then $x \in \emptyset$, so $x \neq x$ is a contradiction, therefore $(a,x) \notin A \times \emptyset$

[vital dew]

Coolemπre93

[quick folio]

it's enough to just say that the empty set has no elements

[spark field]

It's the definition our book gave as a 'formal' alternative

[quick folio]

yeah it is formal

[spare slate]

orz u

[spark field]

orz csp

[hexed gust]

thanks'

[snow hamlet]

nothing in empty set so nothing in A and empty set boom

[spark field]

Yeah that was originally what I was gonna suggest

But I particularly despise proofs like that

[snow hamlet]

question

prove syymmetric difference of three sets is associative

[winged delta]

Either draw pictures or grind through the definitions

[snow hamlet]

yea its a string of equalities

[spark field]

<@&268886789983436800>

[snow hamlet]

huh

[spark field]

Always an annoying proof

[snow hamlet]

A \ B = A intersect B abs complement I just use this and applied associative rule

[crude dirge]

Also there is an another way to prove it if you know what is a product of groups.

Build a bijection $f$ between subsets of a set $X$ and ${0,1}^X$.
$$
Y \subset X \mapsto (a_x)_{x \in X}, a_x = 1 \text{ if } x \in Y, a_x = 0 \text{ otherwise}
$$

It easy to see that $f(Y_1 \triangle Y_2) = f(Y_1) + f(Y_2)$ (addition is componentwise mod $2$). ${0,1}^X$ with componentwise addition is product of cyclic group. The group operation is associative

[vital dew]

Kratkost

[past rivet]

Symmetric difference is indicator function mod 2, bam

Together with addition mod 2 is associative

Oh right that’s what kratkost just said

[rocky kiln]

Whats a good way to intuitively understand probability in discrete? I want to apply it to games i play and the like for fun

[grand crown]

the main ideas to know for computing probabilities in games is

1. computing compound probabilities for independent events

2. computing probabilities of disjoint events

3. computing probabilities in uniform problems by counting

all you really need to compute probabilities is an understanding of conditional probability and how to compute and use it, but often times in games you deal with independent or disjoint events (or otherwise it's probably too difficult to compute the exact answer)

[white breach]

Hey everyone, I've been very confused lately, recently my teacher introduced us to the $F_p$ fields with them being generated by polynomial functions, because we are studying cyclic codes, but i cant seem to be able to build intuition on the way they work

[vital dew]

ɹǝʇʇnq ɐp

[white breach]

could anyone help me on that regard, please? :)

and the concept of generative roots feel kind of alien to me

[spark field]

These beat my ass over summer 😩

Are you interested in the code side or the finite field side

[white breach]

both tbh 😭

[spark field]

Trying to decide if I should try to explain or wait till someone more knowledgeable comes by 😅 maybe I'll wait like 8 hours or so and if no one answers you then I'll go through it

[little prism]

I hope you know the complex numbers

[white breach]

i do

[little prism]

you need to convince yourself that those are the same as doing the construction you have seen in your course

just with R and the polynomial x^2+1

we start with some field (R) and add a symbol i that satisfies the polynomial x^2+1

finite fields work the same way

[white breach]

okay that is confusing, because ive only seen the polynomial congruence applied to finite fields (aka $Z_2$

[vital dew]

ɹǝʇʇnq ɐp

[little prism]

we start with some modulo setting and add a symbol a that satisfies some polynomial

[white breach]

trying to grasp that concept around an infinite field seems way harder

[little prism]

you need to understand this sentence

finite or infinite field doesnt matter

you have some number system in which you can calculate stuff

and then you add a new symbol

which satisfies some law

and thats it

[spark field]

Im annoyed your teacher didn't make you learn the classic example of field extension

[white breach]

we've never seen field extensions unfortunately

[little prism]

you are literally doing field extensions

[white breach]

well, it was never presented to us that way

[spark field]

(This adding an element with the polynomial thing is field extension)

[little prism]

oh wait, or are you viewing cyclic codes as ideals in the ring F_2[x]/(x^n-1)?

polynomials also come up that way

same construction but different flavor

[white breach]

kind of i believe, tbf he gave us Z_2, and he made us create a field by giving us an irreductable polynomial, and making us build a new field around that polynomial

[little prism]

thats a field extension

you are extending the field Z_2 to a bigger field

[white breach]

that was never clear in my lessons

the way it was given to us: if $S \in Z_2[X]$ is of degree $d$, then $F_d$ is the field $(Z_2[X]/S[X],+,\cdot)$ with $2^d$ elements

[vital dew]

ɹǝʇʇnq ɐp

[white breach]

and also, $F_p$ is the field containing all roots of $X^p-X$

[vital dew]

ɹǝʇʇnq ɐp

[flat lintel]

How can I be better at this exercises from Book of Proof? Do I need to know formulas, how can I learn them?

[spark field]

Practice

And I guess seeing examples of how other people do them

Similar to how one gains intuition for loops in programming

[flat lintel]

But does the author assume I know formulas? (Where chatgpt reminded me of arithmetic progression and stuff)

[spark field]

Ish

You don't need to be super familiar with those things to do this

One can come up with ideas and try to match them to what they are seeing

If one knows those formulas, then yes it becomes easier

Likely a student taking a discrete/proofs class with have at least seen those ideas before starting that class (e.g., in grade school)

But this is also the first step into mathematical thinking, where you have to learn to think on your own, rather than simply using ideas that are laid out for you

The difference between your typical calculation math class (algebra, precalc, etc.) vs proofs based class

But yes, a few of these are up to recognition

[flat lintel]

Alright, I will try to think harder (Although I'm pretty terrible at it)

[spark field]

Hence why seeing how others apply their intuition is useful (since you gain "hammers", or techniques that you can apply to other version of the same problem)

If you'd like I can do 18 so you can see what I mean

[flat lintel]

How can I see that? I'm studying on my own

There's no others 🙁

[spark field]

Youtube, you can also ask questions here

[spare slate]

#fafo

[spark field]

Literally xd

[flat lintel]

Can you do 18 then, please? 🙂

[spark field]

Other types of the same problem as in

The way that 25 is done is the same as 26
Same for 27 and 28
18 and 21 are quite similar
etc.

Since the goal is to build your problem-solving skills 💪

[spark field]

Sure 🙂

To approach any problem, we have to look at what we're given and take note of anything we can

For 18, what I notice about the numbers is that they are all even

But they all seem kind of random, not like 17

So I'm thinking about what these numbers might have in common

I see 4 and 16, well 4 is $2^2$, and 16 is $2^4$

[vital dew]

Coolempire93

[spark field]

So maybe that is the pattern

Unfortunately 36 doesn't fit

It's not a power of 2

So I go back to thinking

I recognize that 36 is $6^2$

[vital dew]

Coolempire93

[spark field]

And 16 is $4^2$ fits right in between

[vital dew]

Coolempire93

[spark field]

Let me check my work now

0 squared is 0
2 squared is 4
4 squared is 16
6 squared is 36
8 squared is 64
10 squared is 100

It looks like I have a match

Now I just have to turn this into set builder notation

Well, how can I write my pattern down

This is where formulas come in handy

I happen to know that the even numbers 0, 2, 4, 6, etc. can be written as
$2k$, where $k = 0, 1, 2, 3, \dots$

[vital dew]

Coolempire93

[flat lintel]

Yeah, sometimes I recognize patterns but can't translate to a formula

[spark field]

Yeah, I would say learning about arithmetic progressions will help you for that (sometimes when learning one thing we realize that we have to stop and learn another thing)

Even when it's not strictly required, like here, it would make the process much easier

So finally, I have my answer, in set builder notation, our set is $${ (2k)^2 | k \in {0,1,2,\dots}}$$

[vital dew]

Coolempire93

[spark field]

Or, if you've defined the natural numbers (assuming they don't include 0), our set would be ${(2k)^2 \mid k \in \NN} \cup {0}$

[spare slate]

\mid 💢

[vital dew]

Coolempire93

[flat lintel]

I sometimes write $\mathbb{N}_0$

[vital dew]

Sparklymath

[spark field]

That works then

${(2k)^2 \mid k \in \NN_0}$

[vital dew]

Coolempire93

[flat lintel]

Thanks 🙂

[spark field]

Hopefully that helped, and I would say use our #❓how-to-get-help help channels over chatgpt whenever you can, since we can point you in more suitable directions (usually) to exercise your mathematical mind

Regardless as mentioned the way to get better at these is always practice, you can find set builder notation exercises online if you feel like you want more than what you have

Since set builder notation is important in math, good to get the hang of it

Arithmetic progressions also pop back up so no harm in reviewing/learning them now either

But yes

Time for me to run 😆/

[flat lintel]

When do I know if I start a sequence starts at 0 or 1?

n = 0 or n = 1 to try values

[little prism]

doesnt matter

you can always change the formula to switch between them

sometimes one of the formulas looks nicer

[flat lintel]

Yeah, I want the nicer formula

[willow owl]

Can someone explain strong induction to me?

[winged delta]

Sometimes just knowing the previous case is not enough - the proof is easier to handle if you can refer to all previous cases

So instead of the induction hypothesis being "suppose P(n) holds", it's the seemingly stronger "suppose P(k) holds for all k <= n"

I say 'seemingly' because strong induction isn't actually any stronger, in terms of what you can prove with it. It's called that because it feels stronger to work with

[past rivet]

It’s also nicely related to the principle of transfinite induction, which lets you generalise induction beyond just the natural numbers

[spark field]

<@&268886789983436800>

[white breach]

okay that makes everything so crystal clear now, thank you so much

crazy that i needed a few more things from galois theory to understand my undergrad class tho

[haughty gale]

if $f$ is a function defined by transfinite recursion such that it is strictly increasing up to an upper bound, is there necessarily an ordinal at which this upper bound is attained?

[vital dew]

lexi

[coral parcel]

If it is defined on all ordinals and its values are ordinals too and it is strictly increasing, then it cannot have an upper bound.

(This requires just that the definition is such that the restriction of the function to any initial sequence of the ordinals is a set, which is certainly the case for definitions by transfinite recursion).

Or does your function have real values instead of ordinals?

[haughty gale]

two clarifications, then:

• its values are subsets of a set
• for successor ordinals, F(k + 1) = f(F(k)) for a recurrence relation f(x)
• there is an upper bound U such that f(x) = x for all x >= U

[coral parcel]

There cannot be any function f such that

• f(a) is defined for all ordinals a
• f(a) is always a subset of some fixed set X
• f is strictly increasing

(Poof: let k be the Hartogs number of P(X), namely the first ordinal such that there is no injection from k to P(X). The existence of such a number can be proved without the axiom of choice. Now consider g(a) = f(a+1)\f(a) -- if f is strictly increasing then g(a) is always nonempty and all its values are disjoint; thus g restricted to k is an injection from k into P(X), which we assumed doesn't exist).

Oh wait, how does "its values are subset of a set" and "f(x)=x for all x>=U" even make sense together?

[haughty gale]

F is defined, for successor ordinals, through f: S -> S

where F(k + 1) = f(F(k))

[coral parcel]

That doesn't answer my problem. If f(x)=x for arbitrary large ordinals x, how can it also be true that all those x are subsets of some fixed set?

[haughty gale]

f is defined on subsets of a fixed set, as are F(k) for any ordinal k. F takes an ordinal and maps it to a subset

[coral parcel]

If f is supposed to map ordinals to subsets of your fixed set, then how does "f(x)=x in such-and-such conditions" make sense?

[haughty gale]

i think i can make myself clearer

give me a moment

@coral parcel Let $S$ be some set, and $f: \mathcal P(S) \to \mathcal P(S)$ a map such that $f(S) = S$ and for any $T \subset S$, $T \subset f(T)$. Now define $F(\lambda) \subseteq S$ for ordinals $\lambda$ such that if $F(\lambda + 1) = f(F(\lambda))$, and if $\lambda$ is a limit ordinal, $F(\lambda) = \bigcup_{\alpha < \lambda} F(\alpha)$. Is there an ordinal $\lambda$ such that $F(\lambda) = S$?

[vital dew]

lexi

[haughty gale]

i think i have a proof that this holds

[coral parcel]

I suppose you treat 0 as a limit ordinal, so F(0) = Ø?

[haughty gale]

yes

my idea is that you just pick an ordinal whose cardinality is larger than P(S) and show that you run out of distinct sets before you get to that ordinal

[coral parcel]

Okay, in that case I think you're right.

"Ordinal whose cardinality is larger than P(S)" is more or less what I said above too, so we're in agreement!

[haughty gale]

thank you!

[spark field]

<@&268886789983436800>

[lethal hearth]

When testing de Morgan’s law via truth table after p and q and potential r Does it Matter the order of the truth table?

[frail sage]

The two truth tables should have the same values for each variable to make it easier yeah

But all you technically need to check is that “for p,q both 0, is the entry in both tables the same?”

So as long as you check it that way it doesn’t have to be the same order, it just makes it clearer and easier to check

[coral parcel]

The order of the rows doesn't matter for the proof being valid, as long as you're sure you have all of them.
In a given class you may be expected to follow some standard order as a way of making sure you include all of the combinations.

Likewise the order of the columns; it should follow any classroom conventons set up locally, and otherwise just be systematic enough that it's clear to a reader what you're doing.

[harsh pendant]

$5={0,1,2,3,4}$

[vital dew]

YeetusDeletus5

[robust monolith]

You missed some bars somewhere

[odd heart]

No, it works

[shell yew]

There are probably better channels

But there's no good channel for this anyway

So I'm gonna ask

Is there any irrational number that is normal in all bases?

[little prism]

almost all real numbers are normal in all bases

but proving it for any specific one is hard

[shell yew]

how do you prove this

(And what is almost all in this case, cocountable?)

[little prism]

set of numbers that arent normal has measure 0

uses the borel cantelli lemma

[little prism]

(but is still uncountable)

[mystic dragon]

hi! im a little confused on where to start on determining validity for quantified statements
for example, idk how to determine if this argument is valid or invalid

i know the techniques for like argument forms with variables, just not statements and dont know how to proceed with this

[winged delta]

With exists statements, the thing to worry about is whether the objects you’ve been guaranteed are actually the same

[mystic dragon]

what do you mean by this?

im a little confused

[winged delta]

Suppose you know “there exists x such x is even” and “there exists x such that x is odd”

Do you know that they’re the same x?

[mystic dragon]

they arent the same x

[winged delta]

Right! There’s no guarantee that the x are the same

Same issue here

If the x in your hypotheses were the same, you could conclude q(x)

But there’s no reason they should be

[mystic dragon]

if i replace all the exists with for all, would the statement then become valid

[winged delta]

Good intuition :)

[mystic dragon]

arguments with quantifiers are too confusing 😭

[past rivet]

This seems to be a general issue with “dummy variables” right?

[winged delta]

Yeah on the one hand it's avoidable by saying "exists x" and "exists y" for different statements, at least when people are learning it

But in practice no one does this (for a variety of reasons), so it's a question of when the training wheels should come off

[past rivet]

One thing I’m curious about is how to deal with pedagogical issues surrounding dummy variables

[winged delta]

Trying to think about how I do it in lecture

I definitely work some examples like this, and emphasize exactly the above point. I also mention how, for the sake of notation, we often drop the domain of discourse, but we should be especially careful when there are different ones lurking about

[past rivet]

Right right

[winged delta]

I work carefully through "do exist and for all distribute over and/or/implies? And if the statements aren't equivalent, which directions actually work?"

Implies especially requires careful unpacking of what the dummy variables mean

[past rivet]

Oh could you explain more?

[winged delta]

Sure, I ask them to look at the statements "for all x, P(x) and Q(x)" versus "(for all x, P(x)) and (for all x, Q(x))"

And for exists, or, and implies

And and or are easy, and drive home how for all is like a big conjuction, and exists is like a big disjunction

[past rivet]

Oh this seems like a distinction between “internal” and “external” and, right?

[winged delta]

Implies gets gnarly, especially pinning down a counterexample

[winged delta]

Those aren't my usual framework, say more? I want to make sure I understand what you mean

[past rivet]

Ok so, say I have two propositions p and q

Each of these has a truth value, I can denote that by T(p) and T(q)

[halcyon nest]

I think the core issue is students have trouble discerning free from bound variables, even though they might have encountered numerous variable-binding operators like limits, integrals, summation. They just have a hard time with the concept of a variable having limited scope

[past rivet]

“External and” refers to taking the truth values first, and then ANDing them together

So T(p) AND T(q)

It takes two truth values, and spits out a truth value

On the other hand, “internal and” takes two propositions and outputs another proposition

So you have $p \land q$ as a single proposition, which has a truth value $T(p \land q)$

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

Of course, you have that $T(p \land q) = T(p) \text{ AND } T(q)$, but these are different operations

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

Does that make sense?

[winged delta]

Ahhh, yes!

[past rivet]

Maybe you know the same thing by a different name?

I’m not sure if “internal/external” are the usual adjectives for this

Here I’m borrowing terminology from category theory

[winged delta]

Who would have guessed XD

(When I tested quantifiers I did a "match the statement to its translation" involving "the eth program halts in time s". We cannot resist pulling from our favorite fields!)

[past rivet]

I think it was only very recently that I appreciated the two different kinds of “ands”

Another example of this is “entails” right

Given two propositions p and q, you can ask whether or not you can deduce q from p and the axioms and logical rules of your theory

I think this is $p \vdash q$ or something? And it’s a truth value

[vital dew]

Pseudo (Cat theory #1 Fan)

[winged delta]

I think I mainly use internal and, when I teach discrete. External would be, for them, when I discuss logic gates

Since there we're working with the values rather than the propositions

[past rivet]

This is different from the proposition $p \implies q$ and also different from the truth value $T(p) \implies T(q)$

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

For example p could be “the solar system has 5 planets” and q could be “the USA has 50 states”

In my case it doesn’t seem obvious that $p \vdash q$ is true

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

The solar system having 5 planets doesn’t seem to have anything to do with the number of states the USA has

But of course here $T(p) \implies T(q)$ at the logic gate level

[vital dew]

Pseudo (Cat theory #1 Fan)

[winged delta]

Oh I try not to let them worry about the paradoxes of implication - I mention there are other logics where we are very concerned about this sort of thing, but we stick with the logic gate level

[past rivet]

I see

[winged delta]

Maybe I should put an exercise about a truth table for an alternate notion of implication

[past rivet]

To be honest I feel like I still don’t fully understand the different senses of implication

$p \vdash q$ versus $p \implies q$ versus $T(p) \implies T(q)$

[vital dew]

Pseudo (Cat theory #1 Fan)

[coral parcel]

\vdash is usually not implication but derivability.

If you can derive q from p (and you trust your proof system) then p -> q had better be true as a matter of truth values.

On the other hand, simply p -> q being true in some model doesn't say much about which derivations your proof system allows.

[sick grail]

Oh this is where that question came from

[trim thicket]

im trying to find the inverse laplace of original but im stumped
the closest thing matching seems to be e^at cos(bt) but the problem is that the inverse laplace of this has s-a up top, which my left term does not

[spare slate]

Laplace transforms do not fall under discrete math. But note that to match with the result for $\mathcal{L}^{-1} \left { e^{at} \cos bt \right }$, the numerator of your first term should be $4(s+2)$.

[vital dew]

Civil Service Pigeon

[trim thicket]

im so stupid I didn't notice i posted in the wrong channel 🤦

[grand crown]

just to be annoying you can do fourier transforms on vertex graphs which are very cool but probably not the right context here

[slim delta]

(N.B. I’m in second year mathematics, and I haven’t read any material other than some introductions) Hello, I’m about to start work on a group project over the Easter holidays, and our topic is generating functions. We each need to write an individual section around 10-12 pages. I decided to do mine on the Z-transform. However,the definition of a generating function does not use complex numbers, as the z-transform does. I think i want to discuss the inverse z-transform and introduce contour intervals, before computing an example. My question is whether this will be out of scope?

My tutor signed off on generating functions and he said it was a suitable topic

[little prism]

well does your course know complex numbers and contour integrals etc?

if yes then it seems fine

[slim delta]

I’m a joint honours student, the work is suppose to be sort of in a textbook-style where we research a new area of maths

I haven’t covered contour integrals or discrete math in my course

[little prism]

well then thats a lot of things to cover in 12 pages

what are the others writing?

is this supposed to mean that one covers for example the basics on generating functions and the others can take that part for granted?

[slim delta]

Yes, apologies, the report is supposed to be a coherent whole piece, where everyone contributes their own chapter

There are 5 of us: 3 will introduce the topic of generating functions (or an aspect of) in their chapters and me and a fellow student cover an application each at the end

I am not supposed to repeat anything related to generating functions

[little prism]

well then I suppose it could work

do you have a specific example already in mind that you want to do?

[bright dome]

i love generating functions

[vernal wave]

Generating functions for combinatorics are pretty interesting, because in a way they're kinda just an index-tracking device. But then it turns out the properties they share with real polynomials is much more than you'd expect from that!

[deft stag]

hello im currently taking a discrete mathematics course im notreally struggling with understanding but rather with the structure of the questions and the slides material, the material seems repetitive and although I understand the concepts fundamentally I struggle with recalling the specific names of statements for example and also with application do you guys have any tips or helpful resources I can study or look at

[spare slate]

Have you tried looking #book-recommendations? For example, [here](#book-recommendations message).

[deft stag]

thanks! if you dont mind me asking did you take the course?

[spare slate]

I probably (...? idk tbh lol) tested out of my school's version of it.

[deft stag]

oh I wanted to gauge the difficulty of the course as im prioritizing other courses this semester and not really giving this course the time or enough time ig

personally I hate going to its lectures as its hard for me to follow along Ig i just hate theory and proofs 🥲

[obtuse phoenix]

Am i the only one who is scared with functions?

[frail sage]

can you elaborate?

[obtuse phoenix]

I am having some tough time with writing the interval notation of function. For range and the domain. Every conditions is changing, if i stick with one textbook other one is showing a different condition for the function

[frail sage]

you mean something like

f : [0, 1] -> [0, 1]

to mean that the function f is a function from the closed interval [0, 1] to the closed interval [0, 1] for example?

[obtuse phoenix]

Yes. For rational and log function its kinda hard to understand 🥹

[frail sage]

ahh yeah i get what you mean

[obtuse phoenix]

Each textbook have different reference

[frail sage]

thats true, but the good thing about that is that you can technically just pick whichever convention you prefer and use that

no one can tell you that youre wrong, its just annoying to see it in so many different ways when youre not yet able to clearly see that its the same thing written in different ways

[obtuse phoenix]

Technically for the understanding yes, but i am providing a exam on April 25 and i need a good reference as the the Q and A are gonna be MCQ🥹

[frail sage]

but whether you write that log is a function from (0, + infinity) to (- infinity, + infinity) or that log is a function from R+ (positive real numbers) to R (all real numbers) really doesnt matter

[frail sage]

ohh i see, in that case, you should probably find which book the exam is based on and follow that strictly

[obtuse phoenix]

They didn't provide a specific book instead they provide the syllabus only.

[frail sage]

does the syllabus use a specific notation?

[obtuse phoenix]

Sometimes yes and sometimes no 🥹 its for the Csca if you heard of it

[frail sage]

noo i havent, but it sounds tough from a quick google search

if you have enough time, id invest in being able to understand the fundamentals, because then it will only be a matter of notation (which intuition should be able to fill in)

[obtuse phoenix]

Only left with functions others are completed

[languid igloo]

Is there a name for the number of subsets of an n-element set whose cardinalities are congruent to k modulo m? (as a function of n, k, and m)

I was playing around with this function and found out some interesting things, including a closed form (for any fixed value of m). I’m wondering what to look up to find more results about it

[spark field]

I dont have an answer for you but this works out to $f(n,k,m) = \sum_{i = 0}\binom{n}{k+im}$ right?

[vital dew]

Coolempire93

[languid igloo]

Yes, that’s right

[vital dew]

Andrew Li

[languid igloo]

Obviously this is skipping a lot of steps. But this was an amazing thing to stumble upon, and I was surprised that linear algebra, complex numbers, and trig show up. (The latter two are because the matrix’s eigenvalues are complex, and some trig is useful to rewrite some complex numbers that appear)

[spark field]

Reminds me of the way fibonacci numbers can be calculated via a matrix, although much more advanced than my knowledge of recurrence relations

@wicked bolt may be able to obersve your problem

[languid igloo]

It’s exactly the same idea! The system of recurrence relations this uses is f(m, k, n+1) = f(m, k-1, n) + f(m, k, n), which can be seen through a bijection

[upper carbon]

hi, has anyone read the Introduction to the Theory of Computation by Sipser? I went through the introduction but the problems give me a headache, I've mulled over this one over a few days for example... Not that I solved the previous ones (though I can understand the solutions). Should I get something like a combinatorics textbook first?

Also, in another place I was told I should rather learn & understand algorithms rather than try to reinvent all of them myself. On one hand I feel like this could be applied to proofs, on the other I see people say you don't really learn problem solving this way.

[winged delta]

I don’t recall needing combinatorics until quite late in the book

But who knows how editions have shaken things up

Even then though, I would imagine you mostly need the definitions, more than a combinatorics book

Like here I might proceed by contradiction (or contraposition): if a graph has only small cliques/anti-cliques, it must be small

[upper carbon]

honestly I've got even less of an idea how would one go about doing it via contradiction. Does it have something to do with the pidgeonhole principle? If so I think I might just need to look into combinatorics first. I also do think I get the relevant definitions? The graph G is a pair G=(V,E) where V is a set of vertices, E is a set of unordered pairs representing the edges. Cliques and anti-cliques are explained by the question (& I already know that empty graphs & singular vertices count as both at the same time since I asked about it here). Now this let me figure out there is at most 2^n cliques (thus 0 anti-cliques) or vice versa. I managed to figure out this might have something to do with taking the base-2 logarithm but that's it

[winged delta]

Alright, I opened up Sipser and did not realize he gives the solution below the problem!

I would just read it carefully and make sense of it, I do not recall needing a tremendous amount of graph theory knowledge to make sense of the book (but I did last read it like ten years ago)

The word 'clique' does not come up again until at least 250 pages later!

[upper carbon]

so I'm probably better off with the approach of trying to figure out why a theorem is true / proving it, & if I fail to do so on my own for too long, then just trying to understand one of the already existing proofs? I'm aware I can look up the solution. My issue is the whole figuring out why the statement is true on my own, especially since I do see people assert you aren't "really learning how to do mathematics" by just analysing already existing proofs

[winged delta]

I agree with your philosophical stance in general, just not about this particular problem

Sometimes it is useful to read an example proof to get a feel for what is even going on, and sometimes it's better to struggle

I think this problem is in the former category

Since it has so little to do with what immediately follows

[upper carbon]

alright, thank you!

[winged delta]

Sure :)

[fossil mural]

yeah in general i think you have to balance between, like... coming up with the proof on your own can get you a deeper understanding of what exactly is going on, and is also useful practice for times in the future when you won't be provided solutions. but also it takes longer than just reading the proof, and sometimes it will take way, way longer, and you don't necessarily want to spend all of that time when you could just read the solution and move on to something else

i sometimes use an intermediate strategy: read the solution, then come back later once i only kind of remember it, and see if i can reconstruct it, with the weak memories providing some amount of hinting in the right direction but still requiring me to come up with most of it myself

or, along similar lines, you can just like, read part of the provided proof and see if that's enough for you to guess where they're going

[upper carbon]

got it, thank you as well; I take it then people (say math students) aren't necessarily expected to be able to come up with answers to every textbook problem on their own? I'm a very math-deficient biologist so I wouldn't know

[coral parcel]

If the author is presenting the theorem with an immediate proof, when I don't think it's necessarily fruitful to call it a "textbook problem".
This one is even in section/chapter 0, so it's much more likely it is meant as "here's an example of a clever result that motivates why the techniques we're going to develop are important/interesting" than it's "you should be able to figure this out".

[upper carbon]

i mean I had issues with some of the previous ones (cardinality of a power set) but got it, thanks

[coral parcel]

[On the other hand, I've never seen Ramsey's theorem proved, and I've only ever seen it quoted as "for sufficiently large n", so from that perspective stating the clique size as ½log2(n) in particular starts looking like a hint, which does make the statement feel like a challenge. :-) ]

[past rivet]

In set theory we have that $(A \times B) \times C$ and $A \times (B \times C)$ are distinct sets, but with an “obvious” bijection between them. At the bare-bones kuratowski ordered pairs level, how do I properly define this bijection?

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

Also, are there other ways people prefer to axiomatise finitary products than just repeated binary products

Maybe axiomatise is the wrong word, “model” might be what i mean

Or “encode”?

[fossil mural]

well if you start by just writing down the bijection explicitly without worrying about the coding

it's $((a,b),c) \mapsto (a,(b,c))$, right?

[vital dew]

bee [it/its]

[past rivet]

Yes

I think I’m not sure what I’m “allowed” to do when defining a function like this

[fossil mural]

...well tbh i don't have a particularly clear idea of what you're trying to do here

[fossil mural]

like by my standards this is just a valid way to define this bijection

[past rivet]

Hm

I thought i would have to do “f(x) = [something]”

Where x is an element of my domain

I guess, why am i allowed to “pattern-match” on the form of the input?

[fossil mural]

it follows from the fact that if $(a, b) = (c, d)$ then $a = c$ and $b = d$ (which is just one of the standard results about the Kuratowski pair)

[vital dew]

bee [it/its]

[past rivet]

Mhm, right

[fossil mural]

then you can prove from that that a relation of the form ${((a, b), \text{something}) : a \in A \land b \in B}$ is a well-defined function, because for any particular pair the choice of an $a$ and $b$ that gets you that particular pair is unique

[vital dew]

bee [it/its]

[past rivet]

Yes yes makes sense

So I guess that helps you define functions out of products?

[fossil mural]

yeah, because basically what we've proved here is that you can write something like $f(a, b) = \dots$ and get a function from $A \times B$

[vital dew]

bee [it/its]

[fossil mural]

or i guess you could also just view it as, we have the projection functions $\pi_1 : A \times B \to A$ and $\pi_2 : A \times B \to B$ and what we really mean by something like $(a, b) \mapsto (b, a)$'' is $x \mapsto (\pi_2(x), \pi_1(x))$''

[vital dew]

bee [it/its]

[past rivet]

Yes that would also work

Hm

And, would any model of set theory have “enough sets” to have one corresponding to this bijection?

[fossil mural]

in a sense the essential component is this, because if you try to define a function by pattern-matching on something that's not injective then it won't work, unless you additionally prove that your function respects the induced equivalence relation

[fossil mural]

yes

[past rivet]

I guess I’ve heard that sometimes you can have an “external” bijection which doesn’t work “internally”

[fossil mural]

$(A \times B) \times C$ and $A \times (B \times C)$ are both sets, so you can form the set $((A \times B) \times C) \times (A \times (B \times C))$ and then just take the subset of that of sets of the form $(((a, b), c), (a, (b, c)))$

[vital dew]

bee [it/its]

[past rivet]

Like how models can disagree about whether things are countable or not? Iirc

Mhm, right

[fossil mural]

that can happen but also nothing we're doing here is really the sort of thing where that would happen

like, all of this is entirely internal reasoning

[past rivet]

I see

I think I’ve been interested in these kinds of “encoding” questions recently

[fossil mural]

in general, even if from the outside a model looks messed up in various ways (like if it's countable), from the inside it looks like everything is fine and completely normal, because any normal mathematical argument will work if you do it entirely internal to the model

[past rivet]

Oh, interesting

So what kinds of arguments can’t be internalised?

[fossil mural]

...i guess just, anything that relies on assumptions that aren't true in the model?

like if you prove "if there is an inaccessible cardinal, then ZFC is consistent", and then you look at an arbitrary model of ZFC, that model might think that ZFC is inconsistent, because the implication "if there is an inaccessible then ZFC is consistent" does hold in the model but the model might not have an inaccessible cardinal

[past rivet]

In part this was inspired by this frame from a video I watched recently

https://youtu.be/EVwQsvof7Hw?is=aorzrzCQRnO3-L-D

[fossil mural]

or for an example that sounds somewhat less silly, you can prove that PA is consistent by observing that all of its axioms are true in N, but this argument can't be internalised into a model of PA because PA doesn't quite have a notion of "true in N" that's strong enough for this argument to go through

[past rivet]

The item labelled “1” was kind of hard to wrap my head around

It seemed to say that anything “externally” provable should also be “internally” provable

[fossil mural]

and indeed there are models of PA in which PA is not consistent, by the incompleteness theorem (PA does not prove that PA is consistent) and the completeness theorem (if PA + ¬Con(PA) is consistent, then it has a model)

[fossil mural]

...kind of but also not exactly

like that sentence in isolation isn't wrong but it's inconsistent with how you've been using "externally" in other places in this conversation

[past rivet]

Oh i see

[fossil mural]

more precisely it's saying that if you can prove something, then you can prove that you can prove it

[past rivet]

In what situation would that not be possible?

[fossil mural]

uhhh

well i guess if you had like, the theory with the symbols + and * and literally no axioms about them at all

then in this theory you can prove a statement like "everything is equal to itself", but you can't prove in this theory that you can prove that, because the theory is so absurdly weak

...but you're right that it's a very weak condition, that's kind of the point

[past rivet]

Does the reverse automatically hold

Like does Provable(“Provable(p)”) imply Provable(p)

[fossil mural]

for any reasonable theory of arithmetic, if you have a proof then you can prove in the theory that it's a correct proof by just, essentially, going through and checking

[fossil mural]

it does if the theory is sound

[past rivet]

I see

Is soundness an internal or an external thing

(I guess also I’m a little confused what external means here because it means something different to how i was using it before?)

[fossil mural]

...that's a sufficiently confusing question that i'm not sure how to answer it

basically what i mean by "sound" is just, a theory is sound if everything it proves is true

[past rivet]

Then i think what i mean is that

Can a theory tell whether or not it is sound

Or is that something you’d have to check outside the theory

[fossil mural]

(depending on the context you might want to restrict that to certain classes of statements - for instance a theory is arithmetically sound if every statement of first-order arithmetic that it proves is true)

[fossil mural]

by the incompleteness theorems no sufficiently strong theory can prove that it is sound

because if a theory is sound then it's consistent

[past rivet]

Oh i see

Hm

[fossil mural]

(because if a theory is both inconsistent and sound, then because it proves "false", it must actually be true that "false", which is a contradiction)

[past rivet]

Is there an internal statement called “Sound” or something which refers to whether or not the theory is sound

Iirc there’s one for consistency

[fossil mural]

well this gets into issues with not being able to define truth

but if you restrict it to a class of statements that the theory can define a truth predicate for, then yes

for instance in ZFC you can form the statement "every statement in the language of first-order arithmetic that is provable in ZFC is true"