discrete-math

[snow sleet]

okay, but what is ur even number that is being written as the sum of two primes?

it isn't 2(x+y)

[jagged grove]

any number mulltiplied by 2 is even?

[snow sleet]

but remember, that even number must be written as the sum of two primes

[jagged grove]

ohh

[snow sleet]

which number do u have here are u stating that it is the sum of two primes

[jagged grove]

yeah ur right

[snow sleet]

2(x+y)>2x is not necessary

ur on the right track, just need to make it a bit more clear

[deft vigil]

Hi, can I ask a question about something else not sure if I'm interrupting...

[jagged grove]

go ahead ill take a while writing this

[snow sleet]

u can ask

[deft vigil]

So I'm trying to solve the question here and I've been stuck for a few days.

Basically:

1. I figured out the one case where it is not a connected graph, in that case it's the union of K4 and K4
2. It can't be bipartite, since that would mean it needs to be the complete bipartite graph K4,4 since we know that a graph that's bipartite and also regular has |A| = |B|
3. Current approach: trying to find all connected graphs that are 3-regular (cubic) with degree 3 with varying girths, is this the right approach or am I missing something here? I've drawn out graphs with girth=3, girth=4, girth=5 in the the picture, and will draw out grith=7 soon, are these the only cases?

[snow sleet]

Hint: ||think about 10=5+5...we have found primes x,y for which x+y=10. So 10=5+5 is certainly a sum of two primes.||

[jagged grove]

im about to finish

[snow sleet]

any graph theorists here who can help @deft vigil ?

graph theory was not a class I did well in so don't wanna send u down a rabbit hole lol

[snow sleet]

,rotate

[snow sleet]

nice! I'm glad u made use of the fact that those two primes in the sum need not be distinct

[jagged grove]

also

i think i understand the graph problem

give me a sec

[snow sleet]

lemme post my proof. We should really have a graph theory channel tbh

[jagged grove]

u did the graph already?

[snow sleet]

no

[jagged grove]

ahh

[snow sleet]

the problem I assigned u lolll

[jagged grove]

ok

[snow sleet]

and assigned myself

[jagged grove]

why are u using the injectivity?

also is P the set of positive reals?

or something

[snow sleet]

I have shown that given one of infinitely primes p, my function spits out distinct p+p which are even and greater than 2

[jagged grove]

ahh

yes

[snow sleet]

I meant it as the set of Primes

[jagged grove]

they dont repeat

[snow sleet]

yes

[jagged grove]

like there is no such preimage

[snow sleet]

exactly

[jagged grove]

that has the same image

u see i did this years ago

i just need to get the rust out

not this exactly

[snow sleet]

we can assume there are infintely many primes p, but if my function forced infinitely many of those primes to give the same value f(p), then I wouldn't have shown there are infintely many even numbers greater than two that can be written as the sum of two primes

[snow sleet]

short and sweet

[jagged grove]

@deft vigil do they mean by 3 regulars that all vertices have 3 neighboors?

[snow sleet]

imma head to sleep @jagged grove awesome working with u on some problems

[jagged grove]

thx bro

[snow sleet]

<@&286206848099549185> @deft vigil needs some help^. Graph theory is not a subject I'm strong in so I don't wanna send him down a rabbit hole. Hoping someone can help him

[deft vigil]

Yes

[jagged grove]

what their asking is if u can biject the graphs

thats what they mean by isomorphism

basically see for which of those you can set a function that has an inverse

[deft vigil]

Hmm yeah I guess I know what the question is asking

Just wondering if the approach I used to solve this would be correct

Or wrong

[jagged grove]

a graph is composed of a triplet

the set of edges

the set of vertices

one sec

lets just use 2

there is one that uses 3 but it's fine

so u have a graph with vertices in a set V and edges in set E

and the edges are equal to a set containing the two vertices that make the edge

You need to take this construct your graphs

and take a counter example in the ones that are not bijective

[rigid oriole]

(nope lol)

[jagged grove]

thats not how it goes?

[rigid oriole]

nope, i cannot assist with graph theory

[jagged grove]

ahh ok

THX anyway

[jolly ledge]

so...I have no idea how to get started on 22(a). I'm not getting the hint.

oh and the theorem and the exercise don't reveal much, they're just there for the sake of saying congurence is an equivalence relation

[grand totem]

21a lets you conclude immediately after showing that the function f : N -> N/R that sends an x in N to [x²] is compatible with R.

[ivory badge]

R sure looks like mod 5

But yeah just show 21 and apply it to the particular thing

[jolly ledge]

ah

[waxen vale]

oh boy math

[jolly ledge]

wait but... what 21a showed is for function h: N/R -> N
Well... ig I just send an element in the equiv class to it's square and make it back into an equiv class

[grand totem]

Exercise 21 talks about two sets (A and B). For exercise 22 you let A = N and B = N/R.

[jolly ledge]

o h .

my eyes.

ok not my eyes my brain

[jolly ledge]

I... don't even know how this is important or how it "works", but I managed to just bash its properties to get through the equivalence relations questions relating to it.
later on the exercises had us show that the intersection of preorder with its inverse is an equivalence relation and its compatible with said preorder

.... the naming doesn't seem to be a coincidence, especially when the exercises get me to show almost identical things, but I can't see any correlation between the two. Is there any at all? googling didn't get me far . I tried subbing in some values with the fact that function are a special type of relation in mind but nothing really worked out.

[still isle]

What are the criterias for a well-defined function?

[coral parcel]

It's a bit of an abuse of terminology -- when we say "f is well-defined" what we really mean is "the definition that purported to define f actually manages to define something at all".
So if someone says "f is not well-defined" they're really saying "I don't even know what you mean when you say f".

The typical situation where this crops up is if we're talking about a function whose input must be a set and we try do define it as

f(X) = [something involving x] where x is some element of X
This only defines a function if you can argue that "[something involving x]" gives you the same result no matter which element of X you picked.

For example in modular arithmetic we often define addition of residue classes by

[residue class of x] + [residue class of y] = [residue class of x+y]
The problem here is that the residue class of x is also the residue class of many other numbers, and for the definition to make sense we need to be sure that "[residue class of x+y]" ends up being the same even if the choose a different one of them to add to y.

[little prism]

two other things that sometimes could go wrong is that f:A->B is not actually defined for all a in A or that for some a, f(a) is not actually in B. for example f:R->R, f(x)=1/x is not well-defined. (of course most of the time this is just a technicality and can be fixed by changing A and B appropriately)

[torn nymph]

hey can someone help me with a question from my recursion chapter?

I'm having trouble with part b

i don't know how to get from part a to part b

this is what i have for part a

this is the question

[snow sleet]

Troposphere already answered this but it means that for any a,b in the domain, a=b implies f(a)=f(b). Well defined is synonymous with function a lot of times. It means each element in the domain gets assigned to a unique element in the codomain.

[little prism]

the first thing would mean constant function

[snow sleet]

I forgot to add something lol^

[static bone]

Hello. I have no clue how to get r.

Im so close to completing my homework and its a section the teacher didn't go over

[gusty swallow]

it's just arithmetic, isolate r

[silk void]

any book recommendations or anything for graph theory ??

[jagged grove]

try different books

@silk void lets go to book recommendations

ill give u a few titles

[silk void]

okk

[nocturne grove]

What does that symbol mean

I forgot

[plucky wedge]

XOR(Exclusive OR) it basically means that if both truth values are different than it's true if they are the same it's false

[nocturne grove]

Oh I see, thank you

[plucky wedge]

Something more visual

[nocturne grove]

Ok so if they are the same, no matter what it will always be false, but if they are different values then it is true?

Unlike normal or

I see

Thank you for the help and the clear example too

[plucky wedge]

yeah

[warm quest]

Hi friends, I really wanted to get a sanity check on this problem.

Since every student is doing at least one problem, this is the same as distributing the 6 problems again.

We have 4 students, so we have 4^6 different ways we can distribute the problems.

[oak night]

How many of the 9000 four-digit integers 1000, 1001, 1002,...,9998, 9999 have four distinct digits that are either non-decreasing (as in 1347, 1226, and 7778) or non-increasing (as in 6421, 6622, and 9888)?

the final answer from the book is [2 (12C4) - 9]+[12C3-1]=1200

i dont understand

[coral parcel]

The question you've typed seems to be a mixture of 15a and 15b. You write that you want four distinct digits, but several of your examples don't have distinct digits.

In order to get [2 (12C4) - 9]+[12C3-1] to make sense, I think you have to be answering 15b, where the digits are not required to be distinct.

[oak night]

oh sorry, yes 15b solution is [2 (12C4) - 9]+[12C3-1] = 1200, but i dont understand how to get it

i got the answer for 15 a already, and i tried 15b, but when i check the solution, i am wrong

[coral parcel]

I think there must be a stars-and-bars argument somewhere, with bells and whistles to correct for (a) strings that are counted twice (e.g. 5555 would naively be counted as both the increasing and decreasing version of "four 5s" (b) the fact that the strings cannot start with 0.
But I'm not awake enough to map that general idea precisely to the expression you have.

[snow sleet]

out of curiousity, what did u get for 15a

[snow sleet]

I'm getting 336 for 15a

[snow sleet]

For 15b, I got 1200 and did this:

the ascending cases that are non decreasing and don't include constant things like 1111, 5555, ..., 9999, is

$-9+\sum_{i=3}^{11}\binom{i}{3}$

[vital dew]

logician

[snow sleet]

For the non increasing cases that DO include constant things like 1111,2222,3333,...,9999 I got

$-1+\sum_{i=3}^{12}\binom{i}{3}$ since we can have 1000 but we can't have 0000 (that's where the -1 is coming from)

[vital dew]

logician

[snow sleet]

thus the total is

,w -10+(Sum[Binomial[i,3],{i,3,12}])+(Sum[Binomial[i,3],{i,3,11}])

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

@oak night

For 15a, I did:

for the ascending cases I got

$\sum_{i=3}^8\binom{i}{3}$

[vital dew]

logician

[snow sleet]

I fixed the leftmost digit starting at 1, and going all the way up to 6

For the descending cases I got:

$\sum_{i=1}^9\binom{i}{3}$

[vital dew]

logician

[snow sleet]

by left most digit starting at 9 and going down to 3 since 3210 is the last possible descending case we could have...can't go any lower

anyway, this makes the total for 15a:

,w (Sum[Binomial[i,3],{i,3,8}])+(Sum[Binomial[i,3],{i,3,9}])

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

ping me if this still doesn't make sense or if you're answer differed from mine on 15a

[regal gate]

this is false right

my counterexample: divide the 10 vertices into three sets of 3,3,4 vertices. Join each vertex from one set with every vertex from the other two sets

that gives 33 edges

and no squares

in fact, I think that is the actual upper bound (of the number of edges of a square-free graph on 10 vertices)

[little prism]

why should that not have squares

take two points from the first two groups each

[regal gate]

lol ye

ty

[regal gate]

T_(n,r) is partitioning the n vertices into r sets of [n/r] vertices and joining vertices in different sets

why is that probability 1/(n-d(v))

like is it obvious

I remember in the youtube lecture it was just stated lol

so fix the vertex v, then the arrangement should be of the form (neigbors of v) v (whatever). Say there are k neighbors in before v, so we choose (d(v) C k), then order them, and order the remaining n-k-1 vertices, so that gives a total of
[
\sum_{k=0}^{d(v)} \binom{d(v)}{k}k!(n-k-1)!
]
possible configurations?

[vital dew]

Croqueta

[regal gate]

oh wait

that is right

this but with m=d(v) mmh

[jagged grove]

what book is this?

[regal gate]

Yufei Zhao's lecture notes

"graph theory and additive combinatorics"

[jagged grove]

bro discrete math books

ohh

this isnt discrete

nevermind

[regal gate]

eh

[jagged grove]

i mean

this sorta thing wouldnt be covered in a standard

at least not with that notation

[regal gate]

what notation?

I think all the notation used is standard

[jagged grove]

the whole e(G) < e(T_n,r)

like i havent seen that theorem or maybe im missing the notation

cause i have read a bunch of discrete math books

[regal gate]

you dont have to be mr Einstein to figure out the notation

[jagged grove]

what does he mean by K_n+1 free?

like the degree of the vertexs?

[regal gate]

no subgraph is K_(r+1)

[jagged grove]

ahh u mena to say the number of vertices isnt greater than the parent

or something along those lines?

[regal gate]

no

so you say a graph G is triangle free if it contains no triangles, for example

and given a graph H, you say G is H free if it doesn't contain H as a subgraph

[jagged grove]

ahh

[regal gate]

for example, every bipartite graph is triangle free

[jagged grove]

its a way of saying that u dont have the subgraph withouth having to specify X\A where X is the vertices of graph H and G are the vertices of graph G

and u know

its correspondent edges

?

[regal gate]

I'm not sure why this is confusing for you, there is nothing tricky here

given a graph G, consider the set of all its subgraphs. Then we say G is H free if no subgraph of G is isomorphic to H

[jagged grove]

yeah i got that part

i was just trying to rephrase it

and by isomorphic u mean that the graph H has no function which is bijective to any subgraph in G

[regal gate]

to refresh standard graph theory terminology I always go to Diestel's book

ctrl+F "isomorph" and it should pop the definition

[jagged grove]

i use schaum's but mine is in spanish

[regal gate]

where are you from

[jagged grove]

costa rica

[regal gate]

ah, I'm from Spain 🙂

[jagged grove]

i do have books in english

oye tio

q si no me lo dices

no me doy cuenta

lol

[regal gate]

:p

[jagged grove]

weird it only requires one to one

but it sorta makes sense since a edge can have more than one pre image

[regal gate]

no, "correspondencia uno a uno" ="one to one correspondence" implies both injectivity and surjectivity

[jagged grove]

lol

but in english they say one to one

and onto

[regal gate]

no

[jagged grove]

and its completely different meaning

[regal gate]

they also say "one to one correspondence" all the time, and so do I

[jagged grove]

when i say injectivity some people ask me wdym

but maybe thats where the confusion arise

tbf this was from a conv i was having with a CS guy that only does software

so

one to one correspondence means bijective then

got it

[regal gate]

is this folklore? I proved it

but had never seen it

[jagged grove]

im gonna have a look at the book and see

did u use induction?

cause thats what i would have used

[regal gate]

yes, but only after I moved some things around

[jagged grove]

show me

[regal gate]

because then it is not clear on what to induct

[jagged grove]

i inducted proving the cardinality of a set of functions equals a given constant

i think i can manage

if not i have an idea of who to ask

[regal gate]

well first of all, the equality is equivalent to $\sum_{k=0}^m \frac{m!(n-k-1)!}{n!(m-k)!}=\frac{1}{n-m}$

[vital dew]

Croqueta

[regal gate]

or just $\sum_{k=0}^m \frac{(n-k)!}{(m-k)!}= \frac{(n+1)!}{m!(n+1-m)}$

[vital dew]

Croqueta

[regal gate]

but the left is the same as $\sum_{k=0}^m \frac{(n-m+k)!}{k!}$, and now you make the substitution $n-m=r$

[vital dew]

Croqueta

[regal gate]

so that you just have to show $\sum_{k=0}^m \frac{(r+k)!}{k!}=\frac{(r+m+1)!}{m!(r+1)}$

[vital dew]

Croqueta

[regal gate]

for r>=0

and you can induct on m now, with r fixed

[jagged grove]

i would start by making the simplifications more explicit

[jagged grove]

for this in particular

[jagged grove]

is this supposed to be the binomial coefficient notation?

[regal gate]

yes

[jagged grove]

ohh ok i was about to post

lol

i get the problem

give me like an hour so i can go through it in paper

and eat

k?

[jagged grove]

ok lets give this a try

[jagged grove]

so how do u go from this

[jagged grove]

to this

?

@regal gate

u there?

[honest mantle]

Need help w these 4

I got the first 2 right on number 20 but confused for the others

10*

[regal gate]

just changed n by n+1

there is really no need to, but I preffered to not have a -1

and then multiply by (n+1)!/m! on both sides

[jagged grove]

nope i dont see how u can get to that expression

also ur supposed to change to n+1 when u have proven that this holds for n = 1

[frail flare]

Is it standard to use an arrow with a line through it to convey "Does not necessarily imply"? If it is not standard, does it have any precedence? Or should one simply state their proposition in a more elegant way

By this I mean specifically the case that, A could imply B, but not in all cases. Such as ∃x1,x2(x1 > 0 ^ x2 > 0 ^ (x1-x2 <= 0 V x2-x1 <= 0))

[nocturne grove]

@snow sleet its here no way

i think e is correct

thats the only one

idk

i need some more explanation and help on this

@faint sphinx could you help?

[fallow dune]

Can anyone tell me the proof for this theorem, the product of any two consecutive integers is even, but just the case where the first integer is odd

[jagged grove]

e is correct

[nocturne grove]

is that the only one?

[faint sphinx]

There's another one

[jagged grove]

there is

can i give it to him?

[nocturne grove]

so a tautology is when its always true

[faint sphinx]

Famously named after someone.

[nocturne grove]

uh i wanna try to get it

lemme look again

[faint sphinx]

There are a few that it obviously cannot be. For example, f) is never true. So you should be able to rule out most of the rest

[nocturne grove]

is d correct

[jagged grove]

yes

[nocturne grove]

yeah that one was tricky

[jagged grove]

logical equivalence

they just changed the term

but its the same term

[nocturne grove]

yeah

[faint sphinx]

Also please don't ping specific people just because they helped with previous questions

[nocturne grove]

oh ok sorry

[jagged grove]

@faint sphinx can u check the induction that was posted earlier

?

[faint sphinx]

Also, these are De Morgan's laws, which is what I was referencing

[faint sphinx]

which one

[jagged grove]

here

start from there

[nocturne grove]

can you say that a tautology is also satisfiable?

i think i can say it like that

[jagged grove]

a tautology is always true

[faint sphinx]

too many factorialz for me I don't like numbers

[nocturne grove]

yeah, and a satisfiable proposition is true for at least 1 row on the truth table right?

[jagged grove]

but is my reasoning correct?

[jagged grove]

yes

[nocturne grove]

so cant you say that a tautology is also satisfiable?

[jagged grove]

well yes

cause in all its possible truth values

[nocturne grove]

so i can say all this no?

[jagged grove]

its true

[nocturne grove]

yeah

[nocturne grove]

well i wanna checkmark all of them

cause i think that would be right

[jagged grove]

no

check again

[nocturne grove]

wait is f wrong?

[jagged grove]

yes

going off

my head hurts

[nocturne grove]

ok hope you feel better

isnt this all true ?

idk ab the 1st one actually

that might be false

[nocturne grove]

Isn't a correct

since if and only if p then q, it just if not q then not p which is the same as if q then p

thats the only one that makes sense

[snow sleet]

It looks something like this:

Given an integer $k$, set $n=2k+1$. Then $n(n-1)=(2k+1)(2k)=2(2k^2+k)$ and $n(n+1)=(2k+1)(2k+2)=2\left((k+1)(2k+1)\right)$, implying $2|n(n-1)$ and $2|n(n+1)$. Thus $n(n-1)$ and $n(n+1)$ are even.

[jagged grove]

a is correct

[vital dew]

logician

[nocturne grove]

figured this out, I think it T T F

cause first two, you can do truth table and for hte third logical equivalence must give the sme result for both propositions

[snow sleet]

Someone already sorta stated this, and I don't mean to sound rude, but unless I was helping you on some problem and asked u to ping me when u got back online to chat about that same problem or if you needed any further assistance with that problem, please don't ping me. There are other ppl here who would be more than happy to help...again, don't ping them directly right when u post a new problem lol

[nocturne grove]

yeah thats on me, sorry about that again

[snow sleet]

all good u didn't know

[nocturne grove]

when you have a p implies q negation

i get the first one

but not really the 2nd option

i was stuck on that and i searched it up

would like to know the reasoning if i could

[snow sleet]

one way to check is to simply look at the truth tables. It's only 4 rows in that truth table so very easy to check that way

[nocturne grove]

ok let me do that

[snow sleet]

'and' and 'but' are synonymous here as well

d is just a more informal way of saying b

[nocturne grove]

so would that be correct as well?

[snow sleet]

yup should be

[nocturne grove]

ok then im done

i realized i made an error on my previous attempt when doing a logical equivalences question but fixed it so its all good

i feel like i am getting better at understanding the concepts

but still bad at applying it

prob just need more practice

[snow sleet]

we're bad at applying concepts until we aren't anymore, right? just takes practice

[nocturne grove]

true

well i somehow got a lower mark than my last attempt

thats dumb

i thought i fixed everything

happens ig

[mighty dust]

Three sisters, Anne, Charlotte, and Emily, are experts in logical deduction. Their brother, Patrick, tapes a piece of paper to each sister's forehead on which is written a positive integer. Patrick informs them that of the three numbers on the sisters' foreheads, one is the sum of the other two. Anne says, "I don't know what number is on my forehead." Charlotte (correctly) says, "The number on my forehead is 21." What are the numbers on Anne and Emily's foreheads? Explain.

I’ve been wrestling with this for a while

Cannot get it at all

[thorny hollow]

Hello

I am learning discrete mathematics and things about relations rn

Could someone give me some example in question a?

I don't know what he really wants here and this book has no solutions page 😭

What I thought of was,

It has the relation of reflexive as every number is divisible by himself

The "b" one would have a relation of simmetry?

"x has a relation R of being relatively prime with y,"

this would also work with "y has a relation R of being relatively prime with x"

[faint sphinx]

For (a), we say that a positive integer a divides b (writen as a|b) if there is a positive integer k such that b = ak. So, as you said, every integer divides itself, since we can take k = 1. But is this relation symmetric? If I know that a|b, does that mean b|a? How about transitive or antisymmetric?

I agree that (b) has symmetry.

[thorny hollow]

Would it not be a = bk?

[faint sphinx]

Nope.

[thorny hollow]

for example. Substitutes the variables a by 2 and b by 4.

2 = 4k

But 2 divides 4

[faint sphinx]

That shows it should not be a = bk.

Based on the way you substituted them.

[thorny hollow]

Waiy

Ah it is right I misread

[thorny hollow]

By the formula b = ak, can we say it has a relation of inclusion?

As a number x being divided by y implies x be a multiple of y?

Is it right?

[faint sphinx]

What does inclusion mean here?

[thorny hollow]

A relation R is said to be included in the Relation S, if whenever R holds a relation between two objects it implies S to hold a relation between them likewise

In symbols

xRy implies xSy

[faint sphinx]

Right, that's a property, not of the relation itself, but between two relations. (In fact, here the statement y divides x is the same as x is a multiple of y)

They mean properties of just this relation.

[thorny hollow]

So it would be wrong answer it with this?

By the way, it has not a relation of simmetry because a|b is not the same as a|b considering both a and b ≠ 1

So it is assymetric

[thorny hollow]

Transitive? Do you mean,

From: a|b and b|c, it follows that: a|c?

I think it is true?

Is it true?

[faint sphinx]

It is true, yes.

[thorny hollow]

I am just doing a and b questions because I know nothing about geometry so I am skipping them

[faint sphinx]

By the way, while division is not symmetric, that does not mean it is "asymmetric". A relation is asymmetric if, whenever we know xRy, we know that y (not R) x. That is, at most one of xRy and yRx can hold (but two elements might not be related at all).
Division is, however, antisymmetric (unfortunate that they are similar sounding, but you get used to it). That means whenever a | b and b | a, then in fact a = b.
(This is not true for if we consider the relation on all integers! Just on the positive ones)

[thorny hollow]

I see

In the case of b, of relative primes

It is not reflexive?

I mean, considering x = y, then

there is atleast one x and atleast one y which the relation: x is relative prime with y if their greatest common divisor is one, is true

I think, there is at most one?

But it won't holds for any number if x ≠ y??

It holds a relation of transitivity?

if x is relative prime with y and y is relative prime with z, then x is relatively prime with z

Is it true for any number?

I think it is

Is it?

[prime barn]

Can I assume this is monotone decreasing?

sorry wrong chat lol

[snow sleet]

it's obvious we can assume the students are distinct...the question is whether or not the problems are.

[jagged grove]

@snow sleet how many forms of induction do you know?

[snow sleet]

there are two: weak (also called regular) and then strong. The Well-Ordering Principle is equivalent to the Principle of Mathematical Induction so that is technically "another" (not really) form

[jagged grove]

mmm

sec

[snow sleet]

try proving induction using the Well-Ordering Principle

and then try proving the Well-Ordering Principle using induction

both can be done

[jagged grove]

yeah

i know

is therea bot that does that?

[snow sleet]

I can't read that

[jagged grove]

i dont think so

[snow sleet]

idk

[jagged grove]

so take a look at the second

its basically

case 1

and then they go n+1 proof for n

which i found interesting

but i also found one for "infinitely many"

so sometimes people have a hard time fitting induction to particular cases

i thought this might be useful

[snow sleet]

if it was in english, I might be able to read it lol.

[jagged grove]

i think i have a book in english which has them

ill look it u

up*

[snow sleet]

induction typically takes some slick thinking when proving the k+1'th case using the k'th case or all cases before k+1

harder problems require more clever thinking

it's a bit like the Pigeonhole Principle (it's a simple concept) in the fact that given a problem it may be hard for people to figure out what things they want to be their pigeons and what things they want to be their pigeonholes

[jagged grove]

yeah

sort of what we were doing the other day with the cardinality of a set of functions

sort of non intuitive really

[snow sleet]

the only part that required any thinking was figuring out which sets cardinality we'd induct on. A combinatorial proof would have been way shorter by the way

[jagged grove]

using the binomial coefficient and such?

[snow sleet]

no need for that

[jagged grove]

i sorta should get onto doing combinatorics tbh

[snow sleet]

have you taken discrete math?

[jagged grove]

yes

[snow sleet]

counting should've been covered

[jagged grove]

and i have many books on the topic

[snow sleet]

at least the basics

[jagged grove]

well calculating permutations

and combinations

was extensively covered

but just that

not proof based

[snow sleet]

good to hear! combinatorics problems are like fun puzzles

so you've never done a combinatorial proof then?

[jagged grove]

i remember something like C(n-r,r) = C(n,r)

or something

where c denotes binomial coefficient

[snow sleet]

yes that's an identity

and proofs for that are either algebraic or combinatorial

[jagged grove]

they do it by induction

[snow sleet]

ahahaha no need for induction lmaooo

you can do that proof in one line with just the algebra lollll

[jagged grove]

mind u i rembered that from the top of my head

and i took that course 4 years ago

[snow sleet]

this should be C(n,n-r)=C(n,r), right?

[jagged grove]

sec

C(n+1,r)=C(n,r-1)+C(n,r)

lets get spicy

[snow sleet]

have you tried proving that combinatorially?

[jagged grove]

i dont know what u mean by combinatorially?

[snow sleet]

using counting arguments

to show both sides count the same set

and therefore are equal

[jagged grove]

using the cardinality or something like that?

[snow sleet]

in other words, come up with a counting problem, and find the anwer to that using the LHS of the equation. Then find the answer using the RHS. If both sides count the same thing, they are equal. You are essentially establishing a bijection between the sets

[jagged grove]

and by counting u mean something like (given n apples how can you fill x boxes that fit 2)

?

[snow sleet]

I would also like to point out that my proof not only proves the case for odd n but also ensures we don't need the n= even case.

[snow sleet]

here^

[snow sleet]

yes that's a counting problem

[snow sleet]

I'll give you an example using this problem

[jagged grove]

so do i have to construct my own counting problem?

[snow sleet]

yes you need to construct the set you are going to count

[snow sleet]

I'll prove this one so u have an idea

\begin{proof}Given an integer $r\geq0$ and an integer $n\geq r$, suppose we have $n+1$ people in front of us in a line. We wish to construct a team of $r$ people from those $n+1$ individuals. Clearly, we can do this in $\binom{n+1}{r}$ ways. Alternatively, assume Bob is part of the $n+1$ individuals. We could count the teams that do not have Bob and then add that number to the teams that do. So let us set Bob aside. Now from the $n$ remaining people we choose $r$ of them in $\binom{n}{r}$ ways. Let us now assume Bob is on the team already. We fill the remaining spots using the remaining $n$ people. We can do so in $\binom{n}{r-1}$ ways. Thus the number of ways we can construct teams of size $r$ is precisely $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$, as required.\end{proof}

[vital dew]

logician

[snow sleet]

@jagged grove there we go^

[jagged grove]

i get it but you would have to invoke the sum principle and the product principle

right?

like to make it more explicitly evident

[snow sleet]

I implicitly invoked the sum principle when I coun ted the cases where Bob was on the team and where he wasn't and added those cases. I don't need to "explicitly" invoke it. I'm assuming the reader has a proficient understanding of counting.

[jagged grove]

well yes

[snow sleet]

but the point being

that is called a combinatorial proof

[jagged grove]

i guess coding on c++ kinda wired my brain to explicit statements

[snow sleet]

not just because I'm proving a combinatorial identity, but because I proved it using counting arguments

[snow sleet]

I hate programming.

Alright dandida now u try to prove this theorem I made. Prove it combinatorially

[jagged grove]

found a discrete math book that touches on fuzzy sets for counting

lol

[snow sleet]

lolll

[jagged grove]

tomorrow

ps

i promise

im tired

[snow sleet]

I'll post it here anyway

[jagged grove]

yeah

ill check it in the morning

[snow sleet]

Given an integer $n\geq2$, $n+\binom{n}{2}=\binom{n+1}{2}$.

[vital dew]

logician

[jagged grove]

suppose we have n pigs in front of us and we want to add 2 pigs from a group of another n pigs we can do this by n+C(n,2)

[snow sleet]

okay

now make sure the RHS counts that too

[jagged grove]

alternatively from a set of n+1 pigs we want to chose 2 we can do this by C(n+1,2)

like im expressing the two statements

but im not wording it in a way in which there is a relationship

between LHS and RHS

[snow sleet]

how do we know these n+1 pigs relate to the two groups of n pigs u already defined

[jagged grove]

assume piglet is part of the n pigs, taking out piglet to the n+1 pigs and choosing 2 we get C(n+1,2) and if we add n pigs we get C(n,2)+n which is what we wanted to show

[snow sleet]

I'm still not convinced on the RHS

the LHS is good

Ur almost on the right track....

Try considering only n+1 pigs (one of them who's name is piglet). Construct teams of 2 in C(n+1,2) ways. Then count such teams by splitting into cases (piglet is on the team or not). If he is on the team, fill the remaining spot on the team by choosing 1 from the remaining n pigs in C(n,1)=n ways. If he isn't on the team, choose 2 from the remaining n pigs in C(n,2) ways. Thus n+C(n,2)=C(n+1,2).

[jagged grove]

ohh

theres pigeons

and combinations involved

in this

[haughty garden]

isn't this just a special case of pascal's triangle

[jagged grove]

maybe

but my brain is fried at the moment

lol

[haughty garden]

C(n, k) = C(n - 1, k - 1) + C(n - 1, k) with k = 2

since n is just C(n, 1)

[jagged grove]

im going to sleep

but i know i have what to play with tomorrow

[snow sleet]

yes, in my problem n is your n-1

[haughty garden]

it'd be a good exercise to more generally prove pascal's triangle combinatorially since it's not too bad of a generalisation to the k = 2 case

[snow sleet]

fyi @jagged grove the way I proved this statement and the way I even I even came up with this theorem in the first place was I was counting how many dominoes I construct using numbers from the set {0,1,2,...,n-1} on either side of the line dividing the face of the domino. A standard dominoes uses numbers {0,1,2,...,6} on either side of the line dividing the face in half.

[snow sleet]

I'm introducing dandida to combinatorial proofs, so we're warming up with simple problems. Sounds like he's excited to take on that statement you brought up.

[haughty garden]

there's a book that I really like with some really interesting identities that can be proven combinatorially

Proofs That Really Count: The Art of Combinatorial Proof

^it's also designed to be targeted at the undergraduate level

so while there are some really complicated identities, the book steps through how to think about the identities combinatorially

[snow sleet]

there's a really beautiful proof for the sum of the first n positive integers

combinatorial proof*

[haughty garden]

the sum of the first n odd integers is actually quite pretty

[snow sleet]

I'll assign myself that problem. Don't tell me how it's done.

[haughty garden]

well, the proof i'm thinking of is not really a combinatorial proof but a geometric reinterpretation of the result

[snow sleet]

Gotcha, that's the first thing I thought of.

[hollow token]

How would you prove that f is a lattice isomorphism if and only if it is an order-isomorphism?

[twilit sundial]

the last paragraph makes little to no sense: how is it "easy" to immediately reach the inductive conclusion

(the problem)

[fallow dune]

so basically the proof is saying that being divisible by 2 means its even/ having a factor of 2 is even?

[snow sleet]

No the proof is saying: You give me any odd integer u like, and I can guaranteee the product formed with that integer and the one just below it is even. I can also guarantee that the product formed with that integer and the one just above it is even. I showed both of these products are even by showing they're both multiples of 2, yes

I'm not proving that "being divisible by 2 means an integer is even"...I'm assuming that because it's the very definition of what an even integer is right!?

[snow sleet]

A shorter proof would be to say: Suppose x is an integer. Then 2|x or 2|x+1. In either case 2|x(x+1), implying x(x+1) is even.

note here^ I do not need to consider the case x(x-1)

I’m assuming the property here that if a and b are integers and n divides a, then n divides ab

[thorny hollow]

Can someone help me with an example about how to solve a?

A

[thorny hollow]

Please

[jagged grove]

is K a equivalence class?

[thorny hollow]

It is just an arbitrary class

[jagged grove]

classes are not within discrete math topics as far as i know

[thorny hollow]

Classes here is the same as sets, and theory of sets and relations are discrete mathematics subjects

[jagged grove]

if its within that context and ZFC set theory holds

i think i can help u

[thorny hollow]

Yes this book describe sets as classes

[jagged grove]

is it an old book?

[thorny hollow]

So so

[jagged grove]

give me the title so i can look it up

[thorny hollow]

It is from 1994

[jagged grove]

is it just likeR^-1

[jagged grove]

is it knuth?

[jagged grove]

i would not call this discrete math

tbh

[thorny hollow]

But logic is a discrete math subject also

[jagged grove]

but ill try to help u

[thorny hollow]

I would be really pleased if you do so

[jagged grove]

sec

reading a bit

[thorny hollow]

I just need help with a) so I can abstract it and do the rest by my own

[jagged grove]

is the negation of the relationship just that if it has (a,b) then R negative would have (b,a)?

[thorny hollow]

No

Think that way, if R is the relation of x be a multiple of y, then R' means x is not multiple of y

[jagged grove]

i just got the book give me a sec to check some definitions

[thorny hollow]

By means of logic and definition, I think it is true and its converse is likewise

But I am not sure

[jagged grove]

i think the same

but i need to see how he proves things

cause llike

if a is not related to a in R

it shouldnt be in R negative

cause (a,a) is not even a element in R

for all a in A

s.t ARA

mmm i think this is how it goes

[regal gate]

Why?

[thorny hollow]

I searched "discrete mathematic subjects" in google and there it was

[regal gate]

Source?

[jagged grove]

let A be a nonempty subset and let R be a relation such that R is contained in AxA then for any (a,a) is R is irreflexive (a,a) is not contained in R more particularly is (a,a) is not in R it will not be in its inverse relation.

[thorny hollow]

Wikipedia

[regal gate]

What popped for me also included probability

Ah lemme check

I mean

That listsm also includes functions

[jagged grove]

@ivory badge can u check this proof really quick

[regal gate]

Yeah

"Functions"

And probability

[jagged grove]

functions are a subset of relationships

well

[thorny hollow]

Yes

[jagged grove]

more like a kind of relationship

[thorny hollow]

Are relations a subset of sets?

Or conversely?

Or neither

[jagged grove]

no

relations are defined in (AxA)

[regal gate]

This is wrong taken literally

Because many of these fit into what would be called "continuous mathematics" or something like that

[jagged grove]

so in discrete math there is no sense of continuity

[regal gate]

There is no reason to separate the two

[jagged grove]

like when u see the world class

it would mean that the sets that are classes

are not quantifiable

so not discrete math

[thorny hollow]

This book uses the word Classes in place of sets

[jagged grove]

yes and im telling u

thats wrong

in math that word has a different semantical meaning

unless its talking about equivalence classes

[regal gate]

Btw, they say "subjects in discrete mathematics", as in, the intersection logic cap discrete math is nonempy. I think

[jagged grove]

which is as far as i know the only class which is talk about in discrete math

[faint sphinx]

In older texts, class and set are used interchangeably

[jagged grove]

@regal gate did u manage to justify the terms of that induction from yesterday?

[regal gate]

Justify what? My proof was complete from the first time I wrote it

[jagged grove]

lol

i dont think ur proof was right

did u do the n = 1 case?

for starters

[regal gate]

[faint sphinx]

All sets are classes in some sense, but not all classes are sets. Anyways, in ZFC, classes are not objects anyways, so we should be talking about sets more properly.

[regal gate]

Literally my proof was perfect

Wasnt difficult either

[faint sphinx]

The term "equivalence class", despite the fact that it only makes sense with sets, is a consequence of that.

[jagged grove]

were u doing induction for n+1 then it holds for n or something?

[faint sphinx]

what

[jagged grove]

cause he told me

changed n to n+1

[regal gate]

That was just a change of variable

Didnt affect the argument at all

[faint sphinx]

I didn't fully read it yesterday but it looked fine to me at a glance.

[jagged grove]

here

[jagged grove]

and this

[ivory badge]

What proof

[jagged grove]

my problem is i dont see how u can go from the first step

to the second steep

one sec

sharp

[ivory badge]

a R b iff b R^-1 a

[jagged grove]

this is in the context of showing that if a relationship R is irreflexive then its inverse is irreflexive

[ivory badge]

Substitute b = a

[faint sphinx]

gg

[jagged grove]

isnt reflexive that aRa ?

then irreflexive means a doesnt relate to a

[ivory badge]

yes

[jagged grove]

so

im asking you to check the proof i did on that

to which i provided a context

[thorny hollow]

Then it would be false if the proof is right?

Because every element is reflexive to itself, isnt it?

[jagged grove]

it would be false that R is reflexive yes

[faint sphinx]

I mean it's immediate from the definition. What you sent seems confusing/unnecessary details.

[thorny hollow]

to refresh, I am needing to answer question a

[ivory badge]

This is a different thing for R’ then

[jagged grove]

isnt the negation

the inverse of the relationship?

[ivory badge]

Negation is not the inverse

No

a R b iff not a R’ b?

[jagged grove]

i read

fucking reflexive

as irreflexive

holy shit

[ivory badge]

(a R b) iff -(a R’ b)

[jagged grove]

and its the negation here taken the same as the complement of the set

[faint sphinx]

Or R' = XxX - R

[ivory badge]

Ye

[jagged grove]

ahhh

so yeah

if u take any element from R and R is reflexive

that element will not be in R'

[ivory badge]

Yes

[jagged grove]

in particular (a,a) not in R' for any a in A, therefore R' is irreflexive

that induction from yesterday has been bugging me

[ivory badge]

If R is reflexive

[jagged grove]

stated it here

[ivory badge]

Ah yes

[jagged grove]

i edited

can u help me understand the induction im refering to

like

can u just substitute n for n+1 without doing the base case n = 1 in the fp?

[ivory badge]

What induction

[jagged grove]

here

[thorny hollow]

Right, and how this proof the truth or falsity of the statement?

[gritty tide]

Someone explain this to me or i am going insane

[jagged grove]

truth

[thorny hollow]

The statement is true then

And so is its converse?

[jagged grove]

what do u mean

i proved that the statement is true for the a)

[gritty tide]

please? ;dddd

[jagged grove]

ill give u a hint

[thorny hollow]

And the converse of the statement?

[jagged grove]

what do u mean by converse?

[thorny hollow]

Given a sentence "if p then q" its converse is "if q then p"

[jagged grove]

is it in this case something like if R' is reflexive then R is irreflexive?

[thorny hollow]

It would be "if R' is irreflexive then R is reflexive"

If a element is not in R', does it implies it be in R?

[jagged grove]

yes

by definition

of complement of a set in this case u should do if and only if

for the proof i gave u

[thorny hollow]

I am confused

[jagged grove]

so if both q => p ^ p => q this is equal to p <=> q

or

q iff p

[chilly hemlock]

yes a=>b and b=>a implies that a<=>b

[plucky wedge]

I don't think dandida was asking the question lol

[marsh oyster]

Is there any book/website to read the proof of commutative and associative law in composite function of permutation?

I've read some books but couldn't find it, my professor gave me an assignment to prove them

[snow sleet]

Prolly any discrete math book would touch on that...

To prove that a given set $S$ is associative under the operation $\star$, you must show that given $a,b,c\in S$, $a\star(b\star c)=(a\star b)\star c$.

[vital dew]

logician

[snow sleet]

@marsh oyster

You show commutativity by showing for all $a,b\in S$, $a\star b=b\star a$.

[vital dew]

logician

[sour talon]

can someone please tag me and explain this?

shouldn't the contrapositive statement be, if a is greater than or equal to ∛n & b... & c... then n≠abc

I don't think the solution reflects the usage of the contrapositive

so I'm confused

can anyone help explain

[snow sleet]

it's not even a true statement anyways. and btw abc>=n doesn't prove n is not equal to abc.

Suppose n=1(1)(1). Then 1,1,1 are positive integers. But 1 isn't less than the cube root of 1

so the statement is false

[snow sleet]

even if the statement was true (which it isn't as I've stated before) it's not correct use of the contraposition. The assumption is fine, the conclusion part isn't correct as you pointed out

[rapid horizon]

If we got a problem like this where we have 3 particles to arrange in 5 states such that their energies always sum up to 5E,

How would we go about computing all the possible combinations?

[raven python]

If the possible energies are consecutive numbers, you can try to show the equivalence with the number of solutions of the equation
$x_1 + \ldots + x_n = E$
where $x_i \in \mathbb{Z}_{+}$. It might require some additional tweaking depending on the assumptions. This equation, in turn, can be solved in a combinatorics-like way by representing E as 1 + 1 + ... + 1, and by dividing this sequence into n compact blocks

[vital dew]

Thingoln

[raven python]

I'm on my way to work, but I hope this helps

[rapid horizon]

I got it! This helped

[real canopy]

It's this

[short ocean]

i have a question for those who are familiar with the graph theory out there

i dont know the solution, but i think this is a question of discrete maths

[raven python]

I don't think I understand the problem to be honest 💀

[short ocean]

i thought i would get this

so for each and every one of the teams the last condition should be met

and its trying to tell that when a teams opponent's opponents are listed all teams should be included in this list

for example lets assign letters for teams like A B C...

lets say that A makes matches with B C D E F G H I (exactly 8 teams)

and when we list all of the opponents of the B C D E F G H I all teams should be included in this list

[raven python]

Okay, I think I get it now. So we take a vertex, take a look at all vertices that are neighbours of its neighbours. We repeat this for every Vertex. When we sum up those vertices, we get all of the vertices in the graph

And each vertex has degree 8

[short ocean]

yes perfect

[raven python]

Is this correct?

[short ocean]

that is a better way to put it

as i said i havent taken any discrete maths class so thats why i may struggle with the terms

[short ocean]

wait i dont think you got the sum up part

there is no summing up of the lists

[raven python]

So each vertex's opponents' opponents are the set of all vertices?

[short ocean]

correct

no summing up

[raven python]

I see. I'm at work now and it sounds like something that needs to draw something, but if no one answers within like 7 hours, feel free to ping me

[short ocean]

of course, thank you for your help!

[formal falcon]

Opponent’s opponents? If the question wasn’t so weirdly worded I could have tried for sure

[thorny hollow]

What book about discrete math do you guys have read

[formal falcon]

Rosen

[thorny hollow]

I am reading the one from susann now

[formal falcon]

I see

I mean if you like it, nice

This was the recommended book for my course

[brave rock]

Yes, in fact you can substitute R for any infinite set and this will still hold.

This is because if at least one of A and B are infinite then |A x B| = max(|A|, |B|).

Oh, and of course if neither set is empty :)

[short ocean]

how would you describe it then? i dont understand the aggression

[raven python]

The question written in a sane way would be: how many vertices can an 8-regular graph whose diameter is at most 2 have?

[blazing rose]

Hey I am still a bit confused with how to do an induction proof on this
I found out the general formula for a_n already
It is a_n = 3^(n-1) + 1
when I do the hypothesis with that and did the base case I get stuck
at the point of the step
I did say: a_k+1 = 3^((k+1)-1) + 1
how do I proceed now?
how can I use anything from my hypothesis and insert it into my step at this point?

[haughty garden]

Use the recurrence and your inductive hypothesis

a_{k + 1} = 3a_k - 2 and by your inductive hypothesis, you have that a_k = 3^(k - 1) + 1

[blazing rose]

thanks a lot got it :D

[slender verge]

(∼ (p∨ ∼ q) ∧ (∼ p∧ ∼ q)) ∨ (p ∧ (p∨ ∼ q)) if i wanna use argument froms to simplify to p can i say elim (∼ (p∨ ∼ q) ∧ (∼ p∧ ∼ q)) so (p ∧ (p∨ ∼ q))

[jagged grove]

no

simplify the term at the left of the main or in the center

first

thats my advice

wait

ur right

but u have to justify it

what is it that your using to get to say that (∼ (p∨ ∼ q) ∧ (∼ p∧ ∼ q)) can be eliminated

?

[maiden crypt]

been stuck on this john for like 20 mins

[rapid mural]

think about the definition of $\subseteq$ and $\in$

[rapid mural]

and what exactly the elements of S are

[maiden crypt]

I never learned that in class we didnt lecture it but the webwork for sets includes it

[rapid mural]

.

[maiden crypt]

[1,2,3,4]

?

[rapid mural]

nope

that's not quite right

yes, 1 and 2 are elements of S

but 3 and 4 are NOT elements of S

[maiden crypt]

What are 3 and 4 elements of then?

[rapid mural]

you tell me

[maiden crypt]

im not sure cuz its in its on {}

[rapid mural]

right

[maiden crypt]

but its not assigned to a letter

so im not rly sure here

[rapid mural]

well do you think sets can be elements of other sets

[maiden crypt]

yes

[rapid mural]

yep

so

there are 3 elements of S, can you state it?

[rapid mural]

why does it have to be assigned a letter

[maiden crypt]

1,2 and the set {3,4}

[rapid mural]

yep

exactly

so try the question again now

[glossy heron]

man just help my jit out hes been on this shit for the last 2 hours, he accidently fell asleep in class just give him the answers

hes got a date in 30 minutes

help a brother out

[rapid mural]

uh we don't give answers here

[glossy heron]

can you like dm him it or something bro this dude is selling

the bag

[maiden crypt]

ok Ill try it w that logic of 3 elements

[astral flower]

🤓

[maiden crypt]

@rapid mural got it

tty

[rapid mural]

np

[earnest palm]

how does one prove (Ǝk. x= 2k+1) ^ (Ǝk. y=2k+1) -> (Ǝk. x+y = 2k)

[static briar]

Desperately need help for part 2 🙏

[spring sparrow]

F & G

You Inclose the element of a set in curly braces to denote it as a subset

and you do not wrap and object with any braces to denote it as it element and use belongs to symbol

[rigid oriole]

x and y are nonbounded variables

thats generally false.

[foggy sentinel]

37x +15y = 12 how do I solve this using diophantic method?

GCD is 1

1 | 12 which means that the equation is solvable

But then what? I need to find one solution to x and one solution to y and after that conclude a general solution

[icy flame]

hello, I'd like some help with this question. Its been few days that I am thinking about it and it seems to me that I am stuck.

[final cliff]

They should specify what things they are quantifying over, but it's not generally false. Quantifiers apply over sets of objects called a domain of discourse or a universe of discourse. In this case they probably just mean they are quantifying over integers.

[rigid oriole]

huh

the statement is generally false

for all x, y right?

well if we dont say what x and y are, then we dont know if its true or false

[final cliff]

Yes I agree that we don't really know since they didn't tell us what they are quantifying over. But I think they mean to quantify over the integers.

https://en.m.wikipedia.org/wiki/Domain_of_discourse

This is what I'm talking about.

With domain/universe garbage.

When you specify a semantics for a logic in your metalogic you typically have to give a set of objects that tell you what sets of things your quantifiers deal with.

In math it's usually implicit that you're quantifying over sets tho fwiw. So, in most math it really isn't true.

[thorny hollow]

How it disappeared with the p in (p v q)

(p v ~q ) ^ (p v q)

p v ((p ^ ~q) v (q ^ ~q))

[final cliff]

Going from the 2nd to the 3rd line?

@thorny hollow

[thorny hollow]

Yes

[final cliff]

Distributivity allows them to "factor" out p.

[thorny hollow]

How

[final cliff]

Av(B&C) is equivalent to (AvB)&(AvC)

You should have an equivalence along those lines.

[thorny hollow]

How this is applied in the statements there

[final cliff]

They have the right formula here with p=A, B=~q and c=q at line 2.

So, they can conclude the left hand formula is equivalent with those same choices for A,B,C.

[thorny hollow]

I ser

I see

Makes sense

[icy flame]

can someone help me please?

[jagged grove]

their asking for criteria of functions

actually this is kinda fucked up

would have to get pen and paper

but im sorta in the middle of something

by bijective do u mean to proof there is only one such functions that satisfies the equality @icy flame ?

[jagged grove]

ur proof of bijectivity is wrong btw

g(g(n))=f(f(1))

[unborn vapor]

I think mike is right that g(g(n)) = n because g(g(n)) = g(-f(f(1) - n)) = -f(f(1)) - (-f(f(1)) - n) = -f(f(1)) + f(f(1)) + n = n

[jagged grove]

g(g(n))=-f(-f(f(1))-n)-n

-f(f-f(f(1))-n)-n=f((f1))+n-n

f(f(1))

n is a constant

[jagged grove]

also check the parenthesis on ur expressions their not closed

[faint sphinx]

What pigeon said is correct (just missing one ")" somewhere there)

[unborn vapor]

yeah, should be fixed now

[jagged grove]

wait composition is in n

sec

yeah

ur right

still wouldnt what he provided only count as a proof of 1 to 1?

i dont see onto

[faint sphinx]

Since gg(n) = n, g is its own inverse.

[jagged grove]

well yes but he would have to invoke that if f(g(g(n))) is reversible

then its bijective

also

hes affirming f(f(f()))

[unborn vapor]

if you want it in terms of f, 6 compositions of f is the identity function, so for any integer n, f composed 5 times of n is the preimage of n

[faint sphinx]

gg = fff

[jagged grove]

i was thinking of using identity

mm

so he needs the identity function n+m?

[unborn vapor]

wdym?

[jagged grove]

in this case hes assuming m = 0

sec

f(m+f(f(n))) is what hes given

he needs to establish this

for any m

but i guess you could do induction like this?

@faint sphinx ?

took me ages to find the book in which they say u can do induction by 0

lol

[faint sphinx]

This is sometimes calles "strong" induction since you assume P(j) for all lesser j, not just the one immediately before.
But ofc you can start induction at 0

[jagged grove]

thx @faint sphinx, @unborn vapor

[ivory badge]

SL_2(Z) or whatever

[regal gate]

why SL_2(Z)?

its been a while since I havent done a fe

[unborn vapor]

what are you suggesting proving by induction? I think the conclusion that f is bijective is already proven (in general, not just for a special case) because what we showed was that any f that satisfies f(f(f(n))) = -f(f(1)) - n for all n must be bijective, and we know that our function does satisfy that condition since the initial condition in the problem must hold for all n, m which includes m = 0

basically I think that all of mike's conclusions are true, but I don't really have ideas of how to conclude more things (which is why I initially didn't respond to the question because I don't have anything to add)

[ivory badge]

It reminds me of SL_2(Z), that’s it

[regal gate]

what an annoying fe honestly

because a lot of negative signs

there are so many relations its not clear what to do xdd

[willow hatch]

f is bijective, so there has n0 in Z, s.t. f(f(n0))=1
Substitute n=n0 in f(m+f(f(n)) = -f(f(m+1))-n

[regal gate]

nice

gg

[willow hatch]

One can prove that there is a unique f

[regal gate]

||with this you are done, because you have f^2(x)=a-f(x) for some constant a, then rewriting the original equation we have

f(m-1+a-f(n))=f(m)-a-n,

let m=f(n), then the left is constant and in the right we get f(f(n))-a-n=-f(n)-n, so f(n)=-n+b for some constant b, and I assume you can just check what works||

I think?

||f(n)=-1-n||

[willow hatch]

Similar concept. I am beginning from f^3(x) = -f(f(1))-x

||f(x)+f^2(x)=-n0||
||f^3(x)+f^2(x)=-n0||
||=>f(x)=f^3(x)=-f(f(1))-x||
||f(n-1+f(f(n))) = -f(f(1))-n+1-f(f(n)) = -f(f(n))-n||

[weary tiger]

lets say P implies Q and i want to do an indirect proof, the rule is you must assume right hand side is False and prove that P is True not false right?
And for equivalencies, I am able to assume from either side whether its true or false but must prove the opposite side as the same correct?
and regarding proofs and equivalencies, lets say there is multiple cases that prove the implication or equivalencies, do I need to prove all those cases or as long as I provide proof for 1 case that is fine?

[weary tiger]

https://gyazo.com/0688a2f1042b039bae1be54c9469b14c can someone very this? I know there is another case that makes it equivalent if p, q, and r is all true

[crisp cove]

Hello, can you help me?

[gusty grove]

If α:A->B and β:B->A
Is αβ(b)=a possible?
Is this not rather α(β(b))=α(a)=b?

[icy flame]

thanks for the help yesterday, sorry I went offline in the middle of the it but i had to due to personal reasons.

[thorny hollow]

Could someone help me substitute the statements for variables

[forest obsidian]

Is there a symbol for composing n functions together similar to sigma for summations

[vestal bronze]

n of the same function?

just power?

[vital dew]

grothendieckfan1 (Ryx)

[forest obsidian]

thanks

[regal dune]

So this is the problem and solution, I'm trying to understand that first sentence in the solution where it says "expressed in lowest terms". If it says that, and I wanted to visualise it, p could be "2/3" since it's lowest terms right?

[little prism]

p and q are integers. so p cannot be 2/3

but p/q shouldnt be for example 2/4

[snow sleet]

expressed in lowest terms means gcd(p,q)=1 (i.e., p and q are relatively prime). In other words, they share no common positive factors aside from 1.

so p/q is irreducible

[regal dune]

So an example would be 5/12 since they have no common factors right? Something that is reducable would be 2/4 since can be reduced to 1/2?

[little prism]

yes

[regal dune]

thanks a ton!

Does this server have voice channels for discrete or vcs for math?

[little prism]

no

[regal dune]

is my problem

[proper sun]

Kindly help with this

[regal dune]

so if we read this, it says "there are no elements in A that are not in B" = E

[regal dune]

Which is false because n=3, or n=9 is counter example. So {3,9...etc} = E

E says n is an odd multiple of 6 so would this be false since there is no odd multiple of 6?

Counter example would be 3

[dusty ruin]

Hi can anyone explain how to do this problem

[obtuse lance]

what have you tried

[distant grove]

Let $A={1,2,3,6,9,18}$
\
Define $R$ on $A$ as $x \mid y$. Show that $R$ is a partial order relation and draw a Hasse diagram.

[vital dew]

dgh

[coral parcel]

That's just a "check that you have understood the definition of 'partial order' and what a Hasse diagram means" exercise.
There's nothing to do except follow your nose and verify the parts of the definition one by one.