discrete-math

[coral parcel]

For the same reason you'll also see it used for the analogous operation in other Boolean algebras -- e.g. binary XOR on integers in cryptography.

[little prism]

Is that actually useful for more than just an exercise in ring theory?

[coral parcel]

Well, for one thing it explains why an "ideal" in a Boolean algebra is called what it is ... and those ideals show up in a fair number of places in (at least) foundation-ish contexts.

[coral parcel]

And (symmetric) cryptography makes a lot of use of the fact that the operations on integers that general-purpose hardware commonly provides fit together in two ring structures. Cryptanalysis often involves a lot of linear algebra done over one or both rings, which you have to be aware of when designing algorithms that resist cryptanalysis.

[tidal tulip]

can i get a proof check

prove if u is a unit of M, then for all a,b in M, the equality au=bu implies a=b.

suppose u is a identity of M, and let a, b be in M.

from the expression au=bu, let's consider the identity on the left hand side of the expression. then we have that u is a right-sided identity on a and:

we have au=bu -> au=a

similarly, let's consider the identity on the right hand side of the expression. then we have that u is a right-sided identity on b and:

we have au=bu -> b=bu, using symmetry of equality we have bu=b

thus from au=bu, au=a, bu=b

using trans we and see:

au=bu -> a=bu -> a=b

QED

[little prism]

Do you mean unit as in invertible element in a ring?

If yes, just multiply by u^(-1) from the right

[tidal tulip]

The book says "a binary operation *: X x X -> X is said to be unital if there exist a fixed element e in X such that for all x in X we have e * x = x and x * e = x."

[little prism]

Well that's different

An element being a unit is different from an operation being unital

[tidal tulip]

so is my proof correct just i need to change the terms "unit" to "unital"?

[little prism]

Well an operation can be unital, not sure what you mean by an element being unital

An element like that e there I would call identity

[tidal tulip]

i think they mean identity yeah

[little prism]

Or neutral

[tidal tulip]

i edited the proof

see if that is correct

changed unit to identity

idk im confused

[little prism]

Then it's fine. But pretty long

a=au=bu=b. Done

[tidal tulip]

that was short haha

[little prism]

You did nothing wrong by stating everything clearly but sometimes stuff gets too long you know

[tidal tulip]

okay, great ty. this is my exposure to these sort of proofs so it was more for myself

writing all that out just to be sure i understood every step

[little prism]

Yes thats completely fine

[tidal tulip]

awesome, thanks for checking

[little prism]

But it's a good idea after you proved something to take a step back and see how you can shorten the proof

[tidal tulip]

like i wasnt sure if i could use "symmetry of equality"

but it made sense to do it

[little prism]

Where did you ramble on for too long or where did you do something useless etc

[tidal tulip]

this is good advice

[little prism]

The first time you prove something it will never be a nice perfect proof. Look at what you did and see where you can improve the presentation

[tidal tulip]

will do

[little prism]

What where the essential steps. What was unnecessary. Etc

[tidal tulip]

the next question is If "M is a finite monoid and uv=1 in M, prove that vu=1. -- so I assume "finite monoid" just means a monoid (X,*) has a finite number of elements in it and i assume given a specfic fixed u,v in M that uv=1 (the identity). is that correct?

[little prism]

Yes

[tidal tulip]

so u,v aren't arbitrary

[little prism]

No

[tidal tulip]

k

[bronze forge]

Hello everyone, I have a question where I am stuck on, its regarding combinatorial number specially replacement without orderign

here is the problem

[little prism]

stars and bars

[pearl hull]

I am so stuck doing this one,

[bronze forge]

ty 🙂 thats what i started with but im lost when it come to prove the inequality

[stray reef]

@pearl hull have you made any progress so far?

[pearl hull]

Nope, So freaking difficult

Tried using symbolab but nope

[stray reef]

do you know / have you been taught how to find the inverse of a matrix?

[pearl hull]

I skipped a couple of classes, soo nope

[stray reef]

well you will have to learn that then

[pearl hull]

Dang, imma use khan academy

[stray reef]

abbreviating all explicitly written matrices to letters, your equation has the form AX + B = C

[steel hornet]

Super quick question, I'm learning about sets

What does the p / q mean?

[stray reef]

it means p divided by q

[steel hornet]

what

[stray reef]

@pearl hull from here subtract B from both sides to get AX = C-B and left-multiply by the inverse of A to get X = A^-1(C-B)

@steel hornet what?

[pearl hull]

Oh ok

Thanks

You rule

[steel hornet]

ooh nevermind

i thought it was something special

[coral parcel]

$$\binom{a}{b} = \frac{a(a-1)\cdots(a-b+1)}{b(b-1)\cdots 1} = \frac{a}{b}\cdot \frac{a-1}{b-1} \cdots \frac{a-b-1}1 \ge \Bigl(\frac{a}{b}\Bigr)^b$$

[vital dew]

Troposphere

[bronze forge]

Thanks ill look into it rn

[woeful copper]

I hate discrete math so much man

[fair ember]

is 7x + 2 mod 7 the same as 7x ≡ 2 mod 7

[stray reef]

no

highly suspect you have confused yourself w/ notation a lot

[fair ember]

you dont have to give me the answer but how would I solve this?

its not in my book and cant find it on the internet

[stray reef]

can you show the entire problem

[fair ember]

it says 7x + 2 mod 7 where x is a set in positive integers

[stray reef]

show don't tell

give us a picture or screenshot

[fair ember]

lol its in icelandic

[stray reef]

show it anyway

[fair ember]

sure

þar sem is basically where

[stray reef]

this is part c of a problem

can you show parts a and b and the instructions before them?

[fair ember]

yeah np

the instructions are basically "solve the problems"

[stray reef]

bruh

well ok now we know it's the question that's worded in the least helpful way possible...

ig part c is like "What remainder does 7x+2 give mod 7, where x is a positive integer?"

[fair ember]

yeah I dont know the formula though

[stray reef]

better to refrain from what's-the-formula-ism

if you know a thing or two about modular arithmetic this is pretty clear

7x is a multiple of 7 and so gives 0 as the remainder, and 2 is just 2

[fair ember]

7(0) + 2 mod 7

how do you like the language though?

[stray reef]

what do you mean?

[fair ember]

we are just beginning to learn modular arithmetic, its not that clear to me. But the assignment isint due yet just trying to figure this out

[fair ember]

people that dont understand icelandic say its the weirdest language to hear, so I was wondering what your first thought was when you read the text

[stray reef]

well i'm looking at written icelandic rather than spoken

and i have a passing familiarity with icelandic spelling

so it does not really strike me as odd

[fair ember]

nice

[golden edge]

What would be a necessary and sufficient condition for g to be bijective ?

F is included in E

[little prism]

it would need to be surjective. so every subset of E needs to be an output of g. as g "makes sets bigger", what it a good subset to consider for this?

[golden edge]

F would have to be the empty set right, if not you could never "generate it" with the function and therefore it wouldn't be surjective

[little prism]

yes

[sudden topaz]

Can any body solve this problem related to set theory?

https://math.stackexchange.com/q/4539512/1090038

[trim roost]

SOMEBODY HELP ME

IM CRYING

PLEASE

RAJHHHHHHHHH 😭

I STARTED MAKING CRAZY STUFF

pls

help

me

[flint harness]

How come they use multiplication? I thought the E kind of symbol was just summation/addition? 😒

[brave rock]

It's capital Sigma, like S for Sum.

For what it's worth, this is just a typo.

They meant $x = \sum_{i=1}^b x_i 2^{i-1}$.

[vital dew]

Boytjie

[autumn oyster]

hello

i need help

[vale cairn]

[autumn oyster]

What is the contrapositives of this statement: Let a, b, c ∈ Z. If a|b and a|c, then a|(b + c).

[weary tiger]

Can you state the law of contraposition?

[autumn oyster]

basically what is the opposite

which is equal to the orighinal statment

[weary tiger]

Well yes, so if you have a sentence "if p then q", what would its contrapositio be?

[autumn oyster]

not q then not p

[weary tiger]

Exactly, just think how you can choose p ad q to fit the statement and think what their negations are.

[autumn oyster]

so would it be if a does not divide (b+c) then b does not divide a and c does not divide a ?

[weary tiger]

Not quite, the second one is wrong.

Negation of "p and q" is not "not p and not q"

[autumn oyster]

is it is p and is q>

[weary tiger]

If I say "I will buy milk and eggs", then if I buy only one I will be lying. So negation of "p and q" is "not p or not q".

[autumn oyster]

wait what does negation mean i thought it just means the opposite

[weary tiger]

Well yes, but the opposite of p and q is not 'not p and not q'.

Negation of statement A means that it has 'oppoiste truth values'

[boreal plume]

https://i.imgur.com/sbcaoX8.png

[weary tiger]

This channel is taken

Move elsewhere

[boreal plume]

what does it mean by total functions?

oh is this a discrete channel?

[autumn oyster]

list all subset of x and y combine i think?

but any way so it woud be not a dive b or a doesnt divide c

[weary tiger]

Yeah, a doesnt divide b or a doesnt divide c.

[boreal plume]

hmm i was not able to find an explanation in my text book on solving this

[weary tiger]

It's worth to maybe draw a truth table for both of those statements - the one above and the one you thought intially: "not p and not q"

[weary tiger]

They probably just mean find all functions.

That's my guess at least

[autumn oyster]

Thank you ver much have a bless day!!

[thorn lake]

does anyone know anywebsites that offer questions for discrete math

like some questions about listening functions in set builder notation

or finding the factoral of a number

[autumn oyster]

Would the contrapositive of Let a, b ∈ Z and n ∈ N \ {0}. If a ≡ b (mod n), then a^3 ≡ b^3(mod n). be If a^ 3 not ≡ b^3( mod n) then a ≡ b (mod n)

[lean rover]

Can someone help me with a cardinality question

How do I find a bijection between Z+ x R = R

[coral parcel]

Can you use Cantor-Schröder-Bernstein to smooth over some gaps, or do you need a completely explicit one?

[remote crane]

On R, if we define a relation a~b if a-b is an integer, why is this quotient space a circle?

[coral parcel]

Show that a-b is in integer if and only if (cos(2pi·a),sin(2pi·a)) = (cos(2pi·b),sin(2pi·b))

[signal goblet]

My professor asked me a question today in class, and I wasn't too sure on the answer. After some thought (after class), I'm still not too sure. The question is basically this:

If we have a language L that is accepted by a DFA with n states, then why is it that either L = the empty language or there is a string w ∈ L such that |w| < n.

Could anyone help explain the intuition behind it?

[coral parcel]

Either there's no accepting state that's reachable or there is. If it is reachable, then it can't take n or more transitions to reach it in the fastest way.

[rapid mural]

TeX

[woeful scroll]

hi guys, is there anybody use NN did some QUBO loss function tuning?

or may be use NN optimize some interger programming loss function? or maybe use NN handle some relaxation.. something like that

want to listen to some experience, omg

[ebon quest]

if a binary tree with n nodes has ONLY 1 external node, would the height be 0 or 1?

[opal gorge]

so OR is $\lor$, and AND is $\land$. Meanwhile, in circuit, OR is denoted as $+$, and AND is omitted denotation of $\cross$. Does it hold the same meaning and property of addition and multiplication or it's just notation?

[vital dew]

Darkness

[halcyon sand]

hey peeps i was wondering since the empty set can't be a proper subset of itself

{∅}⊂{{∅},{∅}}

This wouldn't be true right?

[signal goblet]

Oh lol, that makes sense. Thank you

[rapid mural]

The second one is a set, but you should remove the duplicate to make it clearer (edited due to mistake)

Sets have to contain unique elements

[halcyon sand]

{∅}⊂{{∅}}

The brackets really have me confused

[rapid mural]

Correct that will not be a proper subset

It'd be \subseteq

[halcyon sand]

What if we were to put {{∅}}⊂{{∅}}

[rapid mural]

That's the same as asking {a} \subset {a}

It's not a proper subset

[halcyon sand]

Ahhh

Thank you so much!

[brave rock]

newpx package. It’s a palatino clone

[cerulean wind]

it’s a set. it’s equal to {{emptyset}}. just because it’s written with dups doesn’t mean it’s not a set

[rapid mural]

Sorry poor phrasing

[halcyon sand]

Hey peeps

The Cartesian product of a set and a empty set is always just the empty set correct?

[brave rock]

That's right

[halcyon sand]

so even then for example A x B x ∅

is still = ∅

[brave rock]

Yup

[halcyon sand]

Right?

[halcyon sand]

thanks chief

[halcyon sand]

The power set of an empty set is just the empty set correct?

[little prism]

no

its the set containing the empty set

[vale cairn]

The empty set is a subset of every set and there aren't any other subsets of the empty set

[halcyon sand]

Ahh.

If i were to subtract The power of an empty set what would that be?

P(∅) - ∅

{∅} - ∅ would just be {∅} right?

[grand totem]

Correct 👍

[halcyon sand]

tyty

[heavy rain]

is ∀x∃yQ(x, y) and ∃y∀xQ(x, y) the same thing

its just that they're swapped, the principle is still the same though right

[vale cairn]

No, they can be very different in fact

Maybe I can sketch some informal examples.

[heavy rain]

wait but the symbols are still the same for the x and y though?

like its still any real number x for both of them

and at least one real number y

[vale cairn]

"For every integer, there's an integer bigger than it"

vs "there's an integer bigger than every integer"

Or similarly "Everybody has a friend" vs "There is somebody who is friends with everyone"

[heavy rain]

even though its JUST the places for x and y that are swapped?

[vale cairn]

Yup

[heavy rain]

this is so confusing wait

heres the context

Let Q(x, y) be the statement “x + y = x − y.” If the do-
main for both variables consists of all integers, what are
the truth values?

∀x∃yQ(x, y) and ∃y∀xQ(x, y) have the same solution though?

[vale cairn]

I don't see the connection

[heavy rain]

there does exist at least 1 integer for y and all integers for x that make that statement true

both are asking for at least 1 integer for y

and both are asking for all integers of x

so wouldnt the answer be the same for both questions?

any real number (x) plus the number 0 makes both of those questions true

[vale cairn]

I assumed the question was asking you to find those pairs (X,y) such that Q(X,y) holds

Or are they asking you to find the truth values of like

Forall x exists y Q(X,y) ig

[heavy rain]

the question to my knowledge is just asking for an integer that fits those slots that makes the equation true or false

[vale cairn]

The two are both true here I guess, but not in general

[heavy rain]

is it like in that context its right but in other contexts it might be different

why is discrete math so hard

[vale cairn]

Yeah

The key thing here is that y=0 is allowed I guess

[heavy rain]

im only questioning whether its right or not because like, why would they put that extra question in the textbook

cuz its like a waste of space other than just trying to trick you if you're not paying attention but

i dont think textbooks are meant to try and trick you

[halcyon sand]

Hey guys I wanted to ask

Idk if im being stupid here

is A - B, the same as A ∩ ¬B

[coral parcel]

Yes, assuming A and B are sets, and A - B means set difference, and ¬B means the complement of B, and you're in a situation where sets have complements at all.

[sand halo]

Can I put a quantifer statement for q in a if statement

[golden talon]

Hi can solve question 1

[stray reef]

do you mean "Can someone solve question 1 for me while I put no effort into it myself, because I don't want to do this menial work as I deem it beneath myself?"

or do you mean "I am having trouble with question 1, can somebody help me?"

[golden talon]

I have trouble understanding

[stray reef]

have you seen incidence matrices for graphs before?

[golden talon]

Not really

[stray reef]

do you know what the word "incidence" means in graph theory?

[golden talon]

No I haven’t studied this

[stray reef]

...okay do you at least know what a graph is

[golden talon]

Yes

[stray reef]

okay

alright

so the word "incidence" is a convenient shorthand

when we say "[edge] is incident to [vertex]" we mean that the vertex is one of the edge's endpoints

do you understand what i said just now?

(i'm not done, but i want to ensure you still follow)

[golden talon]

The end points?

[stray reef]

you know how an edge is something that connects two vertices, yes?

[golden talon]

Yes

[stray reef]

yeah

[golden talon]

Okay I understand that

[stray reef]

ok

great

the incidence matrix is a way to summarize in a systematic(ish) fashion the information about a graph

namely, the rows in such a matrix correspond to vertices, and the columns correspond to edges. for each vertex and edge, you put a 1 in the corresponding entry of the matrix if they are incident, and 0 if they are not

do you understand this?

[golden talon]

Ok i got it

Understood

[stray reef]

are you now able to read the incidence matrix given to you and reconstruct the graph from it, or would you like assistance with that?

[golden talon]

I will try

[stray reef]

ok

would you like me to check your result?

[feral mirage]

Some authors refer to the set of nonnegative integers
as the set of natural numbers and denote it as N. Other authors call only the positive
integers natural numbers. To prevent confusion, we simply avoid using the phrase natural
numbers in this book.

Are these not the same definition for natural numbers?!

[brave rock]

Nonnegative includes 0. Positive does not.

[feral mirage]

Oh fair, thanks

0 is included in all sets of Real Numbers right?

nonneg or negative

[brave rock]

If you mean the set of real numbers, yes

No

[feral mirage]

I get Z^nonneg including 0, but then R+ and R- both include 0?

sorry wish I could do the correct notation

[brave rock]

I think R^+ and R^- tend not to be defined to include 0.

[feral mirage]

oh the definition is any non zero number

my bad

according to this book, nonneg is valid notation, does that mean nonpos is also valid?

i.e. If I wanted to include 0 and negatives, I would use nonpos

whereas Z- would be negatives only

[brave rock]

I've never seen the word "nonpositive" used

I doubt you will ever feel the need.

[feral mirage]

I have no idea either, just imagining in proof writing or something

[remote crane]

This is a dumb question, but can I prove two things with induction at the same time/assume two things together?

I want to prove this, and tried to prove each case by itself but I had to assume the other case to get it

like can I show as a base case: $a_3<a_1$ and $a_4>a_2$, and assume that at n=2k, $a_{2k}>a_{2k-2}$and $a_{2k+1}<a_{2k-1}$ for the inductive hypothesis

[vital dew]

Mirinim

[coral parcel]

Yes, you can make the entire (a) be the thing you prove by induction if you get that to work..

[remote crane]

nvm i didn't even have to do that lol

[plucky steppe]

https://gyazo.com/990d7cb4c16bde1f0f108f0304163972 Could someone explain how this problem has the statements of q and r and assigns the reason of modus ponens to them both? also, the numbers after modus ponens, what do they stand for?

[coral parcel]

The numbers refer back to the lines you use as inputs to modus ponens.
In line 4 you use modus ponens on p and p->q, giving q.
In line 5 you use modus ponens on q and q->r, giving r.

[lusty garnet]

hey all, i need to prove the following: Prove by induction that 4^n < n! if n is an integer greater than 8. i did the proof but don't really get the ending.. anyone want to give it a wack?

[vale cairn]

What do you mean by the ending?

I assume you mean the inductive step or part of that?

[lusty garnet]

yeah

like 4^k * (k + 1) < (K+1)!

what happens affter

[vale cairn]

Oh sure

So you need to show that 4^k * (k+1) >= 4^(k+1) to finish up

Do you see why that's the case?

[velvet vine]

Write the domain and range of the following relation: R = {(-3, 5), (-2, 5), (-1, 5), (0, 5), (1, 5), (2, 5)}
Draw the arrow diagrams to represent the relation: R = {(4, 10), (4, 13), (4, 16), (5, 13), (6, 16)}

[rapid mural]

Intuitively, the domain should be the "left" side of the tuples in R

The range follows a similar line of reasoning.

[dense glade]

"P(C ∪ P ∪ V ) = 1" This st. is only correct if and only if P(C u P u V )~ is 0 right?

[hardy pelican]

just a quick question about truth tables:
How do i split this into a truth table ?

[weary tiger]

guys, i am having trouble understanding my teacher's solution here

so are they non-equivalent?

[elder berry]

They have a slight mistake at the end, applying de morgan would get ya not p and not q

rather $\neg (p \lor q) \equiv \neg p \land \neg q$

[vital dew]

peaceGiant

[elder berry]

You start with three columns for p, q and r, after that you can add additional columns for the left side of the equivalence and for the right side, and a final column for the whole expression

Remember you have to alternate the truth values of p, q and r so that each row represents a unique combination of truth values

[weary tiger]

oh thank you!

i was wondering about that

i think i miswrote it

[covert bolt]

hello I would like to ask if B and C are logically equivalent when transformed to boolean expressions

[coral parcel]

There are only 4 different combinations of inputs to each circuit. You can try them one for one and check whether the two circuits always give the same output.

[covert bolt]

yea I tried that but apparently they are not equivalent according to an answer scheme?

shouldnt the p-p NAND gate in B be functionally similar to the p NOT gate in C

my truth table says B and C are equivalent

[coral parcel]

I don't think there are any NAND gates, just AND, OR and NOT. (The large circles seem to just be a way to connect the symbols to the curved connecting lines, not actually negations).

[covert bolt]

they are nand gates doe

I think its just the website

o wait

OH

oh fuck nvm

haha thank you 💀

guess I have to redo my entire truth table now

[coral parcel]

It's fairly horrible symbolism in those diagrams.

[half hare]

Yeah thats bad

[umbral blade]

Are you allowed to put a negation next to a quantifier? For example: It is not true that for all students y

[elder berry]

Yes, but be careful when putting a negation to remember to also negate the formula that succeeds the quantifier.

Ex.

$\neg \forall y P(y) \equiv \exists y \neg P(y)$

[vital dew]

peaceGiant

[coral parcel]

With the often useful variant $$\neg \forall y (Q(y) \to P(y)) \equiv \exists y (Q(y) \land \neg P(y)).$$
Note that the $Q(y)$ \emph{doesn't} get negated in this variant, which preserves more of the intuition when $Q$ says "which $y$s we're interested in at all".

[vital dew]

Troposphere

[umbral blade]

So would this be fine or would I have to add another negation symbol into the formula after the quantifier

[plucky escarp]

hmm idk about u guys but normally we try not to write stuff like
$\lnot \forall$ or $\lnot \exists$

[vital dew]

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

HellO

[light oxide]

I am supposed to pick one of the four option as an answer, No clue where to start ```
Ch 02 Sec 2 Ex 63 (d) - Find Union and Intersection of Sets using Bit Strings

Consider the sets A = {a, b, c, d, e}, B = {b, c, d, g, p, t, v}, C = {c, e, i, o, u, x, y, z}, and D = {d, e, h, i, n, o, t, u, x, y}. Identify how bitwise operations on bit strings can be used to find the combination A ∪ B ∪ C ∪ D.

a) (11 1110 0000 0000 0000 0000 0000 ∧ 01 1100 1000 0000 0100 0101 0000) ∨ (00 1010 0010 0000 1000 0010 0111 ∧ 00 0110 0110 0001 1000 0110 0110)

b) (11 1110 0000 0000 0000 0000 0000 ∨ 01 1100 1000 0000 0100 0101 0000) ∧ 00 1010 0010 0000 1000 0010 0111 ∨ 00 0110 0110 0001 1000 0110 0110

c) 11 1110 0000 0000 0000 0000 0000 ∧ 01 1100 1000 0000 0100 0101 0000 ∧ 00 1010 0010 0000 1000 0010 0111 ∧ 00 0110 0110 0001 1000 0110 0110

d) 11 1110 0000 0000 0000 0000 0000 ∨ 01 1100 1000 0000 0100 0101 0000 ∨ 00 1010 0010 0000 1000 0010 0111 ∨ 00 0110 0110 0001 1000 0110 0110

[stray reef]

these strings appear to have length 26

this might give you a hint as to what needs to be done

[light oxide]

Ty

[glacial flame]

Does divisibility (|) usually have lower precedence than typical mathematical operations (+-*/)?

[stray reef]

it's not an operation at all

[glacial flame]

oh I guess it has a truth value and would only really get wonky when you are mixing CS with it (where t/f is 1/0)

[umbral blade]

How do you prove these types of propositions false where you can’t use one number/example to prove it false?

[distant glade]

assume there does exist such a number and arrive at a contradiction

[blissful bough]

does anyone know how to do this

its my first time doing it and i have no idea how to write the constraints

[sweet thunder]

I’m really lost on how to start this. I feel like once I start I’ll be fine but I don’t even know what it’s asking.

[stray reef]

a-b is divisible by each m_i

[wise venture]

Hi guys, I can't understand what's the question a) is asking , can anyone help me on it?

[elder berry]

How many different 6 letter words (strings) are there? abcdef for example is different to hbcdef

The words are different if two letters differ in the same position of the word

[wise venture]

which means abcdef and bacdef is the same right

[elder berry]

no

let me fix my defn :p

[wise venture]

sure , thanks!

[elder berry]

so if two words are not identical -- like aaaaab has only one word identical to itself (which is itself), then they are different

[wise venture]

so for a) the total will be 26^6

[elder berry]

yup

[wise venture]

and b) is 26C2 x 24C2 (choose two to repeat ,and two which are not )

sry, I have to times 6!/2!2! as well

c) is 26^6 - 26C2 x 24C2 x 6!/2!2!

[elder berry]

this would be the answer if they required # of words essentially different to LETTER, but I don't think that is what the question is asking

[wise venture]

then that should be 26P6 if we consider the every word in 26^6

[elder berry]

I think c) has to do with partitions -- which has no known closed formula. So probably check out question d) and the example that it wants to show

[wise venture]

ok let me think about that

thanks so much!

[spark silo]

how do you draw a shape based on the word representation?

like take for example abc c^-1 b^-1 dea (not sure if thats a valid closed shape example)

is it something like this?
. = dot
. -a-> . -b-> . -c-> . <-c- . <-b- . -d-> . -e-> . -a-> .

but this is a line with different direction/values, right? how do i make a shape out of this?

[coral parcel]

I think you need to explain more context. "The word representation" (of what?) is not a standard term; neither is "a shape based on" such a thing. It's not even clear what you mean by "shape" in the first place.

[spark silo]

oh, well it says draw the "polygon" that this word represents

does that help 🤔

[coral parcel]

No, sorry. I still don't have any idea even which area you're in.

It sounds like you may be following a book that has defined its own private little symbolic language with a geometric interpretation, and is using that as an example to make some general points about .... something.

[spark silo]

lol all good then yeah i cant find anything about it on google but thats all it gives me, just the word input and that its a polygon. ill ask a tutor at some point, thanks

[coral parcel]

Is this perhaps related to group theory? Free or finitely generated groups? Paths in a Cayley graph?

[spark silo]

yeah group theory

i think

[stray reef]

@spark silo show us the entire problem

maybe itll be clearer this way

[spark silo]

i think its just this

[stray reef]

...

are you or are you not looking at a problem statement right now?

[sweet rock]

quick question

u.v = xu.xv +yu.yv

what's u + v

[stray reef]

what are any of these letters supposed to mean

and what does the dot mean

[sweet rock]

-> -> u × v

idk how to use texit with this math

xu is the axis of u

i'm new to these things

wrong channel?

[stray reef]

yes, you're probably in the wrong channel and also making yourself wildly unclear in the process,

but it looks like you are talking about vectors

so i guess #geometry-and-trigonometry is where you should be redirected

[spring elk]

can i get some help with this?

i need to apply altenrative form/principle of strong mathematical induction

[still sky]

n^5 = O(√2^n)

why is this ?

should O be n^5

[unreal stump]

Ok so if n is even , it can obviously be expressed as a sun of 2s.

If n is odd and not 1,3 or 5, (n-5) is a positive even number and so you can express it as a sum of 2s. Now 5 can be represented as 5 alone and you can't represent 1 or 3.

[unreal stump]

Well because
$\lim_{n \to \infty} \frac{n^5}{{\sqrt{2}}^{n}} =0$

[vital dew]

Drake

[unreal stump]

Is there a way to make that power n look good

[unreal stump]

Polynomial functions grow slower than exponential ones. (Can be shown by using l'hospital 's rule)

[still sky]

my god what is that

[still sky]

Calculus

okay

i

understand it in a few years

holy hsit

isn't there

a non-calculus proof

[unreal stump]

https://math.stackexchange.com/a/55488
Kinda uses calc but ig is more readable?

[still sky]

I'll check

Any polynomial grows slower than any exponential: $n^a \prec b^n$ for $a \ge 0, b>1$. Examples: $n^3 \prec 2^n$, $n^{10} \prec 1.1^n$.

[vital dew]

Timothy

[still sky]

WOooo

it worked

in n^a < b^a

aren

they both exponentials

wtf is a polynomial then

[unreal stump]

Functions of the form f(x)=x^n are polynomials

Functions of the form g(x)=n^x are exponential

[still sky]

and in this

"polynomial grows slower

"

[unreal stump]

Both are polynomial tho

[still sky]

EXACTLY

bro

im gonna cry

why

is this so confusing

They are both polynomials right?

[unreal stump]

Yes

[still sky]

ugh

Ohhh

wait

okay i think these were both polynomials

maybe twas a typo

because they later show how they overlap each other as the values get bigger

[spring elk]

so they first made me show that a1 = (a0)^2 and a2 = 2(a0)^3 a3 = 6(a0)^4 and thus the conjecture formula for an would be n!(a0)^(n+1)

so what i tried doing after that is i can assume its true for ak which is k!(a0)^(k+1) but i need to prove it for k+1.

i tried by using the sum so sum of 0 to k-1 which is just ak and then i have remaining aka0 but this doesnt help..

[glacial eagle]

For the second nested loop, I understand what to do.

I used summation formulas like the ones shown from Ochem Tutor.

However, I am stuck on the first nested loop and I don't know where to start.

[elder berry]

Your conjecture is correct and plugging back in into the sum should work. I think you should try it again, and if you're struggling write back

[glacial eagle]

I'm trying to write the algorithm in summation notation so I am able to write the expression in closed form, the closed-form part I will try to figure out myself

[elder berry]

this?

[glacial eagle]

yes

[elder berry]

I assume you want to count how many times "A" appears, so I'll replace "A" with a 1

$\sum_{i=2}^{3n+1} \sum_{j=i+1}^{2i} 1$

[vital dew]

peaceGiant

[elder berry]

is this what you got with sigma notation?

[glacial eagle]

Yeah

[elder berry]

So, how would you evaluate the inner sum?

[glacial eagle]

sorry, give me a second

[elder berry]

take your time

hint: ||we are summing a constant number. the real question is how many times are we summing this number?||

[glacial eagle]

well, i would use constant summation and multiply 2i with 1, but where i am confused is with i = 2 and j = i + 1 lol

[elder berry]

ignore the first sum, we are tackling only the inner sum first

$\sum_{j=i+1}^{2i} 1$

[vital dew]

peaceGiant

[elder berry]

do you know how to perform an index shift by any chance?

[glacial eagle]

i get a general idea, but i kind of forgot 😢

i know i is the index, and it increments in the loop

[elder berry]

no worries, let's not index shift, instead let's think how many times we are adding 1

you start from i+1, i+2, ..., 2i - 1, 2i

in total these are i 1's that you are summing

there are i numbers between i+1 and 2i

do you need convincing that that is true, or not?

[glacial eagle]

no, i understand that

[elder berry]

great, then since you are summing only i 1's, the answer for that sum is i

good?

[glacial eagle]

ohhh

wait, lemme think about it for a second

i might ask another question if i get confused

thanks for this though

[elder berry]

There are i numbers between 1, 2, 3, ..., i
If you add i to all of them, the number of numbers doesn't change, but their values do
so 1, 2, ..., i -> i+1, i+2, ..., 2i

No worries

your sum ends up as $\sum_{i=2}^{3n+1} i$

[vital dew]

peaceGiant

[elder berry]

which I believe you can tackle

[glacial eagle]

oh yes, that is easy to tackle. thanks. XD i was just confused at the very first part you mentioned

[umbral blade]

How do you prove a there exists proposition false?

[elder berry]

which part specifically?

[glacial eagle]

this part, let me send what i got in latex

$\sum{i=2}^{3n+1}2$\

oops

meant to not hit enter lol

$\sum{i=2}^{3n+1}2i$\sum{i=2}^{3n+1}1$

[elder berry]

the index below should have _ in front; \sum_{lower}^{upper}

[glacial eagle]

sorry, i'm new to this my bad XD

$\sum_{i=2}^{3n+1}2i$\sum_{i=2}^{3n+1}1$

[vital dew]

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

[glacial eagle]

yeah like that but i know that isn't right

[elder berry]

why would you have 2i preceding the second sum?

give me some thoughts on that

oh, the sum isn't correct

[glacial eagle]

i was looking at my professor's notes, and i saw that the second nested for loop was (3i+1)^2 and the lower + upper limits were both i = 1 and 2n respectively.

so my sum had (3i)^2 for one of the sums and 1 for the other. when i added them together

also, i meant to add both the sums on the one above too, not multiply

[elder berry]

so the second loop (the one I didn't highlight in yellow) would be $\sum_{i=1}^{2n} \sum_{j=1}^{(3i+1)^2} 1$

[vital dew]

peaceGiant

[elder berry]

I don't know where the confusion is coming from, I think I need more context + a more concise question on what the issue is

[glacial eagle]

yeah, sorry. lemme write in latex

$9$\sum_{i=1}^{2n}i^2$+\sum_{i=1}^{2n}1$

did you get this?

[vital dew]

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

[elder berry]

you're missing a term

(3i+1)^2 = 9i^2 + 6i + 1

I'm not seeing the sum with 6i

[glacial eagle]

OHH, you're right, i saw that just now. lol

so one more sum with 6i and it should be good?

[elder berry]

$\sum_{i=1}^{2n} \sum_{j=1}^{(3i+1)^2} 1 = \sum_{i=1}^{2n} (3i+1)^2 = 9\sum_{i=1}^{2n}i^2+ 6\sum_{i=1}^{2n}i +\sum_{i=1}^{2n}1$

[vital dew]

peaceGiant

[elder berry]

yupp

[glacial eagle]

okay, thank you. sorry, i am taking an intermediate discrete structures courses and it has been nearly a year since i took the beginning course. so i am a bit rusty, but i am trying to understand everything again haha

[elder berry]

no worries

[elder berry]

probably by proving that the negation is true

$\exists x P(x) \equiv \bot ~\iff ~ \forall x (\neg P(x)) \equiv \top$

[vital dew]

peaceGiant

[elder berry]

providing the actual problem would be more useful though

[spring elk]

still stuck

i can send my attempt

idk what to do from here.

also im not even sure if im allowed to do this. I mean, in my induction hypothesis im assuming it works for k but i dont know if it works for t

[elder berry]

great

[spring elk]

but why am i allowed to do that?

[elder berry]

by strong induction, you assume for all values below n+1 that a_n = n! a_0^(n+1)

the rest is just replacing said values and canceling terms

is there a specific step that is confusing you?

if not, you can rewrite the last step you have

the sum is a sum of constant numbers (they do not depend on the index), and you are summing n+1 of them

in other words

$\sum_{i=0}^{k} k! ~ a_0^{k+2} = k!~ a_0^{k+2} \sum_{i=0}^{k} 1 = a_0^{k+2} ~ k! \cdot (k+1)$

[spring elk]

ohh

[vital dew]

peaceGiant

[spring elk]

ok this makes sense

my only confusion is just why i was allowed to replace the at

[elder berry]

by the principle of strong induction (or whatever the name was)

wait

yeah, it is named strong induction https://brilliant.org/wiki/strong-induction/

[spring elk]

if i prove it works for lets say a(0) and a(1) then i can only assume that it would also work for a(k-1) and a(k) right?

[elder berry]

depends on how you set it up

it is totally possible that you can just show it for a(0) as a base case, and then it will work for any a(k)

i think that exact scenario should be in your proof too, show a(1) = a(0)^2, conjecture that for any k, a(k) = k! a(0)^(k+1), then it is enough to show a(k+1) = (k+1)! a(0)^(k+2)

[spring elk]

its just that, how does this make it different from regular induction? if the steps are the exact same?

besides induction being that im only assuming it works for n=k and the strong induction im assuming it works for all until k

[elder berry]

regular induction is kind of a sub-type of strong induction, rather it doesn't use ALL preceding cases

the steps are exactly the same, it is just that the inductive hypothesis differs in what you will assume

P(1) -> P(2)
P(2) -> P(3)
...
P(n) -> P(n+1)

Strong induction: P(1) is true
P(1) -> P(2)
P(1) and P(2) -> P(3)
P(1) and P(2) and P(3) -> P(4)
...
P(1) and P(2) and ... and P(n) -> P(n+1)```

you apply strong induction when the regular induction is insufficient for the problem, when it's too weak xp

[spring elk]

ah i see. but in the problem that i sent, the regular induction would work as well right?

or actually it wouldnt

[elder berry]

no

[spring elk]

yeah i see

so i still just do 1 base case and then i can make that strong assumption

?

[elder berry]

yep

[spring elk]

alright, thanks!

[elder berry]

npp

[tough dove]

So I have this sequence and I am having trouble finding the closed formula can anyone help?

I’m not sure if this is the right channel as this is discrete structures for comp sci which is like discrete maths but split into 2 semesters I think?

[pine compass]

The griddy formula

[tough dove]

The WHAT

[pine compass]

thank god for rosa parks

[tough dove]

R u serious right now

[lofty portal]

hm where did this sequence come from

I don't see any obvious pattern and oeis didn't turn up anything

[tough dove]

my homework ;-; OI KNOW

i think it has something to do with !

because the last one that was confusing like this one had like n! and some other stuff

but this one is actually hurting my head

Here’s the original problem on the site

Could it be a typo? Because genuinely my brain hurts

Please @ me if anyone can help

[coral parcel]

There appears to be a hint?

[tough dove]

D is the part I am on

So it’s the sum of 2 well known sequences

I was thinking it has something to do with n! But I’ve tried some things and I am stuck 😭

[coral parcel]

(n-1)!+(n-1)³

What a bizarrely silly problem.

[tough dove]

I’m gonna cry 😭😭

Hmmmm

Shoot forgot to mention that the sequence starts at A0 not A1

It’s okay I think

[coral parcel]

Well, then just say n instead of n-1.

[tough dove]

Yeah you did it

Yeah

Thank you

How did you go about solving it?

just comparing to other sequence’s?

[coral parcel]

Based on your hunch that factorials were involved, I tried subtracting some (n±a)! sequences from it to see if what was left looked familiar.

[tough dove]

You are the best thank you so much

[coral parcel]

Tried Fibonacci numbers first but that led nowhere. 🤡

[tough dove]

I know I tried that too because of how lost I was 😭😭😭

[glacial eagle]

beyond solving for the base case of n = 2, how would you go about solving this?

apologies, this is small

$\6(x - 1)^2 >= x^2 for all real x >= 2$

[vital dew]

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

[stray reef]

@glacial eagle why are you talking about base cases though? this isn't a problem that can be proven by induction

(unless you shoehorn it in)

[glacial eagle]

LOL yeah my bad

well, i am trying to figure out what quadratic properties they are talking about. we are learning induction but i don't know if we have to subtract x^2 from both sides

[stray reef]

you don't "have to" do anything, however given that you are asked to prove something for all real x ≥ 2 induction will be inapplicable.

the solution i would have first thought of would be to subtract x^2 from both sides and clean up 6(x-1)^2 - x^2

to see if anything nice jumps out like a factorization

[dense glade]

Anyone could give me a tip about this indentity? I'm having hard time understanding it

[stray reef]

complete the square failing that, i guess..

[glacial eagle]

$5x^2 - 12x + 6 >= 0$

excuse the bad latex

LOL

[stray reef]

\geq

also don't put backslashes where they don't belong

latex does not know what \5 is

if you want 5 just say 5

[vital dew]

torisutan

[stray reef]

you're tasked with proving $5x^2 - 12x + 6 \geq 0$ for all $x \geq 2$

[vital dew]

Ann

[glacial eagle]

yes

i don't want to just plug in numbers

[stray reef]

complete the square or factorize tbh

i see no better/cleverer solution

[dense glade]

just take the dervative

and show its increasing

on the interval

[grand totem]

Are you looking for a combinatorial proof?
In that case a first hint might be as follows: The left side counts subsets of {1,2,...,n} of size k. Now partition those subsets based on their maximum element (that is what the right side of the equation counts).

[dense glade]

i saw that arguement and It confused me a little

I could not understand it

[glacial eagle]

thanks guys! i'm going to try and see if it works :( it's the only one i have no clue how my professor wants us to prove it

[dense glade]

I couldn't follow it for some reason is not clicking

I think the argument you're referring to says pick i larget elements then there will be k-1 elements left to choose from

which makes sense

but I don't get the extension

which is we will the have k c k-1 + k+1 c k-1

[stray reef]

i think you misstated the intended argument

[dense glade]

probably because I didn't really understand it

[stray reef]

may i attempt to explain it then

[zinc dagger]

i have to take discrete math for the third time next semester

i do not like this class

[stray reef]

$\binom{n}{k}$ counts the number of $k$-element subsets of ${1, \dots, n}$.

the sum on the right counts the same thing, except with a split into cases based on the highest number picked

namely, if we take $i$ to be the highest number in our chosen subset, then there are $\binom{i-1}{k-1}$ subsets with that number as their largest (since the other $k-1$ numbers have to come from ${1, \dots, i-1}$

and $i$ can of course range from $k$ (for the selection ${1, 2, \dots, k}$) to $n$

[vital dew]

Ann

[grand totem]

Alright, one thing at a time - We are counting k-sized subsets of the set [n] = {1, 2, ..., n}. Any of those subsets will have a unique greatest element (which will be a number between 1 and n). Since the maximum element is unique, we can partition all our k-sized subsets of [n] based on their maximum element. All that is left to do is to count the number of k-sized subsets of [n] with maximum element equal to m (where m is between 1 and n).
Fix such an m for a moment. In order for m to be the maximum element of a k-sized subset of [n], is must first of all be a member of that subset. Now we just need to count the ways how we may choose the remaining k-1 elements to fill that subset up. Clearly we must make sure not to include elements >m in our choice, as this would go against m being the maximum element. We also exclude m itself because it's already included. We're left with m-1 choices (all those strictly smaller than m), and we must choose k-1 elements out of those m-1 possibilities.

Wrapping up we're now at $\binom{n}{k}=\sum_{m=1}^{n} \binom{m-1}{k-1}$

[vital dew]

Neverbloom

[grand totem]

Aside from renaming m to i, the only thing left to show is that you may get rid of the summands for m < k (why?)

[dense glade]

ok thanks guys both explanations are amazing

[dense glade]

is thats why

your summation starts from 1 and not k?

i assume because the first time is k-1 c k-1

which is 1? or

[grand totem]

Looking at the binomial inside the sum it's easy to see that for m < k we're trying to choose k-1 elements out of a set with strictly less than k-1 elements (as this is not possible to achieve, there are 0 ways to do so and hence the summands for m=1..(k-1) are just 0)

One may also see this when thinking about how we can never have maximum elements that are strictly less than k for k-sized subsets of [n]. Because there aren't enough elements smaller than m to fill up that subset to a subset of size k

[dense glade]

Ok so

correct me if I'm wrong

but the process looks like that

we will pick an element i to fill a subset

i is the largest element in that some subset

and there will be i-1 c k-1 ways left to fill the rest of the same subset ints smaller than i

[grand totem]

Correct

[dense glade]

now for the 2nd term in the extenstion

k c k-1

it's obv not the same logic right?

[grand totem]

I'm not quite following here, where are you counting $\binom{k}{k-1}$?

[vital dew]

Neverbloom

[dense glade]

the second term in the extension

k+1 -1 c k -1 = k c k-1

[grand totem]

I do not see a $\binom{k}{k-1}$ anywhere in that image

[vital dew]

Neverbloom

[grand totem]

Or a $\binom{k+1-1}{k-1}$ for that matter

[vital dew]

Neverbloom

[dense glade]

doesn't the index start at k?

so the second term is k+1, k+2 ....

[grand totem]

Ah, I wasn't aware that they were giving an algebraic proof

Are you confused by how they expand the sum?

[dense glade]

no but I thought those were all the cases

to count the same the thing as the L.H.S

so I wasn't sure about the 2nd case for example

like how does picking an i'th large element

would result in k c k-1

[grand totem]

It is!
The term $\binom{i-1}{k-1}$ counts the number of k-sized subsets of [n] with maximum element equal to i.
For $i=k+1$ we indeed get $\binom{(k+1)-1}{k-1}=\binom{k}{k-1}=k$

[vital dew]

Neverbloom

[grand totem]

The reasoning is that if we include the element $k+1$ in our subset, we may now only choose from the elements ${1,2,\dots,k}$ to fill that subset up. That is we choose $k-1$ elements from ${1,2,\dots,k}$ which is precisely $\binom{k}{k-1}$.

[vital dew]

Neverbloom

[dense glade]

ahhhhhhhhhhhhhhhhhh

i see'

ok i finally get it thanks

lol you're patient

[naive turtle]

Want to learn discrete on my own, what yall recommend?

[night stream]

Hi can someone tell me if i did a and b right

[serene mural]

(proving using mathematical induction)
how does 1 inside [] bracket turned to 2^(n+1) in third line

[stray reef]

,rccw

[stray reef]

1 < 2^(n+1)

[serene mural]

sorry but how did you get this?

[stray reef]

well any power of 2 is bigger than 1 isn't it?

[serene mural]

oh right

thanks

[chrome tree]

Start with logic first, you can find many good tutorials on youtube. One i watch is TrevTutor. I would def. recommend this channel.

[glacial flame]

What would the proper/formal definition of modulo be when you are modding by a negative number? It seems like any calculation site represents the result as a negative number (m < result <= 0), but typically r is defined to be 0 <= r < d where x = qd + r.

[brave rock]

Under the usual definition, we don't actually consider the remainder at all.

In fact modulo m is the same as modulo -m

For what it's worth, you can still choose a 'remainder' m < r <= 0 when m is negative, and this still works, although ofc the definition of remainder adjusts

[glacial flame]

Is there a reason behind why every site makes sure to adjust the result to be the same sign as what you are modding by?

Is that just a convention unrelated to formal mathematical definitions?

,w 1mod-3

[vital dew]

Results provided by WolframAlpha

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

Requested by JJCUBER#9807

[glacial flame]

(As an example)

[brave rock]

.

It is best that you do not think of 'mod' as the remainder. It is a relation.

The remainder is simply a canonical choice of representative

[magic summit]

Does anyone know how to solve question 2

[brave rock]

Yeah you use the contrapositive

[magic summit]

so x=n/m and y=n/m

[chilly kayak]

if x=m/n and y=p/q, then 3x+4y is rational. where m,n,p,q are integers

[magic summit]

isnt the question askinf if it isnt an element of real numbers tho

[chilly kayak]

Q means rational numbers, not reals

real numbers are R

[magic summit]

oh ya thats what I meant

so why are you using intergers if its rational numbers

[chilly kayak]

because you define rational numbers with integers this way m/n

[magic summit]

ohh i see

so I just plug that back into (3x + 4y) and solve

[chilly kayak]

yes

[magic summit]

i think i solved it thanks

the only other thing that is confusing me is question 3

[night stream]

how can i simplify (A⊕B) using tautology equivalence laws?

[odd phoenix]

i have exam tmm and i try to solve these questions my proff sent me

but i don't see thier answers anywhere so i donno i m doing right or not?

if someone know which text book is this or know where I can find the answers lemme know plss..

[rare barn]

@odd phoenix are these your actual exam questions?

[odd phoenix]

NO it's a practice sheet

[odd phoenix]

I just wanna know these answers so i can check my solutions

[restive kestrel]

Hi, can someone help?

[radiant plover]

FTFT

[restive kestrel]

ty

[coral parcel]

Don't hand out answers, please.

[still slate]

If I am trying to do a proof by contrapostive, would this be the first step

then assign p/q to x^y

[coral parcel]

No, you negated "x or y is irrational" wrong. It is shorthand for "x is irrational or y is irrational", so its negation is "x is rational and y is rational".

(By the way, ask yourself: is 2^½ rational or irrational?)

[still slate]

That would be just 1/2 so thats rational. Would contrapostive be the best way to do this then?

[dense glade]

Any idea what I’m doing wrong

[viral turret]

Any one know answers for these

[harsh osprey]

Hello! I have a question

I'm doing Linear Recurrence Relations

my problem asks me: Identify the solution to a_ n = 2a_ {n − 1} + a_ {n − 2} − 2a_ {n − 3} with a_ 0 = 3, a_ 1 = 6, and a_ 2 = 0 for all integers n ≥ 3.

uhhhh

lemme post it the formatting is hard

so I turned this into the characteristic equation r^3 - 2r^2 - r + 2 = 0

which I then made into (r-2) (r^2 - 1) = 0

and established the roots are r = 2 with multiplicity 1 and 1 with multiplicity 2

or, wait, is it 2, 1, and -1? how many roots are there here

I thought it was 1, 1, 2, and so went to say the general solution was (using 2a{n-3} to represent the third term on the righthand side of the above equation, since the _ symbol breaks discord)

I put down a{n} = a{1}(1)^n + a{2} * n * (1)^n + a{3} (2)^n

[unreal stump]

Roots are -1,1 and 2

[harsh osprey]

why

oh

difference of squares duh

hang on lemme redo this

okay yeah that works

I knew what the answer was cause it was multiple choice

and wasn't sure where my mistake was

thank you!

and only one of the answers even satisfied the initial conditions lmao

for some reason I was thinking r^2 - 1 was already simplified

I think I was assuming it was a multiplicity quesiton because I hadnt' encountered any yet, but it was in the chapter

D: wait

r^3 - 6r^2 + 12r - 8 = 0

I suck at factoring polynomials but

is this just (r-2)^3????

well here's my multiplicity lmao

[unreal stump]

Yes

[idle hazel]

Can someone explain the axiom of choice?

Zermelo

I dont understand the notations in this book

[pale epoch]

then share the notation

[idle hazel]

I can show you its not in English though

For every nonempty set X there exists that function with f(A) belonging in A for every A belonging in P(X) without the empty set

[pale epoch]

well, thats it

X is some set, P(X) is the powerset

and the axiom of choice says that there is a choice function on P(X)

i.e. for every nonempty subset A of X, the function f assigns an element of A to A

you "choose" an element of every nonempty subset

[idle hazel]

So for every non-empty subset you can choose an element by using a function?

[pale epoch]

ye, though the word "choose" is maybe a bit loaded

[idle hazel]

I dont understand the f(A) part

[pale epoch]

you get a function that does the choosing for you

A is a subset of X

f is a function on P(X)

[idle hazel]

Ohh

[pale epoch]

this is just function notation, then

[idle hazel]

So f(A) is a subset of A?

[pale epoch]

no

[idle hazel]

😦

[pale epoch]

f(A) is an element of A

it assigns one element of A to the subset A

like uhh

the domain of f is P(X)\{}

and not X

so a subset A of X is a single element of the domain

and this is just regular function notation and not the image of a subset of the domain

[stray reef]

P(X) \ {empty} you mean

[pale epoch]

yes, sorry

[idle hazel]

Ohh I understand now

So for any indexed collection of non-empty sets, there is a choice functions

[pale epoch]

you dont need indexed sets

your variant talks about powersets (minus the empty set) having choice functions

[idle hazel]

I got it in the end

[reef sedge]

guys can someone help explain what an equivalence class is

[pale epoch]

i mostly think of it as a weaker notion of equal

you consider objects equal/equivalent

and consider this set of equivalent objects (the equivalence class) as a new object in its own right

[unreal stump]

@frank sun Literally just find a random number except e^-1 mod phi?

The possibility of getting such a d is literally 1/phi

[coral parcel]

Their deleted message looked like they wanted to find e^-1 and wanted a better way to do that than brute force.

[frank sun]

Anyone familiar with RSA encryption? On wikipedia it says phi should be coprime with e. Another article said n should be coprime with e. A youtube video said n and phi should be coprime with e.

[little prism]

e should be coprime to phi

[frank sun]

thanks dude. 🙂

[still slate]

I'm trying to prove the following. Am I going about this the right way?

[little prism]

you say three cases but only list 2?

what are you trying to do. proving or disproving the claim

[still slate]

Trying to prove. I'm not sure if proof by cases is the best way

[little prism]

well proving by cases could work. but proving by example never works

[still slate]

So this would be a little better

[coral parcel]

That's not really a kind of case analysis you can do here. If you're trying to prove that one of those cases hold, then it doesn't help you to split into those cases. In each of those cases you're already done!

1. Assume that x is irrational and y is rational. Then "either x or y is irrational" is true, Q.E.D.
2. Assume that x is rational and y is irrational. Then "either x or y is irrational" is true, Q.E.D.
3. Assume that x is irrational and y is irrational. Then "either x or y is irrational" is true, Q.E.D.
   What you're missing is an argument that you're even in one of those cases to begin with.

In other words, when you say "x^y is irrational, so there are these three cases", you're assuming the thing you're supposed to be proving!

[coral parcel]

No, 2^(1/2) is not 1/2!

2^(1/2) is the square root of 2, which is arguably the most well-known irrational of them all. (Possibly second to pi, but there's probably a hundred times more people who know how to prove that 2^½ is irrational, than there are people who know how to prove that pi is).

[coral parcel]

"By induction" is indeed a weird specification here. Depending on exactly what your book/course means by "induction", you can probably prove "by induction" that all elements of S are rational numbers that can be written with a powers of 2 as denominator, but then it would be a separate step to point out that 1/6 is not such a number.

[nocturne portal]

thank you

[gusty oar]

is ∃x ¬∃y (s(x) ∧ f(y) ∧ (A(x,y))
the same as

∃x ¬∀y (s(x) ∧ f(y) --> ¬A(x,y))

and are both equal to
∃x(s(x) ∧∀y(f(y) → ¬A(x, y)))

?

[harsh osprey]

question

this is on my homework: How many terms are there in the formula for the number of elements in the union of 11 sets given by the principle of inclusion–exclusion?

I thought the answer was 11 but apparently thats wrong and I dont really understand why

or

oh

ah I see

[spark silo]

i dont understand how they get the vertice and edge count here.
i would have just done 6 vertices and 6 edges

[marble swan]

¬A→(A→B)

I need to prove this using natural deduction, not sure where to start

[chilly kayak]

prove what? that is a tautologia, contradiction?

https://web.stanford.edu/class/cs103/tools/truth-table-tool/

[chilly kayak]

check

[grand totem]

Not every Natural Deduction system is the same, so this will depend on the inference rules of your system.
Chances are that it's just a quick application of Explosion (⊥-Elimination)

[spring elk]

can someone help me understand this example?

how does piA(3,9) even get the value 3 as output?

i know for piA(3,9) it should be equal to 3 but how will y=x^2 give that value for x 3 and y 9?

[little prism]

well 3^2=9

or what do you mean

(3,9) is in D because 3^2=9

[spring elk]

doesnt (3, 9) = 3 imply that the output is 3?

i get that (3, 9) is in d i dont get the '= 3' part

[little prism]

pi_A(3, 9)=3

because pi_A always returns the first element

[harsh osprey]

what am I doing wrong here

I count the paths cfed, cbad, cbed, and cdcd

ohhhh

but also cdad, cded, I see

god theres so many

[harsh osprey]

oh wait

-_-

I just realised Ive been doing it manually

and my book has a formula

im so annoyed

[glacial eagle]

can someone please help explain to me if i did this correctly?

[elder berry]

I find it really disorganized. State the problem statement first: 4*6^n >= 5^(n+1) + (n-1)^2, n >= 2.
Write the base case for n=2. 4*6^2 >= 5^3 + (2-1)^2
Write the inductive hypothesis which you are missing.
Write the inductive step and clearly explain how the inductive hypothesis implies the inductive step

[glacial eagle]

thank you! i'll try reorganizing it and sending it again, i am going to try to solve it and reorganize it then send it back in this chat

[weary tiger]

if one statement from combined compound statement in conjunction is false, can we say that basically, it is negation of conjunction?

[elder berry]

wdym by "it is negation of conjunction"?

[rough fulcrum]

why does this work

[little prism]

why does what of that work

[rough fulcrum]

the j:=k+1 and j:=k

[little prism]

essentially its just a renaming of the variable

as k runs from 0 to n, k+1 runs from 1 to n+1

and k+1 is in a sense more important than k here, so we want k+1 as our variable

and we do that by naming j=k+1 and then writing everything in terms of j

[rough fulcrum]

ah i see

thanks

[weary tiger]

there is no thing as a negation of conjunction ? ig i misunderstood something then

[elder berry]

You can negate a statement that involves a conjunction. Can you provide an example of what you mean and what you want to conclude?

[weary tiger]

like for example there is 2 statement q and p, today is hot and today is sunny weather. both of them False, can we say it is negation of conjunction or we should just say combined compound statement is incorrect ?

and if i am wrong, then what does negation of conjunction actually mean ?

[elder berry]

The compound statement is incorrect and in the given context negation of conjunction doesn't make sense.

The negated compound statement will be true (which is Today is not hot or Today is not sunny)

[umbral tendon]

My brain is too small to handle this riddle.

Anyone want's to try it?

[woeful scroll]

anybody doing matrix multiplication read AlphaTensor paper?

I am not doing matrix multiplication algorithm, but is that model out perform the most efficient algo so far? I remember it seems like O(n^2.778) is away from SOTA, anyway, I am not working on this direction. but it seems like an interesting work

[woeful scroll]

which book is it? is the discrete math textbook one?

[stray reef]

@umbral tendon if the guy is telling the truth then there is buried treasure, if the guy is lying then exactly one of "there is treasure" and "guy is telling the truth" is true, and you know which one it is

[midnight herald]

Hi everyone, how do I determine if

f(n)=n^3 is a onto function from Z to Z?

So far my working are as of below :

Let y ∈ Z
y=n^3
n^3=y (from above)
n = 3√y

I am trying to make n the subject, then subbing into the equation itself but I am not so sure how do I deal with it using this method, on a equation with square and cube square

[stray reef]

n = 3√y

this sounds like you are talking about three times the square root of y and not about the cube root of y as you intended

anyway, the cube root of 2 is not an integer so 2 does not belong to the range of your function so your function is not onto

[midnight herald]

Ahh I see, in that case, will this explaination be valid ?

n^3 = y
n = cuberoot y
If y=2, cuberoot y is not a integer, thus, f(n)=n^3 is not a onto

[stray reef]

the wording stinks but yes

[midnight herald]

Okayy thanks you so much !

[iron wave]

for f(x,y) = y! - x!

would this be an onto or one-to-one? or neither :v

[distant glade]

what's your domain and codomain

[iron wave]

@distant glade F: Z x Z -> Z

[stray reef]

assuming you meant f and not F, what's f(-1, -1)?

[iron wave]

That'd be 0 right?

[distant glade]

how about f(-2,1)?

how are you defining ! on the negatives

[rough fulcrum]

that textbook is for real analysis

its just covering recursion summation induction product stuff that probably needs to be covered for me to properly understand

[iron wave]

Factorials on negative numbers are undefined right?

[distant glade]

well that's why i'm asking you. you could use the gamma function, but if you're saying they're undefined then f is not well defined itself

since f can't map every element from the domain to the codomain

[iron wave]

Ah!

So this would just be neither

and this would be a function either?

*wouldn't

[distant glade]

you're right, it's not a function

[halcyon sand]

Does anyone have any resources for Big-O Notation?

[woeful scroll]

Great! I do combinatorial stuff, and I also want to learn some real analysis for interests, lol. Might need some guidance, like where to start, in the future, lol

[civic lava]

Can you use Theorem 3.16: Symmetry of ≠ to make (p and q ≠ notp or notq) into (p and notp ≠ q or notq)? Can you flip one part of it like that or would you only be able to make (notp or notq ≠ p and q)?

hopefully that question makes sense

[elder berry]

If the theorem says that a ≠ b -> b ≠ a then you can't conclude that p and notp ≠ q or notq from what you were given. However p and notp ≠ q or notq is indeed true

[rough fulcrum]

how would i do 1-33d with induction considering that both n and x are real numbers

i dont see how i can use proof by induction here

[elder berry]

Just x is a real number, n is a natural number. Think of x as a fixed value, as just a constant -- number. Now induct on n.

How would you write the inductive step?

[rough fulcrum]

oh i thought n was a real number

ok nvm i can do this then

thanks

[dawn sandal]

Let A be the set of all CS students this semester, B the set of CS students who took a picture of Lucia’s flag, C the set of CS students who took a picture of the Dr. Strange, and D the set of CS students who took a picture of a program.
A Partition the CS students into 4 subsets:
● CS students who took a picture of a program,
● CS students who took a picture only of Dr. Strange,
● CS students who took pictures of Lucia’s flag or Dr. Strange or both, and
● CS students who didn’t take any of the three pictures.
Show your answers as set operations on A, B, C and/or D. Your solution should use the set operation symbols for intersection, union, complement, and difference, and no other symbols.

[coral parcel]

That sounds like a direct quote of a homework/exam problem. Do you have anything to say about that problem?

[dawn sandal]

yes i have what i have tried forgot to mention it

[red relic]

quick questions on generating functions:
if i had the infinite sequence 0,1,0,0,1,0,0... etc, how do i 'shift' the rational polynomial (1)/(1-x^3) over so that the first 1 starts on the term corresponding to x^1? is it just (1)/(x^2)(1-x^3))?
also, if i had the infinite sequence 1,0,-1,0,1,0,-1... does having (1)/(1+x^2) account for the gaps between the sign changes

[dawn sandal]

1. A intersection D

2. (A intersection C) - (B union D)

3. A intersection (B union C)

4. A - (B union C union D)

@coral parcel

[red relic]

i'm not completely sure how your prof is doing this but do you really need the A? can you not just say 'D' for question 1?

[coral parcel]

We do need A in answer 4, though.

[coral parcel]

Yes to both, unless I'm missing something.

[dawn sandal]

Let A be the set of all CS1800 students this semester, B the set of CS students who took a picture of Lucia’s flag, C the set of CS students who took a picture of the Dr. Strange, and D the set of CS students who took a picture of a program.
A Partition the CS students into 4 subsets:
● CS1800 students who took a picture of a program,
● CS1800 students who took a picture only of Dr. Strange,
● CS1800 students who took pictures of Lucia’s flag or Dr. Strange or both, and
● CS1800 students who didn’t take any of the three pictures.

sorry my mistake, this is the updated version

CS1800 refers to a specific CS class, and CS refers to all CS students

[lusty fern]

Why is it that when we do strong induction relating to Fibonacci sequence, we need to have 2 base cases?

I know it’s because it’s a recurrence relation

But I’m having trouble wrapping my head around it

[coral parcel]

Strong induction doesn't really have base cases.
There's just an induction step where you know p(k) for all k<n, and then you have to prove p(n).
Inside that step you might need to have some special cases for small n where the argument you have in mind for larger n doesn't go through.
But the strong induction itself doesn't care about what the inside of your induction step looks like.

For the Fibonacci sequence, since the sequence has separate definitions for n=0, n=1, and n>1 it will often be natural do do a similar case analysis in your induction step, since that determines what the definition will tell you about the Fibonacci number you're looking at.

[lusty fern]

For Fibonacci the base cases are always n=0 and n=1 right?

[coral parcel]

As I said, strong induction doesn't have base cases.

Which cases you need in an internal case analysis in the induction step, or whether you need a case analysis at all, depends on what you're trying to prove.

[vital dew]

Kin

[rose wing]

Hello, $d_m$ is a set of pair-wise samples $d_m = {(d_m^x(1), d_m^y(1)), \dots, (d_m^x(m), d_m^y(m))}$ of size $m$.

Why its space dimension is $\mathcal{D}_m = (\mathcal{X} \times \mathcal{Y})^m$, instead of $Y^X$? thank you.

[vital dew]

Kin

[glossy dirge]

Can someone explain to me how do we go from rearrange step to solution?

non homogenous recurring equations

[halcyon basin]

It's the equality of the coefficient of two polynomials

Is $2(p_{1}+1)X+(2p_{0}-3p_{1})=0$ then by construction of the polynomials the coefficients of the first hand should be equal to the ones of the null polynomial, hence the result

[vital dew]

black_couscous