discrete-math

[naive gulch]

so 33 (mod 19)

so c = 12?

I think I got confused on the relationship of c and the right hand side

c is the remainder

[faint narwhal]

uh check your subtraction again

[naive gulch]

oops 14

jesus I lack basic math

[tranquil flint]

if i have x = a mod (7^2)

does that mean x = a mod (7)?

since 7 prime

[obtuse lance]

doesn't matter that it's prime, if x=a mod m*n then x=a mod m

go back to what the definition of what it means for x=a mod mn to see why

[tranquil flint]

I see thank you

If I have a system where x = a mod p, x = a mod q, x = a mod r^2, where p,q,r are prime, I can solve x = a mod p, x = a mod q, x = a mod r instead correct?

Im trying to implement fermat's little theorem into each of the congruences, as a is a power representation

and then apply chinese remainder thm

[obtuse lance]

yeah, in particular relating the powers of a prime together is hensel's lemma

putting the separate prime powers together is the chinese remainder theorem

[tranquil flint]

Ohh i see, i know that the pair wise gcd of p,q,r^2 are obviously 1 for each pair. but solving for x in this manner will give me the same x using CRT as if i were to solve with r^2 instead of r

the r^2 just doesnt allow me to use fermats little thm

and im not allowed to use euclids thm with his prime counting function

[obtuse lance]

not sure what you mean exactly

hensel's lemma lets you take solutions mod r and go to mod r^2, mod r^3, etc

however high you need to use with CRT

[tranquil flint]

I havent learned hensel's lemma

what does it say?

[obtuse lance]

well, for going from r to r^2 you probably don't need it

[tranquil flint]

ohh ok

[obtuse lance]

so I wouldn't worry about it for now

I think I see what you're saying now about fermat's little theorem

you can use the euler phi function, euler's theorem generalizes fermat's little theorem

[tranquil flint]

Noo my pset specifically states not to use it 😭

[obtuse lance]

lol oh you called it euclid's theorem and prime counting function I see

[tranquil flint]

I think i kinda got it basically i got x = 1 mod 7

[obtuse lance]

well I don't know what you're allowed to use otherwise

[tranquil flint]

therefore x = 1 mod 49

if x=a mod m*n then x=a mod m
is this an iff statement?

im trying to think about it, if x and a have the same remainder when divided by m*n, then x and a have the same remainder when divided by m

[obtuse lance]

try to come up with a counterexample

[tranquil jungle]

I've shown a) already, do I have to do a full separate proof for b)? b) looks like it's true by some definition

[quartz cedar]

How is this not the answer? What else can I do?

[stray reef]

A(m,P(x)) is just nonsense

∀x P(x)->A(m,x)

[naive gulch]

This is throwing me for a loop, where did you get a = nmc?

[flat inlet]

substitute b for mc

[clear sierra]

Does my proof make sense to you all?

[faint narwhal]

the ideas are there, but its pretty unrigorous

[naive gulch]

Ah okay I don't see how I didn't see that before, but then after that provides c is a multiple of a because nmc right?

[flat inlet]

precisely, nm is an integer, and if a = nmc, then a is an integer multiple of c

therefore c divides a

sorry I made a dumb error before in swapping some letter around in my fugue state

[naive gulch]

Yeah that's what I wrote down

sweettt

[flat inlet]

a|b, b|c, then a|c is because b = na, c = mb, then c = mna, and so a|c

that's the proof written properly, sorry if I confused you earlier

[naive gulch]

yeah no problem I get it!

could someone give me some pointers for starting this? Do I need to use two more variables like s and t?

[flat inlet]

generally with these problems you want to just rewrite these expressions in their algebraic forms so you can manipulate those expressions

so in this case, if a congruent b (mod m), then a - b = km

[naive gulch]

ooh yeah I was looking at how to convert but I just learned this so felt overwhelmed mb

hmm so on the right hand side we could say ac - bc = k(mc)?

[flat inlet]

exactly

then that is equivalent to ac congruent bc (mod mc)

and voila, you've completed the proof

[naive gulch]

wha-

Its that easy?

[flat inlet]

well obviously things will get a little more involved but yeah early number theory proofs are fairly straightforward once you know the tricks

[naive gulch]

Wait so we know that a ≡b (mod m), and we know that can be written as a - b = km. For this problem that can be modified into a(c) - b(c) = km(c), which is ac congruent bc mod mc

[flat inlet]

yes

[clear sierra]

What do you mean by unrigorous? @faint narwhal

[faint narwhal]

what does it mean for there to be an image of f to match every element in the codomain? Why must this happen? How are you using injectivity here?

[naive gulch]

I'm a little confused how m is more than or equal to 2 and c > 0 is relevant then

[faint narwhal]

what does it mean for each element in the domain to be needed to project onto an image? How are you using the finiteness of the sets A and B?

[clear sierra]

it must happen because there are an equal number of elements in set A and B

[faint narwhal]

How does that imply that?

[clear sierra]

that's what I'm struggling with, it just kinda does.

like it makes intuitive sense i just can't think of how to "prove" it

[flat inlet]

the fact that c > 0 is what makes multiplying by c on both sides relevant, e.g. if c = 0 then of course 0 = 0 (mod 0) since 0 = k0 = 0

and since m is a positive integer, setting m = 1 or 0 is also a trivial case

[faint narwhal]

How have you guys defined what it means for |A| = |B|?

[clear sierra]

The values of each element in the set are equivalent, and the number of elements in each set are equivalent

[faint narwhal]

Uh what

You should go check this definition again

[clear sierra]

Is |A| not the domain and |B| not the codomain?

[naive gulch]

I believe it's the power set

[faint narwhal]

A and B are just sets

|A| is usually called the cardinality of A

[naive gulch]

how would 1 matter?

I can see 0

[clear sierra]

OOH

yeah we covered that I just forgot

so the number of elements in each set are equal, not necessarily the value

but that shouldn't change what I wrote any

[faint narwhal]

What does it mean for the number of elements in each set to be equal? How do you define number of elements when the set is infinite?

[flat inlet]

actually I guess m = 1 isn't really a trivial case

not really sure why they excluded it

[clear sierra]

i don't understand where you're leading me.

[faint narwhal]

The point is that to do things rigorously, you need a rigorous definition

Trying to use intuition such as "numbers of element in each set are equal" just ends up making your proof informal and unrigorous

So your class probably defined rigorously what it means for |A| = |B| somewhere and you should look for it

[naive gulch]

ok! Thanks for your help <3

[clear sierra]

okay i see

[faint narwhal]

The most common choice is that |A| = |B| if and only if there is a bijection between A and B, but there are alternatives

[clear sierra]

so when I put the symbols into words I should use the formal definitions not my intuition

[faint narwhal]

yes

[clear sierra]

otherwise does the logic I use check out?

if A->B and B->A then A is true if and only if B is true

is what I was going for

[faint narwhal]

I mean sure that part is true, that's just the definition of if and only if

but there's not really any other logic, just some vague statements

[clear sierra]

How about this? @glossy adder

the second one is the same as the first one just the bottom isn't cut out where it says preimage

[quaint star]

Sure. What have you tried?

Take the two expressions in the square brackets, and simplify those first

Nvm, don't use that yet

Do you know how intersection and union distribute over each other?

$$A \cap (B \cup C) = (A \cup B) \cap (A \cup C)$$

[vital dew]

Lunasong

[quaint star]

And the same thing if you swap union and intersection

Try to use that

Because if you manage to intersect a set with itself, then that will simplify it greatly because it will just be itself

[vital dew]

vinc3nt

[quaint star]

@wispy linden Yes

Distribute that

Apply the distributive law

Doing it to the second square bracket is easier. So try that one first if you can't do this one

[vital dew]

vinc3nt

vinc3nt

[quaint star]

@wispy linden how did you get that?

You just swapped the intersection and union

You didn't distribute

No

Why did you write A as A cap A?

You are making it more complicated

Just distribute the A in

Oh nvm, wait

[vital dew]

vinc3nt

[quaint star]

You were right

I swapped the union and intersection in my mind lol

Now can you do the first square bracket?

[vital dew]

vinc3nt

[quaint star]

No

Can you show your work for how you got that?

[vital dew]

vinc3nt

[quaint star]

A union B union C looks suspicious.

[vital dew]

vinc3nt

[quaint star]

You can

But fix the other one

The A union B union C part is wrong

You are distributing an intersection but there's no intersection there.

You went from (X cup Y) cap Z to (X cap Z) cup (Y cup Z)

insteaf of (Y cap Z)

Yep

Now you can distribute A cup B again

Nvm

Not yep

Check again

Yes

Now distribute again

What

Oh, yes

Okay, now

Wait

We can simplify both expressions a lot more

Are you aware that if B is a subset of A, then B cup A = A and B cap A = B?

The union equals the bigger one, and the intersections equals the smaller one

You can apply that to both

No

You don't know whether A or B are subsets of each other

I am talking about (A cup B) and (A cup B cup C). One of these is a subset of the other.

Yes

A cup B is a subset of A cup B cup C

So their intersection is A cup B

What do you mean?

Simplify the other expression too

I've lost track of which is which. So tell me what the whole thing looks like now after all the simplifying.

[vital dew]

vinc3nt

[quaint star]

Yeah but after simplifying, what does it look like now?

We simplified the first part all the way to A cup B

@wispy linden oh, I see what you mean. I totally wasted your time with distributing, lmao.

You could have just checked which is a subset from the start

Sorry, it's early 😂

Compare A and A cap (B-C). Which is a subset of the other?

Yes, so what does their union equal?

So now you just have

(A cup B) - A

No, you can keep going

No

Yes

That's the simplest

I actually studied from that book last year

I like the book. It's quite simple as an introduction to formal set theory. But you first need to be comfortable with naive set theory which is what you are doing.

That book is about like set theory axioms, which is not what you should be focusing on

I don't know :/

I just learned naive set theory from other courses. I never used a specific book for it.

[quartz cedar]

I am fully confused can you explain

[stray reef]

P(x) is a boolean

[quaint star]

A(x, y) means person x admires person y. But P(x) is not a person, so it doesn't belong there.

Np

[quartz cedar]

Ah

[quaint star]

No

Only the problems that I solved lol

But no official solutions

[quaint star]

@wispy linden Thanks, but delete the link. We have a rule about pirated links.

Oh, nvm

It's not pirated. Just someone who uploaded their own solutions.

[slow jewel]

Anyone know how you would use inclusion-exclusion here

[stray reef]

do you even need inclusion-exclusion here?

i mean, since all you care about is the parity of your rolls, you may as well replace the die with a coin

you will get between 0 and 8 even numbers in your roll, and the rest will be odd

rolls with 0, 1, 2, 7 and 8 evens are the ones not to be counted

[slow jewel]

I have no idea how to use inclusion- exclusion here and i have no idea what yur talking about.

[stray reef]

ignore my 2nd message

anyway

my question is

[slow jewel]

i hate my life

[stray reef]

do you even need inclusion-exclusion here?

like

will you be sent to gulag if you solve this problem without using inclusion-exclusion

[slow jewel]

thats what the lecturer said

but i wouldnt know

[stray reef]

so the lecturer said "you have to solve this problem using inclusion-exclusion, and if you don't i'll send you to gulag"?

[slow jewel]

no

no he didnt

[stray reef]

anyway, there is a straightforward solution route for this.
there are only 9 possible situations in terms of how many even and odd numbers you get:

8 even, 0 odd
7 even, 1 odd
6 even, 2 odd
5 even, 3 odd
4 even, 4 odd
3 even, 5 odd
2 even, 6 odd
1 even, 7 odd
0 even, 8 odd
find the probability of each of these.
then add up the ones which meet the requirements of >=2 odd and >=3 even.

[slow jewel]

For some reason i get Dyscalculia when it comes to counting problems

How do i work our the probabilities?

0.5^8?

[stray reef]

that's the probability for the all-even case

and also the probability for the all-odd case

...i don't know if your class has introduced you to the binomial distribution yet

[slow jewel]

I should've became a physicist

[weary tiger]

if im understanding this right, for a relation to be considered total order, every pair of elements on a set X must be related to each other?

[quaint star]

Yes, that's the difference between a partial order and a total order

[weary tiger]

so every relation that is total order is also partial order but not visa versa

[quaint star]

Yes

[quaint star]

Did someone ping me and delete? 👀

[lilac delta]

How to answer the 1st one

[analog sonnet]

For all x, x is an accountant implies x owns a Porsche

[lilac delta]

Is this the correct way to write it symbolically?

Or do I need to put a right arrow between p(x) and q(x)?

[weary tiger]

for this, im not sure why they are multiplying the 1st fraction by 6/6 and the other by 11/11

[shadow warren]

Can someone please help me with this?

[haughty garden]

You eventually want to have 6! * 11! on the denominator so multiplying the first denominator by 6 gets you 6 * 5! = 6! and multiplying the second denominator by 11 gets you 11 * 10! = 11!

[weary tiger]

Can someone help me with this please

[balmy hornet]

"not all who wander are lost" would use an existential quantifier?

[weary tiger]

thank you!

Prove that if a relation R on a set X is reflexive but not symmetric, the collection of pseudo equivalence classes does not partition X.

Does anyone know what 'collection' is supposed to imply. do i combine the values in each equivalence class together to see if it partitions X?

[mystic moss]

Yeah take the equivalence classes as sets and see if they partition the universal one

[quartz cedar]

Hey going off your logic for 6a, can I get you to check these other 2 I tried doing based off it

b. ∀x S(m) → A(P(x),m)
c. ∀x S(m) → A(m,m)

[quartz cedar]

Also I'm doing this propositional logic statement:

"My sister wants a black and white cat"

And I don't know how it can be possible to do. It's not something like: p = my sister wants a white cat, q = my sister wants a black cat. p ^ q.

But its one, multicolored cat

[minor lake]

Can someone guide me or something

[minor lake]

nvm

https://proofwiki.org/wiki/Symmetric_Difference_is_Commutative#:~:text=Symmetric difference is commutative%3A,∗T%3DT∗S

[stray reef]

@quartz cedar what's S()?

also A(P(x),m) is still nonsense

"mary admires herself" is just A(m,m) no quantifiers at all

[quartz cedar]

S is student

and why no quantiifers?

[stray reef]

why would you need quantifiers for "mary admires herself"

[quartz cedar]

Just trying to base it off of the first one tbh

@stray reef

And then for #2, S(m) is similar to how you did P(x) for professor X. Student->mary?

[stray reef]

does it require explicit clarification that mary is a student?

[quartz cedar]

Technically no

[stray reef]

well then

[quartz cedar]

Also though

[quartz cedar]

Also I'm doing this propositional logic statement:

"My sister wants a black and white cat"

And I don't know how it can be possible to do. It's not something like: p = my sister wants a white cat, q = my sister wants a black cat. p ^ q.

But its one, multicolored cat

im thinking maybe

p = my sister wants
q = a black and white cat

[stray reef]

uh

no

[quartz cedar]

But at the same time like wtf ?

[stray reef]

this sounds like an atomic statement

[quartz cedar]

Does that mean its not possible?

oh just googled it

[nimble glade]

Does anybody know how to do this one? I'm stuck on this practice question

[stray reef]

which part?

[nimble glade]

If possible all parts, I understand A a little bit but thats it

[stray reef]

part b is just algebruh

just expand the right-hand side and simplify

[nimble glade]

Okay I dont need to show anything else right

[stray reef]

i mean, it says "show algebraically"

... okay so have you done induction before?

i don't really want to just give you the proof but i'm not exactly sure how to hint at it or what your doubt is

nor do i know what part of (a) you don't understand

[nimble glade]

I have but don't understand it if im gonna be honest

Proving is something I struggle with,

[stray reef]

there are two key properties of integers that you will need to make use of in this proof:

• the sum of two integers is an integer
• the product of two integers is an integer

[nimble glade]

Okay, hopefully that will get me started and know what I'm doing, thank you sm

[weary tiger]

Prove that if a relation R on a set X is reflexive but not symmetric, the collection of pseudo equivalence classes does not partition X.

how does this prove that it cant partition X?

[weary tiger]

its very close to mengers theorem

but not sure how to prove it

[mystic moss]

@weary tiger try adding a vertex to the graph

[weary tiger]

oh makes sense got it cheers

ugh that seems so simple now i know

how to do it lol

how would you proof this?

consider (1+1)^n

or consider the number of subsets of size n

or use induction

i tried induction, wont that just be (k+1)!/ (k+1 -(k+1)! (k+1)!

honestly dunno what u mean by that

but if you use induction

easiest way is to use the identity $\binom{n-1}{m-1}+\binom{n-1}{m}=\binom{n}{m}$

[vital dew]

same

[weary tiger]

id probs just do it in one of the other ways though

cuz a lot less steps lol

the book says a hint is to use (1+1)^n

but where does (1+1)^n come into this?

[obtuse lance]

do you know the binomial expansion (x+y)^n

[weary tiger]

not yet lmao thats not the next topic after doing this one

[obtuse lance]

the hint is kind of weird then

[weary tiger]

it was taught to me a bit in calc 2 but i completely forgot

[weary tiger]

can someone explain wtf this is saying lol

[maiden drift]

I think the most intuitive way to think about this problem is suppose you have a n element set. Recall the power set has 2^n elements, consisting of precisely all the subsets of of our n element set. You are then counting the total number of 0 element subsets of n, 1 element subsets of n, up to n element subsets of n.

[valid wave]

hi im confused

could someoen clarify plz

im conused by the idea of antisymmetric

if 1,2 and 2,1 are on a set

isnt that symmetric

so in what case is something antisymmetric

the example is confuising me

because why does a and b have to be the same

[quaint star]

@weary tiger Hours late, but a partition is a collection of DISJOINT SETS whose union is the entire set. So [a] and [b] are not the same set, but they are also not disjoint, which means it's not a partition.

[weary tiger]

ah okay, that clarifies it. thank you

[quaint star]

Np

[mystic moss]

What parts did you get

[valid wave]

plz

this is so confusing

ohhh i understand now

[weary tiger]

i think just the idea of a discrete set

im not sure about

what even is a neighbourhood in this context

just any subset of or R^2 associated with x?

[mystic moss]

Yeah just some connected space containing x I think

I’m guessing the idea is that you can’t have two nodes infinitely close together

[weary tiger]

oh makes sense I thought it was weird that it said <=1 but I guess that's just for when X is empty

[minor lake]

https://cdn.discordapp.com/attachments/488104216678760469/812518158967242782/320984783234531338.png

I'm being asked to find the relation between two sets

Consider $A$ et $B$, deux ensembles. Compare (=, $\subseteq$, $\supseteq$) \

[vital dew]

Chad

[minor lake]

Here are the answers

so for the one I posted above they are equal

[vital dew]

Chad

[minor lake]

and for this one it's \subseteq

I just don't understand the answer

and I think that both of my proofs are entirely wrong

[minor lake]

nvm

[naive gulch]

idk if this allowed here but

my discrete math server has no chill

[unreal stump]

I mean,We know their names since you used them in that convo

So, There's no point hiding that

[north jewel]

Is there a way to count the number of $N \times N$ matrices such that every row and column contains each number $1$ through $N$ exactly once?

[vital dew]

Frank

[north jewel]

Like sudoku but without the constraint that requires each 3x3 box to contain the numbers 1-9

[stray reef]

these are called latin squares, i think.

[north jewel]

ah perfect! that's what i was looking for thanks

[faint narwhal]

Can you explain your thought process for what you did?

[stray reef]

and why isn't 50 in your answer?

yes

[languid cradle]

what’s the best way to go about proving this does not contain a Hamilton circuit?

I know that any vertices with degree 2 must have their incident edges in the circuit

and that no smaller circuit can exist within the Hamilton circuit

but there’s no vertices of degree 2 here

[faint narwhal]

Hmmm

You can argue that each one of these 4 vertices like bcde, there's only really one way to go through them

[languid cradle]

through b and e?

[faint narwhal]

So a hamiltonian circuit must include either the path bdce or bcde or the same things in reverse direction

[languid cradle]

yeah so maybe treat those diamonds like 1 vertice?

which would then basically have degree 2

[faint narwhal]

Yeah exactly

And then this graph it's easy to show you can't have a hamiltonian cycle

[languid cradle]

ok bet thanks :))

cus then it’s just a square with a vertice in the middle

and a square gonna be a smaller circuit

[weary tiger]

This isn't a total order right

only partial

[faint narwhal]

yes

Well, if X is only one element, then its a total order

[minor lake]

https://math.stackexchange.com/questions/1482120/prove-that-pa-∪-pb-⊆-pa-∪-b

I don't understand this proof.....

more precisely

Case 1. Suppose X ⊆ A. Then X ⊆ A∪B,

Then X ⊆ A∪B

like what???

[faint narwhal]

A∪B is the combination of all elements in A and B right?

[minor lake]

yea

[faint narwhal]

So if X is a subset of A, then it makes sense that X is a subset of A∪B

Since everything in A is in A∪B

[minor lake]

oh shit

big brain fart

thanks

[worn vale]

Hey, I'm struggling a bit with combinatorics. I would appreciate if someone could DM me and answer a couple of questions.

[barren lily]

If possible, determine the values of a and b of the "cifra" C identical to aP+b(mod 26), knowing that the letter B was coded in C and the letter C was coded in F. Without Using the codification table, verify if there are letters that codify themselves.

Does anyone know how to help me with this?

I'm a first year in computer science and I'm struggling with this...

[royal pier]

Hello, I was wondering if anyone has a** good resource or textbook for discrete math**. I am currently taking a course and struggling in it as the given textbooks is quite bad with minimal to no explanations or examples. and would appreciate any resource

[fallow pawn]

for steady ripple, is it right if i do it like (3c1 * 22c11 * 11c6)*2 since i choose 1 signal out of 3 then 11 cards out of 22 thats either even or odd then 6 card hand out of those 11 cards

[weary tiger]

https://cdn.discordapp.com/attachments/811712657807769603/812854541920894986/Untitled.png

asking for a friend

how to do this

[languid cradle]

belongs in logic

but basically q -> not p is the same as p -> not q

so p -> (q and not q)

which is a contradiction

so not p

anywayyy

I know the n-d > q where n is the number of vertices in a graph, d is the smallest degree of a vertex, and q is the size of the largest independent set in a graph

but I’m trying to wrap my head around how to explain

maybe n-d is the number of vertices not connected to the lowest degree vertex

[mystic moss]

Take any vertex

It is connected to at least d other vertices

So any independent set containing that vertex can’t be bigger than n-d

[languid cradle]

ahhhh

ok sweet thanks so much

I guess it can’t even be n-d actually

because that vertex itself is a part of n

[mystic moss]

The vertex would also be part of the IS

[languid cradle]

oh true, nvm

good looks

[burnt frost]

this might sound dumb but can anyone tell me when youre supposed to use a proof by contradiction and when to use a proof by contrapositive

[minor dagger]

for proof by contradiction you want to assume the statement you want to prove is false and find some sort of contradiction this way

if you look at the proof that the square root of 2 is irrational for example

you are assuming it is an irreducible quotient and showing that it can still be reduced which is a contradiction

proof by contrapositive uses the contrapositve of a statement which is logically equivalent to the statement itself

sometimes it is easier to show the contrapositive holds

rather than the statement itself

[whole latch]

Is random sequence extrapolation possible to complete?

[naive gulch]

Can I do this by direct proof, just give an ex.?

[quick folio]

what book is that btw

and no

[naive gulch]

Discrete math and its applications by rosen

@quick folio can you give some tips for beginning it?

[quick folio]

yessir

(2k+1)^2=4k^2+4k+1 = 4(k)(k+1)+1

k*(k+1) = 0 (mod 2)

4k(k+1) = 0 (mod 8)

4k(k+1)+1 = 1 (mod 8)

@naive gulch

[naive gulch]

woah

uhh

shoot its +1 so we know its odd?

I have zero intuition to think of that

[errant bear]

should clarify that k(k+1) = 2m

[burnt frost]

thanks! @minor dagger

[naive gulch]

This is how I tried to do it but evidently got an even integer

I'm not totally sure what you did in your steps?

[quick folio]

@errant bear oops

k*(k+1) = 0 (mod 2) i thought that would give them the idea

n^2 is always gona be an odd number

realise that 4* an even number is divisible by 8

and you have 1 remainder

[solid trench]

please teach me discrete thanks

[quick folio]

teach me 1141 and ill teach u 1081

@solid trench

[solid trench]

i dont do 1141

[quick folio]

ok 1151

nurd

[solid trench]

idk its just maff

[quick folio]

1081 is legit du hw

[solid trench]

lol

[pallid belfry]

How would I go about doing problems like this? Just looking for some tips or hints to get me started

[stray reef]

#1 takes a little bit of thought to arrive at a trivial answer, the rest can be solved as stars-and-bars problems

[fallow pawn]

can someone explain this to me, i dont understand the second line of the bayes law in this case

[weary tiger]

I mean $P(HHTH\mid B)=P(H\mid B)^3 P(T\mid B)$ by independence and ${B, F}$ is a partition of your space so by the law of total probability $$P(HHTH)=P(HHTH|B)P(B)+P(HHTH|F)P(F)$$ $$=P(H\mid B)^3P(T\mid B)P(B)+P(H\mid F)^3P(T\mid F)P(F)$$

[vital dew]

Seek help

[weary tiger]

@fallow pawn

[whole crane]

Sorry, would a question about time complexity of an algorithm belong here?

[weary tiger]

Sure

[whole crane]

Let me copy it

I have a question about the 3-way mergesort algorithm
In the original mergesort algorithm, I found that the number of operations required for a single call of a merge function is
4L + 2, where L is the size of the merged array
That expression can be bounded by 6L
In 3-way mergesort, when calculating the number of operations required for a single call of a merge function, I get 7*L+3
Am I right?

[whole crane]

?

[whole crane]

...

[balmy hornet]

How would I approach this problem?

Prove that for all n ∈ Z, n is even if and only if n + 2 is even. (direct proof)

• n is an element of the integer number set
• n is even <-> n+2 is even

1. Let n be an even integer
2. Since n is even, there is some integer k such that n = 2k
   • 2k+2
   • This step i have is there as an idea from what i have gotten from the lecture slides

[faint narwhal]

That's the right first step

What do you think you should do next? Maybe think about what your goal is

[balmy hornet]

from what i am seeing from the slides, although it is a different problem, is assign the n as something. thats why step 2 is there but i do not think it is the right approach. it could just be k and not 2k

[faint narwhal]

Well, you want to use the fact that n is even right? And setting n = 2k is how you use that its even

[balmy hornet]

should the equation i write our afterwards then just be 2k+2. Should i factor it to be 2(k+1)?

[faint narwhal]

Yep

[balmy hornet]

Now I can assign, integer m , which is (k+1). This now shows n+2= 2m. This makes n+2 even?

[faint narwhal]

yes exactly

[balmy hornet]

Thank you @faint narwhal

[whole crane]

Help with this please

[balmy hornet]

@faint narwhal what happens if something does not factor? sorry for the ping

[faint narwhal]

Not sure what you mean

[astral bone]

can somebody please teach me what the S.I.R model is in a few minutes?

[balmy hornet]

It's a different problem. Sorry for the lack of info. Prove by contrapositive: Let x ∈ Z. If x2 − 6x + 5 is even, then x is odd. So I would flip it and say " If x is even, then x^2-6x+5 is odd. I can then let x be an arbitary even integer. So I then set x equal to 2k (x=2k). I wil then replace all the x's in x^2-6x+5 with 2k. The result is 4k^2+12k-5. Does it have to factor to prove that x is then even? Correct/point out anything that sounds wrong

[faint narwhal]

Odd numbers don't necessarily factor in the same way that even numbers do

So even numbers are always of the form 2n where n is an integer, and odd numbers are of the form 2m + 1 where m is an integer

So for your problem, you want to factor it into the form 2 * ( ) + 1

where some integer goes into the parentheses

[balmy hornet]

yes, which i would have to take into consideration that x is now even. so then 2n? if that is done, 4k^2+12k-5 is not factorable from what i believe to make it into 2 * ( ) + 1

[errant bear]

5 = ?

[balmy hornet]

wait

its +5

ok wait

[errant bear]

sure, but that doesnt really matter

[balmy hornet]

what do you mean that 5=?

[errant bear]

5 is odd so make a substitution

[mystic moss]

where are you getting these numbers from

[whole crane]

4*L+2

2 index initializations (i,j)

L iterations inside for loop:

+1 comparison

+1 assignment to the merged array

+1 update of i or j

+1 update of index k (merged array)

Just caught my mistake

The number of comparisons in an iteration of a 3 way merge are 2

So the total number of operations for a single merge call is 5*L + 3

Which can be bounded by 8*L

[mystic moss]

are you counting the exact number of commands? or are you just bounding it

[mystic moss]

also don't you also have to check that i and j are in bounds

[nimble glade]

Yall I'm freaking out I saw this in the textbook and idk how to do it 💀

[gaunt gazelle]

answer plz

[unreal stump]

Why does this look like a test?

[gaunt gazelle]

Homework in google forms

plz help, submission time at 5pm

[hybrid tendon]

is there any algorithm to find the largest number in all possible combinations? or any form of elimination?

[empty mauve]

Biggest number in combinations? Elaborate

[hybrid tendon]

I have N numbers and N C r sets with each set having r elements

I can't generate all the possible combinations and then find the largest value in set. That would be time consuming

[stray reef]

what do you mean by "largest value in a set"

do you want the set with the largest sum?

@hybrid tendon

[hybrid tendon]

No, @stray reef
I need to get all combinations of nCr first.
then find the largest value in each combination

5 choose 3 = 10
there would be 10 sets,

elements:
[ 2, 2, 3, 4, 4 ]```

[stray reef]

wait

this looks like a lot of work in the general case

what do you need it for

[hybrid tendon]

I need to find the sum of all largest values from each set, I found a way to solve it, but has some minor issues

[stray reef]

you dont need to explicitly list out the subsets themselves

[hybrid tendon]

No, just the sum

[stray reef]

just sort your set (or array? you seem to be ok with repetitions, so it's gonna be an array rather than a set)

[hybrid tendon]

yea, that's What I did. then I found
(N - i) C (r - 1)
and multiplied with the array that is sorted in reverse

[stray reef]

so that your numbers are $a_1 \leq a_2 \leq a_3 \leq \dots \leq a_N$ (from smallest to largest), and then your sum will be $$\sum_{k=r}^N \binom{k-1}{r-1} a_k$$

[vital dew]

Ann

[stray reef]

...yeah

[hybrid tendon]

wait this is different

[stray reef]

its different because i'm sorting the array in ascending order

in any case the sum youre looking for is just a linear combination of your array elements

what were your minor issues

[hybrid tendon]

I have to implement in C++, and have to do %1000...07

but the final answer seems to be wrong

I checked for overflows also couldn't find what's wrong

[stray reef]

you have to do it mod 1 billion + 7?

you can compute each term mod 1,000,000,007

and take mod 1,000,000,007 at every addition

[hybrid tendon]

how did you know the number exactly?

[stray reef]

i've seen programming olympiads pull this shit lol

[hybrid tendon]

well for multiplication, I'm using some other function
that does the job for me

[stray reef]

how big is N?

[hybrid tendon]

1 ≤ N ≤ 100000
1 ≤ R ≤ 50

[stray reef]

hm

,w 100000C49

[vital dew]

Results provided by WolframAlpha

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

Requested by Ann#0413

[hybrid tendon]

no sorry

[stray reef]

i think there might be some overflow bullshit with the binomial coefficients

hrm

what function are you using for those?

[hybrid tendon]

1 ≤ N ≤ 100000
1 ≤ K ≤ 50
1 ≤ ai ≤ 10^9

but it doesn't work properly for a known case, that's my problem

[stray reef]

theres nothing wrong w/ the formula mathematically, the only issue lies in the calculation of the binomial coefficients

which... you've said there's a function that does it for you?

[hybrid tendon]

am I allowed to post the array here? (size 50) its just a practice and not some competition or smth like that

[unreal stump]

Project euler?

[hybrid tendon]

no

@stray reef when I should I mod with 1000000007? while multiplication or addition or while both?

[stray reef]

probably as often as possible to minimize overflows

[hybrid tendon]

will it okay to mod it even while additions?

[stray reef]

...

i said

as often as possible

[hybrid tendon]

hmm.. works for most of the cases, but still doesn't work for some cases

[fallow pawn]

how can i calculate ripple thats not steady ripple

<@&286206848099549185>

[naive gulch]

What is this question even asking D:

[pale epoch]

a composite integers is not prime

this question wants you to find integers y, y+1 , ..., y + (n-1) that are not prime

[naive gulch]

ok I kinda understand?

But someone recommended me factoring out a c

I'm trying to follow along his logic here, what would the intuition be for the c?

[pale epoch]

if you want to show a number is composite you have to factor it in some way

[empty mauve]

Might this get solved if I were 2 offer a bounty?

[pale epoch]

maybe try asking in #combinatorial-structures

[weary tiger]

im working on simple recurrence atm

can someone explain the intuition of how the left side is equivlent to the right?

[faint narwhal]

It's a geometric series if you've seen those before

[weary tiger]

ah i did that in calc a few quarters back

[minor lake]

So,

I was really confused about whether I should use $\Leftrightarrow$ or $\Rightarrow$

[vital dew]

Chad

[minor lake]

The explanation I got so far

is that => was like -> but only for true cases

since -> can be false sometimes and since => is always true it can be used for proofs

but I'm not sure to understand the meaning about it being "true"

because if the premise would be false and the conclusion true, then overall A -> B would still be considered to be true so what would be the point of => in this case

[pale epoch]

there probably is no difference between $\rightarrow$ and $\Rightarrow$ in the stuff you are dealing with

[vital dew]

Lochverstärker

[minor lake]

But

if I would have to prove that A => B

and let's say A would be false and B would be true

so overall it would be true?

[pale epoch]

yes

[minor lake]

I'm sorry but I don't see how it would make sense

[pale epoch]

if A is false, the statement is true

it's just how implication is defined

A => B with A false is always true

[minor lake]

Could you give me an example of a proof

where A is false

because I don't understand how if A is false overall it can be evaluated as true

[pale epoch]

well

the statement "if 3 is even, then the Riemann Hypothesis is true" is a true statement

[minor lake]

How does that prove anything

[pale epoch]

it doesn't

[minor lake]

so it's impossible to have a proof where A is false

?

[pale epoch]

if you want to prove that A => B is true

assuming A false is the trivial case

so in a proof you would assume A true and try to conclude with B true

[minor lake]

Oh ok that's what I wanted to know

[faint narwhal]

I think one way to think about it is that if a politician says "If I am elected, I will increase taxes", but they don't get elected, then if taxes don't go up, they didn't lie

[minor lake]

Oh I see

so I assume they get elected

alright thanks guys

[pale epoch]

good example

[pallid belfry]

How could I do stars and bars for this?

I have never actually learned this method so im going off youtube

[burnt surge]

hey guys! I've got a question.... I'm trying to solve an exercise where I have f(x,y,z), where I have to find "1" ONLY if there are two "1" in the row. And I can only use negation and implication.... I'm thinking about it for straight hours but I can't find an algorithm for that, can't think of anything... only like doing it mechanically, writing down all the guesses...

[mystic moss]

Hm what’s the exercise exactly?

[languid cradle]

I got b & c

but absolutely stumped on a

[vapid light]

whats the funny looking x thing

is there a definition?

[languid cradle]

chromatic number

The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same colo

r

[languid cradle]

<@&286206848099549185>

[faint narwhal]

is n the number of vertices here?

[opaque pilot]

If yes, then just take n different colors haha

[mystic moss]

@languid cradle how did you do the last two?

[languid cradle]

11 b) I showed that for the size of the largest independent set in G: q

X(G)q>=n

and then since q is the size of the largest complete sub graph of Gcomp

X(Gcomp)>=q

thus X(G)X(Gcomp)>=n

[mystic moss]

Hm how’d you show the first inequality?

[languid cradle]

11c) follows algebraically from b)

from another problem

basically if a is the average size of an independent set

then X(G)a=n

and since q>=a

[mystic moss]

Wait what’s the reason behind that

[languid cradle]

X(G) = k for a k-coloring

meaning k independent sets in G

so n/k = a

[mystic moss]

Ah interesting. So with the average independent set, you’re only considering those produced by the best coloring

[languid cradle]

yeah that’s X(G)

any ideas on a)?

[faint narwhal]

Is n the number of vertices?

[mystic moss]

Yeah

[faint narwhal]

Hm, I think you can induct on n

[mystic moss]

Yeah that’d work—it’s interesting to think about how you’d prove it without induction though

But also like, what does adding/multiplying chromatic numbers mean

[languid cradle]

yeah I’m supposed to induct on n

I think maybe I should use a coloring in G that isn’t used in G complement

[mystic moss]

Hm?

Think about what happens to each of the chromatic numbers after you add a vertex to G

[faint narwhal]

yeah, and think about the degree of the vertex in both G and G complement

[stray reef]

part 2 is 21 stars and 3 bars

[languid cradle]

ok while I’m working on that one

how about number 14?

not supposed to use any theorems really so

I was thinking about maybe taking the longest path in the graph?

[mystic moss]

Hm sure but we don’t know if that’s closed?

What are the characteristics of Hamiltonian circuits that you went through?

[languid cradle]

they visit every vertex once

and are circuits

[mystic moss]

Lol no I meant other things that you derived about graphs with HCs

Ie the theorems they don’t want you to state

[languid cradle]

oh

Like they don’t contain smaller circuits

and any vertex of degree 2 in the circuit’s connected edges must be in the circuit

is that what u mean

I think those are necessary not sufficient conditions tho

[mystic moss]

Kinda? Wdym by they don’t contain smaller circuits, like just by virtue of not repeating any vertices other than the start and end?

[languid cradle]

A Hamilton circuit cannot contain a smaller circuit within it

[mystic moss]

Okay fair

[languid cradle]

as in if there’s a circuit a-b-c-d-e-a

b-c-d-b is not a circuit

[mystic moss]

I just think that by the wording of the problem, there’s probably a theorem in the chapter that basically proves it, so you might like to go over that

[languid cradle]

yeah not sure

I’m looking at theorems now

[mystic moss]

Is this a textbook? Which one?

[languid cradle]

Applied Combinatorics

Alan Tucker

So anyway, I’m trying to find an intuitive way to show this

nvm I think I thought of something

[mystic moss]

If there’s a way to do this without casework lmk

[languid cradle]

I used cases

[mystic moss]

There are exactly two, right?

[languid cradle]

I was trying 3

I know it’s connected

since 3>= 6-1/2

so there’s a path

did 1 case where v1 and v6 are adjacent

1 case where they’re adjacent to the same vertices

And I’m trying a 3rd, but it might be better to do 2 more

[mystic moss]

Hm. I think some of them are going to be isomorphic

[languid cradle]

yeah I just said WLOG

kinda ran out of time to finish that one but I tried it anyway lol

[gritty crescent]

Can a valid argument be made invalid by adding extra premises? An argument is said to be valid if the assumption that all premises are true necessitates that the conclusion is true.
If one adds the negation of the conclusion to the premise, doesn't it lead to an invalid argument?

(The book I'm using claims that adding extra statements to the premise can't make a valid argument invalid)

[unreal stump]

what if you add the premise "the conclusion is false"

[gritty crescent]

That's the same as adding negation of the conclusion.

But adding this extra premise makes the premises inconsistent. I don't remember if consistency is necessary for validity.

[burnt surge]

@mystic moss heeyy, so this is from word to word translated in translator and I tried to correct it better Just use the logical conjunctions (negation) ¬ and (implication) ⇒ to write the logical function of the three variables f (x, y, z), which acquires a true value just when exactly two of its three variables have a true value.

[pastel pike]

anyone has ever studied about modular irregularity strength ??

[faint narwhal]

ok you might want to use #combinatorial-structures actually

[stray reef]

@burnt surge so you want to write f(x,y,z) = {1 when xyz = 110, 101 or 011; 0 otherwise} using only negation and implication?

[burnt surge]

@stray reef if I understand it correctly, then yes

[stray reef]

you can write $A \land B$ as $\neg(A \to \neg B)$ and $A \lor B$ as $\neg A \to B$ i guess

[vital dew]

Ann

[pallid belfry]

I tried number 2. Would the answer be 16,151,520?

[mint bane]

finding the useful denial of an implication is just writing the negation right

so the useful denial of something like P->Q would just be P->not Q ...?

[mint bane]

or rather, how about the useful denial of an iff

[weary tiger]

Are all 3 of these statements false?

[faint narwhal]

no

[weary tiger]

Which one is wrong?

@faint narwhal

[faint narwhal]

can you explain your thought process?

[weary tiger]

Well part d i assumed was false because 235 is not equal to {235}, for part e 235 is in the set so that makes the statement false, and for part f {235} is in {235} so that would also be false

@faint narwhal

[faint narwhal]

uh, there's a difference between $\subsetneq$ and $\not \subseteq$

[vital dew]

Zopherus

[weary tiger]

Oh I didn't know that, whats the difference between them?

[faint narwhal]

The first means that its a strict subset

It's a subset, but not the whole thing

[weary tiger]

But if the last 2 questions were the second subset then would the last 2 statements be false?

[faint narwhal]

uh yes

[weary tiger]

okay thanks

[olive swan]

is this correct for part b ?

sorry about my handwriting

[leaden moon]

Anyone got idea what this question is asking?

The language of all words of length at least 2 that contain the first two letters (in lower case; in a latinized transliteration or transcription if necessary) of your preferred name (please state these letters separately and clearly) in the correct order anywhere within the word over the alphabet Σ = {a, b, c, . . . , x, y, z}. (Note: This is one of the violations of our guidelines. x, y and y refer to the actual characters here)

[stray reef]

there is no question

[autumn pebble]

?tutor

I’m trying to understand the connections between the set X and (a,b) (c,d)

They exists in the set X x X which I wrote out to get ordered pairs

What is (a,b) (c,d) in terms of the set X and the product of XxX would it just be a any two ordered pairs in consecutive order like (1,1) and (1,2)

Or (1,2)(1,4)

[coral raven]

,rotate

[coral raven]

yeah, it's just two ordered pairs

[autumn pebble]

Sweet

So if we took the ordered pairs (1,1)(1,2) as (a,b)(c,d) respectively it would still result in (1,1) (1,2) again since ac=bd

Do I have that right?

@coral raven

[coral raven]

1*1 =/= 1*2 so they're not related

[autumn pebble]

Okay, that makes sense, so is this would be the set of ordered pairs of relation R but they are not equal

Just trying to make sure I answer the question

I’d also write out a directed graph of these unequal pairs?

[coral raven]

uhhhhh you've lost me

(1, 1) R (1, 1)

(1, 2) R (2, 1)

(1, 1) not R (2, 1), unless i've drastically misunderstood something

[autumn pebble]

Okay in my ordered pair set I have{ (1,1)(1,2) } I was using those ordered pairs for the relation

I guess I have to choose two ordered pairs that will be equal

Instead of consecutive ordered pairs?

None of these ordered pairs equal each other

[tranquil flint]

How would we go about finding the number of digits of a number that is very large like 52^1917

[coral raven]

the number of digits of x is more or less log10(x), there's a starter

[tranquil flint]

Oh wow that just flew over my head thank you

i forgot how easy it was

i was overcomplicating it

[lilac delta]

how can I solve 43?

R x R is what i dont understand

can someone clarify?

[coral raven]

the set of ordered pairs of real numbers

they're just saying y and x are both real i think

[lilac delta]

ok

how can i determine whether this is true?

[coral raven]

try things

if it's false you can find counterexamples

[tawdry edge]

Can someone explain a composition relation mapped unto itself ?

Like

let A = {1,2,3,4,5} and r be on A xry iff y = x +1

where we have a relationship rr

r^2 = rr

[autumn pebble]

@coral raven do you voice chat?

[coral raven]

no

[humble bridge]

Where can I practice spectral graph theory problems?

My teacher only assigns a few questions of hw and I feel like its not enough

[stiff rock]

,iam Advanced

[vital dew]

Gave you the Advanced selfrole.

[lethal prawn]

Hey, I have a question.

It says: Is the compound proposition - (P v Q v R) a contradiction (keep in mind - is negation)?

How exactly would I read this?

Do I make a truth table for P, Q, and R, then do a disjunction column for each set, and then do a negation for it after?

[vernal oriole]

I'm trying to get some discrete math help. I have 14 candy bars and I want to give some candy bards to 8 friends but don't have to give out all 14 candy bars.

If each friend can receive any number of candy bars, including zero, how many different ways do you have to distribute the candy bars? I know this is regading inclusion-exclusion principal but I'm a fair bit confused. Is it 8^14

or would it be 9 ^14

all candies don't nessecarily have to be distributed

[mint bane]

Let $a$, $b$, and $c$, be integers. Prove that for all integers $m$ and $n$ , if $a|b$ and$a|c$, then $a|(bm+cn)$

[vital dew]

nitezba

[mint bane]

any pointers on how to start this

my first idea is to rewrite a|b as b = ak, same with c, and plug that into a|(bm+cn) but idk where that'd get me

[unreal stump]

That's the solution

b=ap,c=aq
bm+cn=(pm+nq)a

[shut fjord]

Is it possible to get from A n B to A ?

Using set rules?

[unreal stump]

no

[shut fjord]

Why not?

Or anyway to do

A n empty set

A U Universe from A n B

[unreal stump]

you can't find a set given only a subset of it

[shut fjord]

Dang

Then Idk how to solve my problem

Is this an appropriate chat to discuss Turing machines? Or is that a different channel

[unreal stump]

I guess so

[mint bane]

ok i feel dumb for this one but
for all x, x^2 >= 0
im guessing contradiction?

[robust mango]

or just consider cases, x = 0, x > 0, x < 0

[mint bane]

see i thought about that too

x = 0 easy enough

but then idk about x > 0

bc if it's an irrational real it cant be expressed as a ratio of two integers

[robust mango]

x > 0, we can multiply both sides by x and get x^2 > 0 by one of the properties of the real numbers(for any real numbers x,y, if x >0, y > 0, then xy > 0)

(x > 0 and x > 0 gives x^2 > 0)

[mint bane]

ok i understand that but would that same logic hold for negative

[robust mango]

yes

if x <0

then -x > 0

[mint bane]

thanks @robust mango

[robust mango]

np

[mint bane]

wait @robust mango

im not sure if that'd work cuz it's tryna prove >=

or does the property still hold for x >= 0

[robust mango]

x = 0 gives us x^2 = 0

[mint bane]

i feel like it should but i dont wanna assume

[robust mango]

other cases give us x^2 > 0

so for all x, we have x^2 >= 0

[mint bane]

ok gotcha

[robust mango]

or u can do it into 2 cases

x >=0, x < 0

same thing

[mint bane]

ok bet thanks again

[robust mango]

np

btw contradiction also works. suppose x^2 < 0, which is x * x < 0, which by the property of real numbers implies that x < 0 and x > 0 at the same time

which is not possible

[hardy yoke]

So I have to define some stuff, which i'm not sure are right:

Variable range: {john, bob, jenifer},
Predicate constants: {john, bob, jenifer}, (is this right or constants are Male(x), Female(x))
Defining terms: {john, bob, jenifer}...
Defining atomic functions: Male(john) = true, Male(bob) = true? (or atomic functions are just Male(x)...?
Write some axioms for this language: What do I write here... Male(x) -> NOT(Female(x))? (does this work as an axiom?)

[opal cedar]

say you have this NFA, how can you do it without an epsilon transition?

[last timber]

you can convert it to dfa

[mystic moss]

Can’t you also just merge states 1 and 2?

[opal cedar]

is a dfa an nfa?

instead of an epislon-nfa

[short steeple]

sorry to interrupt, just a little question here: on this problem, i'm not sure what they mean by n1

Let $G$ be a connected graph that has $n_i$ vertices of degree $i$. Recall that $\Delta(G)$ is the largest degree of a vertex in $G$. Prove that if $$n_1=2+\sum_{i=3}^{\Delta(G)}(i-2)n_i,$$ then $G$ is a tree.

[vital dew]

Snodlop

[short steeple]

wouldn't n1 always be degree 1 no matter what? or am i counting the number of degree 1 vertices

[faint narwhal]

its the number of degree 1 vertices

[short steeple]

ok

ok i think i get it

thanks

[short steeple]

update: yeah i got it thanks for the help

[blissful zenith]

can someone please help me figure out how to show this

idk how to deal with the sum here

otherwise id just expand it

[blissful zenith]

<@&286206848099549185>

[balmy hornet]

Considering a binary relation, "is a subset of", ⊆, defined on all sets. Which of the following properties does this relation have? Relfexive, Symmertric, Transitive, Irreflexive, Asymmetric, Cyclic

I was thinking that it would be reflexive, symmetric and transitive but i do not know for sure if that sounds correct espcially with transitive

Can someone explain to me what cyclic is as well?

[weary tiger]

Just follow by definition

For example with transitive: is it true that if A is a subset of B and B is a subset of C that then also A is a subset of C

i hear the first time about cyclic relation do you have a definition

[balmy hornet]

My prof never mention cyclic so i was confused on exactly what it was. Although here is the google definition "A binary relation R is cyclic, iff its transitive closure is not antisymmetric. Note that R may be reflexive and still acyclic, i.e., loops in R are not taken into account."

[weary tiger]

ok do you know what a transitive closure is

[balmy hornet]

Is this the same transitive from before? or is it a more specfic definition? if it is then no

[weary tiger]

no thats something much different than the transitive property

also more complicated

[shadow pond]

Hello

when I want to find | A ∩ B |

i do | A | + | B | - | A U B| ?

[errant bear]

yea

[pure harbor]

how does one easily justify given that a countable union of countable set is countable

that a countable union of finite sets is at most countable

our def is like finite ≠ countable

bijection N

A side note is i think i can prove a finite union of countable set is countable, so to do that I let {A_1,...,A_n} be the finite countable sets, and define A_i = N for i > n, and since A_1 is a subset of A_1 U ...U A_n, which is a subset of A_1UA_2U...... which is countable, it means the finite union of countable sets is countable.

that should work right

[vital dew]

slimvesus

[pure harbor]

but wouldnt the U_{n=1}N =N

hm

i think i have to prove this for like a part

to prove that algebraic numbers are countable

So I showed like given any n right

P = {set of poly with deg n} is countable

and then with that i need to show

$\bigcup_{p \in P}{x:p(x) = 0}$ countable

[vital dew]

Anticipation

[pure harbor]

its fine thanks for the help 😂

So this is the original Q:

how does one easily justify given that a countable union of countable set is countable
that a countable union of finite sets is at most countable

(def of countable is A countable if theres f: N -> A bijection)

[last timber]

all finite sets are countable, all finite and countable sets are at most countable

[pure harbor]

yea but i dont see how that leads to result?

so the result is a countable union of at most countable sets are at most countable

[rare patrol]

How can you solve it with element argument? I am a bit struggling with it

[last timber]

@rare patrol

[vital dew]

Commander Vimes

[last timber]

then show that converse holds

[rare patrol]

Do you think that I have it correctly this way?

[last timber]

first of all in case 2 you should have a in X and a not in Y

second, you showed that LHS is subset of RHS, to complete the proof you should show the converse

[rare patrol]

got it thanks!

I am also super stuck at this question at showing the part of n = k + 1
I wonder if you have any clues of that? Thank you

this is what I have done so far

I just have no idea how to prove ak*ak+3 = (ak+1)(ak+2)+(-1)^(k+1)

[last timber]

@rare patrol so look

[vital dew]

Commander Vimes

$a_{n-1}a_{n+2}=a_na_{n+1}+(-1)^n$

Commander Vimes

Commander Vimes

Commander Vimes

[rare patrol]

I thought I had to prove n = k + 1 tho?

[stray reef]

he's showing you how to rewrite the statement in a more easily provable form

at least if i understand correctly

the assumption is you won't get sent to gulag for such tricks

[rare patrol]

so like don't I like to prove a(k+1)-1*a(k+1)+2 = (ak+1)(ak+2)+(-1)^(k+1)

[last timber]

i mean

if you expand this

[vital dew]

Commander Vimes

you get $a_{n-1}a_n+(-1)^{n+1} = a_{n+1}(a_n-a_{n-1})$

Commander Vimes

and using that $(-1)^{n+1}=(-1)^{n-1}$ and inductive argument you now can arrive to something nice

[rare patrol]

I don't get where do you get (-1)^n+1 and the right hand side?

[last timber]

expanding lhs here, moving some terms to left and some to right

[rare patrol]

and where has (an-1)(an+1) gone to after expanding it?

[last timber]

if you want

[vital dew]

Commander Vimes

[rare patrol]

but how come has (-1)^n changed to (-1)^n+1?

[last timber]

because i move (-1)^n to left

[rare patrol]

Oh so like -(-1)^n then (-1)(-1)^n so (-1)^n+1

[last timber]

also it would be nice if you would parenthesise stuff properly

[rare patrol]

Got this part now thanks I will try if I can get n = k+1

[final topaz]

alternative: use the roots of the characteristic equation

φⁿ = φaₙ + aₙ₋₁

(-φ)⁻ⁿ = -aₙ/φ + aₙ₋₁

multiply these two identities together

then simplify a bit using the definition of the sequence

[opaque prawn]

how do you proof this?

[last timber]

suppose for all x B implies A(x)

then show that this implies that B implies for all x A(x)

then converse

[opaque prawn]

what's the correct way to do step 2 to 3?

[paper parrot]

I don't think that follows

[opaque prawn]

yeh, Idk what to do starting from step 2

[last timber]

that is true

oh no

if b then q means not b or q

now use that b is independent of x

[paper parrot]

Switching from universal to existential in step 2-3 is
~Ex ~(~B or A(x))
then
~Ex (B -> A(x))

Is that right?

no its not