discrete-math

[vital dew]

homer

[ashen bane]

suppose for contradiction it's false

so there is some x in ∅ but not in A

[oak drift]

yea

[ashen bane]

but this is contradiction since ∅ is the set which for all x, x not in ∅

[oak drift]

okok I guess it makes sense

it's just notation thats hard to me

I'll work on that but thx for the explaination

[ashen bane]

yes just spend some time

and good luck

[oak drift]

thx

[ashen bane]

Bumping something from earlier
@vestal bronze @fossil mural
Is there proof to this?
Image
"Recall that since the sampling is without replacement, the unordered sample is uniformly distributed over the set of all combinations of size n chosen from D."

[restive lotus]

can anyone look there and try to answer my question that follows

[ashen bane]

anyone?

[ashen bane]

https://math.stackexchange.com/questions/4349620/linearity-of-expectation-for-calculating-expectation-of-hypergeometric-distribut

i didnt understand the answer there

why E[Xi] = E[Xj] for all i,j

[velvet condor]

hello!

can anyone tell me why the first one is contingency and not tautology?

if we try to expand the implication statement then

(p^q) -> ~p becomes
~(p*q) + ~p

and by de morgan's law
~(pq) becomes p + q right?

so the end statement should be
p + q + ~p which will be true no matter what

[fossil mural]

and by de morgan's law
~(pq) becomes p + q right?
no

[velvet condor]

ohhh

so i assumed it will be
~(pxq) will be ~p x ~q

ohh

got it

i went wrong here

ahhhhh how can i forget that the negation will still stay 🤦‍♂️

im sorry and thank you so much for pointing it out!!

[fossil mural]

also if you think about it, it really just wouldn't make much sense for "if p and q are both true, then p is false" to be a tautology

[velvet condor]

wait tautology means always true right?

[fossil mural]

yes

[velvet condor]

im sorry i cant understand what you meant here

ohhh

wait

i got it

[fossil mural]

well i mean think of any two true statements

[velvet condor]

yes

agreed

yess i forgot that theres an implication in the statement

thank you so much

i should start thinking logically first

Thank you! 🙏

[red forge]

what is the best way to cut n-dimensional cheese? (you want to get the most possible pieces of cheese)

[lean rover]

Is there a bipartite graph where the nodes have the degrees: 3,3,3,3,4,4,6,6,6,6,6,63,3,3,3,4,4,6,6,6,6,6,6?

I drew pictures and came to a conclusion that yes this works but there has gotta be an easier way or pattern I am just not seeing.

I know that the sum of degrees on one side needs to equal the sum of degrees on the other side but I don't exactly know how the nodes are connected here.

[oak drift]

Hello does anyone know if adding the negative before "implies" change the structure ??

¬(p -> q)

same way that ¬(p^q) is (¬p V¬q)

or is it just (¬p -> ¬q)

[lean rover]

¬(p -> q) and (¬p -> ¬q) not the same thing as far as I understand because (¬p -> ¬q) means not p leads to not q. Whilst the ¬(p -> q) is saying that it is not true that p leads to q but it is not saying that negation of p leads to negation of q.

[lean rover]

I think you should like maybe draw truth table

[oak drift]

I just did equivalences and what I got is

it's equal to p ^ ¬q

[fossil mural]

yep

[oak drift]

nice

well thx then

[limpid flax]

We're learning how to prove Big Oh and I want to know if I am doing it correctly. Here is the question:

Here is my solution

[snow cedar]

is this harder to show directly? I feel the main part I had struggled with in the direct strategy is showing that there really is an alternating path / justifying it intuitively

[viral crown]

yeah probably, i think a doable direct proof would give an algorithm that would prove it exhaustively or something, not sure how you'd do it otherwise

when you assume contradiction and you have the x-perfect matching you just gain so much structure that it's much easier

[snow cedar]

Yeah I think I was overlooking some details:

I think I'm still trying to wrap my head around the alternating path argument though.

To me I imagine the vertices of X on the top and the vertices of Y on the bottom. we put a downward arrow on any edge that's not in the matching, and an upwards arrow on any edge in the matching.

I saw somewhere that if you can go from an unmatched vertex in X to an unmatched vertex in Y, you can flip the edges along the path to create a larger matching. Though how do we foresee that when we find an augmenting path for our contradiction proof, that we still maintain the same size?

[viral crown]

saw somewhere that if you can go from an unmatched vertex in X to an unmatched vertex in Y, you can flip the edges along the path to create a larger matching.
true but not too relevant here because we only need them to stay the same (if it increased we would not actually have such a maximum matching to start with)
Though how do we foresee that when we find an augmenting path for our contradiction proof, that we still maintain the same size
well, the edges switch between being in the matching and out of the matching. we know that the path terminates at a y because if it terminated at an x, that would mean the x has no non-matched edges which is impossible (by assumption), or all of it's unmatched edges are to ys that were already hit. it's a neat exercise to show why this last case isn't possible (short for i can't see how to do it off the top of my head but am certain it's easy). if it terminates at a y then that y must be unmatched so when we flip everything we maintain the cardinality of the matching (because our initial x is matched)

[snow cedar]

Oh I see, I was thinking it's more like this:

In the augmenting path alternating from X to Y, # of times to go downwards = # of times to go up + 1.

The starting position of your augmenting path (x) was initially matched to something, so there is an up arrow already.

So the number of up arrows and down arrows you can "see" are equal. When we switch them around, they are still equal?

[viral crown]

hmmm

sure, that seems good too!

So the number of up arrows and down arrows you can "see" are equal. When we switch them around, they are still equal?
in particular this is true and the important part

[snow cedar]

Thanks so much ! 🙂 Do you think in order to prove the existence of an alternating path, we need to show that alternating cycles can't exist? Or is that not necessary in this case?

[viral crown]

it's fine if we have alternating cycles bc we can switch them! remember that bipartite graphs can't contain odd cycles

[snow cedar]

I'm trying this out next. this seems like a stronger statement lol, the inequality sort of looks like halls theorem

When approaching this by contradiction,

If every edge of G extends to an X-perfect matching and there is a subset A where |Neighbourhood(A)| <= |A| , I think if we focus on Hall's condition then it's ok when |N(A)|=|A|, but when its |N(A)| < |A|, it contradicts the condition . Though I'm not sure if this is the right way to think about it

[novel ore]

how can I uniquely determine a surjective function from a function f: N -> N

first thought was take left inverse but that would require that a) f was injective and b) the left inverses are unique

second thought was to construct a function determined by f whose range contains N \ Im f but idk how

there's nothing canonical popping out to me

[broken light]

why are we multiplying tm by 4 here?

[snow cedar]

Actually, I saw a hint somewhere that said "It might be easier to work two jobs if we had an identical twin". I'm wondering how I can relate this to the conditions in the statement. I think the intention of the question is that the size of the neighbourhood for the entire subset A is at least 2|A|.

[analog tinsel]

am I misunderstanding something here?
The subset A could be empty right ? but then the statement is not true ?

[fossil mural]

well there are at least 0 jobs that someone in the empty set is qualified for

if you mean that the converse doesn't hold, then that's not how the logic works, the <= direction says that if that holds for all A then there's a valid matching of people to jobs

[analog tinsel]

wait isnt it "forall subsets A there exists a person p in A such that there exist 2|A| jobs that p is qualified for"?

wait wait

[fossil mural]

i interpreted it as "there exist 2|A| jobs j such that someone in A is qualified for j"

because if you imagine like, two people, one can do jobs 0 and 1, one can do jobs 2 and 3, then clearly there's a valid matching, but the set of both people does not have anyone who can do 4 jobs

[analog tinsel]

yeah

because the statement seemed odd to me

but yeah I guess I misunderstood it

but it is kind formulated in a kind of weird way

idk if its just that Im not a native speaker

Im still confused though lol

[analog tinsel]

what does the "extends to an" mean here ?

https://math.stackexchange.com/questions/3418000/what-does-it-mean-for-an-edge-to-extend-to-a-matching
ah ok found it

[buoyant yoke]

what the hell

isnt the solution a_n = (n+1)2^n?????

cuz the 4a_(n-1) and -4a-(n-1) completely cancel out

how tf did they get that solution

[oblique pelican]

probably a typo

im assuming theres meant to be a $a_{n-2}$ in there

[vital dew]

Dilly

[buoyant yoke]

ohh

how do you solve it if its that then

they didnt show the steps

[waxen knoll]

rewrite to $a_n - 4a_{n-1} + 4a_{n-2} = (n+1)2^n$ then solve normally. Its $a2^n + b2^n$ for homogenous solution then just add the particular solution, this case $n^2 2^n + 1/6 n^3 2^n$

[vital dew]

bDim

[buoyant yoke]

what is the "particular solution"?

how do you solve for it?

[waxen knoll]

Recommend chapter3.5 of Elementary Differential Equations and Boundary Value Problems

[cerulean wind]

V - E + F = 2 holds when you consider the exterior of the graph as a face as well.
see here for validation:

wait what

did they delete their post?

[snow cedar]

yea, i interpreted it the same way as this part: A matching which an edge "extends to" just means a matching which contains that edge as an element.

I tried some sort of contradiction proof for the forward direction but I wasn't sure how to proceed

So assuming every edge of G extends to an X-perfect matching, and there is a subset A, A != 0, A!=X where |N(A)| <= |A|

[snow cedar]

Does the detail that A != X change anything drastically?

[snow cedar]

im having trouble showing the <= direction. I think the assumption lets me apply the halls theorem which says there is an existence of a perfect matching. but how do i show every edge extends to one?

[sand thorn]

Does this work for both directions

for (ii)

[analog tinsel]

I am confused by this. What is given and what do you need to proof, it looks mixed up

to me

[sand thorn]

Basically

For all x,y elements of A, it fulfills x~y if and only if [x] = [y] (the equivalence cases are equal)

and then my proof is to showcase that

[analog tinsel]

I will look more closely into the exercises you posted and let you know in case I find something

theyre interesting

[final cliff]

I think (ii) seems kinda wrong.

[sand thorn]

If we define equivalence cases as [x] = {y eA: x~y}, then by definition, if we assume x~y, then [x] can be defined as {y eA}

and then i do the same thing but for [y]

[final cliff]

When you say ${x\in A : P(x) }$ the x is a variable not a constant.

[vital dew]

DootDooter

[sand thorn]

I'm assuming it for all x

[final cliff]

And ${y\in A}$ is kind of ambiguous.

[vital dew]

DootDooter

[final cliff]

Okay, but in your equivalence class notation [x] and [y] the x and y are particular.

You have specific representatives.

They aren't really variables in the same sense.

[sand thorn]

Oh so it's an x belonging to their particular context

[analog tinsel]

its not clear to me still what youre trying to show

and whats given

[sand thorn]

the above proposition

[final cliff]

Like, you want to show for any x,y in A, that x~y iff [x]=[y].

So you start by saying, take x and y in A. Assume x~y.

[analog tinsel]

ok hang on

[final cliff]

Okay, now take a in [x], how do you know a is in [y] as well?

[analog tinsel]

what does ~ stand for in your course?

[final cliff]

An equivalence relation.

[analog tinsel]

is it equivilance relation

alright

in the courses I attented that was not the canonical symbol

afaik

that was confusing

[sand thorn]

Because we assumed x~y

[analog tinsel]

now I got it

[sand thorn]

they also use capital "r" so R

[final cliff]

Yeah, but this is a, a may not be x or y.

[sand thorn]

xRy

[final cliff]

So what steps tell you a is in [y]?

[sand thorn]

symmetry?

[final cliff]

Not immediately. (If at all depending on how you define [x])

What does $a\in [x]$ mean?

[vital dew]

DootDooter

[sand thorn]

If a is in the equivalence case then x~a?

[final cliff]

Yeah, by definition. So how does that give you a in [y]?

You may or may not need symmetry but there's a particular equiv relation prop you will need to use with your assumptions.

[sand thorn]

transitivity
since we assume: x~y, then we follow these steps

x~a
a~y
x~y

[final cliff]

Yep that'll do it

[sand thorn]

if a~y wasn't the case, then x~y couldn't be while x~a

[final cliff]

Then by definition a is in [y].

[sand thorn]

How would you explain that succinctly because in my head it makes sense

but I can't put it into words

[final cliff]

You don't really need to argue by contra fwiw.

You know x~a, and x~y, by symmetry y~x, x~a so by transitivity, y~a.

[sand thorn]

So I can just put:

By transitivity:
(x~a) - assumed
(a~y) - inferred
(x~y) - assumed

[fossil mural]

just transitivity isn't actually enough for this, you also need symmetry

[final cliff]

It's more like, let a be in [x]. By definition x~a, by our assumption we have y~x using symmetry so by transitivity y~a...

[sand thorn]

oh because a~x so x~a

?

[final cliff]

You can apply symmetry to either x~a or x~y.

[sand thorn]

Ok thank you that's much better

[final cliff]

It kinda depends on how you define [x]. Because you can do it as [x]={y in A : x ~y} or [x]={y in A : y~x}

They are the same sets by symmetry.

[sand thorn]

and then i have to do the converse to prove the other side right

[final cliff]

But if you're being super strict you need to be mindful of it ig.

[sand thorn]

That's true

[final cliff]

So what you showed proves $[x] \subseteq [y]$. You'd probably want to say something about how similar stuff gives you the other inclusion to conclude the equality you need.

[vital dew]

DootDooter

[final cliff]

For the converse you basically just need to unpack definitions as well. If [x]=[y], you know nice facts about a set x is a member of by the earlier parts of the problem.

Or just reflexivity.

[sand thorn]

What's the role of reflexivity here

[final cliff]

x~x right? What set does that tell you x is in?

[sand thorn]

in [x]

[final cliff]

[x] yeah

But [x]=[y]?

This tells you new facts relating x and y

[sand thorn]

x~x
y~x
x~y

?

A mix of reflexivity and transitivity

[final cliff]

So, x~x right? That told you x is in [x]. But [x]=[y]. So x is in [y] now too yeah?

What does the last step tell you about x and y?

[sand thorn]

oh because we already proved this way =>

[final cliff]

Well we're proving the converse. So we'd assume [x]=[y] and need to show x~y.

We already did the other direction yeah

[sand thorn]

So then if x is in [y] then y~x and then by symmetry x~y

[final cliff]

Yep.

To recap for the converse we assume [x]=[y], we know x~x, so x is in [x] and we follow this reasoning until x~y basically.

[sand thorn]

Ok I think I got it, thank you very much

[novel ore]

if a set X is uncountable we can still write $X = \bigcup_{x \in X} {x}$ right

[vital dew]

okeyokay

[fossil mural]

yes

[novel ore]

so in showing that there is no set containing all singletons could we assume there was, then show that the power set contains all sets using this

[fossil mural]

...the power set would not contain every set

it would contain every set which all of its elements are singletons

[novel ore]

oh wait u right

[fossil mural]

its union would contain every set

or use replacement to send every singleton to the set it's the singleton of

or regularity because this set would be ill-founded

or directly a russell's-paradox-style argument, constructing the set of all singletons that aren't elements of the sets they contain

[novel ore]

so something like if S is a set containing every singleton and x is a set then {x} is in S, and x is in {x} which is in S, so x is in the union over S

[fossil mural]

yep

[novel ore]

nice

[weary tiger]

What is the opposite of (non-) discrete math?

continous math?

What is the difference?

[fossil mural]

well "discrete maths" is a... honestly fairly vague term for anything discrete

[weary tiger]

it is not concrete? haha

[fossil mural]

the obvious thing that isn't discrete is the real numbers

[weary tiger]

complex number?

i

equals square of -1

[fossil mural]

no it isn't

(-1)^2 is 1

[weary tiger]

René Descartes called it "imaginary"

[fossil mural]

idk what you mean by "concrete"

[odd heart]

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

There's also discreet math, which you do on the quiet.

[buoyant yoke]

whats the answer to this?

I got n*(n-1)*2^(n-2)

but chatgpt says n*(n-1)*2^(n-1)

[cunning egret]

I want to find the general coefficient of x^k in (x+1)(x^2+1)...(x^n+1)
I just a want a push in the right direction cause I think we can define some sort of a recursive sequence to do that
my approach is basically splitting the power into 1s and then finding how many groupings of 1s will give an acceptable coefficient
so for example for x^6
(1+1+1+1+1+1)=6 -> 1
(1)+(1+1+1+1+1)=6 -> 1
(1+1)+(1+1+1+1)=6 (2 ways to do this, either by constructing x^4 from x^3 and x, or simply multiplying x^4 into x^2) -> 2
(1+1+1)+(1+1+1)=6 (not possible cause this would require two x^3) -> 0
then adding these up to get 1+1+2=4, hence the coefficient of x^6 would be 4

[solar marsh]

n(n-1)2^(n-2)

[misty iris]

We roll two fair 6-sided dice. Each one of the 36 possible outcomes is assumed to be
equally likely.
Given that the roll results in a sum of 4 or less, find the conditional probability
that doubles are rolled.

why is 1/18 a wrong answer?

nvm i got it

[snow cedar]

I am trying to do this question by transforming it into a graph problem. The question implies the checkerboard is a two-colourable graph, so is the subset S. So it is bipartite. But I'm not sure what to do knowing this

[storm linden]

this isnt bipartite right?

[snow cedar]

its 2 colorable so i would say it is

[storm linden]

how? I tried the two coloring and it looked like an odd length cycle?

[inland zenith]

if I'm not mistaken you can just partition the graph into the middle three vertices and the other three remaining ones

[storm linden]

ohh i made a mistake, mb, thansk for help!

[snow cedar]

yeah like this

[storm linden]

sensational, thats my final answer too

https://tenor.com/view/sensational-gif-4975652

[deep vector]

how can i proof that the sum of the distances in a graph of order n is maximum on a path? I know that this is minimum on a complete graph

[short jay]

is graph thery on-topic here?

[deep vector]

yes

[short jay]

thanks!

i have a dynamic programming problem that i'm trying to solve: given a tree on $n$ nodes, determine whether it contains a maximal independent set (i.e. a vertex set with no two vertices sharing an edge) of size exactly $k$

i think i want to have a DP array of size $n \times k$ but i'm struggling a bit to see the right recurrence relation

[vital dew]

PatrickC

[brisk cipher]

Is there a closed formula (or anything at all) for the number of ways to seat k pairs of people on n chairs, where no pair is allowed sit next to each other?

[snow cedar]

I'm trying to reach the hint so I can prove this, can someone let me know if this is the right way to do it?

Assume there is an $X$-perfect matching and assume for contradiction that for every $x \in X$ there is an edge incident with $x$ that does not extend to an $X$-perfect matching. \\
So if we make a subgraph without these edges, it should still have an $X$-perfect matching. Also, in the original graph, for every subset $A$ of $X$ we had that $|A| \leq N(A)$. So in subgraph we need $|A| = |N(A)|$, because if $|A| > |N(A)|$ there can't be an $X$-perfect matching by Hall's Theorem which is a contradiction.

[vital dew]

clementine

[cerulean plover]

why here does it say "S is not equal to the null set". If S is an element of the positive integers, isn't it by default not the null set, or any set for that matter? is it supposed to say "S is a subset of positive integers"?

[fossil mural]

yeah i think that's supposed to say $S \subseteq \mathbb{Z}^+$

[vital dew]

bee [it/its]

[cerulean plover]

kk alright

oh yeah S is bounded below

can't bound a number

[fossil mural]

claiming that an integer is bounded below also doesn't make much sense yeah

and also S is more the kind of variable name you use for a set than for a number

[cerulean plover]

there are multiple ways, no? for example, if the cardinality of the range is equal to the cardinality of the codomain, then the function is onto

[fossil mural]

no that's not true

[cerulean plover]

it's not?

[fossil mural]

it's true if the codomain is finite

[cerulean plover]

mb yes this is what i meant

[fossil mural]

just reading straight from the definitions:
to prove f is injective, assume f(x) = f(y), and prove x = y
to prove f is surjective, take any y and find an x such that f(x) = y

[cerulean plover]

your textbook probably

for my textbook, there's a glossary at the end of each chapter

so go to ur sets chapter and read the glossary, go the functions chapter and read the glossary

[vocal roost]

Could someone help me

This is prob very basic

But I’m having trouble with the concept of trees

[fossil mural]

,rccw

[novel ore]

how does this establish that R is not transitive?

i mean I already came up with a counterexample, but i'm trying to see how this would suffice

[fossil mural]

yeah that doesn't particularly look like a counterexample by itself, is there more on the next page or something?

[novel ore]

no there isn't lol

it's alright

i just took mmod 2

mod 2

and constanat function 0 and constant function 1

[fossil mural]

to show that a relation isn't transitive you'd want to give three objects a,b,c satisfying aRb, bRc, and ¬aRc

[fossil mural]

so yeah basically you'd want something that's 0 infinitely many times and 1 infinitely many times as the "in-between" function, the b in this

[novel ore]

can somebody explain what they mean by this highlighted sentence please

is it just saying that A has cardinality equal to the product of w with itself countably many times

which has same cardinality as w

[clever kite]

Am I going crazy? I feel like multiplying by a^{p-1} is useless since it's congruent on both sides either way. I only did it to satisfy the question

[wide vine]

What are you confused about

x= x*a^(p-1) = b*a^(-1) * 1 = b * a^(-1)*a^(p-1) = b*a^(p-2)

[wide vine]

The whole point of it was to just to express x in another equivalent form (it seems)

[clever kite]

Ah ok sounds good

I was just getting tripped up because a^{-1}b mod p is congruent to a^{p-2}b mod p by fermat's, but you're right they probably just wanted us to express it another way and use fermat's

[fossil mural]

honestly that looks like some lines that were supposed to be there have been removed

like that's just two sentence fragments and they don't actually fit together into a sentence, and given the conspicuous line break i think someone messed up while editing this text and some lines vanished

[wide vine]

Would anyone be able to explain to be how this argument established equality of the single sum and double sum. I am at the point where I understand how they are computing how many f(k) terms show appear in the double sum but I just don't understand how we are getting equality such that we can recast it as a weighted single sum

[wide vine]

The bracket is the floor function

[wide vine]

I guess the real confusion is the last paragraph. Like okay I get for a fixed k, f(k) appears in the sums [N/k] times but I don't understand how we are not missing any terms (under counting) or over counting in some fashion

[austere lark]

hello guys I have this problem I approached the problem like this:

[tacit portal]

Could anyone help me discover an invariant for this problem? I have found a monoinvarient (posted it in the help page) but it didnt help me much. The problem: There is an integer in each square of an 8 × 8 board. In one move, we may choose any 4 × 4 or 3 × 3 square and add 1 to each integer in the chosen square. Can we always get a board with each entry being even?

[haughty garden]

the idea is that you want to somehow control what adding 1 to every square of a 3x3 and 4x4 subboard looks like

if you consider a 3x3 subboard, adding 1 to every integer changes the parity so that's not quite helpful for us; instead, let's consider restricting one of its rows

(i.e. if we consider any 3x3 subboard and add 1 to every integer except for 1 row, then this does not change the parity of the sum of the elements of the board barring a select number of rows)

you can do a similar analysis for any 4x4 subboard

[split oasis]

Suppose you repeatedly flip a fair coin until three consecutive flips match the pat-
tern HHT or the pattern TTH occurs. What is the probability you will see HHT
first? Define a suitable probability space that models the coin flipping and use it to
explain your answer.

can someone help me with this

i dont understand how the answer is 2/3

it should be 1/8 im so lost

[shut ivy]

How can I show that $2^k+2k+1 < 2^{k+1}$ for $k > 4$

[vital dew]

rabbits_advocate

[split oasis]

by graphing

[shut ivy]

it is for an induction proof

i have reached this final inequality that i need to prove by manipulating the expression

[wide vine]

See what you can do with knowing 2^(k+1)=2*2^(k)=2^(k)+2^(k)

So a necessary condition might be now showing 2k+1<2^k for k>4

So maybe try showing 2k+1<2k+k=3k<k^2<2^k for k>=5

[cursive nymph]

how a set where every non-empty subset has a minimal (not the least) element called in English?

[grand totem]

It would make more sense to ask what a relation that obeys the condition would be called and the the answer would be that such a relation is called well-founded

[cursive nymph]

thanks!

It would make more sense to ask what a relation that obeys the condition would be called
well, I mean, I'm just used to saying (R, A) is, for example, a well ordered set

[quick tinsel]

If S is a function such that-
S = {(x, y) | x belongs to [a, b] and y belongs to [p, q]}

where a, b, p, q are real numbers
||it is given that S is a subjective-function||

is it possible to have another subjective function R such that-

R = {(x,y) | x belongs to [a, 2b], y belongs to [p, q]}
(i am not an undergrad in math btw apologies if this question is irrelevant to the channel)

[odd heart]

Yeah, I don't think there's a term exactly like that, you need to talk of a "set with a well-founded order" or something along those lines.

[cursive nymph]

god, I now have SE-anxiety

for that there I'd get 12 down votes in 3m xD

thanks!

[shadow lion]

I've been thinking about this for a while, but I still have no idea where to start :c

does anybody have a hint they'd be willing to give me?

terminology wise, d_x is the degree of x, and a cut vertex is one such that removing it from G disconnects G

[bronze shuttle]

Wtf is a cut vertex

[shadow lion]

I said it already

[solar marsh]

G-x its disconnected

[bronze shuttle]

Oh

Oops

[bronze shuttle]

Assume contradiction

[ivory badge]

Well, do you see why it holds at n = 4 :3c

Does induction work

[shadow lion]

my line of thinking was more like somehow applying Menger's thm

I was thinking about considering any x with d_x >= 3, and letting a, b, c be 3 of its neighbours

then... hold on

nvm idk what I'm doing

[ivory badge]

which one was Menger’s

[shadow lion]

vertex Menger's

uhh

[wide vine]

Disregard.... I figured it out

[shadow lion]

size of smallest vertex cut for x and y = max # of pairwise vertex disjoint paths from x to y

[ivory badge]

I was thinking something like

[haughty garden]

G being a graph with no even cycles would mean that every cycle is odd, perhaps that might be useful for you

[ivory badge]

see it’s true for n, then at n+1 go through and remove any single non-cutting vertex

Then doing some gluing arguments

But idk if that actually works like I’d want it to

[shadow lion]

uwah

[ivory badge]

(Since obviously G sans v also has no even cycles)

[shadow lion]

I shall think about your idea some more then

why is graph theory is so hard for me

[haughty garden]

graph theory is kinda funky

it's kind of like combinatorics

the result might be intuitive but formally arguing it is pain

[shadow lion]

yeah see, I'm really terrible at combinatorics

so maybe that's why

[haughty garden]

i am too

[shadow lion]

[haughty garden]

but i really like it

even if i suck at it

[odd heart]

I'm thinking something along the lines of consider three neighbors A,B,C of x, if x isn't a cut vertex, then each two of these points has a path connecting them that doesn't pass through x, and that path has odd length.

Now combine those paths to get an even cycle somehow, getting a contradiction.

[haughty garden]

yea that's my idea as well

you basically want to force the vertex to somehow arrive at an even cycle

if G - x were to be connected

[shadow lion]

so I was onto smth with the neighbours

agh, let me try this again

[haughty garden]

specifically, since G - x is connected, then there exist a path P_{u, v} that connects the neighbours u, v of x; then in the graph G, you can obtain a cycle by going x -> u ~> v -> x

[solar marsh]

prove that if a vertex not discconect the graph, there are an even cycle

[haughty garden]

that tells you something about the path from u to v (since G has no even cycle)

consider a third neighbour z and by the same reasoning above, you can deduce something about the length of the path P_{u, z}

[shadow lion]

okay, allow me to try

thank you for the pointers!

[haughty garden]

🫡

tis sleepy time for me (but watch me be awake for the next hour)

[ashen bane]

An urn contains N balls enumerated from 1 to N. Let X be the largest number drawn in n drawings,
when random sampling with replacement is used.
(a) Find E(X) as a function of N and n.
(b) Approximate E(X) for large N and constant n.
(c) Approximate E(X) for large n and constant N.

i need help with this question

[shadow lion]

idk if you're still awake, but I solved the problem!

thank you so much!

[snow cedar]

This question said to use "Menger's" as a hint but I didn't do anything of that sort. My understanding was that its not necessary (Also Im not sure how to make use of it).

What I did is contradiction saying that suppose VertexConnectivity > EdgeConnectivity
If edge connectivity = x, then this implies there are x edges I need to remove to disconnect my graph.

Let E be these edges. If I remove a vertex at the endpoint of each edge in E, those edges will be removed too. So if I delete |E| = x of these vertices, this will disconnect the graph.

So this contradicts VertexConnectivity > EdgeConnectivity. Is my approach valid?

[inland zenith]

if you delete a vertex you may delete multiple edges, your argument seems to assume you only delete vertices of degree 1

[snow cedar]

Ah yeah its not strongly worded I realize. Maybe i can talk about induced subgraph without these vertices

Would mengers be better instead? I just couldn't recognize how I'd apply it.

[inland zenith]

let's see, which menger's theorem?

what have you studied?

[snow cedar]

So I know that there are two variants of Menger, Edge menger and Vertex menger theorem.

WLOG,
Vertex Menger says the minimum size of an s,t vertex separator = the largest # of **vertex **disjoint paths from s to t.
And a corollary of it is that G is k-connected iff for every 2 distinct vertices s and t, there are at least k **vertex **disjoint paths from s to t.

[inland zenith]

Yeah

[snow cedar]

Also Vertex seperator is a set S where G - S either disconnects the graph or reduces it to a single vertex

[inland zenith]

yeah

if you have these paths, you know you must remove at most one edge from each path to make the graph disconnected, and you definitely don't need to delete more vertices than that to achieve the same thing

right?

[snow cedar]

I think this is because you need to remove the "middle" of each path to prevent yourself from going from S to T. When you delete a vertex in the middle of a path (it is an endpoint of an edge), it will delete edges that it is connceted to

[inland zenith]

yeah you will delete many more edges but that's ok

at least that's how I understood the question

[snow cedar]

yes that is possible from what i can see too

but whats stopping us from talking about an induced subgraph without the vertices? I thought that would also work if we do a proof by contradiction

[inland zenith]

what's the contradiction?

[snow cedar]

That VertexConnectivity > EdgeConnectivity, but we show we can find an even smaller vertex connectivity

[inland zenith]

hmm, how do you know that you need to delete fewer or the same # of vertices?

[snow cedar]

i can have a strategy: look at each edge, mark an arbitrary endpoint for deletion if none of its endpoints have been marked yet.
Otherwise if an endpoint is marked to be deleted, do nothing and process the rest of the edges.

On each edge we are marking at most 1 vertex for deletion

so |marked| <= |E|?

[inland zenith]

Yes sounds like that would work too

[novel ore]

can I have a hint for b)? IMO it seems canonical to associate each function from X/Y to {0, 1} with its domain to get a function into f^{-1}(the empty set), but this function definitely isn't injective

just because two functions have the same domain does not of course imply that they're equal

oh nvm maybe i can assign each function to their preimage of 0

[novel ore]

oh i'm being pretentious and using it as an adjective

here canonical means natural choice

the first thing that comes to mind

[novel ore]

yes

[cursive nymph]

how, exactly does it imply it?
clearly applying only axiom of regularity doesn't help, since we can have A in A[*] and ø in A, and so ø is that element which was guaranteed to be disjoint from A

but where do I apply the pairing tho?

[*] (aiming for contradiction ofc)

[viral crown]

let S be a set, then {S} is a set by pairing. then regularity finishes it

[cursive nymph]

what exactly does it finish?

S = empty set
{S} is a perfectly valid set

i mean, let me elaborate

[cursive nymph]

here we just assume S is a set, right?
nothing more?

[viral crown]

regularity says "every non-empty set contains an element disjoint from itself"

sps S is a set. then {S} is a nonempty set. thus S \cap {S} = empty set by regularity...

[cursive nymph]

I mean, I still don't see what's wrong with that intersection

if S were an empty set, then of course

emptyset intersect {empty set} is an empty set

we only require {S} to be non-empty
not S itslef

[viral crown]

we can just take them as separate cases if you want, clearly emptyset is not an element of emptyset, then for any nonempty set we are done by the above argument

i guess im kind of confused by ur objection

if S and {S} do not contain any of the same elements then you cannot have S \in S

[cursive nymph]

it's 4:35am where I'm from rn xD

so I might be trippin

I will then come back to it after some sleep

[cursive nymph]

yeah

but that's what you wrote in the first place

idk how you meant to connect A in A and a statement about {A} ({S} in ur nonation)

thanks anyway tho!

hope it will be more clear to be after proper sleep

[viral crown]

hopefullyyy idk it's possible i'm not reading your objection well enough

goodnight!

[deep vector]

Hello, could someone recommend interesting graph theory exercises where König's theorem or Hall's theorem are needed?

[snow cedar]

I think the idea is to remove a perfect matching from a k-regular bipartite graph and apply the same argument to it, but how do i justify that the k-regular graph initially has a perfect matching?

I'm trying to say |A| <= |N(A)|. I made a mistake saying that since its k-regular that |A|k = |N(A)| so it follows |A| <= |N(A)| but this sounds flawed after a second look. any advice?

[haughty garden]

the graph is bipartite, so let the partite be (X, Y) and consider any subset A of X. We will denote the set of edges incident to A by E(A) and the set of edges incident to N(A) by E(N(A)).

(1) Every edge incident to a vertex in A is incident to a vertex in N(A), so E(A) \subseteq E(N(A)).
(2) The graph is k-regular, so |E(A)| = k|A| and |E(N(A))| = k|N(A)|

(1) + (2) together imply Hall's condition

it might be worth mentioning that because the graph is bipartite, edges go from X to Y so A \cap N(A) is empty, which is why the reasoning here works

[hidden totem]

do hypergeometric functions always have compact support?

my instinct wants to say yes, because if the index goes negative, eventually one of the factors becomes 0, and then that kills anything beyond that point

but i dont see how that can necessarily always work on the other side as well, and there is an issue if the summation has a term like (2n+1)!

[snow cedar]

Ohh wait, I think I confused X-perfect and perfect matching. What we showed is X-perfect matching right? Perfect matching to me means that everyone in X and everyone in Y is matched to someone which I think I didn't justify.

I want to claim that if i remove edges that belong to the perfect matching, then the graph becomes (k-1)-regular,

[haughty garden]

yes you have the right idea

what we have rn is that the graph has an X-perfect matching

you now want to extend that to a perfect matching

i.e. what you want to try and prove is that |X| = |Y|

[snow cedar]

I see, I think I'm supposed to use the fact that the number of edges from X to Y is k|X| and number of edges from Y to X is k|Y| somehow since the question talks about k-regularity

[haughty garden]

👍

excellent

so each X-perfect matching is a perfect matching

[snow cedar]

Not sure how to formally talk about it though, like because its bipartite each edge is counted "once"? Because I'm trying to go to k|X| = k|Y|

[haughty garden]

well

the graph is bipartite

so edges can only go from X to Y and vice versa

so every X -> Y edge is also an Y -> X edge

and neither overcount or undercount the number of edges

so you have that k|X| = k|Y| which implies that |X| = |Y|

it's just a corollary of the property that G is k-regular and bipartite

[snow cedar]

Got it

Thanks so much! 😄

[haughty garden]

👍

[wind creek]

Giveaway Letter:
|| D ||

@lusty loom @bronze shuttle @final turret @copper oar

no winners

[young sun]

is there by chance kinda like a path that i can follow or checklist to see which formula for combanatorics i can use

like a flowchart

[cursive nymph]

I mean, it does not directly answer ur question, but still might be helpful

usually, this 'feeling' is just developed by solving problems

bc a flowchart will most likely fail when u need to apply say two techniques

otherwisd the flowchart would have to be enormously big and unreadable to contain anything other than the trivial cases

[hidden totem]

the twelvefold way is what frownyfrog just posted, but it is only a chart for a certain class of combinatorial formulas, namely the number of ways to count the subsets of a set given a combination of additional special properties

however, in general this is not possible. if such a complete flowchart existed, we could probably solve all combinatorics problems (depending on definitions)

but there is a way to meet you halfway there

1. consider the act of counting as a constructive method, where its base "pieces" are, say, the twelvefold way or whatever else you already know is verified to be correct

for example, suppose I want to find the number of permutations of A,B,C. i know that it is 3! = 3x2x1. but what do the numbers 3,2,1 represent and why do we multiply?

the 3 represents the number of choices in the set {1,2,3}, the 2 represents the number of choices in {1,2}, and 1 the choices in {1}

multiplication means we must make one choice in each of the three sets. for instance,
{1,2,3} -> 2
{1,2} -> 1
{1} -> 1
now we have a set of rules that maps (2,1,1) to our permutation. take the 2nd letter B, then the 1st of the remaining letters A, and the 1st of the remaining letters C. (2,1,1) gives BAC

we know this structure is counted correctly because we "built" the list of permutations correctly

2. we can verify any part of the counting problem by either forming a bijection or checking for both overcounting and undercounting

more details: https://m.youtube.com/watch?v=uxjAHkn4VFI

a bijection is the most direct way to verify the count is correct, but if you have a larger problem split into cases, youre going to need to think in terms of the coverage of the cases, like overcounting and undercounting, maybe utilizing inclusion-exclusion as needed

if you can count the pieces, then use the pieces to build the larger picture, that is as close as you can get to a flowchart that tells you which formula is correct

for more "atomic" formulas youre probably using step 2, for more complex formulas or for applying the formulas to problems youll likely use step 1

[hidden totem]

dont hesitate to ping or dm me if any of that was confusing or unclear

[cursive nymph]

i'm back after some sleep xD

tried as follows, but it proved nothing
any directions?

[cursive nymph]

if we never define what a set is, then what does the vanilla equality sign, from the first-order logic, check?

yes, it's «extended» by the extensionality axiom, but assume for a moment we didn't have that axiom

how do we even transform the human notation A={ø, {ø}} into pure first-order logic?

[cursive nymph]

problem resolved

• assume A is a valid ZF set
• then S:={A, A}={A} is also a valid set
• by extensionality it must have at least one element, call it m in S, disjoint from S
• So, it should be that m=A int S={A} = ø
• IF we had A in A, then we must not have it in {A}, i.e. A != A. Contradiction

[ashen bane]

The expected number of dancers falling on stage dur-
ing a contest is .3. What is the probability that during the
next contest, (a) no dancer falls on stage and (b) 3 or more
dancers fall on stage? Explain your reasoning.

why is it possion?

[hidden totem]

it's poisson because, assuming all dancers are the same, as is typically assumed in these kinds of idealized math problems, each dancer has an equal probability of falling at any time, distributed randomly across a continuous span of time

what makes it poisson is that, there is a small chance that a dancer could in theory fall and then get up and then immediately fall again

theoretically there is no limit to the number of times a dancer could fall

this is the kind of distribution that a poisson distribution is modeling

[minor wyvern]

Hey, is anyone familiar with error correcting codes? I'm working on a practice problem about correcting n-bit strings in k places using randomization while communicating as least of information as possible, but I'm getting a bit stuck.

[buoyant yoke]

how do I do this 😭

[earnest cave]

this would be false right?

[glossy canyon]

i'm planning to self-study discrete math, does anyone know a website with good notes?

[bronze shuttle]

i think its false ye

[cursive nymph]

what is meant by a discrete math course varies enormously from one institution to another, more so than for most other courses

see what's on ur curriculum, and find textbooks/notes for those things separatly

for example, my discrete math course includes ZFC, combinatorics and automatas
all of those are independent and one could spend an entire life studying each part

here are thee textbooks for set theory I like (author on the right)
and there is an amazing playlist on YT that gives some nice overview and context for the zfc axioms

[buoyant yoke]

can someone walk me through this please

[glossy canyon]

thank u!!

[buoyant yoke]

anyone? 😭

[quaint dagger]

anyone really keen on group theory

tryna prove this isomorphism without using a function which all the answers use

(R,+) and (R+, x)

the answers just use e^x

which yeah like works

but it feels dirty to use lol

wait nvm there is a group theory one

[solar marsh]

Can Menger's theorem be proven using Hall's theorem?

[haughty garden]

there are a few equivalent definitions for the nth catalan number, how is it defined for you?

[haughty garden]

yes; i believe you can do hall's theorem => maxflow-mincut theorem => menger's theorem

[next sail]

any suggestions on how to approach c without manually findning it?

[cursive nymph]

I mean, it halves each time
for 64 it will be 6 steps
for 1024 ten

not that many ig

[next sail]

okay thanks

would u by any chance know how to approach this problem?

[haughty garden]

A way to think about this function is that you’re really just adding 1 everytime you recurse. So now you want to think about how many times you’re recursing in terms of k

[hidden totem]

what part are you struggling with? because i think if you knew all the definitions then this problem is very straightforward

[rustic helm]

can anyone tell me if this is correct pleaseee

[cursive nymph]

/offtopic/

u know what, I'm making my lecture notes dark. thank you for inspo!

[rustic helm]

thats chatgpt but sure

[cursive nymph]

lol

[wide steppe]

Send help

[solar marsh]

Ah yes, of course, I know that path. I am looking for a direct proof of Menger's theorem using Hall's theorem.

[inland raft]

simply recall what it means for a relation to be a function

then notice x = y for x, y >= 0 implies x * x = y * x = y * y.

[cursive nymph]

check if this holds

formally, if (x, y) in f and (x, z) in f, show that it implies y=z

[manic coral]

The discrete mathematics book that I'm reading is saying that Floyd-Warshall Alogrithm has time complexity O(n^2), but clearly these are three nested for loops, with one comparison in each iteration, so it must be O(n^3), am I missing something?

Also, this algorithm is categorised as shortest path algorithm, but it only gives the value of the shortest path, not the path itself. However, we can keep track of each k in the step 2, thus obtaining the shortest path, right? Am I correct?

[haughty garden]

you are correct in that Floyd-Warshall is O(n^3)

FW is the canonical algorithm for APSP so it gives you the length of the shortest path from any pair of vertices; there are natural extensions to FW that gives you the explicit shortest path

just like how Dijkstra and BFS only gives you the length of the shortest paths for weighted and unweighted graphs from a single source, but it can be extended to give you the actual path

[autumn ore]

{(a,b) | a and b share a common parent}
Could someone explain me one thing. Is it reflexive or not? According to ChatGPT it is not reflexive, but I'm think it is

[little prism]

thats more of a language question than a math question

can you share something with yourself?

[autumn ore]

Yeah, it is strange, but if a and a are the same age then it is reflexive. That is we share the same age, don't we?

I got it. If it is like {(a, b) | a and b have the same parent} then it is reflexive

Am I right?

[ocean socket]

reflexive would be that (a,a) so the set is reflexive if an only if every person shares a parent with themselves. which personally i would say sure

[autumn ore]

So you think that you can share a parent with yourself ?

[ocean socket]

sure. but thats kind of a language game. without a pure definition of what it means to share a parent i cant tell you with 100% certainty what the asker of the question would want.

but my intuitive sense tells me yes.

[autumn ore]

I’m agree with you, but it turns out that there is a difference between “the same” and “a common”

Sorry, my bad

[weary tiger]

it says 2 of them are correct

im unsure which

[cerulean radish]

Let's go through each option

What do you think about i, is there a set that has no subsets?

[stiff plinth]

Is it correct if I set t(n)=t(n-1)+t(n-2)+n for t>=3 for part a?

[cerulean radish]

Yeah

[stiff plinth]

But it’s weird cuz the root of characteristic equation will be 1.62 and -0.62

Kinda messy compared to calculation steps of other examples

[cerulean plover]

is this how you write "The function f(x), which maps integers greater than 10 to a positive integer, is equal to x - 10"?

[cerulean radish]

When specifying the domain and codomain, you should write only the name of the function

The domain and codomain and the rule of assignment should be stated separately also

\begin{align*}
f: { &x \in \bZ \mid x > 10 } \to \bZ^+ \
f(x) = &x-10
\end{align*}

[cerulean plover]

so would it be something like
$f: {x \in \mathbb{Z} | x > 0 }

oh u got it first

cool

[cerulean radish]

The second line can be rewritten as f: x |-> x-10 as well

[vital dew]

A Loner Bean

[brave rock]

People would usually write $f \colon A \to B; x \mapsto x-10$.

[vital dew]

$\mathbf{Boytjie}$

[brave rock]

Usually aligned beneath each other :)

[snow cedar]

interesting problem

[cloud crystal]

no way you're here too

hows it been man

[cerulean plover]

meh

alright

[cerulean plover]

i'm confused as to what this question is asking, could someone clarify?

is it asking about how many possible mappings there are?

nvm i got it

[cerulean plover]

"assign 0 to 1 and n" does this mean f(n) = 0 and f(1) = 0, or that f(0) = 1 and f(0) = n?

[oblique pelican]

whats the question?

[cerulean plover]

oh

duh 0 isn't in the domain

mb 😭

[oblique pelican]

yeah so its the first thing you said

[cerulean plover]

well while we're here, i'm confused on part a

[oblique pelican]

also you cant have a function that maps the same value to different values

[cerulean plover]

if n = 1, then it wouldn't mapping to different values

that was my thinking ig

[cerulean plover]

one-to-one means that the cardinality of the domain must be less than or equal to the cardinality of the codomain, right?

[oblique pelican]

yeah there are no one-to-one functions here

[cerulean plover]

so if n is any value greater than 2, there's no one-to-one

[cerulean plover]

but what if n = 2?

[oblique pelican]

oh yeah

[cerulean plover]

it says "n is a positive integer"

[oblique pelican]

if n=1 or n=2 then yes

[cerulean plover]

so, for all possible values of n, i'd suppose there would be 6 different mappings

2^1 + 2^2

[oblique pelican]

theres only 2 possible 1-1 functions when n=2

[cerulean plover]

u right

[oblique pelican]

1-1 means that each element in the domain maps to a different value

[cerulean plover]

yeah

so that's 4

[oblique pelican]

ye

well you should specify

n=1 theres 2, n=2 theres 2

n>2 theres 0

[cerulean plover]

well i guess "2" isn't really a

a proposition

[oblique pelican]

yeah

I would just word it out

[cerulean plover]

okay for part c i'm intuiting n - 1 but

idk how i'd prove it mathematicallty

i'm proving it to myself by saying that we can imagine the mappings as a bitstring, where a 0 at position i means that the function maps i to 0, and 1 at position i means that the function maps i to 0. the nth position must be a 0, and from there, only 1 of the (n-1) positions may be a 1. so it's how many (n-1) digit bitstrings can be created with only one usage of the number 1

which is equal to (n-1)

oh, it's 2(n-1), because the nth position can either map to 1 or to 0

but idk the actual mathematical process of arriving there

[mental plaza]

what is this asking me to input? am i supposed to calculate the sum using the n(n+1)/ 2 ?

[cerulean radish]

Yes

[full loom]

anyone know a tool that you can plug set builder notation into and get the set?

I've tried looking at wolfram

but it doesn't understand me (or i dont know how to use it properly)

and the ones i found online are a bit too simple

for instance i want to be able to get a few values for this set

${( nx+1,y^2+1) \colon x,y \epsilon N, (n \epsilon Z, n >= 0) } $

[vital dew]

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

[neat cove]

hello dear peers and elders. I would like to know the best resources for discrete maths on youtube.

Ahem* Ahem*

AHEM* AHEM* AHEM* (agressively)

[oblique pelican]

https://youtube.com/playlist?list=PLHXZ9OQGMqxersk8fUxiUMSIx0DBqsKZS&si=8bQnGF-alnXCtyIl I haven't watched this full course but I've seen some of his vids and I think it could be good

[mental plaza]

i cant wrap my mind around this, so i understand up to the step where 2^k+1 < (k+2)! ( k+3). how is (k+2)! x 2 = (k+2)! ( k+3)

[cerulean radish]

It doesn't state that (k+2)! * 2 = (k+2)! * (k+3) either

k > 1 is assumed, so 2 < k+3 and (k+2)! * 2 < (k+2)! * (k+3)

By transitivity, 2^{k+1} < (k+2)!*2 would imply 2^{k+1} < (k+2)!(k+3)

[manic coral]

I want to prove that a tree with n vertices has n - 1 edges. I prove by induction. For n = 1 it's clear, such tree has no edges. Now assume that a tree with n - 1 vertices has n - 2 edges. If we add a vertex to such tree so that it remains a tree, it can only be a leaf node or and extension of a leaf node. So it will add 1 more edge to the graph thus increasing total number of edges to n - 1. Proof is complete (?)

Can someone verify it?

[cerulean radish]

Technically it's fine as long as you know that every tree can be constructed by repeatedly adding vertices to the tree of 1 vertex. If you think it requires a separate proof and don't really feel like proving that, you need to change how the induction step is formulated. For example, say G is a tree with n vertices, there must exist a leaf v (I am assuming this has been shown) and G\{v} must be a tree. The rest should be obvious

[lethal linden]

What's your definition of tree?

There are several characterizations and it's a common exercise to prove they're equivalent.

In fact, for a finite graph, being connected and having |E| = |V| - 1 is equivalent to any of the other characterizations.

[manic coral]

A connected graph that has no circuits

[lethal linden]

For induction, you want to start with a tree on n+1 vertices and remove a leaf to get a tree with n vertices and use the inductive hypothesis on that.

Can you assume every tree has at least 1 leaf node, or is that something you have to prove?

(In this context, a "leaf" is any vertex v with deg(v) = 1.)

[glossy roost]

Hi, can anyone please explain why this proof is incorrect? The solutions manual says the proof is incorrect because it assumes what we’re trying to prove and works its way to a well known fact. I’m not sure I fully understand how that makes the proof incorrect. I’ll appreciate any additional help with this. Thanks.

[cerulean radish]

They start with the given statement, call it P(x, y), and simplify it to a tautology. This means what they are showing is only that P(x, y) implies truth, but that doesn't tell you anything about the truth value of P(x, y) (recall that True => True and False => True)

In general proofs should start with statements that have already been proven to be true, not the other way around

[glossy roost]

Got it! Also this explanation is very helpful for thinking about how to go about writing a proof for it. Thank you!

[hidden violet]

Hi, can someone help me explain how to solve this problem? Given a set M= {1, 2, 3, ..., 99, 100}. How many placements without repetitions exist of the elements of the set M of four elements each that contain: a) number 47, b) simultaneous 17 and 47

I tried to solve this problem, but i don't know is my solution correct. Solutions 4 options for the number 47 and placement from 99 to 3. 4*A(97, 3)

[haughty garden]

If by placement, you mean “without order”, then you simply need to choose 3 more elements to make your set of four elements. So you then have C(99, 3). If by placement you mean “with order”, then each unordered set has 4! ways of being chosen. So this gives you 4! * C(99, 3)

For (b), it’s similar but this time you want to force both 17 and 47 in the set already, so you have 98 more choices to pick/choose 2 more elements

[cerulean plover]

do we use an equal sign or a logically equivalent sign when dealing with propositional functions?

p(x) = (2x = x + x) or p(x) ≡ (2x = x + x)

[versed oasis]

i would use $p(x) \iff 2x = x + x$

[vital dew]

kaue

[cyan dew]

I like $p(x) := 2x = x + x$

[vital dew]

Morrow

[formal pewter]

Here is an interesting question. Let's say G = {a, b, c} is a group with three elements with an operation *

Now since G is a group, there is a neutral element in it. Let's call it the element a

Now let's say that b*b=a

What can you then say about what is b?

[cerulean plover]

so then how would we use it in an assumption?
You wouldn't say "Assume $p(x) \Longleftrightarrow 2x = x + x$", since that assumption isn't that they're both true, it's that they're equivalent. I want to state "P(x) is equivalent to blahblahblah and they're both true"

[vital dew]

Alrighty

[cerulean plover]

you can do \iff???? bruh i have been using

Longleftrightarrow

for like a year 😭

[versed oasis]

the iff acts like an "equals" for statements, this is its truth table:

False iff False --> True
False iff True --> False
True iff False --> False
True iff True --> True

[versed oasis]

yep it stands for "if and only if"

[cerulean plover]

i know how iff works, but what i'm saying is that in the assumption of a proof, you say "Assume p(x) is true". if i say "Assume $p(x) \iff q(x)$", I'm just saying that they're equivalent. I want to state that they're equivalent AND they're true.

wha

oh it think i'm using the underscore

breh

[vital dew]

Alrighty

[versed oasis]

couln't you just say "Assume p(x) is true" or "assume 2x = x + x"?

[cerulean plover]

i'm doing proof by induction, my professor wants me to state the propositional function AND the actual function so we can perform algebra on it

so like

he wants the p(k) and the (2k = k + k)

and he wants us to assume they're both true

i guess i could do like $p(k) \land (2k = k + k)$, but this makes them seem like they're two separate things

[vital dew]

Alrighty

[versed oasis]

Seems like you're trying to do two things at the same time, i would just define p(x) as 2x = x + x and then assume p(k) is true for some k

[cerulean plover]

professor wants it, not me

i do define it earlier that p(x) \iff 2x = x + x

but he's weird ig and wants me to include the definition and the function in the assumption

[versed oasis]

would something like "Assume p(k) is true for some k, so we have 2k = k + k" do it?

[cerulean plover]

probably

[cerulean plover]

Assume $\forall k (p(k)), \therefore 2k = k + k$

[vital dew]

Alrighty

[cerulean plover]

?

[versed oasis]

Normally, when you're doing induction you are assuming for a specific value k, to then try to prove for k + 1

not for all k

if you were to use universal quantifier, you would use $\exists$

[vital dew]

kaue

[cerulean plover]

we have our basis step which proves that p(k) for the smallest value on the domain, but then we have to prove that p(k) -> p(k+1) for all k in the domain

[versed oasis]

"it's true for all values in the domain" is the conclusion, when you are doing the inductive step you assume for a single value k, and then prove its true for k + 1

and if k + 1 is true so is k + 2, etc.

assume $\exists k \in \mathbb{N}$ such that $p(k)$ is true, this means $2k = k + k$

[vital dew]

kaue

[lethal linden]

The syntax doesn't really matter. The professor is trying to make sure you're clear on what the proposition is and what variable you're inducting over, which will both help him see what you're confused about and help you avoid common mistakes w/ inductive proofs.

\\

I'd just say: Let $P(k)$ be the proposition that $2 \cdot k = k + k$ and write $$P(k) := 2\cdot k = k + k$$

$P(0)$ is clear. Then if you write out what $P(S(k))$ means it will become clear what you need to prove. Here $S(k)$ is the successor of $k$. You get: $$P(S(k)) := 2 \cdot S(k) = S(k) + S(k)$$

Well, how is multiplication defined? The recursive part of the definition is something like: $$a \cdot S(b) = a + (a \cdot b)$$

The left-hand side of the equation for $P(S(k))$ is $2 \cdot S(k)$, which looks just like the left-hand side of the definition of multiplication. How convenient!

[vital dew]

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

[lethal linden]

The purpose of this approach is that if you have a clear, explicit expression for $P(k)$ then writing out $P(S(k))$ is almost mindless: find every $k$ in the expression for $P(k)$ and replace it with $S(k)$.

[vital dew]

Cufflink

[weary tiger]

How can you define the notion of a set rigorously?

After some research I can say that that wasnt a bad response since it seems fundamental @vestal bronze
im just gonna stick with the good old "ignore the meaning, if it stops working change the axioms" ig

[vestal bronze]

the problem with my definition is that it's actually about mutisets, where it matters how many times you have the same thing

sets are like, " for each thing you either have it or not", you define a set by defining what things are in and what are out

and then the problem is that you would assume the set can have itself

[weary tiger]

paradox yay

[vestal bronze]

so you can't give a short intuitive definition, it's jsut that speciific thing

[weary tiger]

my problem was more with recursivity than intuition

[lethal linden]

Every definition is an expression of something in terms of something else. What would a satisfactorily rigorous definition of a "set" look like?

In other areas of math, we might call a definition "rigorous" if it can be framed in terms of sets and acceptable set operations + theorems.

But that's not available here.

[weary tiger]

Youre right
My question was wrong to begin with

[vestal bronze]

Set :: List Set

apart from the mentioned earlier paradox, that makes sense i think

[lethal linden]

It's not wrong, but it means one has to interrogate the nature of "rigorous" and "definition"

[weary tiger]

yea its a good definition
from what I can think of now, the notion of lists seems to be fundamental

[weary tiger]

I meant my expectations and question contradicted themselves

thanks for answering my questions though

[fossil mural]

well the issue with this is that sets aren't ordered and can be infinite, and also List has more than one fixed point so this doesn't uniquely specify what Set is, and also some type constructors have no fixed points so in general defining types recursively this way might lead to contradictions

[vestal bronze]

infinite is fine

it doesn't cover uncountable

[fossil mural]

well you'd need an infinite list... ok yeah i guess if "List" counts a list of length omega then that works

[vestal bronze]

list is a pair (thing, list)

thing is the first thing

so it's already optionally infintie

[fossil mural]

ok that's another case where the definition is recursive and ends up having more than one fixed point

[vestal bronze]

right, it's also optionally not a pair

[fossil mural]

what

[weary tiger]

Cant you define it as a classification of objects?
objects are things
and classication is whatever it might be

[fossil mural]

well that's even less of a definition than "Set = List Set" is

like you've just moved the issue to defining "classification"

[weary tiger]

isnt it fundamental though since its rooted in patern recognition?

[fossil mural]

and also it's not clear how something like "all of the sets that don't contain themselves" isn't a classification

[vestal bronze]

a set is a singleton set, or a union of two sets, or an empty set

[fossil mural]

at the point where you're saying things like that you are no longer doing mathematics, you are doing philosophy

[vestal bronze]

maybe it covers uncountable now idk

[fossil mural]

this might include uncountable things

[weary tiger]

isnt math based on phisolophy?

[fossil mural]

"might" as in this defines a proper class of distinct notions of "set", which includes "all of the sets" but also "only the finite sets" or "only the countable sets" or various bizarre middle grounds like "everything that is a union of a subset of R and a finite set"

[lethal linden]

https://en.m.wikipedia.org/wiki/Fixed-point_lemma_for_normal_functions

[fossil mural]

well i don't know what you mean by "based on", but in any sense that's relevant to this conversation, no

mathematical proofs can be checked by computers, philosophy can't (it can't even be checked by humans)

anything which isn't literally a syntactically valid string of symbols in the formal language that you're using, is not a definition, because you cannot explain to a computer what the definition means and what a correct proof involving it would look like

[weary tiger]

I mean that you can have phisolophy without math but not vice versa. It implies that you need philosophy to define math, if my understanding of the definition of philosophy is correct.

[fossil mural]

(of course in practice humans don't actually communicate purely in computer-readable piles of symbols, but still, this is what the standard of mathematical rigour means, anything that cannot be converted into something computer-readable is either not mathematics or just wrong)

[fossil mural]

I mean that you can have phisolophy without math but not vice versa.
i think this is wrong but it doesn't seem like the most important point to address so let's skip it for now
It implies that you need philosophy to define math
maybe you do in order to "define math", in the sense of philosophy, but in mathematics "definition" means something different to that

[weary tiger]

cufflink said that rigour means that it can be defined by set theory
but we are talking about defining the actual sets

[fossil mural]

...i think "rigour means definable in set theory" is just imprecise/wrong tbh

but anyway, the fact that we're defining sets doesn't mean that what the word "definition" means changes

[weary tiger]

what is the correct definition then?

[fossil mural]

well, in what context?

if you're working in ZFC and want to know what "sets" are, well they're just all of the objects

[weary tiger]

so sets := all objects?

[fossil mural]

if what you really mean is "how do you explain to a computer the kind of thing humans do when proving things about sets", then i think the best answer is something like the axioms of ZFC, although exactly which axiom system... will depend on which humans you're talking about and what they're doing

[fossil mural]

in ZFC, yes

[lethal linden]

That's not what I said!

[weary tiger]

What did you mean?

[weary tiger]

What are objects?

arent objects everyting?

[fossil mural]

yes

in the sense that "x is an object" in this context is just always a true statement

[weary tiger]

interesting

[lethal linden]

Someone looking for a "rigorous definition" is looking for a definition that they find satisfactory in some way. Every definition of something is given in terms of something else, however.

In most mathematical contexts, what satisfies someone's demand for a "rigorous definition" is a definition given in terms of sets and their operations.

In other words, such a definition usually suffices, but that doesn't mean it's necessary.

There might well be other objects that would satisfy their demand for a "rigorous definition", if only we could adequately conceive of them.

[weary tiger]

That makes more sense now

[lethal linden]

But someone looking for a "rigorous definition of set" isn't going to be satisfied by defining sets in terms of sets, even assuming you can somehow do it in a non-circular way.

Hence the hope in the 19th century of people like Frege that set-talk could be reduced to pure logic.

[velvet condor]

are the variables free because there is no "for some" or "for all" in this thing??

nvm he covered it in the next minute

[brave rock]

Well what's the standard way to show that something is a subset of something else? We begin by taking some arbitrary element of the former, and showing it must be an element of the latter.

So suppose that y is some element of [a]. What does this mean in terms of the relation? Note that you know a ~ b, so what does this imply?

[clever kite]

Are multiplicative inverses unique?

I did a quick proof that I think means they have to be, but I wanted to check

[brave rock]

Yes

[lethal linden]

Let b,c be two inverses of a, then:

b = be
  = b(ac)
  = (ba)c
  = ec
  = c

[clever kite]

Yep ok, that's what I did basically

[cursive nymph]

I'm just a bit confused
aren't axioms recursive?

For example. We say that Powerset axiom states the following:

Given set A, there is ZF(C) set P s.t. x in P <==> x subset A

so, when we said there exists a set P, we have to guarantee is satisfies the Axiom of Power set. But we are right in the middle of defining what that even means!

[fossil mural]

the axioms don't define what sets are

we just have "set" as an undefined term and then the axioms are some assumptions about the properties of sets

[cursive nymph]

so, instead of saying «there is a ZF(C) set P», I should've just said «there is a set P», right?

[fossil mural]

yeah it's just "there is a set P"

[cursive nymph]

wait, but don't we have to asses it's a 'ZF' set to have any usefulness from the axioms?
for example, that not-necessarily-ZF-set might be a set that contains all the sets..

cause in the powerset axiom, we asses there is just a set, not the more restricted notion of a ZF set

[fossil mural]

well according to the axioms there can't be a set that contains all sets, because then (by the axiom of separation) it would have a subset which is the set of all sets that don't contain themselves, and this is a contradiction

[cursive nymph]

there can't be a zf set, right?

i.e. a set that satisfies those axioms..

i feel I'm confused..

[fossil mural]

the axiom of separation doesn't say "every zf set"

[fossil mural]

it's not an individual set that satisfies the axioms of ZF(C)

it's more like, some meaning of the word set satisfies the axioms of ZF(C)

to check if the axioms of ZFC are true you need to know about all of the sets and their membership relation

for instance if you declare that a "set" is one of the letters A, B, C, and that the membership relation is {(A, B)}, then this isn't a model of ZFC, because for instance the axiom of extensionality fails, A and C have the same elements but they aren't the same set

if a "set" is a natural number, with n \in m iff the nth binary digit of m is 1, then this is "almost" a model of ZFC, but it doesn't satisfy the axiom of infinity

[fossil mural]

maybe it would help if we look at a simpler theory?

consider the theory with a symbol < and the axioms:

1. for all a,b,c, if a < b and b < c then a < c
2. for all a,b, if a != b then either a < b or b < a
3. for all a, a < a is false
   this is just the axioms of a total order

then one model of this theory is the natural numbers, with the obvious < relation

the integers are another model of this theory

but it wouldn't make any sense to take some random object like 4 and ask if it's an "ordered object"

an order is on a set

[cursive nymph]

oh, I don't know what a model is, yet : (
just the basics of ZF axioms

[fossil mural]

basically it's just "a structure that the axioms are true in"

[fossil mural]

for instance my claim that N is a model of this expands into just

1. for all natural numbers a,b,c, if a < b and b < c then a < c

etc.

[cursive nymph]

so we basically 'define' what a set is, in a model, right?

[fossil mural]

...kind of

i'd say it's more, a model is a possible meaning for what a "set" is

but like, there's loads of them

ZFC can't prove or disprove the continuum hypothesis, which is that there's no set with cardinality strictly between the natural numbers and the real numbers, and the way we know that is that we can construct a model of ZFC where the continuum hypothesis is true and another model where it's false

but yes in the sense that the theory ZFC itself doesn't really say what a "set" is (just some properties that we expect sets to have), and a model does

from a philosophical platonist perspective the reason we're doing all of this is that we think there's some "real" universe of sets (which would be a model of ZFC), but we don't know how to define what exactly it is so we kind of just wrote down some statements that should obviously be true about it, and ended up with ZFC

[lethal linden]

I'd think of it more like this.

We have some vague, intuitive conception of a mathematical object, like number or function or set. If we want to prove things about them we have to make our conception precise enough to do math with them.

Axiomatic systems like ZFC aren't a "definition" of set per se. They're more like one attempt to make our conception precise enough that we can do math with them.

So, the power set axiom is saying something more like:

Under this conception of set, if I can talk about some set A then I can talk about the set of all subsets of A.

If you presented a conception of set and power set such that A was a set but it had no power set then I'm committing myself to saying that A isn't a set or that I have to change my conception of set/powerset.

Take something less tricky like the axiom of pairing: if A and B are sets then I can talk about a set containing just those two sets and nothing else, designated {A,B}.

If someone told me there were sets you couldn't pair like that, I wouldn't say "You're wrong, the axiom of pairing says..."

I'd say "Their conception of 'set' must be very different from mine."

That when they say "set" and I say "set" we mean different things.

[cursive nymph]

yes, yes
that is clear: we don't define what a set is, but say what it should behave like

what confuses me tho is that it seems those 'what it should behave like' conditions are resursively defined on top of each other(?)

[lethal linden]

Sure. I mean, how do you feel about Peano Arithmetic?

[cursive nymph]

|| if I have enough fingers on my hand to verify the result, then I believe in it xD /s ||

ok with it

[lethal linden]

Ok, but there are lots of things about PA that you can't verify with your fingers.

[cursive nymph]

yeah, sure
that's why I put /s at the end

i'm ok with PA

[lethal linden]

Right, well, it's giving a particular conception of number.

If you're ok with pulling the successor function S "from the void", so to speak, then why not also be ok with talking about the power set in the same way?

If I have a natural number n then S(n) is also a natural number.

If I have a set A then P(A) is also a set.

Part of the awkwardness are the restrictions in the formal language of set theory. It consists of a bunch of variable and constant symbols, but only a single binary relation ∈. That means you can't talk about "functions" directly.

[cursive nymph]

yeah, that is move convincing!
thx!

[lethal linden]

What does it mean for some set X to be the power set of some other set A?

It means that S ∈ X if and only if S ⊆ A.

So we say: "For all sets A, there exists a set X such that: for all sets S S ∈ X if and only if S ⊆ A."

Ok, but formally we have to unwind S ⊆ A, too, so it only uses ∈.

Well, S ⊆ A means "For all sets w, if w ∈ S then w ∈ A"

So the full power set axiom is that concept, but expressed using only first-order logic and a single binary relation ∈.

[lethal linden]

Sometimes our axioms really do seem to capture something, e.g., when there's exactly one model up to isomorphism. Such a theory is called "categorical": https://en.wikipedia.org/wiki/Categorical_theory

For example, using second-order logic, there's exactly one model of Peano Arithmetic up to isomorphism.

So if you and I both commit to second-order PA then any apparent mismatch between our conceptions is a matter of us labeling things differently (or at least one of us being wrong).

Dedekind wrote a famous paper in the late 19th century called "What are numbers and what should they be?" where he first laid out a lot of the contemporary axiomatic characterizations of things like "infinite set": http://aleph0.clarku.edu/~djoyce/numbers/dedekind.pdf

[cursive nymph]

another (probably more dump, but I'm just starting out) question:

to show that there cannot be a set U that contains all sets, we might say:

• Assume it exists
• by AoSeparation, take its subset, call it A, with the formula phi x not in x
• Then: A in A <==>^"def" A not in A

correct?

[fossil mural]

yep

[cursive nymph]

similar one:

given a set A, show that the collection of x's, s.t. x not in A, is not a set

assume this is indeed a set. call it B. then B is defined as:

forall x [ x in B <==> x not in A ]

checking: A in B <==>^"def" A not in A

all good?

/ going thru some exercises without answer sheet /

[grand totem]

You're supposed to conclude with a contradiction. In the previous proof that contradiction followed from A in A <-> A notin A. So while what you've written so far isn't wrong, you're also not quite done yet.

[cursive nymph]

oh, yeah, my bad
didn't notice it. I thought for some reason I wrote A in A (not B) <--> A not in A

thx

[cursive nymph]

then ig a better way would be to try to construct a set of all sets like this:

A union overline(A)
where overline(A) is the set of elements that do not belong to A

so, we have x in A u ov(A) <==> x in A or x not in A <==> foral x

but I've already shown that a set of all sets cannot exist. so..

[grand totem]

That works 👍

[cursive nymph]

is there difference between the two?

feels like the second one will also include e's that are not in A

i.e. False=>* is true

[odd heart]

I don't get the second one, it seems to claim that everything is an element of A (which is very unlikely to hold)

The first one seems fine as a definition of intersection

[cursive nymph]

well, I was trying to come up with a definition for int A

but I just didn't know which of those is the correct one

[odd heart]

The second one can't be true, because it says that every e is an element of A, so A is the set of everything

The first one is fine

[cursive nymph]

my concern is that if we say forall e [e in A ==> {....}]

then it might accidentially include either e's in A, or x's in int A, that aren't meant to be there, because of False=>Anything is true

[grand totem]

{x | \forall e (e \in A \land x \in e)} would simply be empty, no matter the choice of A

So that doesn't sound like a good definition for the intersection

[odd heart]

If e is not in A, then the implication is vacuously true and we don't care whether or not x belongs to e (which is the correct way to go about it)

If e is in A, then x has to be in e, which is also what we want

[cursive nymph]

But look. Take e not in A. Then that thing is vacuously true. So, it implies some x (can be anything) is in the intersection, no?

[odd heart]

No, because the implication has to hold for every e

[fossil mural]

well the implication has to be true for every e simultaneously

[odd heart]

For the e which are not in A it holds vacuously, and for the e which are in A it might hold and it might not

So "practically" all we need to check is what happens for the e which are in A

But for all of those, x has to belong to e

[cursive nymph]

i'll meditate on this one: don't get it atm

[odd heart]

You've got the universal quantifier there

[fossil mural]

if you imagine there were only five sets $s_1, s_2, s_3, s_4, s_5$

[vital dew]

bee [it/its]

[fossil mural]

then a forall reduces to just a conjunction $(s_1 \in A \to x \in s_1) \land (s_2 \in A \to x \in s_2) \land (s_3 \in A \to x \in s_3) \land (s_4 \in A \to x \in s_4) \land (s_5 \in A \to x \in s_5)$

[vital dew]

bee [it/its]

[fossil mural]

now if for instance $A = {s_1, s_4, s_5}$

[vital dew]

bee [it/its]

[cursive nymph]

right

[fossil mural]

then $s_1 \in A \to x \in s_1$ is just $s_1$, because the hypothesis is true

[cursive nymph]

I think i see where you are going

[vital dew]

bee [it/its]

[fossil mural]

$s_2 \in A \to x \in s_2$ is just true

[vital dew]

bee [it/its]

[fossil mural]

and so on for all the others

so you get $x \in s_1 \land \top \land \top \land x \in s_4 \land x \in s_5$

[vital dew]

bee [it/its]

[fossil mural]

and then the two conditions that are true essentially just vanish, like if you had added 0 or multiplied by 1

$x \in s_1 \land x \in s_4 \land x \in s_5$, exactly what we wanted

[vital dew]

bee [it/its]

[cursive nymph]

i think i got it now
thankss!

[odd heart]

That's generally why implication is defined the way it is (which confuses a lot of people), in particular why "false -> anything" is a true implication.

Because it means that in this kind of statements with universal quantifiers, all that actually matters is the cases where the antecedent of the implication is true.

When it's false, the implication holds either way so we don't care.

But when it's true, we also need the second part of the implication to be true, and that's the only significant scenario

[earnest umbra]

Hey y'all do you know a good book to learn about Discrete Mathematics? I need help specifically with Topic 1 -> Preliminary concepts and number theory. Topic 2 -> Sets, Functions and Counting. Topic 3 -> Graph Theory, Topic 4 -> Classical Propositional Logic.

[lethal linden]

https://www.amazon.com/Invitation-Discrete-Mathematics-Jiri-Matousek/dp/0198570422

[earnest umbra]

Do you think this book will help me? Cause rn i'm really struggling with discrete maths

[lethal linden]

I don't know you. I couldn't possibly say.

[earnest umbra]

Do you know any other books? I'm looking if that book is in my uni's library

[cursive nymph]

btw, what if A=empty?
i.e. \bigcap \varnothing = ?

forall e [ e in A => ... ] will evaluate to true

so will this intersection contain, well, everything?

[odd heart]

Sort of, there's a discussion here: https://math.stackexchange.com/questions/959201/the-intersection-of-an-empty-family-of-sets

[cursive nymph]

oh, interesting
Thanks!

[odd heart]

Typically when you work with unions and intersections, all your sets are subsets of a common space, and universal quantifiers are understood to only apply to element of that space, in which case the intersection of an empty family would be the whole space.

If you're not in a fixed space, then yeah, the intersection of an empty family would be the set of everything, which is a problem (and you should probably bypass it by refusing to consider an intersection of empty family)

[cursive nymph]

I was trying to pin-point where exactly the proof that bigcap A is not a set breaks down when A=ø, but I couldn't..

in that phi(x)
if cal(F) is empty, then indeed phi(x) is true for all x

but the thing is – this is just a separation
we will get at most bigcup F, and no more

so idk where the potential «set that contains all the sets» pops up

wait, what
why do we need to include x in c?
(obviously it must somehow fix the issue, but I just don't get the motivation for asserting that in particular)

/ related to the same question above /

[grand totem]

$c\cap\bigcap A$ is a set by separation (since $c$ is a set) and $c\cap\bigcap A=\bigcap A$ since $c\in A$ and hence $\bigcap A\subseteq c$

[vital dew]

Neverbloom

[cursive nymph]

no, I absolutely understand that it gives the desired result

after all, (x in c AND x in A\{c}) is just (x in A)

i don't get the motivation for that step

[fossil mural]

well to apply separation we need a set that we're constructing a subset of

[cursive nymph]

isn't union A already a set?

so we do separation on it

[grand totem]

Sure, but that requires an additional axiom and doesn't really do anything better than just picking an element from the family

[cursive nymph]

i mean, I'm rather looking to see where exactly my attempted proof, using this axiom of union, shoulda failed

compared to finding the optimal proof (?)

you probably have already explained it; sorry if I don't get it :[

[grand totem]

Your proof only shows that ${x\in\bigcup\mathcal{F}\mid \varphi(x)}$ is a set, you'd still want to show that ${x\in\bigcup\mathcal{F}\mid \varphi(x)}=\bigcap\mathcal{F}$ and that will require the assumption that $\mathcal{F}$ is nonempty.

[vital dew]

Neverbloom

[cursive nymph]

hmm

[grand totem]

A real argument why separating from the union isn't a terribly good idea:
The proof that picks an element out of the family to separate from actually proves that the intersection of any nonempty class is a set.
Taking intersections of proper classes does come up every so often (for example when constructing omega as the intersection of all inductive sets) and then the proof that separates from the union doesn't go through since the union of a proper class is again a proper class (good exercise!)

[cursive nymph]

thank you for the input!
I will come back to that later
(I will. I literally saved ur reply in notion xD)

[weary tiger]

Six X ' s have to be placed in thesquares of the figure below, such that each rowcontains atleast one X. In how many different wayscan this be done?

[true venture]

If I start choosing subsets of an nset, how many must I choose before, the collection of chosen subsets covers [n]? Worst case is choosing all n singletons, but say I assume I choose a subsets of some cardinality first, is there a name for this?

[true venture]

How does one x in each row not satisfy "each row contains one X"?

[weary tiger]

If we place 4 xs in the row 2 and 2xs in the row 1 then row 3 is all empty soi this unsatisfies the condition

[true venture]

Oh you have to place 6 total

[weary tiger]

Yuh read the text first 😭

[true venture]

Sry

[weary tiger]

Ots alr

[true venture]

Since the six xs fill up most of the diagram, it can be helpful to think of this by counting the 2 squares that will be left open

[weary tiger]

I am thinking of placing the first 3 xs in each row so that they satisfy the min 1x condition

@true venture what u think

[true venture]

That's what I though of first, but then when you place the remaining 3 xs you get some overlap

[weary tiger]

Yuh

[true venture]

If you can account for that then that way could work, but for me seems easier to count the empty squares

[weary tiger]

Can we jsut delete those overlaps by counting

[true venture]

We need to leave two squares open. If we number the squares 1-8, going left to right, top to bottom. Then we can count the pairs of empty squares by the first number of the pair.

Also the pairs are all (a,b) a<b.

Then since this is small you can think if I leave Square 1 open what others can I leave open, if I leave 2 open....

[weary tiger]

Should i tell u the answer

[true venture]

Do you have it, let me add them up see if we get the same

[weary tiger]

Its 26

[true venture]

Yea I get 26 too

[weary tiger]

Wiat how

Shiw mee

[true venture]

Do you get what I mean by number the squares

?

[weary tiger]

Yes i get that u need to leave 2 squares empty right

[true venture]

• 1 2 *
  3 4 5 6
• 7 8 *

[weary tiger]

Alr

U numbered them then

[true venture]

So if we leave Square 1 open, what other squares greater than 1 could I leave open?

[weary tiger]

Any one from the 7 squares

[true venture]

Really Square 2?

[weary tiger]

How

I mean why

[true venture]

You need one x per row

Both 1 and 2 can't be open

[weary tiger]

Ohhh okayy now i got it

U ksut used elimination technique

[true venture]

Yea

[weary tiger]

Can we do by my method

[true venture]

So, leaving Square 1 open there are 6 other square greater than 1 I can leave open. Then repeat this for the rest of the square and sum

[true venture]

Idk if I know 😅.

[weary tiger]

Okay but can u try that way

[true venture]

Idk, it's maybe like double counting

[main cargo]

I have a problem but I don't understand the answer really, could someone help me please?

The problem is: There are 4 people on an elevetor in a building and the building has 10 floors, how many possibilities are there for 2 person to get out on each a different floor and then 2 to go together on the left over floors?

The answer given is: 109(4 choose 2). Can someone explain or is this wrong?

[main cargo]

ping me please

[solar marsh]

4320

Among the 10 floors, you must choose 2, then choose 2 people in an ordered way (who will go to those two floors), then choose one from the remaining 8 floors. In total: C(10,2)*4*3*8

[cursive nymph]

this isn't possible, right?

[solar marsh]

A={{1}}
B={2}
C={{2}}
D={1}

[cursive nymph]

oh...
thanks!

Ig I was a bit intimidated by the number of curly braces xD

after you replied, came up with another example (after I was sure it is possible xD):

A={{ø}}
B=ø
C={ø}
D={ø}

[fossil mural]

yeah basically the trick is just, you want A = {D} and {B} = C

[cursive nymph]

cool little exercise 🙂
now I know why we don't define ordered pairs this way

[cursive nymph]

did I miss anything?

[odd heart]

Seems fine

[inland zenith]

I'm stuck trying to prove that a bipartite graph G=(A,B) with maximum degree \Delta has a matching of size at least |E(G)|/\Delta. I know the chromatic index is \Delta but not much else, unsure how to proceed

[next sail]

hey guys!

anyone know how to approach the problem?

[inland zenith]

got it, I got a hint from SO, show that the size of the smallest vertex cover must be geq this number

[solar marsh]

Use Konig theorem

[inland zenith]

Yeah

[hardy stag]

is a pair a set? my graph theory textbook says that an edge set isn't a family but I was always under the impression that a pair is a set of two things

[brave rock]

In ordinary set theory, everything is a set -- we construct things out of sets because we want to provide a foundation for mathematics purely in terms of sets. So yes, in particular a pair is a set.

However, this is the important part -- the pair (a,b) is NOT equal to {a, b}.

I forget the standard construction of this, but it doesn't really matter in this case.

The point is that although it is technically a set, you should think of it as its own thing with its own rules.

(a, b) is typically not going to be equal to (b, a), whereas {a, b} = {b, a}, for example.

[lyric quartz]

Is'nt {a, {a, b}} a common construction?

That way the second element of ordered pair is the one that contains the other element need to go a level deeper, not trying to explain it 😛

[brave rock]

Something like that, yeah. It doesn't really matter.

[cursive nymph]

I can't remember ever using the fact that f is injective iff it has left-inverse and similar for surjective/right-inverse

what are some applications of this little proposition?

[ember cypress]

if i have a class of 50, of x boys and y girls, 30<x<40
I want to split the class into smaller groups of 5 that are preferably more gender balanced, so ratio of 3:2 between genders is best, 4:1 is less desirable, 5:0 is worst.
Is it correct to say that even in the best case scenario ill still need x-30 groups with ratio of 4:1

[grand totem]

This is such a broad question that the simple and obvious examples are probably escaping me right now, but some very random stuff that just came to me without thinking about it much:

• [left-invertible -> injective] If one defines the naturals (up to unique iso) as a triple (N, 0 \in N, s : N -> N) for which there is a unique homomorphism to any other such triple then one can prove that s is injective (one of peano's axioms) by constructing a predecessor function (which is the left-inverse of s),
• [surjective -> right-invertible] Surjections are essentially the same thing as partitions, in particular you could construct a right-inverse to a quotient map [-] : A -> A/~ which picks representatives out of each equivalence class.

You can combine one direction of one theorem with the converse of the other theorem to get two corollaries:

• (i) [injective -> left-invertible + right-invertible -> surjective] If there exists an injection from X to Y (with X nonempty) then there exists a surjection going the other way,
• (ii) [surjective -> right-invertible + left-invertible -> injective] If there exists a surjection from X to Y then there exists an injection going the other way.

These two essentially allow you to go back-and-forth between two notions of what it means for a set to have cardinality less than or equal to another set (remember that |X| \leq |Y| iff there is an injection from X to Y). The latter (ii) is also known as the partition principle.

One example where (classical) mathematicians often implicitly use (i) is in the proof that |A| < |P(A)|. That |A| \leq |P(A)| is clear since {-} is an injection, showing that |P(A)| \leq |A| does not hold boils down to showing that there can be no injection from P(A) to A. But using the contrapositive of (i) with X = P(A) (which is nonempty) and Y = A tells them that it would be sufficient to instead show that there is no surjection from A to P(A), which is precisely the statement of Cantor's theorem.

[grand totem]

Other than that, I would consider neither of these propositions to really be that innocent. That every left-invertible function is injective (and similarly for right-invertible and surjective) is easy to prove and unremarkable, but neither of the converses are that uncontroversial.

Every surjection having a right-inverse is famously equivalent to choice. This shouldn't come as a surprise if one identifies surjections with partitions since then this proposition essentially reads that every partition on a set has a choice function. Whether (ii) implies choice is a still open question.

Meanwhile in constructive mathematics, the proposition that every injection (out of an inhabited set) has a left-inverse, proposition (i) and the law of excluded middle are all equivalent. So a constructivist would even reject the preceeding proof that |A| < |P(A)| (though there are ways to prove this constructively).

[cursive nymph]

Every surjection having a right-inverse is famously equivalent to choice
oh wow, interesting!

Alluffi actually skipped over it somehow (probably bc he decided to use naive set theory ):

[cursive nymph]

wait, abt the second example

did u really mean just pick a representative from each eq class?

that might not be a function, right?

[grand totem]

Why wouldn't it be?

[grave anchor]

length of period of a rational number (2 and 5 dont divide denominator and denominator isnt 1) is the order of 10 modulo the denominator right?

[obsidian cove]

Can someone help me with fields?

I dont understand how F = {0, 1} is a field

[inland zenith]

check the axioms

[obsidian cove]

But correct me if im wrong, isn't one of the axioms of a field that each element in the field has a a number such that adding it to the number makes it equal 0?