discrete-math

[obtuse lance]

actually does transitivity imply reflexivity? wew

[spring hound]

No, you can take a transitive relation and then add an element to the set that doesn't appear anywhere in the relation. That preserves transitivity while ruining reflexivity.

[analog hound]

Oh, true.

[waxen vessel]

I'm a high school student doing graph theory for a research project. I want to maybe study ramsey theory in depth but would that be too complex?

as in would it require too much prerequisite knowledge?

[little prism]

what do you mean with indepth

[waxen vessel]

well I'd want to use it to prove certain results

[narrow prism]

Hello, I have not been able to solve this in some days now, could anyone give me some help?

[chilly dew]

I have a puzzle:

Using only $\forall, \exists, \land, \lor. \neg$, and the arithmetic operations ~$+, \times, =, >, <$, construct an expression $\varphi(n)$~ that is true if and only if $n$ is a power of three. The tricky part is you can't use exponentiation.

[vital dew]

mrean

[chilly dew]

oh wait

all the proper factors must be divisible by three

that is a necessary and sufficient condition for powers of three

nice

[snow cedar]

how they get this?

[fierce quartz]

Does anyone have any resources on probability in discrete mathematics

[fierce quartz]

I'm stuck anyone have any insight?

[reef juniper]

I advise you learn ur venn diagram and set notations.

[fierce quartz]

Yeah that's what I'm doing. Here's the thing amigo.... a) should be 4

[weary tiger]

ah venn diagram

[reef juniper]

u r correct.

[fierce quartz]

I'm not running completely blind

[reef juniper]

i did a probability paper

do u want some notes?

its an introductory course so it covers lotta things

[haughty garden]

split any path into three parts. We first need to find all paths from (0, 0) to (7, 6). We need to go down 6 times and right 7 times (in any order). Therefore, you can think of it as arranging 7 R's (right's) and 6 D's (down's). Then do the same from (7, 6) to (12, 9) and (12, 9) to (17, 12)

[reef juniper]

Let a be an element of set A,

a is a natural number therefore a is even or odd.

Case 1: a is odd, let a = 2k + 1, k is an element of Z.

a^2 = 4k^2 + 4k + 1,

Therefore a^2 % 4 = 1.

Case 2: a is even, let a = 2k,
a^2 = 4k^2

4k^ 2 % 4 != 0.

Therefore, A is the collection of odd natural numbers.

Let b be an element of set B,

b is a natural number therefore b can represented as even or odd.

Case 1: b is odd, let b = 2l + 1, l is an element of Z.

l^2 = 4l^2 + 4l + 1
l^2 = 4l * (l + 1) + 1
l^2 = 8m + 1

8m+1 % 8 = 1

Case 2: b is even, ;et b = 2l.

l^2 = 4l^2.

4l^2 != 1.

Therefore B is the collection of odd natural numbers.

Since A and B are both the collection of natural numbers. They are equal.

IS THIS ENOUGH AS A PROOF?

[stray reef]

Case 2: a is even, let a = 2k,
a^2 = 4k^2

4k^ 2 % 4 != 0.

why are you saying 4k^2 % 4 ≠ 0?

also you've got some missing words towards the end

[reef juniper]

Oh shit I meant != 1

[reef juniper]

What am I missing?

[stray reef]

Case 2: b is even, let b = 2l.

l^2 = 4l^2.
this is false as written. did you mean (2l)^2 = 4l^2?
4l^2 != 1.
sure it's not equal to 1, but did you mean that its residue mod 8 is not equal to 1...?
Therefore B is the collection of odd natural numbers.
correct
Since A and B are both the collection of natural numbers. They are equal.
missing the word "odd"

[dusty juniper]

is this correct? $\sim (x \in X \land y \in Y) = (x \notin X \lor y \notin Y)$

[vital dew]

Odd_the_Wolf

[broken sonnet]

are you trying to show a negation?

by DeMorgans Law, that is correct

[rapid mural]

btw tip instead of sim

\lnot

[dusty juniper]

oh thank you!

[robust kettle]

Anyone able to chime in on this one about sets?
Suppose you have two nonempty sets, A and B, and that A ⊆ B. Let C be a set.
Must (A \ C) be a subset of (B \ C)?

[tight hound]

Yes.

[weary tiger]

Can anybody tell me what's going on here? WHy does it resolve to just one set? [-4, 4]

[brave rock]

{0} is a subset of [-1, 1] is a subset of [-2, 2] etc

You might be confusing $[-4, 4]$ with ${-4, 4}$. Remember that $[a,b] = {x \in \mathbb R | a \leq x \leq b}$.

[vital dew]

Boytjie

[weary tiger]

Oh because it's an interval?

As opposed to a set?

[brave rock]

An interval is a set.

I have described the meaning of [a,b] above.

[weary tiger]

right

[fringe siren]

We are given this function
f: R->R
f(f(f(2x+3)))=x
How can we prove that f is bijection?

[little prism]

you can try explicitly giving the inverse

[fringe siren]

Hmm how?
For simple functions is obvious but I get confused when there's composition of functions

[clever river]

Hi, how is it possible for a boolean function to be represented as a hypercube

Im trying to read this but going from 2d to 3d the vertex changes confuse me

[obtuse lance]

maybe it's easier to see if you define $g(x)=2x+3$ then you have $f \circ (f \circ f \circ g) = id$ so must be that $f^{-1} = f \circ f \circ g$.

[vital dew]

Merosity

[sudden minnow]

wow, that's cool

[granite cipher]

I think you can just prove both injectivity and surjectivity.
Surjectivity is obvious as for any x, take f(f(2x+3)) as a input.
Then for injectivity, you assume f(x)=f(y)
Manipulating the eqn gives u f(f(f(x)))=(x-3)/2
so you have f(f(f(x)))=f(f(f(y)))=(x-3)/2=(y-3)/2 which obviously
=> x=y and you are done.

[shell loom]

I need help with this problem: There exists an integer n, such that n^3-n is odd.

I think the it's false and I can show that it's always even given 2 cases, n is even and n is odd but idk if this is correct

[magic knoll]

its good

n^3-n=(n-1)(n)(n+1)
so it'll always be even

[shell loom]

Okay good, thanks!

[stray root]

I cannot seem to find any quantifiers/operators that make all three conditions true

I've tried OR, AND, <->, ->, (+), ~

none of them makes all three conditions true

[sudden minnow]

so p box q is true when both are true

false when both are false

and true when p is true and q is false

and false when p is false and q is true

so this operation only takes P into account, P box Q = value of P

a projection, if you will

[stray root]

yes i later realized after an hour that it's not asking me to determine the operation for the box

i got it solve though, thanks

[swift kiln]

Suppose we have a graph where the vertices correspond to elements of Zp (p is a simple number). If a and b are connected by a line then and only then when ab = 1 mod p. How many edges does this graph have?

could someone help me with this?

[tight hound]

Other than 0, every element in ℤp has a unique multiplicative inverse (mod p). The answer should be (p-1)/2
Of course, if p is 2 then the answer is 0.
(I assume you mean prime number when you say simple number)

[swift kiln]

Yes, thank you

[primal turret]

what is the number of combinations so order 4 digit to to 5 digit long number like the numbers 1,2,3,4 in to nomber like 11234 or 12342

you just know what you have x digit and the number length is n

and every digit need to apper

[loud oyster]

Need help with this question

The blanked out part is Solve the following recurrence relations

[calm scaffold]

Can someone prove or disprove that deleting edge in k-critical graph increase maximum independent set of vertices by 1 in Graph obtained by deleting this edge

[vital dew]

_FaithAlone_

[sudden minnow]

n choose k = n choose n-k

probably should know that

[shell loom]

the problem is (b) and this is my proof so far but idk what to do next or if im doing it right

[sudden minnow]

can you say something about b now

you are on the right path

[shell loom]

so b is even from the equality right?

[sudden minnow]

yes

[shell loom]

or wait

3b^2 is even but i want that b is even correct?

[sudden minnow]

yes

[shell loom]

then should i say 3b^2=2m?

[sudden minnow]

relax

if b^2 were odd, do you think 3b^2 can be even

[shell loom]

no?

[sudden minnow]

yeah so?

[shell loom]

but b^2 isnt odd right?

[sudden minnow]

the entire point is to show b^2 is even

if b^2 is even, then b is even by the exact same argument you used for a

[shell loom]

yeah but i still have the 3 to deal with

oh

[sudden minnow]

so you've told me that if b^2 were odd, 3b^2 can't be even

but 3b^2 is even

[shell loom]

idk, i was thinking of once again using euclid to say if 3b^2 is even then so is b^2

right since i guess 2|3b^2 -> 2|3 or 2|b^2?

idk

[sudden minnow]

sure... there are like 10 different ways to conclude b^2 is even under this situation

don't overthink it

[shell loom]

okay so "3b^2 is even, if b^2 were odd then 3b^2 can't be even so b^2 must be even"?

[sudden minnow]

yeah, but you can write this too

again, doesn't matter

[shell loom]

so wait did i need euclid for the first bit of my proof?

[sudden minnow]

don't even know what you mean by euclid's lemma

okay googled it

depends what you mean by "need"

if you can use unique factorization it doesn't really matter how you get there

but sure, if you know euclid's lemma and not much else you can keep using it, certainly works here

[shell loom]

well like i think being concise is better right? so i thought maybe using euclids lemma is overkill or something

[sudden minnow]

I'd say a lot of it depends on your audience and the level you are working at, what passes for "concise" I mean

the proof you are writing would probably be too concise for an 8th grader, and 10 sentences too long for a graduate

but in general, focus on being understandable before concise

[shell loom]

hmmm yeah good advice, ill try to keep that in mind

[sudden minnow]

as a general tip, I'd say if you've used one type of argument once you can use it in much fewer words the next time

so like

3b^2 is even, which means b^2 is even, which further means b is even by 2 applications of Euclid's lemma.

something like that would work

but I can't give you rigid advice

proof writing is in the end flexible

[shell loom]

yeah i was thinking about that before but it seemed weird repeating the application of euclid

true

and just to be clear, if i then have b is even, i can then say that means a and b arent coprime since 2 is there greatest common factor which contradicts that they are coprime...

[sudden minnow]

that is the argument, yes

[shell loom]

okay sweet

thank you!

[sudden minnow]

[cobalt canopy]

Hello, I am hoping for help on the following Question:
Let x and y be two real numbers such that x + y is rational. Prove by Contrapositive that if x is irrational, then x – y is irrational.
So far I have this for my proof by am getting stuck.
We will assume that x – y is rational and prove that x also must be rational to prove by contrapositive.
If x – y is rational, that means x-y is equal to a real number that can be expressed as a fraction where the denominator does not equal zero.
Assume a and b are real numbers where b ≠ 0.
X – y = a/b b≠0
Any help on this would be appreciated (sorry, I was having a hard time deciding where this should go)

[rapid mural]

they cant be real numbers

they are a specific subset of the real numbers

which one?

@cobalt canopy

when you figure out which one you will get your answer

[vital dew]

person2709505

[rapid mural]

if that is a set, yes

recall elements of sets are unique

[quasi stirrup]

Hey, just started my discrete structures class and I was wondering what prior math knowledge will I need?

[remote crane]

tldr: check your syllabus

[regal gate]

Why is this not a product?

this has to be wrong

you can count by hand the same problem but with less marbels, and that reasoning yields fake answers

...

this has to be a mistake lmao. In another problem of the same type he uses product

and like, you can prove it should be a product lul

annoying

[desert aurora]

Hi!
I'm reading about antichains in graph theory, and also indpendent set or anticlique. Both are the set of vertices that don't have any edge in the edge set of a graph G.
So are they the same thing ?

[desert aurora]

Nvm, maybe they aren't. Apparently the definition is different for an antichain in a graph vs. a set ? (here https://www.youtube.com/watch?v=aHx2V3u2Cyo he defines G=({a,b,c,d},{ab,bd,dc,ac}) and claims {b,c} is an antichain as theres no direct edge)
But here in a book (for CS DSA), {3,7} is a maximum antichain (evident from the fact that 3 flows to only 4 and 7 doesn't flow to it because of the directed graph). If the video's definition was used then a maximum antichain would be {1,6,4} which is size 3.
Anywho, the maximum anticlique for G could be {1,6,4} which is != maximum antichain for G, hence anticlique != antichain.

[little prism]

I have never seen a definition for an antichain in a general graph which doesn't correspond to a poset

chains and antichains fundamentally are about stuff that's ordered

[tawdry night]

Hi, I want to ask how to get 2^2k x 3 + (2^2k-1)? Why is 2^2k not multiplied into 3 to get 6^2k?

[desert aurora]

Yes it might be possible that the antichain here could be a local definition of the book and not exactly the same as antichain for a poset.
But that raises the question of what do we define as an anti-chain ?

A chain is simply a set of nodes that have edge sets between them, so whats the opposite, i.e., when they dont ? Anticliques wont cover them because they are about adjacent nodes.

[little prism]

well for any two nodes in the antichain you can't find a directed path between them

[little prism]

you only have $3\cdot 2^{2k}$, not $3^{2k}\cdot 2^{2k} = 6^{2k}$

[vital dew]

Denascite

[desert aurora]

Then, the video was incorrect right ?

[little prism]

they say "related"

instead of "edge"

if we draw a poset as a directed graph, we don't draw all possible edges

that would be way too many and make everything harder to interpret

[desert aurora]

Ohhh, you are right.
It's not about an edge in the poset definition, it's about the relation (which can be represented as an edge). It was simply that {b,c} didn't agree with the relation and was hence an antichain.

[desert aurora]

Thanks! Got it now.

[tawdry night]

But why 2^2k is multiplied into 1 to get 2^2k

[little prism]

1*2^2k=2^2k

or what do you mean

it's just a smart way of splitting up the expression to be able to use the induction hypothesis

[analog hound]

Right

I was just thinking that some authors write that eg {0,1}={0,1,0,1} instead of saying that only the former is a set

If we view sets as equivalence classes of multisets under the relation "has the same elements up to multiplicity", can the question be reframed as "should you always choose the smallest element of the class as its representative"?

[simple fulcrum]

help

how to find max and min elements in the set of fuctions

[little prism]

what have you tried

[primal mountain]

could i have a hint for this please

[split wren]

Hi

I'm in a applied combinitorics class and I really don't understand how to think about these problems

would someone be willing to hop on voice to run through some with me?

[obtuse lance]

this seems like the wrong channel, maybe try #calculus personally idk what to do, but maybe writing it in terms of cosh helps, since it's an even function maybe somehow the even exponents cancels with the square roots.

[primal mountain]

idk calculus doesnt seem too fitting but thx 😭

[obtuse lance]

are you sure this even converges?

[primal mountain]

100%

[obtuse lance]

where did this come from

[primal mountain]

putnam

its uhhh

2001 b3

[obtuse lance]

maybe try #competition-math if that's what it is

[primal mountain]

i thought thats preuni though

[obtuse lance]

I don't know what b3 is

[primal mountain]

it could as well use a technique thats at uni

b3 is q3 paper 2 from putna

m

[obtuse lance]

I don't think it matters, just say that when you post it there, if no one answers, nothing lost

[primal mountain]

true

[obtuse lance]

just don't post the same question in multiple channels at the same time

[primal mountain]

yep yep of course

[obtuse lance]

👍 cool

[haughty garden]

It might be fruitful to find a nice expression for <n> or at least, if <n> were to equal to a number, what the range of values for n look like. You can firstly note that, if <m> = n, then <m> should lie between (n - 1/2)^2 and (n + 1/2)^2. Then do some simplification and the value of the sum should fall out

[brave rock]

What is the division principle?

[muted gate]

are you talking about this? it's seen in Kenneth Rosen's Discrete Mathematics and its applications

right after the Sum Rule, Multiplication Rule and Subtraction Rule (counting principles)

[sturdy pilot]

Hi, actually i research about coding theory and found inner product in finite fields
Does anyone know where I can read more about it?
For example in the definition inner product in finite fields, and why ?

[little prism]

well a lot of the stuff that works over R with orthogonality still works somewhat over finite fields. the one big exception being that a space could be its own orthogonal complement. but stuff like dimensions still work

which is really nice

[sturdy pilot]

Yeah for the same reason, i would like to investigate more

For now I met the product l-galois, but I don’t the formal definition in the inner product (on finite fields xd)

[little prism]

well its the same as over R just without the positivity stuff

[sturdy pilot]

But in R
<x,x>=0 if only if x=0

In finite fields exist vector self orthogonal

[little prism]

for me that belongs to the positivity stuff. <x,x> >= 0 with equality iff x=0

[sturdy pilot]

Aah oka but what are the others conditions? Because I remember the scalar conjugate but in the concept the conjugate in finite fields is more complicated, for it i need work in extensions fields 🥲

Also in R is symetric🤔 and Hermitian product it is not

[hollow loom]

utilities problem but with 4 houses and 5 houses

possible?

[rough cradle]

Hey guys, if I say "Every dog is not a reptile". Is the "not a reptile" part still P(x) or is it ~P(x)?

i.e. For all x element of D | ~P(x)

[stray reef]

is the predicate P(x) defined

or are you meant to define it yourself

[rough cradle]

I'm just trying to get a hang of translating English into logic and I was actually just told in another forum "is not a reptile" can be either P(x) or ~P(x). Does that sound correct?

[stray reef]

again it depends on what you take as your P(x)

if you take P(x) as "x is a reptile" then "x is not a reptile" translates to ~P(x)

but if you take P(x) as "x is not a reptile" then "x is not a reptile" translates as P(x)

which one of these would be clearer to the reader is another matter of course

[rough cradle]

Got it. Ok so a bigger question is, I was given an example reading "Every integer has a bigger integer" formally written as:

"For all x element of D, P(x)"

But, was told that P(x) can be optionally expanded to:

"There exists a y element of D, such that y > x"

D here being the set of all integers and y being x+1

My question is, could the above expansion of P(x) be applied to say "All dogs are not reptiles"?

So as to say:

"For all x element of D, there exists a y element of R, such that y is not x"

D being the domain of dogs, R being the domain of reptiles?

In the integers example both x and y belonged to the same domain so my logic was to make the y in the pets example belong to another domain. Is this correct? I was told "no" but it wasn't explained why.

[stray reef]

...

[rapid mural]

the issue here is that just because we have at least one reptile not equal to the dog
doesnt mean we cant find any reptile that is not equal to the dog

[rough cradle]

Ok I see it now.

[final swift]

Hello, I just want to clarify, given the statement, $(p \land q) \lor r$, can I derive the statement $(p \lor r)$ because of the inference rule, simplification? thank you.

[rapid mural]

you want \land and \lor

[vital dew]

ssrrll

[pale epoch]

also you are correct

[final swift]

thank you

[tawdry night]

Hi, i want to ask for this question. It requires only two gates. Because there are three parts, there must be three AND gates. How to draw it?

[chrome fossil]

Construct a truth table

It should be similar to something you know

[tawdry night]

I draw a truth table already. What steps I need to do

[chrome fossil]

Can I see the truth table

[chrome fossil]

Now, what expression can give F, T, T, T as results

hint : ||try negation||

[tawdry night]

Isn't it just adding (~P^~Q) V (~P^Q) on the left and then adding V (P^~Q) on the right to get the answer?

This is the circuit I drew

[golden raven]

how many ways could you make a set with four elements using 1, 2, 3, and 4?

repetitions of numbers obv allowed

[tight hound]

What does it mean to repeat numbers in a set?

[olive ravine]

Whats the cardinality of the set P({1, {2}), its 2 right? 2 elements, 1 and {2}

or would you say its 3, being 1, {2} and 2

[brave rock]

The cardinality of {1, {2}} is 2

the cardinality of P({1,{2}}) is not 2

2 is not an element of {1, {2}}.

If you are unsure of what P( ) means, it is the power set. Given a set X, the set P(X) has as its elements all subsets of X. For example, if X = {a, b} then P(X) = {{}, {a}, {b}, {a,b}}.

[heavy yarrow]

I’m tasked with finding the effective conductance between the two nodes. I used a result I’ve seen before in my working out

Is my answer correct?

[shell loom]

So for (a) i got my x and y value but i have 0 clue what to do for (b) i dont recall going over it in lecture. I also don't know what to do for (c). I was thinking of using a theorem about how basically theres a d such that d|a and d|b as well as c|a and c|b where then c<=d. Id then use this in combination with the gcd(a, b)=ax+by but idk if thats the right approach since when i tried it there wasnt really a way to connect evrything.

[chrome fossil]

But that’s more than two logic gates

[little prism]

subtract the two equations from a) and b)

[chrome fossil]

m = x + (271/gcd(271, 2023))k and n = y - (2023/gcd(271, 2023))k for any integer k would be a solution.
Here’s some more info
https://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

[chrome fossil]

idk how to prove (c) with (a) or (b) or by using linear diophantine but
Let k = gcd(a,b) so a = km, b = kn with gcd(m,n) = 1
gcd(a^3, b^3) = gcd((km)^3, (kn)^3) = gcd((k^3)(m^3), (k^3)(n^3)) = (k^3)gcd(m^3, n^3) = k^3
Obviously gcd(a^3, b^3) = k^3 >= gcd(a, b) = k
With equality at k = 1
So statement is false when gcd(a,b) = k = 1 only

[little prism]

dont give out answers

[shell loom]

oh okay so its false lol

i never checked for the coprime case

but yeah in future just give me hints and thanks either way guys

[shell loom]

uh so when i subtract the equations I get this

[vital dew]

geanan

[shell loom]

what do i do from here?

I also see on the wiki that if you have Ax+By=C then somehow A(x+B)+B(y-A)=C which doesnt look like what i have

[sage lance]

Hi folks! I am trying my hand at writing the proof for the theorem, "An Empty Set is a subset of every set." I am attempting a proof by contradiction -- this is my first attempt so I apologize if it doesn't make much sense. What I would like help with is:

1. Does my proof make sense?
2. How should I improve my proof?
3. Where did I go wrong and how could I improve my logic?

Here is what I have tried:

### Proof by Contradiction

#### Set-Up

Let $A = \emptyset$ and $B$ be a set. 

Suppose we assert the statement: $A \subset B$

#### Definitions

We will use the following [definitions](01202023041150-graphs.md) taken from [Trudeau's introductory textbook](01202023040727-introduction-graph-theory.md).

##### Set 

Definition: Collection of distinct objects, none of which is the set itself.

##### Subset 

Definition: A set $A$ is said to be a subset of a set $B$, if every element of $A$ is also an element of $B$.

##### Empty Set

Definition: A set containing no objects.

#### Proof 

Given the definition of an [empty set](#empty-set), there are no objects within $A$.

Given $\forall a \in A$, we pose the assertion that $a \in B$.

As there are no objects in $A$, at first, the previous assertion seems false.
However, using the definition of a [set](#set), all that is required for a set to be valid is to have unique objects. 
By extension, a set is allowed to be empty.
Yet, being that there are no objects in $A$, we are left to say that $a \in B$ is either true or false.

Building upon this previous statement and the definition of a [subset](#subset), we can then say that the assertion $A \subset B$ is neither true nor false. 
And by the property of vacuous truth, we are left to say that an empty set is a subset of every set. 

Happy to provide additional info as needed! Also, if the markdown is hard to read, attached is the rendering. Thanks! 😄

Carrying the conversation @gusty swallow , sorry about the mix-up, accidentally asked in the wrong place. But yea, I found it a bit funky as a way to get to the conclusion as I thought that was what "vacuous truth" meant in a proof by contradiction sense here. I could be completely wrong however.

[gusty swallow]

not really, vacuous truth means it's true because the premise is false.

"if pigs fly then I'm superman" is vacuously true because pigs don't fly.

[sage lance]

Ooohhh. So should I modify the initial assertion "Suppose we assert the statement: A is not a subset of B" since A is a subset of B?

Or how should I update the premise you think?

[gusty swallow]

it would get to vacuous truth much quicker, imo

you have if a is in A then a is in B is vacuously true since there isn't an a in the empty set to begin with

[sage lance]

Bingo! That's what I was trying to convey but was a bit confused on how to say it. Let me try a small rewrite (updates in bold):

Suppose we assert the statement: **A is not a subset B**

...

Given the definition of an [empty set](#empty-set), there are no objects within $A$.

Given $\forall a \in A$, we pose the assertion that $a \in B$.

As there are no objects in $A$, at first, the previous assertion seems false.
However, using the definition of a [set](#set), all that is required for a set to be valid is to have unique objects. 
By extension, a set is allowed to be empty.
**Being that there are no objects in $A$, we are left to say that $a \in B$ is vacuously true**.

**Building upon this previous statement and the definition of a [subset](#subset), we can then say that the assertion $A \subset B$ is therefore vacuously true for every set. **

Does that make more sense now?

[obtuse lance]

I'd focus on understanding how to prove the empty set is a subset of every set first

proving it by contradiction is just coming off as convoluted to me trying to read this here

[sage lance]

Oh dear, I think I am in trouble. I thought this was a proof that proved that an empty set is a subset of every set. How would you recommend approaching it differently?

[obtuse lance]

this is the proof right here

like you said here earlier: Definition: A set $A$ is said to be a subset of a set $B$, if every element of $A$ is also an element of $B$.

[vital dew]

Merosity

[gusty swallow]

yeah.... this proof should be like 3 lines tops. You can do it by contradiction, or directly and it's very short

[sage lance]

Oh shoot so I wayyy over complicated it.

[tawdry night]

i'm a bit confused😢

[gusty swallow]

you can fill in extra with definitions and stuff like you did, and add length. but it's a pretty succinct proof usually

[obtuse lance]

one thing you can do is cut out this boilerplate of laying out well known definitions before your proof. They're good to write out for yourself on paper so you can easily refer to them and help get them in your brain, but you don't have to resay them

[sage lance]

Ah gotcha! Let me comment back on this in about 30 minutes— I’ll try to clean what I had up to be more concise.

But thank you so much Zybikron and Merosity !

[ripe mulch]

Question: https://atcoder.jp/contests/abc046/tasks/abc046_b

There are N balls placed in a row. AtCoDeer the deer is painting each of these in one of the K colors of his paint cans. For aesthetic reasons, any two adjacent balls must be painted in different colors.

Find the number of the possible ways to paint the balls.

We have N balls (> 10), for the 1st ball, I can choose K colors, for the 2nd ball can only choose K - 1, for the 3rd ball I can also only choose K - 1, and we keep going. So would the number of possible ways be K * (K - 1)^(N - 1)?

[hexed shore]

In how many ways can the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 be distributed so that no even digits are in its original position?

Anyone could give me an info 🙏

[chrome fossil]

Yes

[chrome fossil]

try using inclusion-exclusion.

[tawdry night]

Is this right? If I substitute NOR GATE

[hexed shore]

I did

[chrome fossil]

The given expression is equivalent to not (p and q) (check the truth table)
Now put not (p and q) as a logic gate

[chrome fossil]

-9 x 7!
Where did you get this

[sage lance]

Hey @gusty swallow and @obtuse lance , it took me a bit longer to think through this but I came up with the following proof for showing that an empty set is a subset of every set. Does the following make sense?

For any set, $B$, $\forall a \in A$, we assert that $a \in B$ is vacuously true, where $A = \emptyset$.

[vital dew]

TheCedarPrince

[obtuse lance]

@sage lance I guess you can compare with this and try to understand if there are any substantial differences or not

[hexed shore]

Nvm found it

[hexed shore]

Nvm I did it wrong

,rotate

,rotate

[tawdry night]

How to put not(p and q) as a logic gate?

[sage lance]

Yea, I was flipping between what I was writing and that statement quite a bit. I did not think there were any substantial differences when compared to my statement.

[obtuse lance]

yeah good, you're right

maybe one thing i'd change is refer to A=empty set first, or imo even better just don't introduce A at all and write the empty set there

[rough cradle]

What's the deal with the pipe | and comman , symbols when writing statements? Are they synonymous?

E.g.

[obtuse lance]

sometimes people use | or : to mean "such that" in set notation, I guess comma also can be read that way too

using symbols too much is typically discouraged

[sage lance]

Yea I agree. Wow, this was such a neat experience. This is my first proof that I ever sat down with, took the definitions I knew should be involved, and tried to create a proof with from scratch. I know I had problems in the directions I took initially, but starting from all the definitions and ending up with a proof that was could fit onto half a line is super magical. Thank you for being patient with me and helping me on this -- I feel like I learned something really incredible.

[obtuse lance]

cool, yeah math can be pretty seductive like that sometimes

[sage lance]

Yea, don't want to get too off topic but I could totally see the intrigue with it. I found myself thinking, "Can I make this proof even more compact?" and realized: this is quite fun actually! I also was surprised when we finally ended up with such a compact proof -- all that content boiled down to only a few strokes. It helped click in my mind when mathematicians say something is "elegant". I am beginning to see!

[obtuse lance]

Yeah it's like fumbling around in the dark at first and then you find a light switch and then everything makes sense, I think that's a poor paraphrasing of how Andrew Wiles said it was like in proving Fermat's last theorem

which is pretty relatable I think

[sage lance]

Hey @obtuse lance , sorry for the ping (last one tonight!), but I was trying to write in my personal notes an explanation on the proof. Right now, I have this:

#### Explanation

Via the [set definition](#set), all that is required for a set to be valid is to have unique objects.
This gives rise to the definition of an [empty set](#empty-set), a set that has no objects.

The tricky bit is meeting the [definition of a subset](#subset).
**Suppose the statement $\emptyset \not\subset B$ exists as antecedent.
Next, $x$ can be established as an element of the $\emptyset$ in the statement, $\forall x \in \emptyset$.**
However, because $\emptyset$ does not have any elements, $x$ doesn't exist to satisfy the antecedent resulting in the further condition that $x \in B$ to be vacuously true.

I highlighted the confusing part to me in bold from my notes. I had this written down from our discussion but am still confused about as to where I would get this antecedent from and why not start at "An emptyset is a subset of B". Wouldn't saying this as the antecedent lead to the same resulting proof as I still cannot satisfy that antecedent?

[patent gull]

can i combine the 2 not q into 1 not q?

[rough cradle]

Yes

[patent gull]

thanks

[chrome fossil]

p , q --> and --> not

[unreal stump]

Law of Excluded Middle?

[strange token]

Can anyone help me with this? haha. I can't seem to get it right

[weary tiger]

Can I just clarify that Dijkstra's Algorithm only works on digraphs? I found an A-level maths paper asking to find the shortest path, but there are no arrows on the graph

[leaden jay]

Does anyone have ideas for this problem? I'm not sure what to look for in this given graphic sequence to determine if a cut edge exists...

[shell loom]

This is for (b) Is my proof okay? idk how else to show this

[weary tiger]

it looks reasonable

[shell loom]

for (d) would the negation be "There exists a,b,c in Z such that gcd(a,b)=1 and c divides a+b but either gcd(a,c)=/1 or gcd(b,c)=/1."

[leaden jay]

^^^ Can anyone help me as soon as possible?…This assignment is due soon…

[obtuse lance]

what's a graphic sequence

[leaden jay]

That represents the degree of all of the vertices of the graph…

[last sigil]

all the degrees are even

[shell loom]

this look okay?

[patent gull]

i think i did #1 correctly not sure on #2

[leaden jay]

That’s enough of a justification?

[last sigil]

Well, I just gave a hint to get you thinking

try some smal examples

[leaden jay]

Should a certain theorem be applied here?

All the degrees of this graph are not even, but it still has a cut edge (c, e)...

Wait a second...

This might be an interesting observation...

All the graphs that I have seen that has a cut edge has at least a vertex with an odd degree...🤔

[peak pewter]

Can anyone help me with this

Consider the equation x^2+(y-2)^2=1 and the relation “(x, y) R (0, 2)”, where R is read as “has distance 1 of”.

For example, “(0, 3) R (0, 2)”, that is, “(0, 3) has distance 1 of (0, 2)”. This relation can also be read as “the point (x, y) is on the circle of radius 1 with center (0, 2)”. In other words: “(x, y) satisfies this equation x^2+(y-2)^2=1 , if and only if, (x, y) R (0, 2)”.

Does this equation determine a relation between x and y? Can the variable x can be seen as a function of y, like x=g(y)? Can the variable y be expressed as a function of x, like y= h(x)? If these are possible, then what will be the domains for these two functions? What are the graphs of these two functions?

Are there points of the coordinate axes that relate to (0, 2) by means of R?

[brave rock]

x is not a function of y.

You are right that the equation determines a relation between x and y, but this is uninteresting.

y is not a function of x either.

You should be able to prove these claims with ease.

[weary tiger]

help

[leaden jay]

Can anyone help me from where I left off?

[chrome fossil]

Graphing the functions should help. Invertible functions are one-to-one functions.

[small plume]

can someone tell me whats ambiguous about
Joe saw David driving to school

[sudden minnow]

did joe see david while joe was driving to school

or did joe see david while david was driving to school

[small plume]

ohh right

damn how tf did I miss that

thanks

[leaden jay]

Any thoughts about "All the graphs that I have seen that has a cut edge has at least a vertex with an odd degree"?...

[snow cedar]

for string of length 3, they got 49. how?

im subtracting 4^3 from the number of bad strings

which i thought is 4^3 - 2x(3choose2)x4

[haughty garden]

We use inclusion/exclusion to find the number of length 3 strings which contain 12 or 20 as substrings.
To find the number of strings which contain 12, note that the string 12 must appear in one of two places: either _ 1 2 or 1 2 _. Therefore, there are 2 places to place the 12. The remaining digit can consume one of four digits. This gives us 2 x 4 number of strings that contain 12 and we can check this quite easily: {012, 112, 212, 312, 120, 121, 122, 123}. A similar analysis shows there are also 2 x 4 number of length 3 strings which contain 20 as a substring.

But, of these cases, we would have double-counted 120 twice. So we need to remove the string 120 once. Therefore, the number of length 3 strings which contain 12 or 20 as substrings is 2 * (2 * 4) - 1.

Therefore, the number of strings is 4^3 - 2 * (2 * 4) + 1 = 49

[leaden jay]

Thoughts?

[weary tiger]

Can anyone help me in that question

[weak sand]

Can someone explain me why this one apparently has 60 topological orderings? from my understanding it should be 16

[haughty garden]

Any topological ordering fixes the following vertices

1 _ _ 4 _ _ _ _ _ _

Now in the second and third spot, we can choose 2 or 3 - both are perfectly fine orderings. After 4, we have a few choices to make. Any topological order must place 6 after 5. Any topological order must also place 9 before 8, 10 and after 7.

If 5 comes before 7, then 6 has 5 places to go and 7 becomes fixed. 8 and 10 will then have 2 choices to go. This gives us: 2 * 5 * 2 = 20 for the case where 5 comes before 7.

If 5 comes after 7, then we fix 7 to go after 4. We can first fix 5-6 by choosing two positions and since there’s only one ordering, the number of ways of fixing 5-6 is C(5, 2) = 10. Then, the 8 and 10 can swap and everything else is fixed. Therefore, if 7 comes before 5, the number of ways is 2 * 10 * 2 = 40. This gives you 60 total topological orderings

[latent quarry]

You can also solve this recursively in a dynamic-programming-esque way

i.e. there's a pretty straightforward algorithm to do this for general dags

[weak sand]

thank you. thank makes sense

[chrome fossil]

p -> q
q or r
So r -> p
Is this correct?

[vital jolt]

Can you take the power set of an uncountable set?

And if so, is there a set with a order of magnitude larger cardinality than the power set of an uncountable set

[stray reef]

yes to both.

[tight hound]

Any set has a power set.

[sudden minnow]

<@&268886789983436800>

[grim kraken]

Tyvm

[broken sonnet]

I'm not sure if I am headed in the right direction with my counting question that I made

[shadow grove]

In the 15 puzzle, how are the bricks initially placed?

Just randomly, or is there a pattern? Specifically, I will be doing a DFA on the easier 2x2 puzzle.

[stray reef]

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 ..

this is the solved state of the 15 puzzle if that's what you were asking

[shadow grove]

No, just how to initialize it?

For the 2x2 case

or actually, just the general NxN case

[stray reef]

wdym initialize

[shadow grove]

When the puzzle starts how are the letters arranged in the N x N case?

[stray reef]

they are scrambled, no?

unless you're talking about the popular-then-proved-impossible version

[shadow grove]

Scrambled how? Just intuitively like a normal board game or what?

[stray reef]

like a rubik's cube

[shadow grove]

Okay

thanks

[broken sonnet]

For the RHS of a combinatorial proof, $2(n - 2) + \binom{n - 2}{2}$ can be written as:
\begin{align*}
&2(n - 2) + \binom{n - 2 - 1}{2 - 1} + \binom{n - 2 - 1}{2}\
&=2(n - 2) + \binom{n - 3}{1} + \binom{n - 3}{2}\
&=2(n - 2) + (n - 3) + \binom{n - 3}{2}\
&=(n - 2) + \binom{n - 1}{2}\
\end{align*}

[vital dew]

phamous

[broken sonnet]

Can someone explain how we were able to get rid of (n - 3) and the 2 for 2(n - 2)

[minor whale]

can somone help

me

[short merlin]

Guys I need help with the fixed point method

When is the position of the structure equal to y(t) = 4?

Y(t) = 10e^t/2.Cos(2t)

Starting from x0 = 2

[unreal radish]

Do all enumerable sets have less cardinality than a non-countable sets, when they are infinite? If you are assigning ID's to books, it doesnt make sense that whole numbers allow you to assign less ID's to books than if you used random numbers between 0-1

[brave rock]

You can prove that every uncountable set has an enumerable subset (n.b. this requires the axiom of choice.)

It makes sense to me – you just haven't gained the correct intuition yet.

Keep working with infinity and you will likely eventually agree that it makes sense.

[brave rock]

This is a good exercise.

[shell loom]

does this look okay?

[brave rock]

You have not argued why ax+by = gcd(a,b)

[shell loom]

do i need to say like there exists a divisor d such that etc. or how would i go about doing that?

[brave rock]

Give it a shot first, see what you come up with

[shell loom]

okay let me see

[shell loom]

or is maybe that i need to start with a and b have gcd(a,b)=d and then d=ax+by, 2d=2ax+2by=2(ax+by)?

gcd(a,b)=d
ax+by=d
2ax+2by=2d
gcd(2a,2b)=2gcd(a,b)

this is what i came up with

[brave rock]

You have reversed the same proof, but again you have not justified why 2d = gcd(2a,2b)

You are just asserting it

[shell loom]

okay well bezouts says there is a greatest common divisor d such that d=ax+by for some integers x and y

if i multiply both sides by 2 i get 2d=2(ax+by)=2ax+2by

[brave rock]

You have misunderstood Bézout

Bézout says that there are some integers x and y for which this is true

However, Bézout gives no guarantee that the x and y such that gcd(a,b) = xa + yb are the same as the x and y such that gcd(2a,2b) = x(2a) + y(2b) as you are assuming.

You must justify why this is true.

[shell loom]

yeah this makes sense

i guess all I'm given is that a>1 and b>1, am i to use these somehow?

[brave rock]

I suggest you use the defining properties of the gcd of two numbers.

If you're not sure what that is, it's in the name: it's the greatest common divisor

[shell loom]

the gcd of two numbers a and b is the unique integer d with d|a and d|b and if c|a and c|b then c<=d?

[brave rock]

Are you asking me?

Are you unsure about that?

[shell loom]

yeah im asking

[brave rock]

That is indeed the definition of the gcd.

[shell loom]

okay yeah i for some reason thought bezout was like the def of gcd

this makes sense thoguh

[brave rock]

It can be used as a definition! The number d = gcd(a,b) is the smallest positive integer such that there exist p, q such that d = pa + qb

However, this requires a bit of work to prove. I suggest you use the definition you posted.

[meager lintel]

recursive definition of growth of rabbit population when a rabbit dies

assume we start with 1 new pair and they don't they take one months to become fertile and gives birth to 3 pairs each month after becoming fertile and only lives for a total of 4 months and also they give birth to a 3 pairs in their last month.

[shell loom]

@brave rock I just took a bit of a break but i wanted to ask, do i use the definition of gcd to get a linear combination? or am i to reason about this without the use of a linear combination?

i tried doing without it but i couldnt figure out how i get gcd(2a,2b) from it

[brave rock]

I'm not going to tell you the answer to this. I will say that you should apply the definition of the gcd to try and show that 2d = gcd(2a, 2b).

[shell loom]

So using the definition could i say the gcd of two numbers 2a and 2b is the unique integer 2d with 2d|2a and 2d|2b and if c|2a and c|2b then c<=2d?

[brave rock]

I think you should try completing the proof, not asking for help on each step.

Maybe once you've tried some things, you'll either have completed the proof, or you'll have a great question to ask

[robust spear]

Guys is there a channel for specifically discrete systems and signals?

[weary tiger]

if f(n)^f(n) = theta(n) then what could f(n) be?
i would take log of both sides and make a guess
so f(n)log(f(n) = theta(log(n))

<@&286206848099549185>

[obtuse lance]

you can use the lambert W function, if that's satisfying

[haughty garden]

Be careful. The logarithmic function does not preserve big Theta. Consider f(n) = 2 and g(n) = 1. Clearly f \in Theta(g). Try applying the log to both functions

[obtuse lance]

oh I didn't realize this was big theta, disregard my comment

[haughty garden]

At least I think it is ahaha

¯_(ツ)_/¯

[obtuse lance]

seeing how they used theta seems consistent with that idea I think

[weary tiger]

i cant pick g(n)

g(n) = n

that's part of the question

i have to find f(n) such that f(n)^f(n) = theta(n)

[weary tiger]

it's monotonically increasing. Since's everything's positive that should preserve inequalities

a>b and log(a)>log(b) are equivalent as far as i can see

[haughty garden]

no, the point is that you can't simply say that a monotonic function preserves asymptoticity

this is not true in general

[weary tiger]

i think in this case it can help us make a guess

[haughty garden]

you need to be careful with what constant c you decide to choose

[weary tiger]

we don't have to get into mathematical proofs. The question just askes for a reasonable guess

i also don't know what lambert function is

[haughty garden]

well, such a function has to be bounded above by a linear function

because any function that is \Theta(n) is also O(n)

[weary tiger]

ik f(n) is small

clearly f(n)^f(n) is huge

[haughty garden]

any constant function is too small as well since its lower bound won't be linear

any polynomial will be too big, or maybe most polynomial functions

[weary tiger]

my prof said it has smthing to do with logs

smallest function i could think of was the iterated log

but my prof said that's too small

[haughty garden]

yeah so I suspect no polynomial function is suitable as f(n)

next thought is to go to logarithmic functions

[weary tiger]

bruh if f(n)= n then n^n is bigger than exponentials

someone said lambert function. It looks related

it's the inverse of xe^x

<@&286206848099549185>

[gaunt nest]

log is also too big I think: log(n)^log(n) = n^log(log(n)) which grows just a smidge faster than n

If you're happy to use the Lambert W then I think log(x)/W(log(x)) will work

https://www.wolframalpha.com/input?i=(log(x)%2FProductLog(log(x)))^(log(x)%2FProductLog(log(x)))

[weary tiger]

bro how did you guess this

I don't want the prof to look at my solution and go this guy cheated by using wolfram

[gaunt nest]

Well, I noticed that the function x^x is invertible so I asked WA to invert it

[reef juniper]

any tips?

[tall lodge]

Anyone have advice for self studying discrete math?

I have a background in proofs and number theory

[meager lintel]

recursive definition of growth of rabbit population when a rabbit dies
assume we start with 1 new pair and they don't they take one months to become fertile and gives birth to 3 pairs each month after becoming fertile and only lives for a total of 4 months and also they give birth to a 3 pairs in their last month. <@&286206848099549185>

[night mantle]

hiii, I wanna ask a question on set theory so this is the closest channel I found. I'm reading this solution and got confused by the line"note that this does not imply h(a)>|A| without AoC." But I thought any set of ordinal numbers are well-ordered so why do we need AoC for this??

[tight hound]

What is h(A)?

[night mantle]

hartogs number

of A

[tight hound]

Oh ok

[vital jolt]

What is the infimum of $\omega_1$?

[vital dew]

KayJay

[coral parcel]

Uh. Taken literally the answer would be "0", but I think a better answer would be: That's a strange question, can you give some more context for it?

[sudden minnow]

can you clarify what you mean

nvm

[weak sand]

Given a graph G = (V,E) for which E = 2V+2.
Graph G has 8 vertices of degree 5 and the other vertices are of degree 2. How many vertices does graph G contain?

the answer is 10. but i can't figure out how to solve this? any help?

[vital jolt]

Discussion about infinities

Isn’t $\omega_1$ also the set of all real numbers? If so, how can the greatest lower bound be 0? Aren’t real numbers unbounded?

[vital dew]

KayJay

[coral parcel]

No, definitely not. It's the set of all at-most-countable ordinals.

Depending on whether the continuum hypothesis holds, this set may or may not have the same cardinality as the real numbers, but it certainly doesn't have the same elements.

[vital jolt]

Ok so it’s a different set?

[coral parcel]

Yes.

[vital jolt]

Ok then what is $\omega_0$?

[vital dew]

KayJay

[vital jolt]

Since I think I fundamentally misunderstand infinite ordinals

[coral parcel]

omega_0 is the same as omega: the set of all finite ordinals, better known as the natural numbers. :-)

[vital jolt]

Wait so then the infimam of omega_1 would be 1, right

Since it’s simply the ordinals extended past finite values?

[haughty garden]

By the handshaking lemma, the sum of the degree of vertices is 2E. Therefore, 8 * 5 + 2x = 4V + 4. This implies that 2x = 4V - 36 or x = 2V - 18. The number of vertices in G is given by V = 8 + x. You now have two equations to solve for x and V

[weak sand]

thank you. i did something similar. turn out i had a mistake in the algebra

[coral parcel]

It would be 0, since 0 is also an ordinal.

[vital jolt]

0 isn’t a natural number though

0 is just the cardinality of the empty set

Wait no that’s 1

[coral parcel]

"Natural numbers" can mean either including 0 or not, depending on who's speaking (and often also on what they're speaking about).

[vital jolt]

Oh okay

[coral parcel]

In a context where we're also talking about ordinals, "natural numbers" almost invariably start with 0.

[brave rock]

Also, it looks like you said that the cardinality of the empty set is 1. It's 0.

[weak sand]

The shortest path for 1 - 8 is apparently 3. But I cannot understand how is that possible given there is a negative cycle in 2,3, 5, 4. should that mean the shortest path and walk to 8 should also be undefined?

[stray reef]

do you have the problem statement exactly was it was written...?

[weak sand]

What can be said about the shortest path and shortest walk from vertex 1 to vertex 8 in the following graph?

[stray reef]

surely a path can't take the same edge twice...?

[weak sand]

no

[stray reef]

if we're distinguishing paths from walks, then surely one of them has as part of its definition that no edge is visited twice

or do you object to this

[weak sand]

i do not object. path cannot have same edge twice but walk can

[stray reef]

then how come you said "no" to my "surely a path can't take the same edge twice...?"

anyway

a path cannot make use of the negative cycle

[weak sand]

i meant as "no, they cannot"
I guess my undersanding of bellman ford algorithm is not good. We use it to find shortest path right? so, when we find a negative cycle and our destination vertex is affected by the cycle how can we find the shortest path ?

we just avoid the negative cycle?

[quasi stirrup]

Could someone explain what the little scope looking thing means

[sudden minnow]

XOR, though I've never seen it used as an operation on sets before

[quasi stirrup]

This is a computer science class so that might be the reason

[sudden minnow]

I see

[coral parcel]

The subsets of, say, N form a ring if we consider the addition operation to be "XOR" (also known as symmetric difference) and the multiplication operation to be intersection. So "circled plus" makes some sense for the operation.

[sudden minnow]

oh yeah, in math we generally call it symmetric difference instead

and the symbol is a triangle

idk why I didn't connect the two

[gaunt nest]

I think we use that symbol in CS because for bits it's addition (hence the plus) modulo 2

That's just speculation tho

[ripe delta]

Hey does anyone know if I can use an inference rule on an equation two times?

its an equation with the all quantifier and i wanted to use it for two people in my question

[coral parcel]

Generally you can use inference rules as many or few times as you need.

[rose heath]

Hey, I need help understanding this task

X = { a, b, c, d, e, f, g, h }
How many in X are equivalent relations, where "a" and "b" are together in one abstract class?

[glossy kayak]

is there a non-iterative/non-recurisve way of implementing the logorithm algorithm?

[weary tiger]

what website is this?

[snow cedar]

anyone know what the significance of adding the identity matrix is?

im seeing on the internet squaring matrix tells you there is a "walk" of length 2 from i to j

and by extension a walk of length k

but im looking at the case of a simple graph O---O where the matrix would be 2x2 filled with 1's

squaring it gives [[2,2],[2,2]]

but if we raise it to 4th power, its all 4's

but i dont see 4 walks of length 4 lol

[waxen vessel]

how do you construct a graph such that all spanning trees share an edge?

[fringe siren]

What does it mean for x not belonging to (B\C)?

Is it that the x is in C and not in B?

[meager lintel]

not really

[rapid mural]

quite the opposite rather

[coral parcel]

That's only the right matrix if your graph also has loops at each of the vertices.

Without the loops, the matrix should be [[0,1],[1,0]] and its powers are much more restrained.

[gleaming scaffold]

anyone good with recurrence relations and recursion trees?

ive got a very basic question

it seems like its basic but i just cant figure it out

[gleaming scaffold]

i've got T(n) = 2T(n-2) + theta(1)

and im trying to solve it using a recursion tree

somehow im getting a linear time, which seems very wrong

my guess would be 2^n

how would you go about solving that recurrence using a recursion tree?

[haughty garden]

Recursion trees aren’t well suited for these types of recursions; you use them more for recursions where you have T(n) = aT(n/b) + f(n)

The idea behind a recursion tree is that it can be used to analyse the complexity of a divide and conquer algorithm

[gleaming scaffold]

why would a recursion tree not work? you can still have the call size to be (n-2), (n-4) etc at each level going down

my point being that it can work the same way

[haughty garden]

I didn’t say they wouldn’t work, just that recursion trees aren’t typically the best method to solve a recurrence of this type. A more direct way of proving that you’re right is the substitution method. You can show that this reduces down to T(n) = 2T(n - k) + Theta(1) for any k. It works fine here because you know that, at each stage of the recursion, you’re doing constant time work so the analysis via recursion trees is simple

It may be a bit harder for more exotic linear recursions or even recursions where the overall work time is non-constant

[gleaming scaffold]

so for that particular one would the solution be O(n) or O(2^n)

or something completely different?

[haughty garden]

Should be Theta(n)

Intuitively this makes sense because you can memoise each recursive call

So you only have O(n) subproblems to solve

Each of them takes Theta(1) to solve

[gleaming scaffold]

yeah but each call make further 2 calls, so if you have 6 calls they make a total of 2^6 calls

assuming cost of each call is constant

that cant be linear

[haughty garden]

It only makes 1, no? It just calls T(n - 2) which is wholly different to something like T(n - 1) + T(n - 2)

[gleaming scaffold]

its T(n) = 2T(n-2) + theta(1) so has to be 2

[haughty garden]

Okay so another way to write this is T(n - 2) + T(n - 2) + Theta(1). Though you do make 2 function calls, how many are you solving for?

[gleaming scaffold]

wdym solving for?

2

[haughty garden]

Which two?

[gleaming scaffold]

one second ill send a picture

[haughty garden]

If you imagine it as a recursion tree, you’re only going down a single branch of the tree because, at every stage, you can just cache your result

This is also how you can reduce Fibonacci from exptime to linear time

[haughty garden]

This works iff your algorithm allows caching to work

[gleaming scaffold]

but then why if we have [n/2] we have to consider all branches and sum all branches?

like when using master theorem

[haughty garden]

Because each of the subproblems solve different parts of the problem

Think of merge sort for example

You split the array into two halves but when you’re doing your recursive step, you’re solving for the lower and upper parts of the array separately

For the Fibonacci algorithm, if you know the result of f(n - 1) and f(n - 2), you can cache these results to solve f(n) in constant time

[gleaming scaffold]

my professor summed all the branches when considering T(n-c)

and here we have to sum all the red numbers, which is the cost for each call essentially

[haughty garden]

Oh so you’re not considering any memoised algorithm or at least yet

[gleaming scaffold]

i dont think so

[haughty garden]

Then yeah, the linear time analysis isn’t right

At each stage, you’re solving two subproblems of the same size

The time it takes a single subproblem is constant time

[gleaming scaffold]

yeah linear cant be right

but this is what i got from this working out

which is just a generalisation of the slide above

[haughty garden]

You should have n/2 layers

So you just need to figure out how many subproblems in each layer

[gleaming scaffold]

the way i calculated max depth/number of layers is that the size of each call is (n-2^i), so at the base case that needs to be equal to zero, hence n=2^i, where i is maximum depth

which gives h=log2(n)

i think the mistake i made is regarding the call size

i expressed it at n-2^i

which just isnt true

because you are subtracting 2 each time

so on the diagram it looks right down to the 3rd layer

but beyond that i assumed its n-8, n-16, rather than n-6, n-8

ill try to fix that and post an update

[haughty garden]

Sorry was just eating breakfast lol

[gleaming scaffold]

yup i made a silly mistake

[haughty garden]

Yeah so you should end up n/2 layers since each time you need to subtract 2

[gleaming scaffold]

call size is n-2i not n-2^i

n-2i leads to n=2i hence h=n/2

very frustrating

[haughty garden]

I believe each subproblem takes constant time to complete

[gleaming scaffold]

because 1,2,4 are obviously the same

yeah, each circle on the recursion graph is constant

[haughty garden]

So each layer takes constant time

[gleaming scaffold]

so you do sum from i=0 to n/2 of 2^i

which gets you to 2^n/2 completxity

which seems correct

[haughty garden]

Yeah that looks right

,w T(n) = 2T(n - 2) + C

[vital dew]

Results provided by WolframAlpha

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

Requested by opengangs#7348

[haughty garden]

Yeah so that’s Theta(2^{n/2}) complexity

Actually now that I think about, memoised algorithm would have the recurrence T(n) = T(n - 2) + Theta(1) which is linear time

[vital jolt]

@coral parcel where can I read more about transfinite cardinals and ordinals, and other large inaccessible cardinals like mahlo cardinals?

[fringe siren]

If we have a relation which is transitive we have the definition:
aRb & bRc => aRc for all a, b and c

What is the definition of anti-transitive relation?

[little prism]

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

[fringe siren]

Didn't know that intransitive and anti-transitive are different things

How can i prove that a intransitive relation is not symmetric or not antisymmetric?

[little prism]

well symmetric and transitive don't imply each other so I wouldn't even count on intransitive implying anything.

maybe first find some examples and check whether they always are symmetric or antisymmetric

[vapid drift]

Help

[neon raven]

Agnes: "I have 5 clue sentences."
Ramon: "I have 5 clue sentences."
Set: "Ramon doesn't have 5 clue sentences."
In a game, Agnes, Ramon, and Set each gave one clue sentence to Insi. Among the three, only one person gave the correct clue sentence. If Insi can guess who gave the correct clue sentence, then Insi wins. Who gave the correct clue sentence?

is it Set since he tells you that Ramon is lying in his statement which means Agnes must be lying

[fringe siren]

This is what i came up with

Another problem:
How can i prove this

[little prism]

symmetric does not imply transitive. I don't know where you pull aRc from but it's just wrong

[night merlin]

What have you tried? There's a really simple and somewhat obvious bijection which does the trick

[fringe siren]

Then how we can prove it. I can't think of an example

[fringe siren]

First i thought to represent S as a set af a series with 0s and 1s, where 2023 will always be 1

[night merlin]

That's overcomplicating it

But somewhat has the right idea

Or well, you can use that idea to come up with what it should be

Probably

[fringe siren]

Another thing i tried
P(N)\S is subset of P(N) and to show that they have the same power

[night merlin]

Think of it like this

Suppose you have a set in S

Then you know that 2023 is in the set

Is there a corresponding set in P(N)\S somehow? So can you construct a set in P(N) which does NOT contain 2023 using your set in S?

Think about your original idea if that helps

[fringe siren]

Hmm let me think for a moment

[night merlin]

Sure sure, take your time

It's hard to give hints without just giving you the bijection haha

[fringe siren]

So in P(N)\S there is no set containing 2023.
We cannot construct a set in P(N) not containing 2023 using S

[night merlin]

Yes you can

You just need to modify your set a bit

[fringe siren]

[night merlin]

So if you have a set A containing 2023, how can you take A and create a new set B which does not contain 2023?

[fringe siren]

B subset of A{2023}?

[night merlin]

A{2023}?

[fringe siren]

A \ {2023}

But then it is nit from S

[night merlin]

Yep, any subset of A\{2023} will be in P(N)\S

[night merlin]

A is still from S

Remember, you want to take a set in S, and turn it into set which is NOT in S

[fringe siren]

A yes, B is not

[night merlin]

And B is not supposed to be in S

B is your new set, which you're mapping A to

[fringe siren]

We will just remove 2023

[night merlin]

Yep

So the mapping $\varphi:S\to\mathcal{P}(\bN)\setminus S$ given by

$$\varphi(A)=A\setminus{2023}$$

does this trick then, yea?

[vital dew]

Lorago

[fringe siren]

Hmm so A is a set of all the sets with 2023 and B is the opposite?

[night merlin]

No, so A is one set with 2023, but it can be any set, and you wanted to find a way to create a corresponding set which does not contain 2023

In particular, you wanted to find a bijection $\varphi:S\to\mathcal{P}(\bN)\setminus S$, which is how you prove that $\abs{S}=\abs{\mathcal{P}(\bN)\setminus S}$

Whoops

[fringe siren]

Aaah omg i think i start to understand where you're going

[vital dew]

Lorago

[night merlin]

So the idea is to, for each set A in S, come up with a corresponding set B in P(N) \ S

[fringe siren]

So for arbitrary set A with 2023 we want to show that there is set B without 2023?

[night merlin]

We just want to find a way to do so which assigns a unique set for each choice of A

And so if we just remove 2023 from the set A, we get a unique such B, yea?

Since only one such A will give the set B = A \ {2023}

Does this make sense?

[fringe siren]

Yep

[night merlin]

(Also if there is anything I say which you do not understand, let me know)

[fringe siren]

That's like surjective linear mapping in a way

[night merlin]

Well it's a bijective mapping

So surjective and injective

Haha

Just not linear

And that is precisely what you wanted

[fringe siren]

I mean isomorphic

Sorry, messed up the terminology

[night merlin]

Isomorphic can mean a loooot of different things haha

In the context of set theory, an isomorphism is usually just a bijective function

So then it is an isomorphism

But you could also have, say, an isomorphism in the context of linear algebra, where it is a linear bijection between vector spaces

There are a lot of terms to keep track of in math haha

[fringe siren]

Yeaaah that's what i was thinking of
In the context of linear algebra

[night merlin]

Just be aware that isomorphism can mean a few different things :)

Depending on the structure of the sets you map between

But yeah if vector space isomorphisms help you think about this, then great

[fringe siren]

For any AU{2023} there is a subset B \ {2023} from the set P(N)\S

[night merlin]

Well you don't need that union if you take A in S to begin with, but yeah exactly

So your bijective map is given by $A\mapsto A\setminus{2023}$

[vital dew]

Lorago

[night merlin]

Where $A\in S$

[vital dew]

Lorago

[night merlin]

And similarly we can then obviously invert this by taking $B\mapsto B\cup{2023}$

[vital dew]

Lorago

[night merlin]

I.e. we can go back to our A by just adding back 2023 again

So this proves that the sets have the same cardinality

Does this make sense?

[fringe siren]

I understand

[fringe siren]

Yep

Thank you a lot

[night merlin]

No worries, always happy to help

[fringe siren]

I have one more similar problem will practice on it

[night merlin]

[vapid drift]

help please

[night merlin]

[neon raven]

https://dontasktoask.com

[vapid drift]

someone explain the proces 😦

even if vc is needed

hello

hello plz

[night merlin]

Don't expect immediate help. Not everyone active always knows the stuff you're asking about, or has the time to help (or wants to for that matter). Also please don't just randomly DM me and expect help just because I helped someone here.

[vapid drift]

ok can you help now

[night merlin]

No, because I am not familiar with it.

Also I am busy studying my own stuff

[vapid drift]

kk goodluck

[vapid drift]

can you help now

[fringe siren]

What is the difference between function and partial function?
The both definitions seem the same

[night merlin]

Write down the definitions again

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

Wikipedia has some nice pictures illustrating it

[night merlin]

Also, if no one helps you here, try the help channels

[fringe siren]

@night merlin what do you think about this formal proof?

Is it correct and is it exhaustive?

[night merlin]

I don't see what you're really doing when you're trying to prove that $f$ is injective. To me it doesn't seem like you're really proving anything in that part. For the sujectivity part, did you mean to write $f^{-1}(B)=B\cup{2023}$?

[vital dew]

Lorago

[fringe siren]

We can't write f^-1(B) since we haven't proven yet that f is bijection in order to have an inverse?

Yeah i agree that the injection part is kinda fishy.
How we prove injection for this function then?

[night merlin]

Well what you can do is just prove that $g(B)=B\cup{2023}$ is the inverse of $f$. Remember that $f$ is bijective if and only if it has an inverse, and some times finding an inverse is a much easier way to prove it

[vital dew]

Lorago

[fringe siren]

Ok, the BU{2023} is the inverse but how we prove it? Feeling like we are stuck in a loop.
Find inverse to prove bijection but to prove bijection you have to find the inverse

[night merlin]

Just check that f(g(B))=B and g(f(A))=A and you're done

Since that's the definition of an inverse

[night merlin]

You don't have to find an inverse to prove it's bijective, but a lot of times it's much easier, such as in this case

[fringe siren]

Got it

[night merlin]

[golden otter]

how can I simplify the following expression to not use sigma

[obtuse lance]

notice that it looks a lot like $$2^{2n-1}=\sum_{i=0}^{2n-1}\binom{2n-1}{i}$$ except it's about half of it. But hey, binomial coefficients are symmetric, so you can write out, $$2^{2n-1} = 2 \sum_{i=0}^{n-1} \binom{2n-1}{i}$$ so all you have to do is divide through by $2$ and add on the missing binomial coefficient, $$4^{n-1}+\binom{2n-1}{n}$$

[vital dew]

Merosity

[golden otter]

Your mind

Talent

Tysm

[small plume]

does short circuiting work in propositional logic ?

like if I knew r was T this would just evaluate to T, right ?

[brave rock]

That's not "short circuiting" — that's just the definition!

[small plume]

true I guess

[tight latch]

Can you guys help me to find the inverse of 2x2 matrix?

[vital dew]

The Great Giggleini

The Great Giggleini

[tawdry night]

Hi, I want to ask how to do this question? This is the answer I do.But I dont know what step I need to do?

[rapid mural]

use the hypothesis that n>=5

popbazic

[wise nexus]

You made a mistake while calculating the det

[rapid mural]

det:

[rapid mural]

be honest: did you use chatgpt

[rapid mural]

because this looks like what chatgpt wrote

[tight latch]

I just need some ideas

but I didn't conclude this as my answer

[weary tiger]

Hi! How can i sketch DAG with 1source and 4sinks?

[tepid lake]

Hi, when using simplification,
where p n q is equivalent to p,

am I allowed to simplify if q is (q n r) or something like (q U r)?

so if

p n (q U r), using simplification it is logically equivalent to p?

[fringe siren]

what does y∈AxB mean?
is it that y∈A & y∈B?

[vital dew]

Boytjie

Boytjie

Boytjie

Boytjie

[fringe siren]

i can't think of a way to check if this is transitive relation

what should we do here?

hmm, i get that this relation is transitive

but i dont feel confident with the way i got the transitivity

[brave rock]

There is no general way to check if a relation is transitive. You just have to try things out and, as is often important in math, be creative.

If you want us to check a proof, then post it.

[weary tiger]

How the whole sequence of binary numbers is presented as element of set and what does it mean?

I do not get concept of it which is used in exercise 7,9

Can anyone grasp it?

[kind panther]

idk in which channel i should ask this, but does someone know this?

[wise nexus]

Well

What're you stuck on?

Which part are you confused about?

[kind panther]

question b

[wise nexus]

I was hoping you would say that haha

It's the only one whose definition i don't know lel

Gimme a second

[kind panther]

yeah sure

[wise nexus]

Oh, ok

It's the edge version of cut points

When you delete it, the number of connected components increase

For example, the edge between C and Y is a bridge

Do you see why?

Can you find the rest?

[kind panther]

ohh okay ty

[wise nexus]

[subtle plover]

hi,

if i want to prove the statement:

if r and s are rational numbers, then r - s is a rational number

where do i start?

i think a proof by contrapositive is useful here, so i came up with this negation:

if r - s is not a rational number, then r and s are not rational numbers.

but i don't know where to go from there.

[coral parcel]

You've learned to subtract fractions, right? Observe that when you do that and the incoming numerators and denominators are integers, you get a fraction of integers out of it.

Contrapositive would make this rather more complex. (And by the way, the contrapositive would be: if r-s is irrational then at least one of r and s is irrational).

[subtle plover]

That makes a lot of sense

Also yeah, i forgot about that

If i were to use that technique with a/b - c/d where a,b,c,d are integers (and thus rational) what would the method of proof be called?

[coral parcel]

I'd call it a proof by direct computation.

[subtle plover]

This is my first time writing a proof for anything so dont mind my complete ignorance

So, in formal terms, just a direct proof?

Haha i think the hardest part about this is writing is clearly. The textbook I use regularly moves from plain english to symbols, sometimes at once

And thanks btw

[coral parcel]

Yes, that's a direct proof.

[steady moon]

Hello I am having a problem separating from statement and statement function

whats the difference?

[rapid mural]

are you talking about P vs P(x)?

post the original

[steady moon]

I have the question in #help-26

[silk inlet]

Can someone explain how first question of part b works?

[steady moon]

this is probability or I am wrong?

[weary tiger]

would numbers in an inverse function be a good example of a reflexive and symmetric relation thats not transitive ?

[silk inlet]

Permutations

[rapid mural]

waht?

[steady moon]

What does the line above B mean?

or the line above A and B?

[grand totem]

Complement; $\overline{X}={x\mid x\notin X}$

[vital dew]

Neverbloom

[lofty spear]

give an original example of a real-world device that uses a combinational circuit that relies on AND logic. Justify your answer.

[dusk sierra]

de morgans law

[crimson sentinel]

right

[dusk sierra]

complement is the line above

oh

someone already answered

[south marten]

Saw this challenge problem in another discord, can this be turned into a coloring problem ?

[small plume]

so p-> q means p iff q

can someone explain the last 2 rows

like how is p iff q true if p and q are F

[south marten]

My idea was to use burnside lemma to count the orbits but i'm not sure if it gives you the same results as the harmonic numbers (the legnth of a random n-permutation is 1/k) been trying to find an alternate solution but i'm not sure if my idea would work

[coral parcel]

There doesn't seem to me to be any clear coloring connection.

My argument would be that on an average day (assuming that mean that the order the n team members race in is picked as a random permutation), the probability that a record will be set by at the k'th start is the same as the probability that among the k first racers picked for that day, the best of them is randomly picked to race last -- and it ought to be fairly clear that this is 1/k.

And we can just add those probabilities together without worrying if they're independent, because we're being asked about an average, and expectations are additive even without independence.

[void crypt]

what specific graphs can be decompose into Hamiltonian path and cycle? good for a undergrad thesis research paper

[coral parcel]

No, "p -> q" and "p iff q" don't mean the same -- they have different truth tables.

However "F iff F" and "F -> F" both happen to be true.

As for why "F -> F" is true, you can find a lot of explanation attempts (including one by myself) at https://math.stackexchange.com/questions/48161/in-classical-logic-why-is-p-rightarrow-q-true-if-both-p-and-q-are-false

[small plume]

oh

thanks

[magic knoll]

could someone explain me stars and bars using generating functions

can't wrap my head around wiki's explanation

[south marten]

That makes sense 👍 when looking at the question I knew that we were dealing with a permutation but I wasn't sure how to go from there I tried using the formula for P(n;r) to get something but that didn't work.

[tawdry night]

Hi, anyone can solve these questions?

[snow mesa]

https://tenor.com/view/omori-omori-sunny-math-algebra-logic-gif-23535542

[halcyon dock]

help

[vague garden]

I had a question about radius in trees

I understand that they are the minimum eccentricity of the graph, but it's hard to intuitively imagine what that graphs out to specifically (like for example diameter is just the maximum distance between any 2 points in the graph) and as such I don't fully understand tree centers either

[halcyon dock]

help

[brave rock]

Posting your message once is enough.

If you actually want help, you should ask a specific question instead of simply posting your homework.

[steady moon]

How I can prove this?

do I try with random numbers?

[little prism]

try induction

or first partial fractions probably

[steady moon]

I am pretty bad with math induction

I thought with random numbers

and if I get the same result

[little prism]

examples dont prove anything

[steady moon]

Eh I dont have any other idea that will work for me

[gaunt nest]

Try it for n=1,2,3,... and see if you can see a pattern

[steady moon]

I think its not right

[cerulean wind]

hint:
$$\frac{1}{(i+1)(i+2)}=\frac{1}{1+i}-\frac{1}{i+2}$$

[vital dew]

c squared

[steady moon]

you sure?

[cerulean wind]

yes

[brave rock]

check it yourself

[steady moon]

it turns out to be true

but how do you get that?

[brave rock]

(1) spotting it, or

(2) the partial fractions method

[steady moon]

when I replace i with 2, on the left side is 1/12 and on the right side is 3/4

But when I try to find a2

then its ok with n+1/n+2

[cerulean wind]

wot?

[steady moon]

well when I replace i with 2 here

[cerulean wind]

...

yes

they should be equal

[steady moon]

I think they are not

its 1/3 * 1/4 = 3/4

wait wait

[cerulean wind]

subtraction not multiplication

also: in general, it is not a good idea to convince yourself that some equation or theorem is true by testing it out for a couple of values. there should be a clear reason/proof as to why said equation or theorem is true

its fine if you want to check your result or gain intuition, but not enough to verify if a statement is true or not

[south marten]

This is just a function composition look at an example

[steady moon]

also what does the x mean?

And in this case A = {a, c} and B = {b} right?

[rapid mural]

cartesian product

A x B = {(a,b) | a in A, b in B}

[steady moon]

Can you solve this?

the picture below

[rapid mural]

sorry kind of busy

[steady moon]

whats in A whats in B

ah okay

[small plume]

can someone help prove that these are logically equivalent

using equivalence laws

[gaunt nest]

General strategy with these is to "push negation inward" with De Morgan

So anywhere you see ~(...), try pushing it in and see what happens

[small plume]

yea so I got stuck after using demorgans lol

[gaunt nest]

how far did you get?

[small plume]

p and (q or not q or r)) and not r

should I try to distribute?

[gaunt nest]

What can you say about "q or not q" ?

[small plume]

tautology?

[gaunt nest]

Right, by law of the excluded middle

(or sometimes people have other names for that. But I call it LEM)

[small plume]

hmm so like what do I do

just get rid of it?

[gaunt nest]

Depends how formal you want to be, I guess

but (q or not q or r) is the same as (True or r) which is the same as True

and then x and True is the same as x

[small plume]

yea

[gaunt nest]

Those are the intermediate steps I would write

[small plume]

so am I left with p and r and not r ?

[gaunt nest]

Hmm, not quite

$p \wedge ( \top \vee \sim r) \wedge \sim r$

That much from LEM right?