discrete-math

[sour arrow]

But T(n/2) is a member of the original question. So, we can sub that in:
T(n) = 7[7T(n/4) + (n/2)²] + n²

Yeah, n/2 is really the only thing that the question "allows" here

[summer gull]

right okay

[sour arrow]

So now we have T(n) in terms of T(n/4)

[summer gull]

right and then you do the same thing and you basically find a pattern?

discretely?

[sour arrow]

Yup

[summer gull]

right and that's what I did - would it not be what I had earlier?

[sour arrow]

To do this again, you'll need to sub n/4 this time

[summer gull]

k was just a sum I had from k > 0

[sour arrow]

Oh, was that the answer for what T(n) was?

[summer gull]

yea that's what I ended up with

for k > 0

lemme think of how to write this cleanly

[sour arrow]

There shouldn't be a k, since T is a function of n

[summer gull]

right I just chose k because I needed another variable for distinguishing it from n?

[sour arrow]

Oh I see, that's what the thing is if you do this k times

[summer gull]

yeah

so i do it k times and I'd end up at any of those

[sour arrow]

What happens if you do this infinitely many times?

[summer gull]

for k > 0

it would go to 0 right

lim k -> inf would be n/inf which is 0, + a significantly small number times kn^2 which would also be 0 in limit speak

[sour arrow]

I'm not actually very sure myself. From the looks of my example, we're about to get a sum of quadratics

[summer gull]

ouch

okay

this is gonna be fun for a 1st year college student like me

lmao

[sour arrow]

Yeah these are tough sry

[summer gull]

you're good haha

so if it's a sum of quadratics

[sour arrow]

There's better methods for finding them imo

[summer gull]

how would I find the big theta of that?

just trying to lay some groundwork

[sour arrow]

A sum of quadratics is a cubic

[summer gull]

sorry for all these questions

right

so because a sum of quadratics is a cubic

it would be O(n^3) right

[sour arrow]

So that's my guess. Θ(n³)

[summer gull]

and then the lower bound would also be Omega(n^3) and the upper bound would be O(n^3) which makes it Theta(n^3)

[sour arrow]

I'm not amazing at this method either and I'm working without pencil/paper so for the love of god take me with a grain of salt

[summer gull]

gotcha

okay

tysm tho

!!

[sour arrow]

But the answer can't be T(n) = 0 since T(1) = 1

[runic mauve]

do any of you guys know how to show that (n/(n-1))^n>e

i can send you what the rest of the problem looks like if you want

[faint narwhal]

this isn't true since n/n - 1 = 0

[runic mauve]

oh sorry

its for n > 2

integers

or does that not change it

[last sigil]

I think he means (n)/(n - 1)

[faint narwhal]

3/3 -1 = 1 - 1 = 0

[runic mauve]

yeah sorry @last sigil u got it

lmao

im just in a tutor center rn and we're having trouble figuring it out

but we might have gone the wrong way

[faint narwhal]

writing n/(n-1) = 1 + 1/(n-1) might help

[runic mauve]

is that equivalent to e?

[faint narwhal]

uh

[runic mauve]

i thought e was a limit

[faint narwhal]

it can be thought of as a limit yes

[runic mauve]

i mean i could write that but if it isnt trivial i have to explain it

it might be trivial but not to me atm

[viral parrot]

you have to keep in mind the definition of Euler's number that e = lim n > inf (1+(1/n))^n

so set the two equations up so that its (n/(n-1))^n > (1+(1/n))^n

[olive dragon]

Hello, could we please discuss this problem? thanks

This seems to be the right answer but I don't see how its worked out

Where are the inputs for (i+j^2)+(i+j^2) coming from?

3 & 4 values for variable i and 2 & 3 values for variable j?

(3+2^2)+(3+3^2)+(4+2^2)+(4+3^2)

Okay, I understand this now.

[viral parrot]

correct

[olive dragon]

Thank you for confirming with me^

Another question regarding sorting algorithms

Bubble Sort:

[3,1,5,7,4] -original
[1,3,5,7,4]
[1,3,5,4,7]
[1,3,4,5,7] -end result

Insertion Sort:

[3,1,5,7,4] -original
[1,3,5,7,4]
[1,3,4,5,7] -end result

Bubble sort compares two elements at a time, does Insertion sort compare more than two elements at a time?

[last sigil]

Insertions sort normally creates a new list

Bubble sort compares 2 indices, them swaps them if necessary

Insertion takes a value from the old list and inserts into it proper spot in the new one by comparing it to each value of the new one

[elfin lagoon]

I need a function that outputs all odd primes given 0-indexed inputs

f(0) = 3 , f(1) = 5, f(2) = 7 , f(3) = 11 , etc.

[deep jewel]

The number of nine digit numbers that start with the digit 3 is greater than the
number of nine digit numbers in which no digit is repeated. T/F

I think this is true

because the first would just be 10^8 where the second part would be 10!

can anyone confirm this?

[severe path]

Yes

[deep jewel]

ty

🙏

[cedar dawn]

Hey guys have a question about this anwer
Why are less than pointing towards the smaller number? Maybe it's because I'm reading it wrong, but I don't see how 0 > 3 is true or 3<0 is true

Am I suppose to see this as the less than pointer to the number that is smaller so that
0<3 is true?

[severe path]

Seems like it

[mint salmon]

For outputting primes you can use the sieve of eratosthenes

[acoustic violet]

Hi,
Is there any place online where you can see step by step guide for discrete math?
I am struggling to understand a question which should be fearly easy as it has to do with proving some statement to be equivalent to some other statement.

[wanton sable]

what rules of logarithms can i use to convert 5^(log_2(n)) into n^(log_2(5)) or show that these are equivalent?

[stray reef]

they're both equal to $2^{\log_2(5)\log_2(n)}$

[vital dew]

Ann:

[clever nacelle]

1. Algorithm A uses 10n log n operations, while algorithm B uses n√n operations. Determine the value of n0 such that A is better than B for n >= n0

Can I get help with this, the only hint I was given was "use base 10 not base 2" i tried to set 10nlogn=n√n but, that became very messy. How should I do this.

[faint narwhal]

That's the right idea

[clever nacelle]

Do you have an example by chance

[faint narwhal]

Just do what you did

Solve that equation

[hallow blaze]

hey guys

in this problem

let f: Z x Z -> Z be defined as f(m,n) = 2m + 5n . Show that f is surjective(onto)

why is y = 5y -2(2y)?

isnt it y = 2m+5n?

[faint narwhal]

No

[hallow blaze]

then how would u do it

i dont understnad

i thought ur supposed to show its equal to y

hence surjective?

[faint narwhal]

you are

[hallow blaze]

could u explain then

[sour arrow]

You are supposed to show that every element of the codomain can be an output

[hallow blaze]

ok

so i substitute something

to prove it

right

[sour arrow]

Nah, I wouldn't do it that way. Try showing that you can represent 1

[hallow blaze]

so how

[sour arrow]

I mean, that 1 is an output

[hallow blaze]

wdym

whats the first stpe

step

1 is an output of 2m + 5n?

[sour arrow]

There's not necessarily only one way to do this. But, that's the way I would go

[hallow blaze]

what is the way that does y = 5y -2(2y)?

i wanna know how that works

to prove its surjective

since 1 = 5 - 2 * 2

[sour arrow]

Oh I see. That's ultimately the same way I was about to go

[hallow blaze]

gcd 2,5 = 1

so

1 = 5 - 2 * 2

[sour arrow]

What's f(y, 2y)?

[hallow blaze]

f(m,n)

= 2m + 5n

let y E Z

?

[sour arrow]

Oh mb. I meant f(2y, -y)

[hallow blaze]

y = 5y -2(2y)

so y = f(-2y,y)

[sour arrow]

Yes, that

f(-2y, y) = y

[hallow blaze]

hmm

then what

[sour arrow]

So, in order to get an output y, this tells you what the inputs need to be

[hallow blaze]

thus something

[sour arrow]

Framing the question this way, you can let y be any integer you want, and get the inputs you need. So f is surjective

[hallow blaze]

ok so after

y = f(-2y,y)

what do i say

[sour arrow]

"Therefore surjective"

[hallow blaze]

yEranf

wait what

but why

[sour arrow]

Lol. Or,
"y is any integer, so every integer can be outputted from the function. Therefore surjective"

[hallow blaze]

what does (-2y,y) show

[sour arrow]

I'll do an example. Give me any integer

[hallow blaze]

i mean how can i tell its surjective from f(-2y,y)

because 1 = 1?

and y = y?

[sour arrow]

Gib integer

[hallow blaze]

um

-3

[sour arrow]

f(6, -3) = -3

Therefore -3 is an output of the function

[hallow blaze]

huh

[sour arrow]

f(-2y, y) = y
Therefore y is an output of the function

[hallow blaze]

oh

ok next question

[sour arrow]

And that works for any y you want. You could have given me 27389 but that would be mean

[hallow blaze]

Let g: Z x Z --> Z be defined by g(m,n) = 2^m*3^n. Show that g is injective(one-to-one)

gcd = 1

[sour arrow]

Injective means that every input gets its very own output

[hallow blaze]

right

ok so

gcd = 1

right

right

right

[sour arrow]

Yes but no

That's not helpful here

[hallow blaze]

ok

then

[sour arrow]

Well - that alone isn't helpful. It comes in handy

[hallow blaze]

lets do a

[sour arrow]

There's a much more important role that 2 and 3 fill

[hallow blaze]

lets show

2^m1 * 3^n1 = 2^m2 * 3^n2?

[sour arrow]

If that were true, you'd disprove injective

[hallow blaze]

right so

if m1 cannot equal m2

then one is bigger right

so m2 > m1

lets say

[sour arrow]

Specifically, you want to show that for
f(a) = f(b)
Then it must be the case that
a = b

[hallow blaze]

kk

so im doing a proof by contradiction

here

to show m1 = m2

[sour arrow]

I'm not sure how easy that is to do from little info. However, it's very easy if you can summon unique prime factorization

[hallow blaze]

weoo

since m2 - m1 > 0

that means 3^n is a multiple of 2

but a power of 3 cannot be a multiple of 2

this contradiction implies m1 = m2

so 2^m1 * 3^n1 = 2^m1 * 3^n2

[sour arrow]

"but a power of 3 cannot be a multiple of 2"
That's the power line. Full marks if you include that

Very nice

[hallow blaze]

then 3^n1 = 3^n2

1 = 3^n2-n1

i think

is that it

so i did it?

[sour arrow]

If 3^n1 = 3^n2
Then n1 = n2
Because 3^x is injective

[hallow blaze]

ok

but thats all right

no mroe steps

[sour arrow]

Not sure if you're allowed to assume that one idunno

[hallow blaze]

,_,

nvm ill clarify with my teacher later if ur unsure

[sour arrow]

The important steps are there, yeah. You have to summon the fact that any number written as 2^x 3^y is unique

[hallow blaze]

can we do next problem

this one i suck at

its the chinese remainder theorem and i haz no idea how to do it

so

Use the construction in the proof of the Chinese Remainder Theorem to solve the following system of congruences:
x equivalent 1 (mod 2)

x equivalent 2 (mod 3)

x equivalent 3 (mod 5)

x equivalent 4 (mod 11)

Find the unique solution modulo 330

is there a shortcut

[sour arrow]

Because of Chinese remainder theorem, you know there is a unique solution mod 2×3×5×11

[hallow blaze]

idk anything about this theorem

[sour arrow]

Which is 330 yeah

[hallow blaze]

ok

so m = m1m2m3*m4?

is what ur saying?

[sour arrow]

That's essentially the theorem. If the (mod m)s are each coprime, then the solution is unique (mod their product)

[hallow blaze]

ok

so then what

M1 = m/m1?

[sour arrow]

Now, let's see if I can summon the solution. I tend to guess for it but they probably want the work

[hallow blaze]

M2 = m/m2?

M3 = m/m3?

M4 = m/m4?

[sour arrow]

x = 1 (mod 2)
Means x = 2k + 1 for any k

[hallow blaze]

so

m / m1 = 165

= 1 (mod 2)

is that what ur saying?

[sour arrow]

x = 2 (mod 3)
2k + 1 = 2 (mod 3)
2k = 1 (mod 3)
2k = 4 (mod 3)
k = 2 (mod 3)

[hallow blaze]

uuhhh what

[sour arrow]

Means k = 3m + 2 for any m

And you continue like that

[hallow blaze]

im lost

wat

[sour arrow]

All those lines make sense? Which one is weird?

[hallow blaze]

all

what is x = 2(mod 3)

derived from

[sour arrow]

That's stated in the question

[hallow blaze]

ok

[sour arrow]

I also know that x = 2k + 1

[hallow blaze]

whats k stand for

[sour arrow]

Any integer

[hallow blaze]

oh

ok

is that x = 1 ( mod 2)

[sour arrow]

x = 1 (mod 2)
Means
x = 2k + 1

[hallow blaze]

?

ok

[sour arrow]

Basically, x is odd

[hallow blaze]

wait i thought

[sour arrow]

Three ways to write the same thing

[hallow blaze]

1 means

• 1

im terrible at this

[sour arrow]

x = 1 (mod 2)
Means that if you divide x by 2, you get a remainder of 1

[hallow blaze]

so any integer

[sour arrow]

Which is a fancy way to say x is odd

[hallow blaze]

the remainder is 2 not 1

?

[sour arrow]

x/2 = "something" with remainder 1

x = 1 (mod 2)

[hallow blaze]

1 stands for the modulo?

i thought 2 was

[sour arrow]

Working modulo 2

[hallow blaze]

i thought 1 means divisible once

[sour arrow]

x is congruent to 1

[hallow blaze]

uhhh

im not understanding

lmaoo

explain like im 5

[sour arrow]

If x = 1 (mod 2), then x could be
1, 3, 5, 7, 9...
Because all these numbers, after division by 2, leave a remainder of 1

[hallow blaze]

oh

i thought it would be x = 2( mod 1)

in that case

but its apparently the opposite hmmm

inteeresstinggg

x = 2 (mod 3)
2k + 1 = 2 (mod 3)
2k = 1 (mod 3)
2k = 4 (mod 3)
k = 2 (mod 3)

[sour arrow]

We write (mod 2) in the end to say that two numbers are conguent if you can get from one to the other by adding/subtracting 2 over and over again

Also the same as "leave the same remainder after division by 2"

[hallow blaze]

hmm

mk im gonna try and solve it

[sour arrow]

Okay. Let me know if you need halp

[runic mauve]

That’s a great explanation ^^^ thanks

[scenic axle]

Can anyone give me a hint about how to go about constructing a one-to-one correspondence between the given sets for part c, d, or e?

[scenic axle]

Would lnx maybe work for c if set (0,infinity) as the domain & real numbers as the codomain?

[ivory badge]

i would do it the other way around

[dapper rose]

@scenic axle yes

[scenic axle]

Thank you

[errant bear]

can someone help explain how to find equivalence classes of a function

of A to B

from what I think i understand [x] would be the preimage, or the possible values of the domain for each codomain value? idk tho its confusing

[ivory badge]

i might need you to step back and explain what you actually want

[errant bear]

so we are given sets A and B, and we have a function f, f(x) that relates them

[ivory badge]

if $f: A \to B$ is a function, $f^{-1}(X) = {a \in A,|,f(a)\in X}$

[vital dew]

Darkrifts:

[ivory badge]

the inverse image is the collection of things which map into it (more or less)\

[errant bear]

where does X come from

is that the set from which x is a subset

[ivory badge]

oh, $X \subseteq B$

[vital dew]

Darkrifts:

[ivory badge]

the ^-1 kinda reverses the arrow direction

[errant bear]

ok yeah so i think i get that

[ivory badge]

not exactly, since the inverse proper of a function doesn't always exist, but it's kinda reversing it

[errant bear]

so in the case where A=B=Reals, f(x)=x^2. The equivalence class is

one sec

[x]= {(y^.5, -(y^.5)) | x ∈ R and y=x^2 }?

this is my attempt at an answer

[ivory badge]

$[x] = f^{-1}(x)$

[vital dew]

Darkrifts:

[ivory badge]

?

[errant bear]

um

[ivory badge]

no, that would be $f^{-1}(f(x))$ mb

[vital dew]

Darkrifts:

[errant bear]

is that just x though

[ivory badge]

no

the inverse image is not the same as the inverse function

$\sqrt{x^2}$

[errant bear]

oh yeah myb

[vital dew]

Darkrifts:

[errant bear]

um

[ivory badge]

so anyway, what don't you get, exactly?

[errant bear]

so the pre image is the set of "inputs" going from B to A

right

[ivory badge]

the pre image is the set which gets sent to (whatever you're taking the preimage of)

it's entirely possible that such a set is empty in some cases

[errant bear]

wait so its basically the domain

wait

no

the pre image is what you get after inputting the domain

[ivory badge]

$f^{-1}(X) = {a \in A | f(a) \in X}$

[vital dew]

Darkrifts:

[ivory badge]

the collection in A which sends to X (or B or whatever other symbol)

[errant bear]

yes ok

[ivory badge]

note however that $A \subset f^{-1}(f(A))$

[vital dew]

Darkrifts:

[errant bear]

yeah, because if you have x^2 and your domain is Z, the preimage is N which is a subset of Z right

[ivory badge]

the preimage of N is a subset of Z

should be the whole thing

the preimage of the negative naturals -N is the empty set

[errant bear]

but only positives are being "sent" to B

[ivory badge]

no, x^2 works on negatives too, just only sends to positives

[errant bear]

wait so the preimage IS the domain?

[ivory badge]

the preimage of a set is a subset of the original domain

$f: A \to B$

then

$f^{-1}: \mathcal P(B) \to \mathcal P(A)$

[vital dew]

Darkrifts:

[ivory badge]

(subsets of B to subsets of A)

[errant bear]

is that power set

[ivory badge]

yes

[errant bear]

im lost tbh

time to switch majors woot woot

[ivory badge]

smhj

[errant bear]

im literally not understanding its not u its me

[ivory badge]

if $f(x) = y,$ then $x\in f^{-1}(y)$

[vital dew]

Darkrifts:

[ivory badge]

it's just the inverse function, but allowing more than one thing on the inverse part

[errant bear]

can u answer this q, it will prob sound dumb

[ivory badge]

oof

[viral merlin]

are we allowed to send images

[ivory badge]

depends on the content

[viral merlin]

discrete math

?

[errant bear]

i appreciate ur help but imma just play csgo so i dont cry tonight and just go to my prof during office hours tomorrow thank u @ivory badge

[ivory badge]

aight

[viral merlin]

so i got {3,4,5,6} for a, is that right?

[ivory badge]

I believe so, yes

[viral merlin]

okay for b and c, do you think the y means the y-coordinate of each value in the set or is it just another variable

because if it was the latter, C would be {6} i think

[deep jewel]

@errant bear Discrete math is hard man, but eventually if u keep practicing you will get it. You may be having a bad semester, but that doesn't define your ability in your field. Everyone has their ups and downs

[errant bear]

i mean it was going smooth up until this

like i have no idea what eq classes of functions are and we have like 30 hw problems on it ffs

and like A is RxR and B is P(R) like wtf am i supposed to do we only did single dimension stuff smhh

anyways rant over its csgo time

[deep jewel]

Keep going difficulty in 1 class is not the end of the line

I understand I have to use the difference method here

The ways to arrange abcdef - the ways a is directly followed b or c

I know how to write out the left hand side

6!

I don't know how to represent the ways a is directly followed b or c in numbers

any help

[ivory badge]

what have you tried

[deep jewel]

well I assumed we can group a and b as 1 letter

and a and c as 1 letter

so that we get

6!-4!-4!

actually mabe 6!-5!-5!

[ivory badge]

hm

[mint salmon]

I'm trying to get my formulation exactly right. If I want to use a definition like {k ∈ ℕ | 2k + 1} in a set theory statement, can I then use that in a further statement? like this:

A := {k ∈ ℕ | 2k + 1}

{g ∈ A | g/3}

?

[stray reef]

{k ∈ ℕ | 2k + 1} doesn't make sense

what were you going for

the set of all odd natural numbers?

[mint salmon]

exactly

but also in general

I want to know how to write a set without making mistakes

this is how I understand it: {x | A(x)} where x is defined as the element for which A(x) must be true

and so if I want to use k in another statement, I first need to say what it is

I guess what I meant was A := {n ∈ ℕ | 2k + 1}

and so then I would be able to use n

[stray reef]

"2k+1" is not a statement

it is an expression

the set of all odd natural numbers could be written as {n ∈ N | ∃k ∈ N: n = 2k-1}

now what's on the right of the bar is a statement

change 2k-1 to 2k+1 if your class says 0 ∈ N

[mint salmon]

ok that's what my question was then: how to correctly write a statement. so far it has been very difficult to ask a question about this topic because I don't understand it enough to know what I'm asking for.

[stray reef]

do you do programming

in any capacity

[mint salmon]

yeah

[stray reef]

statements are basically expressions of type boolean

they're things that can be true or false

2k+1 is not one of those

if k is natural, then 2k+1 is also a natura number, not a bool

[mint salmon]

that is very insightful

and helpful

thank you!

[stray reef]

glad i was able to make use of this

[cerulean ore]

@reef thistle Trying to learn Trees, please recommend a resource

[reef thistle]

I don't have a specific resource for it

[stray reef]

why would there even be a specific resource for it

[hallow blaze]

hey guyz

[viral merlin]

hi im having trouble with b and c i think the answer to a is {3,4,5,6} but i dont know where to start with the other teo parts

[hallow blaze]

why is he doing 7 * 8 = 56 here?

why is y4=7 not 8

[hallow blaze]

@sour arrow

why is he only doing a modular inverse on 8(mod 11)

[green crystal]

is a^b a binary operation on any set including 0 considering that 0^0 is undefined, or does that not count

[stray reef]

there are some contexts in which 0^0 is defined to be 1 as a means of tidying up edge cases

[clever nacelle]

IS this good?

[deep jewel]

hey I'm just trying to understand this proof I think I get it but just trying to confirm it's true. 100 integers are pigeons and 37 are holes. 100/37 = 2.7 or something which means there is at least one hole which has at least 3 integers that give remainder 37 when you divide them from a 100 but lets just focus on the 2 integers that divide to give 37 as a remainder A which divides 100's remainder = B which divides 100's remainder but these integers are not the same so their difference is a value that divides 37

[sour arrow]

@clever nacelle
It's messy. I like your work up until
a - b = pqn

Next line says a - b = pq
Which is wrong.

Next after says (a - b)/n = pqn/n
Which is true, but not relevant.

Instead, since a - b = pqn and pq is an integer, n|(a - b) like you want.

[clever nacelle]

I ment to do a-b=pqn on that line. If you divide n by both sides. And pq is an integer wouldn't that show n|(a -b). @sour arrow that is why I felt that is relevant

[sour arrow]

The definition of divisibility doesn't have anything to do with division. Remember that n|(a - b) if for some integer k, nk = a - b

That integer is pq here

[clever nacelle]

Ah that makes sense. Thank you

[sour arrow]

Np, sorry to rip it apart lel. The proof works!

[steady kindle]

Hey

Is there a formula to find out the number of minimum spanning trees formed from a (cyclic?) graph?

I couldn't find it on the internet

[pale epoch]

Kirchhoff's theorem?

or some variation thereof

[cerulean ore]

@steady kindle which book are you using to learn graph/trees?

[steady kindle]

Not using any books per se

Professor's notes

@cerulean ore

[cerulean ore]

Wish I had a good professor

[pale epoch]

i would suggest taking a look at "Invitation to Discrete Mathematics". i used it as a supplementary text for my discrete class. it might cover more/other stuff than you need, but there are a few chapters on graphs and one on trees specifically

[steady kindle]

oh alright

might i add the formula our professor gave us?

[steady kindle]

she used the combinations formula

[ (number of edges) C (number of vertices -1 ) ] - (number of cycles in the graph)

now this formula does not hold true for a lot of graphs and i think it might be incorrect

can anyone provide the correct formula?

[mint salmon]

I'm trying to prove M \ (M \ N) = M ∩ N. So far I have this:
M \ (M \ N) = {x | x ∈ M und x ∉ M \ N} = {x | x ∈ M und x ∉ M ∩ N} = {x | x ∈ M ∩ N} = M ∩ N

It seems to me like it isn't quite complete though

ok wait

it's not just incomplete, it's wrong

[lilac pivot]

intersection is associative, so M ∩ (M ∩ N) = (M ∩ M) ∩ N = M ∩ N

[tranquil cargo]

M \ N= {x | x is in M and x is not in N}

negate this

i trhink the mistake is going from x not element to M /N to x is not elment to M intersects N

you have a contradiction there ig

so if x not element M \ N then x is not an element of M or x is an element in N

demorgens

since x is in M

then x must be an element of N

x is in both

x is in M intersects N

qed?

no

now the otherside

@mint salmon

[mint salmon]

yeah upon thinking about it I saw that I was totally wrong

from step 1 on

[tranquil cargo]

yea

do u understand now?

try to

like when writing proofs of those set theory equalities

try tow rite them cleanly as sometimes

the logic can mess you up

write*

[mint salmon]

my new idea is that there should be an equivalent statement to M\N that only uses ∩

[tranquil cargo]

you know what

if you dontr understand this

you can use ( prove it first ig ) this :

A \B = A intersects B'

thats like the same as i said

[mint salmon]

ok that is an interesting thought

but I also don't fully get it.

B' means not B right?

[tranquil cargo]

B complement

yes

[mint salmon]

but can't that mean everything?

[tranquil cargo]

no

if B is the empty set

yes

XD sorry

assume a and b are nonempty

A and B*

[mint salmon]

ah man I want to understand this

this has to be straightforward

[tranquil cargo]

ok

lets use definitions right

we can never go wrong with that

right?

@mint salmon

[mint salmon]

exactly; that's what I'm trying to figure out. I'm not sure which definitions will help me though

I'll start by listing the ones I know: the definitions for ∪, ∩, \ commutativity, associativity, and distributivity

inclusion, "real" inclusion, equality

and I think that's it

[tranquil cargo]

define the operations for me

[mint salmon]

so based on the definition of \ I could write
M \ (M \ N) = {x | x ∈ M } \ {x | x ∈ M and x ∉ N}

[tranquil cargo]

use refrence from your texbook

A\B = { x | x is in A and x is not in B}

so M \ (M\N) = { x | x is in M and x is not in (M\N)}

= { x | x is in M and (x is not in M or x is in N) }

[mint salmon]

ok wait

that's one of the logical manipulations right?

[tranquil cargo]

yea demorgens law

not(P and Q) = notP or notQ

so M\N is x in M and x is not in N

negate this

[mint salmon]

man that is exactly what I need

[tranquil cargo]

you get x not in M or x is in N

ayy

[mint salmon]

ok now I need to try to apply this

[tranquil cargo]

yea

[mint salmon]

Now I also understand what you said before about A \ B being equivalent to A ∩ B'

[tranquil cargo]

yea

anything else?

[mint salmon]

heh. I don't doubt it, but I'm gonna get back to studying and trying to write the proofs. for now you've helped me figure it out

[tranquil cargo]

sure

if anything just ask

gl

[mint salmon]

👌 thanks

[mint salmon]

@tranquil cargo so now I have a different problem. it's clear after applying de Morgan's law that you get the definition of the intersection. but how do you "remove" the x not in M from the statement? it seems incomplete if I just write this:
M \ (M \ N) = {x | x ∈ M ∧ x ∉ (M \ N)} = {x | x ∈ M ∧ (x ∉ M ∨ x ∈ N)} = {x | x ∈ M ∧ x ∈ n} = M ∩ N

[tranquil cargo]

it seems complete to me tbh

do an argument

x is not in M or x is in N

x is in M

?

or try to distribute

the proposition

on line 3

you get a contradiction or a statment

statement*

which is the statement you got

x in M and x in N

[mint salmon]

ok! the distributive property also works like that for proofs? sweet action. so (x ∈ M ∧ (x ∉ M ∨ x ∈ N)) = (x ∈ M ∧ x ∉ M) v (x ∈ M ∧ x ∈ N) and the first term just cancels

[tranquil cargo]

no

mistake on the algebra

(x ∈ M ∧ (x ∉ M ∨ x ∈ N)) != (x ∈ M ∧ x ∉ M) ∧ (x ∈ M ∧ x ∈ N)

[mint salmon]

wait, I used the wrong arrow

[tranquil cargo]

yes

(x ∈ M ∧ (x ∉ M ∨ x ∈ N)) = (x ∈ M ∧ x ∉ M) V (x ∈ M ∧ x ∈ N)

P and not P is false

so your left with x is in M and xs is in N

got it ?

[mint salmon]

yep

[tranquil cargo]

cool

anything else?

what class is this

anyways

may i ask

[lilac pivot]

M ∩ (M ∩ N')' = M ∩ (M' ∪ N'') = (M ∩ M') ∪ (M ∩ N'') = ∅ ∪ (M ∩ N'') = M ∩ N

you can manipulate it like this

[tranquil cargo]

yea ^

better

[mint salmon]

it's called Mathematik für die Informatik A, which just means that it's the intro to math for computer science

in case you guys don't speak german ^ :P

but I also have a book called Axioms and Set Theory by Robert André to help with reference since German isn't my mother language

[tranquil cargo]

yea

if you have problem with anything just asklk

hopefully i can help

[summer niche]

Show that the set of Complex numbers C has the same cardinality as R, the set of real numbers

Any ideas?

[west hedge]

still stuck? @summer niche

[summer niche]

Yep

Lol

[reef thistle]

@summer niche create a bijection

[summer niche]

Alright

Ty

[drowsy shore]

Hello guys i have this exercise thats i've been stuck on for the past 2 days pls help if u know what to do

We say that a Turing machine M is a composition of Turing machines M1 and M2,
and write:
M = M1 & M2
if, for every input x, M produces the same result or output as the one that results when
M1 is first run on input x, and then M2 is run on the output of M1 as input. Or put
more simply, when M always produces the same output as M1 “followed by” M2.

Question a)
Formulate the Turing machine composition problem (the problem of deciding
whether, when given three machines as input, the first is a composition of the
remaining two) as a formal language.

Question b)
Prove that the Turing machine composition problem is undecidable. Your proof
should be complete – i.e. include the proof that the reduction algorithm exists, by
describing that algorithm in sufficient detail.

[reef thistle]

a) Your input is M1, M2, M3

you can always encode your turing machine... and it shouldn't be a problem making it a formal language

b) Same idea as the halting problem, probably you want to stuff the turing machine that decides it as part of the input

@drowsy shore

[woeful kraken]

The input is M1, M2, M3 no ?

[reef thistle]

where is M3?

ah okay

[woeful kraken]

and the mechine decides Yes or No if M1 is gives same inputs as M2 & M3

[reef thistle]

it's the composition you need to prove yeah

[woeful kraken]

*output

[reef thistle]

Maybe let's call it M instead of M3

[woeful kraken]

1. Lets say we have a trouring mechine S that decides the problem.
2. we create a tm_1 that is any tm and input v that is any input
3. we make M1 run tm_1 on v and then reject
4. M2 and M3 reject everything
   Then we can decide the halting problem with tm_1 and v wich make S undecidable

Does this make sense @reef thistle

[reef thistle]

Think about turing machines as resulting in tape instead of accepting/rejecting

but yeah that idea should work

[woeful kraken]

what if M1 return "11" . M2 and M3 returns "1" no matter input

[reef thistle]

M1 cleans the tape and does tm_1, then returns "1"

[woeful kraken]

ok and M2 cleans and return empty and M3 return "1"?

[reef thistle]

M2 can return anything, which is fed to M3

the outputs are not concatenated

[woeful kraken]

ah ye u right

Thank so much buddy

[drowsy shore]

ahh i seee thank you guys so much :))

[clever nacelle]

This seems too big and like I am doing something wrong. Can someone help me with the correct way to solve this. I feel like I can break it down more

The first problem can be done without a calculator for the most part, the second one in theory, should be the same.

[obtuse lance]

since the remainder is a number from 0 to 6 when dividing by 7, you can reduce 31 down first since 31 = 3 mod 7

also have you learned fermat's little theorem?

[clever nacelle]

I have not, but I can review it and use it.

As long as it is covered in our textbook

[obtuse lance]

well, when you're looking mod p, with p a prime number, it simplifies things pretty well

$x^{p-1} \equiv 1 \mod p$

[vital dew]

Merosity:

[obtuse lance]

as long as x is not divisible by p

so you can effectively throw away multiples of p-1 in the exponent now, or more officially look at 65 mod 6 and use that result as the exponent

I'd be surprised if fermat's little theorem isn't in your book unless maybe your book uses the more general euler's theorem

[clever nacelle]

Just found it and I am reviewing it, seeing if I can understand how you got to 65 mod 6

why would my p be 6 and not 7?

[obtuse lance]

it isn't, it's the exponent that we're looking at

I'll rewrite it in a suggestive way

$x^{p-1} \equiv x^0 \mod p$

[vital dew]

Merosity:

[obtuse lance]

since x^0=1

your exponent was 65 so we can reduce it down by noticing all multiples of p-1 don't actually matter

for instance

$x^9 \equiv x^{6+3} \equiv x^6 * x^3 \equiv 1*x^3 \equiv x^3 \mod 7$

[vital dew]

Merosity:

[obtuse lance]

maybe that helps to see written out?

so here cause I picked the exponent as 9 I can look mod p-1 and turn 9 into 3

[clever nacelle]

I think I understand, let me run with it and see what I end up getting.

[clever nacelle]

This is what I got

remainder = 5

[obtuse lance]

yeah looks good

[clever nacelle]

Thank you very much! That was awesome explaining, and help.

[obtuse lance]

cool have fun

[river plover]

need a recurrence for the closed form $2n^2 + n$

[vital dew]

Da Storyteller:

[summer gull]

Can someone help me with this specific problem? I have a few more CE Method questions (Characteristic Equation Method), but I'm just confused on how to tackle this. Any help would be appreciated!

[summer gull]

Anyone?

[river plover]

@summer gull try your chances in #❓how-to-get-help

[summer gull]

will do, thanks

[weary tiger]

here is the question and here is the solution

question, why can one dish repeat itself?

and why is it 9 factorial * 7 factorial?

is it 7 factorial beings there is one less dish to pick from each day?

[pale epoch]

are you sure there is no information missing on this question

[weary tiger]

none

[clever nacelle]

Can I please get help with the next steps or where I went wrong

[clever nacelle]

I realize the 89-1 is 88, and I can get 2^88=1mod89 using Fermat’s Little Theorem. And I notice a pattern between 88 and 44, but I do not know if this pattern is relevant(44 is half of 88, and also both are divisible by 11) or 2

[plain prairie]

@clever nacelle er

[clever nacelle]

?

[plain prairie]

what is the problem

you said

you have 2^88 = 1 mod 89

[clever nacelle]

Oh my god wait

Oh okay

[plain prairie]

2^88 = (2^44)^2

= 1^2

= 1

?

[clever nacelle]

Yep... wow. I was way overthinking

Not even sure what I was trying to do

[plain prairie]

well

what i wrote

was a little dumb

but you get the idea

[faint narwhal]

That

[plain prairie]

you know that (2^44)^2 = 1 mod 89

[faint narwhal]

is not right

[plain prairie]

yes

which is what i just said

i ready it backwards or something i think

[faint narwhal]

2^44 could be -1 mod 89

[plain prairie]

yes

[clever nacelle]

How could it be -1?

[plain prairie]

because it's something squared

= 1

this can be 1

or -1

but

the work you have in the screenshot

would be a fine way to do it

actually hm

mod 89 the powers of 2 are pretty bad

[clever nacelle]

@plain prairie

[plain prairie]

hm?

[clever nacelle]

How do I know that 2^44 is 1 ?

[plain prairie]

well you can get that 2^44 = 1 or 2^44 = -1 mod 89

since this is an integral domain you know that

[clever nacelle]

If it could be -1 mod 89, wouldnt I need to prove it is infact not that?

[plain prairie]

yes

you would

but im wondering if this is any easier than just showing it's = 1

hm

[faint narwhal]

I'm not sure there's really any easier solution

[plain prairie]

yeah

[faint narwhal]

Other than just seeing that 2^11 is 1 mod 89

[plain prairie]

that's a bit annoying

@faint narwhal it makes fermats useless

like why are the moduli here both prime?

you could've picked a pretty random digit

and done "just see 2^11 is 1"

[summer gull]

Would the big Oh complexity of 7^log2n + 1 + log2n(n^2) be O(7^log2n)? is that a valid Big Oh?

because that would be O(7^n), where n is log2n?

log base 2 of n

[pale epoch]

i mean any function is a valid big oh

but notice that $7^{\log_2n} = 7^{\frac{\log_7n}{\log_72}} = n^{\frac{1}{\log_72}}$

[vital dew]

Lochverstärker:

[pale epoch]

@summer gull

[clever nacelle]

Can someone please verify these for me?

@faint narwhal does this look right to you?

[sour arrow]

You have the easy result from the little theorem:
4^6 = 1 (mod 7)
4^48 = 1 (mod 7)
4^50 = 2 (mod 7)

[clever nacelle]

Not allowed to use it I guess.

[sour arrow]

Oh that's too bad

[clever nacelle]

Professor said we have not learned it yet, even though it is in our textbook in our required reading 🙂

[sour arrow]

You could always just use it "without using it"

Actually, it looks like you did on the second part

[static pagoda]

how many strings are there of lowercase letters of length for or less not counting the empty string?

i know the answer is 475254

but our teacher wants it in nCr/nPr form

not sure how to do that

[faint narwhal]

well how did you get that number

[static pagoda]

26^4+26^3+26^2+26

@faint narwhal

[torpid cliff]

I wonder the same^

[plain prairie]

@static pagoda for nCr length 4 strings that's like asking how many ways can you choose 4 things from 26

This won't count strings like aaaa though

You could do like (n + k - 1 C k)

But I don't think that gives you what you want either

The issue is that 26^4 is just a very simple , straightforward and clean expression for it

And idk why you would want to "write it as a combination" or if there even us a non-contrived way to do so

[floral wind]

Hey so I'm trying to understand how to calculate huge exponents their mod

for example 64^531 mod 121

How would I go about calculating something that big

by hand

I understnad that i have to split the exponent into like the binary factors

so 2 ^ 9, ... etc

but I don't know how to calculate those mods still cause 64 ^ 2 ^ 9 is still fucking huge

[stray reef]

$64^{2^9} = ((((((((64^2)^2)^2)^2)^2)^2)^2)^2)^2$

[vital dew]

Ann:

[stray reef]

@floral wind

[floral wind]

yes no i get that

[stray reef]

well

[floral wind]

oh so you just do

[stray reef]

calculate 64^2

[floral wind]

64 ^ 2 mod 121

then square it

mod 121

square, mod 121

[stray reef]

yes, repeated squaring

you'll get 64^2^k for k=1 and k=4 along the way too

[floral wind]

yeah ofc

thanks a bunch

[static ivy]

hey guys, sorry in advance if this is the wrong channel, i recently started learning combinatorics and there is a concept i cant get the grasp of

ill give an example

lets say i am required to place n rooks on a nxn sized board and the rooks cant be be threatening eachother

(meaning 2 rooks cant be on the same row/col)

the way i looked into it was

looking at my n rows

and saying ok

in the first row

i have n cols to choose from

in the second row n-1 cols to choose from

and so on

that gets me a final answer of n!

however

i dont understand if this has anything to do with them being identical rooks, or unique ones

and if they are identical, am i counting duplicates?

thanks in advance to anyone who can take the time to explain this to the noob i am

[stray reef]

that's correct the number of ways is indeed n!

if they're identical

if they're all unique then it's n!^2 to account for the ways to arrange them color-wise

[static ivy]

ohk

thanks a lot

[static pagoda]

@plain prairie ya i tried a 100 ways and didnt get it ao im really not sure

Maybe i just misunderstood the instructions

[gusty thorn]

if I let set A = {1, 2, 3}

is {} ⊆ A ?

or rather, I was reading this:

and was confused what the point of saying "ε ∈/ Σ" was

[faint narwhal]

Well I mean

You can't really do the inductive part without anything to start with

[gusty thorn]

but Σ is set of elements and Σ* is set of sets, so if ε is part of Σ, it can't be part of Σ, can it...?

i feel like i'm unconsciously assuming something i shouldn't

[faint narwhal]

how do you know that Σ* is a set of sets

[gusty thorn]

the set of strings over Σ (denoted Σ*)

[faint narwhal]

strings are not sets

[gusty thorn]

but doesn't strings mean set of alphabets here?

oh i'm assuming this

oh shoot ahh I see

so string is an element too, of Σ*?

[static ivy]

how many ways are there to arrange 10 books so that 2 specific ones of them are not on the edge

my approach is

all possible ways to arrange 10 books on a shelf - the case where none of these 2 are on the edge

but i cant seem to compute that case where none are on the edge

[floral wind]

Hey so I'm trying to verify RSA signatures, but im having issues with a modulo operation

How would I calculate

$ 3 = (11351 ^ (11)) mod 41449 $

[vital dew]

JohnkaS:

[floral wind]

ok well yall get what im trying to do this is weird

[vital dew]

JY1853:

[floral wind]

yes

it can be false, though

@drifting arrow

[elder cliff]

Could someone explain to me why ii is recursively enumerable and not context free?

[stray reef]

what are your defns of "recursively enumerable language" and "context free language"

[floral wind]

How would you prove that m * n is equal for any m or n in N

[stray reef]

prove m * n is equal to what

[floral wind]

is even*

fuck

not equzl

[faint narwhal]

Do you think this is true?

[floral wind]

yes it is

or well

1 of them is even at least

[robust mango]

no its not. if you take m = 3, and n =3, then its odd

just an example

[floral wind]

nono at least m or n is even

that's a given

forgot to mention that

[pale epoch]

use the definition of even number

[floral wind]

any uneven number + 1?

or any two even or uneven numbers added up?

which oen

[robust mango]

can you repeat the question

full question 😛

[floral wind]

Let m ∈ Z and n ∈ Z. Prove that if the product mn is even, then either m is even, or n is even (or both).

[robust mango]

ah

[faint narwhal]

that is really not even close to what you said

[robust mango]

haha

you can write it as : p implies q

[floral wind]

oh nvm i actually misread

[robust mango]

ive done this before, i can solve if you want?

[floral wind]

rather explain how to

[robust mango]

listen

[faint narwhal]

Don't just solve it for him

That really doesn't teach him anything

[robust mango]

yes

sorry

[floral wind]

should i use the definition of an even number

[faint narwhal]

Really just think about the definition of even

That's all you need here

[floral wind]

where for any even number there is a k for which 2k is that even number?

[stray reef]

bad wording but yes

[robust mango]

@floral wind I think it will be easier if you prove it by contraposition, if you know what it is?

p implies q is the equivalent of ~q implies ~p

it will be easier that way because now you have m or n individually to work with, whereas working with mn as a whole is hard imo.

[floral wind]

i did by contradiction

// even definition here
let m = 2k + 1
let n = 2l + 1

m * n = (2k + 1)(2l + 1)  = 
4kl + 2l + 2k + 1

4kl + 2l + 2k is even by definition

any even number + 1 is uneven by the definition of an uneven number.

So m * n would be uneven for m and n is uneven

for any other case either m, n or both are even```

[stray reef]

odd

it's not "uneven", it's "odd"

[floral wind]

my bad

in dutch it's uneven

and i just translated it directly

[faint narwhal]

This isn't contradiction

This is showing the contrapositive

[static ivy]

question in combinatorics:

how many ways to arrange 10 books on a shelf such that at least one of two books A and B are on the edge?```

[stray reef]

count the arrangements w/o restrictions
count the arrangements that place neither A nor B on either edge

subtract

[static ivy]

o yea havnt thought of that

however i did think of simply considering the 2 different scenarios

but im unsure of my answer

could you tell me if this looks correct?

the arrangement where exaclty one of them is on the side : 2 options in the first slot * 9! for the rest of the slots * 2 (since for any arrangement it could be on the other edge instead of the left side)

• the arrangement where 2 of them are on the edge:

2 options for the first slot * 8! for the other 8 slots in the middle * 1(1 remaining out of the 2 books)

it is now clear to me that they method you suggested is fairly easier than this

but i hope to be able to understand this method for the sake of it

[mint salmon]

are the definitions of ⊆ and ∩ enough to prove this statement: C ⊆ A ∩ B? That is, C ⊆ A ∩ B is true when for every x ∈ C, x ∈ A ∩ B is also true. and x ∈ A ∩ B is true when x ∈ A and x ∈ B are also true

My intuition tells me that it should be enough, but maybe there's another step or something?

[gleaming herald]

https://prnt.sc/psv5ok
https://prnt.sc/psv5u4
https://prnt.sc/psv5ye

I have these 3 questions left on my homework, not sure how to do them

[stray reef]

are the definitions of ⊆ and ∩ enough to prove this statement: C ⊆ A ∩ B? That is, C ⊆ A ∩ B is true when for every x ∈ C, x ∈ A ∩ B is also true. and x ∈ A ∩ B is true when x ∈ A and x ∈ B are also true
My intuition tells me that it should be enough, but maybe there's another step or something?
what are A, B and C?

[viral merlin]

i don't quite understand how to go about these questions, any help would be appreciated!

[gleaming herald]

@stray reef any chance you know about the graph theory questions I posted?

[stray reef]

don't ping me personally

i'm not even a helper ffs

[gleaming herald]

Ok thanks

Really helpful

Have a great day

Just say yes or no what is so complicated

[faint narwhal]

You're joking right

She has to read through all your questions

And obviously if she says yes that means she'll help you

[pale epoch]

honestly you can solve all your questions by trial and error even

for the last question there is some theorem you can use, if you covered it

although trial and error will work fine

[mint salmon]

A, B, and C are non empty sets

The example solution has the two definitions switched. Does that make a difference? Based on this, my wording definitely isn't clear enough though.

[errant bear]

can someone explain why going from a S to T, with cardinalitys 3 and 2, how the number of injections is higher, 9, than the number of functions, 8

like where does the extra thing come from

[errant bear]

thats not even worth asking

u know atleast 2, cuz 6 x 8 and 2x6x8

and 6 and 8 share a common factor so there must be more

huh

and the answer is obvious

u telling me you dont know which is right lmao

bruh

moment

[sour arrow]

24 is divisible by 6 and 8 because
24/6 = 4
24/8 = 3

[errant bear]

kaynex can u help me pls

[sour arrow]

What's up?

[errant bear]

can someone explain why going from a S to T, with cardinalitys 3 and 2, how the number of injections is higher, 9, than the number of functions, 8
like where does the extra thing come from

i understand the functions, but not injections in this case

[sour arrow]

An injection is a function. It's not possible to have more injections than functions

There are no injections from a larger set to a smaller

[errant bear]

wait, so would the num of injections from S to T be 0? as atleast one element of S will get mapped to the same element in T, because theres only 2?

and that makes sense i must have read it wrong

[sour arrow]

Yup!

[errant bear]

but from T to S will be 9

or wait it could be 6

[sour arrow]

You've proven an important fact. If you can construct an injection from A to B, then
|A| ≤ |B|

[errant bear]

oh yeah thats in my notes

hmm now surections

[errant bear]

can anyone help with the union/intersection of two functions

[faint narwhal]

[errant bear]

ok this is the like setting

so in order to show (a), would i just have to show that since a in A is always different from c in C, and due to injectivity that their images are different?

[faint narwhal]

uh

due to injectivity? Where does it say anything about injectivity?

[errant bear]

i mean like, because they are different domains, then their mappings are different

wait thats not true tho

i have no idea

i hate functions

[faint narwhal]

Well what does this problem actually need you to do

[errant bear]

to show that the union of f and g is the function that maps A U C to B U D, using the fact that A and C are disjoint

[faint narwhal]

is the function? How do you know its a function?

[errant bear]

is that not what : and the arrow mean

isnt : defining the function

[faint narwhal]

Yeah it's written pretty poorly honestly

But from the discussion at the start of the problem

The problem only really wants you to show that it actually is a function

It's not too hard to see that the domain of this function is (A U C) and the codomain is (B U D) so

[errant bear]

i agree

but idk what the connection is

[faint narwhal]

What do you mean

[errant bear]

like how do i show that its a function lol

am i just supposed to union the domains and cos?

[faint narwhal]

How do you know when something is a function

[errant bear]

for all a in A there is a unique b in B

[faint narwhal]

what

[errant bear]

from A to B

like every member of the domain has exactly 1 corresponding member in the codomain

[faint narwhal]

Okay

So you need to show that this is a function

[errant bear]

yeah so i need to show that for each member of A U C, there exists a member in B U D

[faint narwhal]

unique member yep

[errant bear]

but couldnt B be equal to D, or have shared elements

[faint narwhal]

It could

[errant bear]

wouldnt that disprove it being a function

[faint narwhal]

Why?

[errant bear]

wait no just injectivity right

functions dont care ab same output, just that input has to have only 1 output

[faint narwhal]

Right

It's injectivity that cares about the outputs being different

[errant bear]

ok gimme a couple to try and solve it

[faint narwhal]

Good luck

[errant bear]

which areas of math, like careers/focuses use functions/sets a lot