discrete-math

[true parcel]

But p shouldn't have any truth value except F if p is a contradiction

Do you need a good explanation?

[cursive dew]

im not sure tbh

so far from what i see, a contradiction has two rules?
Any T/F between two different truth values.
Or
Their both self contradictory(all F's)

[true parcel]

All F is correct (the second one)

But tbh ask yourself why

[cursive dew]

Im not sure how to ask tbh.
If both claim that world is false why would that be a contradiction?

its something they agree on

[true parcel]

Did you learn the concept of truth tables yet?

[cursive dew]

yes

[true parcel]

Ok

So let there be two propositions: A and B

For the proposition A^B, how many columns would u need in a truth table?

Can you tell me the answer?

[cursive dew]

2, 3 counting the result

[true parcel]

Nope

It would require 4 columns

[neon harbor]

I think you mean rows? The columns are A, B and A^B

[true parcel]

A: T, B:T
A:T , B:F
A: F B: T
A: F B:F

[true parcel]

Yeah my question was a bit weird

[true parcel]

@cursive dew can you understand this?

We are writing every possible truth values for A and B

[cursive dew]

kind of , whats the Q in the second row

[true parcel]

Sry typo

[true parcel]

So would you be able to deduce the truth table for A^B

[cursive dew]

T
F
F
F

[true parcel]

Very good

Now try to figure out the truth table for

(ㄱA)^(A^B)

[cursive dew]

F
F
F
F

[true parcel]

Now that is a contradiction

Every possible truth value allocation is a F

Do you understand now?

[cursive dew]

kind of, but still not sure about when two results are false

[true parcel]

Wdym two results

[cursive dew]

it still feels to me as thought when they both claim their false, thats not a contradiction.
Say someone says if you press the some button nothing happens, you dont press the button, nothing happens. Was there a contradiction of some sort?

[true parcel]

I think you are confusing the English meaning of contradiction

[cursive dew]

im gonna go look up some more examples xD

ty for the help 😄

[true parcel]

Ag

U can dm me if u got more to ask

[cursive dew]

I think my my confusion comes from this video: https://www.youtube.com/watch?v=HUBAFF0fqJg&list=PLz0n_SjOttTcjHsuebLrl0fjab5fdToui&index=15

With as he says, two propositions with opposite truth values

[true parcel]

An easy anaology is think of this.
A^(ㄱA) is a contradiction because

F
F
F
F

Event A happens and event ㄱA happens... surely that is a contradiction

[true parcel]

He is implying that A ^ (ㄱA) is a contradiction

I think

[fluid ibex]

¬A is the opposite of A

thus its truth values would also be opposite

[cursive dew]

is it just worded badly then? Is the strict opposite only valid for the negation of one's own self?

[true parcel]

I think he is talking about how we can prove A and ㄱA in a situation of a contradiction, which you don't need to know now

[cursive dew]

I assumed the opposite always had to be there
TF
FT
FT
TF

[fluid ibex]

think of A as the proposition: It is raining.

¬A would then mean It's not raining

if you say ¬A ⋀ A, then that's obviously not true in any case, because it never rain, while also not raining at the same time

Contradictions are simply NEVER true

ever

[sharp rose]

Depends on logic system 🙃

[true parcel]

Not badly necessarily but quite possibly the definition I gave you might be better

[fluid ibex]

well i read that somewhere

[true parcel]

I think we are talking about simple 0 order logic rtnw with law of excluded middle

[cursive dew]

So then
TF
TF
TF
FF
is a contradiction between the two?
I assumed since F,F at the bottom are not opposites, they are not contradictions

[true parcel]

Nonono

There is nothing such as "contradiction between the two"

Just ignore the opposite truth value definition for now

[fluid ibex]

Contradictions are Necessary Falsehoods, and Necessary Falsehoods are sentences that are false in every case, on every evaluation

[true parcel]

A statement is either a contingent, contradiction, or tautology. These properties does not talk about relationship with other statements

[cursive dew]

hmmm ok, then a contradiction if never true...is that just similar to a Nor?
But something weird is going on here.
Is it as if the Nor is applied to the entire truth table at once?
We dont claim indivisual values are contradictions or not right?
TT Not Contradiction
TF Contradiction
FT Contradiction
FF Contradiction
But more so claim its a not contradiction if a single value is true?
Is table wide logic a thing?

actually ig single value comparisons do make sense, but not in the scope of the original question asking if A and B are in whole, a contradiction or not

[true parcel]

We are talking about ALL POSSIBLE truth values when we are talking about contradiction, contingent, tautology

[cursive dew]

reading my own nightmare truth tables makes me all the more inspired to learn that latex bot thingy XD

[true parcel]

So basically a contradiction is a STATEMENT which does not have any possibile truth value allocation other than F

Just remember this

@cursive dew

A^B

Is this a tautology or contradiction or contingent

[cursive dew]

Im not sure, its a proposition from what i can see.

Wait

And denotes a contradiction i think?

I think i get the idea tho

[true parcel]

A^B is an obvious contingent

[cursive dew]

i dont think i heard of that concept yet

[true parcel]

OH

Have you heard of tautology yet?

[cursive dew]

I think? Weird names tbh.
A tautology table -> fancy name for truth table.
A tautology, word by itself -> all values are true, right?

[true parcel]

Correct

So a contradiction is where all tables are F

Tautology is where all truth tables are T

Contingent is when there is a mix of T and F

These are really basic facts you must know when u study logics so I recommend reading thru your text

[cursive dew]

Oh i dont have text sadly xD Just random searching.
Been mostly at the whims of google's ai search results

oh wait

i have heard of something when theres a mix

[true parcel]

Do you mind if i recommend you a text since I think it will be very very very difficult on your own without guidance

[cursive dew]

but they never called that a contingent. They called the table's result "Consistent"?

sure 😄

[true parcel]

Eh consistency and inconsistency is a different concept

Sure let me find it.

[cursive dew]

So theres no correlation between the result of a table being logically equivlant and a contradiction?
Since i assumed F,F wasnt one, i assumed i could of used the logical equivlance, and checking if the result of that is all false

[true parcel]

There is no connection

[cursive dew]

silly me

[true parcel]

But i guess you can say every contradiction are logically equivalent

[cursive dew]

btw this logic stuff is ideal to know beforehand before starting set theory right?

[true parcel]

Actually I'll send it to u thru dm

More appropriate

[cursive dew]

dw already had the page open

[true parcel]

I don't know what other people would say but

I think it is very important to have a strong background of logics before starting set theory

[fluid ibex]

yeah it helps a lot

[polar geode]

how can i interpret "a is not congruent to 0 (mod 4)"?

[little prism]

you can say that a is not divisible by 4

but otherwise I am not quite sure what you are looking for

[polar geode]

can someone give me a tip on how to solve this?

[cerulean wind]

do you have a specific goal you want to achieve? just figure out the sequence of numbers that it generates? figure out the most efficient way to convert logs to charcoal? derive a recursive relationship (if so, you need to be more specific)?

[cerulean wind]

when you are working modulo 4, you only need to consider 0, 1, 2, 3, since every natural number falls into one of those categories.

there are a total of 10 multiplications you can have, so you should be able to brute force this

[polar geode]

so does that mean i only need to look at multiples of 4?

or wdym by 0, 1, 2, 3

[cerulean wind]

what does a = 0 mod 4 mean to you?

[polar geode]

a and 0 have the same remainder when divided by 4
a has the remainder 0 when divided by 4
a - 0 is divisible by 4, so a is divisible by 4

[cerulean wind]

ok… so you are trying to find two number a and b which are not multiples of four, but whose product is a multiple of 4, agreed?

[polar geode]

yes

[cerulean wind]

i am telling you that you only need to consider the numbers 0, 1, 2, 3 for this part of the problem

can you see why?

[polar geode]

i don't understand why 3 is there

[cerulean wind]

what is 7 modulo 4?

[polar geode]

3

ohh wait

[cerulean wind]

okay. good. every natural number has remainder 0, 1, 2, or 3 when you mod by 4

[polar geode]

do you mean that i should look at the possible remainders of 4?

ohh

[cerulean wind]

yes. so either 0, 1, 2, or 3

[polar geode]

so i need to find two numbers that when you divide by 4 you get the remainders 0,1,2 or 3?

[cerulean wind]

no.

[cerulean wind]

this

remember?

[cerulean wind]

any number when you divide by 4 has remainder either 0, 1, 2, 3

those are the only possibilities (up to congruence modulo 4)

[polar geode]

it needs to be a product (a*b) that has the remainder 0 when divided by 4 ?

[cerulean wind]

yes

exactly

and a and b are both not divisible by 4

[polar geode]

so can i say for example

a=2 and b=6

[cerulean wind]

precisely!

[polar geode]

thank you so much!!

[slow warren]

hey so im on the same task actually HAHA, so i kinda get what the thing here is, the problem for rme is how to write it down as a prooff/solution for the task, i mean i wont just ask for it since thats literally giving me an answer, but are there any likd idk tiopps orr any advice on how to "rephrase" this into a valid solution if it makes sense

[cerulean wind]

you can brute force this as well by considering 0, 1, 2, 3, 4, as you are now working modulo 5

and you can just make a 5 x 5 matrix examining all of the products modulo 5

[slow warren]

i mean i AM still figuring ouht on how to wordify the mod 4 part

i get it but i cant phrase it

[cerulean wind]

oh. can you explain to me why you chose a = 2 and b = 6?

[slow warren]

Honestly just because itsa the 2 numbersa i found wich are not div by four but its product is

[cerulean wind]

then say exactly that!

a = 2 is 2 mod 4
b = 6 is 2 mod 4
ab = 12 is 0 mod 4 since it is divisible by 4

[slow warren]

This sounds too simple tho idk XD atp im either overcomplicating things or our teacher expects an essay everry HW we have

because we DO need an overall claim

and now we just picked 2 numbers

yk

[cerulean wind]

yes! and that is all that the question required of us

[polar geode]

it only said find elements

and then the second part is prove blablabla

[cerulean wind]

there are two parts to the question

[slow warren]

ahh

well okay ill just take first part for granted then, atleast my brain works abit ??? hahaha

im almost 5h on studying LOL

[polar geode]

how can we prove the second part?

[cerulean wind]

here is how I would answer the first part of the question:

Proof: We are asked to find two natural numbers an and b, both not divisible by 4, but whose product is.
we choose a = 2 and b = 6.
a = 2 = 4 * 0 + 2 is 2 modulo 4
b = 4 * 1 + 2 is 2 modulo 4
an = 12 = 4 * 3 + 0 is 0 modulo 4
QED

[cerulean wind]

this

[slow warren]

yh i had that in mind kinda

[slow warren]

How are here the numbers 0,1,2,3 interesting tho wich u mentioned

before

[cerulean wind]

take any natural number has remainder r = 0, r = 1, r = 2, or r = 3

and since we only care about remainders for this problem, these are the only parts of the numbers we should focus on

to see this more explicitly, if a = 4n + r and b = 4m + r’, then
ab = 4(4nm + nr’ + mr) + rr’

so if we can figure out what the remainder of rr’ is when divided by 4, then we will know what the remainder of ab is

[slow warren]

ok and how would we do that HAHA?

welp it doesnt matter for now i think

so if we can literally use the same logic for the next parrt

oh no wait

this is exactly what we need isnt it? for the next part

but with remainders being 1 2 3 4

[cerulean wind]

and 0, but yes

[slow warren]

ok

so instead 4 we have 5

a = 5n + r and b = 5m + r’

this right

[cerulean wind]

i encourage you to make the 5 by 5 matrix of remainders of numbers products of 0, 1, 2, 3, 4 when divided by 5

[cerulean wind]

yes

[slow warren]

Huh

can u give 1 example

[cerulean wind]

this

[slow warren]

so 0 mod 5 1 mod 5 etc

wait im gonna think before jumping into my habit of panicking

[cerulean wind]

0 * 0 mod 5, 0 * 1 mod 5, …, 0 * 4 mod 5
1 * 0 mod 5, 1 * 1 mod 5, …, 1 * 4 mod 5

[polar geode]

How can that be useful for the proof?

[slow warren]

lemme finish itr and send it, we might see it maybe not XD

Okay so

the matrrix is

0 1 2 3 4
0 1 2 3 4
0 2 4 1 3
0 3 1 4 2
0 4 3 2 1

what now

if its even corrrect

im gonna shgop grroceries so not responding for a while, i appreciate ur help tho, thank you, illread it once im back ^^

[cerulean wind]

it should be:

0 0 0 0 0
0 1 2 3 4
0 2 4 1 3
0 3 1 4 2
0 4 3 2 1

[cerulean wind]

anyways, you can clearly see that for any a and b not divisible by 5, their product is also not divisible by 5

[polar geode]

is it valid to use this in the proof? like as cases "if r = 1 ..."

[slow warren]

I mean ug we have to write it like he did if a and b are bot div by 5 ab also isnt hence a or b must be div 5

Or sum like that

But im still in market so im just writing it fast

[slow warren]

now im back home

[warped gull]

hello

how would I address this Q? I have been thinking about it for a while and I still don't have a direction

[lethal linden]

What do you have so far? How have you tried to use the hints?

[warped gull]

Literally nothing, I don't know how to start
I need direction

[cerulean wind]

yes, this is perfectly valid. it is just a way of compactly presenting the cases you would consider

[lethal linden]

Do you know what strong induction is?

[cerulean wind]

how would you find the binary representation for 6?

[warped gull]

Yes

[warped gull]

I don't know how to do that as I don't fully understand the question

[cerulean wind]

ok

so, its important that you can do this for small numbers

[cerulean wind]

try to use this definition to get the binary representation for 0, 1, 2, 3, and 4

that is, try to find a natural number r and a sequence c0, c1, …, cr such that
N = c_r 2^r + .. + c0

r should be very small for these numbers

[lethal linden]

Like @cerulean wind said, first make sure you can write down the binary representation for small numbers.

If you understand what it means to represent something in binary, it should take you maybe 30 seconds to write down all the numbers from 0 to 10 in binary.

[pliant horizon]

prof asked me to explain what a "proper set" is to my discrete structure students tomorrow. this is like a super intro course. does he mean "proper subset", or is there a meaning for "proper set" i'm just not aware of that would be reasonable for day one of a discrete structures course?
i'm assuming he doesn't mean explain the set theory axioms like regularity lol
his words exactly were "For this week how about doing problems 1,2,3 on page 12. I did not tell them what a proper set is yet, you would want to explain it to them briefly."
and these are the problems he mentioned.
asking here first in case i'm just obviously overthinking. i think i am but i'm never sure.

[fossil mural]

even if you did explain the axioms of ZFC that wouldn't really result in a meaning of "proper set"

and what the problems are clearly referring to is "proper subset"

so yeah i think you are just overthinking

[pliant horizon]

okay cool thanks

[pliant horizon]

dumb question: so like obviously the answer they want is that {x,y,z,x}={x,y,z}
but I remember in a free group context or something there was a case where the two x's are distinct. am I remembering this right?
and I'm assuming I shouldn't bring it up to my students to confuse them lol

[slow warren]

c squared, u there and have time?

[cerulean wind]

i’ll have some time later today

[slow warren]

ahh okok, cuz im doin the things now, well ill try em and later ask u if its correct or sum haha

[cerulean wind]

there should be ppl on soon to help you out tho

[neon harbor]

The free group on {x} is {..., x^(-2), x^(-1), 1, x, x^2, ...}, isn't it? I can't think of a case where you have two x's in a set that are actually distinct

[quick folio]

hey, just kinda curious. what's your problem? :)

[slow warren]

hellu

1 second

[quick folio]

oh, that's a classic problem lol

ok so following up on what c squared said, you see why you only need to consider the numbers from 1 to n?

[slow warren]

Well since its all natural numbers

[quick folio]

yes

but I claim that that is in fact the same as only thinking about 1 to n

[slow warren]

wut

i mean yeah

i guess XD, so 1 to n cuz theres no neg numbers to be had per def of the task, do you mean this, or wdym ecatly by only consider numbers 1 to n

[quick folio]

no, even if we consider the negative numbers

it is still the same as only thinking about 1 to n

[slow warren]

i think im thinking abt smth else, what did you mean by c squared saying we only consider numbers from 1 to n

[quick folio]

it's basically this

[slow warren]

so we only look at the prime numbers 1 to n

nvm we need to assume m not being prime

[quick folio]

right, so what does m not being prime mean?

[slow warren]

a * b is a multiple of m?

[quick folio]

what is a, what is b?

where are they coming from?

[quick folio]

also that's not true. 3 * 2 is a multiple of 3, but 3 is prime

[slow warren]

ahh i thought abt the def where every number larger than one can be written as a product of primes, but yh that would mean 3 * 2

[quick folio]

ok, so (one of) the definition of a prime number p, is that there does not exists at least two (potentially non-distinct) numbers a,b such that a*b = p AND a,b are not equal to 1 or -1

not that a*b is a multiple of p, that is a lot weaker

[slow warren]

yes

[quick folio]

(ok so I'm assuming this is an intro to proofs class, right?)

question gives off that kinda vibes

[slow warren]

but that will def not be enough#

[cerulean wind]

6 = 3 * 2.

[slow warren]

i dont think thats the point of the task

[quick folio]

lmao yes I changed it

[cerulean wind]

this is not the right definition of prime

oh, i can’t read

missed the not

[quick folio]

no

you didn't

it wasn't there until I edited it

[cerulean wind]

oh cool

[quick folio]

but anyways, a very useful way to think about questions like these, is to first always ask yourself what do you have

i.e. what definitions / theorems are available to you right now

because those are the only things you should need in your proof

[cerulean wind]

this still isnt right. 7 = 7 * 1

[quick folio]

oh ffs, why do units exist lol

[cerulean wind]

lol

[slow warren]

So
M being an element of the Natural numbers
aswell as a and b
If a times b is congruent 0 mod m, then either a con 0 mod m or b con 0 mod m
we assume m is not prime

but yh like i said idk how to ocntinue, my head doesnt work i think

idek if this is all i have#

[quick folio]

the point I'm trying to make is that, the only 3 numbers you have

is m, a and b

along with the knowledge that a*b = m with a,b being not equal to 1

so therefore, your proof should only need these 3 numbers

[cerulean wind]

i think this definition should work fine for this problem:
p is prime iff 1 and p are the only positive divisors of p

[quick folio]

yeah but the ab=m is a lot more useful for this question

[cerulean wind]

i wouldn’t say a lot, but potato potato

any definition of prime (that’s useful here) is going to have some mention of 1 and p

eg, p is prime provided that there do not exists a,b strictly between 1 and p such that ab = p

which says exactly the same thing as the other definition

[neon harbor]

When doing a proof, you should have a list of assumptions (ie. hypotheses you can use) and a list of goals (ie. things you need to prove). One assumption you have introduced is that p is not a prime. What is your next goal? Remember this is a proof by contraposition

[lethal linden]

Use the hint. Write out the contrapositive explicitly.

The original statement is:

If, for all a,b ∈ ℕ, ab = 0 (mod m) implies a = 0 or b = 0 modulo m, then m is prime.

The contrapositive is:

If m is composite then there exist a,b ∈ ℕ such that a != 0, b != 0, and ab = 0 modulo m.

So the contrapositive says that if m is composite your job is to find such a and b. If you really understand what "composite" means then a sutable choice of a and b is almost immediate.

But if you can't see it right away, pick a small composite m like m=4 or m=6 and see if you can't find such a,b. For example, what goes wrong if m is a perfect square like m=4 or m=9?

Because of the way modular arithmetic works you know you only have to look at {0,1,2,3,4,6} for m = 6 because any natural number is congruent to one of those (or {0,1,2, ..., m-1} in general). That means for small m you can just check every possibility.

[slow warren]

i gpot this

If m is not orime it means it is a product of 2 integers wich are larger than 1 but smaller then m wich are a and b in our case,

a * b = m and 1 < a < m , 1 < b < m

so a * b congruent 0 mod m wich satisfy the condition,

but a and b are not congruent to 0 mod m because they are divisors of m and therefore contradicts the conditions that if a * b congruent 0 mod m then a congruent 0 mod m or b congruent m wich doesnt satisfy the condition

Because theres a contradiction in m being not prime it must be prime

[lethal linden]

That's the idea.

There's no contradiction involved.

P ⇒ Q and its contrapositive ¬Q ⇒ ¬P are logically equivalent. If, given a composite natural number m, you can find appropriate natural numbers a,b then you've proven the contrapositive. You're just done.

A composite number m has at least two non-trivial factors. They're smaller than m, so they aren't congruent to 0 mod m, but their product will be m.

[lethal linden]

But the real lesson is to follow the hint, where "follow" means make it explicit for yourself. Don't just think vaguely about the contrapositive, put it on paper in front of your eyes.

When I did that for you, you went from "omg I'm stuck, there's nowhere to go" to seeing it immediately. So: that's the way to get unstuck!

[pliant horizon]

no wait it wasn't free groups it was disjoint unions i think. like if A={x,y,z} and B={x}. but maybe i'm remembering that wrong

[neon harbor]

Yeah, the disjoint union is kind of weird - the disjoint union of {x, y, z} and {x} would have 4 elements, but it wouldn't literally be {x, y, z, x}. You would need some way to keep track of where each element came from, so you could write the disjoint union as {(A, x), (A, y), (A, z), (B, x)} for example

[brave rock]

A typical construction would be $A \sqcup B \coloneqq ({0} \times A) \cup ({1} \times B)$

[vital dew]

$\mathbf{Boytjie}$

[pliant horizon]

ah thanks people that's helpful. I feel more confident just saying it's {x,y,z} then lol

I mean I already was but whatever you know what I mean

[polar geode]

can someone tell me if this looks right?

[lethal linden]

First, say what the contrapositive is.

We will prove the contrapositive:

Yadda yadda

Let m be composite.

I wouldn't say m = pq because p and q in this context generally signal prime numbers, potentially misleading the reader (grader) into thinking you believe m is the product of two primes.

Just say "Then m can be factored as m = ab where a,b are natural numbers with 1 < a,b < m."

If you want to really telegraph that you understand, add something like "For example, let a be the smallest prime dividing m and let b = m/a."

Then that's it, those are your a and b. Neither a nor b are congruent to 0 mod m and ab = m = 0 (mod m). QED.

[polar geode]

what's the purpose of the sentence "let a be the smallest prime dividing m and let b = m/a"?

and thank you for the response i really appreciate it

[lethal linden]

Imagine a hypothetical less experienced undergraduate reading what you wrote. When you assert "Then m can be factored as m = ab where a,b are natural numbers with 1 < a,b < m" they might go "Can it? How?"

You might say, hey, it's obvious, that's what composite means. Or, hey, just look the prime factorization and split the products into any two factors you like.

Or you can just put the right idea in their head from the get go.

Your job is to communicate that you understand, whether to that hypothetical less experienced undergrad or your grader. There's no downside in including the "For example, let a be the smallest prime..." part. Whoever is reading will know that you understand what's going on and have little doubt you could justify that if pressed.

A real stickler might insist you use whatever definition your textbook gave of composite.

[polar geode]

this makes sense, thank you so much

[weary tiger]

can someone explain how we do these?

[lunar ginkgo]

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik.
discussion link :- https://discord.gg/3pNM3H7Z
Anyone who has read the book, currently reading or will start can post some interesting problems, doubts or ideas from and somewhat outside of the book here.

[lunar ginkgo]

i think you solve the two equations as normal linear equations but you can't divide terms left and right as you do normally

book mentioned an ad hoc approach basically some clever observation you made seeing the equations

here it's when you add the two equations the y terms cancel out being multiple of 6 in mod 6

[weary tiger]

why do we have no solutions for a?

and in b, when we find the x values, we only check them for y in second question

[lunar ginkgo]

because anything multiple of 3 can give remainder 0 or 3 when divided by 6

[weary tiger]

whys that?

[lunar ginkgo]

so we can't get 5 for any x

[weary tiger]

okay i got that

[weary tiger]

and this?

[lunar ginkgo]

you got $3x \equiv 0(mod 6)$ as result

[vital dew]

A753

[fossil mural]

$3x \equiv 0 \pmod 6$

[weary tiger]

yes

[vital dew]

bee [it/its]

[lunar ginkgo]

so you then test for what x it's true

[weary tiger]

so x can be 0,2,4

[lunar ginkgo]

yep

[weary tiger]

what after that?

im basically not able to understand the testing for y part

[lunar ginkgo]

you plug the values and verify

[weary tiger]

but we're only plugging in second equation

why's that

[fossil mural]

well we chose values of x that satisfy 3x = 0 mod 6, and if we subtract the second equation from that, we get the first equation

so if the second equation is true the first one is as well (and the other way around too), for x = 0 or 2 or 4

and it's faster to only check one

[weary tiger]

so we could have done it for the first congruence as well?

[fossil mural]

yep

[lunar ginkgo]

you can check both if you want

[weary tiger]

that makes sense

okay i got it, thank you @lunar ginkgo @fossil mural

[native nova]

I'm confused

First off I don't think the book ever showed the logical equivalence stated

[native nova]

Also isn't this false for let's say,

b = 2
a = 9

b is prime but
a is not prime and b is not a divisor of a?

Also a little bit confused about how a nonconstructive existence proof works

[pliant horizon]

i think you're right, that looks completely wrong, i'm not sure what the book is going for. my guess for what they were maybe trying to do is that if b is prime and b=ac, then b divides a or b divides c? idk that's something good to prove using that technique though

[native nova]

Ummm ok

Are there any famous examples that make more sense than I can look at

[pliant horizon]

i mean p divides ab implies p divides a or p divides b is like the famous example

something stupid off the top of my head
if n is an integer then n is even or n is odd lol

[native nova]

Ooo so like if p divides ab, and p does not divide a, then p must divide b?

[pliant horizon]

yeah exactly

in some ways that's how we define prime-ness (in more general settings)

[native nova]

Mmm ok

[lunar ginkgo]

can anyone help me understand this proof
I understood the proof of the multiset theorem for worpitzky identity but
how did we derived the corollary?
we substituted $p = x$ and $k_{i} = k$ for every $i$ but I didn't understood how we got the $RHS$ in our identity and how did we got the relation $a_{n,p} = a_{n,(n-1)k + 2 - p}$ ?

[vital dew]

A753

[astral hollow]

Does anyone know why when using the Euclidean algorithm for binary expansions the largest number (the first number you are working with) translates to the smallest binary digit?

[lethal linden]

p → q is equivalent to ¬p ∨ q, so:

p → (q∨r) ⇔ ¬p ∨ q ∨ r
          ⇔ ¬(p ∧ ¬q) ∨ r
          ⇔  (p ∧ ¬q) → r

For the non-constructive proof, I assume the idea is to prove that for every natural number n there exists a prime number p with p > n?

Unfortunately, the proof is constructive. The proof says: if you want to find a prime number p larger than n, it suffices to do two things:

1. Calculate n! + 1
2. Find any prime factor p of n! + 1

Any such prime factor will be larger than n.

A non-constructive exist proof means a proof by contradiction, which involves wanting to prove P by assuming ¬P, deriving absurdity, and concluding P. This fundamentally relies on the fact that ¬¬P → P, which is true because of the law of excluded middle.

A related thing is a proof of ¬P by assuming P, deriving absurdity, and concluding ¬P. This is constructive and works even if we don't accept the law of excluded middle.

It's ironic because the the proof of the infinitude of primes (this is called Euclid's theorem) is usually presented in terms of a contradiction: assume we have a finite list of all prime numbers, then yadda yadda contradiction. So on its face it appears non-constructive, but if you look at the usual presentation of the proof you see it falls into the second category and not the first.

The proof you posted, however, entirely avoids the "contradiction" language, which makes the fact that it's constructive more apparent!

[lethal linden]

Can you give an example of what you mean?

[astral hollow]

Convert 6 from base 10 to base 2:
6 = 2 * 3 + 0
3 = 2 * 1 + 1
1 = 2 * 0 + 1

Binary representation of 6 is 110

So the "largest number" 6 in Euclidean algorithm gets a remainder of 0 and that is the rightermost bit aka the 0th place

Maybe Im just being weird about it but its just interesting that the largest number translates to the smallest place

[old obsidian]

I look at the last digit as a remainder after the first division, it seems natural

[lethal linden]

The right-most bit is the remainder after dividing by 2, just like the right-most digit in a number is the remainder after dividing by 10.

[astral hollow]

Huge

Huge intel

That makes sense

mod 10 gives me the smallest digit

mod 2 does the same for binary

HUGE

[lethal linden]

Positional notation is really an instruction for how to build a number, even if we learn decimal so well that it becomes second nature.

Like, 247 means:

2·10² + 4·10¹ + 7·10⁰

Well, every non-zero power of 10 is congruent to 0 (mod 10), so that entire expression mod 10 is going to be 7.

If you want the second digit, subtract 7 from the original number, divide by 10 and then look at that mod 10, i.e., (247 - 7)/10 mod 10. That gets you 4.

Subtract 4 from that, divide by 10, blah blah

There's nothing special about 10 there. Replace 10 with any other number n and you'll get the base n representation.

[astral hollow]

Right yea it makes sense

Thank you guys

[lethal linden]

🫡

[astral hollow]

The question was asked to my prof and he didnt have an immidiate answer so I came here

Yall never disappoint

[lethal linden]

It's one of those questions that indicates the student is looking at the situation in an unusual or even confused way, so it's hard to know exactly what's being asked.

Asking a student for an example in a live class environment can be a risky maneuver because they might not have one, they might have one but not be great at saying it out loud, they might be able to say it but it's awkward or confused in its own right, etc.

The lecturer has to weigh the opportunity cost of spending time figuring out what the student "really" meant and then answering it. The error bars on the former are very high.

Spending 15 minutes only to learn it's a wild goose chase is not a great use of lecture time.

[astral hollow]

Thats also useful info lol

Might look into teaching myself one day so I'll keep this in mind I hope

[native nova]

Ooo ok

What a reply

The book said non-constructive proofs are usually contradictions, so I assumed that meant that there are other ways to do non-constructive proofs

[native nova]

But yea this makes more sense, as it appears to be showing the existence of a p such than p>n

Also I just realised I only posted the solution and not the question

[lethal linden]

There's also no reason we couldn't write "247" as "742".

Lots of languages say numbers like "47" as "7 and 40", for example.

[astral hollow]

Well yea I suppose as long as we're keeping track

Do you teach?

[lethal linden]

Or you're working in a language that's written right-to-left like Arabic 😉

[lethal linden]

If you want to nail down what makes a proof "constructive" or "non-constructive" you have to do two things:

1. Turn proofs into mathematical objects so you can say mathematical things about them
2. Given (1), find a criteria for when such a proof-as-mathematical-object should be called constructive or non-constructive

A "constructive proof" in the sense of (2) means a proof that doesn't rely on the law of excluded middle. Every proof by contradiction in the first sense relies on it, and any proof that uses LEM can be turned into a proof by contradiction in the first sense.

These concerns form the core of a entire subject area called "mathematical logic". It's too technical and too unmotivated for an introductory course. Outside that situation, phrases like "constructive" and "non-constructive" are more of a vibe, which is where you get handwavy phrases like "usually involves", etc.

The book would have to get real specific about what "involves" means!

Informally, a proof being "non-constructive" means something like...we can show an object exists with some property, but we can't say anything more about how to determine that object.

Even in that informal sense the given proof is constructive, though. Oh, so given n there exists a prime p > n? How to I find it? Calculate n! + 1 and then find its smallest prime factor.

[lethal linden]

Yes.

[random sparrow]

is the empty set am element of every set or is it just a subset of every set

like, why?

[agile magnet]

what's the difference between subset and element?

can you describe it to me?

Like say $S$ is a set. What is the difference between the statements $A \in S$ and $A \subseteq S$?

[vital dew]

Spamakin🎷

[agile magnet]

And even better, can you give me concrete examples of S and A where one is true and the other is false, and perhaps some examples where both are true as well as an example where both are false.

I don't need super formal mathematics, just write however you best understand what is going on

we can worry about formalism if needed when the time comes

[random sparrow]

S = {a,b,c,d}
A = {c,d}
A is not in S
A is a subset of S
now second example
A ={c,d}
S = {a,b,{c,d}}
A is in S
but idk if A is a subset of S

did i do it right?

I think i messed up

[agile magnet]

nope you did it perfect

[agile magnet]

ok so you seem to understand it enough to give examples, so I will assume you understand the difference between these statements

but lets answer this last part "idk if A is a subset of S"

A ={c,d}
S = {a,b,{c,d}}

so what would it mean for A to be a subset of S?

[random sparrow]

like every element of A is contained in S

[agile magnet]

yea

so is every element of A contained in S?

[random sparrow]

it is not

[agile magnet]

what is an element of A that is not in S?

[random sparrow]

they are disjoint

[agile magnet]

yea

[random sparrow]

c,d are not in S

[agile magnet]

ok cool you seem to have a good understanding

so now

[agile magnet]

lets tackle your original question

a little more abstract, but do you think that the empty set is a subset of every set?

[random sparrow]

I think so, because everyone always say that but I never understood

[agile magnet]

do you know the concept of vacuous truth?

[random sparrow]

no

[agile magnet]

ok so you're familiar with the definition of $P \implies Q$ right? So you know that $P \implies Q$ is true if $P$ is false?

[vital dew]

Spamakin🎷

[agile magnet]

I did not ask for the definition, I know the definition. I am asking if you have seen this before

[random sparrow]

well I sort of memorized this one tbh, I understand it as a politician promise, I have seen it though

[agile magnet]

Well it's the definition

there's nothing really to understand persay

just like how $P \land Q$ is defined a certain way, or $P \lor Q$ is defined a certain way

[vital dew]

Spamakin🎷

[agile magnet]

it's a logical symbol with a given definition

[random sparrow]

the land and lor tables are mor intuitive though

[agile magnet]

sure

so the intuition here is that we want statement like $a$ and $b$ are even integers $\implies a + b$ is even'' to be true. If we consider an odd $a$, then the statement $a$ and $b$ are even integers'' is false, but we still want the whole statement ``$a$ and $b$ are even integers $\implies a + b$ is even'' to be true.

[vital dew]

Spamakin🎷

[agile magnet]

we define the implication arrow in this way to model how we want to think about mathematical statements

just like how we define the logical and and logical or truth tables in a certain to model how we think about statements

so in the end these are just definitions which model how we think about things

but they are nonetheless definitions

[random sparrow]

but sum of two odd is even
or you mean sum of an even with an odd

[lethal linden]

In classical propositional logic, P → Q is equivalent to ¬P or Q. In particular, if P is false then P → Q is true.

That feels weird to many folks, e.g., "If my grandmother is a fish then squares are circles" is true if we interpret that "if...then" as →.

The feeling that this is somehow "off" or "wrong" or doesn't capture what we mean by "if...then" is called the "Paradox of Material Implication" (https://en.wikipedia.org/wiki/Paradoxes_of_material_implication)

I only point that out in case you feel that way yourself. You're not alone!

[agile magnet]

I feel nonsense examples like that only confuse people rather than actually give intuition

[agile magnet]

Exactly! So just because a or b can be odd doesn't mean that the statement "a and b are even implies a + b is even" should be false right? That wouldn't be useful to us.

[lethal linden]

I don't really think there is an intuition. You can say "Well, that's how it's defined"

Or, slightly better, "If we want → to be a binary function on boolean values then the alternatives are worse."

[agile magnet]

I think what I am saying gives a good intuition (at least this example I am giving has helped people in the past when I have TAed discrete math)

but @random sparrow does what I am saying make sense about why we want P implies Q to be true even if P is false?

[random sparrow]

I mean a + b is never even unless a and b are either even or odd

going back to the
P -> Q
what would P and Q be here?

[lethal linden]

Think of the statement A ⊆ B as saying

∀x(x ∈ A → x ∈ B)

In general P → Q is equivalent to ¬P or Q. In particular, if P is false then P → Q is true.

So ∅ ⊆ B translates to

∀x(x ∈ ∅ → x ∈ B)

But x ∈ ∅ is false for all x, so x ∈ ∅ → x ∈ B is true, hence ∅ ⊆ B.

[random sparrow]

how did you translated to a "or"

[lethal linden]

What's a lor?

[agile magnet]

\lor

[lethal linden]

Oh, I see.

[agile magnet]

latex command for logical or

[lethal linden]

Yeah yeah

[agile magnet]

write out both truth tables

they're the same

therefore they're equivalent

[agile magnet]

In the statement $a$ and $b$ are even $\implies a + b$ is even'', $P$ would be $a$ and $b$ are even'' and $Q$ would be ``$a + b$ is even''

[vital dew]

Spamakin🎷

[random sparrow]

a and b are odd makes P false but Q true

[random sparrow]

is this a proof of why emptyset is subset of every set?
really interesting aswell

I confused subset with element in, Again lmao, edited

[random sparrow]

yeah

[lethal linden]

Yes, it's showing how the empty set is a subset of every set if you accept that P→Q is true whenever P is false.

[random sparrow]

really interesting though

I appreciate the help really

I think i am starting to understand a bit more

I will come back with more questions thank you both guys

[oblique crypt]

Do any of you know good resources for self studying discrete? I have a discrete math for cs class this semester and I’ve never done this kind of math before

Like a good YouTube channel or website

[native nova]

Oh wow ok

[oblique crypt]

Also does anybody have any experiences with these books and know if they’re good or bad for beginners with little to no background knowledge

[lunar ginkgo]

kenneth rosen book is quite famous as an introductory text for discrete maths and it's good.

[solar marsh]

Any combinatorial topology book recommendations?

[tender jewel]

On a chessboard, determine the minimum number of knights required to dominate all squares (each square is either occupied or attacked by at least one knight). Prove that this number is [n^2/6] for n>8, or provide a counterexample.

[agile magnet]

I've heard good things about this text: https://link.springer.com/book/10.1007/978-3-540-76649-0

I've never looked at this text myself but if you're curious about the prerequisites:

oops, also this convo should have been in #book-recommendations in the future

[solar marsh]

thank you so much 🤝 👽

[agile magnet]

if you ask there you'll probably get more recommentations

[solar marsh]

ooh okey

[agile magnet]

if you do ask there, say what background you have so that people can give more targeted recs

[olive lake]

how many fully connected 20 point graph with no loops are there?

nvm i forget OEIS exists

[lunar ginkgo]

small doubt will $H_{n^{k + 1}}-H_{n^{k}}\rightarrow\ln(n);as;k\rightarrow\infty;where;H_n ;is; n^{th}; harmonic number$ ?

[vital dew]

A753

[abstract oak]

is this the place to discuss stuff like sorting algorythms?

Alrgortythms not in the AI shit sense

I am new to the space

Looking for people who know more than me to check my work

[lunar ginkgo]

did you made some sorting algorithm and want to confirm or find complexity? or just asking doubts?

[abstract oak]

I made my first sorting algorythm but it might be shit

I think it makes sense and it's pretty fast on big arrays, slow on small arrays

But I'm new so I might be dumb af

[lunar ginkgo]

have you verified that it doesn't exist somewhere already?

[abstract oak]

Yes

I call it InterpolatedSort

[lunar ginkgo]

that's cool

[lunar ginkgo]

what's the idea behind it?

[abstract oak]

This is it in action

[abstract oak]

basically, very basically: it puts the first and last number in a virtual array and interpolates the needed positions from that.

The reasoning: if you know the first and last number in the array you know the numbers in between by basic addition

No further sorting required

The async funtion is bogging me down because I sorted larger arrays in unity within a second

I'm in contact with the site admin and he's gonna increase the max array size

[abstract oak]

    if (elements.length <= 1) return;

    const values = await Promise.all(elements.map((el) => getValue(el)));

    const minValue = Math.min(...values);
    const maxValue = Math.max(...values);
    const range = maxValue - minValue;

    if (range === 0) return; // All elements are equal; nothing to sort
    const sortedPositions = values.map((value, idx) => ({
        index: idx,
        targetIndex: Math.round(((value - minValue) / range) * (elements.length - 1)),
    }));

    sortedPositions.sort((a, b) => a.targetIndex - b.targetIndex);
    const visited = new Array(elements.length).fill(false);

    for (let i = 0; i < sortedPositions.length; i++) {
        if (visited[i] || sortedPositions[i].index === i) continue;

        let current = i;
        const cycle = [];
        while (!visited[current]) {
            visited[current] = true;
            cycle.push(current);
            current = sortedPositions[current].index;
        }

        for (let j = 0; j < cycle.length - 1; j++) {
            await swap(cycle[j], cycle[j + 1]);
        }
    }
}```

This is the code above

[lunar ginkgo]

umm how do you decide which element goes where after assigning first and last element? and how do you insert them?

[abstract oak]

Easily, the array has a clear first and last element, the rest can be interpolated from that

[abstract oak]

As you can see in the video after it finds the first and last elements the grid gradually takes shape

[lunar ginkgo]

so you are using interpolation to assign which element goes where based of first and last element?

[abstract oak]

The async is working aginst me here because I can normalize an array in a single void

[abstract oak]

Welll yes and no, for all the end result cares the original array doesn't even exist

The end result only cares about what it is given

[lunar ginkgo]

does it handle duplicate values ?

[abstract oak]

There are no dupe values because the array consists of individual values

atleast for sortvisualizer.com

[lunar ginkgo]

but what if array had duplicates?

we can't simply assign disregarding the original array

[abstract oak]

Sounds interesting\

[lunar ginkgo]

and what if your largest value != your array size?

something like 2, 7 , 9 ,1000, 100000

[abstract oak]

Okay I like this server

I will come back to this tomorrow

[lunar ginkgo]

if you need to handle duplicates and larger values you might what to take a look at this : https://en.wikipedia.org/wiki/Interpolation_sort

[abstract oak]

This wasn't even a consideration because my introduction to the topic has been in rudimentary tools

But I like it

[lunar ginkgo]

the fastest sorting algorithm you can create will work in O(n) which is scanning the array once

and only thing we probally hade near to it is https://en.wikipedia.org/wiki/Counting_sort with a constraint on your array max element

[abstract oak]

But O(n) doesn't interpolate does it?

[lunar ginkgo]

I would recommend you to start with some basic algorithms like merge and quick sort

[lunar ginkgo]

nope

[abstract oak]

I based interpolatedsort on SelectionSort at first because i felt like I saw a flaw in it, But it didn't work with a virtual bufffer like I expected tp

[lunar ginkgo]

i don't think we use interpolaltion that much in sorting. it's basically guessing based on existing values where as sorting is finding position for each element in sorting array on an unsorted array

[lunar ginkgo]

there are other variants to improve selection sort

[abstract oak]

is that not a big waste? If you know the bounds of the data interpolation seems only logical

[lunar ginkgo]

it's prolly called quadratic sort or something and it extend nicely to a binary tree at end which sort in nlog(n)

[lunar ginkgo]

you have interpolation sort but insted of prediction element you predict the location of element in your sorted array which is pretty much what you need

[abstract oak]

Hmmm okay I will do some more reading tomorrow

[abstract oak]

Which is why the Async bothers me, but I feel like that's prolly because I don't understand what sorting algortyhms are used for

[lunar ginkgo]

you can start with some introductory text on algorithms to begin with

[abstract oak]

Not again 100_aba_rofl

[lunar ginkgo]

introduction to algorithm by cormen, rivset and stien is good to begin with

or you can go full the art of programming if you are masochist

[abstract oak]

I am not a masochist but I feel like both paths require a big mental investment xD

[lunar ginkgo]

yep

[abstract oak]

My brain prefers to learn from the people around me but spend days trying dumb shit

Thank you for this server

[ebon imp]

reading a paper in which this is used. Any Idea why this should hold for r >= 2^2n * lambda_n(L), where L* is the dual Lattice to L and lambda_n the last successive minima of the lattice

maybe its obvious and i just dont see it

[hard stone]

you might want to ask in a more advanced channel, this channel tends to be for undergraduate class material; also it'd probably be easier for people to answer your question if you linked the paper and added more context

[echo niche]

Guys can anyone explain whats a O(x) i see it a lot but idk what it is

[hard stone]

check out the "asymptotic notation" unit here :) https://www.khanacademy.org/computing/computer-science/algorithms

[echo niche]

Ok ty

Ingore everything and can u tell me what the O's r for?

[odd heart]

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

[lethal linden]

Error terms in some kind of approximation Wolfram is performing

[vagrant slate]

Hi if anyone is familiar with set theory, I would appreciate some help with a question!
https://discord.com/channels/268882317391429632/908075848752590918

[glossy roost]

Hi, is there any way to further simplify this expression or is this it?

Actually, this is the right expression

[brave rock]

A xor B

[glossy roost]

Thank you!

[polar geode]

what is meant by order in b) ?

[brave rock]

The order of f as an element of the group S_n.

If you're forgetting what the order of an element of a group is, you probably need to recap the content. I will state it here:

If such a number $n$ exists, the order of an element $g \in G$ is the smallest positive integer $n$ such that $g^n = e_G$, where $e_G$ denotes the identity of $G$.

[vital dew]

$\mathbf{Boytjie}$

[brave rock]

In such a case that there is no such number n, we say that g has infinite order.

[polar geode]

Thank you !

[obtuse spear]

Help others

[analog pike]

lol I asked this exact question in another coding discord last week, dude said it wasn't worth the time while in uni to tackle TAOCP and said to just go full intro to alg with cormen

[vestal bronze]

taocp is a blog, only sicp is a textbook

(i have read neither just trust)

[polar geode]

is this for c) correct?
(f o f)^−1 (k) =
k-2 for k = 3,4…,n
n-1 for k = 1
n for k = 2

[opal crescent]

yes it is

[polar geode]

thank!!

[haughty garden]

clrs isn’t really the best book to study with if you’re just getting started with algorithms. It feels too rigid of a book for it to be useful for beginners. I would recommend either erickson’s algos textbook (freely available) or algorithm design by kleinberg and tardos. imo, those are more approachable while giving you the same level of rigour that you would expect from clrs

[tropic cloud]

anyone know what I'm doing wrong here

[oblique pelican]

looks like you might need to make the numbers subscripts

by using underscores or something

[tropic cloud]

Spent hours troubleshooting these all for it needing to be written as subscripts. It's so over bro

[oblique pelican]

consequences of online homework

[lethal linden]

I would 100% email your professor/teacher and point this out. Don't be testy in your email, but say like "Hey, FYI, I wasted a bunch of time because I was typing v4 instead of v_4 and thought I was going crazy. See the screenshots below. I didn't realize my mistake until I asked for help in an online chat.

If I made this mistake, other folks are probably making it, too. It might be worth mentioning to everyone."

[iron marsh]

I'm having trouble with part b in this problem. I am very close, but....let me show you the problem I am having (one sec)

This was me approaching it in two different ways.
However, I almost get there, but the inequality at the end is a little larger than the desired inequality.

For the first case, I need that 1/n^n to be 1/n^(2n) and the second try I need 1/2^2 to be 1/2^(2n) to actually get the claim

But I don't have that, which is the problem

[iron marsh]

I'm still having issues with this problem. It's frustratingly close and it's bugging the heck out of me

[neon harbor]

On the last line of your first try, wouldn't you get 4n^n in the denominator, which is bigger than 2n, so the fraction is smaller? It's very late at night, so I might be wrong

[iron marsh]

You would get 2^(2n)*n^n in the denominator

the issue is I need 2^(2n)*n^(2n)

[neon harbor]

Hmm, you would need to extract a 2 from the exponent in the denominator, but it might work still, you'd end up with 2n^(n/2), which is still bigger than 2n for n > 2 (I think?)

[iron marsh]

I'm not sure I follow

The big issue is at the very end of both tries, it is impossible to extract the desired exponent, since it will always give us a smaller number

[cerulean wind]

start like this:

$$(x_1\cdots x_n)(x_{n+1}\cdots x_{2n})\leq \left(\frac{x_1 + \cdots + x_n}{n}\right)^n\left(\frac{x_{n + 1} + \cdots + x_{2n}}{n}\right)^n$$

[vital dew]

c squared

[neon harbor]

Sorry, it was just my sleep deprived brain imagining things 🙃 anyways, good luck with Concrete Mathematics

[iron marsh]

You can now use the fact that P(2) is true from here, but....I thing we again run into the same problem

[cerulean wind]

$$ \left(\frac{x_1 + \cdots + x_n}{n}\right)^n\left(\frac{x_{n + 1} + \cdots + x_{2n}}{n}\right)^n = \left(\frac{(x_1 + \cdots + x_n) (x_{n + 1} + \cdots + x_{2n})}{n^2}\right)^n$$

[iron marsh]

So far so good

[cerulean wind]

keep going

you can use P(2) again here

[iron marsh]

Oh.....keep that n outside

[cerulean wind]

yea

[iron marsh]

Got it!

[vital dew]

c squared

[cerulean wind]

(this was up here)

[vale cairn]

Oh fun, p sure this is basically the original proof

there are lots of proofs of this theorem now though

[serene yew]

Let (D,⊑) be a partial order, for some arbitrary domain D. Prove that D does not contain an
infinitely ascending chain if and only if (D,⊑−1) is well-founded aby thought to solve this

[solar marsh]

If $C$ is a chain without a maximum element in $D$, then $C$ is a chain without a minimum element in $D^{-1}$, and vice versa.

[serene yew]

it is mentioned in the question we are not allowed to use this theorem

@solar marsh

[gusty lance]

boys, if a set contains an ordered pair, A = {(1, 2)} for example, could you say that 1 is of set A? or not because its within the pair

[agile magnet]

is the element 1 an element of the set A?

yes or no?

[gusty lance]

that's what im not sure about LOL I would think yes

[agile magnet]

The answer is no

the set A has exactly one element: (1, 2)

that is a single object

it may have two "parts" but it is a single object

1 is not an element of A, nor is 2, nor is {1, 2}

[gusty lance]

awesome. thank you for the clarification

one more real quick question out of curiosity if you have time

lets say
A = {1, 2, 3} and B = { }

what would A x B look like?

[agile magnet]

What is the definition of A x B for any sets A and B? Can you give me both the formal definition as well as however you best think about what A x B is?

[gusty lance]

"it combines every element from one set with every element from another set to create a new set of ordered pairs."

So for every X in a set, combine it with every Y in the other set is basically how I see it. I guess with a second empty set im just not sure if it would stay {1, 2, 3} or if you would use the empty notation ∅.

but reading now ∅ means empty set so I think it would stay {1, 2, 3}

im brand new to discrete so sorry if these are awful questions

[agile magnet]

don't be sorry, that's what this channel is for

[agile magnet]

ok you've given me a good informal / "this is how I think about A x B"

but do you know the formal definition?

in terms of set builder notation

[gusty lance]

I suppose I do not!

[agile magnet]

ok so

$A \times B = {(a, b) \mid a \in A,\ b \in B}$

[vital dew]

Spamakin🎷

[agile magnet]

have you seen this before?

[gusty lance]

While looking around, yes

[agile magnet]

ok so you know what all the symbols mean?

[gusty lance]

yes

[agile magnet]

if so, lets plug it in with the A and B you gave above (this is in general a good strategy when trying to figure out stuff)

${1, 2, 3} \times \emptyset = {(a, b) \mid a \in {1, 2, 3}, b \in \emptyset}$

[vital dew]

Spamakin🎷

[agile magnet]

now here is my question

there are no elements in the empty set right?

so can we form any pairs (a, b)?

[gusty lance]

We definitely cannot.

so, A x B = ∅

?

[agile magnet]

yup!

[gusty lance]

you are awesome

[agile magnet]

so the following lessons

1: think about stuff intuitively is fine, but you must also learn the formal definitions

2: plugging stuff into definitions is a good strategy

[gusty lance]

Thank you for walking me through it like that, and teaching me those two things. As soon as you made me look at the formal definition it started to click.

Thank you very much 🙏

[blazing lodge]

does a set of all sets contain itself

secondly, why does discrete math exist when its just a worse form of curves

[gusty swallow]

no
because there's a lot of the world that isn't continuous

[blazing lodge]

continuity is a result of infinity at the discrete level

[gusty swallow]

great! I'm rarely in possession of infinity things.

[blazing lodge]

neither exists. its a state of both

[gusty swallow]

cool, so we need both, i agree

[blazing lodge]

wait really

im just bullshitting at this point lol

but it makes sense

[gusty swallow]

continuity works where it works, and discrete works where it works. they sometimes work together, but they're generally used to do different things for a reason

[blazing lodge]

so they are both wrong

[gusty swallow]

that's like saying a hammer is useless because I can't use it on a screw.

[blazing lodge]

if the screw and the substrate is correct, then the hammer works

not perfectly perhaps

[gusty swallow]

"If i change the conditions of your statement then it's fine!"

[sharp rose]

Not if you want to avoid paradoxes

[blazing lodge]

math is infuriating

is lovely in that way. respect to all of u studying it

u can never solve it, only discover

[gusty swallow]

there are places where discrete and continuity work together, not perfectly, but they can approximate eachother. But neither is 'wrong' because it doesn't do what the other does.

[blazing lodge]

approximate how

[gusty swallow]

depends on where you're using it.

linear regression is used to create a continuous function that approximates discrete data.
normal approximation to the binomial uses continuous probability distribution to approximate the probability of a discrete distribution

[blazing lodge]

thats all the same bs

[gusty swallow]

okay

[blazing lodge]

so they approximate eachother

show me something interesting

nvm ill show u

https://www.youtube.com/watch?v=idpOunnpKTo

[blazing lodge]

A follow up to the above. Pls mods delete if necessary https://youtu.be/_xfi0NwoqX8?si=ODTZtHAUStUv13_a

chaos doesnt exist, its just too hard to see

[quick folio]

I mean, the "hard to see" part is kind of the point of chaos

[blazing lodge]

so its an excuse

[quick folio]

an excuse for what, exactly

[blazing lodge]

dunno, being lazy and not computing it?

this is discrete math, everything has a solution

[quick folio]

that's not true

and, sometimes even when you know a solution exists finding it can be very difficult

[blazing lodge]

how are u defining true

in what bounds of compute

[quick folio]

a fun example might be the discrete log problem, which is the backbone of DH-encryption

so the question: given integers a,b and n, can you find a number x such that b^n = a (mod n)?

so turns out, if p is a prime and a and b are both not zero, then at least one solution x always exists

but, actually finding it is a very very difficult problem

in the sense that there is no fast algorthim to efficiently find that x

it's a simple problem if a and b are small

but what if they're both integers with 1000 digits?

tough luck, there is no good way to find them without doing the actual math, which is very hard

[blazing lodge]

cant find x it doesnt exist in ur formula

[quick folio]

you can't find a general expression for x in terms of a and b

but if I fix a and b to be two specific numbers, then x always exist (given that n is prime and a,b are not equal to 0)

e.g. we know that there does exist an x such that 1234567^x = 6789 (mod 419)

but actually finding that x is a very difficult task

so this is what discrete math is really about

[blazing lodge]

I prefer Zybikron hes smarter

[quick folio]

lol sure

but this is an interesting example of a problem that's trivial in continuous math

e.g. log(x) is really easy to find

but is very hard in discrete math

[blazing lodge]

elliptic curves

[quick folio]

that's also a really cool example

[blazing lodge]

is it interesting

[quick folio]

I can generalize that a litte bit more to the study of Diophantine equations

which is a really, really cool part of discrete math (number theory, really)

so the question is, suppose we have a polynomial equation in some variables. Is it possible to find all the integer solutions to that equation?

so this is another example of a problem that's """easy""" if you only want continuous solutions

but very diffcult if you restrict yourself to discrete solutions

a concrete example might be the classic Pythagorean equation x^2 + y^2 = z^2

it's a really simple equation from the point of view of calculus

the derivative of polynomails are really easy to do, so are their integrals

but it becomes a much more interesting problem when you only restrict yourself to integer solutions

i.e.:

1. Does the equation x^2 + y^2 = z^2 have integer solutions?
2. How "many" integer solutions are there?
3. Is there a way to find all integer solutions?

[quick folio]

so, that's my answer to your question - discrete math exists, because discrete math was created to study entirely new and different types of questions that aren't related to curves at all; not as a worse form of continuous math

[serene yew]

@solar marsh this one

so is your approach similer to this theroem right ?

[solar marsh]

yes

the same

[serene yew]

so yes the problem i am not allowed to use the theroem

so i do not know how can i prove it without the theroem

i have anothe approach from dude here and it also using the theorem somehow
The forward direction, i.e. well-foundedness implies no infinite descent, is rather straightforward: Does an infinitely descending sequence have a minimal element?
The converse requires dependent choice to construct an infinite descent if there was some nonempty subset of D that failed to have a minimal element.

so what do you think ?

[pale field]

Please help D:

[lethal linden]

What have you tried? Any thoughts about how to approach it?

[pale field]

ive tried picking squares in this arrangement and continuing the pattern

it seems to work but i can't prove it and nor do i know if its the lowest k value

Something tells me it's gonna be some sort of pidgeon-hole argument

But I genuinely cannot be bothered

[lethal linden]

Mmm, I'd think about the 2x2 case.

[pale field]

I thought about it and thats why I tried splitting up the board into a bunch of 2x2s and having 1 square picked in each 2x2 but I couldn't do anything with it so idk if im being stupid or

i get confused trying to figure out the cases where the domino takes up two 2x2 "cells" at once

[vague path]

can someone explain to me why the cofactors of a graph laplacian are all equal without using kirchhoff's theorem? im having a hard time trying to find a good proof of this fact

[solar marsh]

Is this a fact of simetric matrix with sum/colum sum equals to 0

You can proof that every row and column of adj(A) is in the spanned space (1,...,1)

[slow warren]

Makes sense?

[teal terrace]

Stupid question, but does someone know where I can find good discrete math practice problems that gradually go up in difficulty?

[vestal bronze]

codewars lol

[valid thicket]

need the same for probability

[gusty swallow]

you seem to have a typo in your 4th line "Since g in CnD it follows that x in C and x in D" ?

[slow warren]

oh yh i see it thatnk you haha

[teal terrace]

not coding, just the math problems

[terse wyvern]

well you can design algorithms by hand

finding optimal algorithms using combinatorial methods is half the battle

[nimble hemlock]

Let $T:V \rightarrow W$ be linear. $\text{im}T = W$ if and only if $T$ is surjective.

[vital dew]

clubsoda14

[nimble hemlock]

How do I do the forward direction?

[lethal linden]

What is im(T)? What does it mean if im(T) = W? Write out the definitions.

[tidal tinsel]

any idea?

[agile magnet]

I responded in #proofs-and-logic no need to repost in 4 channels

[terse wyvern]

what have you tried

[novel ore]

Why do we have E = 1 + 1/2E

[spring hound]

E is the expected number of tosses before you get heads.

E requires at least 1 heads, so that's where the 1 comes from.

Then, half the time after the first toss, you need to start over with E again.

That's what the 1/2 E comes from.

[spring hound]

Does that make sense?

[novel ore]

Got it. Thanks!

[spring hound]

No problem.

[dire maple]

Not really sure how to apporach this question ay guidance will help

[lethal linden]

What have you tried? Start by writing down the definitions of the terms involved.

[trim thicket]

i dont understand why theres a distinction between range and codomain
im just starting out in discrete math, but i just discovered that theres a difference between the two

is it just, like, a thing you need to be specific about in higher levels?

[oblique pelican]

The codomain is just a set where the outputs of a function live. The range is the set of outputs. The codomain could be much larger than the range. Sometimes the range is unknown or of a very strange form, but you can at least say something about the codomain.

[lethal linden]

Forget the term "range". The two better terms are "codomain" and "image". In middle/high-school math, the difference between the two are often blurred and it's just called "range".

The "domain" and "codomain" are always part of the specification of a function. If you have a function f: ℚ → ℝ then the domain is ℚ (the rational numbers) and the codomain is ℝ (the real numbers).

The image of a function f, denoted im(f), is the set of all output values. It's always a subset of the codomain.

im(f) = {f(x) : x ∈ ℚ}

Consider two functions:

1. The function f: ℚ → ℝ defined by f(x) = x/2
2. The function g: ℚ → ℚ defined by g(x) = x/2.

Are those the "same" function? Technically no, because they have different codomains. They do, however, have the same image.

Why make this distinction? Well, certain concepts like "being surjective" are hard to talk about unless we make the distinction. A function is surjective if its image equals its codomain.

So, for example, g defined above is surjective but f is not. There's no rational number x such that f(x) = sqrt(2).

[trim thicket]

surjective is when each element in the codomain has a corresponding match in the domain, right? this is from memory, im just testing myself

[lethal linden]

Yes. It means for every element b in the codomain there exists an element a in the domain such that f(a) = b.

Another way to say that is the image of f is the whole codomain. And by "another way" I mean that if you write out the definition of im(f) and what it means for two sets to be equal then you will find yourself literally becomes the above sentence ("for all b in the codomain, etc. etc.").

[lethal linden]

Another motivating thing is that you can always construct some "larger" set that your original codomain sits inside.

So imagine we only specify the domain, i.e., say f has domain ℝ and f(x) = x/2. Is this function surjective?

It is if we take the codomain to be just ℝ, but not if we take the codomain to be ℝ∪{'potato'}, i.e., the real numbers plus the string potato. Or not if we take the codomain to be the complex numbers ℂ, if you want to stick with numbers.

The fact that the answer to "Is f surjective?" changes as we change the codomain is a sign we should take the codomain into account up front. In grade school, though, we tend to take all function as having real numbers as output.

In other words, if we want "being surjective" to be a property of the function then the codomain has to be part of the function's definition/specification.

And if/when you learn about ℂ, your attention isn't brought back to these "basic" questions about the definition of a function.

[trim thicket]

wait so we can just like
make up codomains?
so like
if f's domain is real numbers
f is surjective for real numbers
but is not surjective for complex numbers?

[lethal linden]

The better way to think of it is that they're just different functions. A "function" consists of three pieces of information: a rule, a domain, and a codomain.

[trim thicket]

damn wow that sounds like a fire summary
ive never encountered a definition of a function like that
sorry im really new to discrete math

[lethal linden]

This is just "math", nothing about discrete math specifically. You've left The Matrix that is grade school math. 🙂

[trim thicket]

thats funny im actually still in grade school

...i think? high school is a part of grade school right?

although technically my discrete math class is a dual enrollment class, meaning its like college thingy?

ive actually done calculus 2, but i have no idea how rigorous that really was because it was a semester class

the teacher was supposed to teach calculus 3 for the next semester but he quit bc all the students were complaining about him not teaching

[lethal linden]

I see! Well, there you go.

In a world where every function implicitly has a codomain of the real numbers, talking about codomain vs. image would be tricky.

Even the way I remember "domain" being talked about was confusing. You'd get questions like "What's the domain of f(x) = 1/x?" And what was being asked was really "What's the largest subset of the real numbers on which f(x) is defined?"

After all, f(x) = 1/x is also defined if x is a non-zero complex number.

Or something like f(x) = x + x.

Well, that's defined if x is a matrix. Are we taking those into consideration, too?

And you quickly see the need to say upfront, at definition-time, what the domain and codomain are.

[trim thicket]

oh yeah
my question was like
find the domain and codomain of f(x)=sqrt(x)/ln(x)
i think i got it wrong because i defined the domain as all real numbers above 0
and the codomain i defined as all real numbers above e/2 or below 0

[lethal linden]

IMO that's a malformed question.

sqrt(x)/ln(x) is also defined for some complex numbers. Are those part of the domain?

You can also define sqrt(A) and 1/ln(A) for some matrices. So are those matrices part of the domain, too?

[trim thicket]

wow tbh i had a feeling
like, i wasnt gonna include complex numbers, but only because i knew the teacher hadnt really talked about them much

[lethal linden]

Your teacher would probably be happy if you asked "What if x is a complex number? Are those part of the domain?"

If they know the math (and most high school teachers do) then they know this domain-talk papers over some details.

[trim thicket]

so its a malformed question because the domain could really be just anything?

[lethal linden]

Given x is a real number, you can ask: "What is the largest subset of real numbers such that sqrt(x)/ln(x) is defined?"

That's what is being asked with these "What is the domain?" questions.

But that's not how "domain" is used outside of grade school math.

[trim thicket]

i see

[analog horizon]

Hello, if anyone could help me with pretty hard math problem I would be grateful. (help-11 | ferris)

[willow yacht]

Could I define the reflexive property of a relation as:
∀x∀y[ [ (x,y)∈R ] → [ (x,x)∈R ^ (y,y)∈R ] ] ?

[brave rock]

No. You need to refer to the set that the relation is reflexive on. If this were a correct definition, the empty relation would be reflexive on any set.

[willow yacht]

Ok, I just understand what the reflexive property means.

But I have a question (about why the reflexive property was defined as it is)

As I understand, if R⊆A², and we know that R is transitive or symmetric relative to A, then we know that R is still transitive or symmetric relative to any other set X that fulfill R⊆X²

But the definition of reflexive property "∀x∈A[ (x,x)∈R ]" to say that R is reflexive relative to A, prevent that R is reflexive relative to another set that isn't equal to A.

[willow yacht]

And when I think intuitively about the reflexive property, I have in mind the definition that I just give "∀x∀y[ [ (x,y)∈R ] → [ (x,x)∈R ^ (y,y)∈R ] ]", that, R is reflexive "locally" with the elements that participate in R.

So... my question is...

Is there any reason or advantage for why the reflexive property was defined at this way (that should be reflexive between all the elements of the Domain and not just reflexive between the elements that participate in R) ?

[fossil mural]

...honestly i think it's kind of just a "coincidence" that symmetry and transitivity end up not being like that

we generally consider a relation on a set, and which set it's on is conceptually part of the relation, even though you can't infer it from the set-theoretic coding

the same kind of reason as why a function being surjective means that it's surjective on its codomain instead of just on the set of values that it actually takes

and similarly, it turns out that a function being injective can be defined entirely from which ordered pairs it contains, but again, that doesn't really have some deeper meaning, it's just the kind of thing that happens sometimes when you're considering such simple concepts

[languid jacinth]

elp

[willow yacht]

How is "standardly" defined the total property? Because I have seen it as:
∀x,y∈A[ (x,y)∈R or (y,x)∈R ]
But by this way, the greater-than relation couldn't be total, because this definition implies reflexivity and greater-than isn't reflexive.
I have seen a different version such as:
∀x,y∈A[ ( x ≠ y ) --> [ (x,y)∈R or (y,x)∈R ] ]

So, both are "total" but with different surname, or one of both is the "total" and the another is a weak version of totallity?

[lethal linden]

https://en.wikipedia.org/wiki/Total_order#Strict_and_non-strict_total_orders

[willow yacht]

Thanks

[grand totem]

For what it's worth, a relation obeying the latter condition is sometimes referred to as connected

[analog horizon]

Could anyone help me with #help-35 ?

[wind peak]

if i have a binary search tree, say of the numbers 1 to 15, and want to remove a node, how would that work? is there just one way to do it or depending on the algorithm, could the resulting tree be different?

[lethal linden]

Well, given N values there are many binary search trees containing those N values. If "removing a node" means I give you a BST and a value and you give me a new BST without that value (with no other considerations) then there are many possible BSTs you could give me.

[lethal linden]

Like, you take this tree:

    10
  5    15
3   7

You ask me to "remove 15" and I give you back

3
  5
    7
      10

That's still a BST and it contains all the original values except 15.

Now, you could ask for a BST with as few nodes changed as possible or some other constraint.

There's a "usual way" in which we mean delete, but when you ask "is there only one way" you have to say more about what counts as "a way"

[wind peak]

hmm okay then like a binary search tree that mantains the same structure? idk how to explain it, i'll show an example

              8
           /     \
         4         12
       /  \       /   \
     2     6   10    14
    / \   / \   / \   / \
   1   3 5   7 9  11 13 15

[lethal linden]

Sure

[wind peak]

Like i want to mantain the "inorder" structure (I think this is how its called?)

[lethal linden]

I'm assuming you know the "standard" way to delete from a binary search tree? Wikipedia has a description.

[wind peak]

mm i'll take a look

thanks

[lethal linden]

The idea is you recursively remove it from the subtree the value must belong to. Say you find a node with the value.

1. If that node has only one child, replace the node with that child (so the node's parent points to the node's child instead)
2. If the node has two children, remove the largest node from the left subtree (or smallest from the right, both work) and replace the node with it

So, already with (2) there's an arbitrary choice.

[lethal linden]

For example, if I wanted to remove 12 from this tree:

              8
           /     \
         4         12
       /  \       /   \
     2     6   10    14
    / \   / \   / \   / \
   1   3 5   7 9  11 13 15

I could give you:

              8
          /       \
         4         13
       /  \       /   \
     2     6    10     14
    / \   / \   / \     \
   1   3 5   7 9  11    15

Or I could give you:

              8
          /       \
         4         11
       /  \       /   \
     2     6    10    14
    / \   / \   /     / \
   1   3 5   7 9     13 15

Which one is "right"?

[wind peak]

oh i see

[weary tiger]

I have a question about signal processing, essentially I just want to know the right term(s) to look up because I am fine doing research on my own but I really don't know where to start with this. I know that there are connections here with regressions and edge detection, but the specific problem I am working on involves finding curves to match a discrete binary input. I am positive I have seen a process (or perhaps multiple) that produce results like this, which I did by hand to demonstrate what I am trying to get at here. I'll need curves I can do computations with since this is actually a two dimensional version of a 3d problem I am trying to solve involving generating normal surfaces on a voxel grid, which I am positive involves the gradient operator in some way but again I am just a little over my head here. Any direction would be much appreciated.

[willow yacht]

Why does it seem that the definitions of properties in order theory give preference to the 'greater than or equal to' relation (≥) over the 'greater than' relation (>)? 'Greater than or equal to' can satisfy reflexivity, transitivity, antisymmetry, and totality. Meanwhile, 'greater than' is not even reflexive and therefore cannot be total, requiring a special definition of totality as strict totality to qualify. This causes me some conflict, as 'greater than' feels more intuitive than 'greater than or equal to,' which I perceive as a disjunctive composition of 'greater than' and 'equal to.' Is this a historical coincidence due to how order theory developed, or is there a practical reason why these properties were defined this way?

[brave rock]

Some things get more convenient to state if you use \leq. For example, the definition of a maximum or minimum element doesn't require the caveat of inequality.

That's it really.

[analog horizon]

Still can't figure out harder part ...

[lethal linden]

A square with side length 1 contains a figure in which the distance between any two points is not 1/1000. Show that its area is less than 0.34. Or maybe you can show that it is less than 0.29?

When you say "is not 1/1000" do you mean "is not greater than 1/1000"?

[analog horizon]

@lethal linden no, is not exacly 1/1000

[willow yacht]

What is the difference between "Partial Ordering Relation" and a "Partial Ordering Set (POSET)? And, these differences are really important?

[brave rock]

A partially ordered set is a set which we think of as having an associated partial ordering relation

They are different objects in the same way that a group operation is not a group, or (less mathematically) the engine is not a car.

You can recover the set from the relation.

[willow yacht]

In which case we would have just the relation R alone without its relation S? Because to know that R is a relation of S, we have to know R⊆S^2. Or more deeply, to know that R is reflexive we have to know that ∀x[ x∈S --> (x,x)∈R ].

Or are there another names and symbolizations for another kinds of relations, like the equivalence relation (for example, the equivalence relation and the equivalence set)?

[brave rock]

In which case we would have just the relation R alone without its relation S?
Do you mean the set S? We can consider a relation alone whenever we like. In practice we talk about partially ordered sets, though.

Because to know that R is a relation of S, [...] Or more deeply, to know that R is reflexive we have to know that ∀x[ x∈S --> (x,x)∈S ].
In the case of posets, this is false. We always know the relation is reflexive, so we can recover the set S = {x | (x, x) in R}.

This is what I meant when I said you can recover the set from the relation

There are indeed names for sets equipped with other relations, but they're not used nearly as often as posets. The word for a set equipped with an equivalence relation is a setoid, but this is quite obscure terminology and I don't suggest using it.

[weary tiger]

hey for anyone wondering this for future reference, the word is isosurface extraction, and as I suspected it is a very complicated and difficult problem. but that is the relevant search term.

[willow yacht]

Sorry, I tried to write "(x,x)∈R"

[willow yacht]

How exactly Boolean Algebra is a lattice?

[grand totem]

The order can be recovered as a ≤ b iff a ∧ b = a or as a ≤ b iff a ∨ b = b

[willow yacht]

Nonono, but my question is... WHAT EXACTLY IS THE LATTICE HERE? XD

Algebra (in this case Boolean) could be a mathematical structure?!??

[grand totem]

Do you know what a lattice is?

[willow yacht]

It's a poset that is a meet semilattice and a join semilattice

But, how a "subject" as algebra could be a lattice?

XD

It sounds very strange

[grand totem]

A lattice in the order theoretic sense (a poset with finite meets and joins) gives rise to a lattice in the algebraic sense (a set equipped with two constants and two binary operations subject to some identities) by just taking the underlying set to be the underlying set of the order theoretic lattice, the constants and operations become top/bottom and meet/join respectively and the identities are then rather easily verified.
What my initial message was hinting at is that you can also go the other way, i.e. turn a lattice in the algebraic sense into an order theoretic one. And obviously the first step would be to ask how one recovers the order just from the operations of the given (algebraic) lattice

[blazing lodge]

does the set of all sets contain itself

[cerulean wind]

this is russel’s paradox

[vestal bronze]

no lol

[odd heart]

The main difficulty is that a set of all sets doesn't exist; and in general modern set theory is built so that a set can never be its own element, because nothing good comes of it.

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

[neon harbor]

Algebra is not just a subject, it's also an algebraic structure consisting of two operations: https://en.m.wikipedia.org/wiki/Boolean_algebra_(structure) and https://en.m.wikipedia.org/wiki/Algebra_over_a_field

[odd heart]

And also https://en.wikipedia.org/wiki/Field_of_sets (often referred to as an algebra of sets)

Although I think those can be interpreted as Boolean algebras

[lethal linden]

https://en.wikipedia.org/wiki/Algebra_(disambiguation)

[willow yacht]

What would be an intuitive way to explain what a Lattice is?

[lethal linden]

A person's "intuition" depends highly on their prior knowledge and experience.

A lattice being a poset where any pair of elements have both a supremum and infimum seems about as straightforward as you're going to get. Any "explanation" will take no less effort than making sure the student is clear on what the technical terms in that definition mean (poset, sup, inf, etc).

Draw some Hasse-type diagrams and give 2-3 examples using different posets. If that doesn't motivate the generalization then the student probably need more exposure to concrete instances.

[willow yacht]

Well, for example, in Geometry, I intuitively see the slope as the level of inclination of a line, or, if I want to be more precise, the ratio of the inclination of the axes (more intuitively, how many units in 'y' there are for how many units in 'x' to find the next point belonging to the line). But in the formal definition, it appears as the tangent of the angle of inclination of the line, which I’m not saying isn’t explanatory, but at first glance, it doesn’t give me enough intuition to understand why that definition exists or what object or property it’s supposed to be describing. That’s why I was asking if there’s an intuitive idea of what a lattice is that justifies the formal definition.

[brave rock]

The intuition for a lattice is you use them a lot and you prove theorems about them and then it makes sense.

[lethal linden]

Sure, you're familiar with lines and the things you can ask and answer about them, ways to manipulate them, etc.

Then when you encounter another characterization or representation — not even necessarily a more abstract one — you can connect the features of this new representation to the features of representations you're more familiar with.

For example, you say you "see the slope as the level of inclination of a line", but what you mean is when you were first introduced to slope intercept form y = mx + b you were taught how to connect the parameter m to something you more more familiar with.

But you could have just as easily been taught the "intercept form" first: x/x0 + y/y0 = 1 and then you'd "see" x0 and y0 as the points where the line intersects the x-axis and y-axis, respectively.

[lethal linden]

So...if the abstract representation isn't "intuitive" then it means it (probably) doesn't track anything that's more familiar to you (or it does but you don't see how to make the connection).

For example, the integers with divisibility form a partial order (saying a <= b if a divides b). There, the supremum is the LCM and the infimum is the GCD.

The power set with set inclusion form a partial order. The sup is the union and the inf is the intersection.

You would say, "Well, given a partial order, you can always draw a diagram where there's an edge from a to b if a <= b. Then a lattice is where there's always diamond shape like this for any two things a and b"

[willow yacht]

Which bibliography do you recommend to study formally this order theory topics?

[deft lynx]

Does questions on cantor's diagonalization theorem to prove uncountable sets fit here ?

[brave rock]

I'd suggest just asking your question

If it's not appropriate, people will tell you

[deft lynx]

$A = {f \in \mathbb{N}^{\mathbb{N}} : \forall n \in \mathbb{N}, |f(n+1)-f(n)|=1}$ prove that A is uncountable \
Proof: assume A is countable therefore there exists a function from A to $\mathbb{N}$ that's injective, by theorem there exists a $f: \mathbb{N} \rightarrow A$ that is surjective express $f(n)=f_n$\ define a new function: $g(n)=-f_n(n)$

I wanted to ask does g(n)=-f_n(n) work ?

[vital dew]

prograce

[deft lynx]

To prove that g(n) is in A however g(n)!=f(n) for all n

Nvm it doesn't

[lethal linden]

You're dealing with functions from ℕ to ℕ, so -f_n(n) doesn't make sense in general.

Hint: ||Every such f is uniquely determined by a choice for each natural number k. That is, for a given k, either f(k+1) = f(k) + 1 or f(k+1) = f(k) - 1||

[quick folio]

it doesn't seem true?

[clever sail]

yeah it's wrong lmao

i assume they want a counterexample

[quick folio]

it's not that hard to find one

[clever sail]

right

[vapid chasm]

how does rsa cryptography work in laymans terms

theres like a multiple of two primes and you subtract one from each prime for some reason and theres a mod in there

[quick folio]

The main principle at work in RSA is the factoring problem

I.e. multiplying numbers is really easy, but finding the factors of a number is really hard

So the RSA algorithm is just using that

[agile magnet]

"in layman's terms" is kind of vague so the best I can do is point you at this PDF: https://math.mit.edu/research/highschool/primes/circle/documents/2024/Honglin.pdf

it starts from the basic number theory needed (starting from primes, divisibility, Euclid's division algorithm)

so look at that PDF and then if you have more specific questions from that, ask here

[dawn hatch]

x = y = 1.1 works as a counterexample

[pliant horizon]

if we had adjacency matrices $M_R$ and $M_S$ we have

$M_SM_R=M_{R\circ S}$?

[vital dew]

eigentaylor (STfFGMOaPID)

[pliant horizon]

at least, if we do the sort of boolean thing where we turn all nonzero entries to a 1

is that right?

i thought it'd be M(SoR) but it seems to be MSMR=M(RoS). just need to confirm that

[lethal linden]

What does $R \circ S$ mean in the context of graphs?

[vital dew]

Cufflink

[lethal linden]

(If it's graph composition then this can't possible be right. The number of vertices is wrong.)

[muted basin]

hey I'm trying to solve this with proofs

I'm stuck at literally just declaring hypotheses

asked chatgpt (which probably is wrong) and it introduced A as an assumption by itself

we JUST started proofs in my class but my prof never did anything like that

and it intuitively feels wrong to me

is this even an option or is there something I'm just not seeing

I have some ideas of manipulating them but nothing that seems as if it would progress this problem

[sharp rose]

What are you proving

about this formula

Oh I didn't see the implication on the far right

Okay where are you stuck

[pliant horizon]

iirc (a,b) is in RoS if there is some x such that
(a,x) is in S and (x,b) is in R.

[lethal linden]

So S and R are relations on the same set?

[pliant horizon]

yes

adjacency matrices so they're also square

[lethal linden]

Sure, so you're treating S and R as directed graphs on the same underlying vertex set.

[pliant horizon]

yeah

[lethal linden]

(M_S*M_R)_{ij} should be the number of paths of length 2 from vertex i to vertex j such that the first edge comes from S and the second edge comes from R.

In general, if A is the adjacency matrix of a graph then the entries of A^n count the number of paths of length n between vertices.

[pliant horizon]

if $(M_SM_R){ij}>0$, then $\sum (M_S){ik}(M_R){kj}>0$ implies there is some $k$ for which $(M_S){ik}=(M_R)_{kj}=1$. then $(i,k)\in S$ and $(k,j)\in R$, so $(i,j)\in R\circ S$

[vital dew]

eigentaylor (STfFGMOaPID)

[pliant horizon]

is that logic incorrect?

[lethal linden]

Depends on your definition of composition of relations. Just check that it matches. Folks define it both ways (left-to-right and right-to-left)

[muted basin]

i used modus ponens on B and B -> C to get C

from there it says the next step is B^C is made from conjuction of B and C but

wasnt B used up to derive C

[sharp rose]

You still have B

B can infer more than one thing

[muted basin]

but we removed B->C

why not B as well

i might just be thinking about all of this the wrong way

[sharp rose]

So we start by assuming A, right? B is then given by (A->B)

therefore B is always true when we assume A, so we can use the truth of B to first infer C then we can use it to infer D

You said you already got C so now you can just use (B -> (C -> D)) to infer D at last

B is still true because we assumed A

C is also true when we assume A

[muted basin]

just realized i gave wrong work

but same principle between the two problems i used

im getting lost in the sauce with the derivations

i guess mathematically im inclined to believe when I see that given A, A->B then you can derive B that all of the antecedent there is turned into B algebraically

[sharp rose]

where are you doing that here

[sharp rose]

this? wdym

[muted basin]

for 20. that i sent my confusion was on using A as a temporary assumption to be discharged

let me send both

the thing i replied to u with by mistake was referring to step 5 in 10.

used B twice in two steps

[sharp rose]

Looks fine

whats the issue

[muted basin]

i mean i know the solution is right now but im confused on why were allowed to use B twice

or any variable more than once

modus ponens states from P, P->Q we derive Q

[sharp rose]

Yes you can use modus ponens on the same propositions more than once

[muted basin]

So is it more like, if we have B and also B->C, we can add on C but still have the previous two, but I don’t need to use the other part?

I think I’m thinking about this stuff way to formulaic and its causing issues

[sharp rose]

Yes you can refer to any formulas produced, even if they were used already

• Whenever it rains, the street is wet. (A -> B)
• Whenever it rains, the sidewalk is wet. (A -> C)
• It is raining. (A)

We can conclude both B and C given A (we know that both the street and the sidewalk are wet). This is "reusing" modus ponens on A

[muted basin]

okay that makes a bit more sense

i should throw my preconceptions out the window

i have one more problem im trying to solve

[sharp rose]

In algebra you can also refer to any formulas you had earlier, more than once

[muted basin]

im trying to prove that P -> P^P

i could turn it into P’ v P ^ P

from there though i am unsure as to what i can do with the rules we are given (basic equivalence and then modus ponens, modus tollens, conjuct, simplification, and addition)

I could double negate some stuff or maybe use demorgans law to expand

but it just leaves me with more P's than less

if i continue past that

or am i setting up my steps wrong ? we haven't had any ^ or v statements on the conclusion side in practice yet, only implications

[sharp rose]

you can use simp to derive just P (from P^P)

[muted basin]

that might be where i am confused, are we allowed to use the conclusion we're searching for in steps?

my prof was exclusively having us use stuff from what is left of the final implication symbol

and the right being what our final step should be

[sharp rose]

I don't completely understand

[muted basin]

like in the previous problems, we're trying to achieve A -> C for a conclusion into 10, so we don't declare A -> C as a hypothesis

or in 20 we're looking for A' but we don't declare it as a hypothesis

to use simplifcation on P^P it would have to be a hypothesis from my understanding

but the only hypothesis we're given is just P

[sharp rose]

You can have P be the hypothesis

then get P^P (mp)

then once you derive P you can discharge

[fossil mural]

...what?

[muted basin]

how exactly does discharging work? I used it in 20 but I've only used it in a pattern like fashion

[fossil mural]

the problem is to prove "P -> P ^ P"

[muted basin]

I have temp A, I get conclusion B, then discharge A -> B

[sharp rose]

I'm not familiar with how your professor taught this, i'm just trying to mirror how it works as i see in your previous problems

[muted basin]

but prof has not really covered what it means other than using it in a single example like that

[sharp rose]

Oh my bad