discrete-math

[coral parcel]

The columns you already have look correct.

Sorry, I was responding to crypto_addict.

[ebon quest]

Oh mb

[coral parcel]

Never got the hang of tableaux, so can't help you ...

[ebon quest]

Dang, ok

[fiery pond]

Well, you can say that for every possible outcome of a, b and c it is the same for both propositions

[wicked basin]

i am not sure how to do dis

so i know that a set with n elements has 2^n subsets, and a subset with size 3 elements of an n element set is (n choose 3) = n!/(k! * (n-k))!
but idk where to go from here

[weary tiger]

I mean n choose 3 is subsets of n element set of size 3

obviously there are less of those than all subsets

[wicked basin]

ok

but like

how do i prove it without using induction?

[weary tiger]

I just did lol this is a proof

[wicked basin]

part b is when u actually prove by inductoin

which i know how

but idk how to prove without induction for part a

[weary tiger]

hello can you see my messages

[wicked basin]

o ok so i simply say n choose 3 is subsets of n element set of size 3, which will always be less than the number of all subsets of an n element set?

cuz it seems intuitive but not really a proof ya know?

[weary tiger]

okay then prove that for n>2 element set there is a subset of size less than 3

then you will have at least n choose 3 + 1 subsets in 2^n

[wicked basin]

oh ok. thanks.

[wicked basin]

for this, i got 4 * 3 * 2 * 1 *4 * 4 * 4

am i right?

[coral parcel]

That looks like a job for inclusion-exclusion.

Your expression seems to be the number of painting schemes where the first four rooms all have different colors, but that doesn't count, for example, the solution (red,red,white,white,blue,blue,yellow).

[wicked basin]

o

thx

[silent hinge]

i am kinda havin a hard time trying to figure out how to express "but is a ..... "

i get the "If" and the "then" part

[coral parcel]

"but" is just an opinionated way to say "and".

[silent hinge]

i know for a fact this is wrong

ooooohhhh shit

p and (r or s) -> ~q

[tidal tulip]

can someone explain how they did this proof

they assume ExVy P(x,y) is true and let x=d0

so does the expression become

Vy P(d0, y) -> Vy (d0,y)

and then they let y=d

then they get

P(d0, d) -> P(d0,d)

but that makes no sense lol

so how do they do the proof

[young barn]

I read this as f has a domain incuding all Real Numbers which maps to a codomain (range) of all Real Numbers by f(x) = x^2

[haughty garden]

codomain isn't quite the same as the range of the function. The codomain can be a larger set that contains the range

[ember obsidian]

@young barn ^

here codomain is R but image (range) is set of nonnegative reals

[tidal tulip]

i dont understand how the book proved this expression is valid, can someone explain in better detail

[tidal tulip]

is it true because

it assumes ExVy P(x,y) is true.

then it says there is a specific x such that P(x,y), call it d0

so now you can rewrite VyEx P(x,y) as Vy P(d0,y)

and in the Vy P(d0,y) part you know from the hypothesis that any y works, so you end up with P(d0,d)

which is the same proposition as the one in the hypothesis and since we assume it’s true, we have it’s true for the conclusion as well

(ie we now have P(d0,d) -> P(d0,d) and we assume P(d0,d) is true from the hypothesis which we obtained from the substitutions we made, so we end up a with True -> True statement, which is True).

and in english it’s true because it’s saying

you assume ExVy is true so you have a fixed x that’s true for all y

which also means for all y there is that fixed x

is that it?

[crude mango]

Basically yeah

It's not the most complicated thing

We know there's an x such that for all y it's true

And we can prove that there exist an x for any y such that it's true

And that x is the one we already chose

[tidal tulip]

awesome, thanks!

[thin furnace]

is there a way I can write "x is prime" with just symbolic logic?

[pale epoch]

can you be more precise with what you mean by symbolic logic?

[broken steppe]

i dont think so...

[pale epoch]

$x > 1 \land \forall a, b(x = a\cdot b \implies a=1 \lor b=1)$

[vital dew]

Lochverstärker

[pale epoch]

is this symbolic logic for you?

[thin furnace]

oh yeah, it is

I was about to send what I think could work

[broken steppe]

ur better of writing x part of primes

[pale epoch]

this is formalizing x prime in peano arithmetic

you can get rid of the ">" if you want

[broken steppe]

idk think there is a easier way is there?

[pale epoch]

it depends on what you mean by easier

but you do need quantification i think

[thin furnace]

From what I was writing, I ended up with something like this (a bit longer even)

[pale epoch]

there are other ways you can do it

but i am pretty sure you will always need a quantifier

[thin furnace]

Thank you for your help! @pale epoch @broken steppe

[broken steppe]

happy to help

[thin furnace]

oh, got it!

[ebon quest]

Can someone check if these are correct?

Just wanna make sure I’m doing this right

[silent hinge]

What am I doing wrong? I really dont understand where I am failing

The computer is telling me that everything is true

[pale epoch]

false implies anything is true

[scenic birch]

I am trying construct a set of n numbers whose square sums is of order n^3 where each step i can find two numbers with difference 2 and then the bigger gives 1 to the smaller untill they all are equal
I tried ( n, n-1, n-2, ..., 1)
Although i could show with examples I can find difference of two. but I couldn't prove it
Any hints on how to prove it or if even it is correct? how to construct such a set of numbers

[silent hinge]

ok focusing on the second and third col, for the first row i see it as "if true, then true" output: true

for the second row "if false then true" output true

for the row number 4 "if false then false" so output false

this is how i am thinking about this

[pale epoch]

thats not how implication is defined

F -> X is always true

[silent hinge]

can you share a youtube video/article with me that can clear my confusion and further my understanding?

[pale epoch]

well, it is kinda just defined like that

the reason behind it is the principle of explosion

"if you assume something false, you can conclude anything"

there is an example here https://en.wikipedia.org/wiki/Principle_of_explosion
maybe that helps

[silent hinge]

I now finally understand that when the statement is false only when the p is true and the outcome is false

it took me a while to get it

now i see why everything is true on my table

[pale epoch]

nice 👍

[scenic birch]

Any help on this ?

[fiery pond]

Does anyone have experience with indexed union and intersection sets?

[ebon quest]

Can someone check this?

[pale epoch]

by checking the truth table

[severe swan]

Can someone explain this to me?

Give a truth assignment to variables p, q, and r to make the following proposition evaluate to true
p /\ ! q /\ r

p = true or false
q = true or false
r = true or false

How can I find out if p, q, and r are true or false?

Table

p q r !q !q/\r p/!q/!r

T T T F F F
T T F F F F
T F T T T T
T F F T F F
F T T F F F
F T F F F F
F F T T T F
F F F T T F

[haughty garden]

You should be able to read off the truth table to find p, q, r. You found the assignment that makes your statement true

[muted socket]

if I have a function f, and a real number c, I can define a new function cf, that's just defined by cf(x) = c*f(x), right?

Question is, how do I find the inverse of such a function?

[craggy juniper]

do you mean f(c*x) = c*f(x)? because those two are identical no matter what

[muted socket]

In this case, the function I want takes sets as inputs, so I can't use that here

sets as inputs, real numbers as outputs

[craggy juniper]

oh then i shouldn’t talk here lol

[muted socket]

basic set theory is a real monster, my man

i cant do this

[haughty garden]

Wouldn’t you just find it as normal? Assuming c != 0 and f is invertible

let y = (cf)(x) = c * f(x). Suppose that x = c * f(y) and solve for y

[restive kernel]

what chapters should I master before doing discrete math

[weary tiger]

how is the distance between 2 points in a graph defined? is it the smallest value or the smallest absolute value for the length of all the paths between these 2 points

[pale epoch]

how is that different

eh, i guess you mean for weighted graphs?

it should be the smallest value (if it exists)

[tardy remnant]

can someone pls explain what is the difference between asymmetric and antisymmetric function?

[coral parcel]

In which context?

"Asymmetric" usually just means that the thing is not symmetric.

"Antisymmetric" means it has some particular precise property whose definition is in some appropriate sense "opposite" (but not merely the negation of) the definition of "symmetric".

[tardy remnant]

so if there is a relation from a to b ,but not from b to a that is asymmetric?

[coral parcel]

These are properties of the entire relation, not just how it behaves between two chosen elements.

Also, are you talking about relations or functions?

[tardy remnant]

yes

[coral parcel]

This is mathematics alright, but answering "yes" to "is it this or that?" is still just a dad joke.

[tardy remnant]

hahahhahahahah XD sorry I'm bat at english

i'm talking about relations

like transitive symetric asymmetric reflexive

[coral parcel]

Okay, then "antisymmetric" does have a precise definition.

A relation R is antisymmetric if for every distinct a and b it holds that at most one of aRb and bRa is true.

[tardy remnant]

on our exam we will have given sets and we have to tell which caracteristics they have

[coral parcel]

A relation is "asymmetric" (but that word is not used often) if it simply is not symmetric.

[tardy remnant]

okay I understand now .Thank you very much

[weary tiger]

I have a question , I am trying to design an iot solution to manage traffic lights. How do I get to know whether a traffic light is diagonal to another traffic light? I.e, a traffic light is facing another traffic light. Traffic lights can be arranged as a polygon.

[weary tiger]

Purely in a mathematical context.

[trail steppe]

That question seems a little vague

So you are looking for directly opposite vertices of any polygon?

Mathematically I'd check distance

But I think if you try it IRL it would not work unless the precision is good enough

If your polygons are not regular, I'm not sure

[weary tiger]

Somewhat directly opposite (+- 2 cm). Also, I don't have any transceivers in between for simplicity and the fact it would be impractical to have them at every location.

[stray reef]

anyone here good at regular expressions? a friend of mine wants one that matches emerald but not emerald ring

[trail steppe]

I'm not great at it but googling gave me emerald(?! ring)

My regexr
Not sure if you want only e or also allow E

[stray reef]

capitals are unnecessary

kinda irrelevant anyway

the purpose is for item highlight configuration in NetHack

[umbral tendon]

Hi guys, I'm doing some graph theory and I understand the concept of isomorphisms in graphs but I'm just wondering what in your opinion the answer to this question should look like..

[coral parcel]

Start by drawing the graph, for all deities' sake.

[umbral tendon]

I am wondering is I should just rewrite abc to xyz or smth

I drew the graph

I'll send a pic 1sec

[coral parcel]

Though for that question (h), the identify would suffice without drawing anything :-)

[coral parcel]

I suppose the labels on the edges belong to another subquestion?

[umbral tendon]

Yeah don't worry about that

I'm just focusing how the hell should the answer for question h look like

because I understand the theory

But idk what they want me to do so I need some opinions xD

[coral parcel]

Well, the identity map is always an isomorphism, and it looks like the only constratints the question puts on it is that it should map b to b...

[umbral tendon]

What's the identity map?

[coral parcel]

The map that maps each vertex to itself.

[umbral tendon]

There's also a similar question to this one which I got the answer for:

ans:

[coral parcel]

Right, so my proposal is $$\varphi(a)=a, \varphi(b)=b, \varphi(c)=c, \ldots, \varphi(j)=j$$

[vital dew]

Troposphere

[umbral tendon]

yeah that does make sense

[coral parcel]

You should be able to just write "the identity" to describe it, that is pretty standard mathematical jargon.

[umbral tendon]

And it does kind of make sense for the next question:

But I dont know what the other isomorphism would be

[coral parcel]

Ah, that's where they get you!

Well, f is the only vertex with degree 7, so it has to map to itself.

[umbral tendon]

mhm

so could I just swap g and i and that would be correcT?

[coral parcel]

No, because you'd be breaking the gh and ei edges.

[umbral tendon]

hmmm

[coral parcel]

The vertices other than f form a cycle, and that cycle structure needs to be preserved.

So once you decide which vertex to map a to, and which of its neighbors to map b to, everything else will be forced on you.

On the other hand d and h are the only vertices with degree 2, so they need to either stay where they are, or swap places.

So perhaps we should be saying: once you decide which of the two vertices to map d to, and which it its neighbors to map a to, everything else will be forced.

[umbral tendon]

a?

Do you mean h?

[coral parcel]

No, I did mean a. It's true that once you decide where to put d, h can only go to the other one. But I was picking a because it's the neighbor of d, so once you place both d and a you'll know whether the outer 9-cycle is mirrored or merely rotated.
We can also construct an argument (different from what I had in mind) based on placing d and h first.

[umbral tendon]

this is melting my mind 😄

[umbral tendon]

Okay so from the start.. xD What is the cycle structure

[coral parcel]

(was that a question?)

[umbral tendon]

Oh mb

I was asking what do you mean by cycle structure

[coral parcel]

Oh, nothing fancy. I just mean if we ignore f and all the edges that touch it, what is left is a cycle of 9 vertices and 9 edges.

And the isomorphism we're looking for needs to preserve which of those 9 vertices are neighbors.

... with the additional constraint that everything needs to map to a place with the same degree (including any edge towards f) it had from the beginning.

[umbral tendon]

So its correct to give the identity map for question h) right ?

[coral parcel]

The identify map is still a good answer to (h). The identity map is always an isomorphism for any graph.

[umbral tendon]

alright good to know

The whole cycle thing without f vertice is still confusing me a bit

What is stopping me from mapping d to h and h to d

How would that not be an isomorphism

[coral parcel]

We haven't identified any problems with that yet.

We just don't know that it definitely will work until we verify that we can also place all of the other vertices.

But go ahead, checking that is an excellent way to make progress.

[umbral tendon]

hmmm ok...

So mapping everything to itself except d and h

[coral parcel]

That's not going to cut it because we lose the da edge.

[umbral tendon]

do we lose de edge too?

[coral parcel]

Oh yes, and ch and gh.

[umbral tendon]

hmm then I don't really get what mapping does

[coral parcel]

It sounds like you know the formal definition.

Here's a more vivid way to think of it: Suppose the edges were made of rubber bands attached to the vertices. If we pick up all of the vertices and put them down in (potentially) new places on the drawing, do the rubber bands still match the pencil lines on the paper? If they do, we have an isomorphism.

The mapping says where each of the vertices end up after w pick up the graph and put it down with ned vertex positions.

[umbral tendon]

ooh I think I might get it

So your theory was to ignore f and rotate all the other points

[coral parcel]

Yes.

[umbral tendon]

d->a, a->b, b->c etc

[coral parcel]

For example.

Except that won't work because then we end up with "spokes" in the wrong places.

[umbral tendon]

spokes?

[coral parcel]

Edges between f and the outer nodes.

[umbral tendon]

ah yeah

[coral parcel]

(Not a standard term).

[umbral tendon]

yeah i get ya

I feel like the question insinuates that there is one to be found

[coral parcel]

Heh.

A way to make a bit faster progress might be to look at the explicit requirement in the question that b must map to itself.

[umbral tendon]

hmm

how the hell does that help me xD

[coral parcel]

So since b stays where it is, there's basically only two candidates for where a can go.

If a goes to itself, then d goes to itself too, and then e can only go to itself, and so forth all aroud the wheel.

[umbral tendon]

yeah but that doesn't give us any other isomorphism

So you think there isn't any unique isomorphism?

Because if we set a to d then we will end up with the same problem as before where spokes will be different

[coral parcel]

Will we? :-)

Well, we can't send a to d, because a and d have different degrees.

But we haven't checked if we can send a to another vertex that is already a neighbor of both b and f.

that is, c

[umbral tendon]

hmm

doesnt that break the ad edge

and ch

[coral parcel]

Whoops, sorry, I thought we had discarded the idea of mapping d and h to themselves and started over.

[umbral tendon]

oooh

so you're thinking about mirroring the graph

[coral parcel]

Yes.

[umbral tendon]

there b stays the same

that's smart

Yeah I can see how that would work

damn

I would never have came up with that

[coral parcel]

It's basically just a matter of puzzling out -- there's not a foolproof systematic method to resort to (which isn't at risk of taking forever).

[umbral tendon]

Yeah i get ya

Thank you so much for the help!

[coral parcel]

You're welcome.

[wide vine]

How do I tell the difference between tuples from cartesian products and strings?

Is there a specific symbol or is it just context

such that I don't mistake it for A x A = {(x,x), (x,y), (y,x), (y,y)} vs A x A = { xx, xy, yx, yy}

or does it not really matter seeing the order has been perserved

[olive condor]

This doesn’t quite make sense. All regexes matching emerald will, by definition, match emerald ring since it contains the string emerald.

But if your regex engine/library supports negative look ahead (?!), you can do something like this:

[stray reef]

right

i think the issue got resolved but thanks regardless

[olive condor]

👍 It helps to sharpen my regex-fu anyways

[elfin marten]

Hi i have given set let say A = {1,2,3,4}, B = {1,2,3,4} And they both have relations R ={ (1,1), (1,2), (2,1), (2,2), (4,1), (4,2), (4,4) } My question is what type of property does this relations have?

[split drum]

Do you remember the definitions? Start with reflexive: For all a in R, a R a.

Is that true for all of the elements in your sets A and B?

Also, it looks like B is the exact same set and relation as A. So you only really need to look at one.

[elfin marten]

well yes i know the defination

The goal is to identify which relation property does it poses.

Yes A and B are exact same but the relation of the elements are reflexive , symmetry and transitive for few elements but not for all.

[split drum]

Ah, ok I see what you're saying. So if none of the properties hold for every element in R, then the relation holds none of the properties.

1 R 1 and 2 R 2, yet 4 does not relate to 4. So it's not reflexive. And so on with the other properties.

[coral parcel]

In the math-flavored treatment of regular expressions and regular languages (which is the one we're probably in when we don't have looahead/lookbehind assertions), the setting is generally that we're asking whether the regular expression matches the entire input rather than just a substring. It's then expected that if someone wants to match for a substring specifically, they'll prefix and suffix their regexp with .*.

[coral parcel]

You mean 3 does not relate to 3, right?

[split drum]

Yeah, whoops

[elfin marten]

yes the element 3 does not obey any property . Yet Transitive property can be seen

2->1->2 i.e 2 reflexive (2,2) 1->2->1 i.e reflexive(1,1) 4->1->2 i.e (4,2) 4->2->1 i.e (4,1)

[coral parcel]

Do you mean that you have one relation R which is a relation between A and B, but A and B just accidentally happen to be the same set? If so, it is debatable how much sense it makes even to ask whether the relation is reflexive, symmetric, or transitive -- these properties are intended to be used about relations that deliberately go between a set and itself.

[elfin marten]

accidently happen does it matter here to decide the property of relations?

Just asking i have no idea about it 😦

[coral parcel]

Well, formally you can apply the definitions in this case perfectly well. It's more than it's hard to see whether it is useful to know that the relation was, for example, symmetric, unless there's a particular reason that the sets on both sides of the relation is the same.

So without a context for the question "is this relation symmetric", one cannot argue with certainty whether it makes sense to ask the question.

If it's just a free-floating homework question, of course, there's no context and we'll have to take it as we find it.

[wide vine]

if I have A = { (x,y) } would A x A = { ((x,y), (x,y))}?

[coral parcel]

Yes.

[elfin marten]

Yes

[coral parcel]

(continued reply to node1) You can probably just ignore my point; I just found it unusual that you're using two different letters to refer to the same set, when it's implicit in the concepts you're using that there's only one set.

[elfin marten]

okay what's two different letters here?

[coral parcel]

A and B

Hmm, perhaps you intended for either A or B to be {1,2,4} instead of {1,2,3,4} but mistyped?

[elfin marten]

okay hold on then let me draw a diagram of this graph

https://jamboard.google.com/d/1uqBYJxU9B232pRC9DObZnW5paG2vIzEk05Zo2iYT5lk/edit?usp=sharing

[coral parcel]

No access.

[elfin marten]

sorry try now

https://jamboard.google.com/d/1uqBYJxU9B232pRC9DObZnW5paG2vIzEk05Zo2iYT5lk/edit?usp=sharing

[coral parcel]

Hmm, I have the feeling we're talking past each other here. You started by writing:

Hi i have given set let say A = {1,2,3,4}, B = {1,2,3,4}
And I'm trying to understand why you're defining two different names (namely A and B) for the same set {1,2,3,4}.

[elfin marten]

Sorry it might be mistaken here but please refer the graph now . And kindly do let me know what relation property i should associate with this relation

[coral parcel]

The names A and B don't even appear on that graph, so looking at it doesn't help clear up my confusion

[elfin marten]

Does it matter to draw a set name on graph? Or using graph can't we determine it's property?

[coral parcel]

No, but it matters to me that I don't understand why you wrote

Hi i have given set let say A = {1,2,3,4}, B = {1,2,3,4}
Presumably you did so for a reason, and until I know what that reason is I can't know whether it has an influence on the answer I should be giving you.

[elfin marten]

Just to illustrate the relation ship of elements using mapping diagram

[coral parcel]

So far, you haven't even confirmed whether it was on purpose or a typo that the two {1,2,3,4} you wrote are the same set.

Are you deliberately not answering my question?

[elfin marten]

Yes indeed i have wrote the same set, but the purpose was to visualize it's relations

[coral parcel]

Huh.

I'm completely confused.

[elfin marten]

See i have given this graph , to make it clear i have divided it's domain and range into set A and B so thats the purpose and to make relationship

[coral parcel]

Are you asking one question about A and another (but identical) question about B? Or a question about how A relates to B, or what?

[wide vine]

This is true right? If A is a subset of B then (A x C) would be a subset of (B x C) as the 2nd element of the tuples will be equal (C) and we know the first 1 element of A x C tuple (the A portion) will be contained in B x C.

[elfin marten]

I have given only this graph which i have shared with you @coral parcel I need to find it's relation.

[coral parcel]

It doesn't make anything clear at all that you're using two names for the same thing, and stubbornly refuse to give any other explanation for it than "to visualize". To visualize what? Which conclusion am I supposed to make from those two names?

[elfin marten]

Kindly ignore those two names A and B , just consider the graph only.

[coral parcel]

Then I am unable to give you any useful answer.

[olive condor]

Dang, I saw the keywords “regex” and “match” and right away assumed that Ann’s friend was working with a programming tool. Thanks for pointing that out!

[elfin marten]

For mine own simplicity i have derived the domain and range into A and B which i have shared as two set. I hope it's clear now

FIne it's okay if your unable to give an answer. But using this graph you could tell us what relation it has?

I think it's transitive relation

[coral parcel]

My suspicion is that you must be misunderstanding something completely fundamental about how relations work, but I can't get any closer than that on the basis so far.

[elfin marten]

okay.

Anyone here would like to comment, because in the book it says same

[olive condor]

Yes, it’s true. (No because I say so, but because there exists a proof showing that it’s true ;D )

[wide vine]

thanks

[elfin marten]

How about mine 😦

[olive condor]

Sorry, I don’t know, haven’t study into relation properly

Still learning about proofs and a bit of sets

Maybe it helps if you rephrase your questions a little bit? Or try to answer it and show your reasoning?

E.g. “I think it’s transitive relation, because of X, Y, and Z.“?

[jolly vale]

could someone help with this problem please? i've tried this for hours and can't find a path that only uses 3.

[turbid swallow]

I don't understand how to draw the graph in 2(b). Can anyone help me?

[olive condor]

What do you mean by “path”? The three rooms can be D, F, and J, can’t they?

[jolly vale]

that would allow all rooms to have wifi

[olive condor]

Hmm, but the question is asking for “which rooms”, not “which connected rooms”

[coral parcel]

"Path" sounds like there is a hidden requirement that the access points must be in rooms next to each other.

[olive condor]

But I don’t think that’s what the question in the figure asks for

[coral parcel]

Indeed, so I wonder whether that's Simonic's mistake.

[olive condor]

Probably Simonic misunderstands the question?

Yup

[wide vine]

is a set raised to the 0 power = { λ} by definition?

{a,b}^0 = {λ}

[coral parcel]

2(a) and 2(b) are not different graphs; they are two groups of edges that both are included in one graph that the question is about.

[wide vine]

λ = Ø ?

just they are used for different notions?

[coral parcel]

If you're doing formal language theory, lambda is one of several conventional names for the string of length 0, not the set with no elements.

[wide vine]

so what if I am expressing something as a tuple but I end up raising it to the 0 power?

like (a,b,c) vs abc

[coral parcel]

I'm not sure that raising a tuple to any power makes sense a priori.

[wide vine]

well I mean what if I am not interested in having it formatted as a "string"

do we still used lambda

[coral parcel]

I'm confused. Are you doing formal language theory here in the first place?

[wide vine]

idk

my question is

how does b change if we are to express it as n tuples

[coral parcel]

That looks like formal language theory allright.

But I don't see where you get tuples to enter the picture.

[wide vine]

well instead of

{ λ, 0, 1, 00, 01, 10, 11 }

we do

{ λ, (0), (1), (0,0), (0,1), (1,0), (1,1) }

but idk if the lambda symbol would be accurate

because these are no longer strings but tuples

I mean really it is a bit of semantics I guess seeing they both preserve an order

[coral parcel]

How do you distinguish? So far it looks like you're just using (,,,,,) as a non-standard notation for strings.

[wide vine]

well I don't know when to use strings or tuples other than when I am being instructed

for example

[coral parcel]

I.e. do you mean a different mathematical object when you write (0,1) instead of 01, or do you intend for them to be notations for the same thing?

And if you intend them to be different objects, then what is the difference you want?

[wide vine]

That is what I was more so wondering, is there a difference?

or is it more so just different notation

like how you can do <a,b,c> vs ai + bj + ck with vectors

[coral parcel]

Your (now next-to-)latest screenshot doesn't look like formal language theory at all.
I would assume that they are intended to denote the same objects, but just are notations that are useful in different contexts.

[wide vine]

so is an empty tuple a thing and does it use the same symbol

[coral parcel]

In some contexts we write an empty tuple as ().

[olive condor]

I guess Brandon is asking whether λ = Ø = () = {0,1}^0?

[coral parcel]

And the answer to that is complicated.

It is definitely not the case that Ø = {0,1}^0 because {0,1}^0 is a set with one element, and Ø is a set with no elements.

[wide vine]

yeah I see how Ø doesn't work

[olive condor]

So, whether λ = () = {0,1}^0?

[wide vine]

wait...

is it not

{λ}?

or { ()}

[coral parcel]

In a common set-theoretic formalization, the set Ø is used to represent both the empty string and the empty tuple, but that is generally an "implementation detail" that we're not supposed to use when reasoning about strings or tuples.

In formal language theory it is common not to write the {brackets} when talking about a language (that is, set of strings) that contains a single string.

One needs to understand from context whether the writer means "I'm talking about this particular string" or "I'm talking about the language that contains just this particular string",

[wide vine]

😵‍💫 . this is a discrete math course and not very formal with heavy definitions or anything so not sure

[coral parcel]

Pssh, that should be the main job of "discrete math" to introduce the necessary formalizations.

[wide vine]

so idk what formal language theory is

[coral parcel]

Formal language theory is the thing where "language" is a code word for "set of strings". (It contrasts to "natural language", which is what they do in the literature department, and e.g. "programming language" which have computational meanings in addition to being character sequences).

I.e it associates as "(formal language) theory", not "formal (language theory)".

[olive condor]

I think you’ve gone sidetracked

What’s your question again?

Whether {0,1}^0 = {λ} = {()}?

[wide vine]

Yeah

and is {some set}^0 by definition = { lambda}

[coral parcel]

My answer would be that {0,1}^0 is either {lambda} or {()}, depending on context.

[wide vine]

That is what I thought

So I just assumed it is based on how the question is stated

which is why I wondered if strings and tuples are more just different notations for the same thing

[coral parcel]

Well, (and here is why it gets complicated), they are!

Formally, mathematically there's no difference.

[wide vine]

like {xxy} = { (x,x,y)} basically?

seeing the order is preserved or whatever

but one is called a string and the other a tuple

so Idk if I am just arguing semantics at this point

[coral parcel]

You could say that they're different ways of thinking about the same phenomenon, and each of the ways of thinking comes with its own traditions and its own notation.

Which must be why your problems insist on using one notation rather than another. But they're doing so in a somewhat confusing manner that seems to call attentions to "these are the same thing", where the intention bust be to be sure you can distinguish between the different ways of speaking about them.

[olive condor]

Maybe one can think that a string is a syntactic sugar for the tuple? Since there is no “string” in maths from set-theoretical POV?

[coral parcel]

Yeah, I think that must be how Brandon's textbook are defining them; otherwise the admonitions in the problems would make no sense.

Brandon, are you studying CS as a main subject?

[wide vine]

No but this I think falls under one of the CS requirements

[coral parcel]

Yes.

[wide vine]

Here is their definition of a string

I can see how if you are working with numbers that are not base 2

[coral parcel]

I was trying to appeal to a CS intuition when I spoke of "implementation details", but if you're not CS, then that probably doesn't help.

[wide vine]

it would be a problem trying to not use a tuple

[coral parcel]

Right, so they are defining strings as a special case of tuples.

Hmm, now I'm not even sure if I'm still answering a question or just ranting ...

[wide vine]

well obviously if you have something like 10 and 10

but really meant

(10) vs (1,0)

you would want to use a tuple over a string

{(10)} vs { (1,0) } vs { 10}

[coral parcel]

Yeah, you don't use string notation unless it's well established in the context that you're only interested in symbols rather than arithmetic.

[wide vine]

I see

I believe my questions have been answered, thanks!

[olive condor]

That’s a nice discussion, thank you too

And to troposphere

[wanton haven]

How can I turn a discrete function into a continuous one?

[wide vine]

does concatenation exist within tuples? for example strings s=xxy, t=yz then st=xxyyz.

My book used it with strings and don't know if this is a thing with tuples and what the symbol would be

[coral parcel]

There's nothing stopping us from defining it for tuples. It's seldom done because "the contexts where we need to think about concatenation" are roughly the same as "the contexts where we use string notation" anyway.

In fact that's a pretty good guideline for when to use string notation in the first place: If you're going to deal with concatenation, string notation is probably the most useful way to write things.

There are some applied contexts (e.g. cryptographic protocols) where it's useful to be able to concatenate tuples. Then it's often notated $|$, for example $(a,b)\mathbin{|}(c,d,e) = (a,b,c,d,e)$.

[vital dew]

Troposphere

[wide vine]

does this property hold

Concatenating any string x with the empty string gives back x: xλ = x.

[coral parcel]

Yes.

[wide vine]

okay

wait umm dumb question but what would λλ equal?

{ λ}^2 = ?

{(λ,λ)} / {λλ}

I guess by previous definition xλ = x , let x = λ , we then find λλ = λ

so probably {λ}^2 = {λ}

[umbral tendon]

I'm learning Formal Languages and context-free grammars. I've done simpler versions of this question. The only thing that is confusing me is the two <A> rules which can be applied interchangeably and I'm not sure how to describe that structure.

I have a^g b b^n c^k c b^n a^g

g,n,e = Natural numbers & g,n,e >= 0

But That seems incorrect because c^k could also be applied before the b^n.

To make it clearer. rule 3 can be applied before rule 4 and vice versa which is why it seems impossible to me to be able to able to describe that structure....

[coral parcel]

Yes.

[coral parcel]

You should probably go for a description in prose rather than trying to shoehorn it into an algebraic form. (The algebraic notation is nice and succinct when it does work, but it cannot express everything, which is why we have grammars and such instead).

[umbral tendon]

what does a description in prose look like

This is the closes example I found but I still dont 100% get it

https://www.javatpoint.com/context-free-grammar

[coral parcel]

Perhaps something like:

A word in this language has the form xbyczx where x in {a}* and z in {b}* and y consists of the same number of b's as z has, with an arbitrary number of c's inserted between, before, or after, the b's.

[umbral tendon]

hmm

Could that not be done using algebra?

[coral parcel]

If at all, it would be completely unreadable, and therefore a worse answer than the prose.

Hmm, perhaps not \emph{completely} unreadable. You \emph{could} write something like $$\bigcup_{n,m\ge 0} a^n (bc^*)^{m+1} c b^m a^n$$ but I think that is still pretty unreadable compared to the prose.

[vital dew]

Troposphere

[coral parcel]

In particular, mixing a Kleene star with explicit iteration counts feels like an ad-hoc trick that's probably more confusing than illuminating.

[umbral tendon]

I get a feeling that this is what they're looking for

why m+1?

[coral parcel]

Because you get an unpaired b from the S ::= b A production.

[umbral tendon]

$$\bigcup_{n,m\ge 0} a^n b (bc^*)^{m} c b^m a^n$$

[vital dew]

MoreeZ

[umbral tendon]

would this mean the same thing?

[coral parcel]

Please resist the temptation to think an answer in symbols is automatically better. The question says "describe" which perfectly well covers a description in English. Symbols are tools, not our masters, and should be used only when they actually help saying things more clearly than we could otherwise.

[umbral tendon]

hmmm

[coral parcel]

No, that wouldn't be the same thing, because you can generate c's immediately after the initial b.

[umbral tendon]

Ah I see

wait

no I don't think you can

[coral parcel]

S -> bA -> bcA -> bcc.

Your union doesn't describe bcc.

[umbral tendon]

ooh I read this wrong

yeah i get you

[umbral tendon]

But how does this prevent me from generating c right after the first b?

[coral parcel]

What would the n and m that allow you to get bcc be?

Since there's nothing after the final c, we must have m=n=0, and then your expression collapses to just bc.

[umbral tendon]

oh i see

yeah

$$\bigcup_{n,m\ge 0} a^n (bc^*)^{m+1} c b^m a^n$$

[vital dew]

MoreeZ

[wide vine]

sorry to bug again but would does λ make sense in terms of tuples like {a, λ} x {b} = {(a,b), (λ,b)} ? or is this strictly used for strings. I feel like it was answered but im lost again.

[coral parcel]

{x,y}×{z} = {(x,z),(y,z)} makes sense no matter what kind of things x, y, and z are -- in particular you can let y be the empty string.
Note that in order for things to make good sense, we'll need to consider {a,λ} to be a set of similar kind of things, so "a" has to mean a string of length 1 rather than the naked symbol a.

Note also that the Cartesian product × is distinctly separate from string notations, so the tuples it builds will never be notated as strings. That is, it would be wrong to write (a,b) in your result as the string ab. But you can have a tuple of strings without problems.

[wide vine]

Okay 👍

[weary tiger]

how do I go about looking if the set defined by all x,y for which x^2 + y^2 <= 1 is bigger or smaller than R/N ?

any general videos or sources on that type of stuff for comparing sets of R2 to sets of R1 could help as well

Well RxR has same size as R

That set is a circle so its also of the size continuum

@weary tiger

[weary tiger]

what do you mean by "the size continuum"?

Continuum is cardinality of R

[weary tiger]

wait how? if I take the subset of R*R A := {(0,a) for all a is real number}, then I can have a bijection from A to R , which means A has the same amount of elements as R
A consists of less elements than R*R
which means R *R has more elements than R ?

[weary tiger]

ah I see

[weary tiger]

A doesnt consist of less elements

Maybe I dont understand your notation

And your formatting is kinda scuffed

Whats R\R

And R*R

R*R = RxR

[weary tiger]

where do I write that?

In your message

[weary tiger]

Anyways, that proves only A has size of R which doesnt show anything

[weary tiger]

how so? clearly A doesn't contain all the elements of RxR ?

So?

So does (0,1) as subset of R

But they are of the same size

with size I mean number of elements, not dimension

Me too

(0,1) has the same number of elements as R

The bijection is scaled tan(x) restricted to some domain

[weary tiger]

so you mean the set of 2 elements: 0 and 1?

No

or the 1 element (0,1)

The interval

ah okay

[weary tiger]

I don't think I have seen this in my textbook

This is a very good example to remember

This shows any interval of the form (a,b) where a and b are real numbers is of the same cardinality as R

There is also a theorem saying that for any set A, |A|=|AxA|

Any infinite one

[weary tiger]

mhm okay

[weary tiger]

do you know of any book discussing these theories? our textbook doesn't deal with them yet we have to solve excercises where those things are needed..

thanks for the help btw

[weary tiger]

Not really

[cerulean wind]

#discrete-math message

see here

[elfin marten]

Hi

Consider the relation ”is a factor of” from the set A = {2, 3, 4, 5, 6} to the set B = {6, 8, 10, 12}. Make an arrow diagram of this relation.

It looks Reflexive property

Could anyone please verify my answer. 😦

I would be very thankful if someone let me confirm my answer.

[turbid swallow]

Thank you for responding! I was wondering when they say if i=Sk, and j = Sk+1 then (Vi, Vj) is an edge. Here, if S5=1, 2 , 3, 4, 5 and S6 = 3, 4, 6, 2, 1, 5 then does the statement mean each vertex from S5 have an edge to all the individual vertices in S6?

For example, (1,3) is an edge, then (1, 4), (1, 6)... and so on

[coral parcel]

Each s_k is just a single number.

When the problem mentions (5,3,4,2,1) as an example, it means s1=5, s2=3, s3=4, s4=2, s5=1.

[turbid swallow]

Oh I understand now! Thank you!

[coral parcel]

Hmm, are you asking whether isomorphism of (non-rooted) trees is decidable in polynomial time?

Or is the bijection you're talking about not an isomorphism?

[elfin marten]

Could anyone helps me to understand has the same number of factors as” on the set N. What does it meant here?

[coral parcel]

Oh, you mean an (isomorphism-preserving?) bijection between the set of all graphs and the set of all trees, rather than a bijection from (the vertices of) one graph to one tree.

That sounds like it would be as difficult as deciding isomorphism in the first place.
As a nonconstructive existence question: Sure, there should be enough trees of polynomial size to represent all the isomorphism classes of graphs

[coral parcel]

Well, the P-ness of graph isomorphism is still open, but that could settle it one way. On the other hand, if it is shown that graph isomorphism is in P it doesn't seem obvious that we could necessarily use that to construct a "tree-shaped invariant" in polynomial time.

[gilded marsh]

I need help finding the range for (a)

[coral parcel]

The two sets are intervals. Would it help you to write them in interval notation?

(The pencil notation "1-10" is misleading for A because A also contains numbers such as 0.1 or pi-3, whch are between 0 and 1).

[gilded marsh]

i see

would it be x<= 10

and x <= -5

im just not sure how to simplify it since x is smaller than two numbers which are 10 and -5

[coral parcel]

Well, to begin with, you're not supposed to answer with disembodied inequalities, but an actual written-out notation for a set -- braces and all.

And it looks like you've lost the condition 0<x for A.

[gilded marsh]

Like this?

[atomic swan]

You seem to have switched the sign between x and -5, and as they said before, lost the condition 0<x for A

[gilded marsh]

do i add it to the other conditions?

[atomic swan]

I'm not sure what you mean

[gilded marsh]

you said i lost the condition

do i put it right beside the other ones?

[atomic swan]

It would be a solution, however they want you to simplify as much as possible, example is in the question

[gilded marsh]

Like this?

[atomic swan]

you seem to be switching up the signs a lot, try to keep track of if x is greater than or less than a value

and no,

Originally, Your x greater than or equal to -5 was incorrect because x was stated in B as being less than or equal to -5

Hence why I said you switched the sign

as for x<=10, it doesn't have the other condition of set A which is 0<x, which should both be applied simultaneously

I am now going to exit this conversation because I cannot identify the line between helping, and doing the work for you

[golden monolith]

idk this is math

[dry raven]

in most discrete classes what is log base normally 10 or 2?

lg or ln?

ahh okay cool thank you, Ive actually never seen lg tbh

[haughty garden]

Once you fix a professor to sit in a spot, then the problem boils down to a line arrangement since they define where the start and end of the arrangements are. So even though there are n spots for the first professor to sit, each of these spots are identical and it’s not until they sit down that the order of arrangements matter

Alternatively, you have n! ways of arranging them but n of these are identical arrangements because they are just rotations of one another; hence, we would have overcounted by a factor of n

[brave imp]

https://media.discordapp.net/attachments/373217754666500097/934993341475598428/unknown.png?width=1440&height=162

[waxen spire]

confused on what this means, specifically |a - 1|

im used to | | meaning magnitude, but it doesnt make sense to me in this context

[coral parcel]

For real numbers it is just the absolute value. a-1 is a certain number, the absolute value of that number is the (non-negative) distance between a and 1 on a number line.

[waxen spire]

so basically the set A = {0, 1} ?

[coral parcel]

No, you get the interval [-1, 3].

All the real numbers that are at most two units away from 1.

[waxen spire]

i am confused on that, if a was 1, wouldnt the first number in the set be (a - 1) so (1 - 1)?

[coral parcel]

The number that gets put into the set is a.

|a-1| is only used to decide whether a itself is included in the set.

[waxen spire]

could you walk me through how you got -1

[coral parcel]

Do you agree that when a=-1 then it is true that |a-1|<=2?

[waxen spire]

yes, but i thought a couldnt be negative

[coral parcel]

I see nothing that says that. Is there something you didn't screenshot?

[waxen spire]

that is just my mis understanding, i thought the R with the outline was only real positive numbers

[coral parcel]

Oh no, $\mathbb R$ is \emph{all} the real numbers: negative ones, zero, positive ones.

[waxen spire]

if thats the case, isnt this an infinite set?

[vital dew]

Troposphere

[waxen spire]

OH

the | | makes it positive

[coral parcel]

Exactly.

[waxen spire]

thank you i understand now

[weary tiger]

Anyone gets how pr(b) was calculauted

[fading furnace]

what is the standard book for discrete mathematics

[unborn pasture]

If we have a directed graph(G), and we define the nodes fron n > 1. And if G has a node with indeg(0) (meaning that is has no arrows pointing to it), does G have a topological ordering?
My answer: Yes, if the nodes for G are defined for n > 1, we could let n = 2. Then obviouslythere is a topological ordering. Like in the picture: The topological ordering here is AB.

How is this answer false?

I don't see how this is not true. The only thing that i think makes this false is if we let n = 3, then G could have a cycle. But it could also not have a cycle. Maybe i needed to add a lemma like "if G has no cycle then our statement is true" or something

[vale crow]

need helpos

[unborn pasture]

<@&286206848099549185>

[coral parcel]

I don't understand what you mean by "define the nodes from n>1". Can you say that again with more words, please?

[floral abyss]

How would u go about showing wether this is an equivalence relation on R

${(x,y)\in R^2 : x^2y-xy^2-x+y=0}$

[vital dew]

AR_7

[coral parcel]

Here is a graph where one of the nodes has zero indegree, yet it doesn't have a topological ordering (because of the cycle). Is this a counterexample to your claim? If not, why not? I hope your explanation can help me understand what you mean by "define the nodes from n>1".

[coral parcel]

Is it reflexive? Is it symmetric? Is it transitive?

[floral abyss]

Yes I know that but I’m kinda stuck on how to show it

For reflexive it’d be xRx so x^3-x^3-x+x=0 so yes it’s reflexive I think

Not sure for the other 2

[coral parcel]

Right.

You should be able to investigate "symmetric" too.

[floral abyss]

How

[coral parcel]

What is the definition of "symmetric"?

[floral abyss]

If xRy then yRx

[coral parcel]

Right, so assume xRy and see if you can show yRx.

(Or find a counterexample).

[floral abyss]

Yes I understand that but I’m not sure how to go about it

xRy so we have x^2y-xy^2-x+y=0

[coral parcel]

Good so far.

[floral abyss]

And we need to show yRx which is y^2x-yx^2-y+x=0

[coral parcel]

(Well, not entirely good; you're missing an y in the first term of the equation for xRy).

[floral abyss]

Ah yes miswrote it

[coral parcel]

Whese two equations look pretty similar, don't they?

[floral abyss]

Yes

Are we supposed to solve it

Then I’m assuming where gonna get x=y

[coral parcel]

Not solve it as such.

Perhaps it helps to see the point if I point out that y^2x s the same as xy^2 and yx^2 is the same as x^2y?

So the terms in x^2y-xy^2-x+y=0 are almost the same as the terms in y^2x-yx^2-y+x=0, with just one difference.

[floral abyss]

Well I mean yeah? We just swapped the x and y around

[unborn pasture]

with n > 1 i mean that the graph needs to have more than 1 nodes, does that make more sense?

The picture you sent has 4 nodes so n = 4

The one i sent has 2 nodes

[floral abyss]

Why can’t we do that tho? We can show that x=y so the two equations are both equal and equal to 0

And for transitivity xRy and yRz so x=y and y=z and therefore x=z and xRz?

[coral parcel]

Setting x=y won't help for symmetry.

[unborn pasture]

it is the minimum number of nodes that a graph may have*

[coral parcel]

Well, if you could show that it only way to satisfy x^2y-xy^2-x+y=0 was to set x=y, then you would indeed be done.

[floral abyss]

I mean you’d also get x=1/y but I kinda just ignored that lol

[coral parcel]

Don't ignore that! That one's the point :-)

[floral abyss]

So what do we do

I’m confused

[coral parcel]

We're still not quite done with symmetry, so bear with me for a moment.

We have assumed that x^2y-xy^2-x+y=0 is true. We want to show that y^2x-yx^2-y+x=0 is then also true.

Do you notice that y^2x-yx^2-y+x is just the negative of x^2y-xy^2-x+y, term for term?

[floral abyss]

What do u mean by negative

Do u mean opposite

[coral parcel]

That's another way of saying it, yes.

(Except "opposite" can have several different meanings, and I'm not quite sure you're understanding the right one).

Each term in one equation is minus some term in the other.

[floral abyss]

I meant as in the x and y have been switched around

[coral parcel]

No, not that.

The equation we're assuming has a +x^2y in the front. In the we find -yx^2, which is minus that.

The second term in our assumption is -xy^2. Our goal has +y^2x.

The assumption has -x, the goal has +x.

The assumption has +y; the goal has -y.

[unborn pasture]

I’m not sure. The way i interpreted the question is that since G needs to have more than one node (2 nodes is the minimum number of nodes we can have). Meaning we can create a graph with 2 nodes (two dots A and B) and we can draw a arrow from A to B. Then this proves that G does indeed have a topological ordering if there is a node that has no other nodes pointing to it.

So I’m thinking maybe the right answer requires a lemma saying that G does not have a cycle.

[floral abyss]

Oh ok I follow

So how does this help us

[coral parcel]

It means that if we take x^2y-xy^2-x+y=0 (which we're assuming is true) and multiply it by -1 on both sides, we get ...

[coral parcel]

If I'm understanding you correctly, you're trying to prove something for all graphs satisfying certain conditions. To do that it is not enough to show one example of a graph that satsifies the conditions and has a topological ordering -- in particular if my counterexample works, then it shows the claim you're trying to prove is false.
A lemma won't help you (that's just a fancy word for a theorem you prove as a stepping-stone), but perhaps what you mean to say is that you should add an assumption that the graph has no cycles to the statement of the claim you're proving?

[floral abyss]

So assuming xRy
we have x^2y-xy^2-x+y=0
Then -1(x^2y-xy^2-x+y) = -1(0)
So therefore y^2x-yx^2-y+x=0
And therefore symmetry holds

[coral parcel]

Yes. That deals with symmetry!

(It is generally expected that you'll be able to notice things like all the terms in one equation are minus all the terms in another, so do file that away as a useful trick to keep in mind).

Now for transitivity we need a bit more than just the equation, but fortunately you already solved it and found that x^2y-xy^2-x+y=0 exactly if x=y OR y=1/x, right?

[unborn pasture]

Exactly, that last thing you wrote.

I don’t remember exactly if it was for all graphs or specific for the graph G in our question

[floral abyss]

Yea

[unborn pasture]

Can you please lmk when you got the help you needed so i can continue.

[coral parcel]

So we assume that (x=y or y=1/x) and (y=z or z=1/y) and we then need to prove x=z or z=1/x.

[floral abyss]

If y=x and y=z isn’t it obvious x=z

[coral parcel]

Yes it is.

So that is the sort of boring case.

But it could also be that y=1/x and y=z, or it could be that y=1/x and z=1/y, for example.

[floral abyss]

Oh so we need to show it for all the different combinations

[coral parcel]

Yes, because all we're assuming is that one of the possibilities hold for each of xRy and yRx.

We can't conclude transitivity if we've proved it for only some of the (x,y) combinations with xRy.

[floral abyss]

Ok so assuming y=1/x and y=z

We’d substitute 1/x for y and z for y

But then what

[coral parcel]

That sounds like a very roundabout way of putting it, and I'm not sure it actually makes sense.

If y is the same as 1/x and y is also the same as z, then what can you conclude about x and z?

[floral abyss]

1/x=z ?

[coral parcel]

Yes.

[floral abyss]

How does that show x=z tho

[coral parcel]

We're not trying to show x=z.

We're truing to show xRz, and there are two ways for that to be the case.

We just agreed that xRz is the same as "x=z or z=1/x", didn't we?

[floral abyss]

Ah yeah

Thanks a lot

[coral parcel]

(Ah, perhaps I see what you meant by your "substitute" comment? You'd plug 1/x and z into x^2y-xy^2-x+y=0, you mean? That would also work, but be more work).

[floral abyss]

But fucking hell I’m deffo failing this shit

[coral parcel]

Yeah, if there are no other assumptions on G, then my counterexample still works.

[unborn pasture]

😣

[coral parcel]

Why the sad face?

[unborn pasture]

Do you reckon my answer is enough to show that I understand the subject?

My profs didn’t accept that answer. I figured my reasoning was enough but ig not

[coral parcel]

You're being asked "is this stratement true or false". You answered "the statement is true because such and such". But actually the statement is false, so already that makes your answer incorrect, and no amount of reasoning can save it then.

The correct answer would have been: "the statement is false becuase here is a counterexample: ..."

Ooh! I think I see.

[unborn pasture]

Then I’m guessing this would be true? If it is the case that, for each pair of nodes u and v, G has a path from u to v, then
G contains a cycle.

The problem is that he has all these problems online and when I connect the dots it points me towards a)true and b)false

[coral parcel]

The question you quoted is actually sloppily worded. It says

Given a directed graph G , state whether it is true or false that such-and-such.
What it actually meant to ask is
Is it true or false that [such-and-such holds about all graphs]
and the difference in what it seems to say and what it wanted to ask seems to be confusing you. (This kind of sloppiness is so common in exercises that I didn't even notice at first).

[unborn pasture]

Ahhh

Yeah ok that’s fair ig

Unfortunate, i was one points away from passing

[coral parcel]

So a really good answer would have been "it can either be true or false, depending on which graph G is; here are examples of each", though that is a bit of rubbing the teacher's nose in the sloppy wording of the question.

[unborn pasture]

I should’ve paid attention tbh. He has the exact same question online. He just changes some of the words

[elfin marten]

Just asking, is it possible to make a simple graph into Bipartite graph ?

[coral parcel]

Insert a new vertex in the middle of every edge?

Color all the vertices randomly red or blue, and remove edges whose ends have the same color?

Which constraints does "make into" have to be satisfy here?

[lime plinth]

of course that doesn't work
you need to prove for n+1 and m+1 separately

[bold bone]

how do reverses work in truth values like if i have: if for all x such that some y satisfies P(x,y) then for all y such that there is some x that satisfies P(x,y)

[distant bobcat]

If I am given a graph G what is the complement of this graph? Will it just equal the same vertex set?

[coral parcel]

Same vertex set, all the possible edges that G doesn't have.

[distant bobcat]

aha, so the difference is in the edges?

Also for every simple graph if each vertex has degree equal to 2 do I get a cycle? I dont think this holds in the infinite case as I could construct an infinite path, but in the finite case it should hold as the last vertex of this graph must be connected to a previous vertex in the graph (namely the first vertex).

[stray reef]

it doesn't hold in the finite case

you could have a union of some number of cycles

[devout lava]

Sketch a directed graph with1 sink and 4 sources.

what is a sink?

[stray reef]

do you know what a source is?

a source is a vertex with in-degree 0 (i.e. that nothing goes into)

a sink is a vertex with out-degree 0 (i.e. that nothing goes out of)

@devout lava

[devout lava]

oh

thanks

[weary tiger]

Can someone help me solve this question , or share a solution of similar question

[distant bobcat]

@stray reef I see. Like in the example of a disconnected graph with each component being a cycle, so it doesn't hold.

[fallen pebble]

Given a set V = {1,2,3,4,5,6}, can you construct a permutation group order 9?

I've seen this in my textbook, but I have no clue how to even begin

[stray reef]

you mean a subgroup of Sym(V) whose order is 9?

@fallen pebble

[fallen pebble]

Yes

[stray reef]

can you find two elements of order 3 that commute?

[fallen pebble]

like (1,2,3) and (2)(3,5,6) for example?

[stray reef]

these do not commute, so no

[fallen pebble]

(1,3,5)(2,4,6) and (1,5,3)(2,6,3)? I'm sorry, I didn't know what you meant with commute (not a native english speaker)

[elfin marten]

What does discrete object meant? Can we consider it has property of finite or infinite or both?

[weary tiger]

discrete means usually at most countable

[stray reef]

commute means fg = gf

where f and g are your elements

you know the commutative law for operations like addition and multiplication, yes?

[fallen pebble]

yes

[elfin marten]

Can a edge in graph be a infinite set ?

[coral parcel]

"Discrete" has different technical meanings in different contexts. The similarities in intuition between those meanings are usually best understood by knowing many examples of the usage.

[fallen pebble]

I'm assuming both g and f have to be different elements?

[stray reef]

yes

if you picked the same element for your purposes you'd only get a group of order 3 and not 9

[stray reef]

is there any particular reason why you want a particular infinite set to be an edge in your graph?

[fallen pebble]

(1,2,3)(4,5,6) and (1,2,3)(4)(5)(6)? They're both of order 3 and commute, right?

[stray reef]

this will do

though you could've just done (1, 2, 3) and (4, 5, 6)

but yours will do

[fallen pebble]

okay, and I have to use those to create a permutation group of order 9?

[stray reef]

i never said you "had to" do anything

but these commuting elements of order 3 will generate a subgroup of order 9 within the full symmetric group on six points

[fallen pebble]

How do they generate that subgroup?

[stray reef]

what's your native language?

maybe i can find the word for "generate" in your language

cause i am using it here in the same sense as it is used in group theory

[fallen pebble]

Dutch, it's probably a lack of knowledge about group theory terminology, rather than a language thing.

[stray reef]

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

this is what im talking about

it is very common in math to specify a group by naming a set and taking your group to be whatever said set generates.

[elfin marten]

Just wanted to understand the defination and possibility. What i know that in a graph G vertices V are finite and Edges are 2 subset of V.

[stray reef]

you are being very careless with your wording

[elfin marten]

@stray reef Pardon me i'm new to discrete mathematics.

[stray reef]

vertices V are finite
you mean "V, the set of vertices, is finite". finiteness is a property of the whole set, not of any element in it.

[fallen pebble]

I understand, thank you

[stray reef]

and if you really meant to ask "Can a graph have infinitely many edges?" then by your definition the answer is no: a graph on n vertices can have at most n(n-1)/2 edges

[elfin marten]

Here when you said mine defination i believe your refering to this statement "A graph G with vertices V and edges E. I.e G = (V,E) Where Edges are 2 subset of V." ?

For instance let consider V = {1,2,3} then E = { {1,2}, {2,3}, {1,3} }

[stray reef]

okay sure

that is a graph with three vertices and three edges

[elfin marten]

It's just simple graph through that i'm making my example clear.

So if there are vertices and edges are finite. Then it's called finite graph. And do this property is applicable to every graph? I mean there no infinite graph exist.?

[stray reef]

typically in graph theory one deals only with finite graphs.

but i would not say that infinite graphs "do not exist" outright.

if you don't want to work with infinite graphs then you don't have to work with infinite graphs.

[elfin marten]

I'm just trying to understand when a graph is infinite?

[coral parcel]

It can be infinite if you decide to work with infinite graphs.

It's literally up to you which setting to choose to work in.

Typically you'll be expected to warn the reader if you're considering infinite graphs, because it's more common to consider only finite ones -- but that's just a matter of communication pragmatics.

[elfin marten]

Okay.

How do i decide to work with infinite graph? Could you please give us some example?

@stray reef So in a graph Edges are also finite.

[stray reef]

you keep conflating "edges" with "the number of edges"

maybe this is a language barrier, i don't know

[elfin marten]

Edges = Number of edge

[stray reef]

if you keep saying it like that you will not be understood.

[elfin marten]

or number of ties , links or relations among vertices.

[weary tiger]

ann please what else could 'a graph edges are finite' mean..

it seems pretty obvious to me they mean number of edges is finite

[stray reef]

yeah but it sounds jarring at the very least

and bad wording only begets more bad wording which will eventually lead to node1 saying something confusing that actually is understood by nobody

[elfin marten]

😦

[weary tiger]

I think your comments are just unnecessary since the context is obvious, you corrected them once to be sure and its fine,

[stray reef]

i corrected them once and received the distinct impression that i was not being listened to.

[fallen pebble]

I have another question regarding the same subject. What if you wanted to find a subgroup of Sym({1,2,..,6}) with order 10? One of the generating permutation can't be commutative in that case, right?

[elfin marten]

Just asking, could anyone helps me to understand this equations where it defines infinite graph (i'm not sure just taken from internet) G = (Z, {(x, y, w) | (x, y) <- ZxZ, x != y})

[tranquil vector]

Last Halloween 20 different kids came trick-or-treating to my house and I gave out 100 identical pieces of candy in such a way that each kid got at least three pieces of candy. How many different ways could I have done this?

Would the answer be 40^20

[weary tiger]

no

[tranquil vector]

why not

oh 20^40 my bad

[weary tiger]

thats way too much

this problem is basically saying: in how many ways can you dsitribute 40 identical balls into 20 urns

[tranquil vector]

yeah there should be a lot right

give 40 to first person

or 40 to second

or 39 to one then 1 to another

do that for every combination

[tranquil vector]

What would be the answer then

isnt it C^s where C is the number of choices and s is the number of steps

[weary tiger]

the answer shoould be something like 60 choose 19

,w 60 choose 19

[vital dew]

Results provided by WolframAlpha

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

Requested by catfan1337#9812

[weary tiger]

do you know stars and bars techinque?

[tranquil vector]

oh ok that makes sense he told us to use the binomial coefficient

i was doing the problem that's 1 lecture ahead ig ill have to watch the lecture on it

[weary tiger]

actually my answer isnt correct but its something of this sort

its rathehr 59 choose 20 maybe

but yeah google stars and bars if you want to be able to do these kind of problems easier

[tranquil vector]

kk thanks

[weary tiger]

do you know why I restated the problem to this?

not this message but below that one

[tranquil vector]

yeah

[weary tiger]

aight

[tranquil vector]

that's exacly how I saw it

its why I thought it was like 40^20

[weary tiger]

[tranquil vector]

is C^s a thing or did i just make that up (C=# of choices, s=#number fo steps)

[weary tiger]

nah 40^20 says that you can give 40 to any person

40*40.....40 20 times

[tranquil vector]

oh yes youre right

ok thank you

would it be like 40^20 + 39^20 + 38^20

is that what the chose thing is

[weary tiger]

no

[tranquil vector]

nvm i dont think so

[weary tiger]

becasue thats even more

than 40^20

[tranquil vector]

oh yes ur right lol

ok thank you for the hepl

for this question

How many ways are there to place n distinct people into four different rooms so that there are at least two non-empty rooms?

the answer isnt this right

4^n + 3^n + 2^n

[weary tiger]

nope

just do it like that: 3 empty rooms and 2 empty rooms, those are all the cases

oh wait read that wrong, 2 nonempty, 3nonempty and 4 nonempty

[tranquil vector]

yeah so is my thing still wrong

[weary tiger]

yeah

these problems will pretty much always use binomial

[tranquil vector]

so this one is also wrong

How many ways are there to place n distinct people into four different rooms?

its not 4^n

[weary tiger]

nope

[tranquil vector]

rip

ok thanks

[weary tiger]

unless the rooms can be empty I guess?

[tranquil vector]

yes you can

except one

you can have all people in one room if you wan

or split them into 2/3/4

[weary tiger]

gotta go gl

[tranquil vector]

k thanks

[tidal tulip]

is the proper way to write “there is no integer that divides every even integer” in a formulaic expression:
~Ex in Z, Vy in E (set of even ints): x | y ?

[ember obsidian]

negating a whole statement requires brackets around the statement

~(blah)

[tidal tulip]

i’ll rewrite

~(Ex in z, Vy in E: x | y)

and if i want to negate that that would be

(~(~Ex in Z, Vy in E: x|y))

[ember obsidian]

brackets here are off

[tidal tulip]

and if i want to negate that that would be

(~(~(Ex in Z, Vy in E: x|y)))

[ember obsidian]

yes

[tidal tulip]

now if i were to write this out step by step do i put the inner negation sign in front of each term in the expression step by step until it pushes all the way through the expression

eg

(writing it now)

[ember obsidian]

yes

[tidal tulip]

like that ^

[ember obsidian]

without nested brackets on the main statement, "pushing" negations is ambiguous

[tidal tulip]

did i write it incorrectly?

[ember obsidian]

if u nested the main statement in brackets then pushing negation would've been unambiguous

with the commas there id just distribute negation all at once

[tidal tulip]

oh so each thing i negate should go outside the bracket

to indicate that’s the thing being negated and the next thing is inside the bracket

[ember obsidian]

$\neg(\forall x,P(x))$

[vital dew]

RokabeJintaro

[ember obsidian]

distribute all at once

$\exists x,\neg P(x)$

[vital dew]

RokabeJintaro

[tidal tulip]

ok so if i distribute all at once then my last line is correct

[ember obsidian]

yes

[tidal tulip]

k

the original statement

~(Ex in Z, Vy in E: (x | y))

is false because let x=1 then that’s an int that divides all even numbers

[ember obsidian]

yes

[tidal tulip]

k

and there is a similar problem “for all x, for all y in N; there is a z in N such that x | z and y | z.” i say that’s true and the negation of that statement is Ex, y in N, Vz in N: x does not div z or y does not div z — does that look correct

[ember obsidian]

yes

[tidal tulip]

k sweet thanks

[ember obsidian]

yw

[icy blaze]

i have a q like this

and to start

ive written out something like this

havent figured out how to express whetehr something is even or prime but

would using iff be right?? or should i use implies?? i dont really understand the difference in these statements

[livid drum]

Your current idea is almost correct.
But using the iff would be wrong.

Consider the following sentence: "Every prime number is odd."
Observe how it is different than this sentence: "Every odd number is prime."

The first in FOL reads "For every number x, if x is prime then x is odd."
The second reads "For every number x, if x is odd then x is prime."

Obviously the first is true while the second is false.
And obviously this false sentence communicates something different: "For every number x, x is prime iff. x is odd."

Hopefully this helps clear up the confusion.

[icy blaze]

thank you!! i get it now

as a follow up question lol im having trouble expressing whether a number is prime in FOL

this does not seem quite right

i cant tell what quantifiers to use to express a and b because i want it to say

that there is only pair of a and b that multiply to y, which is 1 and itself

but 1 and itself are a factor of every number

idk

actually i think if i use \exists for a and b it will be good

[waxen spire]

i am having trouble on what this means, can someone help me understand

Are these the correct equivalence classes? [a] = {}, [b] = {}, [c] = {a}, [d] = {c}, [e] = {}, f = {}, g = {d}, h = {b}

R = {(a,c), (c,d), (d,g), (b,h)}

[livid drum]

when you wanna express something like "y is prime" in this language, you'd expect the formula to have (at most) y as a free variable (since the truth of the expression would generally vary with the y's).
So once you've removed the quantifer over y, your expression successfully captures "y is prime", but you've got to include something to prevent 1 from being counted as prime.

[livid drum]

yo man, so you're given the set A (of 8 elements), and you're given R is some equivalence relation over A.
You should review what exactly that means.
you're not given explicitly the full table of all the things which are related.
But you're given enough to deduce the rest.
(Ill pm you a short skit to help)

[icy blaze]

thank u for ur help

u have good taste in pfps

[waxen spire]

i think it was wrong, is this more correct? R = {(a,a), (a,b), (b,a), (b,b), (b,h),(h,b),(h,h),(d,d),(b,c), (c,b), (c,c),(c,d),(d,c),(d,g), (g,d),(g,h), (h,g),(g,g)}

[dark geode]

guys i need a bit of help

The parabola y = x^2 is a polished mirror, and light reflects from any point on it such that the angle of incidence equals the angle of reflection.
A laser beam is fired from the point (0, 0) to the point (1, 1). Let (xn, yn) be the nth point of intersection of the laser beam with the parabola so that (x0, y0) = (0, 0), (x1, y1) = (1, 1), etc. Part (a): Compute (x2,y2), (x3,y3), and (x4,y4).
Part (b): Find a recursive relationship expressing (xn,yn) in terms of (xn-1,yn-1) for any n ≥1.
Part (c): Determine xn in closed form for any n ≥0.

i have found the first 5 points

(0,0), (1,1), (6,36), (35, 1225), (204, 41616)

but how would i go abotu doing part b?

[weak grail]

Hey guys isnt that solution a reflexive relation?

[stray reef]

this question

"the" relation

as if there's only one possible relation

"the" antisymmetric relation

as if there's only one possible antisymmetric relation

but the R that they give here does satisfy the definition of an antisymmetric relation...

[neat fog]

Why are these two statements not equivalent?

1. For some x<0, x^2>0
2. For some x in real number, x<0 implies x^2>0

While these two are?

1. For all x<0, x^2>0
2. For all x in real number, x<0 implies x^2>0

[pale epoch]

is there more context?

to me 1. just looks incomplete

[neat fog]

@pale epoch

[pale epoch]

ah ok

eh, let me think how to explain this

$\exists x (P(x) \implies Q(x))$ can be vacuously true when $P(x)$ is false for some $x$
for example $\exists x(x > 0 \implies x^2 = 0)$ is true, because if you choose $x= -1$ then $x > 0$ is false and $(x > 0 \implies x^2 = 0)$ is vacuously true
on the other hand $\exists x (x > 0 \land x^2 = 0)$ is false

[vital dew]

Lochverstärker

[pale epoch]

in your first example both 1. and 2. are true though

[neat fog]

I see

[pale epoch]

tbh writing stuff like your screenshot isn't great

generally you would not write down stuff like $\exists x>0(x^2 = 2)$ in first order logic

[vital dew]

Lochverstärker

[pale epoch]

in natural language its fine, but in first order logic its a bit weird

instead $\exists x(...)$ is better

[vital dew]

Lochverstärker

[olive condor]

Hmm… In my textbook (I think yours too), $\exists x<0 (x^2 = 0)$ is a shorthand of $\exists x (x<0 \land x^2=0)$. That’s why it’s not equivalent to $\exists x (x<0 \implies x^2=0)$. On the other hand, $\forall x<0 (x^2=0)$ is a shorthand of $\forall x (x<0 \implies x^2=0)$. That’s why they are equivalent.

[vital dew]

zacque

[olive condor]

So I think your exercise is to train you on recognising the shorthands and understanding what they actually stand for

[plain needle]

hi guys I need help with finite state machine application problem

am I right?

[elfin marten]

Hi, any algorithms to find or identify that given two graphs is an isomorphic graph?

[pale epoch]

for finite graphs sure

[elfin marten]

Yes, i'm referring to finite graph here.

[pale epoch]

just test every possible map (there are only finitely many)

[elfin marten]

There is two finite graph let say G and H and i would likes to find whether it's isomorphic or not. Well i'm looking for steps to solve such problems.

[pale epoch]

there are finitely many bijections between the vertices

and you can just check them all

(this will take a long time)

better methods are either probabilistic, require more structure on the graphs or are very hard to understand

[coral parcel]

Because what you want to say is $$\exists x\in\mathbb R \begin{cases} x^2>0 & \text{for }x<0 \ \mathsf{false} & \text{otherwise}\end{cases}$$ and $$\forall x\in\mathbb R \begin{cases} x^2>0 & \text{for }x<0 \ \mathsf{true} & \text{otherwise}\end{cases}$$ -- because "false" is the truth value that is neutral with respect to $\exists$ and "true" is the truth value that is netutral with respect to $\forall$. In the $\forall$ case we need to invent a special connective $\to$ to express the case analysis easily, whereas in the $\exists$ case it turns out that the already-existing $\land$ connective \emph{is just what we need}.

[vital dew]

Troposphere

[coral parcel]

The job of the material implication is to allow us to restrict universal the domain of quantifiers with a formula. For existentials, conjunction serves a completely analogous purpose.

[elfin marten]

How about solving in between two undirected graphs.

[coral parcel]

Same answer.

[prisma breach]

heya, I have a little question

$|\mathbb{N}| = א_0 $ $|P(\mathbb{N})| = 2^{א_0} = |\mathbb{R}|$