discrete-math

[tight lotus]

society

[swift sparrow]

is there a room for real analysis ?

[stray reef]

#advanced-analysis

[pale epoch]

the degree of a vertex is the number of adjacent vertices

yes

thats the same thing

two vertices are adjacent if they are connected by an edge

oh yeah, mb

your second picture is a multigraph

there you have to define degree via edges i guess

anyways, the image still has two vertices of odd degree (1 and 5)

[obtuse lance]

you can prove it by induction, imagine starting with a graph of all vertices, then each is of degree 0 which is even, then every time you add an edge you're changing (even, even) to (odd, odd) or (odd,even) to (even,odd) so the total odd degree is always even

[pale epoch]

the e is the number of edges

[obtuse lance]

imagine the graph having no edges and then think about what changes when you add just one edge at a time

[pale epoch]

the idea of the handshaking lemma is that if you sum up the degrees of the vertices its the same as counting every edge twice, since every edge connects two vertices and thus contributes +2 to the sum of the degrees

then you can deduce (c) since the right hand side of the equation is even, so the left hand side must be even as well, so every odd summand must be "cancelled" by another odd summand

(or you can think about it like mero suggested)

well

the sum of an even and an odd number is odd

odd and odd is even

etc

so if there were an odd number of vertices with odd degree

the LHS would be odd

you cannot have an odd number of vertices with odd degrees

it means there is an odd number of edges connected to that vertex

yes

no, this is a graph

but there are 2 (even number) vertices with odd degree

you cannot draw a graph with an odd number of vertices with odd degree

(try doing it and observe how the degrees of vertices change when you add an edge)

(this is what meros idea boils down to)

i dont think so

at least nothing similar

[pale epoch]

this might depend a lot on how this was presented to you

but basically if you ignore the backtracking and make all the edges undirected, you get a tree (forest)

you can also define that via discovery/finishing times

[past gate]

Does anyone know how to prove that 3|(x−y) defined on Z(Integers) is a symmetric relation?

I need to prove that it's an equivalency wich means I have to prove that it is reflexive,symmetric and transitive

[obtuse lance]

what does it mean to be symmetric?

[pale epoch]

what DFS returns exactly depends on your implementation
if it returns a directed graph, you can turn that into a tree/forest if you only consider the forward edges (i.e. ignore back-/sidetracking) and make them undirected

alternatively DFS may return discovery times of vertices

i.e. when was a vertex first discovered and when was it finished (all children have been found as well)

you can use this data to construct a tree

[pale epoch]

ah yes, those

there are like 4 types of edges and i dont know all the names from the top of my head

makes sense to call them tree edges i guess

since they give you a spanning tree

[obtuse lance]

ok so how does that look in terms of 3|(x-y)?

[weary tiger]

is anyone here good at induction or discrete math in general

[sour arrow]

Yes

[light ginkgo]

Yes

[errant bear]

no :(

[minor lake]

dpends

[tight lotus]

^

[weary tiger]

I'm definitely missing something fundamental but

for (c)(i) I said if we assume the function is part comp then there exists N such that f_N,1=g and hence g(N)=f_N,1(N)=f_N,1(N)+1 which is a contradiction

I'm assuming (c)(ii) is a part comp function but why does this exact same idea not work

[past gate]

I really have no clue to be honest,idk how to approach the problem.

[obtuse lance]

in the example they show they give = which is symmetric, all it really means is x=y is the same as y=x

so try to write the same thing with x and y flipped and see if that holds

[tranquil flint]

Hey guys any hints on how to approach this; trying to prove a graph with minimum degree of 3 has a cycle thats length is not divisible by 3

[tight lotus]

what was the exact wording?

u can make a line graph for example with degree > 3, no cycles

[proven shard]

Cant you make an infinite ternary tree with no cycles

[obtuse lance]

typically degree refers to the degree of the vertices, and graph means finite simple graph

[tranquil flint]

Uh i got a hint from someone who said let say a,b,c be the adjacent vertices to an end point say x on the largest path of the graph

yea every vertex in simple graph is at least degree 3

is what it means

and if cycle1 = (x,a,...b,x) and cycle2 = (x,b,...c,x)

if either isnt length divis by 3 we done

otherwise assume both are length divis by 3

would this imply (x,a,....b,....c,x) is length not divis by 3?

nevermind i think i got it haha

[last timber]

@spark silo all trees are circuit free

with purple example it means that it is not circuit free

at least you remove red edge

[last timber]

yes

[ember saffron]

how could I go about proving this? I was thinking I could prove that a cycle exists since the graph effectively only has a "starting node" and no "ending node" but I'm not sure how to mathematically word that

[stray reef]

you could prove that a tree on n>=2 nodes has at least two leaves

(leaf = node of degree 1)

[red nest]

to mathematically word what you want, you may want to show that if G has n vertices, then G has n+1 vertices, then use induction to conclude for all k, G has more than k vertices.

[stray reef]

if G has n vertices, then G has n+1 vertices

[red nest]

By has i mean has atleast

[quaint star]

@ember saffron

[ember saffron]

hi:)

[quaint star]

Are you familiar with the fact that if a tree has n vertices then it has n-1 edges or not yet?

[ember saffron]

yeah I am

[quaint star]

Use that to prove what Ann said

Also recall that sum of degrees = 2 * number of edges

[ember saffron]

so I've got the sum of "all the unknown degrees" (i.e. taking out the known degree 1) to be 2n-3, I think I wanna say "looking at this new graph without the first leaf, 2n-3 = 2(n-1) -1 i.e. the extra -1 shows there's a leaf in this new graph, therefore in the whole graph there are 2 leaves"?

I'm imagining this graph as just a straight line of nodes of order 2 with obvious leaves at either end, my explanation makes sense in that case but there's probably other shapes that make it a bit less rigorous

[quaint star]

Suppose a graph has exactly one leaf and is a tree.

Then one vertex has degree = 1, and all other vertices have degree >= 2.

What does that say about the sum of the degrees?

[ember saffron]

the sum's odd

[quaint star]

No

Idk how you can get that

[ember saffron]

wait no lol

nvm

[quaint star]

We don't know the degrees of the other vertices

[ember saffron]

yeyeye brain missed >

[quaint star]

Okay, so?

[ember saffron]

well
if you take out the d=1 vertex you've got a sum of 2(n-2), put it back in you have 2(n-2)+1 which is basically what I said earlier, not entirely sure what mathematically that tells us

[quaint star]

Well

You don't have a sum of 2(n-2)

That would be assuming every other vertex has degree 2 and not >= 2

[ember saffron]

n-1 vertices so n-2 edges no?

if it's a tree^

[quaint star]

Well, yes, but I want you to add the degrees not the edges

Sum of degrees >= 1 + 2(n-1)

Can you see that?

[ember saffron]

ah ok ye

[quaint star]

Since the one vertex has degree 1, and the other n-1 vertices have degree >= 2

[ember saffron]

since the formula I keep using is basically the minimum

[quaint star]

So sum of degrees >= 2n - 1

Now remember that sum of degrees = 2 * number of edges

So what is 2 * number of edges?

[ember saffron]

if it's a tree that's 2n-2 which is obviously less than the minimum

[quaint star]

Yes

So you get 2n-2 >= 2n - 1 which is a contradiction

So your assumption was wrong

[ember saffron]

not bad 😄

I think I was too stuck on using the degree formula, wasn't really thinking about how I could work towards a contradiction

proofs are probably my weakest area of any maths so makes sense

[quaint star]

Practice will make you better, dw

[ember saffron]

hopefully lol

speaking of practice, I have another one that's slightly harder if you're up for it

it's an extra exercise so it's intended to be quite bad

I'm thinking that like, if you remove a vertex you remove at least one edge, whereas if you remove an edge you remove at most one vertex, but actually that kinda makes no sense

[quaint star]

Have to have lunch now. And this one is not immediately obvious to me anyway. Woukd have to think.

[ember saffron]

sure no worries, I'm gonna work on it for a bit

@stray reef / @red nest you guys able to help with this one? thinking I could actually use some kind of cycles idea buut not sure how I'd start it

[stray reef]

assume k > l for the sake of contradiction

highlight a set of l edges whose removal disconnects G

for each highlighted edge, highlight a vertex incident to it

cut out all l highlighted vertices

the l edges must also go, so G will wind up disconnected

but then we have disconnected G by removing less than k vertices

[ember saffron]

by incident do you mean connected?

(I call vertices nodes, degree order, hate how many ways there are to say the same thing in graph theory lol)

[weary tiger]

two vertices are adjacent if they are connected by an edge

two edges are incident if they share a vertex

[stray reef]

a node is incident to an edge if the node is one of the edge's endpoints

[ember saffron]

I see, I hadn't come across that term

thanks both 😄

honestly graph theory makes me wish I'd been able to do more of it in earlier years, I'm effectively doing an intro module in my final year 😦

[weary tiger]

Quick question, in a digraph if u_(i+1), u_(i+2)......,u_(k) is a walk, is it correct that the number of its arcs is k-(i+1)?

Oh nvm, I figured its k-i arcs

[light ginkgo]

No

[weary tiger]

"In general, two edges are “incident” if they share a common vertex. Not only edges, but vertices can also be incident with an edge. A vertex is incident with an edge if the vertex is one of the endpoints of that edge."

Quoting from a discrete maths textbook

[light ginkgo]

Very weird where are you from?

[weary tiger]

France

[light ginkgo]

Im surprised terminology varies this much.

I have 4+ combinatorics/graph theory books and they all use incident differently.

[weary tiger]

From most English textbook, you're completely right that the second terminology is much more frequently used

If we're given a digraph on n vertices and some walk of length n (that is the number of arcs involved in that walk), can we conclude that there is some repeated vertex on that walk? If it had been a path on n vertices, it would've been a directed tree, and we know any tree on n vertices contains n-1 edges (arcs).

[weary tiger]

You've got p vertices, of which you supposed at most 1 has degree 1 so at least p-1 are of degree 2

So sum of degrees is at least twice the number of vertices of degree two which are at least p-1 plus the sole vertex of degree 1

The reason for the weak inequality is precisely the assumption that you have at most one vertex of degree 1

in the case where all vertices are of degree two you get: sum of degrees = 2*p and that is greater than than the other case where you get exactly one leaf (vertex of degree 1)

yup, is it not what we assume at the start?

"Suppose there is at most one vertex of degree 1"

at most 1 means 0 or 1

[urban saddle]

if you want to find "at least one" in a venn diagram, is that Card(AUBUC)?

[weary tiger]

Wdym?

Can you be more precise

at least 1 = no. total possibilities - no. of cases with no one

[urban saddle]

if you have something like this

it would be E+G+F?

[weary tiger]

And what do you call by at least 1?

[urban saddle]

nvm, it would be the sum of all

[urban saddle]

a practical example, if these sets represent some newspaper and the cardinality is the number of people that read each newspaper, and I wanted to know the number of people that "at least read one newspaper"

[hardy remnant]

is O(n) the same as O(f(n))?

[unreal stump]

No

[weary tiger]

iff f(n) = n

otherwise no

[hardy remnant]

oh ok, i gotcha

[hybrid oxide]

if you want to know the cardinality of the resulting set, look up the principle of inclusion-exclusion

if you just want the set, then the set is just A union B union C

this is the formula on the cardinality of the union of 3 sets, look at the wiki page if you want more info on it

[hardy remnant]

so for a, why is O(f(n)) + O(f(n)) = O(f(n))?

[unreal stump]

Just apply the definition of O(f(n))

[hardy remnant]

[unreal stump]

Are you familiar with real analysis?

[hardy remnant]

thats what im studying rn

oh, im not sure what real analysis is, its the o notation theorems right?

[unreal stump]

Ok,nvm

Let's say a(n)<=c_1 f(n) for n>=n_0 and b(n)<=c_2 f(n) for n>=n'_0

Then a(n)+b(n)<=(c_1+c_2) f(n) for all n>=max{n_0,n'_0}

[hardy remnant]

what is max in this case?

[unreal stump]

maximum

[hardy remnant]

ill have to study more but thanks!

[obtuse lance]

@olive hamlet wondering if this can be answered by looking at eigenvalues with spectral graph theory

[olive hamlet]

hmm characterizing cycles with matrices is pretty hard, remember when we tried to do that

(as far as i have studied so far)

[obtuse lance]

yeah, somewhat, at least I was thinking we could think of the trace of powers being related, not sure

[weary tiger]

So I've come across some algorithm analysis in which I had a some line taking constant running time O(1) and a loop taking time O(n). So the running time is O(1) + O(n) = O(n+1) = O(n). So essentially, O(n+c) for any constant c is O(n) because if f(n) <= K(n+c)= Kn+Kc then making n sufficiently large we get that f(n) <= Kn right ? So that's how we can disregard constants in big-oh notation

Is my reasoning correct?

@stray reef you seem like you know you’re stuff

[stray reef]

uh

i... am stuff?

what?

if you wanted to ask me personally for help, i would've probably been snarky since i don't like being pinged out of the blue

but right now, i just cannot

too busy

[hybrid oxide]

this is a bit divorced from the formal definition of Big-O but in this case you should conceptualize Big-O more as a model that represents the growth of a function as its input gets very large

we can discard the constant because it doesn't affect the growth rate of our function. O(n + c) regardless of what the constant is is still going to have the same growth rate as an O(n) function regardless of c

[weary tiger]

the formal definition I have is f(n) is in O(g(n)) if there exists a constant C and a rank N beyond which f(n) is bounded above by C*g(n)

But I get you

O(g(n)) captures the asymptotic growth so constants can be disregarded

In view of the asymptotic behaviour

[hybrid oxide]

yeah i know the formal definition but i'm saying if you're looking for intuitive reasoning as to why that's the case you don't need to look at that necessarily

although if you are saying that your reasoning is more of a proof then yeah you're correct

[weary tiger]

Thanks !

[gusty echo]

Hi, I have a quick hw question in discrete math. I've been trying to solve these two sub-problems in problem 1 and I got different answers which I'm not sure if they're exactly right. Can anyone please help me out with these two questions:

for prob (a), I said 28 choose 15 [or] nCr = (28, 15) = 37,442,160

for prob (b), I said 7 choose 4 [aka, nCr = (7, 4)] or 7 choose 3 [aka, nCr = (7, 3)]

can anyone lmk if these are right or point out my mistakes please?

[hybrid oxide]

i'm very rusty on my counting so somebody please lmk if i'm wrong on this one but i believe (a) should be (28 choose 5) * (23 choose 5) * (18 choose 5)

i believe (b) would be 5^3

[gusty echo]

hm, ok, (a) makes sense! I get it now! But could u please explain why (b) is 5^3?

[hybrid oxide]

i broke it down into three steps where each step has 5 outcomes (one outcome for each truffle picked) and by the basic principle of counting there should be 5 * 5 * 5 or 5^3 total combinations but i am slightly suspect on that answer because it doesn't intuitively seem correct

let me work through it a little bit more

[gusty echo]

oh ok, sure! Idk I first though about it as 5! (aka 5 factorial) but I don't its right either

[hybrid oxide]

5! wouldn't work because 5! is the number of permutations of a set of 5 distinct truffles

[errant bear]

i first thought about it as 5! (im just exited)

[gusty echo]

oh sorry lol, I'm sometimes bad at counting lmao

[hybrid oxide]

after looking over it again i believe (b) would be 7 choose 3

[gusty echo]

oh, so the answer I originally had then?

[hybrid oxide]

yeah

[gusty echo]

I thought about it like this: 4 internal "boxes" + 3 chosen truffles is 7 per permutation

so, 7 choose 4?

or 7 choose 3?

[hybrid oxide]

yup it's just a stars and bars problem

i merely overthought it

[gusty echo]

oh ok, gotcha, cool, tysm!

[deep portal]

if converse is Q -> P is that also Q ∪ ~P

[weary tiger]

anyone available at 4 or 5 to help me with discrete math couple of questions

i jsut don’t know how to do them

[hardy remnant]

you can post them on here

like me
so i have a question about this inductive proof,
how did (n+1)! become n!(n+1)?

[civic horizon]

How do you define n!

[hardy remnant]

its a factorial

[civic horizon]

I know that

But ill just spell it out

(n+1)! = (n+1)n(n-1)...2

Now note that n! = n(n-1)...2

So (n+1)! = (n+1)n!

[hardy remnant]

huh, oh ok i got it

thank you

[smoky needle]

hello

so this is the question and

lemme send my answer

Is this correct answer ?

[obtuse lance]

,rotate

[obtuse lance]

no because your FSM will accept any non empty string since once it has 0 or 1 it moves from a_0 to a_1 and stays there in the accepting state

you need it to move out if it has an odd number of 0s or 1s

I'd recommend you label your states more clearly instead of a_0 and a_1 you write something like "even number of 0s and odd number of 1s" that would be one state

[smoky needle]

@obtuse lance i think i need more help sorry :( this time i did three horizontal state , i am going to send the pic but the more i think the more it becomes stupid machine

[obtuse lance]

you should have 4 states

depending on if 0 or 1 appears an even or odd amount of times

[smoky needle]

look at this nonsense

[obtuse lance]

,rotate

[obtuse lance]

ok first problem is the start state has too many arrows coming in and out of it

each state should have exactly 2 going out of it

remove the self arrow with 0,1

since if you gain a 0 or 1 you're no longer both even or odd

your arrows are not right but you have the right number of states

try to pick random examples to run through like 11 and see where you end up, since that should be accepted

also you should label your states like I described

you shouldn't try to be fancy and do q_even

there's nothing holy about writing it that way lol

say 'even 0, even 1' for the start state

'even 0, odd 1'

[smoky needle]

teacher asks this way im sorry :Sob:

[obtuse lance]

relabel it after you work it out

your teacher doesn't control your scratch work, that's a bogus excuse lol

[smoky needle]

omg i like label it this way maybe i am fancy -,-

lemme try again thanks for help

does the answer have more than one finish state ? @obtuse lance

[obtuse lance]

nope, only one

try to make examples to test yourself with, that will make guiding where to place arrows easier, one of the main things is knowing those 4 states we have

[smoky needle]

@obtuse lance this is it right ? if it is not im gonna cry

[obtuse lance]

@smoky needle ...

you got it perfectly correct 🤣

good job

[smoky needle]

you scared me with those dots..thanks a lot for helppp

[obtuse lance]

😛 yeah

you're welcome

[smoky needle]

empty U 0*(11)*0

Oh the stars...

Empty U 0 ** (11) ** 0

Omg what

[obtuse lance]

lol discord formats it

put ` on either side of stuff

*****

[smoky needle]

Too late hahah

Is this correct or should 1's be like (11)

[obtuse lance]

what's () mean here

I'm only familiar with * to mean any number, possibly none, of the symbol

[smoky needle]

Actually i am not sure too , it could be for just seperate them

[obtuse lance]

well you don't need them then in that case

0*11*0

so then start looking for counterexamples

so it should accept any number of ending 0s

yours looks like it must be only one ending 0

so that's not right

you can use parenthesis like (a*b)*

so in my example this means any number of strings with any number of a before b

like aaababb would work

since aaab, ab and b all are described by a*b

and I can have any number of them concatenated

[smoky needle]

So zero should have star too ? 0110*

Oh sorry i am dumb

[obtuse lance]

put ` before and after lol

[smoky needle]

0*11*0*

[obtuse lance]

ah that can't work because that doesn't necessarily end in 0

also it forces you to have a 1, and you don't necessarily need 1 either

examples: 00001 is accepted by your regex but is not by the FSM

0000 is accepted by the FSM but not by your regex

[smoky needle]

empty U 0* U 0*11*0*

[obtuse lance]

wait I'm writing my strings left to right

I think I might be causing confusion if you're reading them right to left or

maybe I've confused you by saying that haha

[smoky needle]

Okay yes left to right haha

[obtuse lance]

you still have the 00001 example

also we can do much worse

0101010101010 is also accepted by the FSM

[smoky needle]

How can it end with 1 ?

[obtuse lance]

1* and 0* means you can have no 1 or 0

0*1 is contained in this language

which is words like 1, 01, 001, 0001, ...

just choosing to remove the last 1*0* bit

gotta eat dinner I'm starving so gonna be gone for a while, if you got a question ask real quick

[smoky needle]

Isn ' t the FSM ends with zero ? When you gave 001 example i confused

Umm okay im gonna think for a while thanks and bon apetit

[obtuse lance]

the FSM does

your regex doesn't

0*11*0* means some 0s, a 1, some 1s, some 0s in that order

but the 'some 0s' means we could have no 0s at all

so it accepts just plain 1

[smoky needle]

Oooh i didn't know that

[obtuse lance]

there's also the notation (not completely standard) 0+ that means 'at least one'

so 00* and 0+ are equivalent according to my notation here

but maybe your book/teacher has some different way

anyways good luck keep at it, you'll need to use parenthesis cause remember your FSM accepts stuff like 001100001011100

[smoky needle]

Uhh if that teacher had any way,i would not be here...thank you a lot

empty U 0* U 0(0)*1(1)*0(0)* this is my final decision if it is not true just kill me

[visual pendant]

hey

need help w 10a) plzzz

[obtuse lance]

not gonna work cause you have 1s in one island between 0s

I think of it this way, we start out in q1 and can have any number of 0s, so we start with 0*

then once we get a 1, we can have any number of them and we are stuck not being accepted

until we get a 0

but we can repeat this cycle over and over again

(0*1*)*00* would be one way to write it

since everything in the parenthesis can happen, but we must always end in at least one 0

unless of course we just accept the empty string

[olive hamlet]

what did you try

[hybrid oxide]

all integers are within the rational numbers, but the set of integers is not within the rational numbers

the rational numbers is a set, but does not contain sets within it

only numbers

[deep portal]

is this right? so

conditional: ~p v q
converse: ~q v p
contrapositive: q v ~p
inverse: p v ~p

[hybrid oxide]

no

the contrapositive of p implies q is q AND ~p not q OR ~p (alternatively it is ~q -> ~p)

similarly the inverse is p AND ~q

[lament zenith]

Would this still be symmetric?

SoS

[sour arrow]

Not certain what I'm looking at haha

A symmetric relation? What's the set? What's the relation?

Is the set {a,b} and everything is related to everything?

Cause yeah that's symmetric

[lament zenith]

So you the domain is just {a,b}

The question is whether a domain for S

that is symmetric

it's composite is also symmetric

And it tests whether you can find a case where this is not true

Previously before it was twio sets R and S

on the same domain

Lets say {a, b, c}

They have a binary relationship on the same domain

R and S

is it true that SoR is going to also be symmetric

But I found that its not true, with this example

Both R and S map a binary relationship over the same domain

But there composite does not maek it symmetric, so its anti-symmetric

Therefore the statement is false

Just basically, find a way to break the statement

Whilst you're here, the transitive definition applies if and only if three elements are related therefore the first relationship relates to the last

is this graph considered transitive?

Since aRb and bRc, therefore aRc which it does

And transitive for any binary relationship is if three elements satisfy the first condition

(xRy and yRz)

Therefore we can determine if its transitive or not, so for this example we can't do

bRc since cRelates to nothing else

So we break the first condition and continue along to any three elements that do relate? right

[sour arrow]

Composite? Do you mean complement?

[lament zenith]

no i mean composite

[sour arrow]

Oh lol I'm understanding what SoS is now haha

You're looking for a symmetric relation, that when composed with itself, is also symmetric

[lament zenith]

Yeah

I probs should've made that more clear

/ mentioned it

[sour arrow]

In your example, S is symmetric because ASB implies BSA
And SoS is also symmetric because ASA implies ASA, and BSB implies BSB

[lament zenith]

Yeah bec I used this as an example

Whether if its reflective its also symmetric

For that SoS

Since its symmetric if neither A nor B are related to each other* is true

Also for this example or what I tried to mention about about transitive

R and S are both transitive, but is SoR transitive also* in this case

Since the definition is if any three elmenets who are releated to each other , have some relationship towards them

So, aRb and bRc, then aRc

And thats IF and ONLY IF aRb and bRc

[weary tiger]

#groups-rings-fields

[pale epoch]

tbh here would've been fine

(or #proofs-and-logic)

[weary tiger]

Is my proof that countable union of a chain of sigma-algebras might not be a sigma-algebra correct?
i constructed the following sequence of sigma-algebras over the ordinal ω+1: for each natural n, An is the sigma algebra generated by {0, ..., n}. Then the union of all those is not a sigma algebra cuz ω is not element of any of those sigma algebras but ω is the union of all naturals.

[gritty crescent]

This might draw response in #foundations I guess.

[weary tiger]

it's not really foundational stuff i think

[pale epoch]

is the question just to show that the countable unionof sigma algebras is not a sigma algebra?

isn't that already wrong in the finite case

[weary tiger]

i mean

countable union of a chain* of sigma algebras

[pale epoch]

ah ok

probably ask in #advanced-analysis

[smoky needle]

hello

my question is

for example

Can we use A or B more than once

we can not right ?

[stray reef]

what do you mean?

are you asking whether or not the rules A -> 0A1 | 2 and B -> 1B | 3A are one-use-only?

[smoky needle]

yes exactly

@stray reef

I mean it should be s -> AB -> etc

not S -> ABA or ABB an so on

right?

ı just wanted to be sure because the questions teacher gave us almost all of them not in the L (G)

[stray reef]

S -> AB means S -> AB

but in general no these rules aren't one use only

[smoky needle]

how do u answer this then

i wrote this string is can not be in L(G)

@stray reef

[stray reef]

do you have a proof for that?

[smoky needle]

wait a sec

photo is coming

I couldn't find the string with these rules so i figured it is not in L(G) @stray reef

[stray reef]

well just because you couldn't derive it with those rules does not by itself mean it's not in L(G)

maybe you just overlooked something

[tight lotus]

i think u can consider the necessary ratio of num 0s to num 1s

[stray reef]

to prove a string is not generated by a cfg, the usual method (iirc) is to find some property shared by all strings in L(G) which your target string does not have

i can think of the following:

the only way to get zeros at the beginning is to apply the rule A -> 0A1

and to get four zeros at the beginning we would have to apply it four times

meaning we would have four 1s in a row somewhere in the string

but we don't have that

[smoky needle]

so it is not in the Lg?

[stray reef]

are you more concerned about getting an answer than about being sure your answer is the right answer?

i mean, yes, that's what i demonstrated: our string is not in L(G)

[smoky needle]

no i just want to be sure

thank you

[lament zenith]

For graph powers, would this mean that

If I want to find a graph of a power lets say R^4

I would do R composite R ^3

[crystal lichen]

L = {w | w is of the form x01y for some strings, x and y consisting of 0's and 1's only}
Are the following strings accepted by this language, if not then explain why the string is not accepted:

1. 01

Hi. What should i write for the first question ? Teacher didn't give us examples so i do not have any idea

[crystal lichen]

@stray reef

[hardy remnant]

is there a name for nlogn?

i think i saw that nlogn can be shortened to logn instead so itll just be part of logarithmic?

[pale epoch]

i don't think there is a special name and no it cannot

[mental pecan]

its either like

linear-logarithmetic

or something of the sort

yeah lol

its "linearithmic"

http://catb.org/jargon/html/L/linearithmic.html

[mental pecan]

and it can't be shortened bc O(lgn) < O(n) and it isn't multiplied by a constant, instead something that increases as N increases (b/c it is literally N)

so you can't get rid of the constant b/c there is no constant

[light ginkgo]

log linear

thats what I have heard

[hardy remnant]

Thank you all for the help!

[smoky needle]

hello again

Design a deterministic FSM (transition diagram) over the alphabet {0, 1} that recognizes the regular
language of all strings that contain the string 001 as a substring. For example, 0010, 1001, 11111001111
are all in the language, but 11 and 0000 are not.

does this look correct

omg no

how about now

photo is coming

[obtuse lance]

this is fine as long as you're allowed to make a nondeterministic finite state machine

fortunately if you need to be deterministic, there's a way to turn every nondeterministic finite state machine into a deterministic one

[smoky needle]

what i did was non - deterministic right? and how can i turn it to deterministic i don't know @obtuse lance

[obtuse lance]

yeah you can tell because your start state has two choices for 0

deterministic means only one choice for 0 and 1 leaving

[smoky needle]

ooh okay let me try

[obtuse lance]

sure, might help if you read about it first

https://www.geeksforgeeks.org/conversion-from-nfa-to-dfa/

also you need some more states because those middle states need to go to a dead state

cause as it's written it doesn't say what happens when you're in that 001 if you get something different

which is fine for nondeterministic btw

[smoky needle]

,rotate

[smoky needle]

@obtuse lance

[tight lotus]

looks good to me, tho maybe u should label your initial and terminal states?

can't rely on drawing it left to right since this is no more than a labeled digraph

[smoky needle]

Oh yes i will label it thank you @tight lotus

[gusty echo]

can anyone please help me out with this:

I got this but I'm not so sure if this is right:

so would this be bipartite?

[weary tiger]

Bipartite means you split the set of vertices into two disjoint sets such that every edge has exactly one vertex in the first set and the other in the second set

[weary tiger]

this is bipartite

{a,c} is the first set and {b,d,e} is the second

[gusty echo]

ohhh, ok, gotcha, makes sense! Yeah, I drew this diagram based on the def of bipartite but wasn't completely sure if it was bipartite lmao

[weary tiger]

Another way you could justify bipartition of a graph is through a proper 2-colouring

[gusty echo]

oh yeah, ik that way! Thx!

[hardy remnant]

g(N) = N1.5, then to decide which of f(N) and g(N) grows faster, one really needs to
determine which of log N and N0.5 grows faster. This is like determining which of log2 N
or N grows faster. This is a simple problem, because it is already known that N grows faster
than any power of a log. Thus, g(N) grows faster than f(N).``` 
when theyre talking about which function grows faster, does that mean which one takes the most amount of time to finish?

[pale epoch]

no

[hardy remnant]

wait, im stupid, i guess its growth is talking the speed of which it takes to finish right?

[pale epoch]

finish?

[hybrid oxide]

it's about which function's cost scales faster as the number of inputs grows

there is no "unit" for big-O, it's just an asymptotic growth model

it "grows" faster because the output of the function becomes large more quickly as its input becomes larger

[hardy remnant]

ok, so the green line grows faster then?

[hybrid oxide]

no, the purple line does

[hardy remnant]

frick

ok

got it

[hybrid oxide]

notice how you're approaching higer output values even with a smaller input

[hardy remnant]

i see

damn i lost all my critical thinking after taking a year off school lol

[light ginkgo]

SLOPE

[hardy remnant]

then that means i did this wrong, it should be the other way around

[hybrid oxide]

no you don't have it reversed, the order is just generally out of wack

the hierarchy for big o is as follows:
constant: O(c) where c is a constant
logarithmic: O(log n)
linear: O(n)
semi-logarithmic: O(n log n)
algebraic: O(n^c)
non-polynomial with a base of 2: O(2^n)
factorial: O(n!)

there are others not mentioned

notably algebraic functions can technically be variable growth depending on the value of c

[hardy remnant]

feels like itll be hard to find the growth rate of these functions without plugging them into desmos

[hybrid oxide]

i mean on face the question is just a bad question and doesn't really properly get at what the point of big-O is

but either way you should be able to rank most of these without external graphing help

[edgy vine]

@hardy remnant we used to do l'hospital to compare them.

[hardy remnant]

i do not remember my l'hospitals rule

[edgy vine]

The rule is very simpel. One yt video should explain how to use it. You know it must account that f(n) < c * g(n) <=> c > f(n) / g(n) for n > n0. Using l'hospital you know which function goes faster, and can rank those two functions by this.

And you know if a(n) < b(n) and c(n) < d(n) => a(n) < d(n) for n>n0

so you need less comparisons in total, but for so many terms I think you are allowed to rank some by intuition.

[errant bear]

why is there 20 things it wants u to order

also yes your list is very out of order

[edgy vine]

;_; its 19

[errant bear]

19=20

[weary tiger]

Any hints how to show that in any convex polyhedron sum of triangle faces and vertices of degree 3 is greater or equal 8?

[warm wren]

hello.hello guys

I someone online here

Is*

nobody is online akanob

[civic horizon]

wat

[gusty echo]

can anyone please help me out with this proof problem:

I wrote half of it but I'm not sure if I'm heading in the right direction

I'm trying to solve step 4 of the problem and I'm stuck the number of vertices of and edges of T1 union T2 in my graph. The number of vertices & edges seem to be different for G, T1, T2

anyone have an idea please on how to solve this or if I'm drawing the graphs correctly?

[pale epoch]

please stick to one channel

(anyway, seems they got help in #proofs-and-logic)

[gusty echo]

oh I'm so sorry! I'm new, so I didn't know about that rule

[pale epoch]

read #❓how-to-get-help for further reference

[gusty echo]

ok, tysm!

[weary tiger]

Not sure where to put this really but I guess here is as good as anywhere

We know that computable numbers can be put in correspondance with Turing machines which in turn are countable, and because the reals are uncountable that leaves most reals as uncomputable

Is there another important or interesting class of uncomputable numbers that is countable? One so that it would be very nice to say that "actually, that's countable too, so most reals are uncomputable AND [property X]"

[unreal stump]

Hint:Infinite sets

[unreal stump]

Well, for your original question just consider f(n)=2n

That grid shows there is a Bijection between N and Q

[stray reef]

a counterexample to your thing would consist of two sets

[last timber]

consider smallest infinite set N

as buncho pointed f(n)=2n would work

[unreal stump]

On N to N

[stray reef]

i dont get how f(n) = 2n
isnt onto for every one-one

you're getting things mixed up.

you want to show that the claim "every one-one function from A to B is onto" is false

yes?

@spark silo

and to show that it is false

we need a pair of infinite sets, A and B

and a function which is one-one but not onto

just one function that is one-one but not onto

yes?

do you understand this?

okay let's tackle these one by one

the function f: N -> N defined by f(n) = 2n is not onto because its range does not include the number 19.

to say the doubling function is onto is to say every natural number is even.

which is clearly not the case.

as for how one would know to use infinite sets:

looking at finite sets alone, one would be left with the impression that the claim is true

and in fact, if you replace the "sets" with "finite sets", it is true

but not all properties of finite sets carry over to infinite sets.

if you did f: {0, 1, 2, 3,} -> {0, 1, 2, 3} f(n) = 2n
this wouldn't be a function at all

what do you think f(3) would be? 6?

6 ∉ {0, 1, 2, 3} yknow

[stray reef]

how would i go about proving the set Z+ * Z+ * Z+ * Z+ is countable with a grid?
you would need a four-dimensional grid

i mean, yeah, you could do it via (Z+)^2 i guess

[last timber]

@spark silo just usual diagonal approach

or

if you wish

and you have proved that countable union of countable sets is countable you may even not to construct bijection

[pale epoch]

i suggest using x for cartesian product

this was fine though

the image i mean

except that Z^+ probably does not include 0?

as in that it depicts Z+ x Z+

i see

your second image is something called a group table

just a depiction of Z+ x Z+

as a set

you used the group table to argue about the group operation (in this case addition)

if you want to talk about things like cardinality of the set

then the group operation does not matter

you can for example see that the second table includes every element multiple times

just noticed a mistake in the first pic though

one of the (1, 0) should be a (0, 1)

then it includes every element just once

and that is better suited to argue about cardinality

its a bit hand-wavey

and it would prove $\abs*{\bZ^+ \times \bZ^+} = \abs*{\bZ^+}$

[vital dew]

Lochverstärker

[pale epoch]

you have to be careful where you place your | |

but this is the standard argument

Z+ * Z+ = Z+ is not true

(1, 1) is an element of the LHS but not of the RHS

you can apply the same diagonalization argument 3 times to show that the cardinalities of your sets are the same

more formally you have a bijective function $f\colon\bZ^+\to\bZ^+\times\bZ^+$ and then you can use the same grid method but label the rows with $f(1), f(2), f(3), \dots$ and the columns with $1, 2, 3, \dots$

[vital dew]

Lochverstärker

[pale epoch]

but this quickly becomes a typographical nightmare

well

with an inductive argument you can show that this is true more generally

the key thing that is happening here is that the composition of bijections is bijective

like, that argument gives a bijection $\bZ_+^4 \to \bZ_+^3$

[vital dew]

Lochverstärker

[pale epoch]

and then you just apply it multiple times

until you get what you want

but nobody thinks of it that way

whats the exact question?

ok

this works too and is more concrete

but imo your grid method is fine

you would just do it to show |Z+ x Z+| = |Z+|

and then say "do it two more times"

well, not sure i can help you understand it better

the idea is that the line you draw through that grid gives you an order

because you want to show |Z^4| = |Z| and not |Z^2| = |Z|

but you need to apply it twice more

no my point is

you want to work with |Z+ x Z+ x Z+ x Z+|

and each application of this "grid argument" gets rid of one copy of Z+

[last timber]

has loch explained to you diagonal approach?

[pale epoch]

yes

[last timber]

yes

[pale epoch]

honestly try to understand that first

[last timber]

like you cannot just enumerate rows

since rows are infinite

[pale epoch]

the yellow zig zag line gives you an order in which you can enumerate all the elements of Z+ x Z+

[stray reef]

may i suggest a certain way to biject (Z+)^4 with Z+ without having to apply the grid argument three times

[last timber]

(unless you have proved that countable union of countable sets is countable which i assume you have not)

[last timber]

would it be polynomial in 4 variables?

[stray reef]

no

[pale epoch]

they posted a different proof above ann

[stray reef]

i was going to suggest ||total-first lexicographic ordering||

[pale epoch]

but like

i think you should first try to get the grid argument @spark silo

there is probably good video about that

[last timber]

also there is good combinatorial approach which is essentially similar

[stray reef]

actually now i have my own question but im gonna wait until homeyworkey is done

[pale epoch]

(its called cantors diagonal argument)

specifically this is the first one

[pale epoch]

i also think this is a good approach to the question (better than the argument in your screenshot and the diagonalization one)

but getting the diagonal argument is benefical still

sadly im not equipped to explain it better over text

do you have a book?

[last timber]

i mean gimme a sec

ah

i forgot where i saw brilliant visualization of cantor diagonal argument

anyway

not necessarily pattern

any bijection works

patterns just are easy

so ok @spark silo imagine grid Z+ \times Z+

you want to enumerate its elements

so to construct bijection

you cant just enumerate row by row

since each row is infinite

similar with columns

[stray reef]

can y'all ping me when this is done?

this discussion made me come up with a seemingly fun problem but i dont wanna interrupt

[last timber]

so what you do is that you first enumerate first element of first row, i.e, (1,1), then you move to an element from right

(1,2)

yes

[last timber]

yes

sorry i will be slow since have other doings

but anyway

from (1,2) yo go to (2,1)

so ok

what i am going to suggest now

is that you from (2,1) would go not to (3,1) as picture suggests

but to (1,3)

that is we enumerate like (1,1)->(1,2)->(2,1)->(1,3)

is that clear? @spark silo

i hope yes, otherwise say

[last timber]

so from (1,3) we again move to (2,2) and then to (3,1)

because i can suggest you pattern now

i wanna suggest you procedure which is the following

each time we enumerate point of the form (1,n) we are then going to (2,n-1), (3, n-2),...(n, 1)

@spark silo is that clear?

and after we finish it we are moving to point (1, n+1) and then repeat

so this is basically algorithm by which we do enumeration

i can form it in some form of pseudocode if you wish

but the point is that actually it allows us recursively to find formula

so consider we are at point (n,m)

we have come to it from (n-1, m+1)

and to it from (n-2, m+2)

by construction of our algorithm

so actually we have came to (n,m) from point (1, n+m-1)

hmm

oh ye

look

point (n,m) is m-th in enumeration along line (1, n+m-1), ..., (n, m) if i am not wrong

(2,1) is second in (1,2+1-1) and
(3,1) is third in (1,3+1-1)

ye seems correct

[last timber]

@spark silo so here we go

(n,m) is has m-th number in enumeration from (1, n+m-1)

so do you agree that its total number in our enumeration for Z+ times Z+ is m + number of points enumerated in lines (1,1), ..., (1, n+m-2)?

by line (1,k) i mean sequence (1,k)->(2,k-1)-> as defined before

geometrically it would be triangle which is important

forget this triangle argument lol

anyway

[last timber]

@spark silo this important

let us count how much points in total we cover in line (1,k)

you would be surprised

but this number is exactly k

(1,k)->(2,k-1)->...->(j, k-j+1)->..->(k, 1)

so each line covered before has k points

thus
number of points enumerated in lines (1,1), ..., (1, n+m-2) equals
1+2+...+(n+m-2)

would you find this sum by urself?

no i mean it is just sum of first n+m-2 natural numbers

,w 1+2+...+n

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#4407

[last timber]

plugging n+m-2 gives

(n+m-2)(n+m-1)/2

and adding m which we forgot gives

(n+m-2)(n+m-1)/2+m

that is

f(n,m)=(n+m-2)(n+m-1)/2+m is enumeration for positive integers

voila

@stray reef ig we are dome here

btw @stray reef how was defense?

was it good?

[stray reef]

yes

[last timber]

nice

[stray reef]

anyway ok this problem that i came up with

Let C be a set equipped with a strict total order <, and suppose there exists an element in C called 0. Assume that the following properties hold:

1. For every x in C, there exists an element s in C such that x < s but no other s' satisfies x < s' < s. This s is called the successor of x, and is denoted S(x).

2. For every x in C \ {0}, there exists an element p in C such that S(p) = x. This p is called the predecessor of x, and is denoted P(x).

Classify all sets C satisfying properties 1 & 2 up to order-isomorphism.

[tame arrow]

im learning to write proofs using induction and I want to kms

[stray reef]

jack could you move to #proofs-and-logic please

[tame arrow]

oh shoot you right my bad

[stray reef]

anyway, ok, so my conjecture for this is that the general form of $C$ is $$C = (S_1 \times \bZ) + \bN + (S_2 \times \bZ),$$ where $+$ denotes the sum of total orders, $S_1$ and $S_2$ are arbitrary total orders and the products are equipped with lexicographic order

[vital dew]

Ann

[last timber]

wait

but like

ah no

well C should be less than R

[stray reef]

how so

[last timber]

like since completeness is negated by 1.

[stray reef]

C could very well be uncountable

$\bN + \bR \times \bZ$ will do

[last timber]

[vital dew]

Ann

[stray reef]

nobody said we can't have a continuum of Z-sized 'sections'

[last timber]

well 1 and 2 joined together make C well-ordered set if i am not wrong

[stray reef]

not necessarily

N + Z is already not well-ordered

if you start anywhere in the Z part, repeatedly taking the predecessor will never take you outside of it

[gritty crescent]

||Natural numbers fit the bill, but does this work for integers too? (2) doesn't seem to forbid 0 having a predecessor, so I'm not sure if it can be isomorphic to C.||

[last timber]

but then you would want S_1 times Z to have minimal element

no?

[gritty crescent]

Oh, you already released the answer

Definitely...not close

[stray reef]

no?

why

[last timber]

oh wait somehow i read 2 as 0 does not have predecessor

[stray reef]

everything other than 0 has a predecessor

actually yeah i should say 0 doesnt have a predecessor

that was my intention

but just becase 0 has no predecessor does not make 0 minimal

[last timber]

oh anyway ye

Z+N

[stray reef]

you can have stuff before 0 just not a direct pred

[last timber]

but why we can't then make C to be sum not only of three orders but of arbitrary amount

[stray reef]

the arbitrariness is encapsulated in S1 and S2

[vital dew]

Commander Vimes

[stray reef]

A×Z + B×Z is iso to (A+B)×Z

[last timber]

well then it looks to be true

wait

we may not need Z here

we can take some limit ordinals here

[stray reef]

we can?

[last timber]

or no, hmm

well ordinals are well-ordered iirc

[stray reef]

i was under the impression that every element not of the form S^n(0) generates a Z-sized portion around itself

[last timber]

and the problem is to cut the class of ordinals to make it set

which we can achieve by taking limit ordinal

and hmm i am not sure that cond. 1 is satisfied for ordinal numbers

well yes, it does

since assume a is ordinal

then b = a U {a} = S(a) is minimal ordinal s.t a < b under ordinal numbers ordering

[stray reef]

are you talking about the entire class of ordinals

[last timber]

and each limit ordinal satsifies 2

[stray reef]

limit ordinals other than omega do not satisfy 2

[last timber]

no need to take entire class of ordinals

[stray reef]

not even omega*2 has property 2

omega*2 = {0, 1, 2, ..., omega, omega+1, omega+2, ...}

omega has no pred

[last timber]

ah

you want 0 to be unique

well yes then we have to reduce it to omega being smallest limit ordinal

so just N

[last timber]

well then it seems that this is true

but removing uniqueness of 0 we can just do ordinals

hmm

but would it work with cardinals?

or not cardinals

alephs*

hmm

there again iso to N

[lament zenith]

Does anyone know some resource about partial orders like a particular video, I'm still unsure how to really approach or conceptualize this understanding of a minimal element and maximal element

Like for example this question

I'm given this in the material to help explain it

And the weird symbol that is denoted to express aRb as a<=(curley) b

My only guess is since its partial order on the set (a,b, c, d, e, f, g). Would that mean the maximal elements in the partial order is just d. And the minimal elements in the partial order is a?. Then everything comparable to d is compared to ever other set of elements

Sorry it would be d, and g. for maximal; and minimal will be a and f. Unless I got this interpretation wrong

<@&286206848099549185>

Wait, unless the definition applies for this case. If there is no y =/ x then x is at most y. So a is at most b, and b cannot be greater than a. Therefore a is the maximal element since no element is above a. And this also applies to f.

Would that then mean that d and g would be the minimal elements since no element can be below d or g. For this given partial order set

[knotty gulch]

would someone be able to help with a problem on injectivity and surjectivity please?

[lime fossil]

[knotty gulch]

i have to find a function that is surjective but not injective but both sets involved have to be countably infinite. i know what injective and surjective are but im not sure how to go about creating an example when they have to be countably infinite

[stray reef]

start by picking two countably infinite sets of your choosing

[knotty gulch]

would something like 2x where x is a natural number constitute a countably infinite set?

since it corresponds 1:1 with the naturals

[stray reef]

{2x | x in N} is a countably infinite set, yes

but you're already making this more complicated than it needs to be.

[knotty gulch]

oh ._.

oh waitt i have an idea

if i have f defined as y=x/2 then i define one set as being

the naturals and one set as being

nvm

xd

it worked when i had finite sets

or actually no it does work

since the odd values

will not correspond to any natural

in the other set

hmmm

thanks

[stray reef]

what are you thanking me for?

[knotty gulch]

well i was thinking too much

and it helps to just be able to

talk through my thoughts aloud

[warped pecan]

Does anyone know how to approach this

For reflexive I know we add n pairs but not so sure what is the case for symmetric and transitive

[pale epoch]

i have no idea what this means

what do you know about equivalence relations?

[weary tiger]

What is even the cardinality of an equivalence relation?

The number of its equivalence classes?

Minimum number could be anything no?

[unreal stump]

nvm

Cardinality of relation is the numbers of elements considering the relation as a set

Answer is n

[pale epoch]

n is the maximum, not the minimum?

[civic horizon]

Is it not the minimum

R has to contain all tuples of the form (a, a)

[pale epoch]

oh the relation is the set of tuples lmao

nvm me

[mental pecan]

doesn’t it HAVE to be n,

b/c equivalence is both sets have equal cardinals ty

[civic horizon]

an equivalence of sets and a equivalence relation are distinct

[mental pecan]

ohhhh my b

[warped pecan]

How is n not the minimum?

[pale epoch]

what's your argument?

[lament zenith]

can anyone help me out with the question i posted above, im not sure if im right

[lament zenith]

...

[tame rapids]

Hello (first time question) I am a programmer and I'm working on a video game in my spare time. I'm long out of school and could use help in a graph theory question I ran into. My levels are represented as special graphs that I want to pre-generate, but I need to be sure there are no duplicates--that is, no ISOMORPHISMS. However, the verticies have a secondary attribute that is important to maintain.

For example, a->b->c is isomorphic to b->c->a when all nodes are equal, but a!->b->c is NOT isomorphic to b->c!->a as before, since now ! is a secondary attribute, and its location also matters.

Is there a name for this kind of problem?
The most novel thing I came up with as an idea to represent this is to enumerate the secondary attributes, and give the same number of self edges to a vertex corresponding to which secondary attribute category it falls into. While this may work in this case since I have no self-edges in the original graph, but what if I did?
My "solution" feels like a hack, and I was wondering if there's a better, more general way.

[obtuse lance]

looks like it might be related to graph coloring, which is counted by a graph's chromatic polynomial, if you imagine a vertex having a property or not as different ways of coloring with 2 colors

[vale token]

ahh, so this would be like testing if the graph is structurally isomorphic, and the node colors match up?

like for instance, nodes with a ! would be a different color from nodes with no !, in their example above?

[obtuse lance]

yeah

[vale token]

@tame rapids does that help at all

[tame rapids]

isomorphic graph coloring, now I have a topic to read about. Thanks! (Any tips where to find algorithms for determining this?)

[weary tiger]

Im confused on A x C

{(x, empty set), (y, empty set)}

Is what I think

Is there any reason for A x C = empty set or is it just the way it is

[robust mango]

C has no elements

[stray reef]

$C$ is not ${\rien}$

[vital dew]

Ann

[stray reef]

$C$ is $\rien$

[vital dew]

Ann

[weary tiger]

I don't understand this proof

specifically the "let b be an arbitrary element of B"

why does he do tha

t?

if he shows its true for an arbitrary element of B, he will show it for every element of B

Because b was arbitrary, so it works for ANY element of B

But not every element of B is in Dom(R^-1)

cause $Dom(R^{-1})\subseteq{B}$

[vital dew]

Reaper

[weary tiger]

I would understand if he just let b be an arbitrary element

Cause that's for subset proofs

So yeah its because both Dom and Ran are subset B

b may not be in Dom(R^-1)

But if it is, then it is also in Ran(R) by the argument above

and vice versa

So how come he starts with that then? Like the order seems weird

[weary tiger]

Ohhh ok

Hmmm

That's really confusing

Yeah I think it's to make it quicker, but I agree, I would prefer to take b in Dom and show it implies Ran and do the reverse

But this proof also got some idea which might be worth to understand

What idea is that?

well the proof that you take any b in B and if its not in dom or ran then you dont care, but if it is then you show equivalence

but ye you got it

What's a different way of proving this?

I mean its the same pretty much, just take b in one set and show its in other set and the other way around

probably there are other proofs

just forget about it

what book is this?

Let b be an arbitrary element of Dom(R^-1) then b is an element of B. If b is in Dom(R^-1) then there exists an a in A such that (b,a) is in R^-1 but that means (a,b) is in R and so b in Ran(R)?

how2proveit?

[weary tiger]

How to prove it

Yeah

[weary tiger]

ye but its actually the same thing as ain the book

Hmm

yeah I guess

because your "then" is actually an iff

how?

how can it be an iff

definition

b in DomR^-1 iff b in B

No way...

That's an actual definition??

wait no maybe im tripping

u right

ure right

Relations kinda hard ☹️

yea especially if you dont have many examples

its something you get used to

at least in my case

but ofc dom(r^-1) subset B not equal

it's also kinda confusing cause b is used in two different ways

whatever

Ill figure it out eventually

Lemme try some exercises

btw also you can ask c4t about this stuff, I think he recently did this chapter or is currently studying it and I'm sure it could be helpful for both of you

c4t?

yes

yeah I'm just going through the book

I dont want to ping him

I finished ch2 ch3 and now I'm on ch4

but ye theres just one c4t

ok

Maybe I'll add him

Wait I don't see him

this one

okok

[feral osprey]

Is there a way to prove that if |G| = p which the id is e.
than for every g in G there exists an int k which g^(k*o(g)) = e .

[unreal stump]

How are you defining o(g)

Because if it's the order of the group <g> g^(o(g)) is clearly e

[feral osprey]

right