discrete-math

[hoary cloak]

mm yeah that beats me. i haven't read much about symmatry for planar graphs

glad that worked for you though

in fact it's not guaranteed that u can do this for every planar graph because this one in the example just happened to have nice bounds for this equation. depending on how the graph faces are, trying to prove the sum can't be zero might be pretty difficult

everything involving planar graphs is hard, i just accepted it at this point

except coloring them lol

ehhh, seems okay to me. are you insecure about some part of that

you can do \ before { and } to write set notation in latex fyi

[tidal tulip]

@hoary cloak i just wanted a double check to see if it looks good. thanks for the tex tip!

[haughty spruce]

Yep. The unfortunate thing is that one of them worked out to be >/= 2, </= 6 and the other was >/= 6, </= 18... they both have "6" in the set of answers and so they could equal zero...

So that's why I had to revert back to the old simple trick

Which I think I did correctly, accounting for all possible cases https://cdn.discordapp.com/attachments/496785905474994186/942966876621926470/IMG_1994.jpg

though idk if someone is able to check it

[floral field]

If we want to count the subsets of [n] with at least 2 elements, it would be 2^{n-2} subsets, right?

[n] = {1,2,3,...,n}

Which seems to generalize to subsets of [n] with at least k elements -> 2^{n-k} subsets

[stray reef]

no

the number of subsets of [n] with at least 2 elements is 2^n - 1 - n

which in general is bigger than 2^{n-2}

do not confuse "must contain at least two elements" with "must contain these two particular elements im pointing at"

@floral field

[floral field]

With the latter, wouldn’t it be 2^n - 2?

[stray reef]

it would not be $2^n - 2$ no

[vital dew]

Ann

[floral field]

Because [n] has 2^n subsets and then exclude the two cases u don’t want

Oh.

[stray reef]

what two cases lol

[floral field]

Oh wait, nvm I read this wrong

well I wrote the following combinatorial proof, and I was wondering how I would make sense of the n-2 in the question I pose

[stray reef]

this feels off

[floral field]

Shit

[stray reef]

i mean first off the number of ways to date 2 people at once is n(n-1)/2, not n(n-1), unless chad designates one of his dates as primary and the other as secondary and it matters for him who is which

and then it isn't made clear what n is. is n the total number of people on bumble excluding chad?

[floral field]

It would be the n people who reached out to him.

Wait, you’re right. I think I need to tweak my question

[stray reef]

i think i know how to salvage your thing

have chad pick a primary date (n), a secondary date (n-1), and then a subset of the rest of his matches (2^{n-2})

the latter being potentially empty

and then we could reframe it as first picking a subset of k matches from n (nCk), then picking a primary (k) and a secondary (k-1) from that

[floral field]

Have Chad pick a subset of the rest of his matches after picking a 1,2?

[stray reef]

yes that's what i said

[floral field]

And by “latter” do you mean the secondary date?

[stray reef]

no

i mean... well i guess i mean the third of the three things i mentioned

[floral field]

Ah, I see. Thank you!!

[odd dune]

Hello, help me please, i want to understand how to get the closed formula of a discrete conditional distribution

Letting V_h be any scalar element of V and V\h its complement

[old oasis]

Show that C, the set of complex numbers has the same
cardinality as R, the set of real numbers.

Anyone solve this problem.

[olive wren]

C is isomorphic to RxR

[old oasis]

Use rules of inference to show that if the premises
∀x(P(x) → Q(x)),∀x(Q(x) → R(x)), and ¬R(a),
where a is in the domain, are true, then the conclusion
¬P(a) is true. Given same premises except the last one now
given as R(a), then what about ¬P(a)? Is it true or false.

Anyone give me solution of this question.

[old oasis]

Sir , please give me written solution.

[olive wren]

Given (a, b) in RxR, send it to a + bi
That’s a bijection, so the cardinality of C is equal to the cardinality of RxR, which is the cardinality of R

[hoary cloak]

what kind of rule of inference are u allowed to use? this is just applying (p -> q) <-> (¬q -> ¬p)

[gilded marsh]

having trouble understanding how to solve this

do the x’s have to be set to the same numbers before I begin solving?

[gilded marsh]

My apologies

[coral parcel]

Looks right.

[gilded marsh]

I am on question c

[coral parcel]

They can't all be equal because 17 is not a multiple of 4. So you get to choose which of the terms is different. Then just count how many choices there are for the three equal terms.

[shadow geyser]

Can anyone explain how adding sets of numbers work?

Like what is the difference between Z + Q and Q + Z? where Z is the set of integers and Q is rationals

my professor was teaching us the Ehrenfeucht–Fraïssé game

and the way we looked at adding sets was to break them up into separate entities

but how does that make sense per se?

how can you just add two sets of numbers together like that?

[weary tiger]

Consider the set A$ = {a , b}$ and the set B$ = {d , e}$

The way that sums of sets work is the same as cartesian product, we take the first element from set A and add it to the respective components, then move on to the second element, and all the way up to n elements in your set.

A $+$ B $= {a+d , a + e, b + d, b + e}$

@shadow geyser

[vital dew]

Искатель

[shadow geyser]

these sets are infinite yeah

[weary tiger]

also, the sum for Z + Q and Q + Z are not the same because set addition is not commutative

[shadow geyser]

Right

but how do you visualize that

is my question

like can you show me an example of how Z + Q is different from Q + Z

[shadow geyser]

why is set addition not commutative also?

if you did B + A then it would be d + a, d + b, e + a, e + b

in this case you mean to say they are not the same order?

hence it is not commutative

[craggy juniper]

if a set $R$ is a relation on a set $A$, and $R = A\times A$, is $R$ reflexive, symmetric, and transitive?

[vital dew]

quantum

[craggy juniper]

i feel like the answer is yes but i want to make sure

just thought about it for a second and realized the answer is yes lol

how is the relation $R = {(0,0),(\sqrt{2},0),(0,\sqrt{2}),(\sqrt{2},\sqrt{2})}$ on $\mathbb{R}$ symmetric when there’s only two real numbers in $R$?

[vital dew]

quantum

[craggy juniper]

it says for all x,y in A

but only two elements of A are here in this case

[coral parcel]

How is that a problem?

[craggy juniper]

i guess the phrasing just confused me

oh wait i think i interpreted it wrong lol

[tranquil vector]

Six students are sitting in the front row of a classroom. Four of the students are engineering students. In how many ways can we arrange the six students so that the four engineering students are adjacent to each other?

I know the answer is 144

how do I get that tho

[silent hinge]

guys i am so lost. if you give me something like 112 =-43 (mod 5) cool i can figure it out:

112-(-43) = 155 = 5 *31 true

but i dont know what to fucking do when i see this crap

im refering to number 2

i cant find a similar example on the textbook and pick it up from there

[coral parcel]

Suppose three of the engineering students are late, so initially there's only three students to arrange. When all the engineers have arrives they huddle with the one who was there on time and agree on an order among themselves, without disturbing their collective position with respect to the non-engineers.

[tranquil vector]

yeah that's how I did it initially

I got 4! * 6

[silent hinge]

hello troposphere whenever you get a chance take a look at my question

[tranquil vector]

but how do I get the 6

because I want to be able to replicate this with larger numbers

so I can't just draw all the combinations each time

oh shoot its 3!*4!

so in a case with 9 people, 4 together it would be 4!*6!

is this right

[coral parcel]

Yes.

[tranquil vector]

ok thank you

[shadow geyser]

Hi there question

[coral parcel]

You know at leas one integer that is 1 mod 6, right? All the others are multiples of 6 away from it. 20 is small enough that I wouldn't bother with being clever, jusy write down all the solutions in a list and the count them.

[shadow geyser]

What is the difference between two orderings of sets? Such as if we take the ordering of Q + Z vs Z + Q

where Q is the set of all rationals and Z is the set of all integers

What exactly is this topic called as well? I'm trying to look up "linear ordering" and "ordering" but I don't seem to be getting any proper results

[coral parcel]

Typically this notation means that we're using the natural ordering in each of the original sets, and then decalaring that everyting in the left summand comes before everything in the right.

[shadow geyser]

My professor calls it a linear ordering but I'm not sure

[shadow geyser]

Okay

[coral parcel]

Linear ordering, or total ordering. These are synonyms.

[shadow geyser]

So they are like two different entities but side by side

[coral parcel]

yes.

[shadow geyser]

Q + Z where Q is on the left and then Z is on the right

and Z + Q is vise versa

[coral parcel]

(and you pretend they have no elements in common, such the number 5 that comes from Q is a different element in the resulting ordered set from the number 5 that comes from Z).

[shadow geyser]

Ah

Thank you troposphere

[shadow geyser]

Sorry troposphere one question

How would you identify specific elements within this ordering then?

Like if i wanted to take the ordering of Q + Z and I wanted to identify the number 2

Would I have to like say its from Q or Z?

I mean I recognize that its an infinite set of course

[coral parcel]

If you want to be formal about it you would say something like we're really looking at the set $({1}\times\mathbb Q)\cup({2}\times\mathbb{Z})$.

[shadow geyser]

for Q + Z?

[vital dew]

Troposphere

[coral parcel]

Yes, i.e. the elements are really pairs where he first part of the pair tells where the element came from and the second part tells which one it was.

[shadow geyser]

oh

so like

[coral parcel]

However, this notation is most often used for cases where we're not really interested in the elements themselves, but just in the order type of the resulting set -- that is, which other ordered sets it is isomorphic to.

[shadow geyser]

what would be a shortcut instead of writing it like you did

this may be dumb but if you write {{1/2},{3}} would that be considered

as like Q + Z

or do you have to write it out formally

[coral parcel]

That sounds a bit strange, and I'm not quite clear on what you mean. Each element in the final order comes from just one side of the +. There's not one from each.

[shadow geyser]

so

im overthinking this sorry

[shadow geyser]

so like from this

the 1 is within Q and the 2 is within Z

when identifying elements from specific domains

do we need to write it in such a format

that we create an inner set multipled by the domain

and union both domains

[coral parcel]

The elements of the order are things like
... < (1,-22/7) < (1,-2) < (1,0) < (1,1.5) < (1,1234.6789) < ... < (2,-1) < (2,-2) < (2,-1) < (2,0) < (2,1) < (2,2) < ...

All the rationals each paired up with a 1, followed by all the integers each paired up with a 2.

[shadow geyser]

for Z + Q?

Oh

oh wait

[coral parcel]

No, that was for Q+Z.

[shadow geyser]

oh so 1 and 2 were just

arbitrary numbers you picked

[coral parcel]

Yes, they're just labels.

[shadow geyser]

can the 1 and 2 be anything?

like variables even?

[coral parcel]

Yeah. Well, variables need to have a concrete value.

But you can use symbols if you want.

[shadow geyser]

I see

im trying to write first order logic with

orderings

hence im just trying to understand the difference between the two

[coral parcel]

Variables are always just placeholders for something else. You can't put the variables themselves into sets; what you get is just a set containing the thing the variable was a placeholder for.

[shadow geyser]

Oh

So what are symbols in this case?

like what would be a symbol you would use as a placeholder

[coral parcel]

Just something that you assert is not a variable, not a number, not anything that means something.

It becomes a symbol by your declaring it to be one.

It you're doing very formal set theory you might need to be specific about how to pick some mathematical object to play the role of your symbols, but in ordinary mathematical reasoning you can get away with expecting the reader just to pick something.

[shadow geyser]

Got it

Thank you Troposphere a lot

@coral parcel may I ask you one last question

sorry if im bothering you

can you define what "first order language of <" is supposed to mean?

i know what first order language is which is predicates

but im unclear of what the "of <" is supposed to mean

[coral parcel]

The logical language that has no constant symbols, no function symbols, and a single binary predicate written <.

[shadow geyser]

so thats supposed to represent a true or false condition

but its supposed to be written as a predicate

[coral parcel]

The formal syntax of first-order logic pretends that you're going to write <(x,y) in your formulas, but in practice when writing for human readers you just say x<y instead.

That's just a matter of readability.

[shadow geyser]

i see

alright thank you so much

definitely cleared up a lot of doubts

[silent hinge]

im sorry i just cant figure it out i know 7 is one of them but i really dont know what to do. i red chapter, watch my professors lecture, went to office hours its just not clicking

[coral parcel]

If everything else fails you'll just have to check each number between -20 and 20 separately.

[limpid fossil]

how can i find an exact expression to represent this for loop pseudocode?
for i = 1 to n:
for j = 1 to i:
print(j)

it looks like its 1 + 1 + 2 + 1 + 2 + 3 + ... 1 + 2 + 3 + ... n

[shadow geyser]

Hi I have a followup question

So when you're trying to write a sentence in logic using predicates

and your linear ordering is something like Q + Z

and you want to declare variables in order to create a relationship amongst them

Which set would you choose values from?

Like if you have for all x and for all y

in the linear ordering Q + Z

will x and y correspond to Q and then move onto Z?

or can x be in Q and y be in Z

[cerulean wind]

a(n) = n - m(m+1)/2 where m = floor(-1 + sqrt(8n - 7)/2)

[silver knoll]

Can anyone help me? Why is this always true?

It was something like it's true because x is all that exists in the universe in the latter statement?

[coral parcel]

It's just because if when you have "forall x forall y (something)", the something must also hold when you choose the same element for x and y.

[silver knoll]

Hmm don't quite follow what you are saying at the end. What would be the same element?

[gritty crescent]

In the hypothesis of your implication you propose that P(x,y) is true for all choices of x and y; in particular it is true when y=x, which is precisely what the conclusion of your implication says.

[silver knoll]

I'm sorry studying this in another language and it's hard to understand this when using another language.

But are you saying first statement that all x = y

Therefore because they are similar you can conclude that all x must be the same as all other x's?

@gritty crescent

[gritty crescent]

Okay let's try to see it with an example. Let's take our domain for variables to be the set {1,2}. When we say forall x forall y P(x,y), we say that P(1,1), P(1,2), P(2,1), P(2,2) are all true.

The conclusion of your implication says that P(1,1) and P(2,2) are true.

You see why we can always conclude that?

[silver knoll]

Yeah thanks, much clearer now

[gritty crescent]

Since P(x,y) is true for every such pair (x,y), it would definitely be true for the pairs (x,x)

[silver knoll]

Yeah I got it now, thanks a lot!

[gritty crescent]

No worries.

[compact yacht]

how to solve this?

[gritty crescent]

How is (A\oplus C) defined?

[vital dew]

Manan.

[gritty crescent]

Is it meant to be union?

[compact yacht]

it is symmetric difference

[gritty crescent]

Ah, okay

Have you tried anything so far?

Trying a few test cases could give you a feel for this

[compact yacht]

is this the right answer for 1st question

[gritty crescent]

Hurb

You have to determine that if (i) and (ii) hold, does it follow that A=B?

You can't assume that A=B

That's what you're supposed to prove/disprove, as the case may be

[compact yacht]

oh okay

since A-C and B-C both does not have element of C doesn't this also mean A=B?

[gritty crescent]

No

What if both A and B are disjoint subsets of C?

In that case, both A-C and B-C are empty, and therefore equal

But we can't conclude A=B here

[compact yacht]

Then how can i conclude A=B?

[gritty crescent]

You need to account for condition (ii) as well

Both (i) and (ii) form your hypothesis

[compact yacht]

how am I suppose to do that?

[vital dew]

Manan.

[tidal tulip]

could someone check my proof

I want to prove the $\rightarrow $direction of $A \backslash(A \backslash B) = A \cap B$

Proof

Let $ x \in (A \backslash(A \backslash B))$

$ \rightarrow x \in A \land x \notin (A \backslash B)$

$ \rightarrow x \in A \land \neg (x \in A \wedge x \notin B) $

$ \rightarrow x \in A \land (x \notin A \vee x \in B)$

$ \rightarrow x \in A \land x \in B$

$ \rightarrow x \in A \cap B$

$\therefore A \backslash(A \backslash B) \subseteq A \cap B$

[vital dew]

strings

[tidal tulip]

could someone check that proof

[stray reef]

yes this seems ok

[tidal tulip]

k awesome thanks!

[compact yacht]

Suppose that R1 and R2 are symmetric relations on a set A. Is R1 U R2 also
symmetric? Is R1 ∩ R2 also symmetric?

1st one is symmetric

but i don't know about the intersect

is it also symmetric

[coral parcel]

Can you construct an example where it isn't?

[compact yacht]

can empty set be symmetric?

[old oasis]

Anyone solve this problem.

[coral parcel]

Does it satisfy the definition of "symmetric"?

[old oasis]

Determine whether the set of integers divisible by 5 but not by
7 is countable or uncountable. For those that are countable
exhibit one to one correspondence between the set of natural
numbers and the set.

Anyone solve this problem.

[hard yew]

You've got to stop asking people to just solve your problems... Do it yourself or ask about what's confusing you about the problem

[old oasis]

Main confusion is how to start

[hard yew]

Start by writing out the premises and the conclusion, then think of a way to get rid of the quantifiers that bind P(x), Q(x) and R(x). After that it's just an application of simple rules of inference that you should be provided with in the textbook.

[compact yacht]

Give a transitive relation on the set {m, n, o, p} and contain (m, n) and (n, p)

for this R={(m,n), (n,p), (m,p)} is the transitive set?

or do i need to add more pairs?

[cerulean wind]

should be good.

[compact yacht]

okay thanks

[hoary cloak]

do you know what's the definition of a countable set? what kind of thing needs to exist for a set to be countable? this is my tip for you

i'm not giving you a lot of info really but if you know that, there's not much logic leaping needed in order to answer that

[hoary cloak]

also didn't you post this exact same question just yesterday or a few ago

i think i even responded to you

[hoary cloak]

.

yes i did lol

[hard yew]

He's been doing it for a while now

[ember obsidian]

@old oasis pls dont multipost

[hoary cloak]

i deliberately don't provide a detailed walkthrough when i responded but it would be nice if they read what i said. if you don't understand, ask me questions

[craggy juniper]

i’m not really sure what the “if and only if” is supposed to mean in this context. maybe it’s just because i have no idea how to start. could someone help?

does “if and only if” here mean the same that it usually does in a proof?

[ember obsidian]

it defines what xRy means

[coral parcel]

Yes.

[craggy juniper]

what?

[ember obsidian]

do u know what 'if and only if' means?

[craggy juniper]

yes

[ember obsidian]

xRy is declared to be true if and only if x^2=y^2 mod 4

[craggy juniper]

yeah i know, i just have no clue how i would prove it since it’s if and only if

oh wait

i got confused reading it

i’m not confused anymore

i think i accidentally read it as something like “prove P if and only if Q” lol

[hoary cloak]

yea even though this isn't what you need to do, proving if and only if usually works proving the implication both ways. you prove p -> q and q -> p or something equivalent to those
i know this is usually exhausting af but there's not much way around it

just hope that one way is far easier than the other. happens a lot in my experience

[severe swan]

this would be false correct? If the domain for both variables consists of all integers, what are these truth values? Q(x,y) is the statement "x + y" = "x - y" and if Q is Q(1,1) then 2 = 0.

[ember obsidian]

@hoary cloak yes Q(1,1) is false

[worldly knot]

i can't quite visualize how this question works.. could someone clarify?

[cerulean wind]

do you know about binomial coefficients?

like n choose k?

[hoary cloak]

i'll redirect the message to @severe swan

[ember obsidian]

mb wrong ping, yeah @severe swan

[hoary cloak]

haha no prob at all i don't mind

[tidal tulip]

could someone explain this notation? what is F what is T and could you provide a basic concrete example so i can see?

$\underset{T \in F}{\bigcup} T$

[vital dew]

strings

[lone raft]

F is a family of sets and we taking the union over every set T in F. An example would be $F = {{1}, {2}, {3}}$. We have $\cup_{T \in F}T = {1, 2, 3}$.

[vital dew]

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

[tidal tulip]

did you mean {3}

so that is equal to {1} U {2} U {3} = {1,2,3}?

@lone raft

[lone raft]

yeah.

[tidal tulip]

k that makes a lot more sense now

[lone raft]

thanks, didn't see that.

[tidal tulip]

no problem ty for helping me understand

[fleet sail]

can someone help me urgently please

Please please

Consider S={ (a,b) N x N| a+b is even} . Reply:

Recursively define the set S.

[subtle juniper]

P,Q,R are logical statement. Decide the truth tabel for the expression:

anybody understand how to solve tthis

[haughty garden]

Make the table and use the truth table for the implication. Each of P, Q and R can take one of two values; either it is true or false

[craggy juniper]

make a truth table for $Q\lor R$, then $P\land(Q\lor R)$, then $P\lor R$, then finally $(P\land(Q\lor R))\implies(P\lor R)$

[vital dew]

quantum

[craggy juniper]

@subtle juniper

[subtle juniper]

Oh sry, i solved it guys

I forgot to mention it here

But thanks anyway 🙂

It was just the last part that confused me, I've never seen if then symbol

=>

[wide vine]

does discrete math have any connection with things like taking some continous functions and trying to graph it via some discrete step values?

I was interesting in something like this

and how the whole maping works

seems with more bits you can get better step size and more precision but also you don't have to space your values evenly

and like you could space out your bits so you focus more on a specific portion of interest I assume?

like here you might prioritize the bits into the regions between the orange bars compared with the whole time interval

let me know if you have some more information or if there is a more apprioate channel to ask

[hoary cloak]

buddy i'm not entirely sure if you wanna talk about numerical analysis but it sounds like it

usually the topics here are different from that, but if it doesn't fit in any other channel i think u can ask here

or #computing-software maybe

[gilded finch]

It is more about signal processing, but there is not channel for it AFAIK. For your questions, see

• https://en.wikipedia.org/wiki/Sampling_(signal_processing)
• https://en.wikipedia.org/wiki/Pulse-code_modulation
• https://en.wikipedia.org/wiki/Nyquist–Shannon_sampling_theorem (very important theorem)

and like you could space out your bits so you focus more on a specific portion of interest I assume?
Yes, and these depend on the application. In practice linear quantization is quite acceptable most of the time.

[sleek loom]

Could someone check my proof? Relations in discrete math

R, S and T are relations ofc
I’m not sure if I was right in assuming (b,c) can be in either T or S
Or should I have assumed a different variable instead of b for one of them

[atomic sand]

Not sure if this is the right channel but
If I have elements in a summation then is the derivative of the summation with respect to a different summation index:
$$\frac{d p_{a}}{dp_{b}}=\delta_{ab}$$

[vital dew]

june

[stray reef]

alright so this should be simple but i'm drawing a blank here:

Let G be a graph with more than 200 edges in total such that each vertex has degree at most 10. Prove that there exists an independent edge set of size at least 11 in G.

presumably nothing fancy (beyond like, the handshake lemma) should be required to answer this but like

other than obtaining a lower bound for the number of vertices i cant think of anything

[austere cedar]

@stray reef start adding edges to your set. For each edge you add, there are at most 18 other edges which have a vertex together with the edge you just chose, meaning that you can't add them to the set any more. So after k chosen edges, there are still 200-19k edges left to choose. As 200-19*10>0, you can choose at least 11

[stray reef]

can't there be edges that get excluded trice

oh wait nvm

[hoary cloak]

i was trying to solve this by doing some coloring but that seems correct and simpler

poggers

[winter shore]

{w| w is any string in a∗b∗}

Hi I don't understand the star operation in Deterministic Finite Automata

[olive wren]

The kleene closure is an operator on a language. It’s basically the union of all words that you can create by taking words in the language and concatenating them together.
In this case, a* is a string of as of any length.
So ab could be like aaaabbbbbbbb, etc

[winter shore]

so basically

is it like {e, a, b, ab, ba...}

numbers of alphabet that the DFA needs to accept

what I don't get is how this DFA works

why does not this DFA accept 'ba' though?

[olive wren]

Why ba?

In ab, the as come first

[winter shore]

so basically anything that comes with 'a' first it will accept?

[olive wren]

No

It’s something with a bunch of as then a bunch of bs

So like $a^nb^m$ where $n,m\geq0$

[winter shore]

it will accept a empty string or epsilon also right ?

[olive wren]

Yes

[winter shore]

I am still confused

so it will accept 'ab' aabb

but not 'ba, bbaa'

[olive wren]

Yes

[winter shore]

ok so if its was like {w in any string in b * a * }

then it would only accept bbbaaaa and ba

[olive wren]

Yes

[winter shore]

it does not accept 'aaba'

[olive wren]

Correct

[winter shore]

why doesn't this accept 'aaba'

[olive wren]

Are you asking why doesn’t it or why shouldn’t it?

[winter shore]

why it doesn't

[olive wren]

Because it ends up on the third state

Which isn’t an accepted state

[winter shore]

I get that but why

my question is why isn't 'aaba' valid?

[olive wren]

You’re being ambiguous.
Are you asking why aaba isn’t in the language or why aaba isn’t accepted by the DFA?
If it’s the first, it’s because the language only has strings in the form a*b*, so strings with a bunch of as then a bunch of bs
If it’s the latter, it’s because the two abs keep it on the first state, the b brings it to the second, and the last a brings it to the third

[winter shore]

oh I think I get it , so basically it has to be like 'aaabbbb' or 'bbbbaaa'

[olive wren]

No

Not bbbbaaa

[winter shore]

but It can't accept 'abba' or 'bbbbabbba'

[olive wren]

It’s literally a*b*

The abs are before the bs

A string of as, then a string of bs

[winter shore]

ok

so

{e, a, b, ab, aabb, aaaabbbbb} and so on right?

[olive wren]

The number of as doesn’t have to equal the number of bs

[winter shore]

oh ok

it's make sense now

also

how do I know the number of total states in a DFA such as L1 U L2

for example this questions, how does the L1 'intersection' L2 has 12 states

[olive wren]

It depends on how you write the DFA?

[winter shore]

L1 has 4 states and L2 has 3 states and L1 'intersection' L2 has 12 states

when I do I usually do 2^(# number of states in l1 + l2)

[hoary cloak]

so question for u graph theory people: given a graph G, connected, and with minimum vertex degree k >= 2, and a longest path in this graph that goes from v1 to vm, v1 has a neighbor vi in the path and vm has an vj neighbor and j < i, the goal is to prove that G contains a cycle of length either n (number of vertices) or at least 2k

i proved previously that this graph contains a cycle of length at least k+1 so i can assume that true

and i managed to prove that true for specific cases like x1 is a neighbor of xm, then there can be no vertex outside that path and therefore the cycle includes everything

[humble gust]

Why is belonging of a set not transitive? Say I have two sets B= {1,2}, and A={T, U, {1,2}}. So, is it wrong to say, 2 ∈ A? If Yes, Why so?

[hoary cloak]

the elements of A are T, U and {1,2}. 2 isn't equal to any of that

so correct 2 doesn't belong to A

it sounds weird but imagine i give you a set thay only has other sets. if you say that a number inside one of those sets belong to the big set, wouldn't i contradict myself

say, the set of all subsets of some A

[humble gust]

Ok. But, take this example instead.
Say There is a company T. It owns 3 different sub-companies. Let it be A,B,C. And A owns companies U and K. So, T= {A,B,C}, A={U,K}. So, is it wrong to say that T also owns U and K?

[hoary cloak]

ok so i thought for a moment and i think the thing that is confusing you is that you're thinking of something concrete and doing a reduction, and the matter here is just what a set is. there are ways to model this situation (using graphs for example) which can give you more useful info i think

like depending on how you model your stuff, you can make out conclusions about the stuff you're modelling

so it works the other way around

[humble gust]

Ah Okay. I am following the Paul R. Halmos Book "Naive Set Theory". In the book , he kind of vaguely gives how to think of belonging is not a transistive relation and told the reader of to think of compaines (in a way). So I created a somewhat concrete example out of that

[hoary cloak]

mm yes. im trying to come up with a better example

uhh do you program?

if you code stuff, you can think of it like this. you have a matrix or list of lists or some simple structure like that. and in one of those lists there's a 2

you won't find this 2 by indexing the matrix, infact you'll only find lists. you have to index one of those lists to find the 2

i hopw that helps clearing it out

[humble gust]

Ah Thenks. That will do.

[agile magnet]

yea I think if you're a CS person the best way to explain that thing is type checking

{2} and 2 are different objects

2 is not in A because {1, 2} is a different object than the number 2

[mortal hemlock]

How do you prove this?
$$ \sum_{k=0}^{2n} (-1)^k \binom{2n}{k}^2 = (-1)^n \binom{2n}{n} $$

[vital dew]

Loxvan

[burnt anvil]

hello

[cosmic wadi]

Hi guys. Is there a simple way to type these symbols out?

[dark maple]

hi

wowie! this sure is difficult!

[hard yew]

Why delete?

[cerulean wind]

induction

i don’t see an obvious combinatorial or bijective argument

[cerulean wind]

and it’s not true as written. just take n = 1

the square needs to be removed

[coral parcel]

A combinatorial proof: Let S={1,2,3,...,2n}. Let a k-configuration mean a pair of functions f: S->{0,1} and g: S->{0,1} such that sum_i f(i) = sum_i g(i) = k, and call a configuration odd or even according to the parity of k. The left-hand side of the identity is then the number of even configurations minus the number of odd configurations.
There is an self-inverse way to turn an odd configuration into an even configuration or vice versa: Take the smallest i such that f(i)=g(i) and flip the values of both f(i) and g(i). This matches most of the odd configurations up to even configurations such that they cancel each other out. The only configurations this doesn't work for are ones where f(i) != g(i) for all i. Such a configuration must be an n-configuration (so they are all odd or all even depending on the parity of n), and it is given exactly by the size-n subset of S where f(i)=1. Therefore there are exactly (2n choose n) unmatched n-configurations, which agrees with the right-hand side of the identity.

[coral parcel]

Seems to work fine. For n=1 the identify unfolds to 1²-2²+1² = -2 which looks true to me.

[cerulean wind]

i need to stop doing math and gts

wow. got my very active badge back tho

[willow fog]

eyyy gg

[weary tiger]

Could somebody help me figure this out?

[tidal tulip]

can someone help me understand this notation? could the {x_i for i in I} be re-written as {x_i | i in I} and where I={1,2,3} this set would be written as {x1,x2,x3}? and for (xi)i in I, if I=3 would this represent an n-tuple and if I={1,2,3} then this would be written as (x1,x2,x3)?

[lone raft]

yes, {x_i for i in I} is the same as {x_i | i in I}

[tidal tulip]

what about the (x_i) i in I notation

is my understanding there correct

[lone raft]

Yes, tho not sure mean by what I = 3. If you meant the cardinality of I is 3 then I = {1, 2, 3} in which you are correct. Also note elements of I can be anything, not just natural numbers.

For example if I = {a, b, c}, then (x_i)_{i in I} = (x_a, x_b, x_c).

Notation sucks since I am not using latex.

[tidal tulip]

ah yes that makes sense. if i wanted to write this out as a "for loop" in a step-by-step manner using this notation then would it be correct to write if I={1,2,3} then (x_1) 1 in I, then (x_1, x_2) 2 in I, then (x_1, x_2, x_3) 3 in I

[lone raft]

No, makes construct the ordered tuple (x_i) where taking i from I.

[tidal tulip]

how would i write the tuple one by one using the (xi) i in I notation then

[lone raft]

It hard to write since I don't know what I is, but if $I = {1, 2, 3}$, then $(x_i)_{i \in I} = (x_1, x_2, x_3)$.

[vital dew]

Plegasus

[tidal tulip]

yeah but if you were to look at it like a computer program then $I = {1, 2, 3}$, then $(xi){i \in I} = (x_1, x_2, x_3)$. where the first step i=1 then wouldn't it look like $(x1){1 \in I} = (x_1)$ , then the next step $(x2){2 \in I} = (x_1, x_2)$ etc?

[vital dew]

strings

[tidal tulip]

didnt get the subscripts but get the idea

[lone raft]

I see where your going with this, here i runs through every element in I. The subscript notation is just there to remind us.

[tidal tulip]

ok, would what i did be a correct way to run through the i's step by step to generate the 3-tuple in that example?

but in general the notation is written where you don't do that and just write the expansion

[lone raft]

hold on sec, I need to double check some stuff about this.

[tidal tulip]

k

not sure how spaces work here lets try this

$I = {1, 2, 3}

$(x_1)_{1 \in I} = (x_1)$ ,

$(x_2)_{2 \in I} = (x_1, x_2)$

$(x_3)_{3 \in I} $ = $(x_1, x_2, x_3)$

[lone raft]

Following what you did, if $(x_1){1 \in I} = (x_1)$ following with that we see $(x_n){n \in I} = (x_n)$. So what you did for n = 2 is not valid.

[vital dew]

Plegasus

[tidal tulip]

like if this were computer program doing it line by line

would this be how itd look with that notation

[vital dew]

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

[lone raft]

in this was a computer program, you will have array\list whose size is determined by cardinality of I, in which you loop through the index set I and set it corresponding value in the array.

[tidal tulip]

yeah but using this notation is that how i could generate the tuple

line by line

as it loops through I

[lone raft]

Yeah I am not following anymore, why you trying to generate the tuple?

[tidal tulip]

ok nvm

so when i see that notation

[lone raft]

sorry, I could not help.

[tidal tulip]

just write out the expansion

[lone raft]

yeah.

[tidal tulip]

k

i'll try to tex it up

$I = {1, 2, 3}$

$(x_i)_{i \in I} = $(x_1, x_2, x_3)$

[lone raft]

yes.

[vital dew]

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

[tidal tulip]

ok, awesome ty

i was super confused by that but understand it now

[lone raft]

My question now would be, when defining tuples as above, I has to be an ordered set right?

[tidal tulip]

yeah you're right

it has to be?

[coral parcel]

It would be somewhat unusual to call the result a "tuple" if you don't have a particular ordering of the index set in mind, but it's not implicit in the notation that is needs to be ordered.

[undone bough]

I don't know if I'm overcomplicating this, but I'm asked to prove that for some function F with codomain $Y$ and $C \subseteq Y$, that $F(F^{-1}(C)) \subseteq C$. My approach is that, by definition of inverse, $\forall y \in F^{-1}(C), F(y) \in C$, hence $F(F^{-1}(C)) \subseteq C$. Although I don't feel quite right about it. Any thoughts?

[vital dew]

Expert Thinker El Rey

[gritty crescent]

Looks good

[weary tiger]

anyone know how to latex the power set of some set A?

[coral parcel]

$\mathcal{P}(A)$?

[vital dew]

Troposphere

[stray reef]

$2^A$

[vital dew]

Ann

[coral parcel]

Some prefer $\mathscr{P}(A)$ or even (yech!) $\wp(A)$.

[vital dew]

Troposphere

[weary tiger]

thank you

I also had a question for anyone who could answer:

how can we show that $\mbb{R}$ and $\mbb{R}^2$ have the same cardinality? how can we compare the cardinalities of, say, $\mbb{R}$ and $\mbb{Q}$, or $\mbb{R}$ and $\mbb{N}$ I know that the cardinality of $\mbb{R}$ $>$ $\mbb{N}$, but why?

[vital dew]

Renegade

[weary tiger]

I'm (guessing) thinking that this is because a bijection cannot be made? However, just acknowledging that isn't really mathematically rigorous is it

[coral parcel]

Well, of course it is because a bijection can/cannot be made -- that's the definition of "have the same cardinality".

[cerulean wind]

do you know that |X| < |P(X)|?

[coral parcel]

A useful stepping stone is to know that $|\mathbb R|=|\mathcal P(\mathbb N)|$.

[vital dew]

Troposphere

[weary tiger]

cardinality of some set X is less than the cardinality of it's power set?

[cerulean wind]

yes, this is cantors theorem

[weary tiger]

uhh

[weary tiger]

that's not very intuitive

why is it equal to the power set of N? , I mean, it makes sense for it to be so because then logically this means that R must be > N but

[weary tiger]

makes sense

since the power set also contains the set itself

[cerulean wind]

that’s not the reason

think about finite sets first

[weary tiger]

uh

wait I'm an idiot

yeah, that's not the reason mb

[coral parcel]

I'm not sure it is particularly intuitive that |R|=|P(N)| -- but it's the most fundamental fact we have about the cardinality of the reals, so it needs to be remembered.
If you have the Cantor/Schröder/Bernstein theorem available, it is fairly easy to prove by coming up with injection R -> P(N) and P(N) -> R.

[tidal tulip]

this is a simple problem but want to make sure im not making a mistake:

if X subset A, X subset B prove X subset A intersect B.

proof:

let X subset A, let X subset B
let x in X. due to the definition of subsets x in A and x in B thus x in A intersect B and since x in X, X subset A intersect B

[weary tiger]

so.. I should take it for granted?

[cerulean wind]

u can get an “explicit” bijection using binary expansion of all the numbers between 0 and 1

[weary tiger]

I don't like that tbh but I'm guessing a reason would need me to be more experienced with this

[coral parcel]

Yeah, but dealing with the corner cases of 0.01000....=0.001111... etc. makes the explicit bijection a piece of fiddlework compared to the CSB proof.

[coral parcel]

You don't have to "take it for granted", there are plenty of proofs -- but you do have to keep it in mind.

[cinder sentinel]

i need help with propositional algebra

[weary tiger]

I see

[tidal tulip]

does this look reasonable to anyone

[cerulean wind]

looks good

[weary tiger]

thanks guys

[tidal tulip]

k ty

[cinder sentinel]

Can someone help me

[tidal tulip]

i want to prove or disprove if n|m then nZ is a subset of mZ. i say this is false: it nZ is a subset of mZ, then every element in nZ is an element if mZ. but consider n=3, m=15. 3|15 and 3 is in 3Z but 3 is not in 15Z since no integer multiple of 15 is equal to 3, therefore this is false

can i get a proof check for ^

[weary tiger]

hey, have been doing some more work with set theory and came across:

$\text{cardinality} (\wp(A)) = 2^{\text{cardinality}(A)$

so what you said about the cardinality of the power set is $>$ the cardinality of the original set makes sense

[vital dew]

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

[cerulean wind]

yes

nice

[tidal tulip]

this ok

[indigo tinsel]

This is probably dumb, but what is the negation of a cross product?

How can I prove that this is false I guess is what I'm asking

[pale epoch]

the overline is probably complement (in the universal set)

[indigo tinsel]

Why is the universal set the complement? Sorry for the elementary questions. First time taking a discrete class.

[pale epoch]

the universal set is not the complement

but the word complement only makes sense with respect to some other set

like $\overline{A}$ is the set of all elements in the universal set, that are not in $A$

[vital dew]

Lochverstärker

[indigo tinsel]

Okay, that makes sense but why would this statement not be true then?

Because it is still everything not in x and not in y

[pale epoch]

what makes you think it is not true?

[indigo tinsel]

Because our professor gave us the final solution. I didn't get it right haha..

[pale epoch]

hm

then your professor should have a counterexample

i think edge cases work

what if one set is empty...

[indigo tinsel]

Hold on, here is the solution given: False. Let X=Y={1} and U = {1,2}. Then $\overline{X×Y} = {(1,2),(2,1),(2,2)} and $\overline{X} × $\overline{Y}={(2,2)} Why is x X y that set with our given example?

[pale epoch]

ah ok, that works yes

[indigo tinsel]

I'm confused, why is the set overline{X x Y} = {(1,2),(2,1),(2,2)}

[pale epoch]

$X \times Y = {(1, 1)}$

[vital dew]

Lochverstärker

[indigo tinsel]

Right

Oh, it's everything in U excluding that pair..

[pale epoch]

so the complement of that is everything in $U \times U = {(1, 1), (1, 2), (2, 1), (2, 2)}$ that is not $(1, 1)$

[vital dew]

Lochverstärker

[pale epoch]

indeed

[indigo tinsel]

I see

Thank you so much

And just to confirm, for the compliment x X compliment y, it is because neither y or x can be one. That is the reason only (2,2) is the result?

[pale epoch]

yeah

[hard yew]

You're overcomplicating things

What can you conclude is true from the first premise: (X->Y)andA?

After that, it's the same for the second premise

And use the law of syllogism as the third step

Should be a little clear what the next step would be after these

The premises are all true

Yes

But also X->Y is true

[vital dew]

Alter

[hard yew]

Yes

[vital dew]

Alter

[somber idol]

ya

[hard yew]

You already have everything you need

Just one final step

Although I'd first simplify premise 2 before conjunction

And you won't even need to use conjunction because you'd have sth of the form

[somber idol]

right

[vital dew]

Alter

[somber idol]

Hm

[hard yew]

Did you figure it out?

[somber idol]

no

[hard yew]

No no no

Delete this, totally unnecessary

[somber idol]

tough

[hard yew]

From here

When is 8. true?

Or when (X->Y) is true and W is true right?

And do you know whether X->Y is true or not?

Also, just to note, the implication would be true, but you cannot conclude that W would be true from this. I'll explain later

Reread all the previous premises you have

[somber idol]

to get rid of A

[hard yew]

Right!

[somber idol]

how do we know w is true

[hard yew]

And if you have $T\to W \equiv T$

[vital dew]

Alter

[hard yew]

What is the truth value of W?

[somber idol]

true?

[hard yew]

Yes

Just a question, why isn't it false?

[somber idol]

Im clueless

[hard yew]

Uh, so you don't know why it is true?

[somber idol]

wait i got it

[hard yew]

The implication p->q is true when p is true and q is true, it is also true when p is false

[somber idol]

yah

[hard yew]

We know for sure that p is true

So q must also be true

[somber idol]

Thank you so much

[hard yew]

Yep, that's the one

[hard yew]

No problem

Always start simple with these and build up your premises

Oh right, before I forget

p->q is also true when p is false, but we cannot conclude in any way whether q is true or false here

It's a pretty common fallacy that had some name I always forget

@somber idol

[somber idol]

oh

okay

[weary tiger]

Hi, I'm new here. Any help would be appreciated with this. I don't know how to prove question a). I know that i have to prove theta(p(n)) is theta(n^k).. for p(x)= c0, c1x, c2x^2,..., ckx^k and p(n)= c0, c1n, c2n^2, ..., ckn^k... I believe that I just need to prove that c1g(n) >= f(n) >=c2g(n) for all n >= n0. Completely lost... I know that p(n) needs an outer bound and a lower bound for it to be theta bound... so I'm guessing I just need to pick any constants that show that c1g(n) is a big O bound and that c2g(n) is a big omega bound for p(n)?

[hard yew]

How do you get (7) from (6)?

Oh

Yeah, that looks right

If you want to practice these, think about what you can do differently from (6) using (1). But what you have is already very correct

[somber idol]

uhm can we just say Z is true because if one of them has to be true in (Z v ~X) and we know X then Z must be true

and ignore the left side of 6 as in (Z v Y) through simplification

[hard yew]

Yeah, that follows from (7)

What I had in mind reading it the first time was:
(7) (Z or Y) and Z (cause X is true)
(8) Z from (7) by absorption law
(9) X and Z

But your solution is better though

[vital dew]

Alter

[hard yew]

You can prove this by cases.

1. Let p be true, then...
2. Let p be false, then...

Or using other laws

[jolly rivet]

Does anyone know how to write this in symbols
No vegetarians eat meat.
All vegans are vegetarian.
∴ No vegans eat meat.
I would need to use ∀ and ∃ right

[hard yew]

Start by noticing which are the propositions

Then apply the quantifiers appropriately

And retranslate them to see if what you came up with is equivalent to what you've been given

[jolly rivet]

So would it be
t= vegetarians
v = vegans
m = eat meat

then I could do like

t -> ~m

[hard yew]

Ah hold on

You need sth like

T(x): x is a vegetarian

So that you can quantify it

[jolly rivet]

wait and what does T represent

sorry I'm still confused with discrete math after taking basic logic

Is it like the set of all vegetarians

[hard yew]

Right, I'm kinda explaining this badly

Let's take the domain to be all people right?

[jolly rivet]

yup

[hard yew]

No vegetarians eat meat.
is the same as
If a person is a vegetarian, then he doesn't eat meat.

[jolly rivet]

yup

[coral parcel]

It would be more faithful to render it as "there is no person who is a vegetarian and eats meat", though.

[jolly rivet]

so like ∀ x ∈ T, ~M(x)

[hard yew]

Hmm... do you mind explaining this problem?

[coral parcel]

Which problem?

[hard yew]

I feel like I'm just gonna end up causing more confusion cause English still feels a little weird with logic to me

[hard yew]

this request

[coral parcel]

Sorry, don't mind me, it was just a drive-by comment.

[hard yew]

Ah then lemme think about a clear way to explain

[jolly rivet]

Oh sorry ya I think my teacher just wanted us to write it symbolically

[hard yew]

Domain: all people
No vegetarians eat meat.
is the same as
For all people x, if x is a vegetarian, then x doesn't eat meat.

Let:
T(x): x is a vegetarian M(x): x eats meat

Does it feel easier now to write the statement

No vegetarians eat meat. ?

@jolly rivet

[jolly rivet]

So it would be like ∀ x ∈ T, ~M(x)

[hard yew]

Not quite

[jolly rivet]

For all vegetarians they do not eat meat

hmmm

[hard yew]

It'd be sth like

(For all x) - this means for every person to exist
(If x is a vegetarian) - if T(x)
(then x doesn't eat meat) - then not M(x)

[winter shore]

how do I make a NFA where the second last symbol is a. I made a DFA using it but confused on NFA

[jolly rivet]

so like T(x) -> ~M(x)

[hard yew]

Exactly

But we're missing the quantifier

[haughty garden]

Semantically DFAs are NFAs so if you’ve drawn up a DFA, you’ve also drawn up a NFA

[jolly rivet]

So like ∀ x ∈, T(x) -> ~M(x)

[coral parcel]

Sorry, another drive-by comment: Bean, do you feel that you have to write a ∈ if you use a ∀ symbol?

[hard yew]

I was just about to explain that part

So when we declare the domain to be all people, then we dont need to specifiy that x belongs to the domain

[winter shore]

true but I feel like my NFA can be much simpler than my DFA

[jolly rivet]

ya tbh I still don't really know the meaning of ∈ I thought it was just format

[hard yew]

it means "belongs in"

Or "belongs to"

[winter shore]

@haughty garden NFA seems more general so it's bit hard for me to fully grasp

[jolly rivet]

∀ x, T(x) -> ~M(x)

[hard yew]

Yep

[jolly rivet]

So would it just be this

nice

[hard yew]

Yes, thats the first one

[jolly rivet]

so thats the first line

[hard yew]

Can you translate the second one for me?

[jolly rivet]

then V(x) x is a vegan

[hard yew]

Okay

What else

[jolly rivet]

∀ x, V(x) -> T(x)

[hard yew]

Eh

Youre saying: All vegans eat meat

But the second statement is:
All vegans are vegetarians.

[jolly rivet]

Oh whoops

[hard yew]

Yeah, that looks ok now

How would you translate that second statement in english?

As detailed as you can be, how would you read it?

[jolly rivet]

For all people if they are vegan then they are vegetarian

[hard yew]

Yes

And the conclusion?

[jolly rivet]

Then the last one

∀ x, V(x) -> ~M(x)

[hard yew]

Yep

[jolly rivet]

For all people if they are vegan then they do not eat meat

So if I put it all together it's

[hard yew]

Exactly

[haughty garden]

It depends on how you’ve constructed your DFA. An NFA can be precisely its DFA if every transition label and state uniquely defines a state transition.

[jolly rivet]

Domain x : all people

M(x): x eats meat 
V(x) x is a vegan
∀ x(T(x) -> ~M(x))
∀ x((V(x) -> T(x))
∀ x((V(x) -> ~M(x))

[hard yew]

Right

But I should mention one more thing

[jolly rivet]

And is this valid by hypothetical syllogism

[hard yew]

Yes

But when using quantifiers

You should be careful of which proposition they bind

Or rather, which propositions are in their scope

What I mean is

[jolly rivet]

Yup I'm study a lot this week. Finishing up an intensive course so I'll finally have a lot of time

[vital dew]

Alter

[hard yew]

We want the second version

[jolly rivet]

Oh so should I fix that on all

[hard yew]

So that there is no room for confusion

[hard yew]

Yes

[jolly rivet]

and do I need the comma

[hard yew]

Nope

[jolly rivet]

ok thank you!

[hard yew]

No problem

You can try this with domain being vegetarians for practice, although not sure if it'd be as intuitive

[jolly rivet]

Also I have did this other problem and was wondering if I need to change it now that I used quantifiers

ok thank you

is this still a valid answer

[hard yew]

I wouldn't count it as correct if I was your prof and I have taught you logic functions and quantifiers before handing you the assignment depends

I mean, does it ask you before to use quanrifiers like the one we just did? @jolly rivet

Also, note that when we give meaning to propositions p, q, r... etc. we do it with :, not =

[jolly rivet]

Oh so I guess I would need to change it

[hard yew]

Just this, the rest actually seems fine

[jolly rivet]

Just changed that

also this is the question so I think it's fine

[hard yew]

Ok then it is fine

[jolly rivet]

Since it doesn't specify quantifiers

[hard yew]

If you were asked to do it with quantifiers then you'd have to redo it to be the same as with the vegans

[jolly rivet]

yup

I guess I could have also done the vegan questions without quantifiers right

[hard yew]

Not really

There is no way in logic to express the quantifiers

Unless you want to list every single element in the domain with conjunction/disjunction

$\forall x P(x) \equiv P(x_1)\land P(x_2) \land P(x_3)\land...\land P(x_n)$

[vital dew]

Alter

[jolly rivet]

huh I see

[hard yew]

Domain: all people T(x): x is a vegetarian M(x): x eats meat "There is no person who is vegetarian and eats meat."

[vital dew]

Alter

[hard yew]

@coral parcel is this what you meant?

[coral parcel]

Yes

[hard yew]

I guess I sort of skipped all the way to the end

It seemed easier to show that the conclusion follows that way though, instead of having to go through logically equivaleng transformations

Had me confused a little bit

[jolly rivet]

Oh wait so should I change it

[hard yew]

No

They're logically equivalent

[vital dew]

Alter

[jolly rivet]

Oh ok thank you!

[hasty dawn]

does anybody understand onto

if x is mapped to y then every item in y has to have a corresponding x

but if there was a y that doesnt have an x then why is it still considered in the codomain

wouldn't it just not be part of the y set at all

[gritty crescent]

The set of images of your function form the range (or just image). If your range is equal to the codomain, then your function is surjective, and conversely.

[stray reef]

@hasty dawn think about a cloakroom in a movie theater or something

on a particular day, each person going to the movie theater leaves their coat in the cloakroom and gets a numbered tag that they use at the end of the day to get their coat back

you can view this as a function from the set of movie-goers to the set of coat rack numbers

this function being onto means that the cloakroom is full

i.e. every number is given out to someone

but of course it doesn't need to be full, and we don't stop considering rack #94 to be in the codomain just because there's no coat hanging on it

[hasty dawn]

hm in this case it makes sense cuz a position for hanging can exist even without a coat

[stray reef]

yes exactly

every function can be made onto by restricting its codomain to its range

but doing so is usually an unnecessary overcomplication

[hasty dawn]

hmm

so whats the dif between codoomain and range/image

are range and image interchantable?

[stray reef]

yes

usually image is preferred as range can be ambiguous

[hasty dawn]

if a function is mapped from x in R and y in Y and the function looks like y=x^2 there can never be negative values for y

but are we allowed to arbitrarily increase one of the ranges to allow for a random negative number and that way we can make an onto statement become not onto

like for example y = x^2 OR y = -1

then would the thing go from onto to not onto

[weary tiger]

If A\B = B\A for any sets A,B

Then if I say, x \in A but x \notin B and x \in B but x \notin A

Does that imply that x \in (A \int B) ?

[stray reef]

it is not true that A\B = B\A for every pair of sets (A,B)

did you mean "for some sets A, B"?

also intersection is \cap

...and to answer your question, A\B = B\A implies A=B, and hence both A\B and B\A are empty

so technically yes, x in A\B implies x in A \cap B

[weary tiger]

Well I have a proof question That says

Proof (Or disprove by counterexample)

That if A\B = B\A for any Sets A and B, then A \cap B = emptyset

And this is false, but I'm not sure how to find a counter example, because if we take any sets, then A\B = B\A isn't true, but I'm not sure if that is enough to show that the whole statement is false

So I thought I could show that since A\B = B\A, we have that x \in A \cap B, hence it is false that A \cap B = empty set

[pallid lintel]

Huh. You just need a counterexample. Like if A=B=integers

[stray reef]

"A\B = B\A for any Sets A and B"
is that exactly word for word what it says

[pallid lintel]

The question seems poorly worded

[stray reef]

yes, hence my attempt to verify that it's the question itself and not OP butchering it

[weary tiger]

Yes, the exact wording:

Consider the following statement. Determine if it is true or false. If true, explain why. If False, give a counter example proving the statement false.

If A\B = B\A, then A \cap B = {} (For any sets A and B)

So it's very easy to show that the antecedent is false, since we can take any sets, A={1,2} and B={2,3}, clearly A\B does not = B\A, however this doesn't disprove the statement.

[stray reef]

how about A = B = {1}

[cinder sentinel]

Please help

[weary tiger]

Well then A\ B = B \ A = ∅ so A \cap B = ∅

So then it is true for a specific set.
However, the statement is false since it doesn't hold for all sets A,B. -- That's what I would say (We don't need a formal disprove)

I think I can just say the statement is false since it isn't true for any sets A,B right? Our professor did a similar proof by counter example which also included the use of any sets, however since we can use any set, we only need one set to disprove the statement

[cinder sentinel]

Can somebody help me

[weary tiger]

need help

ping me if you have any ideas, thank you

[pale epoch]

there is no question

[gritty crescent]

Hah

[weary tiger]

hahah sorry - I need to list out the elements between braces

[pale epoch]

ok, what have you tried and what is giving you trouble?

[weary tiger]

right so I don't necessarily understand the set builder notation

we have a set such that the set X is an element of the power set {1,2,3} with cardinality less/equal to 1

is that correct?

(for 10)

[pale epoch]

ye

can you list the powerset of {1, 2, 3}?

[weary tiger]

right so the power set of 1 2 3 is {{1},{2},{3},{1,2},{1,3}, {2,3}, {1,2,3}, o}

idk how to latex empty set

sorry

[weary tiger]

so X is a set which is an element of the power set with cardinality <= 1

[pale epoch]

you are missing {2, 3}

but yes

[weary tiger]

fixed it

alright so then we have

X = {{1},{2},{3},o}

this?

[pale epoch]

this isnt an element of the powerset

[weary tiger]

um

Right so

{1} is

{2} is

[pale epoch]

ye

[weary tiger]

{3} is
empty set is too

that's all right?

[pale epoch]

thats all with cardinality less than or equal to 1, yes

so that deals with 10

[pale epoch]

this is an example of X being a subset of the powerset

[weary tiger]

oops

I think we made a mistake

not we

I did

[pale epoch]

ok?

[weary tiger]

{empty set} and empty set should be included right?

since it's <=1

cardinality of the empty set is 0 but the cardinality of a set containing the empty set is 1

wait

[pale epoch]

i thought you mentioned the empty set

but the set containing the empty set is not an element of the powerset

[weary tiger]

oh

yeah

sorry

thank you

do you know how to do 11?

[pale epoch]

yes

[pale epoch]

this is related

[weary tiger]

alright so we have a set such that X is a subset of the power set of {1,2,3}

[pale epoch]

the best is to first list a few subsets of the powerset

to get a feel how they look like

[weary tiger]

right yeah makes sense

okay okay

so we have

the power set of {1,2,3} being {{1},{2},{3},{1,2},{1,3}, {2,3}, {1,2,3}, o}

aaaaaaaaa

im not sure how to proceed

[pale epoch]

well

you already listed a subset

[swift idol]

i am self studying a free course on discrete math. and have recently advanced from well ordering proof to induction (yay). Just curious if well ordering proof is still used in more advanced topics?

[pale epoch]

X = {{1},{2},{3},o}

can you tell the cardinality?

[weary tiger]

yeah, it's 4

[pale epoch]

ok so that doesnt work

but how did you come up with this set

[weary tiger]

because all other elements have a cardinality of 2 or more

like {1,2} or {2,3}

[pale epoch]

hm?

i mean how did you know this is a subset of the powerset

[weary tiger]

oh

well because i knew the power set

[pale epoch]

the way i would think about this is:
start with an empty set {} and then take an arbitrary element of the powerset, say {1} and add it to the empty set to get {{1}}

this is now a subset of the powerset of cardinality?

[weary tiger]

hmm

it has a cardinality of 1

this is the answer

it makes sense I guess?

[swift idol]

2

[pale epoch]

i mean it makes sense to me

i cant tell you if it makes sense to you

[weary tiger]

i feel like im wasting your time so i'll come back to this later, thank you for all the help though, much appreicated

[pale epoch]

not sure what well ordering proof is supposed to mean but i occassionally use the fact that certains sets are well ordered

[pale epoch]

if you were wasting my time, i wouldnt reply

[swift idol]

i have been working on proving simple things on my book like use well ordering to show that sums of positive integer have a certain formula. now there is induction that says you can prove the same thing and they are equivalent in some sense. reading ahead, it seems like everything is proved using induction in the exercises. just wondering of the utility of well ordering proofs

[pale epoch]

it wont be as prominent

but induction appears all the time in mathematics

even though it might not be explicitily

[weary tiger]

thank you, in that case, could I ask you for help with 17?

[pale epoch]

this is one more step of abstraction

if you think of the elements of A as 1, 2, ..., m it might be easier

[swift idol]

wouldn't that be 5 choose 1? and if they asked for <= 2. just 5 choose 1 + 5 choose 2.

[pale epoch]

not quite but close

[weary tiger]

uhh

[pale epoch]

and the case presented here is easier, you can just "list" all the elements

[weary tiger]

hmm

[swift idol]

oops. i was doing an example in my head with the number 5. i meant n

[pale epoch]

ye still, you missed|| the empty set||

[swift idol]

ahh right

[tidal tulip]

can i get a proof check

i want to prove or disprove if n|m then nZ is a subset of mZ. i say this is false: it nZ is a subset of mZ, then every element in nZ is an element if mZ. but consider n=3, m=15. 3|15 and 3 is in 3Z but 3 is not in 15Z since no integer multiple of 15 is equal to 3, therefore this is false

[pale epoch]

this is correct

but are you sure you weren't supposed to show $n \mid m \implies m\bZ \subseteq n\bZ$

[vital dew]

Lochverstärker

[weary tiger]

question

also, I got the aforementioned problem however I'm kind of stuck conceptually

on the power set of $\mbb{R}^2$

[vital dew]

Renegade

[weary tiger]

so there is this excerpt taken from my book

I don't necessarily understand why it's the power set and not just the set itself ...?

[tidal tulip]

i think this is what i need to show. how do i alter my proof

[pale epoch]

you can't because my version is actually correct

[tidal tulip]

is my proof wrong for that version

[pale epoch]

you give a correct counterexample to your version

my version is correct, so that wont work

i.e. your counterexample wont work because 15Z is a subset of 3Z

every multiple of 15 is also a multiple of 3

the proof will just be writing this down more formally and more generally

[tidal tulip]

let me check the book closely

[pale epoch]

R^2 is the just the (empty) plane
you can think of a subset of R^2 as some part of the plane being painted black

[tidal tulip]

ok i think the problem is “if n|m then does nZ subset mZ?” give a brief explanation

[pale epoch]

ok, then this is your version and your counterexample works

[weary tiger]

empty plane?

[tidal tulip]

ok sweet ty

[weary tiger]

isn't it completely full with real numbers?

so completely black

[pale epoch]

sure whatever you want

the point is you can assign a different color to elements of a subset

more precisely a subset of R^2 corresponds to a choice function R^2 -> {0, 1}

that assigns true or false to every point in the plane

and then you can color the true and the false ones differently

and think of them as pictures, text or whatever

[weary tiger]

ah

ohhhhhh

so the power set of R^2 is essentially anything you want

everything apart from 0,1 can be marked as false for example

[pale epoch]

i think the comment is supposed to convey that its really big

[weary tiger]

whereas in R^2, it's not given any arbitrary true/false meaning

it's just... there

[pale epoch]

in fact you cannot even imagine most subsets of R^2 in a sensible way

[weary tiger]

that makes sense

thank you

[coral parcel]

However, each of the example shapes the book suggests can be recovered (up to completely invisible differences) from its intersection with Q², so P(Q²) also has representatives of all the examples as elements. But P(R²) is a much larger set than P(Q²).

[swift idol]

That excerpt from the book sounds very profound and a beautiful thought. So if I were to somehow generate an image of the binary representation of square root of 2 as a black and white image that would not be in P(Q^2) but P(R^2)?

[coral parcel]

As long as you're only generating images of symbols with lines of nonzero width, Q^2 suffices.

In fact, if you can accept a bit of pixellation without losing the meaning (and if you can read this, you can!) Z^2 suffices.

[swift idol]

ah right that makes sense. i can type first 5 digits of pi

[tidal tulip]

professor said prove 4.57 is false but i don’t see how it’s false

[vital dew]

Alter

[tidal tulip]

let X = A U B, where A and B contain distinct elements. Then A U B is a subset of A U B, but A U B is not a subset of A because A U B contains elements in B not in A and A U B is not a subset of B because A U B contains elements in A not in B, therefore this is not generally true

is that a good proof?

@signal rover

[austere cedar]

if you want to prove that a statement is not true, just give one example where its not true. Thats enough

[tidal tulip]

ok. is my proof fine or do i need to give it specific examples

[austere cedar]

I would give specific examples

[tidal tulip]

ok

[hard yew]

Where did you get from that X = A U B?

[tidal tulip]

i’ll give a specific example give me a min

[hard yew]

And in this case it is rather simpler to just give a counterexample to the given implication with concrete sets A, B and X

[ember obsidian]

they plan to set X=AUB in a counterexample

[austere cedar]

One could argue, that you didn't prove that sets A and B exists, where A is not a subset of B and B is not a subset of A. Or something similar

[tidal tulip]

i’m cooking up an example give me a few

[hard yew]

Ah, I see

[tidal tulip]

let A={1,3,5}, B = {2,4,6}
X = A U B = {1,2,3,4,5,6}

then X subset A U B
X is not a subset of A
X is not a subset of B

is this a valid counter example

[austere cedar]

yes