discrete-math

[past rivet]

How do you actually do that?

[fossil mural]

you... kind of just translate each part of it and it works? i don't really see why there would be a problem

"for every statement P in the language of first-order arithmetic, if there is a proof of [a translation of P into the language of first-order set theory] from the axioms of ZFC, then (N, +, *) |= P"

[past rivet]

Hm, then my issue is probably a lack of knowledge on how these translations are done. Where could i read about that?

[coral parcel]

It is important here that "is true" is interpreted as "true in (N, +, *)" which is a set ZFC can speak about.

Also beware that just because you can form that statement in the language of ZFC doesn't mean ZFC can prove it.

[fossil mural]

well anything that proves the incompleteness theorems should involve defining the notion of "proof", because that's one of the key parts of it (the statement that the theory is consistent is just expressed as "the theory does not prove [obviously false statement]")

[past rivet]

Oh interesting, i thought it’d be a lot more complicated than that

The statement of consistency that is

[fossil mural]

for the definition of ``$(\mathbb{N}, +, \cdot) \models P$'', you kind of just do recursion on $P$, for instance $(\mathbb{N}, +, \cdot) \models \varphi \land \psi$ iff $(\mathbb{N}, +, \cdot) \models \varphi$ and $(\mathbb{N}, +, \cdot) \models \psi$

[vital dew]

bee [it/its]

[past rivet]

In this case the $\land$ is internal and the “and” is external?

[vital dew]

Pseudo (Cat theory #1 Fan)

[coral parcel]

It's implicitly assumed here that the proof system is a remotely conventional one where proving a contradiction would mean you can immediately prove everything. That gives a wide range of equivalent ways to state "is consistent", of which you can pick the one that suits your purpose best.

[coral parcel]

Yes.

[random sparrow]

$\textbf{Exercise 3}$ Can it happen in any base that the sum of two fixed-precision numbers has a carry greater than 1? Provide an example or prove the opposite.

[vital dew]

Renato

[random sparrow]

hopefully the translation is accurate but
in a sum of two numbers of same base, the maximum digit that you can have is like (b-1) where b is the base
say for example the rightmost digit where we have 0 carry for now
you sum (b-1) + (b-1) you get 2b - 2 + 0
so this leads to next digit with 1 of carry
we do (b-1) + (b-1) + 1 now and we get 2b -2 + 1
which leads to carry 1 again
the thing is, intuitively it seems like carrying 2 out of two same numbers of same base is impossible because (b-1) + (b-1) is the max + the carry, we would need a carry of >= 2 for it to be possible

[spark field]

In the ones place that's true but what if you also have a carry from a previous place(?

Oh you covered it
Nvm my question then

[sick grail]

-# i think that's the last bit, even if it is a little poorly phrased

[random sparrow]

not necessarily in binary (base 2), in any base, the max digit for each digit in the number is b - 1

[random sparrow]

in the rightmost digit of the number we start with carry 0

[spark field]

Yes, I agree with your logic now

[random sparrow]

say for example

00001
00001 +

we sum this, we get 1 + 1 = 0 with 1 of carry
we sum this we get 0 + 0 + carry = 0 + 1 = 1

if the base is 2, b = 2, the maximum digit we can have in every digit is 1 , aka b - 1

now say for example hexadecimal

0xC0FFEE + 0xCOFF00

C0FFEE
C0FF00 +

C -> 12
F -> 15
E -> 14

we do 14 + 0 = 14 , zero carry since 14 < 16
we do 15 + 15 = 30, since its floor(30 / 16) = 1 we get carry of 1
we do 0 + 0 + carry = carry = 1
C + C = 12 + 12 = 24 >= 16 , but since 24 < 32 we get carry of 1

basically we get

1-8-1-15-14-14-14
which is
0x181FEEE

[spark field]

You already wrote a proof, and I agree with it, no need for a demonstration 😆

But yes

I agree with the demonstration as well

[random sparrow]

i mean to prove it formally we would need induction

but.. we get the gist of it

[spark field]

I think that the implicit induction you use is fine, someone with more experience with this specific subject may disagree though

Ah, I guess technically it isn't implicit

Sure then

Not that it would change much from what you wrote

[random sparrow]

care to elaborate?

[spark field]

I thought it was implicit but when I wrote out my cases I realized that it depended on the assumption of an induction hypothesis

So it would have to be written explicitly

as you said

[random sparrow]

can you help me with the proof

[spark field]

What part do you need help with

[weary tiger]

I would like to see if anyone can check my proof of a problem in a book

[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.

[weary tiger]

Its problem 3.1 letter d

This is my proof

And the definition of o(n) I am using

[spare slate]

Forgive me if I'm being thick, but does not not implicit assume that all of the coefficients are non-negative?

You're only given that a_d is positive

not anything about the other coefficients

[weary tiger]

You are correct

I did not see that

[spare slate]

The definition of little-o notation also mentions a lower bound, which you hve not addressed (granted this is trivial, but you should still mention it).

[spare slate]

You also start with the inequality that you're trying to prove, which can be interpreted as you assuming what you're trying to prove (big no no). Usually, you'd start with your assumptions/definitions. So something like "Let c>0 be an arbitrary constant..."

[weary tiger]

That was more of a test case to figure out how to solve for n0

My thought process was if this inequality were true then the expression in the radical would be less than n

I can then choose n0 to be greater than the radical expression without the powers of n in the denominator

[frail sage]

Can someone please help me with how to get started on this problem?

[grand crown]

try a similar strategy pigeonhole principle. consider every sequence of k adjacent numbers around the circle. what is the overall product of products?

[frail sage]

I know I have to somehow apply the pigeonhole principle but tbh I really don’t see how it applies..

[grand crown]

did you do this

[frail sage]

I’m not sure I entirely understand what you suggested I do, but I think it will be the product of P(n,k) for every k that there is? P(n,k) being n * (n-1) * … * (n-k+1)

[grand crown]

not exactly

i guess let's go through the motivation of pigeonhole principle

the idea is that if i have n boxes and more than nk balls, at least one box has more than k balls, right

[frail sage]

Yes

[grand crown]

one way to think of this is that if every box had <= k balls, then the overall sum of the balls would be <= nk

in some sense looking at an accumulation of buckets gives us information about how big individual buckets have to be

here, each bucket is one of the sequences of k adjacent numbers

how many buckets do we have?

here's an example, let n = 7 and k = 3

let's say the numbers are ordered as

1 3 2 4 5 7 6

then one sequence is 1 3 2. another is 7 6 1. how many sequences can we form in all?

the idea is that for each sequence, you can compute its product. then you can compute the product of the products. this is where pigeonhole comes into play:

if all of the sequence products are "small", then the overall product of products would also be "small". so, if the product of products is "big", then at least one sequence product is "big"

it's just that instead of adding and dividing like in regular pigeonhole, we use different operations

[frail sage]

n right? Because it’s around a circle so it wraps around?

[grand crown]

yup

[frail sage]

Right so we’re finding an upper bound which means we focus on how big the smallest sequence at least has to be when it’s of length k?

Is that correct?

[grand crown]

its a lower bound on the maximum bucket size

but yes

the rest of what you said is correct

[frail sage]

Right right, bucket size

Okay thanks a lot, that gives me a place to start!!

[grand crown]

this strategy will work, you just need to figure out what operations to use and how to compute the product of products

[rugged sky]

Hello everyone!

I am studying combinatorics, and everything was going fine until I had to solve problems involving sums with binomial coefficients. I don’t have many problems with the combinatorial part itself, but rather with manipulating the sums to get the desired result.

Could anyone suggest any resources that I can use to improve my skills in working with summations?

Thanks in advance!

[vernal wave]

There's a very tough book by Knuth et. al. with lots of hard exercises -- if I recall correctly, "Concrete Mathematics" is the title. There's also a great book, not as hard, also great content, written recently by Douglas West.

I don't know of any resources other than textbooks for this, and I suspect (but could be proved wrong) that textbooks are going to be the best resources that you're going to find for it.

[past rivet]

is this proof fine?

[rugged sky]

Thanks

[wooden python]

no it's too purple

[misty hatch]

Guys, I’m stuck 😭

[dense mountain]

Hi everyone! I’m looking for help with the Principle of Vacuity. I understand the predicate notation (∀x∈∅,P(x)), but I’m struggling to internalize ∅⊆A or the cases A⊆B with false P->Q purely through the lens of set inclusion. I’d like to understand it as a relationship between sets rather than just a 'default' logical implication. Does anyone have any resources or an intuitive explanation for this?

Ive been doing a TON of research on this but I still can't quite go on sorry for long msg

[winged delta]

A vacous truth is where there is nothing for it to be true about, so it is true

"All the elephants in my office are pink"

Is true vacously because there are no elephants in my office (to my knowledge)

In terms of sets, you just need that fact about ∅⊆A really

The set of elephants in my office = ∅

The set of pink elephants = A

The idea of a false premise proving anything could then be seen as following from translating "if P, then Q" into set language: "the set of x such that P(x) is a subset of the set of x such that Q(x)"

[slim geode]

You've got 7 equations of 7 variables there... Why don't you use Gaussian elimination to solve it?

[cosmic topaz]

this questions has some value wrong ...i checked it.....

your method is fine but use this instead after rechecking the wrong values given in question..
use this formula from set theory :
n( T or P or B) = n(T) + n(P) + n(B) - n(T and P) - n(P and B) - n(B and T) + n(P and B and T)
Also T,P and B in above are different than what u have described in your answer. T is tacos ( 50 acc to your question) and so on......

your required answer gonna be n(T) - n(T and P) -n( B and T) + n(B and T and P)

[valid willow]

isn’t this paper too much to except from first year undergrads?(except first and second q)

[vernal wave]

It's not easy but it's not unfair. You're not, like, solving stuff that couldn't be learned after a week or two of study.

[misty hatch]

Man, I feel so stupid reading this

[misty hatch]

Wasnt taught that

Took the exam just now and that question wasn't even on it. So upset

[slim geode]

It's a well arranged way to solve systems of linear equations

[blazing fern]

Love this book!!

[willow owl]

https://share.google/images/LhSWmVqKAb780M7Pr

Penultimate Venn Diagram

[blazing fern]

if that’s the penultimate one what’s the ultimate one

[odd heart]

It's the same one but without the pen

[willow owl]

DNE

[spark field]

<@&268886789983436800>

[lethal hearth]

Is the equivalent or form and the logical negation of a problem always the same formula?

[grand totem]

could you clarify, in particular what's 'the equivalent or form'?

[thick owl]

Hello everyone.
Does anyone know of a resource, whether videos, notes, or a book, that explains difference equations well, especially the complementary function and particular integral?

[dull briar]

Have you seen markiplier thumbnail

For Elden Ring

[willow owl]

No

https://klipy.com/gifs/ups-error-1

[lost ridge]

Hello everyone
Im currently doing DM1 for my CS degree and trying tho make sense of some exercises about the principles of addition and multiplication (i think these are basic but i tend to struggle with math alot).

One of them goes as follows:

A, B , C and D are nodes of a computer network. There are 2 paths between A and C, 2 between B and D, 3 between A and B and 4 between C and D. Throug hiw many paths can a message form A to D be sent?

[little prism]

draw the situation

then draw all paths between A and C

if you feel adventurous, draw all between A and D

uh wait I skipped the text they arent in a line

well step 1 is to draw the situation anyway

honestly you can draw all between A and D

sometime during the process it should get clear what is happening

[analog hound]

$x\geq y$ and $x\not>y$ do not imply $x=y$ in an arbitrary poset, right?

[vital dew]

person2709505

[little prism]

x >= y means x>y or x=y unless you are very weird

[analog hound]

Well the axioms for poset I've seen just describes certain rules >= must satisfy

[little prism]

then they define x>y as meaning x>=y and x!=y

same thing

[analog hound]

Oh hm

Very good, thanks. My faith in the = sign and its meaning is restored...

[lost ridge]

But how would i go about drawing it out though?

[little prism]

draw 4 dots, call them A,B,C,D and connect them with lines

two lines between A and C, 2 between B and D and so on

[lost ridge]

Im just not sure if they should be linearly laid o ut or not though

Out*

[little prism]

just try things

[lost ridge]

aight

[lost ridge]

I got something like this but i think its incorrect since there are more than 3 paths from A to B

[lost ridge]

.

[lost ridge]

<@&286206848099549185>

[prisma vapor]

Helpful LMAOO

[lost ridge]

Im actually so confused bruh

Still havent figure it out

[coral parcel]

The problem statement doesn't mention any paths directly from A to D, or between B and C, so I think we ought to assume there are none. Thus those edges should not be part of the drawing.
With the way it is described it sounds like you can get from A to D by going through B (with several choices for each of the two stages) or going through C, but not by going through both or neither.

[spark field]

For a poset? they could be uncomparable no?

[coral parcel]

Yes, but then would write neither x >= y nor x > y nor x=y.

[spark field]

Oh right

Xd

stupid me

[spark field]

Hmmm

Here let me draw something that might help

[lost ridge]

If i remove both of those connections, i end up only having 2 paths between A and B (and if im correct there would only be a max of 2 paths connecting any 2 given points)

[spark field]

If I say, as an example, "there are two paths between A and B and three paths between B and C", here is what I imagine:

Where I can get from A to B using the top path or the bottom path (2 choices)
And then from B to C using the top path, the middle path, or the bottom path (3 choices, independent of the previous 2)

By the multiplication rule, there are 2*3 = 6 ways to get from A to C:

top top
top middle
top bottom
bottom top
bottom middle
bottom bottom

I believe you should be approaching your problem this way, does this example make sense

[lost ridge]

It does thank you

So by that logic (if i understood it correctly), then there would be 4 paths from C to D (independent from the other 5) and by applying the multiplication pricinciple id have:

234 = 24

Therefore 24 ways of getting from A to D (?)

[spark field]

Not quite

Almost there though

[lost ridge]

Oh wait you used an example my bad

[spark field]

Ah yeah 😅 not your exact problem

[lost ridge]

😭

[spark field]

For your problem, you'll need to split into cases (to apply the sum rule)

I'll provide an example of that now so you can see

Not the best drawing I've ever made but xd

Here I have cases

If I want to travel from A to D

Leaving A, I can either go to B or to C

There is 1 way for me to go from A to B
Then 3 ways for me to go B to D
By multiplication rule, there are 3 ways for me to go A -> B -> D

There are 2 ways for me to go from A to C
And 3 ways for me to go from C to D
So 6 ways to go A -> C -> D

These are the only ways for me to get from A to D
The total number is 11

(excluding the possibility of going backwards)

So now I've applied the sum rule

[lost ridge]

11?

[spark field]

9

Sorry

I can't add

[lost ridge]

Ah

I got confused lmao😭

Thanks a lot

[spark field]

No problem, it's still not your problem (you'll have to draw that and do it yourself ) but hopefully it's clearer now

The traversals (vertex paths) get added
Within each one you can make decisions of which connection to walk down (so those get multiplied), but they ultimately lead you to the same place (the next vertex in the traversal)

In general, multiply when you can do different things to get to the same next step
Add when you have to take different next steps (of course, everything works towards the same final ending)

[spare slate]

orz u

[spark field]

I was gonna wait till you got here and give the problem to you but you didn't come so I tried myself

[spare slate]

scrolling up hard I see pictures

[spark field]

original

[lost ridge]

I got 14

[spark field]

That's what I get as well 💃

[lost ridge]

Thanks man i appreciate it
I gtg sleep now tho, cya

[spark field]

👋 glad to help, sleep well

[lost ridge]

Ive woken up and ive got another one:

"Referring to the set of whole numbers between 100 and 999 (inclusive), how many of them are divisible by 4?"

When it was 2 and 5 it was easier to figure out due to the divisibility criteria being directly tied to the last number but im having trouble now that the criteria for being divisible by 4 is very specific.

[cosmic lake]

how to be a math guy to master it for AI track

[vestal bronze]

The criteria is you skip 3 numbers, you're not supposed to use the divisibilty tricks

there are 900 numbers if you separate them in fours, there will be one number in each group, so it's 225 total

[lost ridge]

But wait wdym i skip 3 numbers? I didnt really understand that part

Could you explain it differently?

[little prism]

lets start listing all the numbers

we have 100, 104, 108, 112, ...

which are 25*4, 26*4, 27*4, 28*4, ...

we continue and arrive at 980, 984, 988, 992, 996

which are 245*4, 246*4, 247*4, 248*4 and 249*4

can you now think about a way to count them?

[vital cloak]

Can anyone help me with breaking down IEEE half-precision? I don't really sure about this

For example for 5555 base 16 how would I transfer to decimal

[coral parcel]

Is that significantly different from single or double precision, other than the fields having different lengths?

[vital cloak]

Can you explain it simpler? English is not my first language so

In my course we only deals with rationals and double-precisions

"Half-precision floating points" they say

Mainly about hexadecimals in IEEE

For instance, they calculated things like this

[coral parcel]

If you know double precision, a value there is represented as 64 bits, of which there's 1 sign bit, 11 bits of (biased) exponent, and 52 bits of mantissa (with an implicit leading 1).
Half precision works pretty much the same way, except there are only 16 bits in total, divided into 1 sign bit, 5 exponent bits, and 10 mantissa bits.

[vital cloak]

I see

But how come they can do the operation n+15=21 over there?

[coral parcel]

15 is the exponent bias, just like double precision represents the exponent with a bias of 1023.

So the value represented there is +1 × 2^(21-15) × (1.0101010101)_2.

[vital cloak]

so they remove the first bit for sign indicators, then the next 5 bits are for exponent

the rest is mantissa a.k.a. fraction part

[coral parcel]

Yes.

[vital cloak]

Alright, thank you for your explanation!

Just doing quick revision for exams after term break ;-;

[glass summit]

Hi, is anyone willing to check over my work? The question is bit detailed but I've attempted it and would really appreciate if someone can have a look at it. It's related to Turing machine

[daring gyro]

!da2a

[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.

[bleak spoke]

my prof is asking us to describe symmetric differences of sets
ex.
Some sets, A, B, C

The symmetric difference of A and c is equal to the symmetric diffrence of B and C which implies that A and B are equal.

im not super sure what hes on about because symmetric differences are not in the text book at all. if anyone could explain to me what this means it would be greatly appreciated

I seem to think it means that its the set of elements that are exclusive to either set in the difference but i want to make sure

[little prism]

yes the symmetric difference of A and B are those elements which are exclusively in A or exclusively in B

in symbols you can also write it as $(A\setminus B)\cup (B\setminus A)$ or $(A\cup B)\setminus(A\cap B)$

[vital dew]

Denascite

[bleak spoke]

okay thanks.

another thing is hes asking about cardinality for example what is the cardinality of the empty set which also doesnt make sense because isnt cardinality comparitive?

[little prism]

no

asking for the cardinality of the empty set is a question that makes sense

[fossil mural]

if the only definition you've seen of cardinality is things along the lines of "X has cardinality at most Y iff there is an injection from X to Y" then you're right that it wouldn't make much sense

but for finite sets you can say that the cardinality of the set is the natural number n for which the set has a bijection with the set of natural numbers less than n (assuming a convention where 0 is a natural number)

so for instance the cardinality of the set {A, B, C}, where A, B, C are any three distinct things, is 3, because you have the bijective function that maps A to 0, B to 1, C to 2, and {0, 1, 2} is the set of natural numbers less than 3

(which agrees with what you'd intuitively expect - it's just the number of elements in the set)

[cunning slate]

Hi everybody, why is AoC considered an axiom? It honestly seems derivable to me. Don't get me wrong idk how to derive it, but it feels like it should be right?

Actually I just realized that I am wrong.

I was arguing based on personal feelings rather than actual logic.

[coral parcel]

And that's why it's considered an axiom.

It feels intuitively safe enough that it surely has to be true, and at the same time the other axioms of set theory are not enough to prove it by themselves.

[frosty mulch]

pssst

who’s ready to do some math

discretely

[coral parcel]

No, that is "discreet", not "discrete".

[robust monolith]

Discretion

[drowsy marlin]

Prepping for a final exam and combinatorics and graph theory will be large components of it. The course covered counting sets using perms, combinations, etc, proofs using set theory and integers, and counting the size of binary relation spaces by their properties using Sterling numbers. Mostly follows Grimaldi's combinatorics textbook.

Any recommended methods for reviewing these topics? I find the course is very heavy on definitions and I didn't feel that I got enough guided practice because of it.

I didn't fall behind on definitions, so mostly wondering if there's efficient ways to spend this time besides rereading the textbook and doing each of the hundreds of practice problems in this course's scope

Because going back over every practice problem leaves me a little unchallenged and takes a lot of time.

[frail sage]

Honestly doing the problems is always the most efficient way of using your time

Going over problems you’ve done before and know how to do can give you a false sense of confidence

[drowsy marlin]

Yeah, for sure. A lot of the problems in the textbook don't match the difficulty/complexity of the exam problems to-date.

But I can certainly cherry pick the ones that are close.

[frail sage]

Also sorry for posting my question right after but I’m wondering whether this proof is more “mathematically rigorous” than just saying “all possible degrees are 0 to n-1 but since we can’t have both 0 will either be replaced with smth from 1 to n-1 or n-1 will have to be replaced with smth from 0 to n-2” and finishing the argument there.

This is the question: Prove that for any graph $G$ of order at least 2, the degree sequence has at least one pair of repeated entries.

This is the proof I wrote:
We can split into two cases, since G cannot have a vertex of degree 0 and another vertex of degree n-1 at the same time. (If vertex $u$ has degree $n-1$ that means it must be adjacent to every other vertex in $G$, i.e., it must share an edge with every other vertex of $G$. But if another vertex $v$ has degree $0$ that means it is not adjacent to any vertex, i.e., it shares an edge with no one. An edge cannot simultaneously exist and not exist between $u$ and $v$)

Case 1: Assume G is connected. Then, its minimum degree is at least 1 and its maximum degree is at most n-1. Therefore, the set of possible degrees in G is {1, 2, ..., n-1}, which is of size n-1 < n. By the Pigeonhole Principle (where pigeons = slots in degree sequence; pigeonholes = possible degrees), since we have n-1 possible degrees and n slots in the degree sequence to fill, at least one entry will repeat.

Case 2: Assume G is disconnected, so the minimum degree is at least 0 and the maximum degree is at most n-2. This gives us the following set of possible degrees: {0, 1, ..., n-2}. Since this set is again of size n-1 < n, the Pigeonhole Principle still applies as above, resulting in at least one entry being repeated in the degree sequence of G.

[vital dew]

chanti

[frail sage]

Are they more difficult or less difficult?

Also, is there any way you can gain access to past exams? If yes, I’d say practicing those with a time limit is always good for practice

Or even “compiling” your own exam by cherry picking questions that are nice representatives of the difficulty

I feel like endurance is smth important to train, cause doing a set of problems from one topic, then a set of problems from another topic (with breaks and stuff) is one thing, but really sitting through 3 hours or so of working through questions that test a semester’s worth of material is another thing

[frail sage]

FYI this is also the proof the TA presented, but then when I explained it to my friend they just said this is way too much and you could just write the very first paragraph and conclude the proof from there… so idk

[drowsy marlin]

Most Grimaldi problems are less complex than the exam problems. The exams usually expect full proofs using the primitives and theory of the textbook, sometimes for theorems from outside the textbook. Not multiple choice. And then a handful of computation questions using the combinatorics equations on problem spaces that are nontrivial

[frail sage]

I’m using a book called “combinatorics and graph theory” which is very good and has hard problems

[drowsy marlin]

Only past midterms/quizzes, so the graph theory questions are an unknown

[frail sage]

Maybe you can look there?

[frail sage]

Very proof heavy

[frail sage]

This question is actually from there haha

https://data.fmipa.unand.ac.id/matematika/file_bahankuliah/ebooksclub.org__Combinatorics_and_Graph_Theory____2nd_Edition__Undergraduate_Texts_in_Mathematics_.pdf

Here’s the link

[drowsy marlin]

Better intros than Grimaldi's, which is a very dense pile of definitions and theorems

[cobalt cosmos]

Is my demonstration corerect?

[fallow stratus]

The forward direction you can prove by contradiction. Thus assume that $\Gamma \models \beta$ holds, and suppose for the sake of contradiction that $\Gamma \cup {\neg \beta}$ is satisfiable. Then this means there exists a valuation $v$ such that $v \models \Gamma \cup {\neg \beta}$. This means $v \models \Gamma$ and $v \models \neg \beta$. Since $v \models \Gamma$, then by our assumption this means that $v \models \beta$, but then $v$ satisfies both $\beta$ and $\neg \beta$, which is a contradiction. For the other direction, do it again by contradiction. In a sense, suppose that $v \models \Gamma$ but $v$ does not model $\beta$, and see what contradiction you get.

[vital dew]

Mootje

[frail sage]

Hi everyone, I want to prove that for any graph $G$ of order at least 2, the degree sequence has at least one pair of repeated entries.

I already know how to prove it but I'm wondering what the best/most rigorous/most elegant way is

[vital dew]

chanti

[lucid trout]

Btw ive a combinatorics question: how tf do you specify a set of n-tuples with k elements to choose from and none of them overlap, for example the set of every configuration of a card deck

In set builder notation

[spark field]

Are you referring to the set of permutations(? or is this more than tuples without duplicate elements

[lucid trout]

Ah yes

[lucid trout]

Just tuples with no duplicates

[spark field]

Hm in set builder notation

Normally I'd write out ``tuple $\sigma \in S_n$''

[vital dew]

Coolempire93

[spark field]

How would I write it in set huilder

If you write the components explicitly its not too hard but it's also far from elegant

But that might also be the only way to attack the condition

Ah I guess if you treat the tuple functionally, as you would a permutation

That abstracts from the components themselves

But you'd have to define the notation beforehand

${\sigma : i \neq j \implies \sigma(i) \neq \sigma(j)} \subseteq [n]^k$

[vital dew]

Coolempire93

[lucid trout]

I just write it as uhhh {(i;j) | i,j \in Universe | i ≠ j}

But hold up

I only really need to consider 2-tuples

So the above notation would suffice

[spark field]

Ah then you definitely could also just address explicitly

${(a,b) \in [n]^k : a \neq b}$

[vital dew]

Coolempire93

[spark field]

[n]²*

The set of transpositions

Regardless in that case your notation is fine

I would write (tuple) in Universe² though to not have double "such that" inside the set builder

[lucid trout]

Ok thanks (hold up how tf do i write a range of ints again, [m;n]^2| m,n \in N looks cursed)

Or is it implicit since my book tells me that a < i,j < b works

[spark field]

You could do either

$i,j \in [a,b]$ is typical, but $a \leq i,j \leq b$ is also used

[vital dew]

Coolempire93

[spark field]

Oh you mean foe the in N part

Yes usually that's implicitly known

[lucid trout]

Ok thx

[spark field]

Although personally I still state the convention at the top of the page/paper

Since sometimes its N, sometimes N_0, etc.

[weary tiger]

Anyone want to study together? I havea quiz on thursday and wouldn't mind people hanging around while I study in a call or something

[delicate dagger]

put me on guys wher do I get a free bona walk through combinatorics pdf

[inland raft]

You can't ask such things here

[robust monolith]

What?

[boreal crescent]

Can anyone explain why co domains have 0,1 and more than 1 pre images?

[past rivet]

That’s an exhaustive list of options

[boreal crescent]

Could you elaborate in simpler terms?

[little prism]

well there are no other options than 0, 1 or more than 1

thats what pseudo means

but I'm guessing you want to ask something else. tho I have no clue what

[boreal crescent]

you see when talking about functions we have pre-images and images right? my question is that when elements are mapped on a co-domain then how many pre images will it have that were previously mapped on it from the domain? does that depend upon the elements mapped? because I just searched and it said that it could have either 1, 0 or infinite possibilities (more than 1 in this case)

[boreal crescent]

ps I'm not really familiar with words such as pseudo or exhaustive as much yet I'm actually taking this course for the time for the very first time. I'll appreciate if you could explain the terminologies you use in this context!

[little prism]

pseudo is the name of the other person

exhaustive is just a normal english word

[boreal crescent]

alright

[little prism]

what other number of preimages are you expecting.

1/2 preimages?

0.1905061396... preimages?

[boreal crescent]

no like why 0,1 and n numbers are included? Reason?

[little prism]

I have no idea how to answer your question. what else should it be

[boreal crescent]

Okay can you explain pre-images and images in terms of domain and co-domain?

[little prism]

a function has a domain and a codomain and a "rule" which says that if you put in some element from the domain you get some element from the codomain

so f:R->R, f(x)=x^2 has domain R and codomain R and the rule is that you square the number you put in

so f(1)=1, f(17)=289, etc

the image of the function is the set of all numbers that you can actually get

so all numbers >= 0 in this case

the preimage of a number is what you can put into the function to get that number

so the preimage of 4 is {-2,2}

because f(-2)=4 and f(2)=4

so here 4 has two preimages

the preimage of 0 is {0} because only f(0)=0

the preimage of -1 is the empty set

because there is no number with f(x)=-1

is that helpful?

[boreal crescent]

woah what you explained is not even 1/2 of what my teacher explained he just explained that pre-images from Set A maps to Set B making them images and somehow co domains have 0,1 and more than 1 pre images. Thanks it cleared things up

[sturdy frigate]

Instead of proving the inequality for products try to convert it into a sum by taking logs and the problem would structurally start making much more sense

[south quarry]

does anyone know where I could turn to to get tutored in on discrete math. I just need to go over practice exams

[blazing fern]

basic question about functions

If we have a function f: X -> Y where y=f(x), how would the definition of a function permit situations where f(x) is undefined at certain points? Does the corresponding x still map to something?

Would it still be a function?

im just thinking about very basic removable discontinuity examples

[quick folio]

well, no, when a function is said to be undefined at a point then that means that that point is not in the domain of f

[blazing fern]

i see

so if we have a function f defined over R x R and then “poke a hole” in the corresponding curve then the domain wouldn’t be R anymore, if that makes sense?

[quick folio]

yeah sure, I think I get what you mean

[blazing fern]

thank you

[past rivet]

You may be interested in “partial functions”

[grizzled wasp]

i had leaerened maybe i am wrong that llm understand us by 3 math branches
Discrete math is the grammar. Linear algebra is the meaning. Probability is the voice

[blazing fern]

thank u

[lucid trout]

what is this bullshit

this doesnt even make sense

[blazing fern]

if u squint really hard it makes a little sense

[drowsy marlin]

LLMs specifically don't understand. They are text prediction, like autocorrection on your phone or Markov chains.

[cobalt cosmos]

In the second example , I didn't understand why they're not terms?

[spare slate]

P(a) is an atomic formula, not an object

and so f(P(a)) is not a term by r3

[jolly plinth]

i find pnc bit difficult to understand so what should i do , i can't drop it either

[velvet knoll]

As in permutations like P(5,3) = "ordered sets of 3 objects out of 5" and combinations like C(5,3) = "ways to pick 3 out of 5 things" ?

Though you may use different notation

Assuming that's right, if you've got a test on this topic coming up really soon I'd focus on trying to remember the formulas, and that P(n,m) is "with order" and C(n,m) is "without order"

So the number of possible 5 card hands from a 52 card deck where the order doesn't matter is C(52,5)

But if you played a game where the order you drew 5 cards in did matter, there would be P(52, 5) possibilities

@ me if you wanna discuss this more

[keen flower]

can someone explain me Unions, Intersections, Differences, and Complements please?

union means set of both of them

intersection means which elements are in both

but what are the differences and complements?

[spare slate]

You can google this yourself

set differences

[keen flower]

i tried, i tried youtube too

[spare slate]

set complements

[keen flower]

its hard to comprehend i need it said in easier words lol

[velvet knoll]

So for there to be a compliment you need a larger set U

Let U = {1,2,3,4,5} and A = {1,2,3}, then the compliment of A in U is A^c = {4,5}

A \ B means everything that is in A that is NOT in B

[velvet knoll]

Does this help at all?

[keen flower]

Yes

Thank youuu

[velvet knoll]

No problem!

[keen flower]

Did u draw that diagram?

[velvet knoll]

Ye

Though I'm sure you could find similar, cleaner ones if you look around

I know I've seen it presented this way before

Oh one thing, you might see A - B sometimes, that just means the same thing as A \ B

Different notations for the same operation

[keen flower]

i appreciate your effort a ton!

[blazing fern]

This turned out to be very helpful and inspiring thank you

[wind pelican]

I think this is the right place to ask but I am stuck on this problem:
"Let [n] = {1,2,...,n}, consider S = {all subsets of [n] of size k} ,
Suppose you want to partition S in such a way that for every pair of sets in each part, they are not disjoint. Show that n-2k+2 is an upper bound on the size of S."

I think this is equivalent to saying "Show that n-2k+2 is an upper bound on χ(Kn(n,k))"

if we have a colour set C, then f^-1(c∈C) is an independent set.
I know n is enough because at each stage you can construct S and remove all sets containing 1, then all sets containing 2 and so on

I can improve this to n-k+1, because suppose i play a game with a friend where i ask him to pick k distinct numbers in [n] and if I say any of them he loses. Then there are n-k numbers he didn't pick, so to eliminate his choice, i need to say at least n-k+1, but for Kn(5,2), only 3 colours are sufficient, but n-k+1 = 4 ...

[wind pelican]

Nvm came up with a proof
Proof: Let S0 = [n], fix N ∈ n and generate all sets that contain N of size k. Remove N from S0 to create S1 and repeat...
Note, if |Si| < 2k then any set of size k will not be disjoint from any other sets (Consider the edge set of Kn(2k-1,k)), as such the last set in the sequence is Sn-(2k-1), so we have sets S0, S1,...,Sn-(2k-1), this corresponds to n-2k+2 independent sets/partitions containing non disjoint sets ❑

[spark field]

ah nice it's the chromatic number of kneser graphs

[wind pelican]

wait is it proven that it is exactly n-2k+2

[spark field]

When they are connected (so n >= 2k) yes

[wind pelican]

I hope i never have to prove that in an exam

[spark field]

That was Kneser's conjecture

the origination of the class of graphs

[wind pelican]

I see

I should not have taken Discrete Mathematics 🥀

[spark field]

Your class just seems like it has a bunch of extra stuff in it 😆 our discrete class definitely didn't cover specific classes of graphs

[wind pelican]

my entire course always finds a way to talk about graphs, while its not always "what tyep of class is this", its always "show this graph has this property", "does this graph have this property? Justify your answer", or "Prove this holds for all graph of this type"

i quite like graph theory but man I am just not good at Combinatorics

[spark field]

Maybe I'm your professor everything must come back to graphs

joking joking haha

[spark field]

this is real

me when my professor asks me to succinctly write a proof for a conjecture that was open for 22 years

[wind pelican]

https://giphy.com/gifs/individual-zrozevn-zvn-aM3HiCbAFVByxPWYdD

[wind pelican]

THIS IS SO TRUE

I HATE IT

https://tenor.com/view/vergil675-gif-2877674803769001259

[robust thunder]

Any guidance on how to approach and solve these types of questions?

[cerulean wind]

a binary operation on a set X is just a function X x X —> X

[robust thunder]

I get (a). testing if $x \cdot y \in S$ but how do you go about this?

[vital dew]

4E656F

[cerulean wind]

show that if x = a + b sqrt(2) and y = c + d sqrt(2), then x * y is of the form e + f sqrt(2) for some rational numbers e and f

[robust thunder]

Thanks mate, that makes sense

[sick copper]

Is anyone able to make out what the question is saying 😅

[spark field]

Determine whether $f : \ZZ \to \ZZ$, $f(x) = x^3 - 1$ is a total function, partial function, one-to-one, onto, inverible. If the function is invertible, then find $f^{-1}$ (15 points)

I believe

[vital dew]

Coolempire93

[spark field]

Not sure exactly if it's a x^3 or x^2 but I think x^3

[sick copper]

yeah it is

this is pretty impressive ngl I wasnt able to make out a single word lol

thank you so much

[spark field]

No problem

[storm violet]

Determine whether $f : \bZ \to \bZ$, $f(x) = x^3 - 1$ is a total function, partial function, one-to-one, onto, inverible. If the function is invertible, then find $f^{-1}$ (15 points)

[sick copper]

thats the same thing as what the person above sent right?

[sick copper]

can someone walk me thru solving the last one?
Will the cartesian product be a tuple of everything or what exactly

[spark field]

Doing multiple cartesian products like that gives you a product of everything yeah

It would be the same as if you did $(A \times B) \times C$ (or $A \times (B \times C)$) and then removed the inside parentheses

[vital dew]

Coolempire93

[spark field]

Which is probably the easier way computationally to do it, i.e. if you were actually asked to write out all the values from some simpler sets

For this you can just pretend you extended the definition to more than two sets

$A \times B \times C = {(a,b,c) \colon a \in A, b \in B, c \in C}$

[vital dew]

Coolempire93

[spark field]

Keeping in mind as well that the members of your set A are tuples themselves, so you will have nested parentheses

[cunning plank]

if you had P = {a,b} and Q = {c,d} PxQxQ would look different from (PxQ)xQ right?

[spark field]

Yes

[cunning plank]

alr

cuz u nest the parantehse

[spark field]

Although functionally they are the same

Technically different objects 👌

[cunning plank]

how it feels after doing 20 questions of whether {1} is an element of {1,2}

[spark field]

real

especially those empty set questions

[cunning plank]

fr

[spare tulip]

Is this how power sums are usually calculated? I'm working on a project for school where I'm moving towards a least regressions formula. The first image is the example for p=2 while the second is general.

Also I think this is the right spot to ask this but I'm not actually sure

[spare slate]

This isn't usually how they're calculated, but it seems valid

normally you'd use induction to verify and faulhaber's to actually come up with the formula

[spare slate]

I suppose it fits into here

discrete calculus

doesn't matter too much tbh

[spare tulip]

Faulhaber's is a bit out of my league for school, I was looking at it but I think this will let me show the relationship by integration

and faulhaber's is lowkey just disguising the recursion since bernouli numbers are recursive anyways -_-

[spare tulip]

like integrating the previous terms to find the next ones

[spare tulip]

Good to know though thank you very much

[spare slate]

[idle geode]

so ive been thinking a bit about number bases, seems theres something called compressed fibbinary (basically a bijective function to the binaries using 0s and 1s but not ordered the same way)

there's a problem im interested in:
minimising the number of bits to represent multiple numbers, without any separators like commas and with no upper limit of number size.

i know you could do it in O(log n) extra bits per number but is there something that does it in O(1)? like for example a completely new number base which leaves a few bits of freedom in its representation to encode if the number should end

doesnt have to be constant but any improvement to its complexity is fine

example:
90, 3, 10 = 1011010, 11, 1010 could be encoded as 11111101011010101111101010

i know you could do something like repeat this process one more time for the size of the size but to me that is not an interesting solution

i guess anything below O(log log n) is good

another way to do it would be to mangle the numbers into a single result which might be the only option to reduce it tbh

like you could do something like π(n_1)*π(n_2)*π(n_3) but then you'd not know the order

probably doesnt give a lower complexity anyway

[idle geode]

my intution says it cannot be done since the prime decomposition is basically bijective to its set (possibly with repeated members) of prime number indexs

and my list of numbers is strictly more information than its set

[cerulean radish]

You could also use the enumeration of ({0,1}^*)^3, but then you would probably be concerned with the encoder and decoder complexities

[idle geode]

i guess that would work for the case where elements are rather close in size

it would effectivley be constant of +3 bits

if they all same size

[idle geode]

i guess theres also one more similar method:
enumerate based on total number of bits used, so yeah it's possible to get O(1).

for fixed list lengths |N| its O(log |N|!)

i guess thats actually just written as O(|N|log |N|)

[vital cloak]

If I have $(X \land Y \land \neg Z) \lor (\neg X \land Y \land Z) \lor (\neg X \land Y \land \neg Z)$ equivalent to $(X \land Y \land \neg Z) \lor (\neg X \land Y)$ for 3 variables X, Y, Z, which one is DNF (Disjunctive Normal Form)?

[vital dew]

Minλ

[spark field]

I believe both but if the second is equivalent you would call that minimal DNF

whereas the first is

canonical?

[vital cloak]

well i was doing question like this

I am not sure whether to use for the circuit, since my prof ask for both component form and circuit

[vital cloak]

so they are both DNF right?

[spark field]

Yeah they're both disjunctions of conjunctions which is the only requirement

[vital cloak]

Right, thanks

Sometimes help channels are just not helpful enough as these advanced channels

[spark field]

haha yeah I've stopped reading the help channels as I realize my enjoyment of seeing less and less actual numbers in my math

[vital cloak]

Wow

[spark field]

Not to say that I don't enjoy this

I think k-maps and normal forms were the most interesting part of my digital fundamentals class

[vital cloak]

Yeah help channels are getting boring

I think logistic maths is quite interesting too

[sick copper]

Am i on the right track here? Or have i done something that is considered to be wrong before writing since j and k are integers therefore (a+c) - (b+d) = mx and that therefore they are congruent

[daring mantle]

the algebra is basically what would be involved in a proof but you want to try to write out a paragraph in words and using logical qualifiers

but yes on the right track

[sick copper]

how can I add logical quantifiers to it I get the paragraph part and im working on it but now the logical quanitifiers

[daring mantle]

i’ll just give some pointers for the beginning and let you try to see how to do it for the rest of the proof. do you see where you have 1) m | a-b = km = a-b? that doesn’t make sense grammatically, “m divides a -b” is a statement (a sentence with a truth value) and then you set that sentence equal to km, except i don’t know what k is without reading your mind and you shouldn’t set a statement equal to something, you need a new sentence there

so instead you can say something like, “since a = b mod m then by definition there exists some integer k such that km = a-b. likewise since c = d mod m there exists an integer j such that jm = c-d.

hence (b+d) - (a+b) = ….” and go from there. remember the goal is to show that expression is of the form (integer) *m which will establish the first congruence you want.

[sick copper]

Alright thank you ill try rewriting my proof like that

[daring mantle]

if you have any programming experience then using an existential quantifier like “there exists k such that” is kinda like instantiating a variable before you begin writing code with it

basically only the a,b,c,d, and m are fair game to reference without specifying what they are since they’re used in the problem statement

[sick copper]

Is this fine?

[spare slate]

c-d, not a-b

[spare slate]

the way you wrote this makes it seem circular, and honestly it's kinda of a mess from this point on

You're better off doing

,texsp ||Since $a \equiv b \pmod{m}$, $a-b=mk$ for some integer $k$. Similarly, because $c \equiv d \pmod{m}$, there is some integer $j$ such that $c-d=mj$. It follows that
$$(a+c)-(b+d)=(a-b)+(c-d)=mk+mj=m(k+j).$$
Because the integers are closed under addition, $k+j$ is an integer. So,
$$m \mid (a+c)-(b+d) \implies a+c \equiv b+d \pmod{m}.$$||

[vital dew]

Civil Service Pigeon

[daring mantle]

yeah i think you want to think of your proof as showing the existence of some integer you're calling x. your sentence that begins with "by definition of divisibility there exists x..." feels a little premature because it takes a little work to show that (a+c) - (b+d) is actually divisible by x

how CVP wrote it is perfect so that's a good model to look at but make sure you understand the difference we're pointing out

but compared to the first attempt it was already a big improvement

[chrome iron]

❓

[spare tulip]

what law states that the integral and sum are interchangeable?

[little prism]

linearity of the integral

assuming its a finite sum

[pallid heart]

Is the correct term indexed set or indexed family?

[ember obsidian]

we say indexed family or collection. also note that its distinct from the set of indices which we call the index set

[spark field]

In my book we called it an indexed set

With the same set of indices being called the index set

but I agree "indexed family of sets" is clearer

[merry kayak]

what have you tried?

[vast mason]

a.) 3! x 6C1 x 5C2 = 360
b.) 6C1 x 5C2 = 60
c.) 6!/1!2!3! = 60

if you want me to elaborate just ask

[chrome iron]

i couldnt differentiate how to solve the a v/s b part

[chrome iron]

can u kindly elaborate the diff b/w like box 1 and one box

[vast mason]

from what i understand, box 1,2,3 are labelled, whilst there being 3 boxes are distinct and not labelled, so the reason we x by 3! for the first one is cuz 3! ways to assign the labels 1,2,3 to the 3 boxes

[chrome iron]

yea right like there are still going to be 3! ways to label the boxes as box 1 ,box 2 and box 3.

but in the b part theyre already labeled so theres just one way to label them correctly

[slate dove]

pretty sure b) is 360 but Idk im not sure about the first tbh

actually no

the balls aren't distinct I Imagine

shouldn't the answer be 1 then for b

and c even

if balls ain't distinct the first one would be a permutation of 3 so that's 6

second and third I think should be 1

[chrome iron]

the balls are distinct

see if they are to be indentical the question will specifically make that a case

solve by taking B1,B2......B6.

if anyone is confident about pnc kindly ping me i need help understaning some sub topics and i got some minor doubts will be sending some qs tmrw

pnc=permutaions and combinations

[slate dove]

If they're distinct then what he did is correct

start with b since it's simpler to understand because the boxes are ordered

box1 box2 box3, start with the first, you have 6 balls and you wanna place one of them, so that's 6C1, all possible 1 combinations of 6 balls.. which is obviously 6, now after we put that one we have 5 left, find the different 2 ball combinations you can have, because we don't care about order of insertion we use combinations not collections so that's 5C2, finally we have 3 balls left, cuz they're the final balls you don't really have to do anything, but for deeper understanding you can do 3C3, all combinations of 3 balls from.. 3 balls, which is only one.

so that's 6C1 * 5C2 * 3C3 = 60

you can obviously start the other way around, like 6C3 * 3C2 * 1C1 if ya want to, because each one is already reserved for the respective box

now going back to a, it's the same, but at the end you multiply by 3! because the number of balls isn't relative to the number of the box, it just says that one of them must have one, one must have two, one must have three, not important which is which, so that creates a permutation of possible outcomes, they're 3 so that's 3!, = 360

for c, the boxes are not distinct, but since each box has a different number of balls attached to it this doesn't create much of a difference, opposed to it saying two of the boxes had two balls for example, yea that'd need extra work, but because each box contains a different amount of balls you can go through the same process you used in b

[slate dove]

actually you seem to understand nvm

I yapped for nothing

Ig I revised the topic tho thanks for the refresher

[chrome iron]

tysm for this

[cobalt sable]

where can I find videos explaining these properties of images

can anyone help me collect them?

what do I need to search to get these results?

[chrome iron]

i think u can look up khan academy lectures if u speak eng i mean and look ralations and functions and set theory in detail on there it will help u understand these prepoerties ig

or maybe the oc tutor if he has taught this stuff

or just look up any arbitrary lecture there are alot of good teachers with less reach

[long willow]

hey

[west hedge]

https://math.stackexchange.com/questions/359693/overview-of-basic-results-about-images-and-preimages
see the top answer. this is the gold standard reference

[agile magnet]

I mean the thing to do would be trying to prove them

and getting stuck and asking for specific help would be good

[simple solstice]

Just to clarify my understanding, two geodesics belonging to some connected graph G that have lengths equal to the diameter of G must have at least one common vertex, or else it contradicts the fact that the lengths of the geodesics equal diameter? (Sorry if my wording is bad)

OR is this a false fact because we can have geodesics that do not have any common vertices, but retain a length equivalent to the diameter of the graph?

[grand crown]

take the two geodesics, suppose for contradiction they don't overlap. since the graph is connected, there is a path from some vertex in the left geodesic to some vertex in the right geodesic, and WLOG we can assume the path doesn't use edges in either geodesic. then we can take the augmented path that uses the "longer" segment of each geodesic, and the bridging path, and the overall length will be longer than either geodesic

[simple solstice]

Thanks!!

[indigo stump]

Guys, is this the correct way of making a number adding machine?

I wanna try and make one out of wood, but I'm not very good at math so idk whether this system will work properly

[coral parcel]

Is that supposed to be a binary adder? I don't completely understand your notation, but it looks like if it works it would be more complex than the common ripple-carry design.

[indigo stump]

It is supposed to. Maybe this image will help

Black lines are which gates are supposed to be active

[coral parcel]

The trick is to build it from copies of a pattern that can add three single-bit inputs and give a two-bit result. Then the three inputs to that can be one bit from each of your original number together with the carry out from the previous bit position.
That way you won't need a whole wedge-shaped structure whose size will grow as the square of the number of bits.

I think each of your XOR/AND crosses is a correct 1+1->2 bit adder. You can build a 1+1+1->2 bit adder by cascading two of the XOR/AND crosses. The carry ("and") outputs of those cannot both be 1 at the same time, so you can OR them together before you feed the carry to the next bit position, and end up with much smaller overall solution.

[slim geode]

What you want is a sequence of full adders https://www.geeksforgeeks.org/digital-logic/full-adder-in-digital-logic/

[coral parcel]

It would be neat to find a link that explains without that extremely annoying cookie splash. (It's not enough to scroll though the long list and uncheck all the "legitimate interest" lies, you also need to click "vendor preferences" at the bottom to get an even longer list with about a hundred further "legitimate interest" lies to deny).

[indigo stump]

Like this?

[indigo stump]

Oh, thanks

[coral parcel]

More like (going left to right):

 input1 --and----------or -----> carry out
        \/            /
        /\           /
 input2 --xor --and--
              \/
              /\
 input3 --------xor ----> result bit out

[indigo stump]

ye but I've only figured out how to make XOR and AND out of wood

😄

and other available materials

which is why I tried to replace OR with XOR on XOR + AND

[coral parcel]

I see.

[indigo stump]

Well, okay, thanks for your help I'll start trying to make it then 🙂

[coral parcel]

In the above diagram, you can also replace the or with an xor -- since the inputs to it cannot both be 1, anyway.

[indigo stump]

oh yeah it makes sense

this is a lot of fun.

[wind pelican]

https://tenor.com/view/copy-squidward-gif-14421011

[drowsy marlin]

Might help to use standard notation here so colourblind people can read it.

Normally the gate names are ommitted in circuit diagrams

So you just have the labels for in/out

You can expand the full adder to any number of bits by feeding the carry out to cin of the next bit

And the last carry out can detect overflow conditions (when the result is invalid because the computer can't store MAX + 1)

[plain tangle]

Does anyone here have a good bibliography to start studying discrete mathematics?

[spark field]

#book-recommendations probably does

Otherwise good books include
Discrete Math and its Applications (Rosen), which is more CS/usage focused
Discrete Mathematics (Johnsonbaugh), which I think is really good for self-study
A Transition to Advanced Mathematics (Smith et al), which is more math focused
I will think of others in due time probably

[plain tangle]

thank you

[flint valley]

I'm in a cs focused discrete math and we're using rosen. It is fine. I don't love it simply because it isn't written like most math textbooks I've used before.

But it explains things in an approachable way for non-math people.

[keen flower]

can someone help me with these

5.2

idk how to even get started

[grand crown]

try writing the LHS for n = k + 1 in terms of the summation for n = k, and then adding an extra term

then you can replace the n = k summation using the inductive hypothesis

[keen flower]

im on 6.2 now

[spark field]

Need help with 6.2 or are you working

[keen flower]

Im done

Thank you thoo

[spiral nest]

Is that a valid way of formalising "It is not true that every natural number is either not dividable by two or by 5" while I should only use the existential quantifier, negation, conjunction and disjunction?

[spare slate]

yes

[spiral nest]

I am a little scared because I did not use a disjunction

[grand crown]

you dont need to use everything

[sand talon]

intro to discrete math V.K. Balakrishnan is pretty fire

[lapis gate]

what no

does (x:2) mean "x is divisible by 2" ?

[spiral nest]

Yes

I am still used to write it that way from school but yeah

[lapis gate]

what then I do not understand wtf does it have t do with every natural number is either not dividable by two or by 5

you are starting by saying "there exist an x"

while the sentence sayss "for all x"

[spiral nest]

There exists a number that is dividable by two and not by 2

[lapis gate]

(in N)

[spiral nest]

The task was to only use the existential quantifier

[lapis gate]

by 2 and not 5 you mean

[spiral nest]

Yeah, I am tired mb

[lapis gate]

but that's just not the sentence you wrote after

for example 4 is divisible by 2 and not 5

how does that inform us on like 13 for ex ?

[coral parcel]

The prose statement is fairly weirdly phrased. Either of these would be unambiguous:

... every natural number is either not divisible by 2 or divisible by 5
or
... every natural number is not divisible by 2 or by 5
(and they don't mean the same), but the wording given seems to be somewhere in the middle.

[lapis gate]

or 25

[spiral nest]

Yeah that irritated me as well

It was originally written in German but with the same issue

[lapis gate]

no I think its every n number is either not div by 2 or not div by 5

[spiral nest]

I am disproving the statement using a counter example

[lapis gate]

?

oh ok

[spiral nest]

Then it would have been phrased that way

[coral parcel]

The disjunction correctly became a conjuction when you pushed the "not true" down past it with De Morgan's laws.

[lapis gate]

I thought you had to write it even if it was false

mb

[spiral nest]

I would say that is equal to saying "it is wrong that the statement is true"

[spiral nest]

Thanks

[coral parcel]

That just makes it triply ambiguous, then.

[rough crescent]

Hello

Can anyone help me
I want to self study math but idont know where to start.
I alr know calc with like epsilon delta proofs,
And a little bit of linear algebra
Where do I go next

[mystic linden]

https://youtu.be/byNaO_zn2fI

What you could also do if pick a university of your choice and take a look at the modules that they offer and study the relevant textbooks

Hope this helps

[old briar]

My working on paper

[spark field]

<@&268886789983436800>

[grand totem]

<@&268886789983436800>

[scenic mesa]

does there exist a graph whose group of isomorphisms is generated by a 3-cycle of nodes?

[cerulean radish]

You mean the group of automorphisms?

This graph has automorphism group isomorphic to Z3

You may also be interested in Frucht's theorem, which states any finite group can be presented as the automorphism group of a connected graph

[scenic mesa]

yeah the group of automorphisms

i think it can be isomorphic to Z3 but i'm wondering if it can be actually equal to a group generated by a 3-cycle

i suspect not

[cerulean radish]

Ah, I get what you mean now, yeah that's not possible

Actually, let me think about it

[cerulean radish]

Yeah, say the 3-cycle moves v1, v2, v3, then {u, vi} in E iff {u, vj} in E for any i, j and u not in {v1, v2, v3}, meaning swapping v1 and v2 will also be a permutation

[scenic mesa]

thanks

[visual solstice]

let's call right rotation L( , ), right rotation R( , ), the pivot node "p" and the root note "r"

and T the tree

R(T,p) = L(T,r) ?

am i crazy or are R() and L() not inverses of each other?

they're only inverses if, like in this diagram, we also swap who is the pivot and who is the root

[keen flower]

Can someone help me out with this

Im going over my tests preparing for finals

gpt is saying im right

[fossil mural]

,rcw

[keen flower]

Idk what i did wrong

[fossil mural]

the second line should be $(p \land \neg p) \lor \neg q$

[vital dew]

bee [it/its]

[fossil mural]

(you have the $\lor$ and $\land$ the wrong way around)

[vital dew]

bee [it/its]

[fossil mural]

$(p \lor \neg p) \land \neg q$ would be equivalent to $(p \land \neg q) \lor (\neg p \land \neg q)$

[vital dew]

bee [it/its]

[fossil mural]

although your final answer of ~q still happened to be correct, it's just the steps that were wrong

[keen flower]

Wtfff

Why did he take off 5 points for that

I got the answer right

Can u show me the entire steps please

If u have time

[keen flower]

Can someone help me with 1

[spare slate]

In the future, please use the ,rotate command.

,rotate

[spare slate]

The point is that zero is a rational number. What happens if you divide by zero?

[keen flower]

u get undefined

[spare slate]

mhm

you don't even get a number as the result, let alone a rational one

go back to the theorem you reference - I'm sure there's a condition on something being nonzero that's not in this question.

[keen flower]

apparently thats not even a theorem

[spare slate]

probably because you're missing the condition of something being nonzero

[keen flower]

how would you answer that question

[keen flower]

im confused :/

[spare slate]

As I said earlier, zero is a rational number

and as you said, when you try to divide by zero, you get an undefined result

which is not a number at all

So this is a case where dividing two rational numbers doesn't even give a number, let alone a rational one

and hence your answer is no

As I've been referring to, you need to impose the condition that the number you're dividing by is not zero

which relates to this condition that you incorrectly assumed/introduced/imposed

[keen flower]

ohh okay got it

i think

maybe maybe not

How is it not a Yes, except when you're diving by 0

which is what i was trying to say there

[spare slate]

You never said "except when you're dividing by zero"

and the question never imposes that condition at all

this is similar to the idea of finding a counterexample

if you find one example where something fails, then it's not always true

[keen flower]

ohhh

https://tenor.com/view/ahoklollmao-of-course-ohhhh-oh-that-makes-sense-gif-11896286840118452668

thank you civil service pigeon

[spare slate]

[keen flower]

i got more 😉

are u available?

[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.

[keen flower]

you literally smash knowledge into my mind so i appreciate your method of teaching

ohh

oopsie

.rotate

[keen flower]

!rotate

[spare slate]

you wrote 2k+1 on its own with no other context

and as they say, you should specify what k is

k is an integer

furthermore, you're reusing k between two different integers (m, n), which is bad practice

You're better off saying something like

Let $n=2k_1+1$ and $m=2k_2+1$ for integers $k_1$, $k_2$. Then, both $m$ and $n$ are odd by definition.

[vital dew]

Civil Service Pigeon

[spare slate]

note this is why there's the comment of n=m?

becuase in a literal sense, you wrote n and m as both being equal to the same thing (2k+1)

(insert comment about transitivity if you want to be super thorough/pedantic/whatever)

also at the end it seems like you're floundering about

an integer is even if and only if it's a multiple of 2

aka 2 times some integer

perhaps you meant to write that, but it's not clear at all

[keen flower]

yeah i meant to write that

idk how to write proofs at alllll man

holy cow

what does a good proof for this question look like?

[spare slate]

Let $n=2k_1+1$ and $m=2k_2+1$ for integers $k_1$, $k_2$. $m$ and $n$ are both odd by definition. By a direct computation,
$$m+n=(2k_1+1)+(2k_2+1)=2k_1+2k_2+2=2(k_1+k_2+1).$$
Since $k_1$, $k_2$, and $1$ are all integers, it follows that $k_1+k_2+1$ is also an integer since the integers are closed under addition. So, since $m+n$ is the product of $2$ and an integer, it is also an even integer. This shows that the sum of any two odd integers is even.

Here's a rough first draft

The key points are to invoke things in an at least somewhat chronological order (obviously this isn't a hard and fast rule, especially with things like lemmas, but try to write things in an order that makes at least some sense)

ex. you invoked closure of the integers under addition before even writing down the equation where it's relevant

and at the end, you could be a lot more direct with how you invoke the definition of being even

all you need is multiple of 2 -> even

I think writing too much at the end may have shot you in the foot here

oh and also don't recycle notation

that's important as well

[vital dew]

Civil Service Pigeon

[keen flower]

Damm

[keen flower]

Wdym by this

[spare slate]

Hello?

[keen flower]

Ohh thats what u meant

Im sorry

And thank you for your help!

[spare slate]

[elder crane]

does anyone know who has the best course for University Math 2 (discrete math/structures)?

[keen flower]

wdym

[keen flower]

Can someone help me with #5

[austere swan]

It's been 10 minutes lmao

[keen flower]

ahahah

[keen flower]

i love your pfp!

[austere swan]

Thanks

Oh wow the person who was marking this sucks

They read you writing (2k)*(2k) as you wanting yo write (2k)^2. (2k)^2

What do you need help with exactly?

[keen flower]

Idk how to answer it

I tried it but idk what I did wrong

[keen flower]

😭😭😭 everyone been saying that

They even stated im missing reasoning for contropositive

Like what did I miss

[austere swan]

Idk about reasoning, the only things I think you "missed" are:
In your contrapositive statement you need to say "for all integers n" before saying "if n is even...".

When you start the proof, you need to declare n (let n be an integer, suppose n is even/let n be an even integer)

Oh also, you added "for some even integer k" but you can have n=2k with k odd. I think maybe that's why they asked "why"? Otherwise there's nothing really to explain here, even means n=2k for some integer k by definition

[keen flower]

okay i think i got it

he took off 4 points for that holy molly

this one i just winged it i did not know how to answer at all

[austere swan]

Yea that's crazy work. Shit feedback too

[keen flower]

it would help if he gave constructive comprehensible feedback

class avg is like 40% i heard

[austere swan]

Here first you failed to write a/b=(7-4sqrt(2)), so it just says "by the definition of rational, a/b such that b\neq 0.

Also, like the grader wrote, a,b rational implies ab rational does not say anything about irrational numbers, so you can't use that to conclude 4sqrt(2) is irrational

The play here is to rewrite it to be sqrt(2)= (bunch of rational stuff) and obtain a contradiction by irrationality of sqrt(2)

[keen flower]

how would i get to that point

[keen flower]

.

i appreciate you helping!

a lot!

[spark field]

<@&268886789983436800>

[feral harbor]

Are math proofs part of discrete mathematics?

[coral parcel]

Discrete math courses typically has some amount of introduction to proofwriting as part of their goals.
Formal proof theory is something different, however. Some discrete math courses do contain a bit of it, but that's not an universal feature.

[spark field]

I think this might be better for #linear-algebra

or advanced analysis or smth
Idk enough math to say but I just don't know that it's right for here

[dire bough]

so as stated part 1 is just wrong

T certainly cannot be compact

but yeah this is more suited for #advanced-analysis

[spark field]

<@&268886789983436800>

[keen flower]

what happened broski

[spark field]

scpammers

[uncut wagon]

can anyone provide me a hint on how to tackle this problem?

[grand crown]

what does exercise 4.17 say?

[robust thunder]

Can someone help me draw this Hasse diagram? I just can't get it to work?!

[grand crown]

i dont think this is a valid partial order

8 divides 3 * 24 and 24 divides 3 * 8

[robust thunder]

Ah so it's not anti-symmetric. I didn't check if it's a poset @#$!

[uncut wagon]

Exercise 4.17 states that with the conditions in the problem statement, G has a face that is bounded by at most four edges

[grand crown]

mm an idea i have is to keep identifying a face and compressing it down to a vertex

that way you decrease the number of faces and vertices while ensuring every vertex still has degree >= 3

so inductively you can color the new graph

then maybe figure out a way to expand back to the original and color the vertices that you condensed

actually that doesnt work u dont get simple graphs

[vivid osprey]

Basic question. Reading a proof in Rudin's book. He says something along the lines that every permutation of {0, ..., k} is a composition of two special cases considered already in the proof; swapping 0 with any 1 <= j <= k, and swapping i with j, for 0 < i < j <=k.

My question; it was some time ago I studied permutations, but I'm familiar with the fact that every permutation in {0, ..., k} can be written as a composition of disjoint cycles. Is that the theorem Rudin refers to?

[vivid osprey]

Solved it.

[spark field]

oh yeah I remember this from my abstract algebra book

you can write an n-cycle (1,2,3,...,n) as (1,n)(1,n-1)...(1,3)(1,2)

and then I guess if you have multiple such cycles the second special case comes into play

so everything comes as a result of the theorem you're referring too

That's nice

[spark field]

<@&268886789983436800>

[old briar]

📈

[craggy trench]

Hai kittens

[elder tide]

how to solve this ;-;

[waxen mist]

What is this 😭🙂

[glossy solstice]

I suppose its asking for solutions modulo 4, 15 and 28.

Do you know how to solve ax + by = c in integers?

[elder tide]

nope

forgot

[glossy solstice]

Do you know the euclidean algorithm for finding the GCD/HCF?

[elder tide]

forgot too ;-;

[glossy solstice]

There are other ways to solve these, but they are either harder (continued fractions) or trickery, I think you should take a look at your classnotes.

[elder tide]

m- my classnotes? I didn't take any 😭 </3

[glossy solstice]

RIP

[elder tide]

[glossy solstice]

You can watch it on youtube

Since you knew it already it won't be hard.

[proud laurel]

Chinese remainder theorem

[coral parcel]

Well, the theorem itself just states that a solution exists, right?

[coral parcel]

It's really just modulo 4, 3, and 7, since the middle and last equation can be divided through by 5 and 4, respectively,

[spark field]

The proof of the theorem outlines the algorithm

At least that is how our book did it

So after the proof the book said now let's attempt to apply it

(Rosen)

But I agree CRT is likely the intended way

Although this system is simple enough to just work by hand

[glossy solstice]

Well, as soon as they'd convert it into a linear equation they'd see it.

[thorny hollow]

Is the answer 7

Yes or no please

7 or 13

11

Oh

Thx

Oh

Y

[worn wyvern]

Yeah its 11 sry

[thorny hollow]

Is it

My thought process for eleven is that,

there's 6 people with both blonde hair and blue eyes, x - 6 people with blue eyes, and twice as many as that with blue eyes which is 2x (cus x -6 + 6 is x), and 3 people whos neither

So

x - 6 + 2x + 3 = 30
3x - 3 = 30
x = 33/3
x = 11

Dunno

Hm

[thorny hollow]

[thorny hollow]

Do I ping staff

[hidden totem]

x-6 people with blue eyes but not blonde hair but otherwise this work looks good

honestly its easier if you just visualize a venn diagram, one circle for blonde hair, another for blue eyes

notice that one circle is x, the other 2x, overlap is 6, 3 outside both circles

so now its easy to add the two circles, subtract overlap

cleaner to think about that way

[thorny hollow]

Im just following the books guide, that says it's important to know how to transform it into an equation

Tried to do this inside my head only. Is the answer for a) 66?

[spare slate]

no

[thorny hollow]

Thx

[spare slate]

[hidden totem]

oh yeah it's definitely important, im not saying to skip the step of creating the equation, im saying this is a cleaner way to think about how to write out the equation

its slightly less prone to mistakes

[thorny hollow]

57?

That or 84

When you try the same question thrice and you get three dif answers

[coral parcel]

That's when you conclude that the only way to trust an answer is if it produces a full breakdown of number of dogs in each of the 2³ possible states, and then verify that it satisfies each of the givens.
What's up with the hints though? 131 is definitely no the answer to question (b), but then what it is?

[thorny hollow]

It says to use a venn diagram and start from inside out

[coral parcel]

"It says"?

[thorny hollow]

It's what the hint says

So

hmm

[thorny hollow]

Cus i have 9 in the middle, I'd subtract 9 from the ones that knows 2 skills only, so I'd have

8 dogs who can sit and stay, 3 dogs that can stay and roll rover and 9 dogs that can sit and roll over. So, if this reasoning is right, the answer for question b is 20?

[thorny hollow]

[spare slate]

the answer for question b is 20?
yes.

[thorny hollow]

So

The answer for a is 84

Or 85

Wait I just guessed sorry

Leemme thunk

57?

[coral parcel]

Instead of asking here, I will once again recommend this way to check your work.

[thorny hollow]

Wdym by a full breakdown? 2³ possible states?

[spark field]

This goes back to the venn diagram idea

You have 3 conditions, A B and C

Each one has 2 possibilities

yes A or no A, yes B or no B, yes C or no C

So you have 2^3 possible states

no A, no B, no C

yes A, no B, no C
no A, yes B, no C
no A, no B, yes C

yes A, yes B, no C
yes A, no B, yes C
no A, yes B, yes C

yes A, yes B, yes C

you need to make sure that your answer accounts for all possibilities, and also plug back in your answers to make sure it satisfies each of the equations you constructed ("the givens")

Only then can you be certain that your answer is valid

The only way to get better than just producing multiple answers, who knows of which is the correct answer, is to know how to check your answer

[thorny hollow]

I see

Thank u

[spark field]

Or at least that is what I assume tropo meant

[thorny hollow]

Im trying to understand how to apply it here

Do I attempt to solve my question and substitute A, B , C with my answers?

[spark field]

A, B and C here are "can sit", "can stay" and "can roll over", respectively

[thorny hollow]

Oh

Oh

Ic

[spark field]

Here is a 'full workup' if you will

There are shortcuts and better ways to approach this (with a little simplification of the PIE) but if you were to go complete brute force

In this case I would look at the givens here and go

Starting from 9 dogs can do all three (that is case yes A yes B yes C)
17 dogs can sit and stay -> 17 - 9 = 8 dogs can only sit and stay (case: yes sit, yes stay, no roll over)
12 dogs can stay and roll over -> 12 - 9 = 3 dogs can only stay and roll over
18 dogs can sit and roll over -> 18 - 9 = 9 dogs can only sit and roll over
By turning them into individual cases, I get sets of dogs that do not overlap (basically, I am partitioning the full set of dogs into the 8 cases)

Then
50 dogs can sit. Of those 50,
8 can also stay but not roll over
9 can also roll over but not stay
9 can do all three
So exactly 50 - 8 - 9 - 9 = 24 of them can only sit

29 dogs can stay
3 can also roll over but not sit
8 can also sit but not roll over
9 can do all three
29 - 3 - 8 - 9 = 9 dogs can only stay

34 dogs can roll over
3 can also stay but not roll over
9 can also sit but not stay
9 can do all three
34 - 3 - 9 - 9 = 13 can only roll over

Now I have all the cases
9 dogs do everything

8 dogs both sit and stay (but no roll over)
3 dogs both stay and roll over (but not stay)
9 dogs both sit and roll over (but not stay)

24 only sit
9 only stay
13 only roll over

9 do nothing

I'll leave adding up the total number of dogs to you

You're essentially doing the work of a venn diagram, by enumerating the number of dogs in each possible state (that is every intersection of circles in the venn diagram)

Again not necessary, but hopefully at least this is instructive

[thorny hollow]

You did the cooking and left me with the incredible task of eating ur food

Not just

Lemme read it

Thx

Yes 84 was right wasn it

Interesting manner of sorting it

Ill see if I find other problems to apply that

U all are very sweet instructors, thank u and sorry to bother u with my neuronless brain

[spare slate]

<@&268886789983436800>

[lunar pawn]

Does a version of the Akra-Bazzi method also provide another way to prove the master theorem in its full generality? I see this paper refer to the continuous and discrete Akra-Bazzi theorems, though I can't parse the paper myself as the proofs are written as formalizations in some proof assistant.

[haughty garden]

Yes, the Akra-Bazzi method can be used to prove the continuous master theorem and it is, in some sense, then most general formulation of the master theorem

[thorny hollow]

1.4.2 is 56? (8*7)

[spark field]

Yes

8 choices of shirts, then 7 choices of ties

Or $8^2$ tuples in $[8]²$, take away 8 for matches $(1,1)$, $(2,2)$, etc which are invalid, gives $64 - 8 = 56$

[thorny hollow]

How

[vital dew]

Coolempire93

[spark field]

Each number 1 through 8 represents a color

The first entry of the tuple represents shirt color

Second tie color

[thorny hollow]

No I mean the in terms of a function part

[spark field]

Oh that was me writing the wrong thing by accident

I meant individual mappings of elements

[thorny hollow]

Oh true

Permutations can be shown in means of tuples

True

[spark field]

In terms of functions

I guess there are 8² mappings from [2] to [8]

But that's just coordinates

I.e. just writing writing tuple entries as function

[thorny hollow]

Ic

Thx

[spark field]

I know that representation is nice for something but I can't remember

Vectors as functions are really interesting though

[thorny hollow]

True

[halcyon nest]

If you want to count all 3-permutations of a set with 10 elements (so think same problem but shirt, tie and pants and 10 colors), that's the same as counting how many injective functions exist from the finite set {1,2,3} to the finite set {1,...,10}, which is 10(10-1)(10-2), called a falling factorial

[thorny hollow]

1.4.7 would be 8*7*6 possibilities?

[spark field]

cf what IOM said

[thorny hollow]

[spark field]

Oh I guess yet another approach goes something like

Choose 3 from the 8 to win medals
Then permute those 3

3!*(8 choose 3) = 3!*8!/(5!*3!) = 8!/5! = P(8,3) that is the 3-permutations of a set of 8 elements

Me when combinatorial proof of formula for permutations and combinations in terms of the other

Idk i can't think of anything cool and insightful

[thorny hollow]

I can already see me crying when I take some proof based counting theory

[hidden totem]

counting is weird, you'd be surprised what is easy and what is hard

[hidden totem]

if you want an accessible explanation to how counting proofs work and how to check your work: https://m.youtube.com/watch?v=uxjAHkn4VFI