discrete-math

[keen cave]

for (p -> q) -> (not p -> not q) is p OR not q equivalant?

i found it by using conditional as a

disjunction, and demorgans theorem

then I use communitive rule

and then absorption

[torpid mango]

ive never seen anyone use the index of upper bound before

what does this mean ?

[vernal vigil]

Dankie. You carrying my exam on Thursday

[torpid mango]

im used to seeing r index i here

[cerulean radish]

What do you mean exactly?

[keen cave]

does anyone know this?

[torpid mango]

let me show you a picture of what i mean

note im 2 months into cs

so very new

here is what im used to seeing

but my professor

is replacing index for number sequence with upper bound

in a task

[cerulean radish]

Yes

[torpid mango]

https://cdn.discordapp.com/attachments/496785905474994186/1163384388634030161/image.png?ex=653f6124&is=652cec24&hm=094c0e11e64c678d9634558b7d42932abce33fc3b5c21c51e33603eb65a5e9eb&

so my question is, what does this mean ? i guess

[cerulean radish]

Ah you mean why is it r_k and not r_i?

[torpid mango]

other way around

oh yes

now aftter edit

yes

that is my question

[keen cave]

yoo thank you, so it is valid to do (p ^ ¬q) v (p v ¬q) which is (((p ^ ¬q) v p) v ¬q)

then by absorption

[cerulean radish]

It's either a typo and they meant to type r_i or they may have meant b(r_k + r_k + ... + r_k)

Depends on the context

[keen cave]

p v ¬q

just making sure I don't have to distribute

[cerulean radish]

Was this written to signify a rule/law?

[torpid mango]

yes

it was

[cerulean radish]

Yeah I got the same thing

[keen cave]

thanks for confirming!

[torpid mango]

but what does it mean if its the upper bound as index ?

[cerulean radish]

Yeah I would guess they meant to write r_i but it is not invalid notation to have the running index absent

[cerulean radish]

I'll give you an example

Actually no I'll write what it means if they meant r_k

[vital dew]

A Lonely Bean

A Lonely Bean

[cerulean radish]

This is the difference

It's not incorrect to write r_k even if k is the upper bound of your running index

But I still think they meant to write r_i there

[torpid mango]

is it possible to elaborate further on why its (k-i+1) amount of terms ?

[cerulean radish]

In general between natural numbers a and b (including a and b themselves) there are a + b - 1 natural numbers

[torpid mango]

ah yes

ah

so its like a loop in programming

where index can represent the amount of times we do something

but for the actual thing we add its each time r_k

[cerulean radish]

If you are studying cs it could be helpful to think of the sigma notation as using a for loop, yes

[torpid mango]

yep its cs program

[cerulean radish]

Yes, so it will just be adding the same number each iteration

Whatever constant r_k is

[torpid mango]

but we still do it the regular amount of times ?

right

[cerulean radish]

Yes

[torpid mango]

like start at i

and go to upper bound

inclusive on both

[cerulean radish]

Yes

[torpid mango]

its just that we add the specific element each time

in this case r_k

[cerulean radish]

And if it was r_i, it would be different in each iteration, i.e., r_1 in 1st iteration (i = 1), r_2 in 2nd iteration (i = 2), and so on until the last iteration (i = k) where it adds r_k

[torpid mango]

yep

cause i changes

but im used to seeing that notation

but now i understand the other one

after your explanation

does that mean i got this one right to ?

@cerulean radish

[cerulean radish]

Yes, but it should be (n - k + 1) times

[torpid mango]

ah, but arent they the same ?

[cerulean radish]

i is the running index that starts at k and stops at n, it doesn't have a stationary value

n and k are the endpoints, there are n - k + 1 natural numbers between them

[torpid mango]

ah, if they swapped positions in the equality i would be correct right ?

[cerulean radish]

Yes

[torpid mango]

if it was k=i

ok

cool

[quick tusk]

what makes this uniquely decodable?

[torpid mango]

can anyone see where i am wrong?

my calc is the white one

answer = black one

ignore the = to 3

last one, was supposed to type something but forgot to remove the last 3 xD

nvm i found my error i think

[haughty garden]

the intuitive explanation for this code, at least, is that the 0 acts as a marker for the start of a potential symbol to be decoded and if you see too many 1's, then you know that you would have hit a c5 symbol.

For example, if I take the string 001001111110111, then the 0's tell us that the first codeword is c1, followed by c2, followed by c1; we then hit the remaining string which is 01111110111. I can either break this up into 01|111110111, 011|11110111, or 0111|1110111. However, only one of these fit the bill, specifically, 011|1111|0111. So we can uniquely decode the string.

A more rigorous treatment would show that if you consider the reversals of each of the codewords, then you obtain a prefix code and in fact, this is enough to show that C is UD in the first place! All prefix codes are UD (the converse is not necessarily true, this code is an example), so I will leave it to you to convince yourself that if the reversal of C is UD, so is C

[vernal vigil]

How do I find the properties of matrices? Is there anywhere I can read online on how to get an understanding to questions like these?

[quick tusk]

oh yeah i see the reverse being a UD.

this is my observation, but if there are prefixes in the forward and reverse could that mean it is not uniquely decodable

[quick osprey]

https://cdn.discordapp.com/attachments/1154037671103053835/1163369027234701342/image.png?ex=653f52d6&is=652cddd6&hm=cdd974b0e8e02cc91015d89364dcc4891c95b86f3c776f43c7d9484593cb2b60&

Why is A wrong

[vestal bronze]

A is strings that don't contain 0000

[quick osprey]

Isn’t that what we are looking for?

Oh or is it like the bitstring can’t contain 4 0’s

[vestal bronze]

just because it's true for the opposite, doesn't mean it counts as true

[quick osprey]

Wdym

[vital remnant]

hey im trying to find the derivatives of x

in the book they ask me to find y2

that means i differentitate with respect to x again one more time

but as they asked me to find y4, there are no mentioning if they are actually differentiating at this point or is it just to make it look more clean?

can some1 help me with this?

[inland apex]

Anyone know how to prove q->q is tautology using propostional equibalence and the laws of logic?

[dreamy river]

the definition of the conditional is "not P or Q", so q->q means "not Q or Q" which is a tautology

[deft falcon]

can equivalence classes only be for equivalence relations? and can equivalence classes only be for relations on a set S. As in can they be on an equivalence relation between sets A and B and can they be on nonequivalence relations?

[plucky wedge]

yeah as slime said you'd use the fact that ~p V q is logically equivalent to p -> q and since are only variable is q it would be ~q V q which is called the complement law and will always be true.

[inland apex]

thank you!

[sweet gorge]

Z x Z the same as any int squared

[cerulean radish]

In standard notation Z x Z means ordered pairs of integers

I.e., {(a, b): a, b in Z}

[blazing rose]

I’ve got i) A element B; ii) A element B and A subset of B?; iii) A subset of B; iv) A element B and A subset of B

Is that correct?

[cerulean radish]

Yes, everything's good

[blazing rose]

Thanks

:D

I can’t think of a set for which the conditions in c) hold..

Used A = {0, {0}} and A = {{/emptyset}} for a) and b)

The only set I can think of which satisfies that it is subset of its power set would be A = {\emptyset}

[rigid oriole]

Theres a simple example. Very simple.

I say this as a hint to reconsider what you might be overlooking

[blazing rose]

Is it the empty set?

[rigid oriole]

why

[blazing rose]

Empty set is subset of its power set since it is subset of every set

Then it has no elements x I suppose?

So the second condition holds as well?

[blazing rose]

But here I’ve also stated A subset B for ii) which would be in contradiction with that..

[rigid oriole]

Thats right

the empty set is a subset of every set, and any statement universally quantified over it is vacuously true

[rigid oriole]

How.

[blazing rose]

I Said A is subset of B

[rigid oriole]

A is a subset of B as well as an element of B

well it is.

[blazing rose]

When A = empty set

Oh yea

Right

Definition of subset is every element in A is also element in B

And A has no elements right?

[rigid oriole]

no elements

[blazing rose]

Well the power set of A would then only be {empty set}?

Therefore both conditions hold

[rigid oriole]

idk what you're asking

for

p({}) = {{}} yes

[blazing rose]

Okay

Thanks a lot

[drifting brook]

reason why this is wrong?

[weary tiger]

Top one $\notin (A \cup C)$
Bottom left one $\notin (A \cup B)$

[vital dew]

<:F_button:1095679234497843251>

[final cliff]

The top check mark?

[weary tiger]

yeah

[final cliff]

It's in A so it's in AUC

[weary tiger]

My brain

Yeah, you're right. i was thinking intersection for some reason

[final cliff]

I think your concern about bottom left has a similar issue

[weary tiger]

yeah

[final cliff]

It is missing the check mark in A tho, because if x is in A, then x is in AUC and likewise if x is in A, then x is in AUB.

Also the check mark in B and C.

The check mark that's just in B should be excluded because it won't be in AUC

A similar idea should exclude the checkmark that is just in C.

(These were both left out in the original answer btw, just confirming that they were left out correctly.)

[turbid dagger]

Can anyone confirm if my solution to problem 10 is correct?

I feel like maybe I'm misunderstanding the question

problems 8 and 9 lead up to this so I thought including them may be helpful

[twilit sundial]

im not convinced by their justification for the insertion construction here

why can we suddenly conclude the existence of those indices?

[weary tiger]

here is a really interesting question

any ideas?

[coral parcel]

I think I have a solution in 18 moves, but the moves don't alternate between white and black, and I'm not sure there's any solution where they do.

[rugged atlas]

I believe this counts as discrete math

tho it's a discrete programming class

i'm stuck converting this into an CNF

as of rn i have ((!t + !q) (1) ) + ((q!r(1)(p+s)(p+t)

[weary tiger]

is this data management

[rugged atlas]

No just Boolean algebra

[keen cave]

I am so annoyed rn, on the verge of punching my computer screen, just cause of discreete math structures. I've never encountered math this difficult and nonsensical

predicate logic DOES NOT MAKE SENSE ESPECIALLY WITH CONDITIONALS

holy crap they want me to convert real life statements into predicates

with conditionals in them

layered multiple times

fucking bring me back to calculus 3 2 or even physics holy shit

[signal sphinx]

Any graph theorists in the chat?

[sullen vessel]

My textbook states that every non Hamiltonian graph is semi Hamiltonian, and every strongly connected graph is Hamiltonian. The proof is similar to the one in yours but differs slightly, I could share that if you like

[coral parcel]

"Translate natural language to formal logic" exercises can be pretty inane, especially in the sense that the "natural language" sentences are not natural at all -- they're not something anyone would say in any real situation. The only feasible way to approach them is often to think not "I understand this sentence, now how do I write it symbolically?" but "the exercise author must have a formal statement in mind when he wrote this bizarre combination of English words, what can it have been?"

[errant bear]

it might be faster to write a script to check lol

[plucky wedge]

|e^x| : R -> R, is this a function?

[brave rock]

Why not?

[plucky wedge]

because not all values in it’s domain are mapped to the codomain

for it to be a function must it be R+ -> R

or actually no

we can input all members

I think I see now

[brave rock]

:)

[plucky wedge]

I was trying to think of why some of the functions I used in math or functions like ln(x) are functions when the graph of the left side for x doesn’t exist but now I see we still enter in those values it just maps to the right side of the graph, and when I was thinking of why 1/x is a function usually theres a domain restriction of 0 can not be in the domain right. But if 0 were to be in the domain, R->R including 0, then it wouldn’t be a function(1/x) right?

[brave rock]

the map sending x to 1/x is not a function R → R but it is a function R\{0} → R.

[plucky wedge]

Oh ok that makes sense

Ok yeah I have a better understanding of functions and sets now thanks

[molten junco]

anyone got ideas for b?

[plucky wedge]

For members in the codomain y, that does not have an x mapped to it, it means there is no ordered pair where (x,y) exists and that’s why in the defintion of a function we say that (x,y) must be a memeber of F? For codomain is it basically a generalization of the type of elements in our range? So in A x B, B would be considered the range, I think I was interchanging A -> B as the same as A x B and I was wondering how could a function not be onto if we are taking the cartesian product domain and codomain which would give a ordered pair for all values of x and y. Am I getting things right

[ember basin]

Can some one give me resource to solve number 1?

[fringe turret]

This implies statement is bugging me when p is false, them its a tautology.

the condition is not met, the truth of the conclusion cannot be determined; the conditional statement is therefore considered to be vacuously true, or true by default.

Is this because, we do not have any kind of information when p is false. Like another statement r which states "otherwise" of p?

[rigid oriole]

P => Q is equivalent to not P or Q

i dont think much beyond this

hmmm

===========
Another way of thinking about it is "if we start with a false premise, we can prove anything"

Thats essentially what this says

And you can make sense of it with some examples

like assume 0 = 1, then go on to prove whatever you like

[fringe turret]

Why? Just because a book says or it makes sense to you? If latter, again why?

[fringe turret]

Well that is helpful 😄

[plucky wedge]

A common example is the politician example. Say you have a politician, and he says that if it rains tommorow he will give everyone a paycheck.
p = it rains tommorow
q = everyone got a paycheck

now let says we have the case p = true and q = true. It rains and he gives everyone a paycheck. Well then the entire statement is true since he followed thorugh with his promise.

lets says that it doesn’t rain tommorow and he doesn’t give the paycheck to everyone(p = false, q = false). Well we say this statement is not false because he did not break his promise, it’s a true statement it’s just that it’s vacousouly true, it’s truth does not have much meaning.

Let says it doesn’t rain tomorrow and he still gives everyone a paycheck (p = false, q = true). He still has not broken his promise, which was if it rains tommorow he will give everyone a paycheck. Thought it didn’t rain and he gave everyone a paycheck the statement is still not false, it’s vacuously true.

Lastly in the case where it rains tommorow and he does not give everyone a paychecl. This is where the statement is false (p = true, q = false) he did not follow through with what he stated. It rained however no paycheck was given. We can see that out of the conditional this the only clear thing that was stateed and broken. If you think about it all the other cases are technically not false because his promise was never broken.

[fringe turret]

So, I am confusing it with how we convey such information using natural language, where otherwise is also implied implicitly. Like, If it rains tomorrow, everyone will get a paycheck. Otherwise, not. So it is like paycheck depends on raining tomorrow.

[fringe turret]

Also, that is not what correct reasoning means. So correct reasoning requires premise to be true, and arguments that leads use to true conclusion. :/

[wet laurel]

Let R, S, T be sets. Suppose that R ⊆ S, and S ⊆ T . Prove that
R ⊆ T .
how do i prove this?

[brave rock]

Use the definition of ⊆, and show that it holds.

If you don't recall the definition of ⊆, now's the time to look back at your notes and find it.

[ember obsidian]

gof represents "apply f then apply g", so in order to have (gof)(0)=4, think like this: 0 -> ? -> 4

[plucky wedge]

is a sequence domain the subset of natural numbers or integers

the book says integers but online I'm getting natural numbers

I remember my teacher saying natural numbers also

I mean it could be both right but is natural numbers used more

[runic magnet]

Bro i got discrete midterm on friday any good youtubers to watch for additional reviewing

[granite perch]

Whats a Weibull Variate?

[fringe turret]

Are then venn diagrams of A ⊂ B same as A ⊆ B?

If A ⊂ B and A ⊂ C, then elements of ∀x(x ∈ A ^ x ∈ B ∩ C), basically I meant this ∀x(x ∈ A → (x ∈ B ∧ x ∈ C)). Is this correct assertion?

[fringe turret]

Did I get it right?

[fringe turret]

Also about this

[rigid oriole]

No it does not, otherwise proofs by contradiction wouldnt work

By definition, if you assume something in the premise, it is then true for the rest of the argument

[fringe turret]

Yes, that I know. What do you mean by false premises? Like just a negation

For eg p -> it is raining then !p it is not raining.

[fringe turret]

Plz explain this to me.

What does that mean. Is i an element or set?

It is a set, i was confused with notion that small letters are elements of set. But for a set of sets, the type of element itself set

Setception 😅

[valid monolith]

What makes this: (( P ∧ Q ) ∨ R ) well formed, but not P ∨ Q ∧ R

[rigid oriole]

parens

no defaults are defined when they are missing

[valid monolith]

what is defaults

[rigid oriole]

think about how in ordinary arithmetic

a + b + c

means (a+b)+c

You can think of another human "compiling" this expression

And by definition we mean that for convenience

it saves us writing brackets

Similarly a + b * c := a + (b * c)

It's like a syntactic sugar

[rigid oriole]

No such thing is defined here.

You can consider that list of 4 points to be everything you program into your "compiler". Nothing more nothing less

It does not understand P \lor Q \land R

[rigid oriole]

ig its not just those 4 points, its a bit more (you have to tell it what an atomic statement is)

===
(I may be interpreting this wrong, but im fairly certian this is what's going on)

[grand totem]

If you're not convinced then it's a good idea to try and actually prove that the first is a wff (this is rather straightforward), but the other isn't (this is quite annoying but certainly worth doing at least once)

[rigid oriole]

Ah right, I missed those 4 properties implicitly encode this

[rigid oriole]

the 3rd property encodes parentheses to work exactly as we need them to work without explicitly defining an order of operations or similar

not even P or Q is well-formed in this definition

[true token]

is this a better chanel for me @rigid oriole , im just in logic sets functions relations for now ,

[fringe turret]

Read it two ways

(( P ∧ Q ) ∨ R ) - P and Q, or R (with pause, and some emphasis on comma, will tell that either P and Q or R
P ∨ Q ∧ R - P and Q or R (without pause it will look absurd, like what did you say)

This is how I registered it in my mind. Please correct me if I am wrong.

[fleet slate]

idk what im doing at all but what the hell is a weibull variate??

[normal sentinel]

about Regular Expressions, is Ruby the default way of writing it?

[placid carbon]

Does anyone know good resources to study for exam 2 discrete math. (Proofs, sets, functions, sequences)

[cerulean gate]

guys can anyone help me with discrete math homewokr?

i have a simple discrete math question

I basically don't understand why the answer would be No to this graph questino

[placid carbon]

https://youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz&si=A1tWzjx8RkalP8IO

[faint sphinx]

Assume that $g_k = 2^k + 1$ for all integers $k \leq n$. You want to show that $g_{n+1} = 2^{n+1} + 1$

[vital dew]

Hatsune Ryxmiku

[faint sphinx]

(this is strong induction, where you assume more than just the previous step) In particular, you need that this holds for k = n and k = n - 1

(I think this should be enough)

[true tulip]

Recurrence relations problem, need help visualizing this

I've determined that E(3) = 4, E(2) = 2, E(1) = 1. The same is true for O(3), O(2), O(1)...

I'm going to evaluate E(4) and O(4) now to hopefully get me somewhee

so both would be equal to 8

Does that mean E(n) = 2 * E(n-1)??? and same with O(n)? And the base case for both could be E(1) = 1, O(1) = 1. I don't understand why the recurrence relation needs to be written in terms of both...

The power set of X has a number of elements equal to 2^n, where n is the number of elements of X. |P(X)| / 2 = |E| = |O|

Well I feel confident kind of about
E(n) = 2 * E(n-1)
O(n) = 2 * O(n-1)
So that's the answer I'm going to submit, I will find out in class tomorrow if I was missing something

[frank bay]

which one should I get for self study of Discrete ? Rosen or Susanna book?

[chilly hemlock]

biggs' book

[frank bay]

why is it better?

[chilly hemlock]

simple

and good explainations

lots of fun problems too

[grave sail]

What can you say about the sets A and B if we know that A Δ B = A?
Prove your answer. -------does it make sense to say B is empty, so B is a subset of A ?

[cerulean radish]

Yeah B is empty

Don't answer with only "B is a subset of A" though

[lean rover]

How to write this using predicate logic: "No animal is both dog and cat"
I did ∀x( (D(x) ∧ ¬C(x)) v (¬D(x) ∧ C(x))
is it wrong?

[cerulean radish]

I think it should be for all x, not (D(x) and C(x))

Or is that the same

Yeah it looks like you are saying that every animal is either a dog or a cat

I suppose we are aware of the fact that there are animals besides dogs and cats

[cerulean radish]

So yeah should be this

[lean rover]

yeah they did it in a different way

Where they had to specify the universe animals

[meager prawn]

imagine coming into mathcord and the first thing you read today is this

[lean rover]

but otherwise they did ¬∃x(Dog(x) ∧ Cat(x))

or ∀x(¬(Dog(x) ∧ Cat(x)))

[cerulean radish]

Ah yeah so basically what I suggested

[lean rover]

mine is a little longer but would that still suffice

[cerulean radish]

Well, again, your statement is false for animals other than dogs and cats, but the original statement is true for any animal

[lean rover]

but in that case this should be false too tho

[lean rover]

this

[cerulean radish]

Why?

[lean rover]

because it is also only talking about dogs and cats

and not all animals

[cerulean radish]

If we pick x to be some animal besides dogs and cats, then Dog(x) = F and Cat(x) = F

F ∧ F gives F and negation of F is T

[cerulean radish]

Ah

So we are talking about only dogs and cats?

As our universal set

[lean rover]

no idea

"No animal is both dog and cat"

this is all I have to go on with

[cerulean radish]

I would assume the universal set to be all literal animals if it's not specified

[lean rover]

so I could assume my universe is all nimals or cats & dogs

[lean rover]

yes

[lean rover]

but what you mean here then?

why is my statement false for all animals?

[cerulean radish]

If we take x to be a lion for example, D(x) and C(x) are false, so this gives F v F

Which is F

[cerulean radish]

Not "false for all animal" but "not (true for all animals)"

[lean rover]

yes get it

thanks for the help btw

"All numbers between 6 and 8 are odd"

I did ∀x(6 < x < 8 -> x = 2n+1)

but in the answers they did: ∀x(x<8 ∧ x>6 -> Odd(x))

I understand what they did but is my solution wrong?

is it not allowed to do 6 < x < 8 or x = 2n + 1?

The predicate odd is a fomula for x = 2n +1 technically tho? But is it wrong to do it this way?

[cerulean radish]

No, what you wrote is correct

Because contrapositive is equivalent to the original implication

Uh wait

Ah I see

6 < x < 8 is the same as "6 < x and x < 8"

They just chose to write it like that

[cerulean radish]

No, because that's not what the statement says

[lean rover]

What do you mean?

As far as I understand, my answer says exactly the same thing as the correct answer, just different way of describing it.

But the question is whether or not my way of describing it is illegal in predicate logic?

[cerulean radish]

This is your answer, right?

[lean rover]

yes

[cerulean radish]

Would have to mention that n is some integer, I see no other issues

[coral parcel]

It has n as a free variable, which is definitely not what you want.

[lean rover]

but how do I do that?

[lean rover]

why?

[cerulean radish]

Just add "exists n in Z" before "x = 2n + 1"

[coral parcel]

Use an appropriate quantifier to bind it at the right place in your formula.

[lean rover]

but isn't it allowed to have free variables?

[coral parcel]

You don't want "All numbers between 6 and 8 are odd" to mean something that is true for some values of n and false for other values of n.

From a straightforward understanding of the English sentence, it ought to be true.
But what you wrote is false when n=22.

Because ∀x(6 < x < 8 -> x = 2·22+1) is false. (Namely, 6 < x < 8 -> x = 2·22+1 is false when x=7, and then it doesn't matter that 6 < x < 8 -> x = 2·22+1 is true for some other values of x).

[lean rover]

yes so I need to use existential then right?

[coral parcel]

Yes.

[lean rover]

one more

"There are infinite numbers"``` I answered: ∃x ∀y (x>y v x<y)

But they answered

∀y∃x (x>y)

I feel like my solution is wrong but I wanna double check

My soultion states that there is either a larger or smaller number which is not true because both will always be correct but I can't use "and" in this case

[brave rock]

I don't agree with the 'correct' answer here, but in any case, yes your answer is wrong.

You are saying that there is some number such that all other numbers are above or below it

But if there are just two numbers, rather than infinitely many, this fits.

[lean rover]

so I am right?

[brave rock]

So clearly your sentence does not describe that there are infinitely many numbers.

[brave rock]

I said right here that your answer is wrong, idk how to be clearer than that

[lean rover]

yes

[brave rock]

The reason that I don't agree with the correct answer is that it says a lot more than simply there are infinite numbers.

[lean rover]

so if we ignore whether the answer is correct or not

[brave rock]

If we wanted to translate that directly into first-order logic, we would struggle. But at least they could have stated they wanted you to find a sentence that implies what they wanted, rather than merely translating it.

[lean rover]

What is the difference between: ∃x∀y (x>y v x<y) and ∀y∃x(x>y v x<y)

[brave rock]

OK let me give you a different example that hopefully will make things intuitively clear

What is the difference between the sentences:

∃ tool ∀ problems the tool solves the problem

and

∀ problems ∃ tool the tool solves the problem

?

The first says that there is a tool that solves EVERY problem. One tool that solves them all.

The second says that for every problem, there's a tool that solves it. Possibly many tools, but at least one per problem.

Is it clear how these are different now?

[lean rover]

given this would this be correct answer to the original question: ∀y∃x(x>y v x<y)?

[brave rock]

Still no, because there could still just be two numbers.

[lean rover]

But it is saying for all numers there is a number that is either greater or smaller then the given number

[brave rock]

Yup

[lean rover]

how is that not defining infinity?

[brave rock]

and 1 is less than 2, and 2 is greater than 1

so the set {1, 2} satisfies this.

Typo.

[lean rover]

but I can't do this tho

∀y∃x(x>y ∧ x<y)

so this means I am only allowed to use one of then

[brave rock]

Well that's just false, there is no such pair of numbers

[lean rover]

but it doesn't matter whether it is > or < right?

[brave rock]

In what world is x < y and also x > y?

[lean rover]

that is what I mean

[brave rock]

∧ means and.

[lean rover]

yeah but given that I conluded

[lean rover]

this

[brave rock]

No.

[lean rover]

wdym

[brave rock]

The statement you have written is just false.

[brave rock]

What you are saying is just not true. I don't know why you think you can only use one of the facts on either side of a conjunction.

[lean rover]

I can only do either ∀y∃x(x>y) or ∀y∃x(x<y)

[brave rock]

No

[lean rover]

or otherwise I'm beyond saving

[brave rock]

Are you confusing ∀y∃x(x>y) v ∀y∃x(x<y) with ∀y∃x(x>y v x<y)? These are very different.

[lean rover]

I didn't mean "v" by or

[brave rock]

v is or.

[lean rover]

yeah

but I am saying as an option

[brave rock]

I still don't know what you mean by this.

[lean rover]

I am saying

I can either answer: ∀y∃x(y<x)

or I can answer: ∀y∃x(y>x)

but that is still a question

are both true?

[brave rock]

Yes, both are true facts about integers

[lean rover]

R(x) = "there is something red" and B(x) = "there is something in a box"

This is supposed to be the solution BUT

It looks illegal, how can you use Existence elemination and still end up with existence. I mean I know the predicates are different and all but I was just wondering if this is the right way of formatting this? This is from my TAs notes so wanna double check.

[royal canyon]

Are they saying both sets are individually functionally complete or the sets combined together form a functionally complete set? Also just to be clear that I've got the definition correct, Functionally complete set is a set of connectives that can used to represent any compound proposition?

[cerulean radish]

They mean the former

Yeah

[coral parcel]

You can.

[royal canyon]

Ok

[coral parcel]

\neg for negation.

[lean rover]

Prove

t1 = t2 ⊢ (t + t1) = (t + t2)

This how they did

[coral parcel]

That's one of the equality axioms, as applied to the + function.

[lean rover]

2      t+t1 = t+t1     =i (t+t1 = t+u [t1\u]
3      t+t1 = t+t2     e 1,2 t+t1 = t+u [t2\u]

I don't really understand what is going on here?

[grand totem]

The first line should read t1 = t2. The second line is by reflexivity. Now if I had to guess, the =-elimination rule probably reads something like "if t1 = t2 and phi[t1/x] then phi[t2/x]" (for t1, t2 terms, x a variable and phi a formula, possibly with x occurring free).
They then consider the formula phi := t + t1 = t + x (with x a free variable). This way, phi[t1/x] = t + t1 = t + t1 and phi[t2/x] = t + t1 = t + t2.
Now this instance of =-elimination essentially reads "if t1 = t2 and t + t1 = t + t1 then t + t1 = t + t2".
But you already know that t1 = t2 and t + t1 = t + t1, so this instance of =-elimination allows you to conclude with t + t1 = t + t2.

[lean rover]

yes my bad it is supposed ot be t1=t2

[grand totem]

A small subtlety: You should choose a "fresh" variable x that guarantees that phi[t1/x] = t + t1 = t + t1 and phi[t2/x] = t + t1 = t + t2 will actually hold. Without being a bit careful here that might not be the case.
For any term u, the substitution phi[u/x] will be (t + t1 = t + x)[u/x] which (after applying the recursive definition of substitution a couple of times) will yield t[u/x] + t1[u/x] = t[u/x] + x[u/x]. Now the last substitution is always carried out, so we finally arrive at t[u/x] + t1[u/x] = t[u/x] + u.
But in our case we also want that no other substitution there is carried out (since we want to end up with t + t1 = t + u after all!).
So a good idea is to simply choose for x a variable that doesn't occur in either t or t1. And since we have an infinite supply of variables at our disposal, that is no problem.

[lean rover]

sorry I don't really get it can we break it down step by step

I am just starting with predicate logic so I am finding it a bit overwhelming

[grand totem]

I wouldn't worry about that unless your course or book actually pays attention to such details.

I just included the remark for completeness reasons. Judging by the proof you posted above, your course/book just implicitly assumes variables are chosen carefully enough that things work out as we expect them to.

[lean rover]

yes but I kind of struggling a little bit with understanding exatcly what they did?

[grand totem]

As in, you have trouble following this proof?

[lean rover]

yes

[grand totem]

I'm not sure how to explain any differently from how I did before. Applying =-elimination is probably the trickiest part since you have to "reverse engineer" some formula that, after substituting your terms, give you something that you can work with

Coming up with that formula yourself might take some practice, so for a beginning student I'd suggest to trust the book that the formula they chose works and instead focus on understanding each individual step in the proof

[lean rover]

I am a bit slow rn to be honest, so I am gonna need to take a little break

[grand totem]

Which there aren't many of since the proof is rather short, but take some time to comprehend how they applied =-elimination (carry out the substitutions by hand and see what this specific instance of the rule says and why the premise of the rule is fulfilled and how the conclusion of the rule ends up matching the goal statement you're supposed to prove)

[lean rover]

yes the thing is I just don't understand it when it is used in action

the rule is pretty straigt forward but I can't even prove a simple stuff

[grand totem]

It takes practice, especially the formal proofs that involve =, since equational reasoning in everyday mathematics is usually done without thinking about the details too much. Meanwhile your proof system only has two rules from which you may derive any other property of = you might expect it to have.
For example, it is a very good exercise to show that equality is symmetric, i.e. that t = u |- u = t. Try doing that after you've convinced yourself that you understand the proof you posted earlier.

[lean rover]

Thanks, I will try that out:)

There is not many exercises in my book, at least not easy ones. Do you have a recommendations? The internet requires me to know what to search, so I have not really found any good materials

[vital dew]

Ratatatat

[grand totem]

What book are you currently using? Most mathematical logic books don't pay much attention to carrying out proofs in some formal proof system (they usually care more about reasoning about the system). So it would be good to know what kind of book you're currently working with.

[royal canyon]

Can someone help me better understand the associative laws? Would this be equivalent or not? $$(A \land B) \lor C \equiv A \land (B \lor C)$$

[vital dew]

Ratatatat

[faint sphinx]

Associativity is for when you have the same operation. Since you switch the operation here, this would not fall under an associative law. Hence these are not equivalent

[royal canyon]

Ok thanks

[ember obsidian]

now when we have DIFFERENT operators we might consider whether they can "interact" by a distribution law and here the answer is yes. $\lor$ distributes over $\land$, ie
[(A\land B)\lor C\iff (A\lor C)\land(B\lor C)]
and vice versa

[vital dew]

Roketsune Miku

[gilded sun]

I cannot seem to understand how to deduce Aramis's identity other then process of elimination.

[lean rover]

Show that ∀x(0+x=x) ⊭ 1+0=1

Can anyone help me with this?

[keen cave]

true thanks for the tip

[slim dawn]

can we prove this by making x = mary and y = john

[fringe turret]

I think so yes. Because there exist x (Mary) who is married and is parent of y (John).

[coral parcel]

Consider an interpretation where + means the function that always returns its right input.

[lean rover]

Yes the answer is x+y=y and I get that the result of the left side (0+x = x) is given by the right side of the addition sign whilst the right side (1+0=1) result given by the left side.

[lean rover]

but this is addition why does it matter?

considering I am even right

[coral parcel]

The point is that formal logic doesn't know "this is addition". That's something you guess from the shape of the symbol, but formal logic (and the |= notation) is about things that hold no matter which functions we interpret each symbol in the formulas to be.

[brave rock]

Yes

[cerulean radish]

I really hope that's not the entire question the book gives

[lean rover]

The first is my solution and the second my TA:s. The question is is my solution correct?

I always struggle after making an assumption, how to get out of it (assumption box). Is there any rule or can we get out whenever we want, in this case I thought line 5 should be inside the inner box but still didn't really understand exactly why so I kept it out since it felt easier that way. Any comment will be appreciated.

Also in the second solution on the 6th line, why isn't it 3-5 instead of 3-4?

[uncut shoal]

This is my first time using induction. I'm trying to prove the predicate at the top. I think I'm doing something wrong because I don't know where to go from here.

[ocean wyvern]

hi bros

[royal canyon]

struggling to find videos on conjunctive/disjunctive normal forms. is it not really taught much in US/UK discrete math courses?

[haughty garden]

Hint: (k + 1)! + 3 = (k + 1)*k! + 3 = k*k! + k! + 3, and use the inductive hypothesis on k! + 3

[uncut shoal]

Thanks, I got to that point, but I haven't figured out how to use the 3q to make a proof that it's divisible by 3.

I did some algebra from k!k + k1 + 3 = k!k + 3q to k! + 3 = 3q, but I don't think that's enough proof that that's divisible by 3 since all I did was get back to the beginning.

[haughty garden]

k >= 3 so k! has a factor of 3

[uncut shoal]

Is that something I need to prove to prove the original predicate?

[gentle kite]

im finna die in this class

logic and induction so easy

but combinatorial proofs

😢

[midnight nova]

Guys can I get some help on this? Not exactly sure when to place ands and buts for 6(c) here

[plucky wedge]

I believe it would be Bill is tall but not tall and not dark right

[coral raven]

can someone explain to me why k >= n implies G is hamiltonian?

ping me if you reply pls

actually nvm i got it

it's actually explained later.

god

[midnight nova]

yea that was my initial thought aswell, thanks for confirming that

[coral raven]

mathematics is universal timeless beauty locked behind ten hundred thousand logical mazes of suffering and mental strain

[gentle kite]

for combinatorial proofs, is it the same to say the cardality of A is n instead of A has n elements

like |A| = n
instead of the set A has n elements

[flat echo]

Guys, I need to find a particular solution to the recurrence: a(n+1) = a(n) + (n+1)^2

Any ideas? It should work with a(n) = A + Bn + Cn^2, but then when substracting a(n+1)-a(n) the principal coefficients cancel out and I can't get a solution

[brave rock]

You need at least an n^3 term

that's all I'll say, you should be able to work it out from there.

[flat echo]

But I'm taking this proposed solution from a guide. Is it wrong then?

It said I should try with a polynomial of the same degree of F(n), which is in this case F(n) = (n+1)^2

[tight hound]

Let b(n) = a(n+1) - a(n)
Then ∑b(r) for r=0 to n might give you something useful

[flat echo]

I know

I'm using this recurrence to find a formula for that sum

So I can't use the formula for that sum, since it's what I'm trying to prove (the sum of the first n squares)

[tight hound]

Ah, sorry

[flat echo]

Np, thanks for trying to help

[brave rock]

And you tried it, and you concluded it didn't work, didn't you?

[flat echo]

Yes, and I just tried with a cubic and it worked

But I don't get it then, I've seen it in many websites that the particular solution should be of the same degree of f(n). Are they all wrong then?

[brave rock]

I think you've just found the answer to that question yourself

[flat echo]

Actually I haven´t. I forgot to notice that since 1 is a root of the characteristic polynomial, I should multiply by n

[gentle kite]

pls 😢

[torn tendon]

Yes , the cardinality of a finite set is the number of elements in it

[gentle kite]

okay thank you, also what would be the difference between a combinatorial proof and a permutation one?

[abstract flower]

So I’m doing a project for this class involving this summation here, where I have to prove it converges. Is there a possible way I can write the summation as a formula?

[distant grove]

I have a question about a problem involving RSA cryptography. I need help understanding the solution provided, specifically from the point
[d \cdot e \equiv \varphi(1) \Leftrightarrow d \cdot 5 + 216 \cdot k = 1.]

The problem: Crack the crypto (m = 12) with the public keys (e, n = 5, 247).

Solution: The provided solution takes steps to factor the public key (n = 247) and calculate the private key (\varphi). However, I'm having difficulty comprehending how they use the coefficients -43 and 173 in the reverse Euclidean algorithm. I'd like to understand why these values are used and what 'k' signifies in this context.

I follow the solution and have no problems until the point
[d \cdot e \equiv \varphi(1) \Leftrightarrow d \cdot 5 + 216 \cdot k = 1.]
After that, it becomes challenging for me to understand how they use the Euclidean algorithm to determine the private key (d) and decrypt the message. I'm having difficulty seeing why they use the coefficients -43 and 173 in the Euclidean algorithm. Can someone help me understand this step by step? Why are -43 and 173 used in the Euclidean algorithm, and what does it mean for decryption?

[vital dew]

dgh

[fringe turret]

Hey @plucky wedge @rigid oriole , could you confirm this?

[spare trench]

Hellooo, I need some help with my discrete math homework. I'm stuck at these 2 questions, it's about network flow 🥹

Could anyone give me a hand, I've been stuck at these for the past few days 🥲

[blissful shell]

for all x,there is exist y, such that x²+y²=9. this is true right?

[coral parcel]

Are x and y supposed to be real numbers?

[blissful shell]

i guess?

[coral parcel]

Which y would work when x is 4?

[blissful shell]

oh i forgot imaginary number exist, okay thx

there is exist x, for all y, such that if x<y then x²<y²

how to do this? when there is the implication form?

[cerulean radish]

That implication is always true when x >= 0, so pick any nonnegative value for x

[real tiger]

Can I ask about sets in this channel?
I'll take the liberty to ask anyway...
If an ordered pair can be represented as a set as (a, b). This notation was was originally of the form of {{a},{a, b}}.
{a} is a set
{a, b} is a set,
{{a}, {a, b}} is therefore also a set who elements are sets.
Elements within a set can be in any order which means it is that true that
{{a}, {a, b}} = {{a, b}, {a}}
(a, b) = (b, a)
So this would mean that an ordered pair could has not been established using this notation?
Could someone please help me understand how this is the accepted notation for an ordered set. Or am I overthinking this?

[hushed wagon]

A sphere is colored in two colors. Prove that there exist on this sphere three points
of the same color, which are vertices of a regular triangle.

[hushed wagon]

can anyone solve this?

The positive integers are colored black and white. The sum of two differently colored
numbers is black, and their product is white. What is the product of two white
numbers? Find all such colorings.

[hushed wagon]

and this

Given an m × n rectangle, what minimum number of cells (1 × 1 squares) must be
colored, such that there is no place on the remaining cells for an L-tromino?

[hushed wagon]

also this

[coral parcel]

No. (a,b) is {{a},{a,b}} whereas (b,a) is {{b},{b,a}}. These are not the same set even if you try to switch around the order. The element with two elements is the same (namely, {a,b} = {b,a}) but the one that is a singleton is {a} in one case and {b} in the other, and those are not the same thing.

[blazing rose]

Whats the difference between totally ordered and well ordered?

[brave rock]

R is totally ordered, but not well ordered.

However every well ordered set is totally ordered

Other examples of totally ordered sets that are not well ordered are Z and Q.

[coral parcel]

(not well ordered by the usual ordering, that is. It's easy to define different orderings of Z and Q that are well, much less easy for R).

[blazing rose]

ah understood ty

[weary tiger]

how do i solve this

[coral parcel]

This might mostly be about knowing exactly what "cycle" means. Several of the wrong answer options correspond to particular misunderstandings of the concept.

(The second line of text sure is confusingly worded. It just seem to mean "if you have two cycles that look the same except one visits the vertices in the opposite order from the other, those count as two cycles").

[lean rover]

Does φ hold for the φ below? Please justify your answer.

(b) |= q → (p ∨ (q → p))) ∨ ¬(p → q)) → p.
I have answered but the difference is that, I don't really understand what part of this should we look to check whether the validty is nor trash.

[coral parcel]

What is "(b)"?

If it's not really part of the question but just a number for it, my initial assumption would be that you're supposed to fill in a truth table. Especially since it is asking about |= rather than |-.

There seems to be more ) in the formula than there are (, though, so you'll have to resolve that first. Perhaps that will let you get away with answering, "No, because that is not a wff at all".

[blazing rose]

Im working on this task right now and i almost finished my proof, the issue is this task is marked as not that hard but my proof is a bit long for that imo, as I included the proof that "for any equivalence classes [a] and [b] if their intersection isnt empty [a] = [b] and a is related to b in that equivalence relation" to prove the antisymmetry property of Rho. Am I on the wrong path?

If needed I could direct message my full proof if anyone wants to take a look

[real tiger]

That's great thank you. You've helped me see where I went wrong.
👍

[slow nova]

Dont understand this answer to the question at all

[real tiger]

Sorry, I'm still struggling with how things go from an unordered set to an ordered pair.
I understand that {{a}, {a, b}} is a set with 2 elements {a} and {a, b}.
I understand that if 'a' is not equal to 'b' then the 2 sets are distinct with 'a' in both sets and 'b' not.
So keeping within the definition of what a set is, how does this create order? Is it because of a 'transformation' into a pair and saying that because 'a' is in both and 'b' is not this allows 'a' to be the first element of the ordered pair and b is the second element? Is so this would then lead me to ask for clarity that an ordered pair can only be made from a set as described above?

[coral parcel]

I suspect you may be reading too much into "ordered pair".
There's nothing about {{a}, {a,b}} that inherently says that a has to come before b -- that's an interpretation we simply choose as a convention.

There are plenty of other definitions we could have chosen to use to implement the intuitive concept of "ordered pair" instead of {{a},{a,b}} and which would work equally well. They would lead different sets representing the idea of (5,8), but as long as we use the same definition each time we write (something, something) that doesn't matter.
The important requirement is just that the definition we choose must allow us to prove that (a,b) and (c,d) mean different sets unless a=c and b=d.

(If you're interested you can find a list of several possible alternatives to {{a},{a,b}} at https://en.wikipedia.org/wiki/Ordered_pair#Defining_the_ordered_pair_using_set_theory)

[real tiger]

Yes, looks like I might be trying to read too much into it. Thank you for the link, I'll do some more reading with a more general mindset.

[lean rover]

Check whether this is true or not

(q → ¬r) ∧ (∼q → r) ∧ p ⊨ (p ∨ q) ∧ (r → p)

I have done a truth table and I thought I understood it but what what is that I am gonna check? Whether the right side is true when left side is true? Or do I have to check each connection like (q → ¬r), (∼q → r) and p and that the right side is true when these 3 are true in order for it to be a logical consequence? Or do I have to check each alphabet? Kinda confused since I only have one premise.

[tepid trout]

I've got a problem I need some help with. I need a logic circuit that takes 10 inputs, preferably infinitely expandable to more than that, and outputs only 1 bit
the truth table is simple, but when I attempted to solve it I reached several blocks so I came here for some help or general discussion because it is quite interesting
the circuit takes 10 inputs and outputs 1 if and only if only a single input from the 10 is true. the rest are false

I attempted to make a simple xor ladder but that outputs true if all inputs are true which is not what I want

[grand totem]

The more appropriate lemma about equivalence classes here would be that [a] = [b] iff a ~ b (writing ~ for the equivalence relation). The right-to-left implication in particular should help you out in the antisymmetry proof.
Other than that, you'll somehow need to use the fact that ≤ is antisymmetric and a final hint might be that the least element of a subset of A is always also an element of that subset, i.e. least(A') ∈ A'. In particular, least([a]) ∈ [a]. But what does that tell you?

[vestal bronze]

make an adder ladder

[tepid trout]

?

[vestal bronze]

like XOR and AND

so the sum propagates, and at any point if the sum is two

it gets reported

it's super heavy but there's not much else to do

[tepid trout]

yeah that's a problem
my plan is to build that in minecraft with redstone 😂

I guess I'll try and look for a redstone specific solution

[vestal bronze]

are you still trying to tell if the sum is 1?

yeah my bad

you said so

[tepid trout]

I'm trying to make an encoder that takes one of 10 inputs being a base10 digit and encode it into binary
that circuit works, but I want a second circuit that lets it only work if only one input is on

or else the output of the first circuit gets jumbled

it's not a necessity but it's just cleaner to make sure the system doesn't break

[stark spire]

hi! does anyone recommend a discrete maths free course? im covering a lot of things in my classes, but when i search it up on youtube, i barely find anything as complex as what im taught :p

[worthy gyro]

@stark spire You’re really not going to find good YouTube videos on it tbh or discrete math free course. It’s just not the same as what you’re taught in the class and in the text book as online. I can recommend blackpen on YouTube he covers some discrete math topics that r similar to my course at least

[glossy needle]

Hey, would anyone be free to help me out with part of a question im trying to do? I just dont really know what to do for part e, I got sick and missed the last class where my prof explained it.

Ive done all of the other parts of the question, could just use some help on figuring out what im supposed to do for part e

[deft sage]

I need help on this please, I tried D(1)=2, D(2)=7, and when n is odd, D(n)=2D(n-1), when even, D(n)=7D(n-2) but I’m getting nowhere really

[coral parcel]

This seemed wildly difficult, until I figured out that ||the 12 vertices of an icosahedron form not just the 20 equilateral triangles that are vertices of each face, but also 20 larger equilateral triangles that make up a great icosahedron. Taking all those 40 triangles into account it is fairly simple to derive a contradiction if each of them must have at least one vertex of each color.||

[halcyon raptor]

Hello can someone explain the counting rule of addition and multiplication to me?

[coral parcel]

This is a cute problem. I don't quite see how to make use of the "product of two whites" hint, but here are some hints that would also lead to a characterization of all the possible colorings:

1. ||If you know two different white numbers, what is the color of their difference?||
2. ||If you know the smallest white number, what does (1) tell you about the other white numbers?||
3. ||Is it possible for there to be a largest white number?||

[zealous fiber]

anyone mind help explaining how to do some of these homework problems?

Theyre probably easy to do but im failin over here

[lime iron]

does anyone know good resources for induction proofs, different and good types of problems with solutions, etc

[faint sphinx]

Definitionally two sets have the same cardinality if there is a bijection between them.
But N and {0, 1, 2} are not in bijection (one is finite and one is infinite), so their cardinalities are not the same.

[hushed wagon]

oh I got it I appreciate your hint, the only thing I need hand with, was the first one, differencing ( or multiplying 2 white number and guess what's the color of the product )
it can be easily proved that the color of integer 1 is black and assuming k is the minimum white integer, therefor k , 2k , 3k , ... , k(k-1) are white and using the first hint we find out that also k ^ 2 is white, thus k ^ 2 + k , k ^ 2 + 2k , ... and so on are white (we can use induction too for a concrete proof) and all the other numbers which are not divisible to k, are black so the coloring is dependant on our smallest white number (k), correct ?

[hushed wagon]

oh I see it thanks a lot

these two were one of the hardest questions from coloring proves from Problem Solving strategies by Engel Arthur

[hushed wagon]

x = 0 -> 1/0 is wrong so the domain shouldn't contain 0

[hushed wagon]

I can't understand why I find the relation for D(n) = 2 * 3 ^ n-1

[hushed wagon]

for example there are two ways a and b (you can assume n-ways for it) for doing something, if they are independant from each other , in an other word, choosing one of them doesn't affect another one, the final answer is a * b (or multiplying all the n integers)
and if they are not independant, so the total ways to do the thing is a + b (addition of n numbers )

[hushed wagon]

You may also read these
https://en.wikipedia.org/wiki/Rule_of_product
https://en.wikipedia.org/wiki/Addition_principle

https://gmatclub.com/forum/learn-when-to-add-and-multiply-in-permutation-combination-262678.html
this one has simply defined them

[hushed wagon]

supposing D(n) = 3 * D(n-1) D(1) = 2
the generation function D would be (x - 1)/(3*x - 1)

[echo shell]

Idt this recurrence you're getting is right

[hushed wagon]

exactly

[echo shell]

Its most probably D(n)=3D(n-1)+2D(n-2)

Oh wait I can just check it

[deft sage]

It is not, because D(6)=733

[deft sage]

Why would it be this

[echo shell]

Yeah

[deft sage]

I don’t think it’s D(n)=3D(n-1)+2D(n-2) either because D(6) isn’t 733

[hushed wagon]

Its D(n) = 3 * D(n-1) it can be easily proved, why are you representing that relation?

D(n) = 2D(n-1) + 2D(n-2) + 2D(n-3) + .... -> D(n) = 3D(n-1) and we also have D(1) = 2

[echo shell]

Yeah I checked and i wasn't getting it

[echo shell]

D(1)=2 D(2)=7 according to you D(2) should be 6

[echo shell]

Can you rotate the tiles?

[deft sage]

Yes I think so

[echo shell]

I'm getting all sorts of numbers close to 733 but not exactly 733

[echo shell]

Do you know the value of D(3)?

[deft sage]

But that’s still not 733

[deft sage]

I tried to count by hand and got 14, idk if it’s right or not

[echo shell]

Wait let's reference the boxes by coordinates

Let's figure out D(3) first

Because it isn't 14

[deft sage]

IsD(2)=7?

[echo shell]

Yes

[deft sage]

Oh wait I counted D(3)=16

[echo shell]

If you have a 2x1 tile at (2,3) then you have D(2) tilings, you could replace the 2x1 tile with 2 1x1s and get another D(2) tilings.
The third case: You could also place a 1x2 tile at (2,3). If you placed a 1x2 on top of that, you'd have D(1) tilings. Either one of the 1x2 tiles can be replaced with 2 1x1 tiles so you have 2D(1) more tilings.
Last case: if you have a 1x2 at (2,3) and then a 1x1 at (1,3) and a 1x2 at (1,2), you'd have one more tiling. You can flip this over again and get another tiling. So imo D(3) is D(2) + D(2) + 3D(1) + 2 =22

I'm referencing the boxes as if they were in an 2xn matrix

[deft sage]

Yeah I understand that reasoning, so D(n)=2D(n-1)+ 3D(n-2)

But why +2

[echo shell]

Thats just an artifact of the case n=3

Anyways

I think I have it

D(n)=3D(n-1)+D(n-2)-D(n-3)

D(1)=2,D(2)=7,D(3)=22

You get D(6)=733 from this

Wait

I might have made a calculation mistake

,w D(n)= 3D(n-1)+D(n-2)-D(n-3), D(1)=2, D(2)=7, D(3)=22

[vital dew]

Results provided by WolframAlpha

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

Requested by bathroomjug

[echo shell]

Yes D(6) is 733

[deft sage]

How did you get to this

[echo shell]

Lemme type it up one sec

[echo shell]

The coordinates will be as usual, suppose you have a 2xn grid. The bottom right tile (the tile at (2,n)) can be filled with 3 tiles. (i)1x1, (ii)2x1, (iii)1x2
Il do case (i) and (iii)at the end because they're wierd
(ii)2x1: now you just need to fill in a 2x(n-1) grid so you have D(n-1) ways to do this
(iii)1x2: the tiles at (1,n) and (1,n-1) can be filled in three ways
(iii).(i) both tiles are 1x1
(iii).(ii)the tile at (1,n) is 1x2
(iii).(iii)the tile at (1,n) is 1x1 and the one at (1,n-1) is 1x2

(iii).(i): D(n-2) ways
(iii).(ii): D(n-2) ways
(iii).(iii): now you need to fill a 2x(n-2) grid with (1,n-2) missing. Let the number of such ways be C(n-2)

Now case (i):
If (1,n) is filled with a 1x1 tile, there are D(n-1) ways of filling in the rest

If (1,n) is filled with a (1x2) tile, this is like case (iii).(iii), so C(n-1) ways of filling this in.

Now you can add these up.

D(n)= D(n-1)+2D(n-2)+C(n-2)+D(n-1)+C(n-1)

Now however we need to eliminate C(n). We can do this easily if we notice that in a 2xn grid with a corner tile missing(say (2,n)) the tile at (1,n) can be filled in two ways
(I)1x1 tile
(II)1x2 tile

(I)there are D(n-1) ways to tile the rest.
(II)C(n-1) ways.
This C(n)=D(n-1)+C(n-1). Now we have a system of recurrences. Eliminate C(n-1) and C(n-2) from this and you'll have D(n)=3D(n-1)+D(n-2)-D(n-3)

Now you need to find D(1),D(2) and D(3) which we just did

Theres for sure a much easier way but this is much more systematic @deft sage

[deft sage]

I don’t understand how we elongate C(n-1) and C(n-2) there

[hushed wagon]

yep I made a mistake

[echo shell]

Elongate?

[deft sage]

Eliminate * lol

[echo shell]

You have a relation between C(n) and C(n-1)

Replace n with n-1

So you'll have C(n-1)=D(n-2)+C(n-2)

Now you have two equations relating C(n-1) and C(n-2)

[hushed wagon]

Sorry is that D(n) = 3*D(n-1) + D(n-2) - D(n-3) ?

[echo shell]

Yes

[deft sage]

Oh I get it now, thank you so much. Combinatorics is so complicated lol

[echo shell]

Its not i did a big and long method

There's almost surely a really genius way of doing this

[deft sage]

Oh

[hushed wagon]

I saw a question on Problem-Solving strategies book it was like : n = k + d(k) + d(d(k))
which function d(n) returns the sum of digits of integer n
it was easy to say if there are some integers n, k that satisfy the relation : n = k + d(k) + d(d(k))
n is divisible to 3 ( n mod 3 = 0 )
but can we say that for every integer n which is divisible to 3, there is at least 1 integer k which satisfies the relation : n = k + d(k) + d(d(k)) ? can we say there is only one integer k which satisfies the relation? what about the question for n = k + d(k) + d(d(k)) + d(d(d(k))) + d(d(d(d(k)))) ?

[echo shell]

Arthur engel?

[hushed wagon]

yes

only the first part that says prove that n is divisible to 3 is in book , I just made up the rest

I tried to use induction but I think it's a bit hard, I wanted to do induction on the integer k to build integer n

[echo shell]

Can you send the exact question because you can just pick values of k and you will get corresponding values of n

Ah my bad I didn't read your question correctly

You want to see if a solution for n=k+d(k)+d(d(k)) exists whenever n is 0 mod 3 right?

[hushed wagon]

yes exactly

[echo shell]

good news is we only need to check values of k till n-3

[hushed wagon]

yes thats correct XD

I programmed that too

[echo shell]

Did you see any pattern in if there was a solution or not?

[hushed wagon]

well I don't know

I checked n = 123456789 and I got k = 123456738 d(k) = 39 d(d(k)) = 12

@coral parcel

[vivid ravine]

Im stressing studying (sets functions groups relations complex numbers ..)
What do i have to take in my daily studying life to not be stressed and get to the points

[vivid ravine]

If anyone faced some hard things in that way and make it pls advise me/ give me resources and way of studying

[torn tendon]

aside taking some rest time for yourself , practice and do exercises , the more you are familiar with a topic the less stressed about it you will be

[willow halo]

does f|X mean that f(x) is defined for all x in X?

[gusty swallow]

Usually $f|_X$ means something like "The function $f$ with the domain restricted to $X$"

[vital dew]

Zybikron

[willow halo]

yes, but does this mean that every x in X must be in the relation?

[gusty swallow]

it would mean the domain is X, so yes every x in X should be used.

[lime iron]

does anyone know good resources for induction proofs, with different and good types of problems with solutions, etc in a intro level discrete math course? my textbook has 0 solutions

[hushed wagon]

Im a computer olympiad student, I practiced induction through Introduction to Algorithms - A Creative Approach by Udi Manber it has such a good questions, also Problem-Solving strategies by Engel Arthur and a book which is written in my mother tongue, I also read Introduction to Graph Theory by Douglas B West

[gusty swallow]

The Book of Proof has a decent section on induction and problem sets. I think it's free online too.

[hushed wagon]

Sir I had a question

[gusty swallow]

??

[hushed wagon]

this one @gusty swallow

[gusty swallow]

definitely not only one integer k.
15 is 5 + 5 + 5 and also 11 + 2 + 2

[lime iron]

thank you

[plucky wedge]

Is this wrong

It said the answer was 4

Why can’t it be 3?

If 3 is the highest degree does it have to be greater than 3?

Same for this one they said the answer was 7 instead of 6

[haughty garden]

x^3 * log(x) > Cx^3 for any fixed C > 0 when x is eventually large enough

this is because log(x) -> inf as x -> inf so you can’t bound log(x) by some constant

[unique dove]

There's this question asking how many distinct 3-trees with height 2 are there and the answer it gives is 721 and I'm not sure how im supposed to figure it out, I looked through the chapter for anything and I could find anything

Question #13

I was able to get it to 3^6-8 8 to account for the first layer but I'm not sure about why 3^6

[hushed wagon]

Yes I tested with my computer too, there could be like many answers as n grows, but the main question is there always a k for any n which is divisible to 3, that satisfies the equation?

[gusty swallow]

seems likely. Seems like you should get something like 3n = 3(n-s) + 3(s-t) + 3t so that everythign in the sum is a multiple of 3 nvm I'm wrong But still seems like it should be possible.

[hushed wagon]

maybe, I was thinking about kind of induction on k or maybe bijection

nvm seems like this question won't be proved easily so forget about it

[full grove]

can i use directed graphs to inspect transivity?

We consider the relation 𝑅={(𝑎,𝑎),(𝑎,𝑏),(𝑎,𝑐),(𝑎,𝑑),(𝑎,𝑒),(𝑏,𝑐),(𝑏,𝑒),(𝑑,𝑎),(𝑒,𝑐)}.
Is R transitive? Justify briefly.

i drew it out to be

i would say its not transitive as, by my interpretation of the definition of transitive, I am unable to find a single path that touches every element once

[magic knoll]

(d,a) and (a,c) in R, but (d,c) is not in R
thus its not transitive

[magic knoll]

thats not true as R={(a,b),(a,c)} is transitive

[full grove]

if i were to interput this in a graph, would it be an undirected graph or directed one

[magic knoll]

directed

[full grove]

if undirected i can see how that';s transive

oh

[magic knoll]

i mean, that was ur interpretation, but it fails in both cases

[full grove]

b to a then a to c

hence b,c

[magic knoll]

but then ur graph also has a path(undirected), thus its transitive? so no

[full grove]

im not fully getting itt

[magic knoll]

where did you find this?

cos its not true

[full grove]

just the way i thought about it

cuz like a,b and b,c hence a,c exists

[magic knoll]

also there is a path, d->a->b->e->c

[full grove]

ahh

right

[magic knoll]

but R is not transitive

[full grove]

i seee i see

now im a bit lost on the definnition

of transivity

[magic knoll]

aRb, bRc=>aRc

[full grove]

how did you manage to point out that d,c is whats needed to complete transivity

[magic knoll]

i didn't say that

theres a lot more to be done for R to be transitive

[full grove]

right

[minor thistle]

I just learned the Chinese remainder theorem, and I understand that for all i, if x = a_i (mod m_i), the solution x must be smaller than the product of all m_i. How do I find a_i such that the solution x is maximized?

[regal gate]

https://en.wikipedia.org/wiki/Moore_graph#Examples

I'm a bit confused by this. Our professor mentioned this theorem a while back but didn't say anything about girth. If you remove the girth 5 condition, what happens?

its confusing, because they also include graphs of other girths, so Im confused

like you can surely have graphs with arbitrarily large diameter and degree that are Moore

[coral parcel]

The maximal x that is smaller than the product of the m_i is that product minus 1. Compute the a_i that corresponds to that ...

[echo shell]

All of this is only if the m_is are coprine

[coral parcel]

Sure, but otherwise the CRT doesn't apply anyway.

[echo shell]

They have to or else we wouldn't be talking about crt

Yeah

I think it's worth telling him why the maximal x is product m_i-1

[coral parcel]

It's a bit confusingly phrased, but my understanding is that the bulleted list is the actual theorem, and "if the girth is 5" is a corollary of that list.

Hmm, but that is not consistent with what the rest of the section says ...

[coral parcel]

That seems to follow pretty directly from his own understanding that x must be less than that product?

[echo shell]

Then he wouldn't be asking the question

[vital dew]

bathroom mug

[echo shell]

Finally

6th times a charm

[echo shell]

Actually, yeah. But if you've learnt this bijection proof of crt the maximal x is obvious. He might have learnt one of the other wierd long proofs of crt

• you get that solution is lesser than product m_i bit as well

[echo shell]

It should be (product m_i )-1 at the end

[coral parcel]

My suggestion was that no matter how he knows x<product, the best he can hope for is clearly x=product-1, and he might simply try to find equations that it solves.

[echo shell]

Ah

It looked like you were trying to say that the solution being lesser than product implies the solution must be product-1

Or i read it that way atleast

[regal gate]

I am inclined to think that what wikipedia says is also wrong. This is a Moore graph of degree 3, diameter 3 and girth 3, I think

and in this way you can construct Moore graphs of very large diameter and degree and low girth

if you want the girth to be big then it is much more difficult, so I believe that the girth is bounded. But they say that all the girth 3 Moore graphs are the complete graphs, but the example I show is not complete (they do not say it explicitly, but they say that the other Moore graphs outside that list have girth 5,6,8 or 12 and the only Moore graphs of girth 3 on the list are the K_n)

[coral parcel]

That looks like diameter 6 to me. (Consider e.g. R to S).

[regal gate]

uh wait yeah I totally trolled the diameter, but it is still not included in the wikipedia list

oh wait

yeah

mb

that is not Moore then

mmh yeah I see now that you really have some restrictions

[coral parcel]

BTW, Google found an Arxiv preprint in Russian whose English abstract promises a proof that the possible degree-57 example doesn't exist.

[regal gate]

🤔

how long ago? can you send the link

[coral parcel]

2020. https://arxiv.org/abs/2010.13443

[regal gate]

bruh I dont have access

now its fine

[coral parcel]

Sorry, pasted the wrong link.

[regal gate]

no worries, thanks

Perhaps instead of five they meant odd

[coral parcel]

The odd cycles can have any odd girth, though.

[regal gate]

because the other Moore graphs they mention below, are "generalized Moore graphs" that include even girth (like C_(2n)), and my profesor didn't use that definition, so it would all make sense

[coral parcel]

Oh, but degree 2.

But complete graphs can have any degree and odd girth (namely 3).

[regal gate]

uhm yeah

yeah ok, idk english

that is correct, but it confused me that they state the girth 5 first, then list all the Moore graphs. I think what is going on is the following: All the Moore graphs are classified and are in that list, Hoffman-Singleton did the case of girth=5 for the final step, which was particularly more difficult somehow

[coral parcel]

Yes, that was what I was trying to say here.

[icy flame]

hello, i was thinking about this problem and got to a solution but i am not quite sure if it is correct. could someone please help me to figure out if there is a mistake in my work?

[opal crescent]

looks fine

[icy flame]

the thing that i am the most not sure of, is the part were i showed that the union of Ai is equal to E because i didn't use the fact that f is surjective and my friend is telling me that we need it there...

or did i implicitly used this information (kind of without knowing)?

[opal crescent]

you already used surjectivity at the beginning anyway

x in f^(-1) (f(x))

you don't need f surjective for that to be true

@icy flame

[unborn vapor]

You don’t need to use that information there. Even if it weren’t surjective, the union of the Ai would still be E, because if you take the preimages of all the possible outputs (plus some things that aren’t outputted, in the case of a non-surjective function) then you’ll get all the possible inputs (and nothing more, as elements of preimages are in the domain by definition)

[icy flame]

alright thanks

[unborn vapor]

The only reason that it wouldn’t be a partition if the function weren’t surjective is that some of the sets would be empty. Everything else still works

[grand totem]

In which case we wouldn't call it a partition though (if we were to be really pedantic). And since partitions on a set and surjections out of that set are essentially the same thing, it is a good sign that they used the surjectivity assumption (to show that every block in the partition is inhabited). Though you indeed don't need that assumption to show that the union is all of E (like your friend claimed).

[weary tiger]

who can help me with a question

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[humble storm]

@snow sleet I'm sorry I haven't gotten back to you. I have a lot of things going on in life. I'm still interested in new concepts nonetheless

[dry tusk]

any idea for <== direction

[austere vector]

nvm got it

[weary tiger]

coding theory?

[jovial marsh]

x (P(x)  Q(x))  (x P(x))  (x Q(x))


Show whether or not this is
possible (as shown above). Provide
proof or support your answer with
clear explanation.

[rigid oriole]

Please explain what the rectangles are, and include the full original question (if anything is missing)

[chrome sand]

hi guys

i have this proof

how he gets from second to third line?

these 3 formulas are given

[rigid oriole]

thats the usual definition of <=>

how else would you define it

"P <=> Q" is defined by "P => Q and Q => P"

is what ive always seen

[chrome sand]

true

[ember obsidian]

its easy to show the 2nd line is equivalent to the given definition of set equality

[regal dune]

I'm a little stuck on this one:

I get the first step is where you write the first congruence as 37t + 12 and then set it equal to the second congruence:

37t + 12 = 14 mod 41

Subtract the 12 and you are left with

37t = 2 mod 41

Then you find the gcd using euclidean which is gcd(37,41)

41 = 37 * 1 + 4
37 = 4 * 9 + 1

I'm stuck on what to do after this, I see my professor used linear combination but how does that work?

[chrome sand]

Hi guys

is there a difference

{(0, 1)}

to

{0, 1}

[coral parcel]

Yes. {(0,1)} has one element, which is the ordered pair (0,1).
{0,1} has two elemets, namely 0 and 1.

[chrome sand]

ah ook

{(0, 1)} ∪ {(1, 1)} = so this would be {(0,1) , (1,1)}

[coral parcel]

Yes.

[chrome sand]

Anotner question

(N0 \ {2n − 1 : n ∈ N}) × (N \ {2n : n ∈ N0})

i should simplify that

(N0 \ {2n − 1 : n ∈ N} = {n $\in N0 | 2n }

how can i write latex here

[hushed wagon]

I had a question
why should we need generation function for some problem like partition of integer n?
and did Ramanujan did the same? did he just find out and write the generation function for partition function ?

[vestal bronze]

we need it for harder problems

not for finding partition number for some small n, they didn't discover it for that purpose

[hushed wagon]

so what is it used for?

[vestal bronze]

i don't know

[red ice]

does a congrunce still have a solution if theres no modular inverse?

[obtuse lance]

yeah you can

2x=4 mod 6 let's say, what are the solutions?

[red ice]

ahhh ok i see

x=2

[obtuse lance]

there's not just one solution

[red ice]

the congruence class of 2 ?

[obtuse lance]

even more than that, there's a separate congruence class

@red ice I'm only interested in working on math in the server not in dms

[chilly dew]

From Bona's combinatorics book: The sum of one hundred given real numbers is 0. Prove that at least 99 of the pairwise sums of these hundred numbers are non-negative.

So far, I've justified to myself that for this sequence $(a_i){i=1}}^{100}$ that $a_j \leq a{j+1}$

[vital dew]

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

[chilly dew]

and considering each case of how many positive/negative integers the sequence has, it seems obvious, put the idea is to give a proof using the pigeonhole principle. Does anyone have any hints?

[blazing rose]

what would be an approach to prove these?

I was thinking of using the definition of uncountability and the fact that B dominates A

hence there exists a bijection from A to some C where C is a subset of B

but i kinda dk how to continue

ah and I prolly would need to use the fact that N is being dominated by A since A is uncountable

[hushed wagon]

well that's correct you can assume B is countable and as A is a subset of B, therefor A is countable too but that's a contraction and it's not possible

[hushed wagon]

you can either use the above one or use the bijection from A to B

[blazing rose]

Is it enough that B dominates A to say A is subset of B?

Because only looking at the definitions from my script I can only assure that A~C and C is subset of B

[blazing rose]

If B dominates A Isn’t there only a bijection from A to B if B were the natural numbers?

Domination only implies injection or am I missing smth

[hushed wagon]

I don't know what you mean by dominate but since you have a one to one from A to C where C is a subset of B, car(B) >= car(C) = car(A)

[blazing rose]

Sorry, What is car?

Haven’t seen that before 🥲

Ah cardinality

[hushed wagon]

cardinal number of a set A, is the size of the set

[blazing rose]

Yea ok thanks

[hushed wagon]

car(A) = n(A) = |A|

[blazing rose]

Yes

[blazing rose]

Ok but by this I don’t necessarily have a bijection from A to B do I?

[hushed wagon]

yes you do

[blazing rose]

Ok i understood the proof by contradiction

ty a lot

now how would I approach b)

Im having a really hard time picturing these sets in my head

with like finite or infinite binary sequences

I mean its basically sequences of 0 and 1

I know {0,1} infinite sequences are uncountable

now what functions in this case do are just mapping a finite binary sequence to an infinite one I suppose?

I would assume I could somehow use Cantors diagonalization argument here but im not sure how as I am not able to rly process how these functions that map finite to infinite binary sequences look like..

[meager prawn]

It's basically pairs of sequences
Remember that |B^A| = |B|^|A|

There's most notably an injection from the set of sequences to that set

[blazing rose]

yes but what about the functions

I mean it could be any functions

I would start by saying I have a countable list f1 f2 and so on

[meager prawn]

who cares about the functions ?

[blazing rose]

that has a bijection to natural numbers

[meager prawn]

even {0} -> {0, 1}^N is uncountable

imagine {0, 1}

[blazing rose]

what would be the first step to prove this?

[meager prawn]

here's the second

[weary tiger]

I'm having trouble understanding the difference between Symmetric and Antisymmetric

[gusty swallow]

for equivalence relations?

[blazing rose]

If a relation (lets define it as rho) is symmetric on a set S then for all elements a,b if a rho b then b rho a

Take the siblings relation for example

If a is a sibling of b then b is also a sibling of a

This would be a symmetric relation

Meanwhile antisymmetric means if a rho b and b rho a then a = b meaning that if two elements are related to each other they have to be the same element

I.e. there are no two distinct elements for which the relation goes both ways

As an example Take the <= relation

If a<=b and b<=a then a must equal b as one can easily see

[full grove]

i have this relations
𝑅={(𝑎,𝑏),(𝑎,𝑐),(𝑎,𝑒),(𝑏,𝑐),(𝑏,𝑒),(𝑐,𝑏),(𝑐,𝑒),(𝑑,𝑏),(𝑑,𝑒),(𝑒,𝑏)}
i wanna see if its transitive

a,b exists in R and b,c exists too but not a,c?

does this mean its not transitive or does the existence of the first 2 elements should imply that a,c does exist and hence it is transitive?

i understand the definition of transitivity by reading it but i have a hard time applying it?

[vestal bronze]

the former, it's instantly not transitive

except (a,c) is the second element

but if you find something missing it's not transitive

@full grove

[full grove]

oh my days

right

[full grove]

and i dont fully understand?

[clear lake]

does anyone know any good youtube channels or such where I can learn from??

[brave rock]

I'd recommend just reading a book

[hushed wagon]

Universities OCW such as MIT or Oxford or Harvard OCW videos, I study CS through them and also Sharif University OCW, but reading book is essential, these videos + books is outstanding !

https://www.youtube.com/playlist?list=PLUl4u3cNGP62qauV_CpT1zKaGG_Vj5igX

https://www.youtube.com/playlist?list=PLUl4u3cNGP61iQEFiWLE21EJCxwmWvvek

https://www.youtube.com/playlist?list=PLUl4u3cNGP60hI9ATjSFgLZpbNJ7myAg6

[clear lake]

Thank youuu

[keen totem]

I showed (1) by using (3) which we proved earlier in the year but I was wondering if there’s a way to show (1) without (3)

Also just to check is (1) a discrete version of hospital rule?

[coral parcel]

Yes.
It's not immediately obvious to me how you use (3) to prove (1), but I think (1) can be proved fairly directly with an epsilon-N argument. The crucial idea is to apply the definition of the right limit with a smaller epsilon than the one you're proving the left limit for -- and even then be prepared to need to increase the N you get from the right limit considerably before you reach one that will work for the left.

It may be a bit easier to keep things straight if you start by arguing that you can assume that the right limit is 0 without loss of generality -- namely if the limit is L != 0, then replace each x_n by x_n - L·y_n.

[keen totem]

I see, figured it would need to be in 2 cases for if L was 0 but couldn’t be sure of it

[keen totem]

As for using (3) this is how I did it

You can check it satisfies all the conditions and then with the sums it cancels out. It’s a telescopic sum

Anyway thx, I’ll try to see if I can solve it with just epsilonN with the help you gave

[steep ether]

Kinda lost on this question, part A im skipping until tomorrow since I think I can go at part b and c, but for part b I think [3]={m ∈ A | m R n} = {m ∈ A | 3 |(m^2 − 3^2)} and so I have to find m in my set such that its mod 3? I'm just somewhat lost and trying to follow my textbooks explanation, i got {-3,0,3} as the equivalence class for [3]R.

[haughty garden]

You essentially want to find all of the values of m in A such that 3 | (m^2 - 9). A is small enough to test every value out

[steep ether]

Part c i havent really attempted fully, wanted to know whether im even on the right track, would it be a valid method to solve it by checking all the equivalence classes for all elements in A, then picking each one without repeating duplicates. Part of the reason why I didn't attempt to solve it fully is because I have no idea whether im getting my equivalence classes correctly

[steep ether]

so that m^2 - 9 = 3k? or that m^2 - 9 mod 3 = 0? sorry im slightly lost on what im checking here

[haughty garden]

yes that’s right

[steep ether]

which one i said 2 😭

[haughty garden]

they’re the same

If m^2 - 9 = 3k for some integer k, then m^2 - 9 = 0 (mod 3)

[steep ether]

so for [3]R, would the equivalnce class be {-3,0,3} since -3^2-9 = 0 (mod 3)

and the solving the same way for the rest of the values of m in A to get the -3,0,3

[haughty garden]

Yes that looks about right

[steep ether]

then the distinct equivalnces would be each unique set that i get by doing that for all values of n and checking the equivalences with m?

[haughty garden]

Well you immediately know that a and -a belong to the same equivalence class

because a^2 - (-a)^2 = a^2 - a^2 = 0

And 3 | 0

[steep ether]

like [2]R gives {-2,0,2} (quick math i could be missing something) and then [-2]R gives the same thing so i would only say -2,0,2 and hten -3,0,3 and -1,0,1?

[steep ether]

yea so i'd just end up with {0} {-1,0,1} {-2,0,2} {-3,0,3}

[haughty garden]

Does 0 belong to the equiv class of 2?

[steep ether]

no ur right it doesnt

brain fart

[haughty garden]

Same as 1 and 0

[steep ether]

it doesnt to 1 or 2, just to 3 since

[haughty garden]

yep

and 0 is not its own equivalence class either

[steep ether]

well 0 belongs to 0

is it not?

[haughty garden]

[0]R = [3]R

[steep ether]

ah so its not unique then?

[haughty garden]

yep

[steep ether]

i didnt really get why it is = to each other, do u mind explaining that? sorry to bother u

[haughty garden]

And this should make sense because you’ve already shown that 0 belongs to the equivalence class of 3

[steep ether]

ah thats why

got it

mind if i bother u with another question @haughty garden ?

This time i think i got the answers right

hopefully

I got yes yes no yes

cause for m <= m will always be true, hence reflex, if m <= n, and n <= z, m <=z is always true, hence transitive. R is not symmetric as 2<3 and 3<2 isn't true, i know theres proper way to write it with for m R n, for symmetric n R m or something i cant recall

and for anti symmetric i cant remember why i got yes

[haughty garden]

Anti symmetric should be no

2R(-2) and (-2)R2 but 2 and -2 are not the same element

[steep ether]

not going to lie, i think this makes sense but its also 2 am so i need to revisit that

A i put 4, 8, 12, B i said since S is full of even numbers which we assume from base, we can deduce s and t are even numbers and therefore s + t is always even using structural iduction but my 2 am brain is telling me that sounds too simple

not posting c since i havent even tried to solve it and doesnt seem fair to ask about it

if i dont follow up i probably fell asleep on my laptop

[grand totem]

To show that every integer in S is even, you show that the set of even integers is also "closed" under the rules I and II.
I.e. you show that 4 is even and that if integers a, b are even, then so is a + b.
The fact that S is defined as the least set that satisfies I and II (this is essentially what III says), lets us conclude that S must be a subset of the set of even integers - or in other words, that every integer in S must be even.

So your job now is to provide two quick proofs, both using whatever definition of "even" your class uses: One showing that 4 is even and another showing that if two integers are even, then so is their sum.

[azure adder]

hi guys
in this example I don't understand in the inductive step they derived x = 2^k

[twin pilot]

So what is happening is if the normal has a positive x component, then I can easily find the equation for the reflection vector angle (θ_r) which lies in quadrant 4. But this same equation does not work if the normal vector is pointing in the negative x-direction because then it assumes the reflection vector is in quadrant 1 now. If it doesn't make sense still, try imagining the normal on the very far left side of the line of a parabola. now imagine how the normal will look as it moves along the parabola and think of how the reflection vector changes its orientation. Bear in mind, the incidence ray is fixed pointing in the negative y-axis direction. Now it doesn't make sense for the reflection vector to be pointing out of the parabola due to the fact that is not how light reflects, therefore it has to be in quadrant 4. But then how can I find ONE single equation for that angle between the positive x-axis and the reflection vector as a function of θ, for when the reflection vector is in quadrant 3 and 4??? I say I need one equation because I do not see how it is possible to use two equations for θ_r and in the future without having to manually input each equation for all surfaces, whenever the normal vector changes its quadrant

[unborn vapor]

Well that’s the definition of being a power of 2: it’s equal to 2 raised to some exponent

[neon jewel]

Does the notation $Z_n$ or $Z^*_p$ automatically imply that the result obtained after performing the operation specified in the group should be taken modulo n?

[vital dew]

Slim Reaper

[full grove]

i have a relation R {(𝑎,𝑎),(𝑎,𝑏),(𝑏,𝑎),(𝑏,𝑐),(𝑐,𝑑),(𝑒,𝑑)}
i am wanting to add links to make it transitive
i beliebve the links are (a,c) and (b,d) but it is apparenrly wrong?

can someone explain why? and how

[little prism]

well then you have for example (a,c) and (c,d). so you need to add even more