discrete-math

[ivory badge]

Yeah so why would putting a zero in front make it different

[quiet eagle]

ooh, for negative numbers z_(n-1) would be 0 and z_n is 1 then? The other numbers don't change

[ivory badge]

make sure they're the same number

is 1010 the same as 10010 when I go up a digit count

[quiet eagle]

Yes it is

[ivory badge]

what number should 1010 be

[quiet eagle]

10

[ivory badge]

considering it starts with a 1, didn't you say it should also be negative

what's it negative of

[quiet eagle]

ahhh

[quiet eagle]

Those are equal to -2

[ivory badge]

so if I add 2, it'll go to zero?

show me that this works, then

[quiet eagle]

To prove this, can I assume that the given number is representable with n digits?

[ivory badge]

it's representable with n-1 even

[ivory badge]

add 2 to 1010 though

[quiet eagle]

I ment, generally

[ivory badge]

so do I

[quiet eagle]

what

what if n=1, then how can I represent any number with 1 digit also with 0 digits?

[ivory badge]

the problem literally says n-1 going to n

[quiet eagle]

oh mb, I thought it was n going to n+1

[ivory badge]

please check this though

[quiet eagle]

uhm, 1111?

[ivory badge]

what is 2 in this notation?

and what is 0

I would think it should be 1100?

[quiet eagle]

just negating the bits of 1010 gives us 0101

[ivory badge]

neither of those are zero though

[quiet eagle]

yea

[ivory badge]

that looks like 5

[quiet eagle]

that is weird for me

[quiet eagle]

I don't know why this happens rn

[ivory badge]

because I think you're thinking about it wrong

1010 looks like -5 yes?

10010 looks like -13

I do not think your method is correct homie

[quiet eagle]

I think I confused 2 number representations with each other and mixed them

[ivory badge]

I do not know where you did

because idk where you'd get 1010 as -2, much less adding 2 giving us 1111

[quiet eagle]

What is 1010 in your opinion then?

[ivory badge]

I'd say it's -6

5 is 0101, and 1010+0101 = 1111. Add the last 1 and go back to 0000

[quiet eagle]

I could allow 1010 to be "-2" and "10" regarding which number representation was used. But how did you get -5 or -6 for it?

[ivory badge]

how does addition work

[quiet eagle]

by adding the digits

[ivory badge]

how could this possibly be -2?

1010 + 0010 should be 1100?

[quiet eagle]

in sign-magnitude representation, where the first digit tells us the digit of the number

[ivory badge]

add 1010 and the representation for 2 for me rq

all the steps

[quiet eagle]

the representation for 2 being 0010?

1010 + 0010 = 1110 (only one step)

[ivory badge]

that's not zero right?

[quiet eagle]

yes

[ivory badge]

so it's not -2

[quiet eagle]

yes

then I'll create -2 by calculating the two's complement of 2

[ivory badge]

but 1010 + 0110 (6) = 0, so it's -6

[quiet eagle]

oh ok

[ivory badge]

that's why it's two's complement

[quiet eagle]

what is the reason for what?

[ivory badge]

because that's where you get negatives

and signed 32 bit integers

[vital dew]

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

[quiet eagle]

in my textbook there is also this

[ivory badge]

that's not 2's complement though

the og question is two's complement, not whatever that bad sign bit one is

[quiet eagle]

haha, you are judgy

okay having that cleared up, I'll start the proof

[fossil mural]

what kind of "number" is -0

[quiet eagle]

yeah, that's a waste of memory

@ivory badge does (110) = (00000110) ?

[ivory badge]

well, if you consider them as positive yeah

however, 110 looks like -010

[quiet eagle]

Why does bitflipping change them to different numbers though?!

[ivory badge]

why wouldn't it?

[quiet eagle]

because they are equal

[ivory badge]

they're equal in terms of being 6

but if you consider the front being a negative signifier

then no

[quiet eagle]

I won't do this anymore. I have just read that this number representation is bad

but (001) is not equal to (11111001) anymore

[ivory badge]

well, 001 is -111

-11111001 is 00000111

[quiet eagle]

ahhh

You cant do this

does binary have minus signs?

[ivory badge]

no, but it's a negation

add em together and you get 0

[quiet eagle]

okay

[ivory badge]

start with "positive" numbers

they already have a 0 in front

[quiet eagle]

oh they are equal. I am sorry for overreacting, they just looked very different

[ivory badge]

so 0z_n-2 z_n-3....z_0

puttiing a 0 in front will keep it the same

[quiet eagle]

Is that still the case for complement number representation?

[ivory badge]

yes

because it's positive

if it's 1....z_0, you need to do something else

[quiet eagle]

okk

[ivory badge]

what is it you do?

[quiet eagle]

Are we talking about the number before/ or after it was two's complemented?

[quiet eagle]

let it be 10...z_o

Also if I want to N's complement any b-adic number, I have to convert the number to be N+1-adic. Is that correct?

[ivory badge]

in the representation

[ivory badge]

no

110 -> 1010 in that setup, but 110 is -010, 1010 is -0110, so something changed

-2 and -6, resp.

[quiet eagle]

let it be 11...z_o then

[ivory badge]

now prove that works

[vital dew]

Sciencenjoyer

[quiet eagle]

@ivory badge

got it

[ivory badge]

There’s an extra hat in there but sure

Showing they represent the same numbers is also important

Idk C_2 is

[quiet eagle]

oops

[quiet eagle]

that's the two's complement

[quiet eagle]

That's too hard

[ivory badge]

That’s the problem it’s asking though

[ivory badge]

C_2(C_2(x)) = x for any x though?

[quiet eagle]

yes

[ivory badge]

-x = C(x) + 1

[wraith patio]

is there a way of properly testing if my fsa is correct other than just test cases and inspection

similar position to yesterday

my implementation works with the test cases

just isnt the same as what my given answer is

im not really sure how to properly check if all my fsa's are 100% correct when i dont have a standardised way of checking for sure considering theres muiltiple fsa's that can accept the same language

the only thing i can think of is just to create a bunch of test cases that i know should accept/reject and try them out in jflap but that could be time costly in an exam

[fossil mural]

(what's the given answer?)

[haughty garden]

You can think of your automaton as matching prefixes of 001; it’s similar to the construction of the automaton used for KMP. Yours is just non-deterministic (depending on whether you view omitting transitions as non-deterministic), whereas the sample answer is the standard string matching automaton

they should accept the same language though, so yours is equally as correct

[fossil mural]

...the given answer also omits a transition (0 from q2)

[haughty garden]

That is also true

[fossil mural]

the only difference between their answer and what was given is that in the given answer q0 and q3 do essentially the same thing, and their answer makes them the same state

[haughty garden]

It’s effectively the same

[quiet eagle]

I have -x = C(x) + 1 - b^n for every b-adic number x with n digits

[ivory badge]

Can b^n be represented in that system

Also it’s not b-adic, it’s base b

x + C(x) = b^n - 1

But b^n has a 1 in the n+1th digit so….

It’s 0

@quiet eagle

[quiet eagle]

Sorry, I misunderstood. That is the definition of the b-complement. My equation was based on C being the b-1-complement

[ivory badge]

huh

[quiet eagle]

What is it?

[ivory badge]

Idk what you mean there but aight

It’s not being the wrong b

It’s the right complement I think

b^n is just zero

[quiet eagle]

What even is the base of the given number in my task?

[ivory badge]

2?

[quiet eagle]

It could be 3 too or anything else

[ivory badge]

The problem was two’s complement

So 2

[quiet eagle]

You could apply the two's complement on a number with base 15 too

could you?

You would need to carry on to the subtraction to the next column

Is that a thing?

[fringe turret]

There is line in the book I am reading

An element of a set can not be subset of itself.

What does it mean actually?

Also does $A = { {1} }$ invalidate this?

[vital dew]

ĐARK々MÁTTER

[fringe turret]

Because $x = {1}$, such that $x \in A$ and $x \subset x$

[vital dew]

ĐARK々MÁTTER

[fossil mural]

they might have been trying to say that an element of a set can't be a proper subset of itself? since no set is a proper subset of itself

but yeah i'm not really sure what that means, the most obvious reading is about as false as it could be (every element of a set is a subset of itself, at least if you assume that elements of sets are sets)

[fringe turret]

I see

I got the answer here but struggling to understand, https://math.stackexchange.com/questions/3241082/in-an-element-of-a-set-can-never-be-a-subset-of-itself-what-does-itself-sta
I looks difficult because of english 😅 would you help me here?

[little prism]

basically, author fucked up

[weary tiger]

can someone help me with this ?

[true pelican]

What is your problem

For example S becomes 11101, it should be obvious no?

[elfin adder]

anyone know how to show that an n-cube is non planar for n >= 4 using kuratowskis thrm? I can't seem to find K5 or K3,3 from the 4-cube..

[weary tiger]

Ah I understand, I am just painfully slow and dumb 😄

[quiet eagle]

@ivory badge You know how can calculate e.g. binary numbers with a sum? For example: (011)_2 = 0x2^2 + 1x2^1 + 1*2^0 = 3

[ivory badge]

Yes

[quiet eagle]

But how does this work with negative numbers like (101)_2 ?

I wanted to use this sum for that proof but idk

[ivory badge]

You make the most significant bit negative

-2^2 + 0 + 1

[quiet eagle]

but every z_i itself is still positive. So where does that minus sign come from?

[ivory badge]

You add it in

On the biggest bit

That’s it

[quiet eagle]

That can be proven right?

[ivory badge]

That’s a definition on one hand, but yes

[quiet eagle]

Why didn't my book give me this >:(

Do I need this sum for my task though?

[ivory badge]

Because it should be fairly apparent?

[ivory badge]

No

[quiet eagle]

How is it fairly apparent?

[ivory badge]

Though using it to verify can help

[ivory badge]

If it has a 1 in front it’s negative

Work from what adds to what

To get 0

[quiet eagle]

I still don't understand why my first proof was not correct

[ivory badge]

Because you just moved the front digit forward

Or do you mean the one where C(C(x))=x was included, but that’s not useful

[quiet eagle]

yes that one. I used it to explain why the first digit of a negative number is 1

didactic purposes

[ivory badge]

It didn’t

[quiet eagle]

If x = 1, then C(x) = 0, then C(C(x)) = 1 again

That was my idea

[ivory badge]

But that’s just saying x=1

It doesn’t say anything

True doesn’t mean useful

[quiet eagle]

I used that fact that C(z) being negative was given to show that z_n-1 = 0

I could have just said that z is positve so z_n-1 =0

[ivory badge]

Yes

[quiet eagle]

That aside, my conclusion was that if I add an 1 to a negative binary number it doesn't change

[ivory badge]

X+1 definitely changes

Putting a 1 in front works though

[quiet eagle]

that's what I ment ._.

[ivory badge]

Instead, just use -x = C(x)+1

gg that tells you putting a 1 in front is still the inverse

[quiet eagle]

well you don't add one but put a 1 in the front

[quiet eagle]

So how is this useful?

[ivory badge]

Put a zero in front of a positive one

Show that keeps the same value

-x = C(x) + 1, so you flip that new zero to 1

[quiet eagle]

easily done by using the sum notation

[ivory badge]

Done

[ivory badge]

This is exactly the original -x but with an additional 1 in front

gg

[quiet eagle]

oh C(x) is equal to -x

[quiet eagle]

What stops us from substituting it in this equation?

[ivory badge]

No, it’s C(x) + 1

You add 1

Not in front, you add a one to the complement

C(x) + x = 2^n - 1

[quiet eagle]

That must be the one's complement here

[ivory badge]

the 2’s complement

[quiet eagle]

fake information

[ivory badge]

well then you can simply take the L

[quiet eagle]

lmao

[ivory badge]

Idk bro just look up two’s complement

[quiet eagle]

ahh I mixed it up again

[ivory badge]

I do not understand what you can mix it up with ngl

[quiet eagle]

wait no

one sec

Lemma 1.12 For any n-digit, b-adic number z, the following statements hold: \ \

1. $z+C_{b-1}(z)=b^n-1=(b-1, \ldots, b-1)_b$, \
2. $C_{b-1}\left(C_{b-1}(z)\right)=z$.\ \
   If $z \neq 0$, we also have\ \
3. $z+C_b(z)=b^n$,\
4. $C_b\left(C_b(z)\right)=z$.

[vital dew]

Sciencenjoyer

[quiet eagle]

@ivory badge this

1 and 3

[ivory badge]

How do you define C_{b-1} and C_b on the same z?

[quiet eagle]

I got the defintions

one min

[ivory badge]

Idk why you bother so much with the “b-adic” (just base b numbers) complement, I don’t think theres much warrant ngl

If it’s defined like that then just -z = C_1(z) + 1

[quiet eagle]

I'm just using the same words my textbook does. I don't know the difference between "b-adic" and "base b". What do you mean by "why bother so much" if this decides with equation I can use?

[quiet eagle]

-z is equal to C_2(z) right, correct, true?

[ivory badge]

According to 3, however it’s defined

[quiet eagle]

what is?

[ivory badge]

C_2 is

[quiet eagle]

I never said it wasn't

[fathom crag]

hi does anyone have any good intro to discrete math online courses im currently doing cs and am taking it next semester and wanting to get ahead

so i can be sweaty

ping me pls and ty

[thorn birch]

I know Codecademy has one, and there's an MIT course available for free, and there's the Aho/Ullman "Foundations of Computer Science" book online for free, which is an intro to discrete math for programmers.

I haven't gone through these yet for myself, but I've recently been looking for material as well.

[fringe turret]

If $A \times B$ is my universal set for defining a relation between domain and co-domain. And lets say set $R$ is relation set such that $R: A \to B$ and we know that $R \subset A \times B$ for sure, can $R = \phi$ (empty set)?

[vital dew]

ĐARK々MÁTTER

[fringe turret]

Also if yes, then there would be no arrow from domain to co-domain. So can be say having no relation is also a relation?

[brave rock]

LaTeX protip: \emptyset is the empty set symbol, not lowercase phi.

Indeed, the empty set is a relation. It is even a function, in certain circumstances.

[robust python]

I think yes, relations can be empty. It can't be a function if A is non-empty

[fathom crag]

These sound great, thanks very much for the recommendations

I'll check some out and report back if you need it

[fringe turret]

Like in computer science we say when function return type isvoid it returns nothing?

[fringe turret]

So a function must return something?

So a function is a special type of relation where for element of set has only one image in codomain. To have image, domain must have some elements and so does codomain. That means, both A and B cannot be null set.

[fossil mural]

void is nothing to do with the empty set

void is a set with one element
a function that returns void "returns nothing" because being given an element of a set with 1 element gives you no information, since there's exactly one way to do that

[fringe turret]

Mathmetically it would look like ${ \emptyset }$, right?

[vital dew]

ĐARK々MÁTTER

[fossil mural]

the type that's actually the empty set isn't in most languages - it's the type of a function that can never return, meaning it always loops forever or crashes or throws an exception or something like that

[fossil mural]

yeah that's one possibility
it doesn't really matter what the single element is as long as there's only one of it

{5} would work equally well as a void type

[fringe turret]

I see, so if for any value we input to function, and it does not return any different input then we can say it is not giving any information hence the return type of function in computer science void which also means ~ no information.

[fossil mural]

i'd say it's more specifically to do with the codomain having one element

if the function always returns the same thing then you still get one piece of information which is which thing it always returns

f(x) = 2 and f(x) = 3 are two distinct functions from numbers to numbers

but for a set with one element there is always exactly one function to that set, if you ignore things like side effects and the possibility that the function never returns
so having the function really does give you no information at all

[fringe turret]

Btw void (programatically) means "the return type of a function that returns normally, but does not provide a result value to its caller". So technically void in context of relation and programming doesnt look same to me

[fossil mural]

no void in this context does also mean it returns normally

"not returning a value" is actually just returning a value with no information in it

[fringe turret]

side effects ? meaning

[fossil mural]

stuff like printing to stdout

doesn't happen in maths but it exists in programming (in most languages)

[fringe turret]

Yeah

[fossil mural]

also nondeterminism
not really a "side effect" but it's in the same class of things that functions in programming languages do and mathematical functions don't

[fringe turret]

it makes sense now. Like f(x) = 2, we can see of each value of x {(1, 2), (2, 2), (3, 2) ... }, no such actual information is returned, just a literal value which is pre determined.

So if we ignore it as you said, then again repeating your line "function never returns so having the function really does give you no information at all"

[fossil mural]

uh...? that's not something i ever said

there is at least one input to f(x) = 2 for which it returns (take x = 1), so it doesn't never return

[fringe turret]

Ohk let me give you a python function

def f(x):
  return 2

Doesn't it return 2?

[fossil mural]

yes

you said that it never returns, which is incorrect

[fringe turret]

What I meant was we can ignore this since it is not adding any usable information at all.

[fossil mural]

well that's nearly true, but like,

def g(x):
    return 3``` this is a different function, right?

[fringe turret]

Yes it is

[fossil mural]

so there is some amount of information

if neither of these functions contained any information at all then they would be the same

[fringe turret]

I see

Actually I got your point, I also have problem with expressing myself in english 😅

[fringe turret]

btw these are constant functions, they are valid functions because as you said they have some information, which is line parallel to x axis crossing y axis at 3

[fossil mural]

...well a function doesn't need to contain any information to be "valid"

but yes they do contain information

[brave rock]

No

I mean when A is the empty set

[robust python]

Yes, that's true if you are considering a function A to B where A is non-empty

http://en.wikipedia.org/wiki/Empty_function

Otherwise it's a so called "empty function"

[fathom crag]

interesting

[rigid rover]

not a butter

[glass spade]

stuck

[short geode]

oof the start of group theory is really definition dense

[meager prawn]

Yeah but it's fine. You'll get familiar with them pretty quickly

[honest holly]

thats how i felt when i learned chapter 2 of rudin pma

instead of introducing the definitions as needed, he introduces ALL of them at the SAME time!!!

i could not for the life of me follow along at all

[dusky pagoda]

Why is this sentence true?
"The number of such choices with min(Y)>max(X) is equal to: "

[limpid lava]

As mentionned in the line of solution one the number of choices is k+aCk * n+k+aCn you can use the factorial expression of both terms and simplify to reach n+k+aCn+k

[dusky pagoda]

i didn't understand

[elder berry]

if min(Y) > max(X), then min(Y) is greater than all the elements of X.
so the goal is to count all ways to construct two sets X and Y with k and n elements respectively, so that all of the values in X are smaller than all the values in Y.
think of this as making one big set of n+k elements; whenever you choose a set with n+k elements, there is only one way to form the sets X and Y, and that way is by selecting the k smallest elements and allocating them to X, while the rest go to Y.
so the problem now becomes choosing an n+k element set, which is given by that formula

[tender karma]

I don't think this is true. If P=NP, only P-complete problems will be NP-complete. Some P problems could be unable simulate all problems in P and NP.

[fossil mural]

if P=NP, then for any problem in P (or in fact any problem at all), you can reduce a problem in NP to it by just solving the problem (since it's in P), and then just find an instance of the problem which gives the answer that you know is correct

[true pelican]

Any problem in P is P-complete

[true pelican]

In response to this btw

[fossil mural]

since we're dealing with decision problems, there are only two possible answers, so we can just hardcode in the algorithm an answer for "yes" and an answer for "no"

[tender karma]

https://en.wikipedia.org/wiki/P-complete#Problems_not_known_to_be_P-complete Wikipedia seems to disagree.

[fossil mural]

that's about a kind of P-completeness that's irrelevant here

we're asking about problems in P that are complete under polynomial-time many-one reductions, because those are the kind of reduction that matters in the definition of NP-complete

in other words, problems in P that any other problem in P can be reduced to in polynomial time

since this turns out to be a rather boring complexity class, the wikipedia article about "P-complete" instead describes problems complete under reductions that probably don't include all of P, like NC or L

but NP-complete still means polynomial-time reductions even if P = NP

any problem in P is P-complete under polynomial time reductions
the wikipedia article even says that

Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions.

[nimble condor]

how do you do proofs with 1-1 and onto functions?

can someone please explain it to me bc i really don't understand any of it

i've read through the chapter in the textbook that covers it and idon't understand it either

[ivory badge]

1-1 = injective means f(x)=f(y) -> x=y

[nimble condor]

Yeah I understand the concepts behind the proofs but I don’t know how to do the proofs themselves

I just can’t figure out how to logically structure the proofs

[ivory badge]

Well, that’s not something you can say “this is how you do it”

The good point of injective is you can bring equality outside f

And the good point of surjective is you know you hit everything

[nimble condor]

what do i need to do? i've proven that $(g\cdot f)^{-1}=f^{-1}\cdot g^{-1}$
is that really it?

[vital dew]

nd

[ivory badge]

That’s all it asks?

So yeah

[stray reef]

\circ btw

[dense fjord]

hey im new here so i just want some help from you guys. my professor gave us an assignment on topic 'mind blowing math' so i was wondering about the concepts i can use for the report, presentation. can i use theories like fibonacci for that topic? im still in 1st year so im quite new to reports. will be a great help if u can give few ideas

[short geode]

what is the group theoretic way of thinking about this question?

so the answer is that from each coloring one can achieve 24 distinct colorings by means of rotations (rotation of a cube is of order 24) and then 6!/24 = 30 distinct ways.

but what promises us that the symmetries will form a partition of all the colorings? Can I think of the symmetries as a normal subgroup of all the possible colorings somehow?

and how is this related to commutants? (this question showed up in a commutant sub-chapter)

[obtuse lance]

I'd guess it's promised by burnside's lemma but I don't know the proof of that by heart

[short geode]

na that's way ahead of the material in the book

we're just defining what is a quotient group and showing some basic properties of the commutants

[short geode]

it will be helpful to think of the partitions of the 32 teams into the 4 groups that face each other before the semi-finals

[short geode]

mmm I can't tell for sure you might be double counting your probabilities. If you double check by counting how many ways you can organize the teams so you get the desired result and divide by the total amount you should get the same answer and then you know if it's true or not

[brave rock]

The symmetries describe a partition of the colourings, via the group action on the colourings. The parts of this partition are called orbits.

If you haven't seen group actions, then this exercise is just here to make you appreciate how hard this kind of calculation is before they introduce the high-powered machinery of Burnside's lemma

[short geode]

Understood, so burnside will give the theory of the orbits?

[brave rock]

Burnside will allow you to count the number of orbits in a relatively easy way

Hence one of its other names, "the orbit-counting lemma"

Btw some people even refer to it as "the lemma that is not Burnside's"

[weary tiger]

Hey I don't know how to prove the following :

On a G chart simple of order 2n,in which the degree of each edge is even,there is for each vertex another vertex connected to an even number of edges in common.

Thanks for help

[stray reef]

did you translate this from french

[meager prawn]

syntax feels similar, but no one would write a CS property like this
I sure hope not

[short geode]

Many thanks

[quiet tendon]

what is the subject called where u get questions about how many possiblites are there if and then they give a situation

[meager prawn]

combinatorics ?

[quiet tendon]

can u also explain the difference between a simple event and a sample point are they the same?

[honest holly]

what is the context of this?

this just looks like nonsense to me

[quiet tendon]

uhh

[honest holly]

if this is probability, I can tell you that this is nonsense

[quiet tendon]

I think it's more statistics I guess

[honest holly]

yeah, this is nonsense

[quiet tendon]

ah okay so it's like irrelevant

[honest holly]

throw away the book!

[quiet tendon]

but it's bain and engelhardt

oh wait no

[honest holly]

i have no idea who that is

[quiet tendon]

this ithe otehr one

wackerly

[quiet tendon]

this one

[honest holly]

i also have no idea who those people are

[quiet tendon]

which book do u use?

[honest holly]

oh wait I do know now'

[quiet tendon]

I thought this was a common one

[honest holly]

it's that book the math sorcerer always talks about 😂

[quiet tendon]

wait I know math sorcerer the youtuber right

[quiet tendon]

is he good?

[honest holly]

no

[quiet tendon]

oh

[quiet tendon]

which youtubers do u usually watch?

[honest holly]

none

[quiet tendon]

but u know the math sorcerer

[honest holly]

i used to watch his videos

[quiet tendon]

but do u recommend it?

[honest holly]

don't watch anymore, I unsubcribed and the algorithm stopped pushing him to me as well

his videos are just entertainment, not sure what there is to recommend or not recommend

if you mean should you listen to his book recommendations, no you shouldn't

[quiet tendon]

do u also watch video which are like good educational purposes but not for entertainment

[honest holly]

i watch some talks if Im interested in them

[honest holly]

i don't really recommend any stats book

[quiet tendon]

how about good informative talks then?

[honest holly]

for probability, grimmett and stirzaker, but it's quite dense

at the more advanced level, durrett is standard and also pretty good imo

[quiet tendon]

what do u count as advanced? do u mean after knowing graph theory and doing proofs?

[meager prawn]

Simple events would be when doing probabilities rigorously

You define a probability space (Omega, F, P), where Omega is the set of simple events

[quiet tendon]

ahhhh and omega itself also has several sample points

[meager prawn]

no

sample points don't exist

sample points are related to the law of large numbers

they're not your probability space

sample points aren't a part of rigorous probability theory until much later (I haven't seen it, but I've only seen the most basic stuff)

[fading sun]

what does it mean by simple variable because like how is ¬s a sub formula

this is to do with tseytin transformation

[fossil mural]

i guess p, q, r, s, are the variables

¬s is a subformula because it's here (and it's a formula)

and it's not a variable because it has a ¬

[fading sun]

so a^b V c, c wouldnt be considered the sub formula?

[fossil mural]

c would be a subformula of that

but it's also a variable, so it wouldn't appear in this list because this list is explicitly of things that aren't variables

[fading sun]

ah k thanks

[weary tiger]

oh!

[honest holly]

i meant measure theory i guess

[honest holly]

i think what's confusing

is that simple event should just literally mean "outcome of the experiment"

i also have no idea what you mean by sample point

[honest holly]

it depends what you are interested in...

if you just go on youtube and look up the topic you are interested in, you can probably find a talk

IAS, simons institute, etc

I watch stats talks

[meager prawn]

at the end of the day it is, usually. When you describe a real situation as a mathematical probability space, you turn each outcome into a simple event (like "the die rolled a 6" or "the number is 1064") with an associated probability. Then you can study random variables on this space, and look at things like its mean, variance.

Reality and the associated experimentation only comes in when considering the law of large numbers, saying that we simulate 100 dice throws (which I guess you could call sample points) as 100 independent, identically distributed variables, and look at stuff about them, such as their mean converging to a certain value, or what their variance is, etc. And that's where the intuitive part of probabilities as being frequentist comes in, not before that

[honest holly]

"hen you describe a real situation as a mathematical probability space, you turn each outcome into a simple event (like "the die rolled a 6" or "the number is 1064") with an associated probability. Then you can study random variables on this space, and look at things like its mean, variance."

I would say this is not generally how people think of things. Everything is thought in terms of random variables, no one ever thinks of the sample space

[nimble condor]

How do you prove that the power set of the natural numbers is uncountable? I just got that problem on a test and I tried doing the diagonal thing but I wasn’t able to

I googled the solution and it said that we need to use Cantor’s theorem b it we haven’t learned that yet

[fossil mural]

well cantor's theorem is "the diagonal thing"

if you have a map from the natural numbers to the power set of the natural numbers, let's call it f, you can take the set of every natural number that isn't in the set f maps it to

so for example
if f(1) = {1, 2, 3}, then 1 would not be in this set
if f(2) = {5, 6, 7, 8, 9, 10, ...}, then 2 would be in this set

now if f maps any number n to this set, we can ask: does the set contain n?
well, it contains n, if and only if f(n) doesn't
but f(n) is this set, so this set contains n if and only if it doesn't, which is nonsense

therefore, any map from the natural numbers to the power set of the natural numbers must miss at least one set

therefore, the power set of the natural numbers is strictly bigger than the set of natural numbers, so it's uncountable

cantor's theorem is essentially this argument, except replace "the natural numbers" with an arbitrary set because we didn't actually use the fact that this is the set of natural numbers; so the more general result is that any set is smaller than its power set

[wraith patio]

i dont understand how the last 2 transitions have been created

i get the first 3 (the ones ive drawn)

because its just merging them

but idk where the last 2 have come from

[meager prawn]

it's a union

$\Delta(S, \sigma) = \cup_{q \in S} \Delta(q, \sigma)$

[vital dew]

Bezier graduate

[meager prawn]

so here {q1, q2} by a leads to : q1 through q1, q2 through q1, nothing through q2, so {q1, q2}

and by b they just lead to q1

[meager prawn]

where S is a set of states, Delta the transition function, and sigma a letter

[honest holly]

It's a hard question for sure

The idea is that you can biject the naturals with say the unit interval

since any subset of the naturals can be thought of as encoding a binary number

[wraith patio]

oh ok yeah think i got it

so if im getting this correctly, for the set on the right, you take everything that q1 with letter a transitions to, then add everything q2 with letter a also transitions to

to get the set on the right

in this case q2 doesnt actually go to anything so its just q1

[meager prawn]

yes

[timber barn]

anyone know something about master theorem and proofs?

[haughty garden]

yes

[honest holly]

Yes but I WONT tell you

[stray reef]

@vital helm here

[cunning mason]

if A is infinite, then does |A| = |A| + |A|?

[brave rock]

Yes, although this requires some work to prove

[ivory badge]

It doesn’t just instantly fall out, but yeah. Consider N+N, and kinda zig zag back back and forth across the two copies

[cunning mason]

so then probably also |A|=|A|^n for any natural number n?

[ivory badge]

That needs choice

I think there’s some choice going on with addition too but |A|=|A|^2 for every set A is kinda equivalent to choice iirc

[brave rock]

For sets where at least one is infinite, |A x B| = max(|A|, |B|), iirc. What you see here is an example of this.

[remote acorn]

I need help with this

[iron marsh]

So a mini sudoku puzzle. Very cool

[remote acorn]

Yes, pretty much. A full sudoku is too difficult for me.

[short geode]

I would start by counting how many possibilities there are for the first row.

Then given a first row, how many possibilities for a second? Given a first and second row, how many possibilities for the third?

[rich kraken]

Does anyone know of any youtuber that is good at explaining ug level discrete math?

[vital helm]

How to solve
x=0mod8
X=1 mod 125

[brave rock]

The chinese remainder theorem.

[jolly ledge]

proof

[weary tiger]

Does this definition make any sense?

[ivory badge]

$A\subseteq B$ is not a set

[vital dew]

The fictitious Sharp

[ivory badge]

@weary tiger

And |B| >= |A| is 100% unnecessary since it’s implied by the fact that everything in A is in B

(Which that’s how it should be defined, as a proposition)

[weary tiger]

Oh, right, it's just a statement. I believe intersections and unions are sets thought. Is that correct?

[ivory badge]

Yes

[weary tiger]

Thanks bro

[obtuse lance]

as a trick, you can use the fact that 2 to a power 3 or larger is 0 mod 8, then use Euler's theorem to get that 2^phi(125) = 1 mod 125.

in general you can do this kind of thing to make a function that's 1 at a power a prime and 0 at other primes to make an explicit formula for the CRT too as a bit of fun

[quaint marsh]

Ping me everyone

[timber barn]

Will this make any difference while proving?

[short geode]

cool example of using groups / a special finite field to treat a game

[turbid mason]

Yes, the proofs will be different. Propositional Logic/Calculus (PC) is not the same as First-Order Logic (FOL). PC is contained in FOL. FOL has more structure. The PC proof of "(P->Q and Q->R) -> (P->R)" mostly use modus ponens, while the FOL proof will also use rules based on the universal quantifier, its introduction and elimination in particular. Does that make it clear? If you know Fichte's Natural Deduction proving method, I can show you the quick contrast directly. What system or book are you using?

[outer bridge]

(p(a), subset) (p(a) is powerset of a) this is a well known poset but if a = 0 then phi will be in the powerset it is said that only phi is a toset too but according to the defination of toset (A,R) for all a , b belongs to A(a is related to b XOR b is related a) but here phi relates to itself but there is not other element so how do we check for it? according to the deffination?

[short geode]

hey you know a lot more math then i thought you did

sorry i talked to you down a bit I misjudged your competence. I was babying a bit because I thought you were (mathematically) immature

[short geode]

btw i thought about what you asked and gave up a bit

i couldn't even show what the formula was true something kept on messing up with my algebra

i don't quite understand how the (sqrt((8n+1))) always ends up the same number giving the range n moves in

[turbid mason]

No worries! Yeah, the problem is actually not trivial.

I’ll let you know if I make any progress.

[near socket]

Hi , I need internship for my personal experience .

[brave rock]

I cannot emphasise how much this is not the place to post this

Nobody here can give you an internship, and it is a super bad idea to post your personal info on random forums online

I strongly suggest you remove your CV @near socket

[gray raptor]

hi i had a doubt

( P ∨ Q ∨ ( ¬ P ∧ ¬ Q ∧ R)) ⇔ P ∨ Q ∨ R

prove that they are logically equivalent

[turbid mason]

What's your doubt? Do you recall what it means for two propositions to be logically equivalent? One (brute force) way to see it here is with truth-tables.

[gray raptor]

Without using truth tables is the question

[turbid mason]

If it wants you to manipulate algebraically, one way to do it is to simply starts by using the De Morgan rule here on (¬ P ∧ ¬ Q ∧ R). Starts from the left hand side, and use those logical equivalences you already know. Be sure to justify at each step. Let me know if that helps.

Further Hint : ||Use the law of double negation, and the idempotence of "∨".||

[spring hound]

Do you know how to do A v (¬A ^ B) <=> A v B?

[proud needle]

I have a question about Turán numbers

If we're considering the Turán number of a graph, like $K_3$, would the Turán number be 2?

[vital dew]

sxbuto

[proud needle]

Or am I understanding Turán numbers incorrectly

[pastel coral]

To solve this, I know how the Chinese remainder theorem works, but I suppose I need to have equalities of the form x (moduli)= a?

So is 2x (45)= 26 the same as x (45)= 13?

[pastel coral]

or how do i get started with this problem?

[clear pier]

Hey y’all this was one of the previous quizzes

I wanna ask is the correct answer d?

Or is it a?

I cant seem to get the union and intersection right. If anyone can explain it to me ;-;-; that would be great

I know with the union it involves everything and with the intersection anything that’s below it. Is that right?

Also side note: if anyone is willing to be a study buddy that would be great help ;-;

[glossy kayak]

hello; i have a list of elements [0 ,1 ,2 ,3, 4, 5, 6, 7, 8, 9] is it possible to create a factoradic (or rather to permute) the list starting with the first elements first?

ie

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 0, 2, 3, 4, 5, 6, 7, 8, 9] [0, 2, 1, 3, 4, 5, 6, 7, 8, 9] [2, 0, 1, 3, 4, 5, 6, 7, 8, 9] [1, 2, 0, 3, 4, 5, 6, 7, 8, 9] [2, 1, 0, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 3, 2, 4, 5, 6, 7, 8, 9] [1, 0, 3, 2, 4, 5, 6, 7, 8, 9] [0, 3, 1, 2, 4, 5, 6, 7, 8, 9] [3, 0, 1, 2, 4, 5, 6, 7, 8, 9] [1, 3, 0, 2, 4, 5, 6, 7, 8, 9] [3, 1, 0, 2, 4, 5, 6, 7, 8, 9] [0, 2, 3, 1, 4, 5, 6, 7, 8, 9] [2, 0, 3, 1, 4, 5, 6, 7, 8, 9] [0, 3, 2, 1, 4, 5, 6, 7, 8, 9] [3, 0, 2, 1, 4, 5, 6, 7, 8, 9] [2, 3, 0, 1, 4, 5, 6, 7, 8, 9] [3, 2, 0, 1, 4, 5, 6, 7, 8, 9] [1, 2, 3, 0, 4, 5, 6, 7, 8, 9] [2, 1, 3, 0, 4, 5, 6, 7, 8, 9] [1, 3, 2, 0, 4, 5, 6, 7, 8, 9] [3, 1, 2, 0, 4, 5, 6, 7, 8, 9] [2, 3, 1, 0, 4, 5, 6, 7, 8, 9] [3, 2, 1, 0, 4, 5, 6, 7, 8, 9]

[silk wing]

Can anyone solve this please

[lone burrow]

if you need to further your understanding of propositional logic you should read “how to prove it” by daniel j velleman

an excellent explanation of everything you need to know on negating, proving, creating statements etc

[silk wing]

Sounds interesting thanks I will look into it

[snow junco]

2 inverse mod 45 is not 1/2, so no. Multiply both sides by 23 instead (2*23=1mod45)

Otherwise I think you’re on the right track

Wait I’m an idiot 23*26 is 13 mod 45

You’re all correct

Not sure if crt will work though

Given modulos aren’t coprime

Or nvm that still is solvable

[jolly ledge]

so I have this problem...

and when I translated it to math it didn't look any easier, well, prob cuz I was doing that without using brains

let $x$ be the total number of sticks of length 2, $y$ and $z$ be those of 3 and 4 respectively. Then I need to solve\
$2x_1 + 2y_1 = 10 n_1$\
$2y_2 + z_1 = 10n_2$\
$x_2 + 2z_2 = 10n_3$\
$3x_3 + z_3 = 10n_4$\
$5x_4 = 10n_5$\
Where $x_1 + ... + x_4 = x$, $y_1 + y_2 = y$, and $z_1 + z_2 + z_3 = z$. Maximize $n_1 +... n_5 = n$.

how I "derived" this was to consider all possible combinations of sticks to get a stick of length 10

we have
2 sticks of length 2 + 2 sticks of length 3
2 sticks of length 3 + 1 stick of length 4
1 stick of length 2 + 2 sticks of length 4
3 sticks of length 2 + 1 stick of length 4
5 sticks of length 2

but clearly, solving this is um, quite undesirable. I considered CRT But I'm unsure of how to implement it.

[vital dew]

Kiameimon | Welt Rene

[jolly ledge]

at 1st I considered prioritising one or two of these combinations and using the remainder to form whatever sticks I can. For example I'd try to have as many sticks in the form of 2 sticks of length 3 + 1 of length 4, and 2 of length 4 with 1 of length 2, before you finally use the remaining sticks to form whatever pairs u can, but I couldn't prove that this is always going to be the optimal combination.

[jolly ledge]

wait... I just realised that this is wrong. my brain's so... crammed

[fossil mural]

||using an x+y that you already have instead of bonding together an x and a y is always at least as good: if you later want an x+y instead of an x and a y, you can just bond the x and y then
also, sticks of length 3 are only useful when you have two of them (because they're the only odd-length sticks involved and we want to make even lengths), so we can bond them together in pairs first and act like we were given sticks of length 6||

[jolly ledge]

mhm. sticks of length 3 must form pairs...

Oh... could that be what we use to decide how we pair the 2s and 4s?

oh wait, that could just work lemme dig further into it

[normal patio]

HELLO I need help in discrete maths

isis any one doing discrete maths from rosen?

Iwanttolearndiscretetoimprovemylogicbuildingfordsa

can anyone help me out

[jolly ledge]

[normal patio]

ok

rosen book for mathematics

Is it good

?

[jolly ledge]

depends on what u mean by "for mathematics"

it's a decent discrete math textbook

but discrete math isn't really that important for higher math

[normal patio]

I didn't get u

[jolly ledge]

what part specifically did u not get? And you're asking if rosen is a good book?

[normal patio]

Yess

Would it be good for improving logics

I am solving dsa questions

So could u tell?

[quiet eagle]

I couldn't find a solution online, so I want to ask for help here.
First, how do I show that for every x there is such y?

[brave rock]

Hint: Bézout.

[quiet eagle]

okk, I'm not familiar with his Lemma, but I'll look into this. ty

[quiet eagle]

The textbook I used hasn't even mentioned the euclidean algorithm at this point let alone Bézout's Lemma. Is there a way without using much theorems?

[little prism]

what is example 2.3.4?

[proud needle]

what book is this? is this paul zeitz?

[quiet eagle]

yes, it is

But wait, I think I have skipped that example and its given solution before. I'll try again after having understood example 2.3.4. I'll reach out to you again

[brave rock]

No.

At the very least, since this statement is equivalent to it, you will end up proving it in any case.

[quiet eagle]

I sadly can't apply the proof from example 2.3.4 to this

[quiet eagle]

Oh I see, well it should be possible to do this proof without knowing Bézout's Lemma, I hope

[brave rock]

I doubt.

You should at least learn Bézout. It is a keystone of elementary number theory

[quiet eagle]

I can't believe such a popular book has such a bad design

[remote acorn]

Can I form the composite function f(g(x)) if g(x)'s codomain does not equal to f(x)'s domain?

[faint sphinx]

No

If the codomain of g is a subset of the domain of f, then the composition can still make sense, however (i.e., you apply g, then include it's image into the domain of f, then apply f)

for example, if A and B are sets, and g: A --> N, f: Z --> B are functions (where N is the natural numbers and Z are integers), then the composite f \circ g still makes sense, as above

[ivory badge]

If you ever have some output of g which isn’t in the domain of f, that’s problematic

[remote acorn]

Makes sense, so I suppose that f(g(x)) is undefined if g codomain is neither a subset nor equal to f domain?

[ivory badge]

Well, if the image is a subset of the domain of f, you can do something

Think sqrt(x) as a function R+ -> R+ on the positive reals

x^2 can be seen as R->R

Composing them still makes sense even if this x^2 function has bigger codomain

(Though you’d want to instead look at g: X -> im g, but uh)

[remote acorn]

But it need restriction right?

[ivory badge]

Well, it’s not so much restriction as uh

Corestriction ig?

[faint sphinx]

Essentially, the distinction is between the image of a function, and it's codomain. In the example that I gave, we can extend the codomain from N to Z, since N is a subset of Z. In Sharp's example, you can restrict the codomain to just be the image, and it can stil make sense. So really, it matters that the image of the function g is in the domain of f

[ivory badge]

Basically, it just needs to not spit out anything problematic

[nimble condor]

How does one do proofs in Discrete Math? I still really don’t understand.
My prof keeps taking off lots of points on my homework and tests for “incorrect justification” but I don’t understand what I’m doing wrong. My grade is in the mid-70’s but the average grade in the class is 95. For the last test I studied by doing 20 practice problems from the textbook that covered the same topics that were on the test, but I got a 73 on the test itself. The test before that I got a 66.

I’m practicing a lot of problems and I’m taking a lot of notes so there must be a systematic error that I’m making.

[ivory badge]

What kinda of justifications do you make

[nimble condor]

Wdym

[ivory badge]

If he keeps counting off on your justifications I’d assume that’s a reasonable place to start

[nimble condor]

I do the problems on the tests and homeworks, the prof takes points off because something I said was incorrect

[ivory badge]

Give an example problem

And your own solution

Without looking at a given one, ideally

[nimble condor]

“Prove that if R is an equivalence relation on a set A, the equivalence classes of R form a partition of A.”

This was my solution, and the professor gave me 3 points out of 10 possible.

[ivory badge]

You pointed off to a prior problem which may be not ideal

Assuming 3 was good i probably wouldn’t count off much here though

Maybe make a note that you have at least one equivalence class [a] for each a?

This doesn’t seem like a 3/10 to me though

[nimble condor]

The prof has a reputation as a very easy grader so I might put in a regrade request for that specific problem tbh

Got a 7/10 on this problem

Prof’s only comment was “bad justification, can’t award full credit”

I think I should have just been more clear and not tried to be concise.

[ivory badge]

this is bad and too concise

[nimble condor]

My logic is sound, the way I’m writing the proofs isn’t.

[ivory badge]

you say "because gf is bijective"

but thats what you're proving

so no

[faint sphinx]

You only checked that the domains matched on this question. There could be many functions C-->A that are not f^{-1} g^{-1}. Instead, think about what it means to be an inverse, and how you could show that through composition of f^{-1} g^{-1} and gf

[astral hatch]

is this right…? im self studying so maybe this is dumb

this is a practice exam, ill delete it if thats against the rules

[brave rock]

This is not right

Recall $\neg\forall x \in S, P(x)$ is equivalent to $\exists x \in S, \neg P(x)$ for any predicate $P$.

[vital dew]

Borty

[astral hatch]

Thats helpful, thanks

So i just change the universal quantifiers to existential quantifiers

[brave rock]

Still no, but I want you to think about it.

[remote acorn]

I have an injective but non-surjective function f: A -> B. Then, is the inverse function of f f^-1: B->A or f^-1: rng(f) -> A?

[weary tiger]

strictly speaking f is not invertible. you need to restrict such an f to its range to get an invertible function

and then the inverse would be a function from range(f) to A

that's if you want to be incredibly precise. this is usually done implicitly

[remote acorn]

Got it, thanks.

[weary tiger]

Hey i want a book that covers math from grade 1 to college
I am in bca degree program
I had mathematics in school but
I was not good i would like to study everything from basic to advance

[brave rock]

Lang's "Basic Mathematics" might help you out

[weary tiger]

problem: Let G be a connected graph. Let $x, y \in G$ such that $xy \in E(G)$ and $G' = G - xy$.\ (a) Show that if G'
is connected, then G has a cycle C containing xy.\
(b) Show that if G'
is disconnected, then G'
contains exactly 2 distinct
connected components, C1 and C2, such that $x \in C_1~and~y \in C_2 $\par
solution: \par(a) G' is connected that mean there exists an xy-path, suppose that $v_i\in V(G)$. then there is a path $P={xv_1,v_1v_2,...,v_{n-1}v_n,v_ny}$, $G' = G - xy\implies G = G'+xy$ this mean that we can have the cycle ${xv_1,v_1v_2,...,v_{n-1}v_n,v_ny,yx}$.\
(b) let $C_1~and~C_2$ be connected components such as $x\in C_1~and~y\in C_2$ such as $V(C_1)\cup V(C_2)=V(G)=V(G')\land\ V(C_1)\cap V(C_2)=\emptyset\land E(C_1)\cup E(C_2)\cup {xy}=E(G)$ we have that $G = C_1 + C_2 + xy \implies G'= G - xy = C_1+C_2$ so G'
contains exactly 2 distinct
connected components

[vital dew]

john.

[weary tiger]

can someone tell me of it is correct ?

[faint sphinx]

(a) is alright, I don't really follow your argument in (b) though

To me, it seems like, since you are starting off with V(C_1) \cup V(C_2) = V(G), you are already assuming that there are only two connected components

[weary tiger]

oke i'll think about it more

[faint sphinx]

Clearly, there are at least 2 connected components, and clearly x and y are in distinct components, yeah. But why can't there be more than 2? I would try to approach this along the line of "Suppose G-xy had more than 2 connected components. Then there exists a z \in G with no path x --> z and no path x --> z in G-xy..." then try to get a contradiction

[weary tiger]

thank you @faint sphinx

[thorn silo]

Hi, Im solving for 11x + 7y = 6 using extended eucledian algorithm, Im getting that x = 2 and y= -3. But in the solutions it shows that x =-2 and y=4, anyone know who can help me understand how that happens?

[faint sphinx]

The extended Euclidean algorithm finds the gcd of the two integers x and y, as a linear combination combination g(x,y) = ax + by . Here, gcd(11,7) = 1, and you can check that 11x + 7y = 1 = gcd(11,7)

Try multiplying x and y by 6.

Although I guess that won't get you x = -2 and y = 4 huh

[thorn silo]

I tried that too, but no I didnt get those results :/

[astral hatch]

What do these symbols mean

Is it a normal 3 choose 3

Wait i found the answer

Its a multi choose

[warm flower]

Anyone got any tips for converting geometric representations of matroids to matrices?

[warm flower]

Okay now I think I got asked to do a representation that's unpossible

[jolly ledge]

wait what's a multichoose

[astral hatch]

idk i used wikipedia

[weary tiger]

im not sure what that is

maybe binomial coefficient?

so like

(a)
(b)
but say a and b are in the same parenthesis

then,

(a)
(b)
= a!/b!(a-b)!

so like

(5)
(3)

= 5!/3!(5-3)!
= 5!/3!(2)!
= 120/6(2)
= 120/12
= 10

i think that's what you're referring to

but im not sure

wait no

you can describe it on text with

C(5, 3) = 5!/3!(5-3)!
= 5!/3!(2)!
= 120/6(2)
= 120/12
= 10

i think

im not sure since

i just started these kinds of things

so mb if it's wrong

[cobalt cipher]

,w multichoose

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by amukh1

[cobalt cipher]

💀

[astral hatch]

Is there somewhere i can grab discrete math practice problems from or practice exams

[vital dew]

john.

[weary tiger]

crapppp

[weary tiger]

?

[jolly ledge]

dw I didn't understand either.

[cobalt cipher]

Maybe aops

[astral hatch]

Does an inverse relation just take each element in the relation and switch the two

Ie, if i have R = { (Rock, Scissors), (Scissors, Paper), (Paper, Rock) },

R^-1 would be { (Scissors, Rock), (Paper, Scissors), (Rock, Paper) }

[faint sphinx]

Yes, the inverse relation just swaps the order of each pair in the original relation

[astral hatch]

Thanks!

[vague scarab]

For this, since B is reflexive and A is a subset of B, don't I just include (1,1) and (4,4) and then use combs? So like |A| = 11, |SxS| = 25 and then since B is reflexive, |set of potential pairs| = 25-11-2 =12? Then it'd be 2*(12C0+12C1+...+12C5) + 12C6

or am I missing something

[warm flower]

So you're taking B = A, (1, 1) and (4, 4). That's the minimum they need to satisfy A subset B and B reflexive

For every other value in S x S \ B, taking any subset of that and tacking it onto B gives you a valid B

[vague scarab]

wait no

i'm definitely wrong 💀

[vague scarab]

it's just the powerset then hey

but actually I compared my answer and they're the same value mine just overcomplicates it lol and it marks it wrong

[warm flower]

well the powerset of the rest of it

[vague scarab]

Yeah that's wat i meant my bad

[cunning mason]

if $z:B\to A$ and $k:C\to D$, what exactly proves that for all $f:A\to C$, the function $k\circ f\circ z$ is unique?

[vital dew]

MyFavoriteAccount

[cunning mason]

is it that composition is a function?

[meager prawn]

composition between two well defined functions is always well defined

(k o f o z)(x) = k(f(z(x))) is clearly unique

[quiet eagle]

I got this exercise in the topic "Invariance Principle". I wanted to do this proof on my own, but I can't find the invariances ;(((. Can you help me find the invariance(s), so I can work with that? The obvious invariance is the number of integers. I suppose, that is useless though.
"
Start with the positive integers 1,..., 4n − 1. In one move you may replace any two integers by their difference. Prove that an even integer will be left after 4n − 2 steps."

[ivory badge]

Even + even = even, what about other combinations

[quiet eagle]

I have thought about that already!!! But I forgot

thanks

[urban berry]

hi quick question

for a question where we have to prove inequalities

what is the best way to approach it

or is there some sort of pattern of methods that i should exhaust

im reviewing for my exams and this question in particular is triping me up

yeah

y 😢

intro one but yeah

it was covered in the start and i was pretty good at it back then but now its kinda forgotten

i was thinking of using AGM

or AMGM as some people call it

yup x,y >0 so no concern in this scenario

im trying to manipulate it to arrive at some sort of basic fact then build my proof form there

but so far its been running in circles

gotcha

[nimble condor]

how do you do RSA encryption?

i'm very confused

[vague scarab]

How would I go about proving that a homogenous linear recurrence relation that has a characteristic equation with irrational roots will yield a closed form solution that generates integer values?

[vague scarab]

this is the question btw

[haughty garden]

A and B are not necessarily integers

[vague scarab]

yeah that's wat i wrote but im guessing i need to write more than that?

or would that be enough lmao

[haughty garden]

Well, they’re claiming that A and B are integers which leads to their confusion of a_n being irrational, which I suppose is the “incorrect” conclusion

Probably something like that anyways lol

[obtuse lance]

I think when A=B they end up cancelling out if you expand it by the binomial theorem

at least, it's a common scenario to end up in, idk if it applies to this case

[vague scarab]

Yeah I figured as much I didn't do the working though because it seems kinda annoying for a 2 mark question

I guess just pointing that out would be enough

especially since they say briefly justify

[haughty garden]

Someone asked this very same question to me a few days ago as well

That was at least the conclusion that we were happy with kekw

[vague scarab]

Wait exact same question? If so then probably cos we have an exam and these r from like the question bank that could possibly be used

There's like 17 Qs and they throw 1 or 2 in

[haughty garden]

Yea you probably go to my uni

[vague scarab]

smth like that

[haughty garden]

[obtuse lance]

if A=-B I think you end up having an integer multiple of sqrt(...) or 1/sqrt(...) to work too

that's how the fibonacci numbers play out I think

[vague scarab]

LMAO UNSW?*

surely not

[haughty garden]

yessir

[vague scarab]

far out small world

[haughty garden]

Yea basically boils down to the constants not necessarily being integers I think

a la Fibonacci sequence

[quiet eagle]

"Start with the positive integers 1,..., 4n − 1. In one move you may replace any two integers by their difference. Prove that an even integer will be left after 4n − 2 steps."

The way I wanted to show this by going back from S(4n-2): There is always one more uneven number in these 4n-1 numbers than even numbers, because 4n is not included.
So S(4n-2) = even = even + even = even + uneven + uneven. Now we always have exactly one uneven number more than the even numbers because uneven = even + uneven that doesn't change.

On the other hand if the remaing number would be uneven:
S(4n-2) = uneven = uneven + even

there would be no possibility to get exactly one additional uneven number... wait that's not true..

Is this the wrong way?

[obtuse lance]

I think it's the wrong way

since you have +1 = -1 mod 2, you can just pretend you added them. And since addition is associative and commutative, you now are just adding the numbers from 1 to 4n-1, so that's (4n-1)(4n)/2 = 2n(4n-1) = 0 mod 2

[quiet eagle]

That is very nice. Thank you

[obtuse lance]

Yeah you're welcome

[timber barn]

Is this correct?

beause U is or not and right?

[median flare]

It's union so yh

[timber barn]

but it should be or

[timber barn]

this would be and

[fossil mural]

it isn't "A union B" though, it's not A union B

x isn't in the union of A and B

which means x isn't "in A or in B", which is the same as it not being in A and not being in B

[timber barn]

what if it was cross section

how would you write that?

[median flare]

So wouldn't it be better to write x $\notin $ A,B?

[fossil mural]

if x isn't in the intersection of A and B, then that means it isn't "in A and in B", so either it's not in A or it's not in B

[timber barn]

I think that the bot is not working

[timber barn]

ok thanks

[fossil mural]

$\nepsilon$

[vital dew]

bee [it/its]
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[fossil mural]

looks to me like it's working

i think you wanted $\nin$

nope that doesn't exist either

$\notin$

[vital dew]

bee [it/its]

[fossil mural]

there it is

[median flare]

Ok

[timber barn]

Was confused because of this

here is clearly an and

[fossil mural]

yep
x is in the intersection of (complement A) and (complement B), therefore x is in complement A and x is in complement B

which is different from x being in the complement of (the intersection of A and B), or equivalently, x not being in the intersection of A and B

[timber barn]

thats why I thought that here should be or

[fossil mural]

if it was "x is in the union of (complement A) and (complement B)" then that would be the same as "x isn't in A or x isn't in B"

but if you have "x isn't in the union of A and B", that means "x isn't (in A or in B)"

[timber barn]

can you write that?

[fossil mural]

$x \in \overline A \cup \overline B \iff x \notin A \lor x \notin B$

[vital dew]

bee [it/its]

[fossil mural]

i think maybe what's confusing you here is that there are two different things happening

there's the correspondence between set operators and logical operators: complement is not, union is or, intersection is and

and then there's the fact that "not (A and B)" is equivalent to "(not A) or (not B)", and "not (A or B)" is equivalent to "(not A) and (not B)"

or phrased in terms of sets, $\overline{A\cup B} = \overline A\cap\overline B$ and $\overline{A\cap B} = \overline A\cup\overline B$

[vital dew]

bee [it/its]

[timber barn]

ooh so it changes from or to and because there is negation

[rich tiger]

I dont really understand this

[spare slate]

^ (Reposted in #help-15 message)

[astral hatch]

So partial orders need to be no reflexive and transitive

But because each integer in the set divides itself, doesnt that mean each element is in a relation with itself, meaning its reflexive and not a partial order

Later on though they say you can assume | is a partial order on D, where the same issue would reside

Hold up im just wrong

Nvm

[astral hatch]

Ok so i confused the definition for strict posets and a normal one

Posets need to be transitive, reflexive, and antisymmetric

I can show its not a partial order because it isnt antisymmetric - -1 and 1 divide each other, but they arent the same element

[ivory badge]

Yes

[ivory badge]

“Strict poset” is just a <= b and a =/= b, they’re the same otherwise

[vital dew]

Tofu

[vague scarab]

For this would I just sub $x = 91 + 1459t$ in for $x^2$ so then it's
\begin{align*}
(91+1459t)^2 &\equiv -473 \mod{1459^2}\
182\times 1459t + 1459^2t^2 &\equiv -8754 \mod{1459^2}\
182t + 1459t^2 &\equiv -6 \mod{1459}
\end{align*}

[vital dew]

Cone

[vague scarab]

but then Idk where to go from here

I thought maybe I'd complete the square but then I'm gonna end up with horrible numbers lol

or is this just completely wrong

[obtuse lance]

yeah you can do this

at least if I understand your findal step correctly, I haven't worked through it

[vague scarab]

Yeah I skipped a bit of the working lol

[obtuse lance]

yeah looks like it checks out since 1459 factors out

you can use the quadratic formula directly, and hope the square root is easy to calculate

there's anothe direct way to get it by something called Hensel's lemma, basically it's just Newton's method from calculus

you have f(x)=x^2+473 then f'(x)=2x and you make g(x)=x-f(x)/f'(x) and your answer is g(91) mod 1459^2

although you'll end up having to find the inverse of whatever is in the denominator, so that might be annoying to do too, although you could do it with the euclidean algorithm by hand I suppose if you wanted

[vague scarab]

I just slipped it into the quadratic formula and it's pretty ugly assuming I've done everything right rip

[vague scarab]

hmmm I'll look into this I don't think we've learnt it (or at least I haven't lmao)

will have to double check the lecture notes

[obtuse lance]

it's not really any different in principle from what you're doing actually

if you have some a such that f(a)=0 mod p and f'(a) != 0 mod p then you can grind through a bit, which is explicitly what you did with a=91 there, since you want f(a+tp)=0 mod p^2, and you can expand it out generically as: f(a+tp)=f(a)+tpf'(a) mod p^2 then you have 0 = p (f(a)/p + tf'(a)) mod p^2 and divide out the p like you did, 0 = f(a)/p + tf'(a) mod p and solve for t as t=-f(a)/pf'(a) mod p

actually come to think of it

your t^2 term should be multiplying something that's 0 mod p

@vague scarab check your work and make sure

it should be linear lol

1459=0 mod 1459 throw it out 🤣

I can't believe I didn't catch that, I'm so tired

[vague scarab]

oh yeah LMAO wtf

wat am i doing

so then it's just [182,-6]

man i rly overcomplicated that for no reason

ty for the help tho (:

[obtuse lance]

yw lol

[sick lantern]

no channel for graph theory?

[faint sphinx]

Graph theory can go here

[outer bridge]

so expect K2 graph we cannot have a complete bipartite graph for any number of verticies?

[ivory badge]

Sure you can, draw K3,3

[outer bridge]

but it will be odd number cycled graph

[ivory badge]

what

[outer bridge]

oh sorry it can be a cyclic

[ivory badge]

It’s hard to have complete graphs that are acyclic yes

[faint sphinx]

Complete in the sense of typical graphs, no that's the only one (unless you count K1 maybe?)

[ivory badge]

You can draw an edge from a single node to an arbitrarily large second set of nodes though

Which is bipartite

[faint sphinx]

But there is a notion of a complete bipartite graph which Sharp is referring to

[ivory badge]

Which ya know, you do mention bipartite in your message

[outer bridge]

hey k2 there is a complete graph btw

so i meant to say every complete graph except k2 will not be bipartite

[faint sphinx]

Correct

[outer bridge]

sorry for the confusion i got a lil confused

i added complete before bipartite cus i was studying it

it made the difference ig

[faint sphinx]

Yeah you just accidently said something that has an actual meaning lol, it happens

[outer bridge]

💀

[outer bridge]

oh i get it now every complete bipartite graph is a bipartite graph so the statement will have meaning regardless

[outer bridge]

here i just wanted to clarify if the cycle is of odd length for example c3 , c5 it will not form a bipartite graph because there will always remain one element which related to the element in the set sorry if it sounds vague i have yet to learn proof of these things

and if we try to make a complete graph like k3,k4 it will always have odd length cycle which will make any complete graph expect k2 invalid of bipartite

i think of this in a way like every polygon can be broken into traingles and every traingle has odd number of vertices

and because they are complete graph they will have all the edges to every vertices

[ivory badge]

Well, if you show that bipartite graphs don’t have odd length cycles then drawing a triangle would do it I think yeah?

[faint sphinx]

Correct

[outer bridge]

yeah but that would also be a point for all complete graph except k2

[ivory badge]

? Yes

[outer bridge]

so here stay with me for a min let go for maximum number of edges in a bipartite graph lets say the number of vertices is n so the most edges will be represented only if we split it in n/2 n/2 but here we dont consider the fact that if it is even possible to draw a graph like that or not? am i missing something here?

[ivory badge]

I don’t know what you’re getting at here

[outer bridge]

you got it until the point of spliting the set in n/2 vertices?

or not?

[faint sphinx]

You may just be interested in learning about complete bipartite graph directly, that sounds like what you're trying to get at

[outer bridge]

yes , exactly if we have n vertices maximum n.o of edges for bipartite graph

that will be complete bipartite graph and for that we have to split the distinct set in n/2 , n/2

but what i want to ask here if it is even possible to make a complete bipartite graph for maximimum edges is there a proof for that which i you guys can point me to?

its just the lack of imagination on my end

[faint sphinx]

If you split the number of vertices into two groups of either n/2 and n/2 for even n, or (n-1)/2 and (n+1)/2 for odd n, then that should maximize it, yeah. Idk of a place that has a proof written out for that explicitly tho, you may just find it in a section on bipartite graphs in a textbook

[outer bridge]

Yah I'm gonna read Rosen now

[sick lantern]

If we are given that a graph is k connected i.e. deleting any set of k - 1 vertices will not disconnect the graph , how can I go about formally proving that this also means that deleting any set of k - 2 or k - 3 ... Vertices will not disconnect the graph.

[last flicker]

Trying to figure 1b) out here. The advice i've been given is to look for a bijection from the a_i to a different set of variables b_i which in some way forces a_j-a_i>=2j-i or makes more clear when it holds while maintaining b_1<=b_2<=b_3<=b_4 or something similar, but I haven't been able to do that so far. Does anyone have any inspiration on that front? Just looking for a starting point really

[empty sphinx]

The question is basically how do you find 3 consecutive numbers divisible by a square number

[meager prawn]

x works because 2^2 | x, 3^3 | x+1
Adapt this to the case of 3 numbers

[outer bridge]

it was here

[outer bridge]

yeah i found it what i wanted

[charred harbor]

can i ask graph theory here?

[faint sphinx]

yes

[charred harbor]

oh tnx, nvm i kinda get it already

[fallen hatch]

Given a positive integer n, what's the number of nodes in the smallest directed graph such that there are 2 nodes A and B, and there are n paths exactly from A to B

(Acyclic) else infinite number of paths

[ivory badge]

What have you tried?

[fading sun]

idk whether this will get me into oxford but i finished my boolean satisfiability solver which implements cdcl and converts boolean expressions into cnf form using de morgans law and tseytin transformations i've got some improvements that i can add but its going well so far

in c++

[faint sphinx]

Probably not into Oxford on its own, no

[fading sun]

ik not on its own but i think it maybe good enough for my personal statement

[faint sphinx]

If you spin it right, i.e. how it's motivated you to learn more or how it's shaped your interests, then sure that can help

[fallen hatch]

I have only constructions.
Construction 1: Fibonacci numbers
each one connected to last 2
it's known that each number can be represented as sum of distinct fibonacci numbers (zeckendorf for example)
so connect 7 to whichever ones you want to add

Construction 2: binary: each node connected to all greater nodes

there are 2^(n-1) paths from node 0 to node n

then connect node 7 to all previous nodes which have 1s in the binary representation

this seems to be the most space efficient, needing 1+ceil(log2(n)) nodes in total but I struggle to prove it

[quiet tendon]

In a restaurant, four women and four men sit at one round table, on eight chairs
a circle on the same side of the table. Everyone has a random place
assigned. We speak of a match if there are two people of different sex next to it
sitting together.
(a) Determine the maximum number of possible matches and the corresponding probability of them
outcome. Note: This means no one of the same sex next to
sitting together.
(b) Also determine the minimum number of possible matches and the corresponding probability.

I think a is 2 * 4! * 4! / 8!

but if I do this I won't take into consideration it is a round table right?

[boreal lark]

@blissful path

[ivory badge]

@pale epoch ayo we got some ping spam it seems (in multiple channels)

[pale epoch]

surely it will improve if you ping me

[ivory badge]

Idk chief ur the mod

[faint sphinx]

Least stubborn mathematician (part 2)

[jolly ledge]

fr wait sharp actually has a life outside of #proofs-and-logic ?

[ivory badge]

Not much

[jolly ledge]

please DM @graceful condor if u wanna advertise your server

[meager prawn]

I'm sure @ Moderators makes it get to them even faster

[jolly ledge]

I mean by now pretty sure a mod would have checked this channel so

[meager prawn]

arguably yes

just keeping the joke going because I'm bored

i.e. launching modded minecraft

[rigid oriole]

<@&268886789983436800>

[rigid oriole]

not true

[jolly ledge]

me oof

[vernal python]

anyone free I need some help asap

[faint sphinx]

bruh what is your bio (offensive)

questionable

[rigid oriole]

pings mods then

i cant make head or tail out of it

[faint sphinx]

idk, seems homophobic to me

[ivory badge]

Hieroglyphs

[naive mural]

can anyone here take a look at this negation problem? #1142924371317489747 message

[ivory badge]

Don’t advertise it

[weary tiger]

Can we do this without Pigeonhole?

[ivory badge]

Why do you want to without pigeon

[weary tiger]

Because my book is supposed to cover it in a later chapter 💀

[faint sphinx]

probably try induction then ig?

[ivory badge]

What have you tried

[weary tiger]

No idea yet

[ivory badge]

Also yeah finite means induct oftentimes

[weary tiger]

How do i do it?

[ivory badge]

Well if he told you how that would basically solve the problem

[weary tiger]

Ye you're right

Ig I have to prove that it is true for all cardinality n?

[ivory badge]

Well, I suppose that would work

[gusty swallow]

you could also use the image of f as a subset of B to show a contradiction.

[regal gate]

how is the exercise true

take an edge x-y and sps x and y are not connected to anything else. Put x in some V_(i-1) and y in some V_i

what am I not understanding

[meager prawn]

Try to build such a partition. You'll notice that it basically forces itself to be a certain way:

If v is in Vi, then all its predecessors must be in V(i-1) and all its successors in V(i+1). It being connected means this process (which is akin to a graph traversal) naturally creates a partition (since we're assuming existence, everything works well). Then the first partition is indexed as V0 and that is it.

And from that it should be quite clear that it is indeed unique (most convincingly because it doesn't depend on the starting vertex)

[regal gate]

ah wait the graph must be connected (?)

[elder berry]

that is true if the graph were connected, but all it's stating is that the graph mustn't have an isolated point, so Croqueta's construction does follow that definition

[meager prawn]

It's unique for every connected component

[regal gate]

I was thinking of something like

and connectedness is not mentioned anywhere

[meager prawn]

But you could offset them between one another

You'd need to impose that for every connected component, V0 mustn't be empty

[regal gate]

so then the exercise is false

or what definition of uniqueness are they using? because its not clear to me then. A partition is something that deals with sets

[meager prawn]

A layered partition is unique if for all layered partitions you could make, they'd be the same

i.e. have the same height, and same V0, V1, etc

[regal gate]

above I show an example where V0 changes for two layered partitions

and I don't know what height means, if you could explain it, I'd appreciate it

[elder berry]

the exercise is probably false, for uniqueness to exist one may assume that for each connected component, the very first outgoing edge must be between V0 and V1, so this solves the uniqueness problem, for examplein your sketch that would be the second option

[meager prawn]

h is the height. Doesn't make sense, but h <=> height to me

[meager prawn]

i.e. this

[elder berry]

oh, btw must the graph be directed?

[meager prawn]

It better be

It says "edge goes"
Sounds directed to me

[elder berry]

yeah alright, ty

[regal gate]

yeah, the graphs are directed in the discussion

but it doesnt make any difference right? it is obvious that if it is directed then "goes" also implies a direction

[elder berry]

if it were undirected it would be just in V0 hahahaahha not true nvm