discrete-math

[faint narwhal]

The set of quaternions is just R^4

[rough crater]

can someone please help me with this?

fₙ,ₖ represents the number of distributions for n different balls into k different containers such that not a single container is left empty.
find the recurrence for fₙ,ₖ along with it's initial conditions:

[faint narwhal]

What have you tried?

[tough root]

so cardinality for set of quaternions is c?

[cerulean wind]

for quaternions over R yea

[tough root]

thx

[subtle charm]

Can someone explain the proofing solution here. I don't quite understand it.

Do I just have to show that the conclusion is true? since the statement is true by default, if the hypothesis is false?

[pale epoch]

the proof doesn't work so that's why you may not understand it

[subtle charm]

wait what?

[pale epoch]

the argument for x not in A does not work

[subtle charm]

If it is wrong, then how do I go about solving this type of question?

[pale epoch]

you don't, the statement is wrong

you cannot prove wrong statements

at least hopefully...

[subtle charm]

Okay, suppose if the statement is valid?

in general, would if be fine to just show that the RHS of the statement evaluate to true?

[pale epoch]

whats the RHS

[subtle charm]

Right hand side

or conclusion

[pale epoch]

to show an implication A->B is true, it suffices to show B is true

[subtle charm]

Ah okay

[slow jewel]

What is (ii) if mean?

[quaint star]

Which part?

Equal means they consist of the exact same vertices and edges, and disjoint means they have no vertices or edges in common

[slow jewel]

disjoint

thanks

[tough root]

G(3,2) and H(3,2)
graph G is same like graph H

[slate burrow]

I'm trying to write a "logical formula" for this statement:
"There exists a natural number that is larger than some odd natural number"

And this is sort of what i came up with, and i was wondering if it's legitimate?
We can prove this by saying setting up this condition, x > y, where x is a natural number and y is a odd natural number.

We can get a odd natural number with the help of (2n+1) which turns any number to a odd number.

and to prove x > y, we can make a function for x, for instance (2n+2)

Using (2n+1) and (2n+2) we can find a natural number that is bigger than a odd natural number.

(Please show mercy, i'm new to discreet math)

Imo it holds, since if we try for n=2
for (2n+1) we get (22+1)=5
and for (2n+2) we get (22+2)=6 which proves the statement

[tender hearth]

I’ve tried a few things but can’t get this question. I know that strings of length less than ur equal to k is sigma from 1 to k 7^8. How can I solve this?

$\sum_{n= 1}^{k} 7^n \ = \frac{7(7^8-1)}{6}$

[vital dew]

A Kid Named Galois

[tender hearth]

<@&286206848099549185> pls help me

[faint narwhal]

Can you figure out what the last symbol in the string has to be? @tender hearth

[tender hearth]

Yes. Wouldn’t it be the horseshoe?

[faint narwhal]

And how did you figure that out?

And can you adapt this idea to figure out the second to last symbol has to be?

[tender hearth]

From the particular order we imposed

[tender hearth]

I don’t know how. 😪 I think I’m onto something. If we set 1 million to the sum, wouldn’t we get n= # of strings with length k. That’s as close as I’ve gotten

[faint narwhal]

I mean, you looked at the remainder of one million divided by 7 right?

[tender hearth]

Oh yes. I thought about that. So it does not divide evenly. Does 5 being the largest that divides evenly mean the last symbol is the diamond?

[faint narwhal]

I'm not sure what you mean by 5 being the largest

[tender hearth]

Oh bad thought. But continue pls. I see what you mean that it’s 142857.142857 with a repeating decimal that’s the same as the whole number part

[faint narwhal]

The idea is that the last digit repeats every 7

So you can look mod 7 to figure out the last digit

Similarly, the second last digit repeats every 49

[tender hearth]

Thank you. So the pattern continues? 3rd from last repeats every 343?

[faint narwhal]

Yes

But it's a bit simpler than that

The second last digit repeats every 49

but each shape shows up 7 times in a row

So to figure out the second to last digit

You just subtract off the last digit

Divide by 7

And then look at the remainder mod 7

Repeat

Its basically the same as converting to base 7

[tender hearth]

Thank you!!!

[subtle charm]

Can someone explain to me how do I go about writing proofs for the following statement?
if A U B = A intersects B then A = B

Can I write this:

1. suppose A = B
2. A U B = A U A = A?

Can I just assume the conclusion to be true and use it to show that if the conclusion is true and the hypothesis is true then the statement is true?

[snow sleet]

no!!!

if that was a valid form of proof, then you can prove anything!

you cannot assume A=B

[subtle charm]

how shld i go about solving this question then

I am kinda lost on how to proof set theory questions

[snow sleet]

Well if (A intersect B) equals (A U B), then you know that they each have the same elements

now

what does that mean?

I'll be a little more clear....

you need to show that x is in A if and only if x is in B

if x is in A

then x is in A U B

meaning

x is in A intersect B (due to the given equality)

so x is in A and B

hence x is in B

now suppose x is in B

and now prove this direction. (I showed x is in A implies x is in B).

make sense @subtle charm ?

[subtle charm]

yes

[snow sleet]

awesome

you'll notice that the proof for "x is in B implies x is in A" is quite similar to what I have written here

[subtle charm]

so if I showed that A U B = A intersect B, then what is the next step

[snow sleet]

this is given

you don't need to show that equality

because we want to show: if A U B = A intersect B, then A = B

so we can assume A U B = A intersect B (without proof)

and now we just need to show A=B by showing x is in A if and only if x is in B

[subtle charm]

okay this part i understand

[snow sleet]

nice! now notice that showing (x in A implies x in B) AND (x in B implies x in A) will show that A and B are the same set. Hence equal

[subtle charm]

uhm but what if if had something like A intersect B = A U B complement then A = empty set

[snow sleet]

then B would have to be the empty set

for A intersect B = A U B to hold

[snow sleet]

if A is the empty set, then (x in A implies x in B is vacuously true)

do you you mind if I prove one direction and then you can prove the other?

[subtle charm]

yes pls

[snow sleet]

so you understand what it should look like

aight

\begin{proof}Suppose $A\cup B=A\cap B$. Suppose $x\in A$. Then $x\in A\cup B$. Now due to the given equality, $x\in A\cap B$. This means $x\in B$. Now we show that if $y\in B$, then $y\in A$...\end{proof}

[vital dew]

logician

[snow sleet]

did everything I just wrote in my proof of one direction make sense?

[subtle charm]

I don't quite get the second sentence where you show that x is an element of Union B - > x is an element of A intersect B

[snow sleet]

this is due to the assumption A intersect B = A U B

[subtle charm]

oh wait

[snow sleet]

since A U B is the same set as A intersect B, x being in A U B means x is in A intersect B.

[subtle charm]

Yup, I got it as soon as I draw the venn diagram out to visualize it

I see thanks @snow sleet

[snow sleet]

You're welcome!

ping me if you have any more questions on this

[subtle charm]

will do!

[subtle charm]

@snow sleet can I say that if (A intersects B) = (A intersects C) then (x is an element of A and x is an element of B) and (x is an element of A and x is an element of C)?

[snow sleet]

Yes

You should be supposing x is in some set first tho

Like say “if x in A intersect B”

Then ....

[subtle charm]

actually can I jump straight to saying x in (A intersects C)?

[snow sleet]

Yes

[subtle charm]

or do I have to show that x is in A then X is in (A intersects C)

[snow sleet]

Since the set are equal

Oh

Um

if x is in A intersect B is what I think you meant.

x is in A isn’t enough

To say x is in A intersect C

[subtle charm]

So, I have to start off the proof by saying that suppose x is in ( A intersect C) ?

[snow sleet]

Depends...what is the statement you’re trying to prove?

[subtle charm]

A U B = A intersects B then A = B a question similar to this

[snow sleet]

That isn’t what you just talked about lmao

[subtle charm]

I was just wondering if it is okay to just go straight into saying x is in (A U B)

[snow sleet]

After saying what?

I’m getting confused about what statement you’re trying to prove

[subtle charm]

for this question, A U B = A intersects B then A = B.
In your proof. you started by saying suppose x in A. Then x in A Union B

[snow sleet]

Okay gotcha

[subtle charm]

I was wondering if it is okay to omit the statement suppose x in A

[snow sleet]

No

Leave that there

We wanted to show A=B

By showing x is in A iff x is in B

So to show “if x in A then x in B.”

I needed to suppose x in A

Now to show y in B implies y in A, you need to assume y in B

[subtle charm]

ah okay

[snow sleet]

Aight dope. I’m heading to bed rn but you can ping me if you have more questions and I’ll reply as soon as I can. I got a busy schedule tomorrow so my reply may be late

[subtle charm]

Sure, thanks for the help! @snow sleet

[fresh grove]

how do i prove this? i think this is under equivalence relation

[sour arrow]

Two sets are equal when all of their elements are equal

Or, A = B when, for any a ∈ A you might choose, there's exactly one b ∈ B st a = b

And no extra b? Haha

I'm getting too into that. You know when two sets are equal.

So it's one of two cases:
{x1} = {x2}
{x1, y1} = {x2, y2}

Or:
{x1} = {x2, y2}
{x1, y1} = {x2}

Second case is unreasonable, so you have to have the first@fresh grove

[fresh grove]

oh right ok so use the definition of equal sets

i see thankss 👍

[fresh grove]

the qn defined an order set (x,y) to be {{x}, {x, y}}. But after proving the above biconditionally, they asked us to find another way to define order set, how do we do it?

[maiden notch]

{x, {x,y}} should work too iirc

[cerulean wind]

this is kuratowski definition and also works. you can define it as (x,y) = {{ x, 😦 }, { y, 🙂 }} where 🙂 and 😦 are just symbols not in X or Y.

[sour arrow]

Simplest way one might think of is:
{{x,1}, {y,2}}
But there's nothing special or ordered about the choice 1 and 2.

[cerulean wind]

yea, just tagging x and y

[fresh grove]

ohh

i see okay thanks

here i define a relation on rational numbers

im q confuse what equivalence class is exactly? isit the equivalence class of 37/7 would contain the elements that fulfils the condition of the equivalence relation?

so it can be anything, like 1/2 or 2/7 or 2/5

cuz first, reflectivity,
37/7 - 37/7 is an integer (true)
second if 37/7 - y is an integer, y - 37/7 is an integer (true)
third, if 37/7 - y is an integer and y - z is an integer, 37/7 - z is an integer (true)

[stray reef]

[37/7] consists of all such rationals x such that x R (37/7) is true.

i.e. in your case it consists of all rational numbers that differ from 37/7 by an integer.

[fresh grove]

oh i see thanks!

can i check if im understanding correctly, so for another example, if
x R y <=> xy > 0, where x, y are rational numbers
for equivalence class [2] it would also contain any element where x R 2 is true, so it can be any rational number greater than 0?

[stray reef]

wording...

yes, [2] would be the set of positive rationals.

[fresh grove]

sry my bad thanks, is this derived from the definition of equivalence class?
cuz let's say
a ∈ [x]

a ~ x (by definition of [x])

but how do i get from here to
a R x

is it by property of reflectivity?
since x R x, then since a ~ x,
it would be a R x

[stray reef]

aren't ~ and R just two symbols you'r using for the same thing...

[fresh grove]

i wanted to ask are they the same?

[stray reef]

you're talking about an equivalence relation

but you seem to be undecided as to what symbol you're using for said relation

[fresh grove]

I learnt that R just means is related to
while ~ is equivalence relation

[stray reef]

R doesn't mean anything

it's a variable name just like x or z or any other letter

it's just that in your context it typically stands for a relation

[fresh grove]

oh okk i see

thanks

[fresh grove]

so for [x], it only contains elements that makes x true for the equivalence relation?

eg. for the equivalence relation modulo 3 (x % 3 = 0)
if i have a set {1, 2, 3, 4, 5, 6}
the equivalence classes would be
{1, 5}, {3, 6}, {2, 4}

like i feel the modulo example and [37/7], the way we determine the equivalence classes is different?

[polar hound]

Hey guys, is this the same as A intersection B?

[pale epoch]

ye

[acoustic sphinx]

How would one go about finding the number of surjective functions from let's say set A with 7 elements to set B with 4 elements? I suppose I have to use stirling numbers of the second kind S(7,4) but I'm not quite sure, so any explanation would help tremendously! :)

[pale epoch]

think of the set B as 4 distinct baskets and the set A as 7 distinct balls

then you have to figure out how many ways there are to put the 7 balls in the 4 baskets such that no basket is empty

[plush dock]

Hey!

I need to find the coefficient of this, for x^9:

Now, I know it's this:

But I can't wrap my head around why the 4* C(6+2,2) is correct here?

[stray reef]

x^3 term from (1+4x+6x^2+4x^3+x^4) * x^6 term from the series

[west kestrel]

how to solve this question?

[plush dock]

I get the series, but how the x^3 from that term?

And thank you for agreeing to help of course

[stray reef]

it's literally 4x^3 lol

[plush dock]

Okay thanks, sorry

[slate burrow]

"for all odd natural numbers n, it is the case that n^2-1 is divisible by 4"
How can i prove this statement? Can i use "strong induction" to prove it?

I tried for 3, 11 and 13 and it holds

[stray reef]

are you explicitly instructed to use strong induction?

[slate burrow]

It says "write a logical formula" so no

[stray reef]

"logical formula"?

can you show the exact statement of the problem?

[slate burrow]

I'd see a pattern, but i'm not sure if it's related or not. Whenever you take n^2 of a odd number you get a odd nubmer and whenever you substract -1 it becomes a even number

yes

[stray reef]

it sounds like you may have misread or misunderstood what is actually required of you here.

[slate burrow]

oh and this

no sorry

wait

[stray reef]

so you are not actually asked for a proof.

[slate burrow]

Right

[stray reef]

you are asked merely to transcribe it in logical notation

[slate burrow]

If you use induction you give a proof?

[stray reef]

who cares about induction

we're not proving anything ehre.

here*

[slate burrow]

Ok, i can just plug in for some values and see if i see a pattern or something that i can express logically

[stray reef]

all we're doing is translating our statement, "For all odd n, n^2-1 is divisible by 4"

no

you will not be plugging anything in

you are tasked with translating this sentence into logical notation

nothing more nothing less

[slate burrow]

ahaa

like this?

[stray reef]

something like this.

except of course it won't be exactly that.

[slate burrow]

right right

i see, i thought i was supposed to make a proof or something. Thank you, i understand now. :)

[acoustic sphinx]

I'm trying to wrap my head around the Erdos–Szekeres theorem but it's just not really clicking. If anyone knows about some article/video that talks about it then please do send it over! :)

[weary tiger]

hey guys, i have a graph theory question

Use the graph given below to fill in the table and determine the articulation points. Begin with vertex A. When given a choice, explore neighbors in alphabetical order. Note for example that C will explore its neighbors in this order <A, B, D, I>.

these are the instructions

im really confused on what this is asking for

like the low 1 low 2 low 3

and the numbers in the table

[north dust]

Combinatorics is interesting.

AHHH

[floral lily]

hello! I am trying to understand this however i dont think i understand it well. am i just trying to prove the propositin, and indicate its value without showing why? I am not sure how to explain how its true i guess so im not sure if im even understanding this assignment here

[low carbon]

if the domain for all these variables is all, why is only one of them Vx, and the other 2 Ex

[stray reef]

the quantifiers mean "for all x in the domain" vs "there exists x in the domain"

they do not have to do directly with the definition of their domains

[hushed cedar]

Hey I was wondering if I can get help with a simple hoare triple problem

can anyone explain this to me please?

[stray reef]

if 5 is not 5 and you assign to x the value 5 then x won't be equal to 5

[hushed cedar]

but how can 5 not be 5?

doesn't that make the statement false?

[stray reef]

ex falso quodlibet

[hushed cedar]

OOOOOOOOOOOooo

I seee

[stray reef]

a.k.a. principle of explosion

[hushed cedar]

we're reasigning the value of to not be 5 right?

[stray reef]

we're setting x to 5 but 5 isn't 5

so we're setting x to something that isn't 5

[hushed cedar]

I get it thank you ❤️

[silver escarp]

Is my answer right?

[bitter moss]

hi there. so my question asks for which whole numbers is that polynomial divisible by 7

the answer is none, but what other way can i solve it without spending a whole lot of time trying all numbers from 0 to 6

(we're not allowed to use calculators thats why itd take a while to try out all those numbers)

[cerulean wind]

i want to say x^7, x^3, 2x^2 mod 7 = 0 if and only if x mod 7 = 0

yea. it follows from fermats little theorem and some modular arithmetic

[bitter moss]

ooo

i was considering fermants little theorem

[bitter moss]

but how would i go about it when i have 3 x terms

[sharp ledge]

Q1:Is there any ways to count to 4096 using just fingers ?

Q2. Determine all functions f : Q → Q that have the property
f(x+y) = f(x) + f(y) +2xy for all x, y ∈ Q.
And how do we prove that our answers are the only such functions possible?

[short geode]

Q1 is something something binary
Q2 normally if you mess around with the number 0 in those functions you can milk out some equations that point the way forwards. the other hint is dig around in the rationals. the other way is to put the same variable in.
f(a+a) = 2f(a) + 2a^2. now you got some data. so f(0) = 0 by necessity.

[weary tiger]

i have a graph theory proof that i wanna prove

and a write up

if someone could give feedback that would be awesome

Prove that the sum of the number of vertices in all biconnected components of a graph is O(n).

[royal glade]

How do we negate quantifiers without using the negation sign?

[lavish hornet]

How many different ways to put 70 identical marbles into 10 boxes such that:
b. the first four boxes contain at least one marble and not more than 2 marbles.
(combination problems that can be solved using the Ordinary Generating Functions)

[lavish hornet]

hi guys, any clues ?

[weary tiger]

use quantifier negation law

[royal glade]

Should I flip the quantifiers and change the open statement to say not equals?

[low carbon]

I dont understand b at all

I have VxA(S(x), Professor)

I guess you cant have an S(x) inside a pair

does discrete math get more difficult than nested quantifiers? shit

I also dont understand d

this is so hard to decipher

wow am I allowed to say discrete math was harder than when I was learning calculus

probably should be simple

sometimes a person means Ex other times it means Vx Im so confused

[low carbon]

ignore the above, I just dont understand f.

f seems inconsistent with the other answers because it groups one of the domains, ExF(x) together with A(x, y), a pair.
in all the other answers, the domains are grouped together. ExF(x) and VyF(y), for example

[snow sleet]

still need help with this?

ping me if you still need help with it

[snow sleet]

I'm heading to bed now since it's 1am here lmaoo but feel free to ping/dm me if you have any questions on this @lavish hornet

[lapis sluice]

Hi

I'm new here.

[weary tiger]

can anyone explain me their thought process when finding the answer to this? It makes no sense to me lol

[remote cosmos]

have you done relations yet in class?

$(a, b) \in R_1 \text{iff } a > b$

[vital dew]

pitabread

[weary tiger]

@remote cosmos yes, and I have a decent grasp of composition. What confuses me is that there are no numbers, and only a>b, a≥b etc.

[remote cosmos]

you can do small examples on a smaller range

to get a feel for it

https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf#page=213

[slate burrow]

This is my answer

[weary tiger]

hey all i have a graph theory problem im still stuck on

Prove that the sum of the number of vertices in all biconnected components of a graph is O(n)

[faint narwhal]

what is n here? The number of vertices?

[weary tiger]

yes!

number of vertices

i wasnt sure too but i got clarification about this

i had an idea for what to do but it got so convoluted that i dont think i actually know what to do

[faint narwhal]

yeah this seems pretty hard hm

[weary tiger]

yeah im so confused

i was thinking of something with articulation points?

i found this link https://stackoverflow.com/questions/58732674/possibility-number-of-biconnected-components-greater-than-number-of-vertices

but i have no idea what its actually saying in it

[faint narwhal]

This just tells you the number of biconnected components is less than n

[weary tiger]

ah ok ok

yeah

then im so confused and have no sense of direction :/

[bleak wren]

is not-symmetric the same as anti-symmetric?

[pale epoch]

for relations? no

[bleak wren]

ah ok good to know thx, im using a matrix to decide whether R is anti-symmetric

[ruby cobalt]

if the predicate evaluates to true, will the whole proposition evaluate to true regardless value of x?

[slate burrow]

i want to write a formula with two quantifiers that is false when we quantify over the natural nubmers but is true for rational nubmers. And i was wondering would this be true?

[weary tiger]

x/2 is not a statement

[slate burrow]

My reasoning is that since it says "for all x belonging to N" this formula is true, since the formula is not valid some values in N

what would be considered a statement here? Isn't just a formula a statement?

[weary tiger]

I mean that's like saying
"Bread implies Muffin"
or what we have here
"x/2 implies ℚ"

But we would need
"Bread is tasty implies muffin is tasty"

[slate burrow]

yea so if we ignore the implies sign

i understand it's wrong

would x/2 be considered true?

[weary tiger]

No it doesn't have the syntax of a formula

[slate burrow]

aha

[weary tiger]

I.e. it doesn't make sense to ask of the truth of something that is not asserting something

[slate burrow]

Right

[weary tiger]

x/2 is like the bread in my analogy, is bread true?

[slate burrow]

I understand, let me see if i can figure something out

[weary tiger]

Or is it rather true that bread is tasty?

[slate burrow]

yeah, i get what you are saying

how should i come up with something then?

Everybody in the class is stuck on this question

[weary tiger]

Well first of all it seems that your question is asking you that both of your quantifiers range over either the naturals or the rationals and not both

[slate burrow]

right, but it has to be only true for rationals

and not for natural numbers

heres the exact question

[weary tiger]

What you could do is consider the number line

When you draw in the naturals and then the rationals, what is the first thing that pops into your mind about them?

[slate burrow]

let me see

they are in the form of a/b or decimals ?

[weary tiger]

Well decimals is a good thought, specifically look at the numbers between 0 and 1, could you ever draw all the rationals in that interval?

[slate burrow]

no

there is infinite decimals

or like infinite number of rationals or numbers between 0 and 1

:3

[weary tiger]

Yeah you can make them as small as you like, so can you formulate the sentence that you can always pick a rational number in that interval that is smaller?

I.e. when you have ε > 0, then you can find q > 0 with ε > q

That shouldn't be true for the naturals

[slate burrow]

oh...

[weary tiger]

This is something you can do in 2 quantifiers

[slate burrow]

so just one question

what does q > 0 and ε > q mean?

that you can always find a rational that is smaller?

[weary tiger]

Right, for example if ε=1/100000 was given then you could always for example pick q=ε/2 to get half of that

And q is still greater than 0

[slate burrow]

aha

right

makes sense, just need to let it sink in

i see what you are saying, thanks for explaining

[royal glade]

Anybody know of an open statement that satisfies all of these requirements?

[royal glade]

Would x>y work?

[weary tiger]

Let Q(x,y) state that
x > y ∨ [y ∈ ℕ ∧ x ∈ ℕ ∧ y ≤ x]

[daring beacon]

¬(p → ¬q) ↔ (p∧q), how do you prove this using only rules of inference ? What I know so far is that you start with an assuming the left side is true, but I don't even know the exact reason for that either. Can someone help me ?

[bleak wren]

does the order of a set of ordered pairs matter?

[daring beacon]

@bleak wren idk what you mean by the order of a set of ordered pairs if you're talking to me

[bleak wren]

sorry i didnt ask very well i basically mean

is R = {(a,b), (a,a)}
the same as
R = {(a,a), (a,b)}

[daring beacon]

@bleak wren sorry I still don't know what you mean b/c I don't have a b or R in my equation

[bleak wren]

sorry ill be back to help in about 10 minutes

[bleak wren]

¬(p → ¬q) is the same as ¬p → q

because of double negation (two negatives make a positive ie.
¬¬q = q

actually im not sure i can help you apoplogies (hope that at least helps lol @daring beacon )

[bleak wren]

this was me asking a seperate question of my own @daring beacon

[weary tiger]

does anyone have any insight about this

[cerulean wind]

yes

[cerulean wind]

this is not right

[cerulean wind]

p --> ~q is ~~ ~p v ~(~q)~~ ~p v ~ q

[plush dock]

Hey. I'm trying to figure out what I've done wrong with this problem (since it obviously went very wrong)

I need to find the total number of options in integers (including 0) that would be true for this equation

My intuition was D(3,13) * D(6,11)
The D(3,13) making sure that the first three x's has more than the other three, and then D(6,11) to 'spread' the among all 6
But obviously the answer here is wrong, as it gives a result that is much bigger than the actual result (which is 55,237).
I know how to solve it now since I saw the solution and I understand it, but I'm trying to figure out how and why my solution is faulty, and what am I intuitively missing here?

Thanks !

[snow sleet]

[p-> ~q] is equivalent to [~p v ~q].

[regal hamlet]

Can anyone double check my work pls

[cerulean wind]

my bad, typo

[weary tiger]

which part

or all of it

the bottom part is right

the top is not

up to line 5 was correct

from there you made a mistake with the negation symbols

[regal hamlet]

yeah something didn't seem right about it but couldn't figure it out

[mystic elbow]

hi

[royal glade]

Is this expression a mathematical statement or an open statement? “There exists an even integer b and an integer m, Q(a, b, m)”

[sand cipher]

this is wrong rite?

cuz x can be 1

just asking cuz that's what my professor answer and i thought did i do smthing wrong or was ti a mistake

[robust mango]

The statement is true. There does exist a natural number such that it's less than or equal to every natural number and yes that natural number(x) is 1.

[marble pivot]

How can I prove this? $$\sum_{i=0}^{n-1} \left(2^i\right) + 1 = 2^n$$

[vital dew]

abs_0

[weary tiger]

Are
not p implies q
And
P implies not q
Logically equivalent

[red nest]

No, let p be true and q be true

[terse rune]

https://en.wikipedia.org/wiki/Mathematical_induction

[celest plover]

Can someone tell me if this looks right?

or am I missing something?

[mint bane]

if i have a group of 6 people labeled A and 8 labeled B, and i draw 3 from each group, what are the odds that A_1 and B_1 both get drawn

[snow sleet]

please don't post your question in different channels

[marble pivot]

It’s right, but I think it could be cut down a bit.\

If you define $A \times B$ to be $${x \mid \exists a \in A,\exists b \in B, x = (a,b)},$$ then you can just say since there’s no elements in $A = \emptyset$, the statement ``$\exists a \in A$’’ is always false, so there cannot exist any $x$’s with $x = (a,b)$, and thus $A \times B$ is empty.

[vital dew]

abs_0

[celest plover]

I see, thank you!

[marble pivot]

Ye

[vital dew]

abs_0

[celest plover]

Okay

Oh oops

Didn't notice that

[serene drift]

anyone want to explain to me which ones are true and why?

[marble pivot]

A is true because all the elements of {1} are elements of N

B is false because Ø is not an element of N

[serene drift]

so is {1} ⊆ N the same as 1 ⊆ N?

[marble pivot]

No not at all

{1} is not the same as 1

A \subset B means all the elements of A are also elements of B

For {1} \subset N, all the elements of {1} (literally just the number 1) are elements of N

[celest plover]

1 = {\emptyset}, right?

[marble pivot]

For 1 \subset N, 1 is not a set so it doesn’t really have elements

I have a feeling they haven’t done that yet though, isn’t that some construction of numbers or something idk

[celest plover]

Yeah

[marble pivot]

Well it’s still false right, cause the empty set isn’t an element of N

[celest plover]

Yeah

Still false

[marble pivot]

C is true because it satisfies the definition of subset. If ur confused b/c there’s no elements in Ø, read this

[cloud lotus]

Need assistance guys

[last timber]

what have you tried

and where are you stcuk

[spare gull]

Sorry to interrupt, anyone know how to tackle this Q?

[mystic elbow]

Can anyone please help

[stray reef]

@mystic elbow do you still need help with this?

[mystic elbow]

Yes

[stray reef]

what's this I supposed to mean?

[tepid bay]

Can anyone help me on this lil problem?

How many 7-digit numbers (without leading 0's) contain two 5's, two 0's, and three 4's?

[mystic elbow]

Integer ig

@stray reef

[stray reef]

so $\bZ$

[vital dew]

Ann

[stray reef]

and $I^+$ is supposed to denote the positive integers?

[vital dew]

Ann

[stray reef]

@mystic elbow in any case, how familiar are you with set-builder notation?

[mystic elbow]

No

[stray reef]

no as in you've never seen it before?

[mystic elbow]

Yes it’s my first time doing all this

[stray reef]

ok do you at least know what a set is

[mystic elbow]

Yes

[stray reef]

set-builder notation comes in two forms, only one of which is in use here, so i'll try to explain that
{x in <set> | <criterion>} describes the subset of <set> consisting of all objects that satisfy <criterion>

the variable at the beginning doesn't need to be x specifically, it can be anything not used elsewhere

for example:
{n in N | n is even and less than 9} = {2, 4, 6, 8}

do you understand this?

[mystic elbow]

Yes

[stray reef]

is this explanation sufficient for you to do question 1.2?

[mystic elbow]

Hmmm I maybe but can u solve one question then I’ll get a better idea

[stray reef]

i am not going to do any of those questions for you.

[mystic elbow]

i understand this

but can u explain what does the q mean

[stray reef]

the question presents you with some sets and wants you to write them down in list-of-elements notation.

[mystic elbow]

does it mean i need to find no. less than than

square numbers

[stray reef]

{x in Z | x^2 < 10} consists of all integers whose squares are less than ten.

[mystic elbow]

so -3,-2,-1,0,1,2,3 ? @stray reef

how about 3,4?

[stray reef]

this but with {} around it

for 3 and 4 you will need to know about unions and intersections

[mystic elbow]

Yes I know that

I’m trying to find

[stray reef]

write down the sets {x in Z+ | x^2 < 10} and {x in Z+ | 2<x<8}

then unite them for 1.3 and intersect them for 1.4

[mystic elbow]

Unite as in the conman numbers

Ya?

[stray reef]

unite as in take the union.

[mystic elbow]

So common numbers

[stray reef]

idk what you mean by "common numbers"

but that sounds suspiciously like intersection and not union

[mystic elbow]

intersect is 3

union are 4,5,6,7 and -3,-2,-1,0,1,2?

@stray reef

[stray reef]

........

[mystic elbow]

?

[stray reef]

first off you are forgetting braces

the intersection is {3}

the union is not "4,5,6,7 and -3,-2,-1,0,1,2", nor is the union {4,5,6,7,-3,-2,-1,0,1,2}

the union is {-2,-1,0,1,2,3,4,5,6,7}

i think you have severely misunderstood what the word "union" means

also keep in mind that the "or" in the definition of union is inclusive

any point that happens to be in both of your two sets is also a member of their union

[mystic elbow]

Ohhhhh

Sorryy

I see it know

Union is the entire thing

I mixed up

[mystic elbow]

How about -3

[stray reef]

wait hold on

[mystic elbow]

Shouldn’t it be included

[stray reef]

...

no it shouldn't and neither should -2, -1 and 0

we are looking at positive integers now

i missed it when i was trying to explain to you what union is

[mystic elbow]

Ohh right

But why not include 0

[stray reef]

0 isn't a positive integer.

[mystic elbow]

neither negative nor positive

[stray reef]

we are looking at positive integers now

0 isn't a positive integer

does this answer your question of "but why not include 0"

[mystic elbow]

Yes got it now

Thank you so much

Now I’ll never forget what union and intersect means 😅

[lofty night]

Hello is this channel being used?

I assume not but still want to make sure

[minor lake]

read above

also i think channels being used is only a thing in help channels

[lofty night]

alright

well i am having a bit of trouble with domains and predicates as well as writing them into quantified statements

like the sentence "all chihuahuas bark at passing cars" how would you approach it?

[outer hinge]

This is really bugging me. My professor told me to write a truth table to understand DeMorgan’s law

Why is it the case that ~p and ~q is false unless both p and q are false ?

Why is it different from other or statements like p or q

I understand the “not” is modifying them, but I’d think that if that was the case it would just mean p and q couldn’t be true

Both at the same time

[minor lake]

idk, all is pmuch forall quantifier, for chihahua i think it depends whether or not chihahua are the only stuff being considered but I'd just consider it to be an object in a set, as for bark at passing cars it's just the same ig

[minor lake]

because if each one of them is false they become true because of the not

not(false) and not(false)

true and true

true indeed

idk maybe as a programmer it's just too trivial but idk how i can dumb it down more

[outer hinge]

Can it be the case that ~p or ~q can be true if either ~p or ~q are false ?

So long as one of them is true ?

Here is my edited truth table

[left kindle]

@outer hinge have a feeling this might apply here

with ~p V ~ q if either one of them is true the other would be false

but please confirm since im still learning discrete

[worthy mist]

To answer both of your questions. The first one was when is ¬p ∧ ¬q true. Now lets think about this without truth tables for a moment, when is the conjuction (aka logical and) of two statements true? When both the left and the right side are true. So when is

1. ¬p true
2. ¬q true

well ¬p is true if and only if p is false, ¬q is true if and only if q is false. So this means ¬p ∧ ¬q is true if both p and q are false.

Secondly for ¬p ∨ ¬q. When is the disjunction (aka logical or) of two statements true? When either the right, or the left side is true (this of course also implies that its true if both sides are true since then for sure the left side is true as well). So again when is either

1. ¬p true
   2.¬q true

As we know from above ¬p is true if p is false and ¬q is true if q is false. Hence ¬p ∨ ¬q if one of the following is true:

• p is false
• q is false
• p and q are both false

[nocturne obsidian]

How would you approach c or d in this case?

[keen parrot]

Think about parity (on the number of true statements)

Are you allowed to use XOR? If so, it would be much easier

[left kindle]

a.) p <-> q, (since logical equivalence uses XNOR)

b.) (P v Q) /\ ~ (P /\ Q)

[brave magnet]

Please give me a starting hint there. Source is Diestel GT Chapter 7 Problem 11

[atomic osprey]

Choose among the m vertices a set of vertices that are still incident with as many edges as possible. - This is the hint Diestel gives

[brave magnet]

ah thanks. got it

[atomic osprey]

How can I show that a vertex transitive, non-cycle, two connected graph is actually three connected?

Without using the idea that you can get biconnected graphs only from adding H paths successively to a cycle

[slate burrow]

I am trying to prove this is true for n >= 2, and i am sort of stuck on the assume part of the induction. For the step case i have P(k) >= P(k+1) for k >= 2. And i was wondering how do i write for the assume part for P(k)? Should it be 1,2,3....k=2^k+3^k>4^k?

[vale cairn]

'Assume for some k >= 2 that 2^k + 3^k < 4^k'

and then you must prove that 2^(k+1) + 3^(k+1) < 4^(k+1)

[slate burrow]

i don't need to write 2,3,4..k?

alright let me see if i can prove it:)

lord why do we have proofs in math 😩

why can't we just show for some values and be like ok this holds and say screw proofs

[slate burrow]

I can't figure it out, any ideas what i can do? :)

[vale cairn]

Assume 2^k + 3^k < 4^k and note that 4^(k+1) = 4 * 4^k

[slate burrow]

i am doing that but i'm sort of stuck

2^k is same as 2 * k

[vale cairn]

Sure, so what can we way 4 * 4^k is larger than?

[vale cairn]

It isn't (except k = 2,1)

[slate burrow]

:/

[vale cairn]

2^k = 2 * .... * 2, not 2 + ... + 2

[slate burrow]

Isn't this one same as 4^k+1?

[vale cairn]

Yup, 4^(k+1)

[slate burrow]

That's it?

[vale cairn]

But I put it in that form so we can make use of the fact 4^k > 2^k + 3^k

Hence 4^(k+1) = 4 * 4^k > 4 * (2^k + 3^k)

[slate burrow]

right

[vale cairn]

can you show that that is larger than 2^(k+1) + 3^(k+1)?

[slate burrow]

i believe i can

let me try

[vale cairn]

sure gl

[slate burrow]

i also got this, but when i tried it for some values k it was false, but when you mentioned "can you show that that is larger than 2^(k+1) + 3^(k+1)?" I believe i can see the solution

[slate burrow]

No, i'm sorry i can't do it. After a bit of thinking, this is what i came up with, and i am 100% sure it's a illegal move. To write 4 *(2^k+3^k) as (2^k+1)+(3^k+1), the only thing i can come up with is to re-write for instance 8^k as 2+2 *2 *2^k, i can then convert 2 * 2 to 2^k+1, but that is obviously wrong.

but i know 2+2* 2 * 2 is wrong :/ i thought i saw it before, but i was mistaking

oh 2^k+3^k is 2^k+1 + 3^k+1 because of our induction hypotheses no?

[vale cairn]

No, those aren't equal from the hypothesis

You can't write 4* (2^k + 3^k) 'as' 2^(k+1) + 3^(k+1); our goal is just to show 4*(2^k + 3^k) > 2^(k+1) + 3^(k+1)

it might help you if i expand it: we need to show that 4* 2^k + 4* 3^k > 2* 2^k + 3*3^k

[slate burrow]

Right, exactly

[vale cairn]

Do you see why that's the case?

[slate burrow]

i do see why we need to show this 4* 2^k + 4* 3^k > 2* 2^k + 3*3^k, but expanding does not make it clearer :/

[vale cairn]

Firstly 4 * 2^k > 2 *2^k

[serene drift]

is my order wrong or am i missing something?

[cerulean wind]

urs is the right most list, right?

[serene drift]

yea

[cerulean wind]

i think its just stated incorrectly. you should use contradiction. i would start by swapping the upper right and left terms

[snow mango]

Could someone explain to me what the question is asking?

I dont know where to start

Ive been trying to learn discrete maths on my own

[pale epoch]

you are supposed to show T(n) <= nlog(n) + n - 1

[south badger]

Let $a \in \mathbb{R} : f : (a, \infty) \rightarrow \mathbb{R}$

[vital dew]

Hellboy

[gritty crescent]

[gritty crescent]

@short lynx Check the definition of unit element e.

[analog venture]

Combinatorics questions go here?

Like introductory level questions

[weary tiger]

can somemone help me in math im not good at math

[gritty crescent]

Sure, this channel should be fine.

[proud summit]

For (a), how is f surjective??

[gritty crescent]

Can you find an element in S that is not mapped to by f?

[gritty crescent]

(Bear in mind that f(n) is the remainder when 5n+2 is divided by 12. What are the possible values for remainder?)

[proud summit]

This is just rough working I did

[gritty crescent]

Well, a is not equal to (5n+2)/12, but rather the remainder when 5n+2 is divided by 12.

[proud summit]

Ohhhhh my brain

[gritty crescent]

Can you take it from here?

[proud summit]

Lmao I wrote my f incorrectly 😂

[proud summit]

Yep I should be able to take it from there

[gritty crescent]

😛 I hope you can fix it

[slate burrow]

can i divide with 2?

sorry for late response, i went to bed. If you don't want to help anymore it's all good

[vale cairn]

I'm fine w helping further. This just follows because both sides are positive and 4 > 2

[slate burrow]

Right. I came to that conclusion as well. But i don’t understand what that proves

Because we proved that 4^k = 4^k+1

[vale cairn]

We didn't prove that, when do you think we did?

That would be equivalent to saying 4 = 1

[slate burrow]

I thought that we proved it by multiplying it with 4. > 4^k became 4•4^k <-> 4^k+1

So we didn’t do it. But why is this 4>2 important? Does it prove something? :)

[weary tiger]

whats the relationship between biconnected components in a graph and the number of vertices?

i know its a factor of n because articulation points overlap but im not sure beyond that

[vale cairn]

4 > 2, so 4*2^k > 2 * 2^k

Similarly 4*3^k > 3 * 3^k

[atomic osprey]

What does 'k-hop' mean in the context of graph theory?

Is it the set of vertices at a distance k from some vertex? I just saw it in a post

[weary tiger]

if someone knows pls ping me ❤️

i have been struggling on this same problem for over a week now 😢

[faint narwhal]

@weary tiger try posting in #combinatorial-structures tbh, you might have more luck there

[weary tiger]

darn

[weary tiger]

i thought bc its graph theory it could go here

[faint narwhal]

I mean thats true

it does fit here well

but its just that higher level people tend to only look at the advanced math channels and this is a pretty hard question so you might have more luck there

[weary tiger]

i have a small hint

that the articulation pts are overlapping

hence why its k * n

[weary tiger]

but that feels like saying its n because its n hahah

ok i will post there too

[weary tiger]

are dfs graph traversals easy to follow?

[shell lagoon]

not sure if this is the right place to put this

Σ = {a, b}. We write #a(x) for the number of occurrences of
the letter a in the word x and similarly for #b. We claim that
∀x ∈ Σ∗, ∃y, z ∈ Σ∗ such that x = yz ∧ [#a(y) = #b(z)].

I understand that if you take any string this will be true, but I don't know how to prove this without loss of generality, any ideas?

[solid garden]

hi yall i was kinda lost on a problem regarding rules of inference

honestly not sure where to even start with this one, watched videos and reviewed the notes but this problem has been kind of an outlier, was able to do everything else

Problem:

Prove the following using the basic rules of inference:
(∀𝑥|𝑥∈𝐷:(∀𝑦|𝑦∈𝐷:(𝑊(𝑥)∧𝑈(𝑥,𝑦))→𝑃(𝑥)))
(∃𝑝|𝑝∈𝐷:(∃𝑞:𝑞∈𝐷:𝑊(𝑝)∧𝑈(𝑝,𝑞)))

∴(∃𝑧|𝑧∈𝐷:𝑃(𝑧))

if i could get some help on how to do this or where to start that would be great

[snow sleet]

I can help with this

(∃𝑝|𝑝∈𝐷:(∃𝑞:𝑞∈𝐷:𝑊(𝑝)∧𝑈(𝑝,𝑞))) is saying that there are p and q such that W(p) and U(p,q)....now (∀𝑥|𝑥∈𝐷:(∀𝑦|𝑦∈𝐷:(𝑊(𝑥)∧𝑈(𝑥,𝑦))→𝑃(𝑥))) guarantees that for such p and q, we have P(p) since we have W(p) and U(p,q). So we have that there exists an element z in D such that P(z)...namely, that element is p.

make sense @solid garden ?

[solid garden]

That makes sense, thanks!

[snow sleet]

You're welcome!

[solid garden]

I’ll get back to you if I can’t get past that

But that makes sense so I should be able to

[snow sleet]

yeaa we can vc about it if you want and I can prolly explain it better if that works for ya

pretty much since (𝑊(𝑥)∧𝑈(𝑥,𝑦))→𝑃(𝑥) holds for all x,y in D, it must also hold for such p and q (which are also elements of D). So (𝑊(p)∧𝑈(p,q))→𝑃(p). Since we had (𝑊(p)∧𝑈(p,q)), by modus ponens, we have 𝑃(p). Hence we have P(p) for some p in D.

(i.e., we have P(z) for some z in D)

[wild dust]

Could someone explain how to proof the 5.5? please
The exercise is about permutations in lists, the triangle is constructor for the list like "a (cons x L)" and the other is the concatenation between 2 lists
I know that is with induction on L but a I don't know how to start

[weary tiger]

How do they know the second last part is true?

Wouldn't it be only a subset?

[stray reef]

@weary tiger every point in the union of A_i is also in the union of B_i

take $x \in \bigcup_{i=1}^{\infty} A_i$ and let $n = \min{i : x \in A_i}$, then $x \in B_n$

[vital dew]

Ann

[weary tiger]

Ohhhh I see

[hybrid ether]

Hello, why order of -1 is 2?​
|-1| = 2. But how?​

[sour arrow]

Please avoid multiposting #proofs-and-logic

[hybrid ether]

@sour arrow
https://c.tenor.com/FCdeOWK8r-YAAAAM/venky-brahmi.gif

[gritty crescent]

Please avoid all this in question channels, #chill

[hybrid ether]

@gritty crescent I'm sorry

[slate burrow]

Can somebody verify if i did this proof correct or not? Any feedback is appreciated. :)

Question: Prove by simple induction on **n **that the proposition is true for all **n≥2. **

2^n+3^n < 4^n (please tag me)

There is just one thing that is unclear, why can one assume the inequality is true and say "since 7^k > 0"

it suppose to be 2*2^k + 3^k, 7^k is wrong apparently

[proven silo]

Uh seems very weird what you are doing. First show base case if you haven’t then just use 4^(k+1)=4 * 4^k then apply inductive hypothesis on 4^k and arrive at it being greater than 2^(k+1)+3^(k+1)

[vale cairn]

Also your assumption should be different, you can't just assume the inequality holds for all k >= 2 - just assume it holds for some k

Further you have said 7^k = 3^k + 4^k implicitly on the penultimate line, which is false...

[slate burrow]

ok no more criticism pls

[slate burrow]

oh so i just wanted to see if the induction part is true or not. I have tried for the base case which is 2 and it holds, it holds for greater or equal to 2.

[slate burrow]

yeah my friend corrected me on that, 2*2^k+3^k is the correct one.

i assume it holds for k meaning 2^k+3^k<4^k and then i want to somehow convert it to 2^(k+1)+3^(k+1)<(4^k+1), right?

[proven silo]

Then you assume true for n=k and want to show its true that
4^(k+1)>2^(k+1)+3^(k+1).
Use the hint I gave above to rewrite 4^(k+1)

[slate burrow]

ok, could you please guide me through this?

im gonna get some paper

[proven silo]

Start with 4^(k+1) and use what I said here

[slate burrow]

just 4^(k+1) or the entire inequality? 4^(k+1)>2^(k+1)+3^(k+1).

[proven silo]

You want to show that inequality

So you can’t start there

[slate burrow]

alrighty

so

[proven silo]

Just write equal lol

[slate burrow]

alright

i want to show that this is greater than 2^k+1 + 3^k+1

aha

[vale cairn]

lol

[proven silo]

What did I say you should do now then?

[slate burrow]

i thought you could use <-> if you wanted to state that these two functions (not sure what we call them) are the same

apply the I.H

one sec thinking

oh so the I.H is

ah

what is the inductive hypotheses

4 * (2^k+3^k)

[ornate cliff]

A ={a,{a},{{a}}},  B={∅,{a},{a,{a}}}

What is the A ∩ B? I think it’s
A ∩ B = {a}

Can you pull out {{a}} from set B’s {a,{a}} with an intersection? Is it the same element as set A’s {{a}}?

[vale cairn]

It's {a} yes

{a, {a}} is not {{a}}, as a is not in {{a}}

[ornate cliff]

So they are different elements?

[slate burrow]

yes

[ornate cliff]

Great, thank you!

[slate burrow]

you talking about intresection between a and b

[ornate cliff]

Yes

[slate burrow]

whatever that's in A and B together

[weary tiger]

could i ask about a

dfs graph traversal here?

i filled out a chart but im kinda sus about 2

[weary tiger]

Hello

[weary tiger]

im trying to do a dfs traversal
is it possible to have the low for a node change twice?

is it possible for b to have a low 2 of 1 and d to have a low 2 of 2?

[analog venture]

I mean the answer just has to be 6 Choose 4

But I don't get why

not sure if this is the best place to ask but well se

see

I would appreciate if someone could walk me through this maybe

[olive wraith]

did not understand this

[faint narwhal]

@olive wraith what did you not understand?

[olive wraith]

how it is not inversible

[faint narwhal]

If you tried to invert it, how would you define f^-1(4)?

[olive wraith]

i did not understand that

[faint narwhal]

Do you know what an inverse is?

[olive wraith]

https://www.youtube.com/watch?v=V8DiyyO7JcI&ab_channel=WellAcademy

yes

i took this lecture also and read from discrete book too

it only apply on one to one and onto

I have that much concept but I m not good at math but I want to learn discrete math I m very fond of learning math

[weary tiger]

Maybe an example will help, let's say domain of x squared is not all real numbers, but just 2, -2 and 3 so when you square these three numbers you get {4, 4, 9} and this is a function because it is allowed for two different inputs to give same output (both 2 and - 2 give 4) but inverse of x squared is square root of x and as you're taking inverse, your codomain {9,4 ,4} becomes domain and your domain becomes codomain {2, -2 , 3} and this is not a function since square root of number 4 gives both 2 and -2 which is not allowed for a function to do. This basically means that you will not get function when you inverse x squared.

https://www.youtube.com/watch?v=6u9Qh1Vi_Qw

the second graph in the video is basically x squared only shifted down, so it should help

[olive wraith]

thnx

[weary tiger]

Can someone help me with time complexity exercise , I obtained BigTetha(n^4) as a solution for worst case and BigTetha(1) for best case since for best case I took n=0 but yet my teacher gave us a solution where he gave O(n^3) for best and worst case which I don't think it is correct

[last timber]

@weary tiger this algorithm is O(n^3)

n = 0 does not mean it is O(1)

[weary tiger]

hmm why?

no this is my work

[last timber]

you do not plug specific values for n

[weary tiger]

best case :
     n=0 
     complexity O(1)
     worst case :
     T(n)=c1+Sum from i=0 to i=n*n -1 of (Sum from 0 to i-1 of (c2))
     T(n)=c1+c2(Sum from i=0 to i=n^2-1 of ((i)) )
     T(n)=c1+c2((n^2-1)(n^2)/2) which is BigTetha(n^4)

[weary tiger]

it is just for best case

[last timber]

no

best case would be say like if you had
if n == 0 return

then it would be O(1)

but your algorithm constantly performs O(n^3) operations

[weary tiger]

I don't really understand , By best case I meant : specific case

when n=0

and for worst case I took n as variable that goes the infinity

[last timber]

no this is not how it does work

[weary tiger]

if best case was the same as worst case then no need for best case

[last timber]

you have input of length n

what is performance of algorithm on n?

you do not know if n = 0 or n = 1083219382183912873

[weary tiger]

yeah

it is O(n)

[last timber]

no

it is O(n^3)

[weary tiger]

what is the work that led to O(n^3)

I showed you my work that led to BigTetha(n^4)

how is it wrong

[last timber]

and for each of it n^2 operations there is exactly i operations

first loop is n^2 operations

[weary tiger]

yep

[last timber]

look, for each step of loop you do i summations

you this n^2 times

[weary tiger]

each time i increments I do a loop from 0 to i

and i increments n*n times

like show me math proof like I wrote

[vital dew]

Commander Vimes

[weary tiger]

you meant i=0

not k

[last timber]

it does not matter

[vital dew]

Commander Vimes

[weary tiger]

yeah alright

but it is not just a series from i=0 to i=n^2

you also have an inner one

from j=0 to j=i

[last timber]

no

at each step i have exactly k summations

[weary tiger]

nope

try it

[last timber]

wdym no

[weary tiger]

it is a summation inside a summation

you have another inner summation from j=0 to j=i

try it by hand and see the total number of iterations

[last timber]

yes and inside loop takes exactly i sums

and there is n^2 such loops

[weary tiger]

yeah but i increases for each iteration

it is not a fixed i each time

[last timber]

yes but i do not say i is constant

[last timber]

this is formula

[weary tiger]

this is for the inner loop?

[last timber]

this is for both loops

[weary tiger]

nope

[last timber]

summation is outer loop

[weary tiger]

this is wrong

[last timber]

ok, do it by yourself then

[weary tiger]

it shuld be Ki

not K

Ki

dude I just tried it

[last timber]

i am not interested in repeating what i said again and again until you get information correctly.

[weary tiger]

the summation you gave didn't work

just go try it

omg I tried it I swear

I didn't get a correct amount of iterations

just try it

Take n=2 , total amount of iterations is 0x0 + 1x(1+1) +2(1+1+1) +3(1+1+1+1)+4(1+1+1+1+1)

[last timber]

,w sum k from k = 0 to 100^2

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#4407

[weary tiger]

,w sum k from k=0 to k=4

[vital dew]

Results provided by WolframAlpha

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

Requested by Joseph 9#9722

[weary tiger]

0x0 + 1x(1+1) +2(1+1+1) +3(1+1+1+1)+4(1+1+1+1+1) this gives 40

not 10

[last timber]

,w sum k from 0 to 10^2

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#4407

[weary tiger]

dude , I am sorry I am not here to argue with you

I apologize if I sounded rude

[last timber]

,w sum k from k=0 to 10^2

[weary tiger]

just that I am a bit angry

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#4407

[last timber]

ok so yes lost 100 iterations somewhere

[weary tiger]

yeah this is what i was referring to

the summation must be wrontg

dude my professor is so fucking retarded goddamit

[last timber]

oh

i got

upper bound of sum is wrong

n^2-1 is correct upper bound for n > 0

[weary tiger]

yep

but since you are going from n=0

you can start from 1

and go to n^2

not to n^2-1

[last timber]

no this breaks again

[weary tiger]

same number of iterations

[last timber]

the point is that n^2 is not included in outer loop

[weary tiger]

yeah I got that

try again

it stills give a wrong number

[last timber]

no this is wrong from your side

since code agrees with this

[weary tiger]

,w sum k from k=0 to (10^2-1)

[last timber]

run this code by urself

[vital dew]

Results provided by WolframAlpha

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

Requested by Joseph 9#9722

[weary tiger]

hmm this is weird

,w sum k from k=0 to (4-1)

[vital dew]

Results provided by WolframAlpha

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

Requested by Joseph 9#9722

[weary tiger]

?

didn't work

[last timber]

yes code gives this amount of iterations

[weary tiger]

let me try it

n=4 right?

[last timber]

n = 2

[weary tiger]

yeah n^2=4 I meant

n=2

yeah the summation is correct

exactly what I did in my work

I did it here

     T(n)=c1+c2(Sum from i=0 to i=n^2-1 of ((i)) )
     T(n)=c1+c2((n^2-1)(n^2)/2) which is BigTetha(n^4)

here I got i=0 to i=n^2-1 of (i)

which is the same as the summation you gave me

I don't understand why are we arguing lol

what I am arguing about is that it is not O(n^3) it is O(n^4)

[last timber]

actually sorry i am idiot

[weary tiger]

dude I got so confused

what is happening

[last timber]

,w sum k from k = 0 to k = n^2

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#4407

[last timber]

yes it n^4

[weary tiger]

yeah finally so much cofusion from my part too , I am actually multitasking and I thought the k that you wrote was a constant

not realizing it refers to i in the code lol

and yeah it is n^4

my bad

and thank you

see my professor is dumbass

[weary tiger]

What is this... \😬

[pale epoch]

a set?

[coarse cave]

can someone explain this modulo question

2x ≡ 2 (mod 8)

like what does that mean

<@&286206848099549185>

[proven silo]

that you have to find x such that 2x = 2 mod 8?

[coarse cave]

ya i guess so

this is the exact questipn:

[proven silo]

the trivial solution should be very obv

what x fulfils 2x = 2 mod 8?

[coarse cave]

I have no clue tbh we just learned modulo

I understand the mod part

[proven silo]

2 = 2 mod 8?

[coarse cave]

I draw out a circle and have the remainders

so for what x does 2 have a remainder of 2?

[proven silo]

that is not the question?

find x such that 2x = 2 mod 8

x=1 is very obv a solution

2 = 2

[coarse cave]

oh I didn’t think it was that straight forward

lmao thank you

[coarse cave]

I’m not sure what to put here

<@&286206848099549185>

well the first two are wrong

Nvm got it

[stable vessel]

wait this is impossible right

D cant contain 1 or 3 (or else D x D would remove (1, 1) or (3, 3)) so {1, 3} subset of A, B and so theres nothing that can remove (1, 3) or (3, 1)

[faint narwhal]

yeah that makes sense

[daring beacon]

does anyone know how to solve this or at least lead me to some online resource that might help me to solve it

[weary tiger]

$\neg{\forall{x\in\mathbb{R}}(x^2>{x})}$

[vital dew]

jswatj

[weary tiger]

simplify this @daring beacon

[winter shore]

can I get help understanding proof by cases

[daring beacon]

how ?

[weary tiger]

Use quantifier negation laws

[lavish hornet]

hi guys, i wanna ask about this.. what is the initial equation ?

I don't have any ideas

(x+x^2+x^3+x^4+3+...)^4 x (1+x+x^2+...)^8

is it right ?

[boreal lark]

hey guys, im having trouble with a Big O proof problem thing

i have let f(n) = n h(n) = n^2 g(n) = n^3
and have proved that f(n) and h(n) = O((g(n)), but i dont know how to prove that the sum is equal to Big O g

i need to get to to n^2 + n <= n^3

from 1<=n

<@&286206848099549185>

[daring beacon]

how would I use rules of inference to prove this is invalid

[last timber]

@daring beacon how would you state all sentences in logic way?

[snow sleet]

this fallacy has a name....try write writing things symbolically to see this

[daring beacon]

solved, thanks all

[fossil torrent]

Hi just kinda need help working through this would really appreciate a discord call or something to really walk through it.

The work I have so far

<@&286206848099549185>

[weary tiger]

Does anyone know a good way to think about this?

<@&286206848099549185>

[analog sonnet]

What's A

What's F_Tom

What's S

[weary tiger]

Sorry @analog sonnet

[analog sonnet]

Still don't know what A and S are

[grave totem]

Probably there's some kind of relation defined beforehand which you forgot to mention

[weary tiger]

Nope. It doesn't matter what A and S are.

The set describes a as being part of A. At the same time (a, Tom) is a part of S - thus A ∈ S since a ∈ S and a ∈ A.
Therefore A must be a subset of S.

[grave totem]

[analog sonnet]

...

[weary tiger]

A and S are not defined

[analog sonnet]

So you've given the full question?