discrete-math

[elder berry]

I'm mistaken, I think you're correct indeed. Since only the group IAE and EAI need to be counted.

[vital dew]

Karlan

[frank sun]

Does anyone know. We pick 4 cards from 13 ranks, then 2 cards from a single rank, then 1 card from 1 rank three times.

[elder berry]

When you pick the 4 ranks for the cards, you don't specify which rank will be a pair.

Because you can set any of 4 chosen ranks to be a pair, you need to multiply by 4

rather 4 choose 1

So you end up with $\binom{13}{4} \binom{4}{2} \binom{4}{1}^4$

[vital dew]

peaceGiant

[frank sun]

Thanks 🙂

[still slate]

Hello,
I'm trying to show a sequence of equivalencies for (¬q∧(p∨p)) → ¬q
I'm getting lost when we apply the demorgans law and the double negation. I know for demorgans law we can take the ¬q∧(p) to ¬q V ¬p, the double negatives at the front confuse me.

[elder berry]

De Morgan's rule says that $\neg (s \land t) \equiv \neg s \lor \neg t$

[vital dew]

peaceGiant

[elder berry]

So, think of s as not q, and t as p

[vital dew]

peaceGiant

[elder berry]

Makes sense?

[still slate]

So for demorgans rule, it doesn't matter if the orginal ( s ∧ t ) has a not in front of the s? we can still apply it?

[elder berry]

Yup, you can think of not s as a single proposition. You can substitute it with a different letter like not s == r

It's very common to apply these rules to more complicated expressions as well, for example we can substitute s with (p and not q and r) or whatever we feel like

and we could still apply it

[still slate]

I understand, I guess that was throwing me off because I though it had to be exactly like demorgans law to apply it. even though its "not q" and not just q, we can apply demorgans law.

[weary tiger]

Sanity check if my reasoning's correct: In class there are 18 boys and 8 girls, with distinguished boy A and girl B. Every day 2 boys and 1 girl are picked. Need to find the probability that A and B have been picked at least once in the span of 5 days. Let's compute to complement of this event: A or B haven't been picked: $$P(A orB) = P(A)+P(B) - P(A and B) = \left(\frac{16}{18}\right)^5 + \left(\frac78\right)^5 - \left(\frac{14}{18}\right)^5$$ Does that seem right?

[vital dew]

Catematician

[weary tiger]

Adding to that, what Im struggling with is finding expected value of number of kids being picked in 5 days. Natural approach was to find E(X+Y) where X - number of boys, Y - number of girls. P(Y=k) should be ( 8CK * 5Ck * k^(5-k))/8^5 (we pick k girls, then assign them days, remaining days have k^(5-k) choices). I have a problem with P(X=k).

Hmm now Im thinking my P(Y=k) isn't correct, it may be counting more than it should?

[tardy comet]

Can someone help me 4-colour this planar graph? It's the Goldner-Harary graph.

[stray reef]

should work

[tardy comet]

Thanks, Ann

[lusty fern]

Hi i was wondering if i have the correct interpretation of union of sets here

my understanding:

[weary tiger]

Not quite, for example A_2 should be {o,{o}}.

But the cardinality should be 3, this is one of the definitions of natural numbers in set theory, A_i corresponds to i.

[lusty fern]

I’m confused

I think I have too many brackets

[coral parcel]

Yes.

Except for the extraneous brackets, the answer has the right overall shape.

[lusty fern]

So what should A_1 be? Just Ø?

[coral parcel]

You have A_1 right.

It's only in A_2 that you start to have too many brackets.

[lusty fern]

fixed it

this should be good now

[coral parcel]

That looks right.

[lusty fern]

so strange to wrap my head around this concept im not sure why

[coral parcel]

It's a common trouble to have. You'll get it.

[lusty fern]

thanks i appreciate your help

[remote crane]

Is this valid?

I tried to modify the books version of sqrt(2) is irrational but idk if its right

[little prism]

yes. but the important step is that p^2 being divisible by 3 also implies that p is divisible by 3. maybe expand on that

[remote crane]

thx

[carmine swallow]

could anyone please explain me Please? this class is killing me :/

[grand totem]

You sure the there are no typos in the question?
The conclusion (s) isn't mentioned in your set of premises

Oh woops nvm

While that is true, notice that q is mentioned twice in your premises, one time negated. And since from a contradiction anything follows (principle of explosion), you might want to try and derive q ∧ ¬q and then conclude with s.

[viral turret]

Could anyone plz help which cards go eliminate?

[tepid crystal]

Can anyone translate this binome form into factorial, just like for exmp. "5 choose 2" is equal to "5! / 2! * (5-2)!"

[final cliff]

Is this supposed to be a multinomial coefficient? If so it's just 13!/(2!2!2!2!1!1!1!1!1!) (which will obv simplify).

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

(From this thing)

[tepid crystal]

thanks

[honest forge]

Would a ∈ {{a}, {b}, {c}} be true? Since or is a not an element since it is within another set

since the elements are {a} {b} and {c} , a is not an element of the set?

[brave rock]

a is not an element of {{a}, {b}, {c}}

Your reasoning in the second message is correct

[honest forge]

Would that also stand for ⊆

So that 3 ⊆ {{1}, {2}, {3}} is false

[brave rock]

That is just nonsensical, 3 is not a set ||if a pedant comes and tells me that typically 3 is constructed as a set, I will scream||

It's not (usually) meaningful to ask if 3 is a subset of a set

[honest forge]

That's what I was wondering since 3 is an element you shouldn't it be checking against sets is an element of set

But thats my practice problem lol

[brave rock]

They probably want you to say that that is not a meaningful proposition, or perhaps just to say that it's false.

Fwiw it's false even if you take 3 to be the usual construction of 3 in set theory.

[honest forge]

False since 3 is not a set, therefore all elements of 3 cannot be contained with the set

[brave rock]

I'd mark that answer as correct, sure

[tepid crystal]

How many different 5-digit numbers are there (abcde) where, 1 ≤ a ≤ b ≤ c ≤ d ≤ e?

What method should i use to solve such problem?

[coral parcel]

Do you know how to count partitions? Such a number corresponds to a nonnegative partition of 8 into six terms, namely (a-1, b-a, c-b, d-c, e-d, 9-e).

[stray reef]

im gonna be pedantic and say thats not a partition

at least qualify them as ordered partitions

ordered partitions of fixed length

or something

[coral parcel]

Hmm, the correct term feels like it's slipping my mind.

[stray reef]

combination with repetition or somesuch?

[coral parcel]

I'm almost sure "combinations" will give the wrong idea to a typical combinatorics student.

Anyway "ways to get 8 as an ordered sum of six nonnegative integers".

[true venture]

Locally restricted composition?

Related, how many locally restricted compositions of n are there, where the first term is 1 and the difference of adjacent terms is within {-1,1} ?

Example for 6 there are two : 123 and 1212.

[unique abyss]

try raising a small adjacency matrix of a simple graph to say 2 to build some intuition

[astral sand]

Is a hashing function one-to-one, onto, both, neither, or different depending on the situation? Why?

[unique abyss]

Typically they are not one-to-one as the domain size vastly exceeds the co-domain

There do exist “perfect hash functions” that are injective however (this necessarily requires them to take have a limited domain as well)

As for onto, it’s generally unknown for crypto hash functions

Modern day crypto hash functions like the SHAs have quite a few elements in the co-domain so its very computationally expensive to compute if they are all possible outputs

But if we’re talking about a hash function that’s in a hash map implementation for example, then that would be onto and it’s pretty easy to prove it

[astral sand]

Ok, thank you @unique abyss

[rough coral]

how does Modus ponens work exactly?

I have no idea what it's talking about

[unique abyss]

Modus ponens is typically used as a rule of inference

Intuitively, it’s like if you had the implication “if it’s raining outside, then I’ll get wet.” And you find out it’s raining outside. So you will get wet. That’s what modus ponens is saying

So we can infer you’ll get wet because

We know if it’s raining, then we will get wet

And we know it’s raining

So we can infer you’ll get wet

[rough coral]

oh...

and then what is it different from Modus tollens ?

I'm kind of stuck between those two.

[unique abyss]

Are you familiar with the contrapositive of an implication

[coral parcel]

Modus ponens is: If you know P->Q and P, you can conclude Q.
Modus tollens is If you know P->Q and ¬Q, you can conclude ¬P.

[primal jolt]

I need help on #10. How do I prove it for all integers n

[grand marten]

proof by induction. establish base case where $n=1$, then try $n+1$ and expand. you'll get $n^3+6n^2+11n+6$. the terms with 6 can be ignored. $n^3+11n$ can further by proved to be divisible by 3 by proof of induction again. let's call it $k^3+11k$ to separate it from our earlier proof. let's say $6l=k^3 +11k$. then, for $k+1$, we have $(k+1)^3+11(k+1)=k^3+11k+3k^2+3k+12$. note that $k^3+11k$ is in the expanded form. some more simplifying: $6l+3k(k+1)+12$. everything in here is divisible by 3.

[vital dew]

RIN

[carmine swallow]

hi , someone could tell me what im doing wrong i would appreciate it thanks

[wicked breach]

you should not have purple in your response

use only p, q, r, and some of the logical symbols that they mentioned

[carmine swallow]

should i state that p is purple and p is quiet?

[primal jolt]

i see, but from my understanding i thought using Proof by Induction proved it only for all Natural numbers. or is this wrong?

if i had n=k-1, (and assuming k<0), and solved it similarly would that be correct?

[sick grail]

You are correct in thinking you need more proof for 0 and negative numbers, and going down instead of up in the inductive step achieves this, although you can use the same base case

There's also a (imo better) proof that doesn't use induction

How often is there a multiple of 3 when counting up?

[primal jolt]

wdym

[sick grail]

There is a multiple of 3 every 3 integers

You have 3 consecutive integers multiplied together

[grand marten]

does that count as a mathematical proof?

[sick grail]

So one of those is a multiple of 3

[grand marten]

i just assumed it wanted induction

[sick grail]

Unless you're expected to show that multiples of 3 are spaced this way, yes

Although if this is in a section about induction probably better to do that anyway

Looking at q8 it isn't

[primal jolt]

i see what you mean by the 3 consecutive integers part and it does make sense to me. using induction though, i made n=k-1 for the Inductive Step, and plugged into the original problem. so i got 3/(k-1)(k)(k+1).

in the first part, my I.H. was for n=k (where k>0), 3/(k)(k+1)(k+2) is true. now that im trying to show it for negative numbers my I.H. is for n=k-1 (k<0), 3/(k-1)(k)(k+1). i see that the only difference is that there's a (k-1) but what now?

[primal jolt]

?

[chilly kayak]

proof by cases. there are only 3 types of numbers regarding their multiplicity by 3. 3n, 3n+1, 3n+2. so you test that claim with each of the cases. and you will find that that expression is always 3 multiplied by some integer.

[sick grail]

Sorry it got quite late. Your inductive hypothesis is still k, in the next step instead of k+1 you do k-1

[tidal tulip]

lets say i want to prove f: X->Y, f o id_x = f. is this a valid proof: (f o id_x)(x) = f(id_x(x)) = f(x) --- im confused because i end with f(x) as opposed to function f with not input variables

[hidden sparrow]

@tidal tulip how do you define two functions being equal then?

[tidal tulip]

if for every input they both have the same output

[hidden sparrow]

and that's what you've shown there, so it seems fine

[tidal tulip]

ah, ok so that's a valid proof?

[hidden sparrow]

yeah -- you've shown f o id_X and f agree on every input

[tidal tulip]

similarly is this a valid proof. prove g:Z->X id_x o g = g, proof: (id_x o g)(z) = id_x (g(z)) = id_x (x) = x = g(z)

[blissful bough]

i didnt think a channel for discrete maths existed

im so glad

does anyone know about augmenting paths

[coral parcel]

Someone might, if you ask a question about them. https://dontasktoask.com/

[blissful bough]

i do not understand the question

[coral parcel]

(If I recall correctly, "augmenting paths" is an auxiliary concept used in algorithms for constructing maximal matchings in bipartite graphs)

(Hmm, or apparently non-bipartite graphs too).

[blissful bough]

i looked into the lectures they just explained how to do it but it didnt really teach us how to read them questions ;-;

i kinda have an idea on how to do it but i dont understand what the trivial augmenting paths actually mean

[coral parcel]

This is not a "be clever" exercise. It's jus a check that you understand how the algorithm works, by showing what it does in one particular case.

The "avoid trivial paths" just means "don't do it in the boring way where you already know a maximal matching from the beginning and add exactly those edges one by one, declaring each edge you add to be an augmenting path of its own".

[blissful bough]

if i start augmenting does it include the lines that make the star or just the outside of the star?

[coral parcel]

All the lines in the diagram are equally good edges in the graph.

[blissful bough]

is this one way to do it

[coral parcel]

You're supposed to show a whole sequence of stages of the algorithm, each with a single augmenting path.

(Or, well, at least note down the augmenting path you use in each step and which edges the matching NOW contains).

[blissful bough]

um

im confused

how do i show it?

is it like

i = 0 : c->b

i=1: ....

[coral parcel]

Well the staring state is cd, not bc.

In each step I'd write down the augmenting paths I'm using and which edges are now in the matching.

So for example we could start with

1. Use the augmenting path b,c,d,g. The matching is now {bc, dg}.
2. Use the augmenting path j,c,b,a. The matching is now {ab, cj, dg}.

[blissful bough]

ah i see

thank you

[blissful bough]

Is this okay

[tidal tulip]

can i get a proof check for this

prove g:Z->X
id_x o g = g,

proof: (id_x o g)(z) = id_x (g(z)) = id_x (x) = x = g(z)

thus id_x o g = g

[brave rock]

You introduce this new symbol x for no reason. Just say: id_X(g(z)) = g(z).

It might be worth saying something like "this is true for all z, so id_X o g = g by definition"

[tidal tulip]

how do you know it’s true for all z? isn’t that what i want to prove

[brave rock]

Uh yes that is what you proved

I'm saying, just say that's what you proved

[tidal tulip]

i’m confused what changes should be made

(idx o g)(z) = idx(g(z)) = idx(x) = x = g(z)

thus for all z: idx o g = g

is that what you meant

[brave rock]

What is this thing "x" that you introduce

You've started using it without telling us what it is

I don't know why you say "idx(g(z)) = idx(x) = x = g(z)" instead of just "id_X(g(z)) = g(z)"

thus for all z: idx o g = g
No, this is pointless; z is not involved in this statement.

I'm saying: you have proven that (id_X o g)(z) = g(z) for all z, which means that id_X o g = g.

[tidal tulip]

im not entirely sure how to state the proof without using variables x in X and z inZ

[brave rock]

Okay hold on for a moment

[tidal tulip]

the only modifications i’d make is x in X, z in Z <same proof computations>

[brave rock]

I'm writing id_X because this is the identity function on X (the set)

you're writing id_x

what does this mean to you?

[tidal tulip]

Id_x should map X to X

id_x should map specific x in X to same x in X

[brave rock]

so why do you write it with a lowercase X? Is this just shorhand, or is this associated with any particular x in X?

I'm asking for a good reason, I assure you

[tidal tulip]

i assumed it was a specific x since g(z)=x

[brave rock]

OK no.

So you've done a lot more in this proof which you didn't mention, and which show me that you don't actually totally understand what's going on.

1. id_X is associated with the set X, not any element of x.

It is indeed the function such that id_X(x) = x for all x in X.

2. You do not need to say "for all x in X..." in this proof, and what's more, you erroneously conclude that g(z) = x when you cannot infer this in general.

It concerns me that you say you can't imagine doing this proof without saying for all x, because it is completely unnecessary

[tidal tulip]

well i never seen an example of this so im doing a best guess which is assuming they meant mapping specific elements in sets

to other elements in sets

and showing for any elemental mapping you get certain results

[brave rock]

OK, let me show you a very pedantic proof of this fact.

[tidal tulip]

ok

[brave rock]

We wish to prove that id_X o g = g.

We first prove that for all z in Z, (id_X o g)(z) = z.
Proof of this smaller fact: Let z be any element of Z. Then (id_X o g)(z) = id_X(g(z)) by definition. Since g(z) is an element of X, by definition of id_X we have id_X(g(z)) = g(z), so we conclude (id_X o g)(z) = g(z). The element z was chosen arbitrarily, so we are done.

Now by the definition of equality of functions given earlier, we conclude that id_X o g = g from the smaller fact proven above.

[tidal tulip]

ahhh i see

[brave rock]

I must say this is a very pedantic proof and you won't be expected to write proofs of this kind always

[tidal tulip]

okay. i see. there is another proof i need to do that’s similar. i’ll try this approach on it

thanks for showing me this

[brave rock]

No worries. I'll be happy to give your next proof a look

[blissful bough]

how do i know if this is an interval graph?

[tidal tulip]

@brave rock i took some space away from your solution and wrote both problems in my own manner, see if this looks good

Let,

f: X->Y
g: Z->X
id_X: X->X

Prove:

a) f o id_X = f
b) id_X o g = g

meta-comment: to prove that two fucntions are equal, we have to show that for every input both functions have the same output.

a)

We have:
f o id_X: X-> Y
f: X->Y

We want to show f o id_X = f.

Proof:
if x in X
(f o id_X)(x) = f(id_X(x)) = f(x)
The element x was chosen arbitrarily, so we see that for any x in X: f o id_X = f

b)

We have:
id_X o g: Z->X
g: Z->X

We want to show id_X o g = g

Proof:
if z in Z
(id_X o g)(z) = id_X(g(z))
Note g(z) is in X, thus id_X(g(z)) = g(z).

The element z was chosen arbitrarily, so we see that for any z in Z: id_X o g = g

[brave rock]

So your proofs are correct, I do agree w them

I just want to comment on one thing

When you're saying:

for any z in Z: id_X o g = g
z isn't actually mentioned anywhere in this formula; you don't need to mention it

In fact this actually breaks things if Z is the empty set!

The point of saying id_X o g = g is that we don't have to mention any elements

But apart from that I don't have a problem w what you've written

[tidal tulip]

what should i correct / delete in the above proof then? in your proof you wrote >We first prove that for all z in Z, (id_X o g)(z) = z. Proof of this smaller fact: Let z be any element of Z. -- does that not include z?

[brave rock]

Yes that does

But n.b. that's proving the statement "for all z, (id_X o g)(z) = g(z)"

Again like I said, this statement certainly is equivalent to id_X o g = g

but the latter doesn't have any mention of z

Does that make sense?

[tidal tulip]

i see. im confused as to how to prove id_X o g = g then ig

because to show they are equal means all inputs / outputs match

how do you prove this without using inputs/outputs

[brave rock]

That's exactly what "for all z, (id_X o g)(z) = g(z)" means!

It means!

For any input z, the outputs match!

I thought we'd gone through this?

[tidal tulip]

yeah i understand that part, but that still uses z

you said you can do it without using z

[brave rock]

That's not what I'm saying at all

[tidal tulip]

which suggest you can do it without using elements

[brave rock]

No

[tidal tulip]

(in my misunderstanding)

so what needs to be corrected in my proof, im confused

[brave rock]

Strings, do you understand what "for all z..." means? Like,

[tidal tulip]

yeah

for every element z in Z

[brave rock]

That's correct.

But note that no particular element of Z is mentioned

[tidal tulip]

ah

[brave rock]

Now

I define equality of functions as such

if f and f' are functions A -> B

f = f' when, for all a in A, f(a) = f'(a)

Now note

a is not mentioned when I write f = f'

It is pointless to say "for all a, f = f'"

because the definition of f = f' means, as I stated, "for all a in A, f(a) = f'(a)"

Does this make sense?

[tidal tulip]

yeah

[brave rock]

OK great

[tidal tulip]

im trying to figure out how to patch my proofs then

[brave rock]

So you say:

for any z in Z: id_X o g = g

Do you now see why this is redundant?

[tidal tulip]

yeah

[brave rock]

Great.

That's all.

[tidal tulip]

ok i see

[brave rock]

I should also mention why it causes issues when Z is the empty set

if Z is the empty set, then for any predicate P, "for all z in Z, P(z)" is true

This is called vacuous truth

[tidal tulip]

ok i see

[brave rock]

If we want to prove that id_X o g = g, then it's insufficient to show that for any z in Z: id_X o g = g, since if Z is the empty set, it tells us nothing.

[tidal tulip]

Let,

f: X->Y
g: Z->X
id_X: X->X

Prove:

a) f o id_X = f
b) id_X o g = g

meta-comment: to prove that two fucntions are equal, we have to show that for every input both functions have the same output.

a)

We have:
f o id_X: X-> Y
f: X->Y

We want to show f o id_X = f.

Proof:
if x in X
(f o id_X)(x) = f(id_X(x)) = f(x)
The element x was chosen arbitrarily, so we see f o id_X = f

b)

We have:
id_X o g: Z->X
g: Z->X

We want to show id_X o g = g

Proof:
if z in Z
(id_X o g)(z) = id_X(g(z))
Note g(z) is in X, thus id_X(g(z)) = g(z).

The element z was chosen arbitrarily, so we id_X o g = g

Assume all sets are non-empty

i can fix grammar

i changed the last line

The element z was chosen arbitrarily, so we see :id_X o g = g

similarly for the other a)

[brave rock]

You shouldn't assume this... the fact id_X o g = g is still true even if the sets involved are empty.

[tidal tulip]

ok i see

[brave rock]

Whoops I replied to the wrong message

[tidal tulip]

then do i need to do a proof by cases

one if sets empty

[brave rock]

No, the proof you've given works

[tidal tulip]

ok

[brave rock]

I... I feel like you're not listening. Like, I was explaining why proving "forall a, f = f'" isn't helpful. This is a different thing.

Listen, fwiw, the proofs you've written now are correct.

[tidal tulip]

i understand one is about the mechanics of showing how redudant my sentence was

and one is about vacaous trutjs

[brave rock]

That's right. OK, well I wish you good luck in learning more about proofs.

[tidal tulip]

ty so much for your help

i learned a few things from this

[brave rock]

Glad to hear it. Feel free to ask here or in a help channel (probably preferable) if you have more questions

[tidal tulip]

will do!

[ashen canopy]

when something is a proposition, that means it's either true OR false right?

(learning axioms on epsilon relations)

[brave rock]

Short answer, yes.

Long answer: there are some systems of logic in which this isn't the case, but not the one you're working in.

[ashen canopy]

ahh ok

thank you!

[ashen canopy]

i might need more paper...

this is only five minutes of notes

[unique abyss]

Knew it

[primal jolt]

i need help with 10. i used induction to prove for all natural numbers but im confused on how i would prove this for all integers n

[chilly kayak]

prove for n=1

then assume that for n=n the claim is true

then replace n->n+1

you will get another expression which will have a form dependent off the original expression

[primal jolt]

yeah i tried that and i got the answer for all natural numbers but now how do I prove it for all integers

[chilly kayak]

so you need for negative integers numbers

[primal jolt]

yes

[chilly kayak]

prove with induction for -1( the whole expression)

with n being positive

-1 times "the whole expression"

[primal jolt]

ok

i got -k^3-3k^2-2k

heres my work for the natural numbers

so i noticed that the part in blue is the same just with a (-1)

nevermind, not the part in blue but the one that has the arrow

[chilly kayak]

since you already proved that is multiple of 3 when is positive

then, it is true for the negative form aswell

if 3k is multiple of 3, -3k it is too

[rough coral]

What is the meaning of p ↔ q in the truth table?

I know p->q and q->p, but I have no idea what p<->q means.

[coral parcel]

It's either defined by the truth table in the first three columns, or an abbreviation for "(p->q) and (q->p)"

[carmine swallow]

hi , can anyone tell me if there is a mistake_

?

thanks

[verbal crystal]

it can be read as "p if and only if q" or "p iff q". iff is shorthand for "if and only if".

It is called a biconditional

so as you can see in the chart, p and q both have to be a true statement to get a T in the output.
so top line: "true if and only if true" = T
2nd line: "true if and only if false" = F
3rd line: "false if and only if true" = F
4th line: "false if and only if false" = T

but yeah Troposphere was right, it can be broken down as "(if q then p) and (if p then q)"
like this:

[verbal crystal]

I'm pretty sure the 2nd statement should be (q -> r) or "if q then r"
Not sure if the "Only" changes anything but in any case it doesn't mention to use the biconditional symbol

The rest look correct though

[carmine swallow]

thanks ill check that

[coral parcel]

"Only if" is the opposite of "if".

[verbal crystal]

ah that makes sense

[coral parcel]

The natural-language logic behind this meaning is arguably a bit tortured, and it basically has to be learned as a fact -- but it is firmly established in mathematics and not going to go away.

[weary tiger]

Can someone help me with thiis?

[tidal tulip]

my question is when you prove two functions are equal (every input has the same output) in one direction do you need to prove it in the reverse direction

ie

if you proved f=f’ do you then need to prove f’=f

[cerulean wind]

no

[tidal tulip]

@cerulean wind thanks. why not in this case?

i didn’t prove it like that was just curious

[lusty fern]

How do I get better at counting problems? It’s basic stuff but for some reason it hard for me

[unique abyss]

Any specific part of the problem you notice you trip up on?

Without more details, it's hard to give a answer that will help you in the future

You should try to conceptually understand all the "tools" being used (combinations, FTC, etc.) and then do as many practice problems until you feel comfortable

if you can't solve an excercise after dedicating a reasonable amount of time, look at the solution, understand it, see where you went wrong in your train of thought

[lusty fern]

Im learning permutations and combinations right now , and the concepts are easy but I get some questions wrong because my counting techniques are off

I think I need to go back and work on that first

[rough coral]

what is addition rule in equivalence rule?

I do not understand why p->p v q works

[last timber]

@rough coral consider that you know that

[vital dew]

Commander Vimes

[last timber]

then it means that either p is false and p or q can be anything (but obviously it just then means that we do not care about q

another option is that p is true and obviously p or q is true then

now using this you can get to the idea of proof

let p = x in A and q = x in B. If p is true then p or q would be true as well. Since x is arbitrary here we see that for all x in A we get x in A or x in B i.e. x in A U B

[unborn widget]

This should be false, right? Or am I missing something? the "for all z" becomes
"for all x" suddenly

[last timber]

yep

[brave rock]

Perhaps this was a typo

[unborn widget]

even if it was a typo this should be still false right?

[brave rock]

Yeah

[unborn widget]

can someone enlighten me on what should be the answer of these two problems?

[weary tiger]

can i get help on this?

#discrete-math message

[ashen canopy]

digital notes fit so much more space omg

[verbal crystal]

How can I read the "slanted E"?

I understand the | with a line through it means "does not divide by"

but I'm not sure what the slanted E means. And I am assuming the Z means sum

[brave rock]

That is the symbol $\in$

[vital dew]

Boytjie (Plutonic Relations)

[brave rock]

It means "is an element of"

It's erroneously been italicised there

[verbal crystal]

so a, b, n is an element of Z?

[brave rock]

Here this is shorthand for a is an element of Z, b is an element of Z, and c is an element of Z.

So it's saying a, b, and c are integers :)

[verbal crystal]

Ok, so is Z just an arbitrary variable?

[brave rock]

No, Z is the set of integers.

[vital dew]

Boytjie (Plutonic Relations)

[verbal crystal]

I see

[brave rock]

Your question tells you this, actually: it says "Z (the integer numbers)"

[verbal crystal]

so
Z = {a, b, n}?

[coral parcel]

No, Z = { ..., -3, 2, -1, 0, 1, 2, 3, ...}

[ashen canopy]

wait, are that symbol and epsilon different?

or is that an epsilon

$epsilon$

[vital dew]

mirupii

[ashen canopy]

damn it

[coral parcel]

The $\in$ symbol was originally an $\epsilon$, but they are always typeset differently nowadays.

[vital dew]

Troposphere

[ashen canopy]

so… the axioms of set theory

[verbal crystal]

I see. So it's saying they are just some random integers that do not divide by each other

[brave rock]

No.

See Troposphere's comment.

[ashen canopy]

i can just call it “in” rather than “epsilon”?

[brave rock]

Yes, people usually do

[ashen canopy]

ahhhh ok

[coral parcel]

They are just some arbitrary integers. The claim is that if you have some arbitrary integers where n doesn't divide the product of a and b, then n doesn't divide a or b separately either.

[vital dew]

lord of crime

mirupii

[ashen canopy]

ahhh ive heard that before

ive never seen it written

should probably look at the lectures im listening to

im trying,

[unique abyss]

Everyone is at different stages in math

[ashen canopy]

ouch, man…

noted, next time i wont ask lol.

[brave rock]

@ashen canopy fwiw, xor often has different notation based on the author's preference. Furthermore this symbol has many other meanings. You really oughn't feel silly for not knowing it, and people shouldn't insult you for it either.

[ashen canopy]

id only ever seen it prior as ⊻…

[brave rock]

Exactly

[tiny arrow]

Hey, does anyone know a youtuber or an online (prefer free) course to start off with basics of discrete math?

[night stream]

hi! can someone help me solve this?

[unique abyss]

It's an application of the inclusion-exclusion princple

I got the number of testers and recruiters being 6

[night stream]

so ow would you figure that out as well?

[night stream]

wait because both testers and recruiters are missing you also dont know how many employees are only testers?
because ya theres a total of 24 but thats from also the testers and engineers and those who are all three
so how would you figure that out as well?

[unique abyss]

You don't have to know how many employees are only testers to solve this problem

begin by excluding the employees that are none of the three categories leaving you with 60 emplooyees

Then use inclusion-exclusion and "fill in the blanks"

60 = 50 + 24 + 14 - 15 - 10 - x + 3

solve for x

that's your answer

[night stream]

wait so x is testers and recruiters ?

[unique abyss]

yeah 👍

[night stream]

OHHHH okay so the way to write it would be |NE |= (E U T) + |R| -(E U R) - (TU R) + |E U T UR|?

wait i dont think that right;-/

[night stream]

wait isnt it 20 not 60

[unique abyss]

You are excluding 20 so you’re left with 60

[unique abyss]

It would be:
$\|E \cup T \cup R| = |E| + |T| + |R| - |E \cap T| - |E \cap R| - |R \cap T| + |E \cup R \cup T|$

[night stream]

ohhh so the 60 are the total employees are in the venn diagrammm

[vital dew]

ALPH2H

[night stream]

ohhhhh okay thank you!

[night stream]

wait after doing the math i got x = 36?

is that correct?

[unique abyss]

I don’t think so

[unique abyss]

Try solving this

[night stream]

hmmmm yeah i got 6 sorry i think my calculator is just being weird thank you!

[gloomy pelican]

What would be the best way to show that the amount of ways that dominoes can be placed on a 2xn chess board is a_n=a_{n-1}+a_{n-2} ?

Adding one 2x1 row

remove one placed vertically from a previous configuration to add 2 horizontally?

[normal raptor]

Would someone please explain to me how the answer is

short of just looking at it and realizing it, is there some theorem I can apply or utilize a law to show how B was canceled?

[vital dew]

lord of crime

[ashen canopy]

I'm having a bit of a hard time understanding the power set axiom

so... for all x there exists y where for all z where z is a subset of y that equivalent to z that has less stuff than x

I think

but I don't really understand what that means

but what's z?

ohhhhh ok

so y is like...

all of the subsets of x

ahhhh thank you!

[glacial flame]

Is there a way to determine the minimum length of a number such that all permutations of a 4 digit number shows up within said number (i.e. 12345 has the numbers 1234 and 2345; I want the minimum length of a number that has 0000, 0001, …, 9998, 9999 in it)?

I presume this would be combinatorics-related right?

(This is just something I randomly thought of so I don’t know exactly where it falls)

[coral parcel]

10003 -- you can avoid repeating any 4-digit subsequence until you've tried them all.

To see this, imagine a graph whose vertices are labeled 000 through 999, with an edge going from abc to bcd for each combination abcd.

Each vertex has equally many incoming and outgoing edges (namely 10 of each), and the graph is connected. So it has an Eulerian circuit.

Pick a place to start and read the circuit off digit for digit, producing an 10003-digit string that contains each 4-digit combination exactly once.

[glacial flame]

Thanks! Time for me to decipher this since I’m a bit lacking on graph-related math 😅

[coral parcel]

The result is called a https://en.wikipedia.org/wiki/De_Bruijn_sequence

[glacial flame]

I think the main thing I’m confused by is what you mean by going from abc to bcd when the labels are numbers (unless a b c d are each digit placeholders?)

[coral parcel]

They are digit placeholders.

[glacial flame]

Ah okay that makes more sense

In the link, the infographic seems to imply that it requires the ability for some subsequences to wrap around from the end to the beginning, or am I just misinterpreting that?

[coral parcel]

Wikipedia describes a cyclic sequence, yes -- but if you have one you can unroll it and just keep a 3-digit overlap between the beginning and the end.

That's why I claimed a length of 10003 digits, rather than 10000.

[glacial flame]

Oh I see, thanks!

[carmine niche]

Weird question, but, just to be sure...
A relation R {(b,a), (a,b), (c,a)} is not symmetric right because while ba and ab pairs are symmetric, ca isn't.
Similarly R2 {(a,b), (b,c), (a,c) (b,a), (a,c), (c,b)} isn't transitive because... while first 3 follow the property second doesn't.

Am I thinking correct?

[coral parcel]

Your conclusions are right but your reasoning is off. Transitivity is not something you test on triples of pairs. You can do one of:

Test on triples of elements, like the formal definiton does:

• (a,b,c) good: (a,b) and (b,c) are in R2 but so is (b,c) as required.
• (b,a,c) good: (b,a) and (a,c) are in R2, but so is (b,c). It doesn't matter that the place where (b,c) appears in your list is not immediately after (b,a) and (a,c) -- sets have no concept of their elements being in a particular order.
• (c,a,a) good: neither (c,a) nor (a,a) are in R2, so the "transitive" property promises nothing here.
• (b,c,a) good: (b,c) is in R2, but (c,a) is not, so the "transitive" property promises nothing here.
• (c,b,a) bad: (c,b) and (b,a) are both in R2, but (c,a) is not.
• (a,b,a) bad: (a,b) and (b,a) are both in R2, but (a,a) is not.
  Once we have found at least one triple that fails the test, we know the relation is not transitive.

Or test on pairs of pairs, which can be a bit quicker to do by eye:

• (a,b) and (b,c) good: these pairs fit together, but (a,c) is also in R2 as required
• (a,b) and (a,c) good: these pairs don't fit together (the second element of the first is not the same as the first element of the second) so "transitive" promises nothing here.
• (a,b) and (b,a) bad: these pairs fit together at b, but (a,a) is not in R2 like it should be.
• (c,b) and (b,a) bad : these pairs fit together at b, but (c,a) is not in R2 like it should be.
  Again, since we have found one or more failures, the relation is not transitive.

[next bone]

is O(n log(n)) in its final form? quite rusty on Big O stuff, I remember doing something like reducing something down to only its fastest growing n, so my instinct says it reduces down to O(n) but also that doesnt feel right

[pale epoch]

its not right

not sure how you would define final form

but all other ways to rewrite O(nlogn) i can think of, look more complicated

you also see it a lot in literature

[next bone]

i see, whats the difference between O(n log(n)) and O(log(n)) then? i guess im struggling with the concept of multiple n's inside Big O

[pale epoch]

nlog(n) grows faster

for some intuition, graph them on desmos

[next bone]

oh woah theyre completely different, I see, thanks!

[pale epoch]

otherwise you have to refer to the definition

[next bone]

yeah I did it on desmos theyre vastly different

[pale epoch]

mostly what you do when simplying big o expressions is

you remove constants so e.g. O(3n^2 + 5) = O(3n^2) = O(n^2)

both additive and multiplicative

and if something grows faster additively, you can cancel it

"cancel"

so O(n^2 + n) = O(n^2)

and O(n+log(n)) = O(n)

but when you multiply expressions, you generally cant do that

[next bone]

ahhhh, thats actually a very clear explanation, thank you!

i have another question with Big O applied in a code environment if you have a sec

[pale epoch]

just ask

[next bone]

I have to come up with a Big O for some code I wrote, which breaks apart a big array of words into lets say 5 (amount doesnt matter) other arrays. it then sorts those smaller arrays using a sort function which has O(n log(n)), then merges all the arrays back together to give a final sorted array. its basically merge sort (which I read also has runs in O(n log(n)) in 3 cases).

im struggling to come up with the final Big O, would it be (5*O(n log(n))) + O(n log(n))? which = O(n log(n))?

[pale epoch]

from your description it sounds like it

if you sort n/5 = 1/5 * n elements, thats just a multiplicative constant

so each sort operation takes still O(nlogn)

so you get (5*O(n log(n))) as you said

the merging im not sure its O(n log(n))?

eh, maybe

but it wont matter

your end result is correct

[next bone]

gotchu thanks!, and finally at the end of the code it goes through all the words in the merged array and writes them to a file which is tecnically O(n) but as you said since this is additive and slower growing it's also irrelevant to the final answer right?

[pale epoch]

yes

[next bone]

great! thanks for your help and swift replies :D

[compact root]

p implies q meaning q is a necessary condition and p is sufficient?

A passenger on an airline qualifies as an elite flyer if the passenger flies more than 25,000 miles in a year or takes more than 25 flights during that year.
In this case, it sounds like the necessary condition is to fly 25k miles + 25 flights?

does this look correct? ∀x((P(x, 25000) v Q(x, 25)) -> R(x))

[mighty flame]

so I was practicing valid/invalid arguments

and I did the same question twice

got to the same correct conculsion

but I was wondering

is it normal to sometimes find two syllogisms where in the instance they mean the same thing?

more specifically

is disjunction elimination the same as modus ponens?

like ik
p -> q
p
q
is modus ponens

isnt this also true by elimination too?
since p -> q is:
~p v q

[final cliff]

They are equivalent but not the same.

It depends a bit on context and what you mean too.

Like, in some proof systems you may have one but not the other. In these cases the difference in form really matters.

You may only have modus ponens and you may want to "apply" it to lines such as ~pvq and p but this would be incorrect (unless you have some other rule in your proof system that allows you to apply modus ponens directly in this situation).

[mighty flame]

Ok thanks 👍🏿

[next bone]

"if the implementation was O(n^2), then for larger n, a 3000 length array should run 4 times as long as a 1500 length array"

how did they get the "4 times as long", and how would I get the same value for O(n*log(n))?

[stray reef]

(2n)^2 = 4n^2, and you cannot get the same value for O(n log(n)) because (2n) log(2n) is not a clean multiple of n log(n).

well, you could divide 3000 log(3000) by 1500 log(1500) perhaps

[next bone]

I see, gotchu, thanks!

[weak grail]

I want to count the no of ways I can get a 7 will I roll a 6 sided die twice.

How to approach this using combinatorics?

I just came across integral solutions, can this problem solved using the following approach:

x1 + x2 = 7  ---- eq1

where{
condition 1 : x not equal to 0
               condition 2 : xi <=6}

Factoring "condition 1" into eq1 :
If xi is not equal to "0"
I can make x1 + x2 = 7 into :

x1 + x2 = 5

But now how do I add the other constraint of "xi <=6"?

[weary tiger]

Well, are you sure by integral solutions you mean >=0 and not in Z?

Because else the constraint x<=6 is unnecessary.

[little prism]

well here in this case of caring about sum=7. if we instead asked about sum=10 then that constraint is necessary

you can for example check here https://mathworld.wolfram.com/Dice.html, equation (10) for the general case or (11) for this specific one. it's not an easy problem

[weak grail]

Xi should be part of natural numbers not even whole numbers.

Cuz when I roll a 6 sided die,

I can get atleast 1 and atmost 6.

So must be greater than 0
And less than equal to 6

[little prism]

I think the point they were trying to make was that because x1+x2=7 and each of them is at least 1, they can't be larger than 6 anyway

[weak grail]

Wow, this is what I was looking for, I did not get to the end of the article. I started with grimaldi text on combinatorics and discrete math. I just got curious about this question. But this article showed me that I need more tools to tackle this problem.

Thanks @little prism the article is gold.

[little prism]

The thing about combinatorics is that some simple question can have quite hard solutions

Similar to number theory for example

But you of course don't know that yet when asking the question

[weak grail]

True that.

Just curious, what are the pre reqs of number theory?

[little prism]

Well for some basic stuff I'd say you can just start.

But it can get quite involved with abstract algebra and complex analysis and stuff like that. Not that I've actually done it

[weak grail]

Got

Got it

[pure acorn]

How discrete is the math? Like police won't catch you with it?

[pale epoch]

this is a serious channel @pure acorn, read the topic

[pure acorn]

Mb I'm just trying to apply logic into what a discrete math is

[pale epoch]

its a common name for a university class

the topic lists some subjects often covered

[weary tiger]

Is this correct?

From Wilson's Theorem:

$n! \equiv n : (mod :n+1) \iff (n+1)$ is prime

$\newline$
If we let (n+1) = p, p is some prime number, then:

$(p-1)! \equiv (p-1) : (mod : p)$

$\newline$
$\implies (p-1)! : mod : p = (p-1) : mod : p = -1$

$\newline$
Since $-1 < p$ for any prime p, -1 = -1 mod p

$\newline$
$\implies (p-1)! \equiv -1 : (mod : p)$

[vital dew]

ↈ Pencil/Idris ↈ

[brave rock]

Yup

[weary tiger]

Thank you

[lusty fern]

is this a correct way to prove the statement is true?

[sick grail]

The best way is to find this p

Are these your notes?

Line 2 is not the correct reading of line 1

[lusty fern]

its my answer to a homework question

we had to set the quantifier for p

I set it to E

[sick grail]

And then line 2 is ...?

[lusty fern]

then write it in english

then informally prove it true

[sick grail]

Ah ok

So what you wrote is the english for something very similar

$\forall k\in\bZ\quad\exists p\in\bN$

[vital dew]

Edward II

[sick grail]

And then the same thing on the end

[lusty fern]

what would be the english translation of line 1?

[sick grail]

The quantifiers are read from left to right

So first there is a p, and for that p every k yada yada

Usually read 'There exists p such that for all k ...'

It's the same p for all k, whereas your english implies that the p can be different

[lusty fern]

ah i see

the quantifier i picked is correct i think? p is E

if p was universal then it wouldnt make sense

[sick grail]

Yeah the statement isn't true for any pair of integers

With one natural

[lusty fern]

ok this sounds much better lol

[lusty fern]

I just have to prove for 1 existence right?

so my proof makes sense

[sick grail]

To prove existence it's enough to find 1

[lusty fern]

Yeah my proof only holds if k >= 0

[sick grail]

It also sets p to something depending on k

Which doesn't work

Because you need one particular p

[lusty fern]

oh you cant do that?

[sick grail]

No because you need a p that works for all k, so if it depends on k it's different for the k

[lusty fern]

oh so am i setting k?

[sick grail]

Also no because it has to work for any k

[lusty fern]

...

[sick grail]

You can set p to something, it just can't change for different k

[lusty fern]

it doesnt hold true then

i think

so idk how to prove these type of questions

proving something exists for something universal

[sick grail]

Do you mean existence then universal quantifiers?

[lusty fern]

yeah

[sick grail]

Because then it's something exists such that for something universal

It's confusing because in english we put it backwards

[sick grail]

This is universal then existence

[lusty fern]

this order?

[sick grail]

Yeah

[lusty fern]

universal is after existence?

[sick grail]

Yes but when in english we say something exists for anything that is not what we mean

Something exists for anything means the something depends on the anything (usually)

E.g. there is a number for any even number that divides it

[lusty fern]

so its interpreted as for anything there exists

[sick grail]

I think I've confused myself

(This is why the symbols were invented, but learning them is painful)

[dense glade]

in conditonal probability, how do you estimate the numerator
if I don't have P(AnB)

[lusty fern]

wait first of all its exist -> all right? Not all -> all

cuz p is natural number

so all natural number does not hold true for all integers

so its false

so it has to be exist then all

[sick grail]

This means you can take any k, and then there is a p for that k that something is true for.
e.g. for any even number there is a number that divides it (this is p = k/2)

This means you can take a specific p, and then no matter what k you take something is true

e.g. There is a number p so that for any integer k, p divides k

(That is p=1)

[lusty fern]

wait my proof is wrong i think

you cant set p to k something?

[sick grail]

No because you need one p that works for any k

Is you set it to k something, then it changes with the k

[lusty fern]

im doing a proof by case where p is 0 , 3 cases where k is - , 0, or +

i think this works

[sick grail]

Yep

Quantifiers are a bit weird to learn because they're different from english, but helpful for precisely the same reason

[lusty fern]

thanks, i think i understand it now.

@sick grail ok so using the wording technique from the previous question, this is how you translate the first like here in English?

[sick grail]

Yep

[lusty fern]

niceeeeeeeeee

[lusty fern]

So i just set p to something, and if the condition holds true then its proved

I think i understand it now!

[sick grail]

Except the statement is false?

[lusty fern]

wait i mightve set the quantifiers wrong

i can choose the quantifiers for m and p

i have to choose m and p quantifiers

oh i should make p a quantifier too

WAIT

just make everything universal????

I think my professor advised against doing that though

[sick grail]

Sorry I can't help more I'm going out

[lusty fern]

I dont remember exactly what he said

[sick grail]

Existential

[lusty fern]

?

[sick grail]

He probably said existential

[lusty fern]

oh

[weary tiger]

are you guys in first year uni?

[little prism]

well some are, some aren't

[torn dome]

Could someone please help me with this?

[crisp veldt]

Im assuming A^c is the complement of A

Which is just everything in the universal set thats not in A

So then everything thats not in A but is in U is a subset of B

So because the union of A and
A(complement)= U then the union of A and a set containing all of A(complement) would be atleast U and since A and B are subsets of U their union cant be greater then U

@torn dome hope that helps

[torn dome]

Thanks!

That sounds reasonable

Can you vc?

[crisp veldt]

Im on cell data rn so id rather not

[torn dome]

Couldn've I done it by allowing A^c = B?

[crisp veldt]

Well if that were true then yes

[torn dome]

I see but its not in this case

[crisp veldt]

But B is possibly greater

[torn dome]

So suppose A and B are any sets

We must show that if A^c subset B then A U B = U

[crisp veldt]

Yep

[torn dome]

Let x be any element in A^c subset B

Let A^c = A

[crisp veldt]

No

Thats just wrong

[torn dome]

Ok so do I let x be any element in A U B?

[crisp veldt]

Idk about that

All i know is A^c never equals A

Unless maybe your U is the null set

[torn dome]

I thought you said it did

[crisp veldt]

No it equals everything in U not in A

[slender skiff]

Can somebody help me solve a question?

[last timber]

[weary tiger]

Okay, so I'm doing this counting problem and I'm not sure if this is the best approach, or if it works. Consider an urn with 5 different coloured balls. You draw 20 times each time putting the drawn ball back. I'm supposed to find the expected value of number of coloured drawn this way, but it all comes down to calculating $\mathbb{P}(X=k)$, where $k \in {1, \dots, 5}$. Let's denote by $A_k$ set of 20 element sequences with entries being exactly k of 5. I wanted to find $|A_k|$. $|A_1|=5$. I tried to do it 'inductively': $$|A_2| = \binom{5}{2} \left( 2^{20} - \binom{2}{1}|A_1|\right)$$ $$|A_3| = \binom{5}{3} \left(3^{20} - \binom{3}{2} |A_2| - \binom{3}{1} |A_1| \right)$$ $$|A_4| = \binom{5}{4} \left(4^{20} - \binom{4}{3} |A_3| - \binom{4}{2} |A_2| - \binom{4}{1} |A_1|\right)$$ and finally $$|A_5| = \binom{5}{5} \left(5^{20} - \binom{5}{4} |A_4| -\binom{5}{3} |A_3| - \binom{5}{2} |A_2| - \binom{5}{1} |A_1|\right)$$ Although this gets quite ugly if I wanted to plug in all the values directly and compute the expected value. First question - does this approach seem correct or maybe I am miscounting somehow this way? Second question: maybe there is a clearer way, or will it just be ugly?

[vital dew]

Catematician

[rich bronze]

Can you frame the question little more clearly? There are some typos which are confusing me

What is $A_k$?

[vital dew]

KD

[sick grail]

Set of sequences consisting of k colours

[weary tiger]

Yeah and I hope the formulas are self-explannatory what I was trying to do.

[sick grail]

I would go directly from expectation rather than try find probabilities like this directly

[weary tiger]

Well for expectation you need P(X=k). This is what I was calculating.

(Since you just need to divide |A_i| by 5^20)

[rapid pelican]

how do u find the rule of inference for this sentence?

If n is a real number such that
𝑛 > 2, then 𝑛2 > 4. Suppose that 𝑛2 ≤ 4, then 𝑛 ≤ 2

[lusty fern]

Is it possible to subtract powersets using complementary counting?

if the total amount of sets A in a set B is 2^10

and we want to take away 2^5 sets

would the cardinality of A just be 10-5?

[sick grail]

I meant write the expectation in terms of other expectations easier to calculate

e.g. condition on first draw, then the second etc.

Although that's not very nice

Or split the X into other r.v.s

Ok yeah that works out

[weary tiger]

What exactly do you mean by that? @sick grail

X_i being i being drawn?

[sick grail]

Yes

Indicators of that event

[weary tiger]

Hmm so that would be basically 5 P(X has been chosen)?

[sick grail]

i has been chosen

[weary tiger]

Well yeah. This approach sounds nicer, thanks.

Does the answer $5( 1 - (4/5)^{20})$ sound reasonable then?

[vital dew]

Catematician

[sick grail]

Yeah that's 4.94 which seems reasonable for 20 draws

So because it's easy to get a result for arbitrary number of colours and draws this way

That works for 2 colours 3 draws which can be calculated directly from definition quickly

[opal gorge]

hi, id just like to ask what the latex for ¬

[sick grail]

\neg? I think

[opal gorge]

$\neg$

[vital dew]

Darkness

[opal gorge]

oh thanks

[sick grail]

For future use search 'detexify'

[brave rock]

That's a good way of putting it, yes

Nice and brief

[rapid pelican]

can someone explain to me why the 2 premise do not imply the conclusion?

“No juniors left campus for the weekend” and “Some math majors are not juniors” imply the conclusion “Some math majors left campus for the weekend”

[brave rock]

The conclusion means that at least some people left campus, but neither of the premises mean that anyone has left campus. It is perfectly possible, for instance, that nobody left the campus at all, and the first premise would still be true.

[rapid pelican]

would it be possible to show it does not imply via the rules of inferences? or it would not be possible at all?

[brave rock]

No, because it may in fact imply the conclusion in certain situations.

[rapid pelican]

ah i see thank you so much

[brave rock]

What does it mean for an integer to be odd? Tell me this

Where y is any number?

That's not true

YOur additional comment is confusing.

[unique abyss]

Your edit is still incorrect

Consider y = 5

[brave rock]

An integer n is odd if there exists a number y such that n = 2y + 1. This is different to what you have said

In predicate logic: n is odd <-> (∃y∈Z)(n = 2y + 1).

Your attempt to turn the statement into predicate logic introduces y without saying what it is, making it incorrect.

So this is a first step: let's make sure we have the definition of oddness correct.

[unique abyss]

Hint: can you take Boytjie’s definition of odd number and rewrite it in the form (k-2)+(k+3)?

[silent hinge]

hello guys i was given the following:

2. A bowl contains 10 red balls and 10 black balls. Suppose you randomly select the balls from a bowl.
   a) How many balls must you select to guarantee that 4 balls of the same color have been selected?
   b) How many balls must you select to guarantee that 4 red balls have been selected?

do i need to use generalized pigeonhole principle to work this out ?

[silent hinge]

nvm i solved that shit already

i dont understand how i am going to use this in the real world

[sweet thunder]

Can someone help me with uniqueness I understand the intuition behind it but I’m lost on how to write it down or if I’m answering the question the right way

[last timber]

@sweet thunder still need help?

[sweet thunder]

@last timber yes please Im not sure what they’re asking me to state or how to show this

[last timber]

Well for a)

assume a) is true

it says that exists x such that for all y P(y) is equivalent to x = y

consider equivalency in there

assume P(y) = T

what it imposes on x = y?

[sweet thunder]

Since it’s biconditional would x=y also need to be true?

[last timber]

well yes, not even because biconditional, but because implication

so anyway

it basically says that if there is at least one y such that P(y) = T then y is forced to be the same as x

so for now we can have set of y such that P(y) = T to be {x}

it still can be the case that there is no such y that P(y) = T, but it shows uniqueness

do you agree?

[sweet thunder]

Yes I see that

[last timber]

now see othersize implication

x = y -> P(y)

we assume this implication is true

so what are the cases when it would be true?

and, more important, what is the case when implication would fail?

[sweet thunder]

Anytime p(y) is true, the implication would be true. The only time it would fail is if True implies False

[last timber]

yes

so in other words

how you would describe
"x = y -> P(y)" to be false

in the terms of True -> False?

[sweet thunder]

If x=y does not imply p(y)

[last timber]

no

we know that (x=y) implies P(y)

it is true by our assumption

so we know that case that implication is false cannot happen

case when implication fails is T->F

how would you describe x=y -> P(y) in terms of T->F?

like what is T and F here

[sweet thunder]

P(y) is always true so T->T

[last timber]

no.

why P(y) is always true?

i mean

[last timber]

.

answer the question

[last timber]

.

[sweet thunder]

Im a little lost at this part. P(y) is true and x=y is also true. Or would x=y not matter in this case since p(y) is already true?

[last timber]

why P(y) is true?

again, we are considering the implication
(x=y) -> P(y)
when it would fail?

we have shown that P(y)->(x=y) implies that if there is y such that P(y) then x = y, that is, if P is true for some element, then it is true only for that element

we now want to use implication (x=y) -> P(y) to complete our reasoning

@sweet thunder any advance here?

[sweet thunder]

I think so. Should I be rephrasing the statement to show equivalence?

[last timber]

no.

[last timber]

i mean just do this.

[last timber]

we have done this part to show uniqueness

now we want to use implication (x=y)->P(y) which is part of equivalence to show uniqueness

thus we want to work with case when this implication would be false

so describe this case.

[sweet thunder]

Y=x is true but p(y) is false.

[last timber]

yes

well, ok i should've mentioned that we considered only one of two lines here, i will speak about second one further

but for now

[last timber]

consider now that since we assume implication to be true

it cannot be that case

so it cannot be that y=x and p(y)=false

agree?

[sweet thunder]

Yes agree

[last timber]

so this now show existence

since we can just take y=x and we are forced to have p(y) = T

so x=y->P(y) gives that solution exists

P(y)->x=y gives that if solution exists it is unique

connecting them together we get solution exists and it is unique

@sweet thunder understand this?

[sweet thunder]

Yes I understand that

[last timber]

now a little step back
we considered basically T<->T
it could be the case that F<->F

ok so see that for F<->F we should have
P(y) is false for all y and x!=y

but take y = x what would you get?

@sweet thunder

[sweet thunder]

Is that also true? Also, I don’t recall seeing “!” In the text book except for in the question

[last timber]

@sweet thunder i mean your whole statement requires equivalence
P(y) <-> x=y

when equivalence is true?

[sweet thunder]

Oh. If I take x=y then I get P(y)

[last timber]

no

[last timber]

this is another case when equivalence is true

first case we considered and derived existence and uniqueness from it

second case is P(y) = F and (x=y)=F

but take y to be x, what then you get?

like what would be truth values for P(y) and x=y if you take y to be x?

[sweet thunder]

If y ~=x then y does not have the unique property. So if y is x then you’d have T<->T right?

[last timber]

what?

how is this related to my question?

[last timber]

answer this question

[sweet thunder]

True and true

[last timber]

why true and true?

we have considered the case T<->T. We have derived that uniqueness and existence follows from it.

now we consider another case when equivalence is true

P(y)=F<->(x=y)=F

what will happen with this if we take x to be y?

[sweet thunder]

Then y=y would have to be true wouldn’t it?

[last timber]

yes

and you get F<->T

which is nonsense

[sweet thunder]

Ohhhh

[last timber]

thus equivalence could be true only in case T<->T, other case is impossible

and T<->T shows existence and uniqueness

now you have to formulate all of these nicely and understand it

and other two statements are to be done by you

[sweet thunder]

Thank you so much 😊

[rustic adder]

Well, got this question in exam and 1 min to solve it😅. Anyone could try it out?

[glossy dirge]

Is this the solution to the problem?

for at least 1 b and at most 2 a

or is this the solution

[north girder]

How do I do (c) ?

Here’s (a) and (b)

Anyone??

[rustic adder]

U can find the retardation by finding the slope of the line from 160 to 200. Thats will be (y2-y1)/(x2-x1). i.e. (0-V)/(200-160).

I believe this should do but it has been a while I did stuff with kinematics .😅

[hardy jackal]

Find all functions 𝑓(𝑥) = y from 𝑋 = {𝑎,𝑏} to 𝑌 = {𝑢,𝑣} Express the answer as a set with lists of valid functions

Solved it

[craggy knoll]

It’s a beautiful summer day, and Jake is at the beach, constructing his unparalleled kingdom of sandcastles. Armed with a bucket and a shovel, he built n sandcastles (n ≥ 2), which are interconnected
by bidirectional paved roads. At most one road connects any two sandcastles. He consciously chose to
build his kingdom such that not every sandcastle can be reached from every other sandcastle. Prove
that there exists a pair of sandcastles such that the total number of roads leading out of the pair is
less than n − 1.

[coral parcel]

The story about Jack and his sandcastles really drives home how relevant graph theory is for real-world situations, doesn't it?

[craggy knoll]

yup, any ideas on the proof? im thinking smth with spanning trees

[coral parcel]

It's not clear to me how to interpret the story in a way that even yields a true statement.

"not every sandcastle can be reached from every other sandcastle" just seems to mean the graph is not complete.

[craggy knoll]

yes it is disconnected

[coral parcel]

Ah, that could make sense.

So choose your two vertices in different connected components.

If the sum of their degrees is at least n-1, they must either be neighbors or share a common neighbor. Contradiction.

[craggy knoll]

a pair means they are connected

so the vertices have to be in the same connected component

[coral parcel]

Huh, that would be a strange condition. Is that a special-case meaning of "pair" that has been defined in your course?

[craggy knoll]

would this proof work?

[dense glade]

how do you read : in set builder notation

{x | ∃k ∈ {1, 2, . . . , n} : x ∈ Ak}

[fading token]

@dense glade For all of x there exists a k such that x is an element of Ak?

I'm not sure lol

BUt maybe that makes sense

[dense glade]

yeah its def of a union

so it does

[sly citrus]

can anyone tell if what I did is correct?

[waxen sigil]

(AXA')' + C
= 0' + C (AA' is always 0)
= 1 + C (0' = 1)
= 1 (1 + Y = 1)

is this correct?

AB denotes A and B and A' denotes A complement

[rustic adder]

Yes
(AA’)’ + C
= A’ + A + C
= 1 + C
= 1

[rustic adder]

Anyone got a clue about this?

[tidal yoke]

"If the file is locked or the system is in executive clearance mode, the user cannot make
changes in the data." can someone tell me the negation of this statement?

[elder berry]

The statement you have is just

[vital dew]

peaceGiant

[elder berry]

how would you negate this statement? Resolved

[viscid rivet]

I have this for now but am not sure what to do ( re uploaded because I added stuff)

Okey I tried changing it up a bit but this is probably all wrong lmao

[coral parcel]

The trick here is that you don't even need to use the induction hypothesis.

If X is ¬A, then it cannot be ((bot)) because the first symbol of ¬A is ¬, whereas the first symbol of ((bot)) is (.

Essentially, this way you're just using the structural induction principle as a justification for doing a case analysis on the topmost level of the formula.

[viscid rivet]

oh that makes sense

so no need to compare it to A and use the I.H. at all in this case

[viscid rivet]

however, if I wanted to use the I.H. can I do it in the way I did here or is it all wrong?

[coral parcel]

I don't think there's a way to make use of the induction hypothesis here that won't look like an obvious detour.

I now see there's a bit confusion between ((bot)) and ((¬bot)) in your writeup; I assume those are just typos?

If you fix the typos you can say something that ends with

since A cannot be ((¬bot)), X (which is ¬A) cannot be ((¬bot)) either.
but it's a bit pointless, because the conclusion that ¬A is not ((¬bot)) doesn't depend on what A is or is not.

[viscid rivet]

ahh okey yea that kinda makes sense its just confusing but I guess its really confusing because of what u said, that it is kinda pointless to try to use the I.H.

So according to what u said it should be something like this

[coral parcel]

Yeah.

[viscid rivet]

Thank you :) I hate the book that has these exercises

it doesn't have any answers -.- Can't even check if what am trying to do makes sense lol

[median flume]

is discrete considered easy for advanced math students? Just curious

[little prism]

well depends on which topic and how advanced the student is

but I would say no. there are very hard discrete math topics

[median flume]

oh alright, so it has a very high skill ceiling

[rough coral]

Can somebody explain what this questions is asking?

[hard citrus]

Basically, you're given x and y and to show that x<|y you need to find some integer k for which it holds that 2x+5y=7k. Taking 1<|8 for example, x=1, y=8 and 2*(1)+5*(8)=7k or k=6. So you've shown that 1<|8 by finding that k=6.

[silent tapir]

Am I allowed to ask for homework help here?

I can’t figure out this problem

[weary tiger]

What have you tried?

@silent tapir

[silent tapir]

I haven't really gotten anywhere. I tried the proof starting from both sides but I can't figure out how they're related so I haven't been able to get anywhere. I've spent the past like hour just staring at the problem trying to think of how to start.

I've erased most of the stuff I've written but I remember trying g o f o g = g but I don't know how that would be useful

The homework is due in 5 min so I turned it in without that problem but I still want to understand it

[coral parcel]

The straightforward direction is "only if". There you know there is a g such that f(g(b)) for every b in B. You're then asked to prove that every b in B is f(a) for some a in A. But you can always find such an a, namely g(b)!

[grand totem]

The forward direction (that is, right invertible implies surjective) is just a matter of definition chasing. Hint: If you're given such a g and you take any b in B and look for some a in A such that f(a) = b. Then certainly g(b) would be a natural choice to check

Guess I wasn't fast enough lol

[coral parcel]

"If" is less straightforward, primarily because of the pedants who are going to show up talking about how it needs the axiom of choice. :-)

[grand totem]

The other direction requires the axiom of choice (it's even equivalent to AC), so it would be good to know what definition of AC your course uses

[coral parcel]

Apologies 😂

But intuitively it's simple enough: The assumption that f is surjective says exactly that there's always a suitable a that you can choose to be the value of g(b).

[grand totem]

I don't mind discrete math courses not mentioning AC where it's technically needed, but giving such a problem as HW without a hint that such constructions are indeed allowed seems like bad pedagogy

[coral parcel]

The main hurdle in the exercise is probably to get past the misconception many students have where they think a "function" needs to be defined by something like an arithmetic expression. However, just giving a table of which outputs correspond to each input will make a perfectly fine function. We do need some handwaving to deal with the possibility that the table might need infinitely many rows, but that handwaving is essentially what the axiom of choice does.

[mint bane]

how is zorn equivalent to AoC

im blue again

[coral parcel]

Which direction of the equivalence do you have trouble with?

[mint bane]

well im having trouble understanding zorn in general

im reading thee gowers blog on it tho

If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.

this kinda makes sense? but i can't see how it's the same as axiom of choice

well i guess if each chain is a subset, choice function is picking the maximum of each chain?

also is this the right channel

[coral parcel]

It's right on the boundary between #proofs-and-logic and #foundations, but this channel has a large known overlap.

Zorn and AC are not obviously the same statement -- neither of the implications Zorn => AC nor AC => Zorn is immediate.

Zorn => AC is a quite straightforward application of Zorn's lemma (take the poset to consist of all partial choice functions ordered by set inclusion; a maximal element will then be a full choice function).

AC => Zorn is more involved.

IIRC you need transfinite induction, and something like Hartogs numbers to induct over.

[mint bane]

will assume this was badness

[odd phoenix]

can someone help me this

[tidal yoke]

help part C

[coral parcel]

It the two of you had bothered to write something about your understanding of the tasks and where you get stuck, rather than just screenshotting a homework exercise an nothing more, you would have a lot better chance of getting useful help.

[remote crane]

Let $f: A \to B$. Let $B_n$ be a sequence of sets in B.
I want to show that: $f^{-1}(\cup_{n=1}^{\infty}B_n) = \cup_{n=1}^{\infty}f^{-1}(B_n)$

Does this work one way: Suppose x is in the left side. Then, there is some n where $x\in f^{-1}(B_n)$, so that means x is in the right side as well?

is that valid or too many holes

[vital dew]

Mirinim

Mirinim

[little prism]

skips a bit much imo

if x is in that set, what is f(x) ?

[remote crane]

if x is in the set, then isn't it just a preimage of some B_n under f?

Idk how to close the gap in logic

[little prism]

lets set $C=\bigcup_{n=1}^\infty B_n$. let $x\in f^{-1}(C)$. what does that mean. what do we know about $f(x)$

[vital dew]

Denascite

[remote crane]

f(x) is in C, so f(x) in at least one of the B_n

idk what else is there

am i missing something rly obvious

[little prism]

well that's it. but you didn't really say that intermediate step. first f(x) is in the union, then it's in one of the B_n. and then x is in the preimage of that B_n

[remote crane]

oh I see thank you

[little prism]

and then x is in the union of the preimages

[remote crane]

got it, I just can't skip over steps

thanks

[ebon quest]

Does anyone understand Big O, omega, and theta notation? Could you help explain something to me? (@ or dm me if you do)

[odd phoenix]

=]\

[zealous elbow]

how do i determine whether a public key is valid for RSA encryption

[coral parcel]

If you mean, check that a claimed modulus is actually the product of two large primes, there's no known efficient method to do that. (Other than actually knowing a matching private key).

[zealous elbow]

i figured it out just had to check if e was valid in (n,e)

[coral parcel]

What does that mean? With knowing d, how would you express the condition for e to be "valid"?

[zealous elbow]

since e has to be between 1 < e < phi(n) and co prime to n and phi(n)

[coral parcel]

But you don't know phi(n) -- if you did, you could compute a corresponding d, and thus get the private key.

[zealous elbow]

oh um i had p and q as well so i could find phi(n)

[coral parcel]

Ah, so you don't just have a public key.

[zealous elbow]

yeah haha i probably shouldve mentioned that

[zealous elbow]

also the private key is just the inverse of e in Zn right

[coral parcel]

The inverse of e modulo phi(n), not modulo n.

[zealous elbow]

oh yeah thats what i meant forgot the phi

thanks

[sand halo]

hey im trying to draw a biconditional circuit diagram

so i figured i'll used p -> q ^ q -> p

and from there use the equivalence of p -> q which is ~p v q

but how do i draw the inverse of that

like q -> p

[coral parcel]

Do you mean a circuit that computes 1 if its two inputs are equal and 0 otherwise?