discrete-math

[torn totem]

yes

[weary tiger]

Is this an acceptable proof that the constants in any instance of Bezout’s identity are coprime?

[velvet lynx]

the set of integers modulo a prime are a principal ideal of themselves right

[stoic wagon]

.

[pale epoch]

every ring is a principal ideal of itself

[velvet lynx]

oh wait yeah the multiplicative identity element

[opal plank]

seems kind of too complicated.

just divide both sides by d and you get xa' + yb' = 1, which implies (x,y) = 1 🤔?

[weary tiger]

Oh i thought that this just shows that gcd(a’,b’)=1, which would be true since d is all their common factors. In that case, would a’ and b’ just become the constants for the instance of bezouts for gcd(x,y)?

[opal plank]

Yes

[weary tiger]

I see, thanks you

[mental plaza]

guys how do i get used to using the discrete math notation and proofs

proofs are killing me

i feel so lost just trying to understand

like what the question even is

[rotund swan]

me too ^

Im confused on laws of propositional logic

[mental plaza]

are you taking discrete?

what topic are you guys on right now

[dreamy locust]

This a question on my homework assignment. I know that (A^m)ij counts the number of walks of length m from vi to vj. I understand the first and last terms on the rhs, (2 ways to traverse cycles and walks of the form vi vj vi vk vi) but i don't get what the 2nd term is for.

[sand pelican]

How can I prove 5 divides n^5-n (with n \in ℤ)? I don't use induction here because there is not a least element n

[opal plank]

Euler's theorem

Though you can use induction too

[sand pelican]

why? I thought induction only applies to sets with a least element

[opal plank]

First prove for positive integers, then extend to all Z

[sand pelican]

How can I extend to all Z?

[opal plank]

If n^5 - n is divisible by 5, then (-n)^5 - (-n) is also divisible by 5

[sand pelican]

Oh, I was not trying to think more about it, sorry and thank you

[sand pelican]

Can I ask more about how we use Euler's theorem to prove it as well?

[opal plank]

Yes

[honest tundra]

can someone explain to me what am i doing wrong here

im so lost

[velvet lynx]

i think thats right?

i think you need to add the presume the reciprocal of x is not unique somewhere

[velvet lynx]

how do finite fields for prime powers work if a modular multiplicative inverse only exists for a number coprime to the modulus

[fossil mural]

for n > 1, the finite field of order p^n isn't the ring of integers mod p^n

because for the exact reason you observed, the ring of integers mod p^n isn't a field in that case

[velvet lynx]

ah

i see

thanks

[fossil mural]

so in fact it's still a field of characteristic p, you just get it by adjoining a root of a suitable polynomial to Z/pZ

for instance the field of order 4 is {0, 1, x, x+1} where 1 + 1 = 0 and x^2 = x + 1

[fossil mural]

(specifically you want it to be irreducible, i think that's enough to make sure you get a field...?, and the size of the field you get will depend on its degree)

[dire schooner]

Do $\lor$ and $\oplus$ have the same operator precedence

[vital dew]

alex

[dire schooner]

In logic

[quiet wharf]

In what way? the first one, or, is on sets? the second one or or xor?

on elements?

[snow cedar]

Any advice for this? I'm unable to find a geometric property that I can exploit

[quiet wharf]

Hmm. When I hear that, I think of Graphs on a sphere, (hollow), not sure that helps.

[snow cedar]

[viral crown]

hint 1: ||think about the curve i mentioned in my earlier hint.||

hint 2: ||think about four arbitrary distinct points ||

hint 3: ||if you can embed Kn for arbitrary n you are done||

the first and second hints are the only really important ones, the third is there just in case you overthink

[frosty blade]

Can someone please explain what the inverse, converse, and contrapostive mean regarding a condtion statement.

[sly flint]

If our condition statement is $P \implies Q$, then the inverse is $\lnot P \implies \lnot Q$, the converse is $Q \implies P$, and the contrapositive is $\lnot Q \implies \lnot P$, where $\lnot$ can be read as `not'.

[vital dew]

gjoa

[frosty blade]

ok thank you

[high helm]

i have to "prove or disprove that the product of a nonzero rational number and an irrational number is irrational"

I started with the rational number being a/b (def. of a rational number), but I'm not too sure where to go from there

i get the general proof process im just stuck on what the next step would be

[clever sail]

Think about how a rational product would be expressed

And then try and derive a contradiction

[high helm]

is this valid?

[snow cedar]

Thanks for the hints! I think I'm lacking a bit of knowledge because I'm not sure what is meant by the curve "(r, r^2, r^3) for r in R" Is there a way to define this in layman terms?

[obtuse lance]

this seems like a totally different kind of graph than the graph theory sense

[viral crown]

im pretty sure this is that kind of graph, i've done this exercise before

[viral crown]

uhh that was calc 3, so if you're being given this problem you probably should know what that is

where'd you get this problem?

[rugged dock]

can anyone help with my combinatorics problem

[snow cedar]

It's from a introductory graph theory course that I'm doing! From what I saw, calc 3 wasn't in the list of prerequisites. I had taken calc 3 about 2 years ago though, so my knowledge most likely faded since then.

[viral crown]

hmmm

the prereqs might have calc 3 as the prereqs

what book is this?

[viral crown]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[rugged dock]

i want to prove $n^{\underline{k}}=(n-1)^{\underline{k}}+k\cdot(n-1)^{\underline{k-1}}$ combinatorially

[vital dew]

javier

[rugged dock]

where it defines $n^{\underline{k}}$ as the number of ways to create a list of length $k$ w/o repeats

[vital dew]

javier

[snow cedar]

We're using this textbook: https://athena.nitc.ac.in/summerschool/Files/West.pdf

Although that problem I sent is linked on a custom file. I am not sure if it is reusing a problem in this book. By the way, the prereqs mention linear algebra. Maybe that would give a different perspective?

[viral crown]

pretty sure this exact identity is somewhere in loehrs bijective combinatorics, don't remember it exactly tho, sorry

is this douglas west's textbook

[snow cedar]

Yeah

[viral crown]

lord

[rugged dock]

welp my proof outline is that i choose my first element, then i have n-1 elements. From there to choose my second element i considered 2 cases: pick a specific element, then a subset either contains it or not

if a subset contains it then i reduce the problem to n-1 and k-1 spots open. If it doesn''t, then the problem doesn't change, k spots still open. For the former case, I have k subsets that contain that element, so i multiply by k

it's a little hand wavy but the algebra agrees

i just don't know how to put the algebra into a clear argument

[viral crown]

do u know the page number?

[snow cedar]

I don't think it's part of the book

[viral crown]

💀

i know like

four proofs of this

three of them are all topological

one of them uses calc 3

[snow cedar]

Yeah that book is like a reference and we just get some random problems for exercises. Like I don't know which sources they even give these from.

By the way for my question, I think a hint I got had something to do with points forming some sort of plane as you build the graph . That sounded more in line with linear algebra but I'm not sure I understand the intuition

[viral crown]

yeah that's the calc three proof

do u want me to explain it?

[snow cedar]

Sure I'm open to it

[viral crown]

okay, here's how it should go

first we take a function, let's call it $h: \mathbb{R} \to \mathbb{R}^3$, where $h(r) = (r,r^2,r^3)$. take the curve given by this

[vital dew]

valley

[viral crown]

let's call the curve uhhhh $C$

[vital dew]

valley

[viral crown]

not uhhhh just C

then take four points in $\mathbb{R}$, distinct

[vital dew]

valley

[viral crown]

let's call them like

$v_1\dots v_4$

uh

nevermind

we'll call them $r_1\dots r_4$ because we already used r

[vital dew]

valley

[viral crown]

keep them distinct

give me a second

[snow cedar]

Yep no problem! Take your time

[viral crown]

i dont know how to do matrices in latex without my shortcuts imma look it up rq

shit

$\begin{bmatrix}
1 & r_1 & r_1^2 & r_1^3\
1 & r_2 & r_2^2 & r_2^3\
1 & r_3 & r_3^2 & r_3^3\
1 & r_4 & r_4^2 & r_4^3
\end{bmatrix}
$

[vital dew]

valley

[viral crown]

okay that looks correct!

okay, so the volume of the tetrahedron formed by $h(r_i)$ is proportional to the det of this matrix by some sweet sweet calculus

[vital dew]

valley

[viral crown]

note that all of these points are on our curve C

thankfully this determinant is nonzero because this is a vandermonde matrix, which are surprisingly helpful in lots of things, like interpolation and when you need certain determinants to be nonzero

because it's nonzero and the volume of said tetrahedron is proportional to it, our points on C are not coplanar

so the edges of our tetrahedron (which are straight!) intersect only at the vertices

then take n distinct points from C

if we form Kn from them, edges intersect only at the vertices

so we're done

wow, this was a truly horrible explanation

i hope that was follow-able

i know that either this or something close to it is correct, soooo

yeah this looks right

aha det isnt necessary here i think

[snow cedar]

Ok wait so in your tetrahedron, are you are placing the vertices in the corners?

[viral crown]

yes

note that we took arbitrary points in C

so if we wanted to make, say, K5, then you could just do it with each four-set of points to make sure that none of them are coplanar and thus have straight edges connecting them

[snow cedar]

Is the reason why you are introducing the complete graph K_x because if we are able to do solve this problem for the complete graph, then it should trivially be easy for smaller graphs?

[viral crown]

every graph on n vertices is a subgraph of Kn

so you can just delete whatever vertices and edges you like off Kn to get the graph you want

since we proved this for any finite Kn this works for any finite graph

argument could probably work as is for infinite graphs too as long as |G| <= |R|

[snow cedar]

Don't think we are doing infinite graphs haha 😆

I think my current issue is that I don't know what the tetrahedron looks like. Why did we only settle for choosing 4 points r1 r2 r3 r4?

[viral crown]

we picked four because there's easy theorems to show the volume of their tetrahedron is nonzero via the vandermonde matrix or just through at+bt^2+ct^3=d on the twisted cubic

we just need non-coplanarity and four was the easiest way to do it

plus, four suffices because we picked arbitrary distinct points

[snow cedar]

Oh I see

[viral crown]

yeah if you wanna make k3 or something just make k4 and delete a vertex and all edges to that vertex

[snow cedar]

This seems like a big brain way to do it ngl, we did not even learn about vandermonde matrix LOL

[viral crown]

vandermonde matrix isn't needed!

[viral crown]

see second point here

i just did it because when i did this, i was thinking a lot about the vandermonde matrix and doing some calc 3, plus the hint i was given seemed to suggest this

and yeah this is a hard problem

it took me like, two hours of just thinking about it

[snow cedar]

That's insane

[viral crown]

a little big brain is needed

without a hint i think it would have taken me ten or so hours

if i wasn't actively thinking about calc three around that time, probably even longer

[snow cedar]

[viral crown]

yep

key takeaways here are probably that moment curve 'trick' and a little bit of lateral thinking in what we can embed

actually probably the main key takeaway is that calc three is always helpful

[snow cedar]

Yeah it seems OP

I am going to digest these details

Thank you so much valley!

[viral crown]

nw! have fun

pick up topology once you get the chance, there are some theorems that make this trivial

[finite cypress]

Can someone help me with counting

Would 10 be 15! Minus the 2 where they were on a single shelf

[finite cypress]

Someone please #36

[burnt nebula]

anyone got time to hop on a discord call and help me understand my discrete math hw, its about proofs

[brave rock]

I'd recommend just asking your questions here

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[snow cedar]

How can I show that Show that if T1, T2, T3 are subtrees of a tree T such that Ti and Tj
always share at least one vertex, then there is a vertex v ∈ T common
to all Ti? I think this would help generalize it to more than 3 subtrees too

[brave rock]

Often when you see a proposition of the form "there exists..." you have to work, as mathematicians say, 'non constructively' which means that while you can guarantee that it exists, you may not actually be able to describe a way to actually find the thing.

This is such a case, and so we should work non-constructively here.

In particular, you should try doing a proof by contradiction.

So suppose there is no common vertex. so say there are vertices a b c such that a is common to T1 and T2 but not T3, and so on.

And you should try finding a contradiction from this information. Hint: a tree is a connected graph with no cycles!

[snow cedar]

So I know this

$T_1$ intersect $T_2$ has a vertex $v_{12}$ and
$T_1$ intersect $T_3$ has a vertex $v_{13}$ and
$T_2$ intersect $T_3$ has a vertex $v_{23}$
\
So I gather $v_{12}, v_{23} \in T_2$ and
$v_{13}, v_{12} \in T_1$ and
$v_{23}, v_{13} \in T_3$

[vital dew]

clementine

[viral crown]

not relevant but i do wonder if you could do a constructive proof

[snow cedar]

i can see that I can travel from v_12 to v_23, then v_23 to v_13, then v_13 back to v_12. (So we can travel from T2 to T3 to T1) Of course there should not be a cycle here, but is that all I would need to state? I feel like I'm not seeing the bigger picture why this shows the intersection of T1 n T2 n T3 is nonempty

[brave rock]

Remember we are doing a proof by contradiction.

We assumed the intersection was empty, and we are trying to show that such an assumption leads to nonsense.

So one way of getting a contradiction would be to show that under such an assumption, the tree would in fact have a cycle.

[snow cedar]

Hmm... How would my statement change if I didn't assume that v_12, v_23, and v_13 were distinct?

[brave rock]

Well if they were not distinct then in fact at least one of them would belong to all three subtrees, and you're done.

[snow cedar]

What if we had a graph that is a straight line? Like

O - O - O

and our subtrees was
O - O - O (The entire graph)

O - O

O

ig that falls under the case that they are not distinct

[brave rock]

Yup

[burnt nebula]

to disprove: integer x is positive if and only if x + 1 is positive

is the counterexample x = 0?

[viral crown]

yep!

[viral crown]

do you still want some help btw?

[snow cedar]

Yeah I think I still need a bit of help justifying the contradiction step

I thought I understood it, but later I realized I don't

[viral crown]

hmm

what do you have so far

[snow cedar]

• So T1 and T2 share a vertex V12
• T2 and T3 share a vertex V23
• T1 and T3 share a vertex V13

When I assume for contradiction that there is no common vertex between T1 and T2 and T3, by referencing the information above I know that:

• V12 cant be in T3
• V23 cant be in T1
• V13 cant be in T2

[viral crown]

hmm

this isn't how i would go about it

remember, we want to create a cycle

we want to show that v_12 is in T3

what should we assume for contradiction?

[snow cedar]

I had assumed T1 intersect T2 intersect T3 is the empty set

[viral crown]

well, we can assume that, but we can state it another way

assume that v_12 is not in T3

functonally the same thing!

[snow cedar]

Yep that is on my first bullet point

or 4th I guess. 1st bulletpoint on my second paragraph

[viral crown]

right, so you know v12 is not in T3, but you know v13 is in T1 and T3, and v23 is in T2 and T3

[snow cedar]

Yep!

• So T1 and T2 share a vertex V12 => v12 in T1 and v12 in T2
• T2 and T3 share a vertex V23 => v23 in T2 and v23 in T3
• T1 and T3 share a vertex V13 => v13 in T1 and v13 in T3

[viral crown]

state the definition of a tree for me

[snow cedar]

a connected graph that has no cycles?

[viral crown]

right

so it's connected

and you have a vertex shared between each pair of subtrees

how would this help you create a cycle

[snow cedar]

Hmm,
I can start at V12. I know that I am have access to T1 and T2.
I will choose to go along T2. So I can go to V23.

V23 has access to T2 and T3. I will choose to go along T3. I can reach V13.

V13 is in T1 too. I can go to V12 again

[viral crown]

yes!

alas, that is a cycle

in T, no less

[snow cedar]

Okay so we went from T1 -> T2 -> T3 -> T1. And if it wasn't a cycle we would have been able to do some sort of backtracking otherwise?

[viral crown]

well, we'll be able to go on a path (v12, ..., v23, ..., v13, ..., v12) with some things possibly in the middle

it doesn't really matter since it's still a cycle

[snow cedar]

Oh I thought we were going to exploit these observations:

V12 cant be in T3
V23 cant be in T1
V13 cant be in T2

[viral crown]

why? we're already done, really

we just needed to construct a cycle to display the contradiction

[snow cedar]

Oh I see

I guess that makes sense then

I was overcomplicating it

thank u

So I am guessing I can generalize this idea for k >= 3 subtrees

and I can use what we talked about above as some sort of "helper"

I am trying to do induction

[viral crown]

go for it!

[weary tiger]

why is this channel public if it's about discrete math?

makes no sense

[viral crown]

that one made me chuckle

[snow cedar]

So I'd assume the induction hypothesis for n = k, that if I have K Subtrees such that for Ti and Tj, their intersection is non-empty, then there is a vertex v in T common to all T_i

And prove for n = k + 1,

I would take T1, T2, T3, ..., Tk, T{k + 1}
Then define T_j = T_k n T_{k + 1}
Then I guess I'd apply induction hypothesis here

[burnt nebula]

having a hard time with this one

x or y is true if one or both are true

is this one where you cant disprove it?

[obtuse lance]

yeah, you're on the right path, keep going with those cases

[obtuse lance]

this can be disproved

[burnt nebula]

true if either x or not y or not x or y are true

if X and Y are T

X or Y is true

But (X And Not Y) OR (not X and Y) are false

op jsut answered myself

lol

[obtuse lance]

yeah that's the best way to do it lol

another name for that thing on the right is XOR which means exclusive or, since it's only true when only one or the other is true not both

[burnt nebula]

gotcha thank you

at some point do you just memorize the truth tables or do you always draw it out

[shut ivy]

can anyone explain the difference between $\implies$ and $\to$

[vital dew]

rabbits_advocate

[shut ivy]

And when to use each notation

[oblique pelican]

$\implies$ is usually exclusively used for implications or to show the next step of an algebraic proof (which is also used as an implication).\

$\to$ or $\rightarrow$ is used for things like functions or limits, but can also be used for implications:
$$f:A\to B$$
$$\lim_{x\to a}f(x)$$
$$p\to q$$

[vital dew]

Dilly

[snow cedar]

I think this is not an isomorphism. I have tried a bunch of functions like x + 1 and x - 1 (For x + 1, 8 would map to 1 like its wrapping around and oppositely for x - 1, 1 would map to 8 like its wrapping around). Is there a convenient way to make a conclusion for these sorts of problems?

[obtuse coral]

given such a set, could i say f^-1(y) = x?

[oblique pelican]

If f^-1 is a valid function, then yes. In general though, f^-1 is just a relation, so a set of ordered pairs, and you can't say anything about the inverse of a particular value. However, you can find the preimage of a set which is the set of x's where f(x) is in that set. So for example, in the definition above, you could say that x is in preimage of the set {y}, denoted f^-1({y}).

[sick grail]

isomorphisms preserve basically all graph structure, in particular there being triangles (actually how many triangles too)

in general if you can find literally any property that differs between the graphs then there can't be an isomorphism

by a triangle I mean 3 vertices with an edge between any two / K_3 is a subgraph

[oblique pelican]

Actually, @obtuse coral are you learning about relations or functions?

And if you're learning about relations, then is f defined as just a relation?

Because then I would be inclined to say that f^-1(y)=x is correct, but it is strange notation since there could be another value w where f^-1(w)=x

[dire schooner]

The math is discrete

[rugged dock]

Hi can anyone help with the combinatorics problem: I have 15 friends and 10 tickets. 6 tickets are assigned seating and 4 are general admission. How many ways to distribute out the tickets to my friends?

Forgot to mention each friend gets at most 1 ticket

[shut ivy]

what about the two if and only if signs like in this example

[dire schooner]

this is just equivalence, no?

$\Leftrightarrow$ just means Logical Equivalence

[vital dew]

alex

[shut ivy]

so when to use each of the two

[dire schooner]

$p \land p \Leftrightarrow p$ This reads $p$ (logical and) $p$ is logically equivalent to $p$

[vital dew]

alex

[dire schooner]

$p \to q$ this reads $p$ implies $q$

[vital dew]

alex

[dire schooner]

$p \leftrightarrow q$ this means $p$ if and only if $q$, or $p$ biconditonal $q$

[vital dew]

alex

[shut ivy]

Can i also think of it as $\Leftrightarrow $ means that the statemnet is a tautology and $\leftrightarrow$ means that the implication needs to be proven true using a truth table?

[vital dew]

rabbits_advocate

[oblique pelican]

Essentially. I guess here they are using $\Leftrightarrow$ to compare two logical statements, whereas $\leftrightarrow$ and $\rightarrow$ are used as implications within those statements. There is no inherent truth to the implications, but the $\Leftrightarrow$ is showing that the two statements have the same truth values. I've usually seen $\equiv$ in place for $\Leftrightarrow$ in these cases and that makes the difference more apparent imo.

[vital dew]

Dilly

[shut ivy]

thanks

[dire schooner]

Is this enough

I may have realized that there is a much simpler way to

oh god im actually silly

[nocturne nymph]

i need some advice, what should i read to understand what the fuck is written here? there's a task to simplify it, but i can't understand a shit. maybe some books or that kind of things?

[dire schooner]

what the fuck

[oblique pelican]

Set dot product just dropped

[agile magnet]

This is a good realization to come to

But often yes this only happens after you've completed the proof the long tedious way

[wraith mist]

Not sure if this belongs here but is there another characterization of when two sets S and T are the same in terms of their complements?

For example is S=T equivalent to S\cap T^c non empty AND T\cap S^c non empty

[odd heart]

Try proving it or finding a counterexample

[wraith mist]

Your right as soon as I asked I realized it doesn't work for subsets

[north junco]

how does my proof look here?

i hope my proof was clear

[lime slate]

What u doing here

[weary tiger]

Hey, just wanted to ask... should I take up a discrete maths course, even if I am not into programming, computer science or data structures? For reference, I am currently learning calculus and thinking to take up combinatorics...

[dire schooner]

Math

[dire schooner]

It’s interesting so yes

[lime slate]

it teaches some number theory and some other stuff too its also useful for logic and stuff in the future proofs etc

[viral crown]

my opinion is to not bother actually

for the math, that is

i think math majors should all take compsci classes, and discrete math is probably a requirement

[viscid sluice]

I am in my second year od comp sci engineering and we had engineering math 1 and 2 in first year. Why is discrete math so weird. I was fully prepared for calculus in my 3rd sem but we got discrete math?? Why?

[kindred flare]

its logic-based, with a big focus on proofs

discrete math has less to do with solving the equation and more to do with proving why the equation works

[viral crown]

discrete math is proof-based for compsci majors

[kindred flare]

i found that getting a deep understanding of discrete math helped me later on, especially in linear alg

[kindred flare]

yes, I have Bachelors in both Math and Compsci

[viral crown]

cool!

[kindred flare]

this is the first channel that caught my eye after i joined 😂 discrete math is genuinely fun once you can understand how the logic works

[viral crown]

mhm!

combinatorics 🔛🔝

[viscid sluice]

I don't really know why but I suck at logics

Logic gates is the best I can do

[kindred flare]

its the written version of logic gates

in a sense

[viscid sluice]

Any good books or notes you can recommend for discrete math?

[viscid sluice]

How does a linked list work? 😭

[kindred flare]

each node points to the next

a -> c -> f -> b -> d

etc

double linked a <-> b <-> c

[viscid sluice]

How does insertion in the middle work

Is it like an array or do we just add an entire node?

[kindred flare]

you would essentially reroute the pointer to the new data, and set the pointer of the new data to the existing rest of the list

[kindred flare]

you would need the new node, if i remember correctly

i believe thats where LL and arrays differ

[viscid sluice]

I see. Our data structures professor literally doesn't teach

[kindred flare]

ugh and data structures is an important class LOL

thats one of the core foundation classes of comp sci imo

[viscid sluice]

Same is with out OOPs prof. He finished the entire sem class in 2 days by just giving us the examples of inheritence, encapsulation and polymorphism

[kindred flare]

what language for your OOP? java?

[viscid sluice]

C++ and Java

[kindred flare]

oh wow, both!

[viscid sluice]

We have Java as a subject as well but our OOP prof uses both languages

I donno how he has been here for 10 years and no one complains

[kindred flare]

ohh i see, thats really good though. my oop was all java, and i never got a good understanding of C

[viscid sluice]

I used to like programming till these teachers destroyed all my existing knowledge of it

[kindred flare]

what would you like to do with compsci? more front-end or back-end work when youre out of college?

[viscid sluice]

Masters in aerospace hopefully

And then I'll decide what I wanna do

[kindred flare]

oh wow, impressive! definitely master your understanding of OOP then

[viscid sluice]

How is it that the important subject has the worst teachers

[kindred flare]

have you gotten into Assembly yet at all?

[kindred flare]

the best teachers make you think, never forget that

[viscid sluice]

HAHHA I tried

Its weird to go from high level prog to low level

[kindred flare]

if a teacher spoonfeeds you info, and doesnt make you struggle, ive always found them to be bad in hindsight

[viscid sluice]

Once my events are all done I will start with assembly again

[kindred flare]

hahaha having to literally program your 1s and 0s and manipulate your physical machine muahaha

[viscid sluice]

My computer architecture is weak

[kindred flare]

see if your school offers it, mine offered it as a class

[kindred flare]

only a week!

😂 cooked

oh WEAK

[viscid sluice]

My school offers none of that

[kindred flare]

i cant read forgive me

[viscid sluice]

The kids in my class do NOT wanna study

half of them are here only for a degree and then to do family buisness so they somehow get the teachers to not teach

[viscid sluice]

I sometimes can't type either

I am relying on autocorrect

[kindred flare]

passed all my compsci classes, and was a TA, but i failed english in college LMAO

its my adhd i swear

[viscid sluice]

We have soft skills once a weak and they made us do mock interviews and I could not sit still

I fell down the chair once mid lecture

[viscid sluice]

I got scolded by my city's AFS head for "being unprofessional" during interview since I was taking the interview

Not my fault the chair could spin

[rustic locust]

(a) Draw a simple connected graph with 9 vertices all having degree 2. (b) A simple connected graph has 9 vertices, all having the same degree d. (1) State the possible values of d. () For each of these values of d, state the number of edges of the graph.

[weary tiger]

English is easy how the hell you failed.

[oblique pelican]

Essays 👎🏻

[kindred flare]

yup

i was double majoring in compsci and math 😂 i couldnt be asked to sit down and focus on writing essays. i retook it over a winter break when i didnt have other classes and passed

[uncut raptor]

Let D = (V, A) be a directed graph. Prove that a closed, directed walk in D contains a directed cycle.

I have to prove this

the answer is:
We will prove this by construction. Denote the closed, directed walk in D by v0 → . . . → vn. Let
j be the smallest index such that there exists an i < j with vi = vj . Then, vi → vi+1 → . . . →
vj−1 → vj is a directed cycle because it contains each vertex (and thus also each arrow) at most
once.

but I am not realy understanding why this theorem hold.

nvm I understand it

[outer gust]

Hey I need some help. I don't have an idea of how to start

[true venture]

How to prove that $\sum_{i >0}{ i\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^i}$ \
Has series expansion
$\sum_{n>0}{2^{n-1} x^n}$
?

[vital dew]

jonathan_fisherman

[high helm]

||you know there's an x for which q is false from one of the premises. as such, since we know that q(x) or r(x) for every x, r(x) is true for whatever x makes q(x) false. since r(x) implies p(x) for every x, we can chain these together.

there is an x that makes q(x) false. for that same x, r(x) is true. we know that if r(x) is true then p(x) is, so p(x) is true for whatever x makes q(x) false.

you can link these to universal modus ponens and such||

this is the conclusion that i got; for a starter hint, you know that there's an x that makes q false, and you know that either q or r is true for every x

see what you can get from that

[outer gust]

gotcha

[naive hazel]

Does this proof look correct the stuff in purple is the premises and they all imply b

Also do I have to use c implies b in my proof or as long as I lead up to b then it's correct?

[oblique pelican]

yeah, you only know that either a or c is true (potentially not both), so you have to show that b is true in both cases

[naive hazel]

Ah ok

I just realized that proof is wrong btw

Cuz disjustinctive addition doesn't work both ways 😭

[naive hazel]

Man this is hard 😭

[limpid flax]

Does this proof make sense? Let a an integer. Let a^2 be even, then a is even. Let p,q be propositions. Let p be a^2 and q be a. If a^2 or p is T, then a^2 is even, else not even. If a or q is T, then a is even, else not even. p->q, p yields. Assume p->q, p is T. Case 1: p is T. p->q is T since q is T and T->T is T. Case 2: p is F. Can not exist since initial assumption is p is T. Hence q is T. Hence a is even. Trying to prove if a^2 if even, then a is even

Tried using chatgpt to check, but was told to use contrapositive

[viral crown]

your proposition: if a^2 is even, then a is even.
the contrapositive: if a is not even, then a^2 is not even

you want to prove the second statement

since a is not even, what does that tell you?

[limpid flax]

a is odd

[viral crown]

cool, so how can you write a?

[limpid flax]

and then expand to 2n+1 and square it to show it can be written as twice an integer + 1 after?

[viral crown]

yep!

[limpid flax]

ty

[viral crown]

mhm

[limpid flax]

quick question. Do you put the quantifier infront of the first time the variable is introduced? Or on the very left side (Like ∃x on the left).

Am trying to say whether one is a predicate, proposition, or not well formed

[viral crown]

you should hopefully not use quantifiers unless it's required for an assignment

[viral crown]

im not sure but there are quantifier guides online that will answer this!

[still bloom]

In discrete math there is a rule called addition. I was wondering if I can add a negation using that rule?

[oblique pelican]

is there more context?

[fair leaf]

im struggling so hard with understanding how to prove graphs, i was doing pretty okay with the basics of discreete math but now we're in graphs and i have to "prove every tree is a bipartite graph using induction" and i have no idea what to do. any tips? in general for learning graphs

[next sail]

GM guys! Could someone help me with this HW question? 👀

"Use a k-map to find a minimal expansion as a boolean sum of boolean prodcuts of each of these functions x, y, and z. then find the same expression using the Quine-McCluskey method..."

Any help would be greatly appreciated!

[still bloom]

Someone helped me out with it appreciate it tho gang

[fossil mural]

it looks like this "proves" that every statement implies every other statement

[fossil mural]

like which step of this logic doesn't work if you're trying to prove "if a^2 is even then a+1 is even"?

[vivid sinew]

If we give a direct proof of ¬q → ¬p then we have a proof of p → q.

Please give a general proof, but not proof some separate case(s).

can someone explain to me what exactly they are asking by the second part? I have emailed the professor but they are not replying

[grand totem]

Unless the original question is in a different language and some things have been lost in translation, I wouldn't know what exactly they mean either.

[fossil mural]

yeah that looks a lot like a translation error, if that isn't what happened then i have no idea what it means

[fossil mural]

...i think if you think your problem is with graphs then you're probably thinking about it wrong

like to prove that every tree is a bipartite graph, you do have to know the definitions of "tree", "bipartite", and "graph", ...and that's basically it, everything else is just general problem solving skills

like before you actually try to write a proof down, just think about why you would expect the statement to be true at all, maybe look at some examples of trees and prove that they're bipartite graphs to get an idea of how it works in the general case if it isn't immediately obvious

or there's the strategy of trying to prove the opposite to see exactly where it fails: see if you can construct a tree that isn't bipartite, it won't work but if you can figure out why it isn't working and is in fact impossible, that's the same as having a reason why every tree is bipartite

[fair leaf]

i guess thats fair. i did ask my professor and he told me to explain why adding a leaf to any tree will always keep it as a bipartite but im not sure how to write it down in a way that is formal enough lol

[rare walrus]

could somebody please explain to me how to use the P(n,k) formula to solve this problem?

[obtuse coral]

does contradiction only work when its fully contained within one proof or could i say like assume that x>1 is true but i then lead to a contradiction thus x<=1 which i will use for further down my proof?

[clever sail]

Hmm I’m not exactly sure what you mean but the idea is that it should be like a chain of implications

Like as long as you’re assuming x represents the same thing throughout the proof then yeah

Like

Idk if you said assume y=sqrt(x) where x,y are real numbers and we want to prove that x cant be less than zero, you can just be like assume to the contrary that x<0, then y = i sqrt(|x|) so we have arrived at a contradiction since y is not in R but we assumed it was

Idk kind of a shitty example but whatever

[thick canyon]

Based on the diagram of the functional elements and the delay element, construct a Moore diagram:

[snow junco]

Those gates are the devil’s work

Note: the left two are useless

[clever kite]

Is this valid? The cyclical argument I made feels like I'm missing something here

[sick hollow]

can someone help me with this homework problem its prove or disprove logical equivalences using domain and Im stuck and dont know if this is right?

[lethal fog]

Aider moi s'il vous plaît

[sick grail]

Tu peux trouver un autre point C qui est situé au même distance du M (pour tout choix de M sur Δ) que B, mais pour lequel le choix de M qui minimise le trajet AM+MC devient beaucoup plus évident.

[bright ember]

Can I write $\sum_{k = 0}^n k {n \choose k} x^k$ in terms of $n$?

where $x$ is a constant?

[vital dew]

Improv

[bright ember]

wolfram alpha gives, but I'm not sure how

[vital dew]

bacc

bacc

[wheat lichen]

At least that way I think you can find a closed form

You get rid of the k

[vital dew]

bacc

[wheat lichen]

Then differentiate again

both sides

@bright ember

[bright ember]

I'm not sure what you mean by integrating and differentiating could you point me to somewhere I can read up on it?

[wheat lichen]

Integrating/differentiating a series is the same thing if you were to do it with a function

[wheat lichen]

https://www.youtube.com/watch?v=dEHZV7q5VV0

[oak drift]

hello, how is this false?

[oblique pelican]

Nah that's true

[oak drift]

teacher says it's false

ohh wait is it because 5 can be -5 or something like that

[oblique pelican]

5>4

Not sure what else it would be saying

x > x-1 is true for every real number

[oak drift]

look cuz the slide right after is this :

[oblique pelican]

Huh

My only guess is that it's showing you the importance of mentioning your universe of discourse

Like the set that you're getting your numbers from

[oak drift]

yeah I guess

cuz we see Uni of discourse right after

[oblique pelican]

Because I guess > is an arbitrary ordering

You could make an ordering where 4 > 5 if you really wanted to

[oak drift]

But I don't think she would use it as her first example

it would confuse students more in that case

tbf this is confusing too lol

[oblique pelican]

Yeah I agree

I think it's not really unclear in this case what the meaning is of x > x-1

Only in certain contexts might you have to actually specify the universe

But it's an exercise to prove a point so I'll let it slide

[oblique pelican]

Really it should say "can't be determined based on the information"

[oak drift]

its one of the options lol

and she says its false

[oblique pelican]

Bruh

[oak drift]

there's also "not a proposition" but that's not the answer

[oblique pelican]

I concede

[oak drift]

a bit easier question, do you know how I'm supposed to translate the part thats between the brackets??

where n = an id and s = a student

I know it's supposed to be C but I don't understand what brackets do

[oblique pelican]

Can you circle which part?

They're just predicates inside

With the quantified variables as inputs

[oak drift]

this part basically

[oblique pelican]

Yeah so the brackets just indicate a predicate

[oak drift]

sorry what does that mean?

[oblique pelican]

It says for every student $s_1$, there exists an id number $n$ such that $s_1$ has id $n$ and there does not exist a student $s_2$ who is different from $s_1$ and also has id $n$

[vital dew]

Dilly

[oak drift]

so it's like "comments" on the proposition?

[oblique pelican]

$\forall s_1\exists n P(n,s_1)$ where $P(x,y) : ID(x,y) \wedge \neg\exists s_2Q(s_2)$ where $Q(z) : ID(n,z) \wedge s_1\neq z$\
Notice $Q(z)$ has free variables $n$ and $s_1$ since they come from the outside $P(n,s_1)$

or wait

[vital dew]

Dilly

[oblique pelican]

lots of different ways to write it but I just split it up that way

you can write it all in one

[oak drift]

ok thx man

[oak drift]

sorry last question

can that mean anything

its ok if it doesnt cuz it's not the right answer anyway but,

[oblique pelican]

whats the question say

[oak drift]

Like "there exists a student for which "if he's a computer science student he likes to dance""

[oblique pelican]

yeah

[oak drift]

i just don't know what the B would mean

I know A is right anyway but what would B mean in english

[oblique pelican]

you said it here

it doesnt really make sense tbh

[oak drift]

ok but that doesn't make sense

[oak drift]

ohh ok well that's all I needed thx

[lime slate]

the hell are bit strings??

[oblique pelican]

I could only imagine a situation where a student only likes dancing if they take computer science (this would be the converse, but whatever)

[oblique pelican]

bit strings are just binary numbers of some length

but it doesnt necessarily need to represent a number

so its a "string of bits"

10100101010111

for example

[lime slate]

but how do i relate to the question about this?

[oblique pelican]

is there more to the question?

I don't see any bit strings to compare them to

my guess is that they mean to represent the sets by putting a 1 in every position that a letter appears in the set
so like {a,b,c,z} would be 11100000000000000000000001

[lime slate]

OH wait

that makes so much more sense yea

thanks @oblique pelican

[proper beacon]

What are some good discrete math resources to learn I'm taking a intro to discrete class and want some extra practice

[lean rover]

It is possible to fill in the table so it becomes the multiplication table for some group. Do it.

I can see the group is not abelian, and that the identity element is a. So the first column and row is filled up but how in the world am I supposed to fill in the rest?

[oblique pelican]

It becomes sudoku. If an element shows up twice in one row or column, you would get something like
[cf = cg \implies c^{-1}cf=c^{-1}cg \implies f=g ]
but each of these elements are distinct, so this is a contradiction. So you cannot have the same element show more than once in any row/column, and consequently every element must show up exactly once in every row and column.

[vital dew]

Dilly

[oblique pelican]

in this case, what i mean is you could have c*f = d and c*g = d for example

which is why youd get c*f = c* g

[lean rover]

wait what? cf!=cg tho?

I mean I do understand that there won't be any duplicates on row/ column but how can I use that to my advantage?

Sorry I remember this now. I have finished the table but I am wondering, wouldn't there multiple groups tho that satsifie this?

[oblique pelican]

satisfy the table?

[oblique pelican]

yeah i was showing why you cant have that

[lean rover]

Yest i think so

[oblique pelican]

yeah thats right

thats a good insight to show that many groups have the exact same structure (they are isomorphic)

[lean rover]

Yeah I learned isomorphism theoretically but don't fully understand it when it comes to groups tbh.

should I think like isomorphism in graphs

[oblique pelican]

I mean its a similar idea, but I wouldn't find it very intuitive to think about graphs

For groups that are isomorphic, you can rename the elements of one group to the elements of the other group (you have to rename the correct elements) and you will get the same operation table

they are basically the same group, they just look different when you write them down

[lean rover]

btw is this correct

[oblique pelican]

yeah looks good

also this is more for #groups-rings-fields

[lean rover]

This looks a little bit weird tho because the next question was to find the inverses of all elements but I am seeing a weird pattern at least when I think of it in terms of numbers but maybe I shouldn't.

inverse of a -> a
inverse of b -> b
inverse of c -> c
inverse of d -> d
inverse of f -> g
inverse of g -> f

Looks like f and g aren't following the pattern

[oblique pelican]

yeah that happens

[oblique pelican]

have you worked with symmetric groups and cycles in symmetric groups?

or permutation groups or whatever you might call them

[lean rover]

Yes but it is just a little weird for me. I have had lectures on it but it is not really clicking.

Like here if I am not mistaken, I have like a as my indntity element, whilst the Sn has a whole permutation as identity element.

[oblique pelican]

Yeah so what I was going to say is that this operation table is exactly the operation table for S_3

(1), (12), (13), and (23) are all their own inverse, but (123) and (132) are inverses of each other

It can be weird to have some sort of action as an element of a group, but the idea is that the actions can be combined to make other actions

And also there are many different ways of representing them because you can rename it to a different group and it'll have the same properties

Anyways all of this isn't too important for what you're learning rn, but just interesting to think about

[lean rover]

thank you so much for your time and the help. I will try to understand this now.

[oblique pelican]

Btw you should move to #groups-rings-fields if you have more questions about this

[lean rover]

One omre thing, I was tasked to find the order and cyclic group of the elements. I was correct on cyclic group assuming for be I wrote <b> = {..., a, b, a, b, ...} whilst in the answer they did <b> = {a, b}. Moving on tho I don't know how to find order of b. isn't it like x^n = 1 in this case b^n=a where n is the smallest, how should I think?

[lean rover]

I am thinking this is the last part of this question so moving on I will post there.

[oblique pelican]

The order of b would be the smallest n such that b^n = a since a is the identity here

Using the operation table, you can see b^2 = a

Also, {..., a, b, a, b,...} = {a,b} since sets don't have duplicate items

[lean rover]

but I was thinking it was like mod of n with addition?

That was the example in my book so I assumed we would do something like that.

[oblique pelican]

Nah

Even then, there wouldn't be duplicates

At least you wouldn't have duplicate equivalence classes

But here you aren't dealing with that

Anyways, I gotta go to bed. I hope you ace your homework

[lean rover]

This wasn't really a home work, I was doing exercises for a small test next week. Thank you so much for the help. I really do appreciate it and have a good night!

[oblique pelican]

Ah ok, good luck on the test :)

[inland zenith]

this is easy if you look at the goal as "P(x) leads to a contradiction", i.e. let x be some element in P's domain, assume P(x) and show it leads to a contradiction. here you can use your two hypothesis to derive ~P(x)

you can't assume both simultaneously so you conclude ~P(x) holds

[slim hollow]

in the convo earlier in the other channel my prof said for this homework question to only use rules of inference

[inland zenith]

this only uses rules of inference

[slim hollow]

oh okay

[inland zenith]

or can you share exactly what you may use?

[slim hollow]

i just have to add more wording?

yah one moment

but the examples in the book they never made any assumptions but at this point i didn’t know what else to do

this was my previous attempt

and my prof said to also follow this format

but the book only has two questions like this and im just unsure if it’s okay for me to claim p(c) is true

[inland zenith]

ok, so you may only use forward reasoning on your hypotheses to do the proofs?

[slim hollow]

i think so cuz when i asked in person if i can say the hypothetical syllogism by contradiction he said i can’t just say by contradiction

so i tried it this way

[inland zenith]

well what I said isn't exactly a proof by contradiction, it is related, but I suppose you still aren't allowed to do something like that

can you explain 5 here?

I didn't follow your reasoning

[slim hollow]

because i made an assumption from 2 for indirect proof

since p(c) is true

[inland zenith]

why?

there's no hypothesis that says P(c) holds

[slim hollow]

because p(c) is true for some arbitrary element c

[inland zenith]

according to what hypothesis?

[slim hollow]

from the premise?

[inland zenith]

Personally I think this is the only way to do it, you need to somehow get a hypothesis saying P holds for some element, otherwise your other hypotheses are useless

[inland zenith]

it just says IF P(x) then Q(x) for all x

it remains to be shown that P(x)

[slim hollow]

so after applying universal instantiating on the premises, i rewrite it to this?

[inland zenith]

after instantiation the hypothesis just says if P(c) then Q(c)

you still cannot conclude P(c)

[blazing peak]

then it must be false ^

[slim hollow]

sorry i am still confused

[blazing peak]

consider q(c), if you use rule of inference then if q(c) is true then p(c) must be true. contradiction comes in when if p(c) -> q(c) implies q(c) is true. if q(c) -> p(c) then it implies p(c) is true. if you use hypothetical syllogism then if q(c) is true, p(c) must be false

[slim hollow]

like i did here?

[blazing peak]

masterbuilder already told you something similiar

[slim hollow]

i’m just not good at reading it, it’s hard for me to comprehend it if it’s on text

[blazing peak]

Vc ->-P(c) thus, Vc(x) -> V-P(x)

... i can't even write it out but thats the closest i will ever get

[shrewd violet]

Wha the FUCK is up with the standard notation for joins and meets in lattices

[slim hollow]

is the V supposed to be the upside down A?

[blazing peak]

yes

[shrewd violet]

I've had half a semester dealing with them and still if everything suddenly switched to ^ is join v is meet I am pretty sure my understanding of them would instantly increase

[slim hollow]

why can’t i assume p(c) is true for contradiction

[blazing peak]

if you assume it is true...it is false since p(c) leads to a contradiction -p(c) must be true for all c

also i saw you broke up the questions above, so i was going off one pic

im not sure

[slim hollow]

like this????

[blazing peak]

🙌

you did it

[slim hollow]

i forgot to write hypothetical syllogism for 5, but other than that everything is ok?

[blazing peak]

seems clean

[obtuse coral]

if the question asks prove some equality concerning the supremum of a set can i assume that the supremum exists in the first place?

[odd heart]

Every subset of the real numbers bounded from above has a supremum.

(and often the convention is that the supremum of an set unbounded from above is infinity, although that isn't, strictly speaking a real number, but it means it's always valid to talk of the supremum of a subset of real numbers)

[past rivet]

Sometimes you also have $\sup \emptyset = - \infty$

[vital dew]

Pseudonium

[odd heart]

Also this

[obtuse coral]

its not explicitly stated that the set is bounded above, only that it asks to prove that some quantity is equal to the supremum

[odd heart]

In which case part of the proof would involve showing that the quantity is an upper bound on the elements of your set

[past rivet]

The way that supremum works is $x \geq \sup S \iff \forall s \in S, x \geq s$

[vital dew]

Pseudonium

[obtuse coral]

then could i say that f(x,y) is bounded above from this?

[past rivet]

For the $\implies$ direction you can substitute $x = \sup S$ and you get that $\sup S$ is an upper bound

[vital dew]

Pseudonium

[obtuse coral]

might be the wrong channel to ask this but

[odd heart]

Right, in this case it's entirely possible for the suprema in question to be infinite

[past rivet]

For the $\impliedby$ direction you get that being an upper bound means you’re $\geq$ the supremum

[odd heart]

(and indeed this is more #real-complex-analysis territory)

[vital dew]

Pseudonium

[past rivet]

Ooh funnily enough this one is kind of nice to use the universal property on

It’s almost designed for that

[nocturne grove]

Hi, need help with 4.9

I got 4^n * n! for 4.9 but not really sure about it

Would like some help

4.7 I got 4^n and 4.8 I got 1

If that is right

Not sure

[blazing peak]

that's right

n1! + n2! + n3! +n4! = n!
= 4n

@nocturne grove

[nocturne grove]

oh ok so 4.9 is 4^n + n!

@blazing peak

[cerulean plover]

y'all i'm malding, my professor took off 7 points on an assignment because the question asked "find out whether or not some expression is a tautology." i wrote out the truth table and then wrote "it is a contingency"

got no credit because i didn't state "not a tautology"

like bruh it's implied 😭

it wasn't like a proof either

[round torrent]

Is there any method to prove inequalities by induction?

There’s no pattern to solving them, it’s as if every question has a different form of solving

[viral crown]

just do more induction problems and you'll figure it out

maybe try Mathematical Induction: A Powerful and Elegant Method of Proof

[loud mauve]

hello, I need help with this question.

its asking to check if the argument is valid or invalid. here is what I've done so far. I don't think I'm getting anywhere

[nocturne grove]

Is my solution right?

Just want a read over, would appreciate it, thanks.

[blazing peak]

👍

[sterile walrus]

is there any algorithm to follow in order to solve proofs question?

or tips

[fossil mural]

there isn't any rigid procedure, just some general heuristics

the advice i usually give is to just, actually think about why the thing you're trying to prove is true

if you just start writing random stuff then sometimes you'll happen to run into the solution but most of the time you won't get anywhere, and that becomes more and more true as you start dealing with more complicated things or statements that are harder to prove

but if you just, look at the problem until you have an actual reason why the statement is true, translating "a reason" into the way proofs are normally written does still take practice but it's a lot easier

[brave rock]

Bee has given some good advice. I will say things in a direct way:
There are no tricks. There is no algorithm. You just have to practise.

[gusty walrus]

classic prob reminds me of the discrete math i took. miss the good times

you could also use proof by contraposition for a)

[inland zenith]

imo it is correct since the statement to prove is that at least one of b and c is even, the negation of that is that neither is even = both odd

[gusty walrus]

for the part B) ur statement "by a), if ..." is confusing. you should say that bcz 10b2 is even by what u proved in a) and so a2 has to be even by equality.

[gusty walrus]

Mb ur right

[gusty walrus]

except for this ur part b) looks good

[slim hollow]

yorkay, so if i change it to this wording other than that everything looks good?

[gusty walrus]

yes, the logic is there and seems to be correct althout @inland zenith should verify bcz im not undergraduate (i need to change that)

[inland zenith]

yeah part b looks good to me too

I would change "no common factors other than 1" to "no common prime factors"

[slim hollow]

ohh okok, i just used no common factors other than 1 because i was referencing the slides

[inland zenith]

it's the same

you can keep it

[slim hollow]

gotcha

[inland zenith]

but 1 is irrelevant as a common factor

i.e. all numbers share 1 as a factor so it provides no information

so to me the other wording is better

[gusty walrus]

1 and itself (felt the need to add that lol)

well we conclude that a*2 is even which from that we conclude that a is even

although i think that ur teacher will understand wym

like more precision is better, but u dont have to

[slim hollow]

yeah i wanna practice getting better so i’ll change it again

[gusty walrus]

lol, for the assignement i would. for homework i write wtv as long as u understand it

[slim hollow]

yeah i’m practicing in mind of the midterms/final exam, so obviously being more precise is better

so do i just take out the 10b^2 part?

[chrome nexus]

The set of integers with squares less than 100 is not a subset of the set of nonnegative integers because −1 is in the former set [as (−1)2 < 100], but not the latter set.

Does this mean :
lets say a = { x| x<100 x E z}
while b = { x| x<100 x E z+}
so a != b?

[brave rock]

Yes

If you're looking for a direct translation of the fact above, that's not it, but still what's written there is true.

The question was about x^2 < 100, not x < 100.

[chrome nexus]

oh yes i see ,would it be:
a = { x| x^2<100 x E z}
b = { x| x^2<100 x E z+} ?

[brave rock]

And indeed these sets are unequal.

[chrome nexus]

thank u so much

[gusty walrus]

no that part is important (in my humble opinion)

(also unless it is like a formal paper u can add parenthesis for precision)

[frosty blade]

Can someone help explain bicondtional statements cause it is breaking my mind. I am confused what "if and only if means". I think "if" means p -> q and the "only if" means q -> p but I dont get how the "only if" means that. It just sounds the same as the first one but more emphsied

[gusty walrus]

lol, relatable

[oblique pelican]

p only if q means p -> q. I agree that this terminology is cringe, but it is saying that "the only case where p can be true is if q is true" because otherwise if q is false, then p being true would create a contradiction as it implies q is true, hence p only if q. Then "p if q" means q -> p, which just means p is true if q is true. "If and only if" means that both statements imply each other, or in other words, they are equivalent in their meaning.

For example, "A shape is a square if and only if it is a rectangle and it has 4 equal sides". A square is definitely a rectangle with 4 equal sides. This doesn't necessarily throw out the possibility that some rectangles with 4 equal sides aren't squares, but we know a rectangle with 4 equal sides MUST be a square, so these are equivalent statements.

[frosty blade]

Thank you. The english breaks my mind reading repeatly but Il just remeber p only if q means p implies q.

[oblique pelican]

Yeah I really dont like "only if"

I have to think about it so much when I read it as well

[gusty walrus]

to be honest, most math prob wont use confusing terminologies

like they will use the most simple if then statement in fear of confusing the student/ reader.

[brave rock]

It's very very rare to see people use "only if" in practice. Don't worry about it too much.

[gusty walrus]

also thats not the point of math papers

[oblique pelican]

yeah "p if and only if q" shows up way way more than "p if q" or "p only if q"

[little prism]

well 30^2 is still fair enough to compute

x-29 being positive is not enough, its also important that its at least 1

rest is fine

[slim hollow]

its cuz it says more than the average person can do in their head tho

[slim hollow]

so i just need to add that part to case 2?

[little prism]

well ok we arent supposed to be that realistic that people arent able to compute 9*100

[little prism]

yes

[pulsar vigil]

Hey, Im learning digital systems boolean algebra is there a channel that i can ask questions in?

discreate have similar concepts so that why i poped in here

[brave rock]

I'd just ask the question and people will point you elsewhere if necessary

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[cobalt crown]

how would i determine the asymptotic complexity of $T(n) = T(4n/5) + n \log n$ using the master theorem?
the only applicable case seems to be the third (since the critical exponent is 0 and $n \log n \in \Omega(n)$), but i cant seem to verify the regularity condition

[vital dew]

Yilian

[cobalt crown]

nevermind, it does work out

[burnt nebula]

is this ordered from least to greatest correctly?

isnt 100^100 bigger than 100!

since it's 100 x 100 x 100 vs 100 x 99 x 98

[gusty walrus]

I think ur logic is correct, but do u have the answer sheet?

[burnt nebula]

i dont

[gusty walrus]

I think it's correct

100! Is smaller than 100*100

[burnt nebula]

what I dont understand is chatgpt says it's not

[gusty walrus]

Chatgpt says a lot of things...

[burnt nebula]

true

actually i think i seeit now

[gusty walrus]

Copilot says that 100*100 is bigger

[burnt nebula]

i mean when i break it down smaller

10^10 is bigger than 10!

[fossil mural]

100! is 93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000 and 100^100 is 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

[burnt nebula]

so 100^100 should be bigger than 100!

[gusty walrus]

Also if u want an Actuall number u can use sterling's approximation

[fossil mural]

so yeah you can see pretty clearly here which one is bigger

[burnt nebula]

what's sterlings approx

[gusty walrus]

It approximately a factorial

Although @fossil mural used a computer to calculate it

I assume

[fossil mural]

yes

[burnt nebula]

okay so 100^100 biggest got it

[gusty walrus]

But if u wanna do by hand use sterling it's not exact but good enough for this kind of comaprison

[gusty walrus]

Ur logic was right as well, trust urself

[burnt nebula]

actually my next question is a sterling one lol

[gusty walrus]

#slay

👀

[burnt nebula]

Is there another way to write the stirling formula

so lets say n = 10

idk how to write that in discord lol

[gusty walrus]

#latex

U prob wanna learn latex if uare going into math

[burnt nebula]

alright that's a bonus q ima skip it for now

[gusty walrus]

Loll

Relatable

[burnt nebula]

you use overleaf?

how would i write that in latex

[fossil mural]

${x \in \mathbb{Z} : |x| \leq 10}$

[vital dew]

bee [it/its]

[gusty walrus]

Personally u just try and hope itworks

[burnt nebula]

nice okay thank you

[gusty walrus]

Alsouse google most commands are gonna be in there

[burnt nebula]

just to answer that problem..

[fossil mural]

for me it's mostly been just, if you use it a lot you learn what the code is for each symbol you use often

[burnt nebula]

is the cardinality 11?

[fossil mural]

no

it says Z so numbers like -2 are going to be in this set too

[burnt nebula]

ohhh

if it said \mathbb{N}

[fossil mural]

(although $-11$ won't be because $|-11| = 11 \not\leq 10$)

[vital dew]

bee [it/its]

[fossil mural]

yeah if it was N, and if N includes 0, then you would have been right

[burnt nebula]

Okay so 21

[gusty walrus]

Waittt, the bars are u saying abs value or cardinality

[burnt nebula]

cardinality

[gusty walrus]

Bcz it means 2 diff things

[fossil mural]

presumably absolute value

[burnt nebula]

o

[fossil mural]

i mean like, what's the cardinality of -4

or the cardinality of 6

[gusty walrus]

It's 1

[fossil mural]

so -4 contains exactly one element?

[gusty walrus]

Bcz there is only 1 element

[fossil mural]

what is that element then?

[burnt nebula]

i think it's saying the |x|, the cardinality of X not absolute value

if x is equal to some integer less than or equal to 10

[gusty walrus]

Actually cardinality doesn't make sense here

[fossil mural]

ok well that wouldn't make sense even with this interpretation of the notation

[gusty walrus]

Yeah it's absolutely value

[fossil mural]

``$|x| \leq 10$'', if $|x|$ means cardinality, is saying that the \textit{cardinality} of $x$ is at most $10$

[vital dew]

bee [it/its]

[burnt nebula]

luckily the back of the book has the answer to this one

it says 21

[fossil mural]

makes sense

{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

10 positive numbers, 10 negative numbers, and zero, makes 21

[burnt nebula]

yup

ive been getting marks off bc i have confusing explanations on my HW lol

[gusty walrus]

Ngl

U probshould have sent the questions well

[burnt nebula]

oh it was jsut "Find the cardinality of the following set" my bad

[gusty walrus]

makes sense now

💀

[burnt nebula]

so can i prove it by saying like because there are 21 integers from {-10, -9, -8, ..., 0 , ... 8, 9, 10)

even though its asking for cardinality it's also talking about absolute value no?

[gusty walrus]

So basically the question is abt cardinality

But the ${x \in \mathbb{Z} : |x| \leq 10}$

[vital dew]

summer harry

[gusty walrus]

Is an absolute value

So there is 11 elements

@fossil mural

Agree?

[fossil mural]

that is an absolute value, but no there are 21 elements

because something like x = -5 also satisfies |x| <= 10

[burnt nebula]

that makes sense thank you

same question

[gusty walrus]

But abs tho

Oooh yes

[burnt nebula]

would this be 2^8 = cardinality of 256?

[gusty walrus]

Yeah 21 elements

Never seen that sort of writing

Cant help

[burnt nebula]

might be better, it's letter F

[gusty walrus]

💀

Idk what that means

[vivid sinew]

for g would it be false?

[brave rock]

Some authors use $\subset$ to mean that the sets are not equal, but some use it to mean that they may or may not be equal. Since the two sets in (g) are equal, unfortunately you need to refer to whatever convention your professor/notes/textbook has.

[vital dew]

Boytjie

[brave rock]

see above

[quaint flower]

Does anybody know boolean algebra here?

So, I am currently trying to understand why I cannot do this:

A + notA AND B =

A AND (notA + B) = AB

And my reasoning is, using duality.

Where:

A + B = Y
is equvilent to:

A * B = Y

[inland zenith]

I don't follow

your claim is that A + (¬A * B) = A * (¬A + B)?

[quaint flower]

Nevermind, I understand where I went wrong.

You have to use absorption law. So: A + (notA * B) simplifies to A + B.

Duality is only used to relate two expressions, they are not logically equvilent.

That was my error.

[quaint flower]

and yes, but I de-bunked myself.

[valid python]

hey i got a question guys

im prepping for an exam thursday

and i cannot for the life of me

think of a function for N -> Z

where it is onto, but not one to one

would i have to use something like a piecewise function or the sort?

[grand totem]

that's a good idea

it's a rather common exercise to come up with a bijection between the two. i'd suggest you attempt that first (or review the solution if that exact problem has been done in class already) and then see if that helps you come up with a surjection that isn't injective

[valid python]

we havent done an exercise lol

but its on the review guide

could x^3 be considered? considering that its the set of all natural numbers

[grand totem]

n |-> n^3 is one-to-one but not onto Z, so no

[valid python]

damn

not x^2 either

yeah a piecewise function is the way to go huh

[little prism]

it often is

[valid python]

huh

honestly kinda gross

how do i even go about figuring that sort of thing out? like what if it asks for any set or something along those lines

linke R -> R

like*

well for that xsin(x)

maybe a bad example

[oblique pelican]

a common enumeration of Z is 0, 1, -1, 2, -2, ... or 0, -1, 1, -2, 2, ...

so you can try getting to that

@valid python

[terse wyvern]

personally i never use the symbol $\subset$. best to stick with $\subseteq$ or $\subsetneq$.

[vital dew]

treesarentreal.com

[odd heart]

I think this hugely varies between fields; in real analysis, measure theory or probability I'd say it's fairly standard to use $\subset$ to mean weak inclusion

[vital dew]

Outsider

[odd heart]

Mostly because strict inclusion is hardly ever something you want to particularly distinguish

[tacit aurora]

can somone help me in this please

[vivid osprey]

When can we interchange union and intersections? Only when both are finite? I.e. $$\bigcup_{i\in I}\bigcap_{j\in J}=\bigcap_{j\in J}\bigcup_{i\in I}.$$When is this legit?

[vital dew]

psie

[odd heart]

Basically never

[fossil mural]

when one of I or J has at most one element

[odd heart]

The epitome of "true but not very useful"

[fossil mural]

well i meant that that's both a necessary and sufficient condition

[brave rock]

C.f. when can we interchange exists x and forall y

[fossil mural]

for some particular families of sets it can work outside of that but for arbitrary families it's only if one of them is a singleton

$\bigcup_{i \in {0,1}} \bigcap_{j \in {0,1}} {x : x = 0 \land i = j} = \varnothing$ \ $\bigcap_{j \in {0,1}} \bigcup_{i \in {0,1}} {x : x = 0 \land i = j} = {0}$

[vital dew]

bee [it/its]

[brave rock]

I think this is best summarised by saying that these just mean very different things

[vivid osprey]

ok 👍

[fossil mural]

yeah it's the difference between $\exists i \forall j$ and $\forall j \exists i$

[vital dew]

bee [it/its]

[fossil mural]

$\exists i \forall j (i = j)$ is false, $\forall j \exists i (i = j)$ is true, and that's basically what this example amounts to

[vital dew]

bee [it/its]

[odd heart]

Very good (counter)example

[terse wyvern]

"basically never" infinitely often or eventually?

[odd heart]

I'm not sure how those terms would apply here.

[terse wyvern]

nvm it's a silly joke

[tacit aurora]

<@&286206848099549185>

[frosty blade]

can someone define what a predicate is? In the book Im reading (Rosen) its called a property but the more I search its called a function.

[brave rock]

Don't worry too much about the details. The idea is that a predicate is a proposition that needs a thing as input. So for example P(x) being defined as "x is mortal" is a predicate. I need to feed it a thing -- namely x -- in order for it to be a proposition.

The function/property thing is either technical detail that would be decided in a foundational system or simply terminology.

[frosty blade]

ok thank you

[brave rock]

Slight addendum, I really should have added this.

[brave rock]

Then e.g. P(Socrates) is the proposition "Socrates is mortal."

I hope that's clear.

[frosty blade]

It is, thank you

[frosty blade]

Can someone define what predicate logic is? I am confused what it can do that propostional logic cant.

[brave rock]

Can you express "if a number is divisible by 4, then it is even" in propositional logic?

You cannot.

You need predicates to express this.

[frosty blade]

couldnt you make p = "a number is divisible by 4" and q = "it is even" to make p→q

[brave rock]

No

"a number is divisible by 4" is true

"a number is even" is also true

But this isn't the implication I'm talking about

I'm saying if x is some number, and if x is divisible by 4 then x -- the same number! -- is even

This is actually, if you like to think about it this way, an infinite collection of propositions

The proposition 1 is divisible by 4 => 1 is even, 2 is divisible by 4 => 2 is even, 3 etc

Propositional logic cannot express this

The example I gave is not of the form $A \implies B$, it is of the form $\forall x(P(x) \implies Q(x))$.

[vital dew]

Boytjie

[frosty blade]

So predicate logic allows you to talk about the logic of 1 propostion multiple times

[brave rock]

Sure, idk exactly what that means but if that's how it fits in your mind then OK

[frosty blade]

ok thank you

[oak drift]

Anyone has a hint as to how to prove this?

I can provide the list of laws I can use

like it makes very much sense in my head but I just dont know what to transform

ALSO, I can use the " -p ^ q = p->q " law

[fossil mural]

given that nothing in this table mentions $\to$ i think your first step has to be replacing each $p \to q$ with $\neg p \lor q$

[vital dew]

bee [it/its]

[oak drift]

yeah I did that

ohhh wait no you're right there's line that links the two big premices

I didnt do it

[fossil mural]

...?

[oak drift]

wait ill draw it

Green = I simplified it

red I didnt do

[fossil mural]

oh right, yeah that makes sense

[oak drift]

well not simplify but transform you get what I mean

im still blocked 🥲

[fossil mural]

uh ok wait i actually haven't solved this so give me a second to work out what expression you get by doing this

$\neg((\neg p \lor q) \land (\neg q \lor r)) \lor (\neg p \lor r)$ i think

[vital dew]

bee [it/its]

[fossil mural]

wow yeah this is a mess

[oak drift]

im starting it over to see if I did a mistake but yeah its a mess

am I allowed to just say that in this situation (where I transformed some of the expressions), if q is true, then p->r and if q is false, p->r

[fossil mural]

i mean that's correct in the sense that reasoning like that can't prove an identity that's false, but i have no idea if whoever asked you to solve this would accept that as an answer

[oak drift]

wait no I HAVE to use the laws I posted

I can't use anything that isn't in the table I posted

except -p/\q = p->q

I can also use that

[fossil mural]

yeah in that case i think you just keep rewriting things until you get somewhere useful

[fossil mural]

(it's -p v q actually)

[oak drift]

wait yeah sorry

[fossil mural]

starting from here the obvious first step is de morgan's law just to get rid of that annoying first negation, because otherwise there isn't really anything useful you can do with the stuff on the inside

so you get $(\neg(\neg p \lor q) \lor \neg(\neg q \lor r)) \lor (\neg p \lor r)$

[vital dew]

bee [it/its]

[fossil mural]

(if you actually have to explicitly invoke the commutative and associative laws then that's going to get really tedious)

then if you use commutativity and associativity of $\lor$ to rearrange that into $((\neg(\neg p \lor q) \lor \neg p) \lor (\neg(\neg q \lor r) \lor r))$