discrete-math

[crystal harness]

Has anyone studied using this ? if you have, is it good?

[spark field]

I haven't but I think I've watched one or two videos and I recommended them to people

Regardless I like the guy, I think he's a good lecturer

[crystal harness]

I used to do number theory from him

a year or so ago

i liked em

[grand crown]

he gave an opening remark at my school for a conference

[spark field]

me when now we know where snowflake goes

[grand crown]

i have a photo with him LOL

[spark field]

as you should

[grand crown]

well i had my last assignment on friday so i basically dont go here anymore

:P

graduation is in a week ish though

[spark field]

ah so graduation on saturday

[crystal harness]

i have so much to study lmao its hilarious

i have to do calc 3, linear algebra and also learn latex and proof writing + some combinatorics before i go to college

[spark field]

I graduated yesterday

[spark field]

Why do you "have to" do all this before you go to college

[crystal harness]

High school or college?

[spark field]

It would be nice to have of course but why do you feel you need it

[spark field]

College

[grand crown]

me every summer trying to make up for my math debt cramming all my courses the previous semester

[spare slate]

me who has just embraced being behind everyone else ik

[crystal harness]

where I am (probably) going, they basically just throw Real analysis at you from 2nd semester, if i am not prepared I am gonna catch a back lol

[spark field]

real

[spark field]

ah like at mit and uchicago real

tbh idt all that is necessary for it but I agree it will definitely up your mathematical maturity

[spare slate]

I'm punching in my guess as CMI

[spark field]

and good that you're doing proofs first
those will certainly be necessary

[crystal harness]

Close, ISI

[grand crown]

tbh the best way to prepare for real analysis is by studying real analysis

not to say you have to be doing that but only if thats what ur worried abt

[spare slate]

damn I was going to guess ISI but dissuaded myself away from that for some reason

then again I was basically coin flipping so whatevr

[spare slate]

real analysis is a very good intro baby course for basic writing and stuf

[spark field]

Very true

I recommend advanced calculus by fitzpatrick for those with little background although there may be a better book

[crystal harness]

lol i kinda messed up my cmi exam but i might still get in but ion wanna go to chennai lowkey

[grand crown]

i think a broader sentiment i want to convey is that you should give every nontrivial math course 2 pass throughts

you dont have to pregame every class but you often will have a much better understanding of synthesis and the fundamental methods while revisiting

[crystal harness]

Lol its analysis from sem 1 itself, I wanna have some background at least before I get there

[spark field]

I always recommend that to my friends and they never do it 😔

[crystal harness]

Yeah for sure I just wanted to get a bit ahead cause I wanna give MMC and SMMC asw

[spark field]

But as someone who does 21 and 22 credit semesters regularly I think it's the only thing that kept me afloat

[grand crown]

yeah like def a good idea, just that you shouldnt be hesitant to just jump into material directly if you want to have an easier time, like csp mentioned real analysis is already a good proof-writing class

[grand crown]

this is so me

im kind of excited to leave though 😭

i feel like ill be more sad when im actually gone

but ill be in a new university in a few months anyway 💔

[spare slate]

all this orzness

me in the corner as a dumb first year:

[spark field]

my thoughts exactly

[spark field]

samesies

[spare slate]

being sentimental:

I've seen people in graduation clothes around campus for over a week istg lol

[grand crown]

omg i thought u were a senior too ur a baby

idk why i assumed that, i think i associate your username with coolempire's

[spare slate]

wtf

I deadass think I'm the dumbest freshman in my classes

dumbest as in I know the least content

algebra

[grand crown]

i think everyone thinks that tbh

freshman year is also kind of humbling

[spare slate]

as in all the freshmen in my real analysis class seem to know algebra other than me

I'm in my dum dum real analysis + abstract algebra phase but this too shall end

and then I need to take actual math

send prayers

algebra is also being postponed for another semester so um

[grand crown]

they probably do bc they pregamed 💔 but this shouldnt deter u

[spare slate]

time to be the dum one again

[grand crown]

i remember my first day in honors analysis everyone was arguing with the prof over results wayyy later in the book 😭

[spare slate]

I have friends that took grad courses 3rd sem and I was always avg in high school so I'm used to being bottom of the barrel lol

[grand crown]

thats valid but i think u should be a little kinder to yourself 😭

but u sound like ur gonna succeed a lot :D

[spare slate]

It's called being honest

[spare slate]

civil service pigeon: 10th percentile helpful

me being TA next sem may or may not go very well depending on what percentile of my quality I end up bringing

[grand crown]

i think it will!! TAing has been so fun and enriching for me

even for classes that i struggled a lot in 😭

[spare slate]

orz

[spark field]

real

[grand crown]

like when i took baby systems/os i felt like i didnt understand anythingggg and then i became a TA for the class and things clicked so much better when i started explaining topics to other ppl

it also made me a lot better at debugging

ofc thats a cs class and not a math class

but i think the experience is similar

minus the debugging

[spark field]

I was about to say I wouldn't dare TA OS but that's a lie

the concepts explain themselves really well (at least with a mathematical mind)

The problem was remembering it all for the test

[grand crown]

i was a lot more confident in prob but even then being a prob TA exposed me to a lot of new ways to problem solve and really solidified some ideas for me

[spark field]

(one thing I really like about tutoring)

I know the info and you're the one who has the test

[spark field]

real

[grand crown]

tbh systems felt very scientific to me which is why i kind of struggled bc i always felt like there was a level of abstraction i wasnt understanding but needed to dip into a tiny bit to fully comprehend what i was doing

i love math bc the abstractions are very explicitly laid out for you <3

i think it didnt help that our slides were kind of barren and the professor stuttered a lot

i love him though hes sooo kind and so knowledgeable on all of the quirks in comp arch and systems

[grand crown]

real LOL

[spark field]

sometimes I feel like this degrades my abilities which is why I started proving things on my own in the first place

but the structure and linearity of classes feels too laid out

and is certainly far fetched from how math is actually created

[grand crown]

i think abt this a lot

i think there's a lot of value in being able to work around ambiguity and still reach deductions, which is kind of not a thing in math compared to engineering/sciences imo

[spark field]

Indeed

and competitions are so specific to what they ar

I don't think they serve the purpose of truly developing that (not to say they were intended to, but that if one sees a need for such a structure, comp math isn't it)

[grand crown]

tbh i like putnam problems

but i think theyre more fun in untimed settings, i think puzzles are fun and illustrative in general

[spark field]

Yeah putnam seems good

more referring to traditional comp math

But yeah puzzles are good, every uni should offer a putnam class

[grand crown]

yeah but tbh i feel like at the high school level you arent really doing math anyway

or idk i do think doing competitions helped me a lot with pattern recognition

but i do think it gave me some vices too

[spark field]

<@&268886789983436800>

[boreal tendon]

Hi everyone, I was given a research report task at university to research some current AI models that answer to Graph Theory related questions not quite correctly, I would like to gather some information if any of you stumbled upon this problem, if so, can you please specify the problem that you were trying to solve, but the AI's answer was not(fully or partially) correct, thanks in advance.

[last quarry]

I was tossing up between putting this in discrete or category. If I should move, please let me know 👍:

Why do some (constructivist) mathematicians not consider the law of the excluded middle axiomatic? What's the (heh) intuition behind that?

[spark field]

The logic people in #proofs-and-logic I know have opinions on this as well, we'll see who responds here but I'm thinking of @grand totem specifically

Something something zorn useful system zfc somethingorother

[winged delta]

I am not a constructivist, but I am a logician by training, so I can give you my view on it.

My understanding is that since constructivists view proofs as generating specific outputs, excluded middle is a logical guess that is entirely unhelpful in doing so. Yes, one of them is true, but which? I have just introduced logical uncertainty into my proof in some sense.

I always think about constructive analysis - given the epsilon, one needs to produce the delta based on that epsilon, not just promise that it’s out there somewhere. What is it?!?

Excluded middle is very much an “I dunno, but it’s out there” kind of reasoning

[grand totem]

I think there's two perspectives on it, the historical one and the sort of "current day working constructive mathematician" one
The earlier proponents of intuitionism as well as some of its biggest figures (Brouwer obviously, but also Markov, Bishop and others) were certainly philosophically motivated by the fact that excluded middle (and its equivalents and consequences) is sort of an omniscience principle in a sense that David already hinted at. Excluded middle specifically giving a mathematician the ability to prove a disjunction without ever actually proving one of its disjuncts.
Now some of the history is a bit ugly and some of the people involved (Bishop certainly) were quite opinionated on what classical mathematicians considered to be obviously true, but in the modern day I think it would be fair to say that most people working in areas related to constructive mathematics aren't doing it out of spite for classical mathematics or because they're inherently philosophically motivated. Nowadays constructivism isn't really an ideology for the vast majority of people (there are some infamous modern day bashers of classical mathematics like Paul Taylor but they're few and far between), rather it's just an established branch of mathematics at this point (or an umbrella term for lots of smaller branches).
So now the question would be what motivates the modern day constructivist to work in constructive mathematics, and I think that's going to vary greatly on what kind of work that person is doing exactly. But chances are they stumbled into a field that just so happens to be inherently more constructive than classical, for example maybe they went down the programming languages -> type systems -> type theory pipeline etc.

[keen flower]

thank you for everyone that answered my questions 🙂 im glad to say i passed my discrete math class ahha

[last quarry]

Thank you @winged delta and @grand totem for the interesting responses. I'm not sure I get it yet though, so as follow-up:

First responding to Linksworth:
I'm very intrigued by your comment "excluded middle is a logical guess that is entirely unhelpful in doing so .Yes, one of them is true, but which? I have just introduced logical uncertainty into my proof in some sense." - from my naive perspective this comment almost doesn't make sense. To presume that a statement A must be true or false defines a binary truth relation for A. If A is not true, then by construction, it is false.

To give a concrete example, if I say A is the statement "3x^2 + 4 = 0 has prime solutions", then A can only be true or false. Indeed, the idea of there being 'kind of' a prime solution rings hollow.

So your statement about "introducing logical uncertainty" doesn't make full sense to me. Am I misunderstanding the situation?

Then to Neverbloom:
I loved your historical summary, but I'm also very interested in your programming languages comment at the end, because I almost feel like that's a bigger question in itself. In particular, if you're referring to what I think you're referring to when you're talking about type systems (I've done a bit of type-oriented programming for work but I couldn't call myself an expert on the topic) and I distinctly remember hearing someone talking about the maybe monad as an allegory for nonclassical truth systems. I don't know if that's true or not, but it seems to me that there's some relaxed definition of 'truth system' that I'm not aware of based on this. Does that relate to this problem of constructivism, and if so, how?

"I don't know if that's true or not" <- please don't call that a truth value 😭

[winged delta]

I think the analogy I gestured towards with existential statements is closer to how I'm thinking about it

Saying "for all epsilon, there is a delta" is, to a constructivist, much weaker (and thus disallowed!) than saying "for all epsilon here is how you find a delta"

Excluded middle is saying "there is a truth value", but it doesn't tell you how to find it

[last quarry]

Maybe I'm oversimplifying it then, but this whiffs of 'good proof hygeine' -- would it be fair to call it that?

[coral parcel]

What you want for the programming-language connection is first and foremost the Curry-Howard isomorphism.

[winged delta]

As a classical logician, that's what it would be. It's much more polite to give a recipe for delta if possible, sure.

Constructivists take this further and say it's not just rude to not do that, it's illegal.

[last quarry]

It's always Curry's fault....

[spark field]

Hello neverbloom I hope it was okay to ping you

[last quarry]

I see. And so the reason that the law of excluded middle is rejected is a consequence of this? I think I get it then.

Thank you for your help everyone, much appreciated. 👑

[winged delta]

Excluded middle, like the axiom of choice, is in this sense non-constructive, because it’s assuming something exists (a truth value, a choice function) without explaining how to find/build it

[grand totem]

I distinctly remember hearing someone talking about the maybe monad as an allegory for nonclassical truth systems
This is largely unrelated. The Maybe monad as it is implemented in Haskell is actually an inherently classical thing. Constructively, partial maps X -> Y are not classified by total functions X -> Y + 1 (indeed the assertion that 1 + 1 classifies partial maps into the singleton is equivalent to excluded middle)

[fossil mural]

from an internal perspective it's not exactly true that constructive logic is about intermediate truth values - constructively, the law of excluded middle isn't false in the sense that ¬¬(P or ¬P) is provable for all P

[last quarry]

Ok, that explains a lot of prior confusion then, thanks. What should I look to for a truly non-classical example in programming?

[grand totem]

I skipped over this earlier, but adding to what bee said, constructive mathematics doesn't reject excluded middle, it is merely silent about it and just doesn't assume it. Not only are some instances of excluded middle simply true, for example one can quickly prove by induction that m = n or m \neq n for every two naturals, the double negation of p or ¬p always holds even constructively.

[grand totem]

I think your best bet would be to follow Tropo's advice and read up on the Curry-Howard isomorphism

[fossil mural]

...this is maybe a slightly weird example, but consider this: can you write a function of type ((a -> b) -> a) -> a?

[coral parcel]

Yeah, I call it ||call-with-current-continuation||.

[fossil mural]

we can prove by case analysis that there is at least one value of this type: either there is some value of type a and we can just use a constant function, or there isn't, in which case there is a function f of type a -> b (vacuously, because there are no possible arguments to such a function), so we can just use \g. g f, because g is of type (a -> b) -> a so that works out

(this corresponds to the fact that ((P -> Q) -> P) -> P is a classical tautology)

but this doesn't help at all with writing a single polymorphic function, in actual code, that works for any a

[coral parcel]

And even more primitively, there are always some sentences we can prove, and if p happens to be one of those sentences, then p or ¬p is directly provable.

[fossil mural]

(assuming you're working in a language that doesn't let you do case analysis on arbitrary types like this, which is most of them)

[coral parcel]

But if we try to apply that argument to actually writing functions in a programming language, then it becomes a problem that it seems to assume that every possible value has a closed term that evaluates to it (or at least that the hypothetical a does), which is not an obvious truth. So we may get in trouble even before we raise our ambitions to wanting a polymorphic definition.

[halcyon nest]

Even though Attelis is saying he objects to taking away LEM, my interpretation (and I could be wrong) is that he's actually objecting to taking away bivalence e.g. three-valued or fuzzy logic

[last quarry]

How should I distinguish the two?

Aren't they co-dependent?

(Not my wheelhouse so bear with me if basic q's)

[spark field]

<@&268886789983436800>

<@&268886789983436800>

[thorny hollow]

[fossil pawn]

Anyone good at ‘’Math logic’’?

[lofty cloud]

Asking the actual question right away is more likely to get responses.

Asking "Can I ask...?" or "Does anyone know about...?" doesn't give people enough information to decide whether they can help, and answering can feel like a promise to help with the actual question, which they might find themselves unable to.

[silent spire]

Guys I need to study Recursion and Modulo for my college end term exam and want theory content can someone please recommend a YT video for the same?
Or maybe even a YT channel that teaches Discrete Math that covers all the theory that I need then that is even better!

[neon pagoda]

Very dumb question, is there a way to prove chaos like the proof by mathematical induction method? As in, is there a way to prove that something cannot be mathematically predicted?

[winged delta]

Yes, since 'chaos' has a mathematical definition, generally meaning "a small change in initial conditions can lead to large changes in the output"

Prediction is thus not impossible, just impossible uniformly. Very specific initial conditions can be analyzed/simulated, but tweak them slightly and you may need a whole new analysis!

[visual solstice]

in the context of directed graphs with weighted possibly negative edges, are we subject to a sort of null-propagation effect where having one overall negative loop absorbs every reachable node into its -INF well?

like here, the only reason why c and d aren't -INF themselves is because there is no path from e or f to c or d

[fossil mural]

yeah pretty much

you can see in the example that g ends up at -INF, because it can be reached from the {e, f} negative-weight cycle

so you can just go around it as many times as you like to make the weight arbitrarily low, s -> e -> f -> e -> f -> e -> f -> [...] -> e -> f -> g

or from another perspective: we have d(s, f) = -inf and d(f, g) <= 7 (because there's an edge of weight 7 there), so d(s, g) <= d(s, f) + d(f, g) = "-inf + 7" = -inf

(obviously writing "-inf + 7" is a bit weird but you can check more carefully with the actual definitions that this makes sense - a distance of "-inf" means that for any integer N you can make the distance at most N, so if you want to make "-inf + 7" at most N, you make the "-inf" part of it at most N - 7, and it works out fine)

but since there's no way to go around the negative cycle and then get to c or d, d(s, c) is still 5, because that's the length of, in this case, the only path from s to c

no amount of going between e and f will let you then traverse the s -> e edge backwards or anything like that, you can get as much negative-weight as you want but also you're stuck in {e, f, g}

and similarly the {h, i, j} cycle is useless because you can't get there - if it was possible at all to reach that component, no matter how much weight it took, it would all have weight -inf because you could go around the cycle enough times to cancel it out, ...but you can't so it doesn't matter

or to phrase it in somewhat questionable notation, $\infty + -\infty = \infty$

[vital dew]

bee [it/its]

[fossil mural]

the unbounded negative weight that you can get from going around a negative-weight cycle is not enough to move along paths that simply don't exist

but any finite weight, for any path that exists, can just get absorbed into going around the negative-weight cycle an extra ten billion times or whatever

so yeah, anything reachable from a -inf will also be -inf

[spark field]

<@&268886789983436800>

[flat lintel]

Do you know any way of not forgetting any subset when I'm listing all subsets of a set? Especially if they are big

[slim geode]

If the set's size is n, then there are 2^n subsets, each set corresponds to one of the numbers 0, 1, ..., 2^n-1

So you can count from 0 to 2^n-1 and add a subset corresponding to each number, if you want a systematic way

[spark field]

If you're familiar with binary counting, then specifically the algorithm:

1. Assign every value in the set a place value (1 through n)
2. Count through all binary words of length n (just add 1 each time, and carry where necessary)
3. Write the corresponding sets, where a 1 means the subset contains that element, and a 0 means it doesn't

Is useful

Example: set is {A, B, C}

Since it's size 3, we count starting from 000:

000
001
010
011
100
101
110
111

If we say the first digit corresponds to A, the second digit corresponds to B, and the third to C, then all our subsets are

000 -> {} empty set
001 -> {A}
010 -> {B}
011 -> {A,B}
100 -> {C}
101 -> {A,C}
110 -> {B,C}
111 -> {A,B,C}

Another algorithm is to consider the subsets in order

1. Write all subsets of size 0 (emptyset)
2. Write all subsets of size 1 (every singular element)
3. Write all subsets of size 2 (go in order from the first element, and write a subset with every element to the right)
4. Write all subsets of size 3 (same as size 2 but fix 2 elements)
   ...
   n+1. Write all subsets of size n (the original set)

This one is more complicated but gives you a nicer answer to look at

An example would be

Subsets of {1,2,3,4,5}

1. {}
2. {1} {2} {3} {4} {5}
3. Fix 1: {1,2} {1,3} {1,4} {1,5}
   Fix 2: {2,3} {2,4} {2,5} (and because you only read to the right, you don't rewrite {2,1})
   Fix 3: {3,4} {3,5}
   Fix 4: {4,5}
4. Fix 1,2: {1,2,3} {1,2,4} {1,2,5}
   Fix 1,3: {1,3,4} {1,3,5}
   Fix 1,4: {1,4,5}
   (1,5 doesn't work because there is nothing to the right of 5 to use as the third element of the set)
   Fix 2,3: {2,3,4} {2,3,5}
   Fix 2,4: {2,4,5}
   Fix 3,4: {3,4,5}
5. Fix 1,2,3: {1,2,3,4} {1,2,3,5}
   Fix 1,2,4: {1,2,4,5}
   Fix 2,3,4: {2,3,4,5}
6. {1,2,3,4,5}

Generally for sets of the same size I prefer this to the first method

But if all you need to do is enumerate (and not look at the sets), the first method is better

[dusty matrix]

Given a 3D polytope such that every two vertices are adjacent, how can I show it’s a tetrahedron?

[worn wyvern]

In plane geometry the only shape where any two vertices are adjacent to each other is triangle

[cerulean ridge]

do you know how I would answer this on a test? Let A and B be sets. Show that A ⊆ B if and only if A∩B = A using set membership notation.

[spark field]

I assume set membership notation means use $x \in$

[vital dew]

Coolempire93

[spark field]

So for the A ⊆ B -> A∩B = A direction, equality between sets we usually prove by double inclusion

1. Suppose A ⊆ B and show that A∩B ⊆ A
2. Suppose A ⊆ B and show that A ⊆ A∩B

for the A∩B = A -> A ⊆ B direction,
Suppose that A∩B = A and show that if x in A, then x in B

[rare scaffold]

Show that the number of vertices with odd degree in a graph is even.

[spark field]

<@&268886789983436800>

oh it's gone

sorry mods

[blazing fern]

redirect me if this is the wrong channel

The last sentence is completely mystifying to me. Why would every neighborhood contain an infinite number of points from S? Does this have something to do with the definition of a “point of S”?

This is also a rather old book, for the record. 1970s.

[blazing fern]

I can elaborate on my confusion if need be, if it isn’t clear enough

[spark field]

This probably isn't the right channel but it looks like something I can respond to, so I shall take a look

Mmm well think about it this way

What if every neighborhood of z doesn't contain infinitely many points in S

What would that mean

[blazing fern]

To be clear, is a “point” of S just an element of S?

This might make it easier for me to answer

[spark field]

Yeah

[blazing fern]

Okay

[spark field]

nowadays we call it a "point in S"

It's probably helpful for you to know

a "point" is a word for a real number

so point just means number

[blazing fern]

I see

Very helpful

[spark field]

(It's an analogy from how in 2d, a point is a coordinate of 2 real numbers, in 3d a point is a coordinate of 3 real numbers, etc.

In 1d then, a point is a single real number)

[blazing fern]

Would you be able to say that S has a finite cardinality? I think this is what is confusing to me. If points are elements in S, doesn’t this mean that S would have to be infinite in size?

[spark field]

Yes, indeed a finite set cannot have limit points

But that's not the conclusion I want you to reach yet

What does not infinite mean

[blazing fern]

Empty or finite

[spark field]

Yep

So if there exists a neighborhood of z that does not contain an infinite number of points in S

that means that neighborhood of z contains a finite number of points in S

But because the number of points is finite, you can consider the closest point to z

between z and t there are exactly 0 points in S

-> z is not a limit point

contradiction!

I can write it more formally if that is hard to follow

[blazing fern]

If you wouldn’t mind

[spark field]

Suppose that $z$ is a limit point of $S$ but that there exists a neighborhood $(z - \varepsilon, z + \varepsilon)$ of $z$ that contains a finite number of points in $S$.
Call this set of points $T$, and define $T_{> z} \coloneq {x \in T : x > z}$ and $T_{< z} \coloneq {x \in T : x < z}$.
Since $T_{>z}$ and $T_{<z}$ are subsets of a finite set $T$, both of these must also be finite, and thus $T_{>z}$ must have a minimum element, and $T_{<z}$ must have a maximum element (they each also have the other, but those don't matter to us here).

Call the minimum element $x$ in $T_{>z}$ and the maximum element $y$ in $T_{<z}$.
Let $\delta_1 = x - z$ and $\delta_2 = z - y$, and let $\delta = \frac{1}{2}\min{\delta_1, \delta_2}$.
Then the $\delta$-neighborhood $(z - \delta, z + \delta)$ contains no points in $S$ other than $z$, contradicting $z$ being a limit point of $S$.

Therefore, if $z$ is a limit point of $S$, there cannot be a neighborhood of $z$ that contains a finite number of points in $S$; that is, every neighborhood of $z$ must contain infinitely many points in $S$.

[vital dew]

Coolempire93

[spark field]

Here you go 🙂

for the claims that a nonempty finite set must have both a maximum and a minimum:

Suppose a nonempty finite set A contains no maximum. Then for every x in A, there must be a y in A such that y > x.
You can continue this process of element-chasing infinitely many times; A must at least be as large as the set of positive integers

[spark field]

I guess as a note, if T_>z or T_<z was empty here, you could just disregard that set in the proof

one of the deltas doesn't exist so you'd just look to the other

[blazing fern]

Eureka

This is excellent thank you

I understand now

[spark field]

Perfect

So yes now we have the further conclusion

if S is finite, S cannot have limit points

and another fun result

if a member of S exists in every open interval of R, then every point in S is a limit point

(we call such a set "dense")

that should come up not far from now in your book

limit points are fun because they let us define what we mean by "open" and "closed"

It's funny that the term has to be defined after you already deal with the intuitionistic notion of open and closed invervals

only to find out that (-infinity, infinity) is a closed interval

[blazing fern]

Oh I see

chucking eggs at you goat

[spark field]

🪺

[wooden horizon]

this is a no, right?

please redirect me if this is the wrong channel, this is an example from our course slides without a solution so I just wish to check my answer

[prisma lily]

correct, there is no hamiltonian cycle

[wooden horizon]

thank you

[spark field]

<@&268886789983436800>

[lucid trout]

Whar

[void forge]

if i take the integers can i add a 1 like it becomes (....,-3,-2,-1,0,1,1.2,3,,,) can i do that?(the more general question is whether a set can have 2 identical elements)

[tall comet]

it cannot by definition

{1,1,1,1,1,1,...} = {1}

if I take Y subset X and take X U Y I get X again

[coral parcel]

In other words, the only thing a set remembers is whether or not each possible thing in the universe is one of its elements -- it doesn't have any idea of "how many times" something is an element.

[tall comet]

I always love the usage of "remember" in math

I think this idea is recurring but I didn't take any category theory yet to really understand

[coral parcel]

Even in category theory, my sense is that "remember" (and similar words like "forgetful") are just vibe words.

[dull briar]

discrete mathematics is fun

[tall comet]

i guess something like "natural" is also a vibe-y word even though there is a precise definition of natural transformation right?
Similar to how in category theory there is a notion of a forgetful functor but still "forgets" can be used in a vibe-y way

[tall comet]

correct way to study, I am going to do this with my scary measure theory book now

[coral parcel]

The existence of a precise definition means that "natural" is no longer purely vibey.
However, there isn't a precise definition of what it means for a functor to be "forgetful" (it's a relatively common pastime to try to come up with one, and then discover counterexamples where it fails spectacularly to match the vibe it was supposed to capture).

[tall comet]

oh I see, i didn't know it wasn't precisely defined

I just heard about it and assumed it was

category theory is weird

taking a course on it next semester though:D

[dull briar]

I like to draw smth on the book if it gets boring, it helps me :>

[lucid trout]

De morgans law mention

[jovial sail]

goated drawing

[spark field]

was scrolling up not sufficient

[tall comet]

<@&268886789983436800>

[tiny depot]

Idk if this is the right place for this

#1507084712139559102 message

But i posted about this in the help forum but apparently thats more for lower division college math

This may be better in #real-complex-analysis ??

[lucid trout]

!noads

[lofty cloud]

Please do not advertise your help channel or thread in other parts of the server. There are many people who need help, so advertising can quickly turn into spam.

[tiny depot]

I am trying to find a better place to ask this question

[lucid trout]

#real-complex-analysis might work

I mean just ask

[vital plover]

Let \alpha be countable ordinal, I want to find a binary tree such that [T^\alpha] \neq \varnothing and T^{\alpha+1}=\varnothing, ^\alpha here is the Cantor-Bendixson derivatvive. I can do this for \alpha = \omega, but I have trouble generalising it. Any hints?
The attached is the omega-th case

probably wrong channel

https://math.stackexchange.com/questions/2596284/cantor-bendixson-rank-of-a-tree-over-omega-possible-values-and-more

This is similar, but I can't adapt it to a binary case. I can't make the roots distinct node in the binary case so that the copy of each trees are disjoint. Eventually some of them will intersect...

[winged delta]

<@&268886789983436800>

[lucid trout]

binary trees are modpingable now?

[lucid trout]

For context this https://discord.com/channels/268882317391429632/1499325860904173650

[grim frigate]

hey

can anyone help me with math syndication

or can anyone provide videos explaining exercise or anything related i can check

[pine anvil]

isn't this Nazi flag?

[spark field]

No.

[spark field]

In any case #foundations might be better for actually getting an aswer to your question

[dull briar]

I find this funny idk

[grand crown]

yeah no = no
no yeah = yeah
yeah yeah = no

[dull briar]

yuh yuh

[wheat moon]

does anyone know any online courses for college cred where i can do discrete math

or are they all extremely expensive

[dull briar]

nope

[cunning plank]

community college

[wheat moon]

u think its too late to apply for summer

[cunning plank]

there might still be some stuff open

[ruby torrent]

logically speaking

[twin rivet]

im trying to break down n

[ruby torrent]

?

[twin rivet]

should i just contradict it

[ruby torrent]

I mean, what you wrote is clear enough

[twin rivet]

say if 2^n + 1 is not prime, then n is not prime something

[ruby torrent]

because it's a proof (or rather disproof) by counter example

you don't need a proof by contradiction for that

[twin rivet]

i can't just do that though like you said

i have to prove it logically

2^n + 1 = prime

anything 2^n will be even

[ruby torrent]

You have proven it logically though, the statement is saying something ALWAYS happens
and you showed a case where it doesn't happen
hence via counter example the statement can't be true

[twin rivet]

o wait

2^3 = 8 + 1 = 9

9 isn't prime

so 2^n + 1 isn't prime

[ruby torrent]

the implication is the other way o:

[twin rivet]

O_O

[ruby torrent]

If 2^n + 1 is prime, Then n is prime

[twin rivet]

tfw my alarm went off for early morning already

[ruby torrent]

what you disproved just now was:
If n is prime, then 2^n + 1 is prime

[twin rivet]

is there any other way i can present it logically or do i just say 4 is already a counterexample

[ruby torrent]

I mean, saying "2^4 + 1 = 17 is prime, but 4 isn't prime, so the statement is untrue" is a logical proof

[vocal sable]

What's the question ? :0

[quick karma]

@twin rivet have you covered truth tables and symbolic logic?

[ruby torrent]

Prove or disprove: If 2^n + 1 is prime, then n is prime

[twin rivet]

yA

[vocal sable]

Oh

Just go for mathematic induction proof ?

[ruby torrent]

no, counter example Dead. 😛

[vocal sable]

Oof

[quick karma]

the truth table for implies is

[vocal sable]

@ruby torrent is right tho , in terms of that logical proof

[quick karma]

so the only time an if-then statement can be false is when P is true but Q is false

[twin rivet]

idk my teacher is pretty anal about avoiding simple counter examples

[quick karma]

here P = "2^n+1 is prime" and Q = "n is prime"

so only n st "2^n+1 is prime" and "n is not prime" could be couterexamples

my teacher was the opposite

[ruby torrent]

@twin rivet I think your teacher wants a little more explanation than just 2^(4) + 1 = 17 done

[twin rivet]

LMAO

[ruby torrent]

to show you understand why you've disproved it

[twin rivet]

thats what i would do

[quick karma]

it doesn't matter how simple the counter example is, it still proves the point

[twin rivet]

so if i do p = f and q = f then p -q must be true

[ruby torrent]

wat

[quick karma]

yep

[ruby torrent]

oh, f as in false

xD

[quick karma]

but you want to show that it's false in general

[twin rivet]

2^n + 1 is not prime, then n is not prime xD

[quick karma]

there's a hidden quantifier

it's really forall n in N: [2^n +1 prime => n prime]

so the negation is exists n in N: [2^n+1 prime and n not prime]

[twin rivet]

let n E N | 2^n + 1 = prime for all n primes

[ruby torrent]

maybe it's wise going back through your lecture notes, and not moving on after each step until you've understood why? o:

[quick karma]

^

[twin rivet]

my walnut brain is half functioning

it is half a walnut

[quick karma]

go to bed then 😁

[ruby torrent]

but still xD

[twin rivet]

i mean i get a posibility i can do

do a truth table and then prove for every case of the truth table

is a possibilty

[ruby torrent]

uhh

[quick karma]

not here because it's for an infinite number of possible n's

[twin rivet]

it just bothers me

the premise is wrong from the beginning

2^n + 1 =! prime all the time

the whole substance of 2^n + 1 is basically
even + 1 = prime lol goteem

[quick karma]

sleep on it and come back in the morning

[twin rivet]

ok

ya its almost 4 am ooof

[ruby torrent]

https://www.cse.wustl.edu/~cytron/547Pages/f14/IntroToProofs_Final.pdf

[twin rivet]

ty for that @ruby torrent

will read in the morning LOL

[jovial stag]

How many functions are there from an n-element set onto
{0, 1}? (I think that the answer would be 2^n be the manual says 2^n - 2 so I'm a bit confused 😦 )

[quick karma]

2^n is the correct answer, they must be imposing additional contraints

oh

it's onto as in surjective

which means the range is equal to the codomain

so that rules out functions with ranges {0}, {1} or {}

and there are two such functions f(a) = 0 for all a and f(a) = 1 for all a

@jovial stag

[jovial stag]

ooh I did not think of this at all! Thank you, it makes sense!

[earnest oxide]

would this be injective, since Z contains the numbers ...-2,-1,0,1,2... ? or am i missing something here

[quick karma]

it's both

[earnest oxide]

because its also at least one right

so its also surjective

[analog sonnet]

The function is injective, but not because of the reason you mentioned

[quick karma]

yep

it's injective because the negative of an odd number is never an even number

[analog sonnet]

And you should explain better why it’s surjective too

[earnest oxide]

The function is injective (one-to-one) if each element of the codomain is mapped to by at most one element of the domain, which it is here because like you said a negative of a odd number is never even, and its surjective if at least one element of the domain, which it is here.

[analog sonnet]

Yep that’s proper

Good job

🍮

[earnest oxide]

thanks

[earnest oxide]

So I've done the first few p(n) out and an haveing trouble identifying a pattern to find the closed form

I'm wondering if anyone has any suggestions on how I can go about looking at this to start it, ie a hint

[ripe cave]

'using a method discussed in the course' ?

[earnest oxide]

Ignore that part.

[ripe cave]

that is a really difficult thing to come up with yourself

this hint might not be enough but try to find any sequence satisfying the condition on the right (ignore the starting conditions)

[earnest oxide]

Ok

I'll try

[twin rivet]

????

~ p ^ p = false?

i paraphrase the logic, as not p and p

[ripe cave]

yeah p and not p is false

[twin rivet]

how is the last step logically equivalent

not p ^ (not q v p) = ( not p ^ not q ) v (False)

[ripe cave]

x or false is the same as x

[twin rivet]

how i paraphrase:
(not p) and (not q or p) = (not p and not q) or false

so I suppose I just see, in the first statement
(not p [negation of p]) and (p) = (not p and p [ which is equivalent to false])

the first statement can be not p and not q

and it can be not p and p

guess that's right so im gonna write it down lmao

[hexed epoch]

Best resource to go over discrete math and combinatorics ?

[twin rivet]

da b00k

also lmaooooo

[hexed epoch]

We do not have a book actually

[twin rivet]

Prove or disprove: If 2^n + 1 is prime, then n is prime

uh idk to be honest sometimes i just google lecture notes from other universities

ay guys i wrote de answer xD b tell me if it sucks

[hexed epoch]

2^4 + 1 = 17

17 is prime

4 is not prime

False?

[ripe cave]

17?

[hexed epoch]

17* right

[ripe cave]

still prime

[twin rivet]

    n = 1   2^n + 1 = 3 true
    n = 2 2^2+1 = 5 true
    n= 3  2^3 + 1 = 9 false
    n = 5 2^5+1 = 33 false
 ``` idk thats my answer so far

[quick karma]

oh, good morning @twin rivet

[twin rivet]

ayyy

lmao

[quick karma]

the counter-example worked

it just seemed like you didn't know why it worked

[twin rivet]

yeah i really wanna know why it only works sometimes and not all the time

im not satisfied just finding a counter example

i dont think my prof will be either lol

[quick karma]

it's sufficient to solve the problem

once you find a counter example then you've proved that it's not true

[twin rivet]

even n=7 is false

[quick karma]

nooo

n=7 has to be true because Q is true

[earnest oxide]

@ripe cave yeah I'm still lost. Someone tried to help me with it and did it in a way we definitely didn't cover in class. They mutiplied by x^k, then did partial fraction decomposition

[quick karma]

take a look at the truth table again

P = "2^n + 1 prime", Q = "n prime"

when Q is true then P=>Q is true

[ripe cave]

@earnest oxide go to #help-9

[quick karma]

regardless of P

[twin rivet]

my tutor gave me a hint

he said because 2^n is even
2^n + 1 = odd
therefore it can't be divisible by 2 or any other even number

[quick karma]

your tutor sounds like he doesn't understand logic

[twin rivet]

lol yeah he answers pretty slow

he even said he is working on another paper hold up lmaooo

ok so

going by yours

P = "2^n + 1 prime" Q = " n prime"
you say when q is true then p->q is true

[quick karma]

yes

see:

[twin rivet]

but de problem is that p is not always true

[quick karma]

the problem is that sometimes P is true while Q is false

[twin rivet]

but by ur truth table

assume p is true, and q is true (original statement) then p->q is true

assume p is true, q is not true then p-> is false yes

[quick karma]

for a given n yes

[twin rivet]

but there are infinity ns

wait

no only prime ns are allowed

but depends on q is T/F

ok

assume p is false, let q be a prime number, p->q must be true

[quick karma]

yes but that doesn't help us at all

[twin rivet]

true

[quick karma]

and non prime n's are allowed

[twin rivet]

because some primes work and some don't
some nonprimes work and some don't

[quick karma]

that's how you find a contradiction

all prime values of n work because Q = "n prime" will always hold when n is prime

so the counter example has to be a case where Q is false,

ie where n ins't prime

[twin rivet]

wow so am i just overthinking this entire thing

[quick karma]

mhmm

[twin rivet]

that's the only way to approach this

counterexample where n is prime and doesn't work

[quick karma]

no such counterexample can exist

[twin rivet]

[quick karma]

no counter example where n is prime can exist

because then Q is true

and if Q is true then P=>Q is true

regardless of P

the only case that would be a counter example is some n st. ¬(P=>Q) is true

and ¬(P=>Q) = ¬(¬P \/ Q) = P /\ ¬Q

[twin rivet]

jeez

[quick karma]

in other words, you need to find an n st 2^n + 1 is prime but n is not prime

and any such n would serve as a counterexample

[twin rivet]

right

because if q (n is prime) is true, the truth table says it must be true regardless

[quick karma]

yeah

[twin rivet]

so let q be false, to find a way to prove p->q is false

[quick karma]

mhmm

[twin rivet]

ooo

and there is only

one way

by using a non prime

my gosh i get it now

thank you

[quick karma]

ding ding ding

awesome,

glad I could help 😁

[twin rivet]

300 iq

there are more far worse than this

eksdee

[quick karma]

haha, good luck

[twin rivet]

wait

w8888

[quick karma]

wott

[twin rivet]

so let the premise be true, let the q be false, p->q must be false rightttt

[quick karma]

yep

that's the only way p->q can be false

[twin rivet]

or are you proving that it can be true so p->q assuming it would be false, means it contradicts itself?

[quick karma]

no, the first one

[twin rivet]

i mean would the second one work too

because the truth table says it must be false but you prove it was true

[quick karma]

do you mean assume the claim's true for all n?

and then get a contradiction?

that would work as well

[twin rivet]

ooo ok awesome

[quick karma]

(although you'd probably only get to the contradiction via a conterexample)

[clear halo]

can someone help me out with linear combinations?

=tex write:the:vector:\begin{pmatrix}a\ b\end{pmatrix}:as:a:linear:combination:of:\begin{pmatrix}1\ 1\end{pmatrix}:and:\begin{pmatrix}2\ -1\end{pmatrix}

[earnest wigeon]

Command disabled

The sever owner has disabled that command in this location.

[vital dew]

swain:
Compile Error! Click the reaction for details. (You may edit your message)

[earnest wigeon]

@clear halo (swain#3798) was responsible for that message.

[clear halo]

Lol did i just get roasted

Fixed the formatting:

$ write:the:vector:\begin{bmatrix}a\ b\end{bmatrix}:as:a:linear:combination:of:\begin{bmatrix}1\ 1\end{bmatrix}:and:\begin{bmatrix}2\ -1\end{bmatrix} $

[vital dew]

swain:

[weary tiger]

whats the vector [ a b ]

[ruby torrent]

basically want to find coefficients (c1) & (c2) for [1, 1]^T & [2,-1]^T (in terms of a and b) such that (c1)[1, 1]^T + (c2)[2,-1]^T = [a, b]^T

I need to learn how to use LaTeX xD

[small ravine]

you basically need to find the inverse of the matrix whose columns are the vectors they gave you

[twin rivet]

ofug ofgfgusfgfg

i need help pls

on my final

Given any set of 30 integers, must there be two that have the same remainder when they are divided by 25? Write an answer to convince a skeptic who has learned about the pigeonhold principle but not seen an application like this one. Either describe the pigeons, the pigeonholes and how the pigeons get to the pigeonholes, or describe a function by giving its domain, codomain, and how elements of the domain are related to elements of the codomain

[twin rivet]

my tutor is really unhelpful

im not sure what he's trying to imply here

tutor just gave up and said for me to use the formal defintion of divisiblity

really unhelpful

[ripe cave]

but 0 is divisible by 5

so m-m is divisible by 5 for all m in Z

and so mRm for all m in Z

[twin rivet]

so it is reflexive?

[ripe cave]

yeah I'm almost sure it is

[twin rivet]

i have difficulty understand where x R y and x R z correlate to

z is the output of m-n? y is n ?

[ripe cave]

here we forget about m and n and use variables x, y, z instead

so x R y means that x-y is divisible by 5

[twin rivet]

what is the x and what is the y

m and n right?

[ripe cave]

x and y are any integers

[twin rivet]

it doesn't work for all integers

[ripe cave]

yeah, but that's the definition of the relation R

$xRy \Longleftrightarrow 5|x-y$

[twin rivet]

i see

[vital dew]

Gonzo17:

[twin rivet]

the relation is that x - y is divisible by 5?

where x,y are all integers

[ripe cave]

yes

we're just using different variables now

[twin rivet]

oooo

So apparently the symmetric definition is if x R y implies y R x for all x,y E A

[ripe cave]

yeah

[twin rivet]

is it basically saying that if i switch x - y, it will work for all x,y since they are elements of Z (all integers)

in that case that would be false wouldnt it

[ripe cave]

yeah and no

symmetry means that $xRy \Longleftrightarrow yRx$

[vital dew]

Gonzo17:

[quick karma]

(they're the same)

[twin rivet]

which they aren't really

[quick karma]

I mean the implies definition holds iff the if and only if definition holds for a given relation

[ripe cave]

$5|x-y \Longleftrightarrow 5|y-x$

[vital dew]

Gonzo17:

[twin rivet]

my mind is boggling about x and y being all integers, im thinking of different combinations where x - y will not be divisible by 5 and so the confusion

[quick karma]

you need to simplify it by not thinking of them as every possible number and just looking at their properties

like you do with an equation before you know the value of x

[twin rivet]

so if i look at it from the text, x-y and y-x are different

i wouldn't have any problems if it was x + y and y + x

[ripe cave]

yes x-y and y-x are not the same number

[quick karma]

yes gonzo is using the property that a | b iff a | -b

[ripe cave]

^

[quick karma]

and -(x-y) = y-x

so x R y => 5 | (x - y) => 5 | -(x-y) => 5 | (y - x) => y R x

[twin rivet]

ooh so it's not just looking at it, it's also adding properties ?

[ripe cave]

yeah you have to use properties of this specific R

[twin rivet]

I haven't seen the property a | b iff a | -b before

but you say it has to be specific to this R

[quick karma]

I hadn't either but it's obvious when you think about it

a | b iff exists c in N: b = c a iff exist c in N: -b = (-c) a iff exist c in N: -b = c a iff a | -b

[twin rivet]

oh right I see

a|b, you see b is (x-y) which is equivalent to -(x-y) where it fulfills the symmetric of flipping xRy and yRx

you just simplified it into a divisibility property of some sort

to see a|b iff a|-b

as the relation

so therefore because xRy imples yRx, it is symmetric as well

[ripe cave]

yes that's it

[twin rivet]

wow genius

oof now to transitive

what defines z?

i think we said y is just n, x was m, z is ?

oh right

z is the output of m-n

hmm

[ripe cave]

no, x y and z are random integers

and you're trying to prove an implication

[twin rivet]

R is transitive if x R y and y R z implies x R z for all x,y,z E A

oh right so x y z are just all integers, random integers

and im trying to prove... that x can be z, y can be z, and x can be y?

well I think because it is symmetric we know x and y can be equivalent to each other

im not sure about z, if z is a random integer where do it apply to the equation x-y

oh right

i think it is obvious that it is transitive

because x and y are proven symmetric

therefore z can be y or x right

[ripe cave]

no I don't think you get the concept

it's like > is transitive

because for any a>b and b>c

we have a>c

[twin rivet]

i saw an example on google images about adopting this with real equations

something about a = b, using b to solve for a then putting them equal to each other along the lines of that

like this

oh right

for any a > b, ( i think this was proven with symmetric property)
but to make b > c ?

c in this case is all integers as well?

we prove a > b, (x-y) can be (y-x)

idk my brain is just stumped by the addition of another variable that isn't defined clearly

[ripe cave]

ok let's go with just x, y, z

you assume $5|x-y$ and $5|y-z$ for some integers

and you wanna prove 5|x-z

[twin rivet]

what is z

oh wait

cant ask that sorry

[ripe cave]

x, y, z are any integers

[twin rivet]

i gotta look outside the box

x - y = y - z?

solve for that then equal to x - z?

[ripe cave]

no they aren't equal

you have to use properties of divisibility

[twin rivet]

if a|b and b|c, then a|c?

[ripe cave]

that's true, but not what we want here

[twin rivet]

for a and b, there exists a c such that b=ac?

owait wrote that worng

ok

[ripe cave]

I'm just gonna tell you the property we want is 5|a and 5|b then 5|a+b

for any integer a and b

and remember how before we had x-y=-(y-x)

now we have (x-y)+(y-z)=(x-z)

[twin rivet]

oh right

wow outside of the box thinking

so 5|a was (x-y)
5|b was -(y-x)

and because we assume x = z, just replace the x with z?

or something about replacing

[ripe cave]

no

this is in no way connected to replacing anything

[twin rivet]

it's something like making them equivalent to another and then ending up with a different formula or soemthing

[ripe cave]

look, we had given xRy and yRz

so 5|x-y and 5|y-z

so from the property I posted above

5|(x-y)+(y-z)=x-z

so 5|x-z

so xRz

[twin rivet]

wow im dumb lmao

xRy was x-y the whole time
yRz then becomes y-z

then do the divisibility property 5|(a+b) = c

assume (x-y) is a then (y-z) is b, to get c (x-z)

c is because in this case we wanted xRz

[ripe cave]

in here c would be x-z not z

[twin rivet]

so when we add it, (x-y) + (y-z) = (x-z)

then ya u got xRz

because xRy and yRz were used to imply xRz, and we got the answer right so it is transitive?

[ripe cave]

yeah it's transitive

[twin rivet]

lmao sorry if im a slow thinker

i can hear you probably inside your head liek "oh my gosh"

[ripe cave]

no worries

Glad to help 😄

[twin rivet]

you are a life saver to someone liek me

a brainlet

atleast i have finally come to realize the answer

after maybe almost an hour or two

ok i have

1 less question

1 more question*

Given any set of 30 integers, must there be two that have the same remainder when they are divided by 25? Write an answer to convince a skeptic who has learned about the pigeonhold principle but not seen an application like this one. Either describe the pigeons, the pigeonholes and how the pigeons get to the pigeonholes, or describe a function by giving its domain, codomain, and how elements of the domain are related to elements of the codomain

so am working my mind on this

i did something with mod25

i assumed array of 30 integers, and each number can go to [0-9] and you can have like tens or hundreds or thousands

so i say, the codomain is the 30 integers
the domain is 0-infinity because they are random integers

the pigeon would be pmod25 = r

uh let me draw it

i think this is accurate

[ripe cave]

you have 30 integers

[twin rivet]

ya and they are random

[ripe cave]

and you assign each one an integer from 0 to 24

so it's the other way around

the numbers are pigeons and remainders are pigeonholes

[twin rivet]

ooo right

let me draw it again

ooo

makes sense

right

so the codomain is 30

domain is the remainder?

and the relation is xmod25

[ripe cave]

that's the function

domain is the 30 random integers

and codomain is {0, 1, 2, ... , 24}

[twin rivet]

ooh right

[rocky girder]

hey can someone explain whats going on here

like i know to solve that but i dont understand the logic of the formula

[twin rivet]

fug

I have 1 more

this one is really hard

no homo

[pre-condition: product = A[1] and i=1]
while(i !=m)
1. i = i + 1
2. product = product * A[i]
end while
[post cond: product = A[1]*A[2] *...A[m]
loop invariant: I(n) is "i = n+1 and product = A[1] * A[2] ... A[n+1]" 

im gonna use this

ok here is my attempt i am stuck

1. {int (i)= 1, product = A[i]}
2. int(i)=1 ^ product= [A1] ^ i != m
3. idk

im so hungry

[twin rivet]

bruh im just gonna BS this

[viral stump]

3 turns into 6, 6 into 12, etc

[weary tiger]

guys, is there a way to do this without trial and error?

i got one value for d =2
but idk the others are getting messy
hoping there's some more logical sol than what im doing

[viral stump]

d=2 is a cycle and d=8 is total

hmm

d = 4 is a cycle plus another cycle inside that skips 1 every time

d = 6 is another cycle that skips 3 every time

suspecting the odd ones are impossible

[stable wasp]

Say I have equation A + B. I want to use AND gate instead of OR. (scarcity of gates)
Can I demorgan (A+B) by encapsulating double not with it, then do the demorgan?
((A+B)')' = A + B
(A'B')' = A + B

[viral stump]

yeah

[stable wasp]

Did it with proteus, but it outputs 1 at all 4 possible values

[viral stump]

check your gates

[stable wasp]

which then (A'B')' != A + B

[viral stump]

if a = b = 0, then a'b' = 1 and 1' = 0

[stable wasp]

thanks! FML no voltage at the 4th button. i thought i broke demorgan

[rough cosmos]

Hey all!

I need some help with this discrete question

Prove that the function f(x)=(8x+5) mod 17 is injective on the set {0,1,2,3,...,15,16}

[ripe cave]

Try assuming f(i)=f(j) for some i, j and see if you can lead to a contradiction

[white echo]

@rough cosmos

Remember 17 is prime so modular inverses exist

[craggy gale]

You can always bruteforce those kinds of questions tbh

[rough cosmos]

@white echo thanks

it not injective though right?

cause if x = 4 and x = 21 then they both will map to 3 in set

[ripe cave]

it's not injective in all integers

but it's injective in the set of residues modulo 17

[white echo]

Aren't you working in Z17?

[rough cosmos]

okay thanks

[rough cosmos]

on the set {0,1,2,3,...,15,16} means -> x can only be from this set right?

[craggy gale]

yea

You have to see f as

$\fun f{\bbZ/17\bbZ}{\bbZ/17\bbZ}x{8x+5}$

[vital dew]

Tuong:

[rough cosmos]

got it thanks

[rough cosmos]

Prove that for an integer X that is not a multiple of 5, X^n ≡ X^(n mod 4) (mod 5)

Any hints for this?

[craggy gale]

Do you know about Fermat's little theorem? @rough cosmos

[rough cosmos]

no

[craggy gale]

it says that for $p$ prime and $x$ integer,
$$x^p\equiv x\mod p$$

[vital dew]

Tuong:

[craggy gale]

It's useful here as 5 is prime

so $X^5\equiv X\mod 5$, i.e. $5\ |\ X^5-X$

[vital dew]

Tuong:

[craggy gale]

so 5 divides X(X⁴-1)

then Euclid's lemma

[rough cosmos]

This might be a dull question but I need to clear my basics, if 2^6 ≡ 2^(6mod4) (mod 5) that means 2^6 and 2^(6mod4) will have same remainder when divided by 5?

[craggy gale]

Yes

Well, that's what you want to prove

[rough cosmos]

thanks everything makes sense now

yeah

[gilded bloom]

Yo

Can someone help me with this WOP question

I've got it right

But I literally don't remember how I did it

Ignore part a

[ripe cave]

assume k is the minimum and try to prove that k-1 is also in C

[small ravine]

but it has indeed a minimum

and it is indeed non empty

🤔 🤔 🤔 🤔

it's namely {0, 1, 2, 3}

oh, it's restricted to n greater or equal to 4

if $$2^n>=n!$$
Then $$2^{n-1} >= (n-1)! \cdot n/2$$

[vital dew]

cardiou:

[gilded bloom]

I think I figured it out

I took out n knot from n knot factorial

Divided that by both sides

2 to the n knot -1 is greater then 2 to the n knot divided by n knot

So I plugged that in

And I think that should hold up

[rough cosmos]

How do I find modular inverse of (8x-5) mod 17?

i reached 1 = 17 - 2(8)

then 1 = 17 - 2(8 - 1*8)

i know that the inverse is (15x-7) modular 17

but don't know how to solve my equations further

[sweet eagle]

i thought i kn ew the difference between DFA and NFA,

but from this diagram mayeb i was wrong?

My initial assumption was that DFA's have unique paths only

[viral stump]

they do

[sweet eagle]

but what about state 0

1*

[viral stump]

what about it

[sweet eagle]

it can either choose 1 -> 2
or 1 -> 0

im jsut getting confused

[viral stump]

it has a unique move for each input

[sweet eagle]

oh

[viral stump]

NFA can have different moves for the same input

[sweet eagle]

ohhh

okok thanks lol

[viral stump]

its 7 choose 4

7 choose 4 has a meaning

n choose k means

n! / k!(n-k)!

look it up

it's an important quantity

yeah

[pearl leaf]

Hello, could someone help me with this problem?

[viral stump]

write all of them

correct denominators to what they should be

add them up

[pearl leaf]

alright I'll try once more

[viral stump]

you could add all of them

or notice that it's the complement of the ones with less than 2

yes

dunno

should be like

2^7 - 1 - 7

yeah

i mean

ive done math for years

[sweet eagle]

Encrypt the message ATTACK using the RSA system with n = 43x59 and e = 13, translating each letter into integers and grouping together pairs of integers.

i'm kinda confused on how to do encrpyption

and decryption

how would i start this?

i know that,
usually e is used for encryption

and if u want to send out a message, you normally would do n^e or something

[viral stump]

read how rsa works

and carry out the algorithm

[sweet eagle]

@viral stump oh

for every rsa question

you have to -1 and -1?

(p - 1)(q - 1)

or do the numbers change sometimes

[viral stump]

dunno I dont remember how the algorithm works

it's probably the euler phi

and for primes it's just -1

[sweet eagle]

ah

im reading it rn again

yeah i get it

thanksssssss

[viral stump]

im eating oatmeal naked on my bed

try it

it's kind of guesswork

the next term depends on the last 2

what common difference

it's not arithmetic

basically try to see how the sequence is defined

and put that in a formula

express it mathematically

and that will be the recursive definition

not geometric either

it's some recursive sequence

you gotta stare at it and find a pattern

yeah you gotta just

stare at it

lol

don't try to find a general formula

try to see how the next term is made

from the previous ones

[white echo]

@neon thorn As he said find a(n) in terms of a(n-1) and a(n-2) and then find the characteristic polynomial

[sage island]

.-. I really dislike these guesswork questions, as they aren't really well-defined unless the question tells you the sequence is of a specific form

[white echo]

If it's of the form a(n) = Ca(n-1) + Da(n-2). Where C and D are constants isn't it always a quadratic?

Although I guess you could design a quadratic without real solutions

[weary tiger]

because the quadratic equation in $\mathbf{Z}_7$ has either 0,1 or 2 solutions and if you find 2 you can't have more

[vital dew]

Twilight:

[weary tiger]

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

see also the table at http://mathworld.wolfram.com/QuadraticResidue.html

just check all the values already, (mod 7) you have 0,1,4,2,2,4,1 and that's it

(consecutive squares)

[sonic crescent]

Hey, could I get a little help with this:

The highlighted bit. I understand the sentence before, but I'm not sure how it gets to the highlighted bit

The way I see it is if there are at most that many numbers below M, then surely the inequality sign should be the opposite

[pearl leaf]

Hello, could someone explain me how can I calculate this by hand?

7(^222) mod 23

[viral stump]

@sonic crescent they have shown there are at most sqrt(M) 2^k possible numbers less than M

because that's the maximum amount of numbers you can write

the inequality follows

because there's M numbers less than M

@pearl leaf little theorem

[pearl leaf]

$ (7^222) mod 23$

alright

@viral stump it's also refered to the fermat's theorem, am I right?

[viral stump]

fermat's little theorem

there's a bunch of theorems by fermat

[pearl leaf]

alright thanks, I'll lookup for it to see if I can solve these problems

[sonic crescent]

@viral stump thanks 😃 I got it

(from what you said)

[viral stump]

nice

did you die

[pearl leaf]

I might need help for getting the inverse of 101 mod 4620
I already got the GCD(101,4620) but I'm applying the extended form I'm getting confused at a few parts of it

[rough cosmos]

why X is not a multiple of 5?

[viral stump]

because otherwise it doesnt work

@pearl leaf what

for there to be an inverse the gcd should be 1

[rough cosmos]

because otherwise it doesnt work -> what?

[viral stump]

gcd(4620, 101) = gcd(101,75) = gcd(75,26) = gcd(26,23) = 1

how are you computing the inverse

because there's an easy way

well not sure if easy

but you can do a^(phi(4620)-1)

i think extended gcd might be easier

[pearl leaf]

the answer my instructor gave me was the 1601 but I'm not sure how he reached there, these were just answers to the excercise which I am trying to get using the extended gcd

I found the values I was missing

[viral stump]

yeah gotta just work it slowly

[pearl leaf]

yeah, thanks for your help tho it kinda helped me try it again xD

[rough cosmos]

if X = 10 and n = 2 then 5^2 = 5^(2 mod 4) mod 5

which will be 25 = 25 mod 5

@viral stump why doesn't it work?

they both have same remainders 0 when divided by 5

[viral stump]

5^4 = 0
5^(4 mod 4) = 5^0 = 1

[rough cosmos]

oh got it thanks

[odd wren]

Is discrete math taught in high school or something bc i've never heard of it

[weary tiger]

It wasn't when I was growing up, but it might be now

[rough cosmos]

In college

[odd wren]

oh, that explains it, must be college lvl then

[rough cosmos]

more in computer science and math major

[odd wren]

ah

[weary tiger]

When I was growing up, computer science didn't even exist :)

[rough cosmos]

woah lol

we have like 1600 students in comp sci right now

[weary tiger]

I'm really frickin old :)

[rough cosmos]

did you major in math?

[weary tiger]

Yes, I did

[rough cosmos]

nice

[weary tiger]

I'm obsessed w/ math :)

[pearl leaf]

finally finished it I understood now where my mistake and confusion was I was missing one of the expansions and substitutions of one of the values I already had

[heavy isle]

hey guys this means that for all x and all y there is some z so that z is the ordered pair x,y right?

its from this if you need more info

[rough cosmos]

I need to find inverse modular 8^-1 mod 17

I have done

17 = 2(8) -1

8 = 1(8) - 0

How do I reverse it now?

[viral stump]

you need 8a + 17b = 1

you have it in the first line

[rough cosmos]

will it be then 8(2)+17(-1) mod 17?

@viral stump

[viral stump]

no

once you have 8(-2) + 17(1) = 1

you take mod 17

and you get 8(-2) = 1 mod 17

[rough cosmos]

oh i get it now

17 mod 17 = 0

and -2 mod 17 = 15

therefore 15 is multiplicative inverse of 8

thanks

[viral stump]

👍

[weary tiger]

So, if i measured 51kg (@160*F) of water flowed into a bucket after 15 seconds.... what is the flow rate of the system in gallons/minute Help??

[sour arrow]

51kg in 1/4 of a minute

204 kg in a minute