discrete-math

[fossil mural]

I don't understand your 24 cent coin point though. I know that for other denomination it doesn't work. I am new to this so I really appreciate you taking a look, please elaborate on why I have to consider other coins when I have restricted the problem?
well, consider this proof that in fact 25 + 2 + 2 is the best way to split 29 with the denomination 1/5/10/24/25

i can repeatedly take 25 cents (which is optimal) and then i'm left with 4 and we know the best way to split that is 2 + 2

29 = 25 + 2 + 2 is therefore optimal

[digital sinew]

i think it does prove optimal

[fossil mural]

you don't have to address other denominations in the actual finished proof, but you do have to address the specific denomination that you are looking at, and use enough properties of it that the proof doesn't work with other denominations

not because that's an extra rule or anything but just because you can't prove false things, and so if your reasoning can be used in a different situation to prove something false, it must not be valid reasoning

and this is useful to know because it's faster than reading through the entire proof, and will often tell you that an error must exist somewhere even if the actual mistake is extremely subtle and you wouldn't have seen it if you didn't know to look for it

[fossil mural]

whatever hole this argument has, and it must have one because its conclusion is absurd, also exists in your original argument

[fossil mural]

the simpler version of this is when there's an outright counterexample

if i found an amount of money where the greedy algorithm just doesn't split it up optimally (on 1/5/10/25), that would show that there's an issue with your proof, because the intended result is just wrong

i can't give a counterexample like that because as it happens the result you were going for is correct

[digital sinew]

||oop|| ( no counterexamples found for n < 10^7 )

[fossil mural]

but if you had a proof like

Theorem: 4 is even
Proof:

1. 4 is a natural number
2. all natural numbers are even
3. therefore 4 is even

i mean in this case it's very obvious where the incorrect step is

but you could also respond "ok well replace all occurrences of 4 with 3, where does the proof fail?"

[pseudo solar]

Okay thanks let me think about it more.

[quick jetty]

well im still kinda stuck on both of them tho

[pastel yacht]

Was wondering if my proof here was okay or if I’m just speaking gibberish and getting nowhere

[agile magnet]

why is X(G) = 2 after you remove the edge? You haven't made any progress

draw a few trees, how would you color them using the minimal number of colors possible?

you should see a pattern

[terse wyvern]

this proof is very circular (pun intended). essentially you want to show that you can colour a tree with 2 colours. could you do that using induction

[agile magnet]

Do this tbh, no induction needed

[ashen cliff]

Is this the right chat to ask questions about problems from extremal combinatorics?

[brave rock]

I'd suggest just asking, and people will point you elsewhere if appropriate.

[ashen cliff]

How does a person go about finding the number of intersecting families for n choose 2? In My first attempt, I tried selecting one number and counting all all other number it can be combined with but I'm running into the issue of duplicates

[agile magnet]

idk what you mean by "intersecting families for n choose 2"

can you give an example problem?

and your attempted solution

[crude shore]

Is there an easy way to see that, if $F_n$ is the $n$-th Fibonacci number, $F_{2n+1} = 4\left(F_n\right)^2 - \left(F_{n-1}\right)^2 + 2(-1)^n$?

[vital dew]

flebron

[crude shore]

I've posted the question along with some more context in https://math.stackexchange.com/questions/4953514/fibonacci-doubling-using-two-squarings

[crude shore]

Aaand answered. It's a combination of Cassini's identity and some manipulation.

[gentle nebula]

hello, I'm gonna be taking an "applied discrete math" course. Can anyone recommend me some good sources, books and videos to study discrete math.

[heady tiger]

Ask in #book-recommendations

[inland raft]

i feel uncomfortable about writing that yb must be a prefix and ay a suffix for w - i am not sure that it is even correct and couldn't prove it immediately. is there an alternative argument or an alternative approach for the whole problem?

[terse wyvern]

could you post the full context?

[inland raft]

the exercise is there at the top, is more context needed?

${a,b}^*$ is the set of all finite length strings of a's and b's

[vital dew]

pika

[brave rock]

I don't think any more context is needed...?

[brave rock]

Yes I agree this isn't well explained

[inland raft]

i am also not sure about fixing the y, i mean it should work cause it's arbitrary so this (if correct) shows that no pairs (x,y) can satisfy the eqn

[brave rock]

We're just supposing we have some minimal (in the length of x) counterexample, and presumably this is where the prefix and suffix thing comes from

I'm trying to think of why this is true

[inland raft]

related to this, there was an exercise before about showing that there is no string x in {a,b}^* such that ax = xb where the authors make a similar minimality argument and claim that x must be of the form x = aub since it must have a as a prefix and b as a suffix

[brave rock]

Wait this is confusing. Are they saying strings w that satisfy w = xay = ybx?

This is not well worded lol

[coral parcel]

Intuitively my first approach would be to count a's and b's in xay and ybx, but that might be awkward to make rigorous.
Perhaps with a monoid homomorphism from the free monoid {a,b}* to Z?

[inland raft]

this is saying w is a string for which way = ybw holds

[brave rock]

No pika I mean they're saying:

By well ordering on the set S of lengths of all strings on {a, b} that satisfy xay = ybx
But which are these strings?

[inland raft]

they here is me, i wrote the proof 💀 i am not sure i did it right

[brave rock]

OK well I don't understand the proof.

I don't find it convincing.

[inland raft]

S is the set {|x|; x in {a,b}^* such that xay = ybx}

[brave rock]

I agree with this. This is the simplest way to prove it.

[inland raft]

where |x| is the length of the string x

[brave rock]

I think you should use tropo's approach.

[inland raft]

i can make a count function that counts the number of occurances of the symbol $d\in {a,b}$ as such:
[c_{d}: {a,b}^{*} \to \mathbb{N}]
defined as
[c_{d}(x) \coloneqq \sum_{i = 1}^{|x|}\delta_{d}(x[i])]
where [\delta_{d}: {a,b} \to {0,1}], $\delta_{d}(x) = 1$ if $x = d$ and $0$ otherwise

[brave rock]

As Tropo pointed out, this is the unique function f such that:
(1) f(empty string) = 0
(2) f(d) = 1
(3) f(x) = 0 if x is a letter other than d
(4) for all words w, v, we have f(wv) = f(w) + f(v).
You get the existence of this function for free due to the nature of the monoid {a, b}*.

After this, you are pretty much done.

[vital dew]

pika

[orchid dune]

Hello,

Does anyone have any good channel / material to read/watch for Automata Theory? I'm studying online and the material is not covered in depth, but the questions make my head hurt.

I don't have much if any issues understanding Sipsers or Hopcrofts writings, but even simple questions from Rosen's textbook cause me to halt(pun intended).

Most of issues I have are with CFG's and Turing Machines. FSA so and so.

[agile magnet]

this would be a good channel for questions

[agile magnet]

wait so you can do exercises from Sipser and Hopcroft but not Rosen???

[orchid dune]

No no that's not what I meant. I meant that I don't have much issues following the text explaining theoretical basis and proofs, I can manage my way there, but when it comes to doing the exercises I go completely braindead, I haven't developed skills to approach the problems from different angles

And my course instructor never assigned exercises for the class, just reading sections from various books, I'm self teaching through Sipser and Rosen

I have completed Discrete Maths as prereq and scored in upper 90% so I think the foundations are not an issue here.

For instance the most I was exposed through lectures was constructing DFA's that find even/odd 1's.

On midterm however I encountered a question where in essence I had to create 3 independent DFA's and merge them. Solved it through bruteforce, and afterwards I asked my tutor to explain how to approach merging DFA's to get an answer that he doesn't know a concrete method to do it

[marsh raven]

Guys your views on Kenneth H Rosen book for a 2nd year cse student?

[terse wyvern]

it's ok enough. most undergraduate textbooks are fine

[marsh raven]

ok enough! okay

[austere vector]

How can I prove that a DFA (with 12 states, inputs {A, B, empty string}, 1 initial state, and 6 final states) is correct using induction? I'm not quite sure how to come up with the predicate. I was thinking of something like:
P(w) := After processing the string w, the DFA reaches the state q_i. (0 <= i <= 12)
For the inductive step, I need to show P(wA) (with A being one of the inputs). This means I need to show that for each state in the DFA, when the input "A" is processed, it transitions to some state in the DFA. Is it really that straightforward?

[marsh raven]

I have two different maths in same sem, Discrete maths and Advance applied mathematics, can me finding a good book for the later? I can provide you the syllabus!

[terse wyvern]

no clue

[terse wyvern]

can't help

[austere vector]

Base case: n = 1

A DFA with a single state must either accept no strings (If the state is non accepting) or accept an empty string (if the state is accepting)

If non accepting then the equivalent regex is ∅
If the single state is accepting then the equivalent regex is ϵ

Inductive step: Assume P(k) is true for k states. WTS P(k+1)

Consider a DFA with k+1 states. {q_1 .... q_k+1}

1. Add a dummy start state q_s with ϵ-transition to the og start state q_1
2. Add dummy accept state q_f with ϵ-transition from each og accept state to q_f

Then we eleminate the states using this formula

R_ij = R_il(R_ll)*R_lj

R_il is the transition from q_i to q_l and R_ll is the self loop on q_l and R_lj is the transition from q_l to q_j and I keep applying this until the dummt start and end states remain.

At the end the transition from q_s to q_f will represent the language of the OG DFA

The thing is Idk if this is good because I didnt get to use the IH at all

[agile magnet]

check your logic again for the base case in the accepting case.

You're implicitly using the IH in the "keep applying this until the dummy start and end states remain" part. You should argue that your transformed DFA using the elimination is equivalent + it has strictly fewer states and then directly apply the IH

also you will need a base case for the 2 state case (think about why)

[austere vector]

oh so when Im removing each q_i from the DFA with k+1 states Im going to end up with less than or equal to k states at one point and then I could just use IH on that right

[austere vector]

are you saying that I also need the 2 state case or replace the one state case with 2 state case?

[agile magnet]

Also need

(at the end of removing all the states you still have the 2 dummy states)

[agile magnet]

Yup

[austere vector]

Im kinda confused about what cases I will need to cover for the the 2 state base case. would it be something like this:

case 1: equivalent regular expression: R
s1 -> R -> s2

case 2: equivalent regular expression RS*

s1 -> R -> s2 -> S -> s2 (self loop on s2)

case 3: equivalent regular expression R + S

s1 -> R -> s2
-> S ->

[austere vector]

or wait do I just assume that theres only case for the 2 state which is s1 -> R -> s2 because when im removing all the states (beside the 2 dummy states) then theres going to be just one direct transition from dummy start to dummy end right?

no self loop or anything

@agile magnet

[agile magnet]

Yes

[austere vector]

bet tysm

[austere vector]

something like this would be good?

[sour scarab]

that looks good to me

[agile magnet]

whoops idk how I missed that ping, sorry

yea looks fine to me as well

nothing glaring but I didn't read super closely

[uncut heath]

there are one-state DFAs with non-empty languages

and you don't need to "repeat the process" on top of the inductive hypothesis, just apply the IH to the automaton without q0 (being mindful of the wording around the dummy states)

a major point of induction is that it's a way to formalize repeating a process

[stray sphinx]

TL;DR: Is there a convention for how an AND operator should be defined for 0 values?

[past rivet]

I think it should be true

This is because TRUE AND p = p

[stray sphinx]

My understanding is you can think of it in two ways, one of them
being 0 elements -> True.

[past rivet]

So it acts as an identity, which is the behaviour you want

Similarly, “OR” with 0 arguments should be defined as false

[stray sphinx]

Can you explain further? I'm a bit rusty on fundamentals and drinking coffee as we speak

[past rivet]

So, do you agree that TRUE AND p = p?

Or I suppose, that the two propositions are equivalent?

[stray sphinx]

Yeah, they both evaluate to TRUE

[past rivet]

Not necessarily

p could be false, after all

Unless I’ve misunderstood what you meant

[stray sphinx]

I have an extra layer confusing me here since I've been doing Python rather than pure boolean algebra.

[past rivet]

Ah nice, then I can use an analogy from Python

[stray sphinx]

the = operator over there could technically define as False for an object against itself.

[past rivet]

Then perhaps I’ll write it as

TRUE AND p == p

Do you agree with this?

[stray sphinx]

as in does True and (p == p) evaluate to True?

[past rivet]

Oh, I see your misunderstanding

[coral parcel]

No, (True and p) == p.

[past rivet]

Let me do brackets

[fossil mural]

no, (True and p) == p

[past rivet]

Yeah, thanks bee

And tropo

[stray sphinx]

Part of it is not understanding how "agree" has meaning here.

From my perspective, I'm concerned about predicate abstractions in a debugger and introspection-friendly way.

[coral parcel]

It's the normal English verb "to agree", no particular mathy meaning here.

[stray sphinx]

Yeah, just double checking. It's been a while since I took a discrete math course.

[coral parcel]

That is, do you need to be convinced that "true" acts like an identity with respect to "and", or do you already know that is the case?

[past rivet]

Yeah sometimes mathematicians do just use English words lol (though strictly I’m a physicist)

[stray sphinx]

I think the coffee kicked in. The point being made is that an AND operator is equivalent to using associative properties to make a reduce work with True as the starting value?

[fossil mural]

i'm not sure i 100% understand what you're saying but yeah i think you're fairly close

if you have an expression like (p and q and r) and (s and t), that should be the same as p and q and r and s and t, because "brackets don't matter"

so the same way, if you put brackets around nothing at all, "() and p" should be the same as just p

[stray sphinx]

It's what makes an n-argument AND function return True for 0 values

[stray sphinx]

I sort of think this makes sense now too:

• The starting value is False
• We're doing equivalent of a binary Or function in each reduce step

[coral parcel]

Same reason whysum([]) is 0.

[past rivet]

Yeah in general - when you want to extend a binary operation to one that takes in lists, then you want the operation to evaluate to the identity on an empty list

This is so that applying the operation is coherent with taking sublists

[stray sphinx]

to evaluate to the identity on an empty list
I don't think I fully understand this

[past rivet]

I.e. if you have a list of lists, it doesn’t matter if you flatten and then apply all(), or apply all() twice

[stray sphinx]

Also nested lists aren't an intended support target for now

that's an exercise for the reader (and why it's OOP. You can write your own rewriter or whatever if you need)

[past rivet]

Sure, though this is usually how “evaluate to the identity on an empty list” is motivated for me

[stray sphinx]

the OOP parts of the library are intended to be immutable and hashable to be consistent with Python's convention of functions being hashable

[past rivet]

If you defined all([]) = FALSE, then this would break

Similarly if you defined any([]) = TRUE, this would break

You might be using a list of lists implicitly in your program if you’re combining multiple all() calls, so it’s useful to have this property

[fossil mural]

it also agrees with the interpretation of quantifiers as basically big conjunctions/disjunctions

[past rivet]

Mhm mhm

[stray sphinx]

🤔

[fossil mural]

you can think of any([p, q, r]) as "p or q or r" or you can think of it as "there is some element of the list [p, q, r] that is true"

[past rivet]

I guess I’m taking a more “monadic” view on this

[fossil mural]

and then any([]) is interpreted as "there is some element of the list [] that is true"

and there clearly isn't, so any([]) should be false

[past rivet]

But I don’t think this is the One True Perspective, listen to bee here

[stray sphinx]

I think the best approach for me right now might be:

1. Polish this library to releasable alpha with doc over the next week or two
2. Post for criticism

[stray sphinx]

This still doesn't seem to make sense somehow on the surface.

i see the point about any([]) being False

[past rivet]

It’s the same idea

[stray sphinx]

https://tenor.com/view/confused-what-huh-gif-15321953

[past rivet]

any is the extension of OR to multiple arguments

[stray sphinx]

It just seems weird from an API behavior perspective to me.

[past rivet]

As bee pointed out

[fossil mural]

another alternative perspective: when you're trying to prove an "or", you get a choice

if you want "p or q" to be true, then you can show p is true and that's enough, or you can show q is true and that's enough

with "p or q or r" you get three options

[stray sphinx]

❗

[fossil mural]

with an empty "or", you have to choose from no options, and that's impossible so you lose

[stray sphinx]

I think this is a good way to phrase it.

[past rivet]

I’ll keep that in mind for the future! Thanks bee

[stray sphinx]

Also I'm a little angry at myself because I can feel myself being nerd-sniped into writing a babydev's first logical operator guide

Ty for all of your help

[stray sphinx]

On this note, I have more edge case: should Xor over 1 input should be True?

[fossil mural]

...no, the identity of xor is False

(false xor p) = p

(although if you actually meant over 1 input, rather than 0 inputs, then it should be whatever that one input is)

[past rivet]

Yeah over a single input, it should always return the input unchanged

[stray sphinx]

Tbh, info on both of these is good. I'm putting together a unit tests suite right now before re-organizing things.

[coral parcel]

Beware that there are two different (both reasonable) ways to generalize XOR to n>2 inputs. It can either mean "exactly one of the inputs is true" or "an odd number of the inputs are true".

[past rivet]

Ooh, interesting

[stray sphinx]

This is the exact sort of reason I'm asking.

Ty.

[past rivet]

Yeah I guess you can think of it as binary addition

[stray sphinx]

The odd number of inputs is a strange one to me.

[past rivet]

That’s the odd number of inputs version

[past rivet]

Except 1 + 1 = 0…

[stray sphinx]

It makes more sense when phrased that way

[coral parcel]

"Odd number of inputs" is what you get from interpreting XOR(a,b,c,d) as ((a XOR b) XOR c) XOR d.

[past rivet]

Right, so the odd number of inputs version is associative

Cause it’s binary addition, so ofc it is

[fossil mural]

and if you look at (True xor True) xor True, that's True, but "exactly one of True, True, True" is False

so "exactly one is true" isn't associative

[past rivet]

I see

[stray sphinx]

SKI machines...

[past rivet]

So then yeah XOR on an empty list should be false

Cause 0 inputs are true and 0 is even lol

Yeah sorry

[coral parcel]

(Fun fact: <=> is the De Morgan dual of XOR, so it is associative too, but nobody ever speaks about "the biimplication of a list of truth values").

[past rivet]

The de Morgan dual?

[fossil mural]

same way that p and q = not (not p or not q)

p <=> q = not (not p xor not q)

[stray sphinx]

in tired people: what comes out when you do the funny not parens thing

[past rivet]

Ah I see. It’s true precisely when an even number of arguments are!

[stray sphinx]

So I see it's associative, but does the reduction chain n-long biimp have practical uses?

It seems possible according to this:

https://web.stanford.edu/class/cs103/tools/truth-table-tool/

[fossil mural]

...no, (true <=> true) <=> true has 3 true arguments but is true

it's true if an even number of arguments are false

[past rivet]

I see

That makes sense

[fossil mural]

so the dual of xor, which is false if an even number of arguments are true

[past rivet]

Right I see, so that’s the correct sense in which to take the dual

[stray sphinx]

which is false if an even number of arguments are true
assuming you're not using the # true inputs != 1 version, right?

[fossil mural]

yeah this is with the associative version

[stray sphinx]

It seems like the viewpoint difference is about binary input / associativity vs being able to choose only one

There are compiler implications that make the first one interesting in addition to the binary addition.

That's what I was referring to with the SKI machines earlier.

🤔 Now I'm not sure which Xor is "right"

[digital sinew]

omg you can demorgan xor, you're a genius

[tawny juniper]

This (the picture below) is what i also got when i did a membership table of the expression (A\B)\C ⊆ A\(B\C).
This I belive would mean that (A\B)\Cis not a subset of A\(B\C) and when i paint the venn diagram I get this result, altho in my teachers notes it says

The market columns shows that if x ∈ (A\B)\C then x ∈ A\(B\C), i.e. (A\B)\C ⊆ A\(B\C).
Is it an error in the notes or have i done something wrong here?

[obtuse lance]

show your venn diagram

[tawny juniper]

One sec

[obtuse lance]

Maybe it helps or not for me to say it this way, but I think of (A\B)\C as you have A and remove elements of B in there and then you remove elements of C from there. So it's really removing A\(B U C). By contrast, B\C is taking all the elements in C out of B, and then removing those from A. So you still have any elements that were in C and A still in A(B\C).

[tawny juniper]

Yes i belive so, then it's probably an error in the notes correct

Sorry it took some time, tried to make it understandable

[coral parcel]

The light blue regions there can be ignored right? It's just the dark blue that represents the entire expression.

And comparing the dark blue regions sure looks like (A\B)\C is a subset of A\(B\C).

[coral parcel]

Actually I think there's an error in your right diagram: the middle region is in A but not in B\C, so it needs to be in A\(B\C).
This doesn't change the conclusion, though.

[obtuse lance]

was distracted, but yeah to draw in the missing piece here that tropo described for you

[tawny juniper]

Oh yes you are right, thanks!
Do you guys know how to, from the membership diagram, conclude that (A\B)\C is in fact a subset of A\(B\C). Is it that the columns are same (0) above the lined line drawn horizontaly in the middle?

[coral parcel]

It's that every 1 in the left red column also has a 1 in the right red column.

(Or equivalently, that every 0 in the right column also has a 0 in the left column).

[tawny juniper]

Oooh okey okey i understand now. Thank you both for your help! 😄

[tawny juniper]

Write p ∨ q only with this character |. I know de morgans in the beginning but after that is unfamiliar to me, the step where we go from AND to | (step 2 to 3). Is this any specific law or is it just to use common sense to figure it out?

[daring moon]

what is |

[tawny juniper]

It is everything except this. So for ex p|qwill be Everything is true except when p and q is true.
But now when i read the question again it is a made up connective 😅

[coral parcel]

It's called the https://en.wikipedia.org/wiki/Sheffer_stroke.

Outside logic textbooks it is often just called NAND.

[coral parcel]

"Use common sense to figure it out" should generally be preferred over remembering names of laws.

[agile magnet]

wait Sheffer stroke is real?

mf I thought this was something my discrete math prof made up for the introductory logic worksheets

[coral parcel]

(Except when your goal is specifically to investigate whether such-and-such particular laws are sufficient to replace common sense in a formal system).

[agile magnet]

I was a TA for that course for 6 semesters how did I not know it was real 😭

[coral parcel]

Well, define "real". As a logical connective, I don't think it's actually used as anything but a parlor trick and source of exercises.
On the other hand, in digital electronics, NAND gates are fundamental (together with NOR).

[agile magnet]

I meant real enough to have a wikipedia page

I just thought my prof made it up as a symbol so that people wouldn't immediately recognize it as NAND and people would have to think a bit more for exercises

[worn inlet]

is this the appropriate channel for discussing "graph math" for lack of a better description? i seek to understand how (sparse) matrices can be represented as graphs.

[agile magnet]

if it's a more advanced question, #combinatorial-structures may be better

but this channel is fine sure

[worn inlet]

i dont know how advanced it is. i am reading a paper relevant for my MsC, and am trying to understand some algorithm a bit better

i will try here for now. Is there some solid videos that visualize how matrices can be represented as graphs?

i would also be happy with any insight here. regarding graphs, this is concepts i have understood so far:

• a vertex is some dot. the vertex itself doesnt carry much information-
• an edge is the connection between 2 vertices, and this connection is the information

some graph is just a collection of vertices and edges!

please let me know if my understanding is outright wrong/ vague, or anything else

ill ask my supervisor next monday if graph theory is relevant

[dim trout]

Heya...
I have a question regarding proofs...
if A \triangle C = B \triangle C then A = B
Now I know this is true!!
however proving it has rather been problematic
I have got to this point in the picture

A,B,C are sets

Going down the route of proving that A is a subset of B and B is a subset of A is tidious and problematic

[weary tiger]

Suppose A is not equal to B. Without loss of generality you can assume there is a x in A that isn't in B.

If x is in C, will x be in A\triangle B? What about in B\triangle C?

[dim trout]

prove by contradiction??

@weary tiger In this case I have to do
Case: x in A and not in B
Case: x not in A and x in B?
then consider if x in C (and not in C) for both the cases?
this would mean I have 4 cases to consider right?

[weary tiger]

sure, altho the cases x in A and not in B is symmetric to the case x not in A and x in B

so you don't really need to prove them both if you know what you're doing

[dim trout]

This is because we are doing symmetric differences is what you imply?

[weary tiger]

no

[dim trout]

symmetric means identical to? (Sorry language barrier... my course is not in english)

[weary tiger]

Basically the proof of those cases is the same up to renaming A and B

[dim trout]

Ohhh

[weary tiger]

But you can do all 4 cases if that's confusing

[dim trout]

since we take into account that x in C and not in C therefore it wouldn't matter if it's in A triangle C or B triangle C ?

[weary tiger]

you need to show that A triangle C and B triangle C are different in both cases

[dim trout]

Okay so I need to do proof by negation and get a contradiction

OHHH okay
@weary tiger I had to look up loss of generality's meaning 😅
I got what you meant when you said I don't have to do the other case

[dim trout]

@weary tiger Sorry for a lot of pings
I just want a clarification
when x in C we get a contradiction since x in A and not in B; therefore x not in A triangle C and x in B Triangle C(and since we know that B triangle C = A triangle C so it's wrong)
in the case that x not in C we also need a contradiction ?

[weary tiger]

You also need to show that A triangle C and B triangle C are not equal in the case that x not in C, yes

[dim trout]

Okay

That's easily proven still since x not in B and not in C it wouldn't be in the XOR of them but x in A and not in C then it would be in A XOR C

Wow thank you a lot
I was stuck on this one for a while

[dim trout]

another question
I have a A a set, R and S are subsets of AxA and are relations of A
I want to prove that if R,S are reflexive then R\capS is reflexive
I took some x in A, and considered:
(a,a) in S and (a,a) in R --> this one is easy
and (a,a) not in S and (a,a) not in R, here I get the case where S\capR is empty which means it's not reflexive, then it would break the statement
or do I not need to take that into account since we know that a reflexive relation is for all a in A, (a,a) in R?

[dim trout]

<@&286206848099549185> tell me if I'm talking nonsense?

[coral parcel]

I don't understand what your point is in the part after "this one is easy". At that point you would just say:

Since (a,a) is in both S and in R, it is by definition in S cap R too. So (a,a) is in S cap R for all a, in other words S cap R is reflexive.
and then you're done.

[halcyon slate]

How do I show that $f: \mathbb{R^+} \to \mathbb{R^+}$ such that $f(x) = \frac {1}{x}$ is surjective?

[vital dew]

James

[dense nacelle]

It's clear this function is Its own inverse over said domain. Any function whose inverse is a function must be bijective (both injective and surjective)

[little prism]

a little more direct, how would you find an x such that for example f(x)=87?

how about f(x)=1946.7181...?

[stable shard]

You cannot unless you have the inverse of the function

or you can say x= g(1956.7181...)

if g(x) is the inverse of f(x)

[coral parcel]

Note that the question specified exactly which function f is, so we do have its inverse.

[thorny hollow]

Why in a reflexive relation aRa such that a in A = {1, 2, 3} it doesn't have the ordered pair "(1, 3)"?

[fossil mural]

well a reflexive relation on {1, 2, 3} could have (1, 3) in it

but it doesn't have to, {(1, 1), (2, 2), (3, 3)} is still reflexive

because for each a in A, (a,a) is in R

[quasi mantle]

for every Kn^2 if N>=2 then there exists at least on graph that K3 is red or KN is blue

I got it right but someone told me its wrong

[violet dawn]

i wanted to check my understanding for three things related to functions:

1. if A is a non-empty set, f: A -> null (where null is shorthand for the empty set)

no function f exist for this mapping because you cannot assign any elements in A to elements in null

2. if B is a non-empty set, f: null -> B

one function exist for this mapping, the null function because it’s vacuously true that all elements in null map to an element in B, since null contains no elements

3. for f: null -> null

there is one function that satisfies this mapping, the null function, because it’s also vacuously true

is that understanding correct?

[brave rock]

Yes

Nb 3 follows from 2; you didn’t need the nonempty assumption

[deep vector]

any hint to proof this pls?

[violet dawn]

Thanks @brave rock

[elder oasis]

bro did u solve this

i feel like it is a proof by induction bc of the sigma

there is no way to algebraically do this right?

cause with proof by induction i can boil the quesiton down to sigma_n f(i)g(i) = sigma_{n+1}=f(i)

[elder oasis]

https://www.desmos.com/calculator/vhwuwcin58

i think the whol eidea of my proof is that given p(n) = g(n), we know that p(n+1) = p(n)f(n) = g(n)f(n), so if we can show that g(n+1) = g(n)f(n) then g(n+1) = p(n+1)

this is true but i can't show it. just need to simplify this sigma if even possible:

https://www.desmos.com/calculator/empciie1dl

[elder oasis]

wtf thats so simple

yea proof by induction failed btw

[solar marsh]

it is easy to keep in mind the basic identities about additions: Vandermonde and hockey

[elder oasis]

def will look into that

[solar marsh]

https://en.wikipedia.org/wiki/Hockey-stick_identity
https://es.wikipedia.org/wiki/Identidad_de_Vandermonde

[feral saddle]

Does anyone know a formula for $\sum_{S \subseteq X}{\lvert S\rvert}$?

[vital dew]

robin goodfellow

[feral saddle]

nvm, it's $\frac{1}{2}\lvert X \rvert2^{\lvert X \rvert}$

[vital dew]

robin goodfellow

[solar marsh]

Let ( X = [n] ). We can count the number of pairs ((a, A)) where ( a \in A \subseteq X ) in two different ways:

First, for each subset ( A \subseteq X ), there are (\left| A \right|) elements ( a \in A ). Therefore, the total number of pairs is (\sum_{A \subseteq X} \left| A \right|).

Another way to count these pairs is to note that, for a given element ( a \in X ), there are ( 2^{n-1} ) subsets of ( X ) that contain ( a ). Summing over all ( a ), we have (\sum_{a \in X} 2^{n-1} = n \cdot 2^{n-1}). Therefore,

[
\sum_{A \subseteq [n]} \left| A \right| = n \cdot 2^{n-1}.
]

[vital dew]

Kevin

[solar marsh]

Here is an algebraic proof.

[true iris]

hey someone can help me with the two last questions please

[spare slate]

Ig take $I_n \approx I_{n+1}$ for sufficiently large $n$ in your result from (1)

[vital dew]

Civil Service Pigeon

[true iris]

okay i seeee

because i thought to do In/1/4n and inject the in result from the question 1 and make limit result 1

but i don't have idea for the last

[obtuse lance]

<@&268886789983436800>

[umbral notch]

hi guys im working through a textbook right now and im a bit unsure on how to approach this if anyone could give me a quick hint so i dont go in the wrong direction id appreciate it since there is no solution manual to the book that i have access to (btw [x]_N represents the N truncations of x in this context)

[coral parcel]

Hmm, I'd say something like: If you just add k digits then you get some result. If you include more digits from the right, eventually there may be a carry into position k, but once there is a carry, it will stay there if you take even more digits, because taking more digits cannot make the sum of the rest of the digits smaller.
So either there's never a carry, or there's always a carry from some point onwards, and in each of these cases, the kth digit will stay eventually constant.

[true iris]

you have an idea pls ?

[true iris]

anybody can help me pls

[vale cairn]

How are you defining the truncation when there are things like 0.99999... and other non-unique representations

[vale cairn]

Note that I_n + I_(n+1) <=2I_n <= I_(n-1) + I_n

À cause de 2)

Et utiliser 1)

[deft crystal]

found this channel today, is it a good place to start learning discrete math or are the examples too simple? https://www.youtube.com/@RelativelyPowder

[obtuse lance]

Even though I don't think the examples are too simple, this doesn't appear to be a reliable source to start learning from.

[deft crystal]

yeah i just need somewhere with lots of examples since most channels i find just explain the concept and do like 1 to two proofs which isnt enough for me to really understand it. Goind down pretty far to find a place like that, any suggestions?

[fluid bluff]

I think Discrete Mathematics is a hard subject to explain to others. Maybe because it's so fundamental and logical to everything in Mathematics

You can't rush it. Have to slowly instill the basic logical concepts.

It also fits the name, Discrete. Carefully calculating and and separating stuff

[true iris]

je parle de la question 4

[quasi frost]

Pour la question 4, il faut utiliser la relation de la question 1
$$I_{n+1} = \frac{1}{2n+1} - I_n$$

Or $I_n + I_{n-1} = \frac{1}{2n-1}$

Donc $I_{n+1} = \frac{1}{2n+1} - \frac{1}{2n-1} + I_{n-1}$

$I_{n-1} + I_{n-2} = \frac{1}{2n-3}$

Donc $I_{n+1} = \frac{1}{2n+1} - \frac{1}{2n-1} + \frac{1}{2n-3} - I_{n-2}$

Ainsi de suite jusqu'à arriver à$I_0$

[vital dew]

un_decorateur

[tawny juniper]

Im learning Stirling numbers of the second kind, and I used this recursive formula that was showen in videos saw on the topic:

S(m, n) = S(m-1, n-1) + nS(m-1, n)
To then answer questions from the past exams im studying I use this to go from S(m, n)to one base case S(m, 0) = S(m, m) = 1.

In my teachers notes however and new videos i saw, they use another formula

S(m, n) = S(m, n-1) + S(m, n)n
that I am not sure how the recursion work.

Is any of these better to use in a certain moment or are they interchangable?

[true iris]

je vois ce vous dite donc je doit faire une récurrence je sais pas comment procéder

[agile magnet]

that second one is just a typo

I mean the recursion would never halt

[solar marsh]

Hello! I am interested in learning about probabilistic counting. Could someone recommend me some bibliography please?

[thin comet]

David Patrick has a good introductory book,
Introduction to counting and probability

[solar marsh]

I appreciate it very much! 😊 I'm going to look at it

[quasi mantle]

Can someone explain to me why this holds , Usisng combinatorics

[terse wyvern]

use induction

[thin comet]

LHS is the sum of binomial coefficients for (2n+1) choose k
Consider a set of 2n+1 items
You can split this into two groups: a group of 2n items and 1 extra item
For each subset we choose, we have two independent choices for each of the 2n items and two choices for the extra item
This gives us 2^(2n) * 2 = 2^(2n+1) = 4^n total possible subsets
From the binomial theorem,(1+x)^m = sum of (m choose k) * x^k for k=0 to m
If we put x=1 in this, we get 2^m = sum of (m choose k) for k=0 to m
m = 2n+1 here, which gives the LHS

[tawny juniper]

Sorry i made that typo, it should be S(m+1, n) = S(m, n-1) + S(m, n)n.
And it is used like this in the questions i have:

Is it better in this situation to use this formula?

[coral parcel]

The sum is the number of subsets of a set with 2n+1 elements that have at most n elements.
That's exactly half of all the subsets, because the complement of a set with at most n elements has at least n+1 elements, and vice versa.

[agile magnet]

what is your question?

[timber barn]

I solved it

nvm

[foggy sentinel]

I finally managed to pass my discrete math exam. 😭 Sincerely thank you so much for your patience and willingness to help me. I truly had none to ask, no teacher, no friends, unironically none to talk to. I’m truly grateful for you both @frigid ocean @harsh frost and you are unironically helping me achieve and better future. Thank you ❤️❤️❤️

||we still gotta finish mult var calc tho hehe||

[harsh frost]

Awwww, well done always a pleasure to do whatever I can

[harsh frost]

[deep vector]

help pls

[ember cypress]

Can someone please eplain this to me

[cerulean wind]

if n <= k, then we are done.

assume n > k. then n - 1 >= k.
let n/k = N + a/k for some integer N and 0 <= a < k
now (n-1)/k = n/k - 1/k = N + (a-1)/k

if a > 0, then floor((n-1)/k) = N so
ceil(n/k) = N + 1 = floor((n-1)/k) + 1

if a = 0, then ceil(n/k) = N and floor((n - 1)/k) = N - 1 so
ceil(n/k) = N = (N - 1) + 1 = floor((n-1)/k) + 1

[frigid ocean]

Congrats!

[tawny juniper]

Hey, i have a question about graphs.
The question is (roughly translated):
You have 5 nodes, how many loop free graphs with undirected edges can you make with 3 edges?
I made this solution

Choose next node   : (4 over 1) = 4
Choose next node   : (3 over 1) = 3
Choose end node    : 1 (which is the start node)
Total graphs: 5 * 4 * 3 = 60
BUT! without direction makes it 60/2 = 30 possible graphs.```
This is the solution example:
```Possible vertexes for an edge: (5 over 2) = 10 
Choose 3 of these: (10 over 3) = 120 possible graphs.```
I fully understand the solution, altho I dont understand why my solution is wrong... Could someone help me to udnerstand that?

[agile magnet]

This reads like you're trying to count the number of triangles you can make in a set of 5 vertices

[ruby zephyr]

Let $a<b\in \mathbb{R}$. Find all $n\in \mathbb{N}$ such that $\lceil an \rceil = \lfloor bn \rfloor$.

[vital dew]

Casiel368

[ruby zephyr]

I'm starting to suspect that this does not allow for a closed analytic answer but I might just be missing something

[cerulean wind]

think about how scaling the interval (a, b) by an integer n works geometrically

what condition on (an, bn) is required for ceil(an) = floor(bn)?

[ruby zephyr]

Actually I followed the inverse path to get to this question haha

The condition is that there is a single integer between them

[cerulean wind]

yea exactly

[ruby zephyr]

To me that is actually a harder problem. How would you approach that?

[cerulean wind]

would you mind clarifying?

not sure what problem you are referring to

[tawny juniper]

Hey, im doing reccurence equations and for the assumtion for the particular solution I have learned these once.
But now I've come accross one that is, if the inhomogenous part is ex C*2^n, the assumtion then will be e*2^n. Could someone explain where this ecomes from?

[ruby zephyr]

To me, the formulation "Find all n such that (na, nb) contains exactly one integer" is harder than the equation I asked

[cerulean wind]

they are equivalent problems

[clever kite]

Is this a valid proof?

I'm still new to this so I want to make sure I'm not making any bad habits

[spare slate]

this doesn't rlly make any sense

By this logic, you could “prove” that there’s no smallest positive integer (which is clearly false)

The typical way to go about this is to ||consider a rational number q and consider dividing it by something||

[spare slate]

Remark: ||this is pretty similar to the way used to prove that there's no smallest positive rational number||

[clever kite]

Alright I'll try going about it again

If I really need to I'll look at the spoilers

I'm also a bit of a fool haha

I'm realizing my first sentence should've been making the assumption there was a positive real number that is less than every real positive number

It's literally a proof by contradiction

How about this?

[clever kite]

Yeah I know the first part is unnecessary I just like to write the problem down

Thanks for the help though!

I'll definitely work on making my proofs more concise as well

[cerulean wind]

the reason this is wrong is because you assume that x > y, but then assume that x is the smallest. you have contradicted yourself in your own proof. the faulty assumption is that x is the smallest, given that you already assumed x > y

[spare slate]

(This is commonly known as the “assuming what you’re trying to prove” error)

[clever kite]

Yeah that definitely would not be helpful haha

[hard citrus]

not sure if it's the right place to ask but it involves graph theory
i have an assignment in python of creating a function that finds the maximum matching of a bipartite graph, we haven't learned about graphs at all so im learning this at the moment on one leg
is the following a correct understanding of maximum matching?
i'm given the set of connected nodes {(1,3),(2,3),(3,4),(4,5)} is the pic the right representation of the graph?
and from here is the maximum matching 3? since you have 3 edges that go to a single node?

[agile magnet]

The graph drawing is correct

A matching is a set of edges in the graph such that all the end points of the edges are disjoint (so no repeated vertices)

So you cannot have a matching consisting of edges {(1, 3), (2, 3), (4, 3)} as the vertex 3 is used more than once

A maximum matching is of course a matching of largest cardinality

[solar marsh]

this is a maximum matching

The number of edges in a maximal matchingt is bounded by the number of vertices on either side of the bipartite graph

[hard citrus]

yeah i got it eventually, now i have different problems, this HW is too hard lol

[hard citrus]

that one was the first out of 4 in a work i need to do in python, problem with the first question was that we didn't study graphs at all.
now i need to find the minimal distance between two permutation matrices, where the distance d(C,D) is defined as D = X.C.Y where X, Y are some product of A, B, A^-1, B^-1 (for example A.B^-1.A.C.B.B.A^-1)

those problems are just tedius and hard

[hard citrus]

anybody know of the n rook problem with forbbiden positions?

[short nexus]

Where you are playing on an nxn chessboard?

[hard citrus]

didn't understand your question, here's the complete question

I've got a HW question in Python where I need to create a function that given an edge list which I translate into an incomplete chessboard and a number of k rooks and the function will give me the number of possible ways to place the k nom-attacking rooks on the board B (which I created from the edge list).

the translation of the edge list into a chess board is irrelevant to this question here, it's just to give background, I saw this problem is actually a known problem and that it usually uses generating functions which I didn't learn, but then I saw a video that gave me some ideas but I still have some questions.

so first of all his video talks about an NxN grid while mine is an NxM grid which throws off some of the calculations, the number of permutations possible in such a (complete) board will be (min{N. M})! at first I thought about adding rows/columns to get back an NxN board (where N would be the max{N, M}) but it doesn't feel right, just now I thought about actually "trimming the board" and get back some MxM board (where M would be the min{N, M}) and then use WLOG (still haven't fully thought about it but the idea is forming), or maybe it's just okay to leave it just NxM and do some different math which I didn't figure out yet.

now secondly let's say the matter of size of the board is fixed, I don't fully understand how to compute those r_k he talks about in the video (which are the number of ways of placing k rooks in the forbidden positions) since in the program I need to write those forbidden areas can be sparse and spread around in a checkerboard pattern or clump around and everything in between.

if lets say in row 1 (with length of 8), I have forbidden tiles in columns 1, 4, 5, 7, and in row 2: 12, 16, how do I calculate the number of possible places for k rooks?

so to summarize currently I have 2 mathy problems, 1. how do I deal with the NxM board? and 2. how do I calculate the permutaions for such an NxM board with some forbidden positions?

and this is the video https://youtu.be/zElN2mvD3z0?si=q4cvWWCN7YTvqmnB

[hard citrus]

in how many ways are there to arrange k non-attacking rooks in an NxM chessboard? k is an integer form 1 to min(M,N)

[short nexus]

Ok I took a minute to think about this, and I don’t know how the program would work, but here it goes.

So we already know how many ways we can place n rooks on a nxn chessboard, namely n! Rooks. You have k rooks. So in how many ways can we make a kxk chessboard? You have M rows, and you want to choose k (binomial coefficient). Similarly, you have N rows and you want to choose k. And for each one of these configurations there are k! Possible moves

Does this make sense?

The “mini chessboards” that you are making should lead to disjoint configurations. This is all intuition btw. I don’t know if it is right.

[hard citrus]

is the following statement correct?
the number of ways to arrange k non attacking rooks in an NxM board with forbidden positions (we'll call this target)
is equal to the number of ways to arrange k non attacking rooks in an NxM complete board (with no forbidden position,
we'll call this complete) minus the number of ways to arrange k non attacking rooks in the forbidden positions alone
(we'll call this missing) so we have target = complete - missing

[vocal bane]

Can I have some help with a discrete math hw? It’s a bit so we might have to take it in dms

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[rugged dock]

Can i post my combinatorics problems here

[spare slate]

Yeah

[rugged dock]

Alr thx

[halcyon dock]

What is a matching

[short nexus]

This looks right to me

[hard citrus]

anyone here strong in generating functions and can help me? i haven't learned generating functions but the problem I'm doing requires them (or some other way i couldn't figure out) and i need help in constructing the gf

[little prism]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[hard citrus]

This is the question, I'm now trying to approach it from a generating function approach

It has to do with rook polynomials

[hard citrus]

I've "reduced" the initial problem into just finding the number of ways to arrange k rooks on an NxM board (n rows, m columns).
I have the dimensions M,N I have the list of forbidden tiles, I just need the math and logic to calculate it now.
On math stackexchange someone said it can be solved recursively with a generating function in the following way

You can find the generating function recursively, working one square at a time. For any grid $G$
, consider the leftmost white square in the topmost row. (Other conventions are possible and give equivalent results; what's important is that the square in question, when removed, doesn't change which remaining pairs of squares attack each other.) Let $H(G)$ be the grid formed by removing that white square and all the squares it attacks. Let $K(G)$ be the grid formed by removing just that white square. Then
$$f_G(x)=x\cdot f_{H(G)}(x)+f_{K(G)}(x)$$
The recursion terminates when $G$
is the empty grid, in which case $f_G(x)=1$

[vital dew]

horizon2.0

[hard citrus]

now I'm trying first to understand why it's right (if it really is) and then how to implement it into python

[river root]

My first attempt a a proof for real analysis part of basic set theory

Is this proof correct and if so what could be better/compacter and if not correct where is it wrong

[short magnet]

is there any good uni course available online for this topic?

[proud haven]

Can you explain how you got from the 4th line to the 5th ?

[fallen jetty]

trying to solve question b from the first and second image
The answer for first image, where A(x) = System error x have been detected, B(x) = Directory x can be opened in file system, C(x) = File x can be closed $$\exists_x A(x) \implies [(\forall_x \neg B(x)) \land (\forall_x \neg C(x))]$$
The answer for the second image, where A(x) = Alert x is active, B(x) = Message x is queued, and C(x) = Message x is transmitted
$$\exists_x A(x) \implies \forall_x (B(x) \implies C(x))$$
I don't understand why it is $\exists$ for A(x) in both of the solutions instead of $\forall$, as I thought "Whenever" or "When" means the all times that x is occurring

[vital dew]

Padoru Padoru

[fallen jetty]

I believed that "forall" (condition) means that the condition is always true, and "exists" (condition) means that the condition is sometimes true. So I thought "whenever" and "when" means at all times a system error is detected, which fits "forall" more

Looking back, I'd guess "Whenever" and "When" is more for the "imples" rather than "forall" or "exists". But I am still confused how it's "exits" for the A(x)

[river root]

Uhhh no I cannot I just based it on logic… Is there a mathematical way I should have come to that conclusion?

I just based it on the first case and the second case with either set B or C

[short nexus]

This is a minor thing, but I think the $\subset$ (proper subset) should be $\subseteq$ (subset).

Unless you have been taught using $\subset$ (subset) and $\subsetneq$ (proper subset).

Idk just something to pay attention to. You should reach a contradiction if you try to prove one is a proper subset of the other because that implies there is an element in one that is not in the other which contradicts the equality.

[vital dew]

original goober gamer (OGG)

[odd heart]

I'd just like to add that people very often do use \subset to include the trivial inclusion (i.e. A \subset A); it's not an error, it's just that the usage of this symbol isn't entirely consistent

[sand pelican]

are these from kenneth r?

[fallen jetty]

Discreet Mathematics and its Applications by Kenneth H. Rosen

[fathom olive]

Is this correct?

[errant bear]

it is correct

the problem is asking for the sequence of sums

[quasi yacht]

does "family of X" like "family of sets" basically just mean an information collection of X? where we dont really have a formal structure or grouping of X?

[ember obsidian]

a family of sets is just a set of sets, typically indexed. without further context there is not much to do other than the usual set operations, but if we have a family of subsets of a space (group, vector space, topological space etc) then there may be more meaningful things to do with it

[hot prism]

is this the channel I would get help discrete mathematics for computing ?

[radiant gale]

Given a (endo-)function $f : A \rightarrow A$, if its left/right inverse exists, then such inverse is equal to its right/left inverse (respectively). Is this correct?

[vital dew]

luke1337

[radiant gale]

Maybe I've missed something, but an endofunction should be surjective iff it's injective, which, in together, implies its invertibility.

[ember obsidian]

its true and the proof only requires clever compositions

write $f_L\circ f=\id_A$. work with $g=f\circ f_L$ and $g_L$ to show $g=\id_A$

[weary tiger]

This can fail for infinite sets

[vital dew]

RokettoJanpu

[radiant gale]

even with AC?

my set theory is rusty so needed some bit of sanity check :/

[weary tiger]

Yes. In fact, with AC, if a set is infinite, there is always a counterexample for it. Without AC there can be some infinite sets for which injective implies surjective

[radiant gale]

like, countably finite and above?

[weary tiger]

Yes, it shouldn't be difficult for you to find a counterexample

[radiant gale]

awesome, so i guess i can at least assume it's true for finite sets

should be trivial to prove too

[weary tiger]

It is true for finite sets

(It is true for Dedekind-finite sets, and without AC there can be infinite Dedekind-finite sets)

[ember obsidian]

theres no need to consider cases if you just use compositions

the gist is ||semigroups with left identity and left inverse have right inverse||

[weary tiger]

As stated this is not true

[ember obsidian]

oh i think im forgetting ||left identity||

[weary tiger]

I'm not quite sure what you're trying to say

It's still not true

To talk about inverses you need an identity

So you need a monoid not a semigroup

And there are monoids wirh left-invertible elements which are not right-invertible

[ember obsidian]

im taking a semigroup with left identity and left inverses, then it has right inverses (wrt the left identity)

[weary tiger]

Oh you mean every element has a left inverse. I think that works then

[ember obsidian]

yep mb that wasnt clear earlier

[radiant gale]

Well if it works at algebraic level I guess I need not care about cardinality

Thanks

[ember obsidian]

yep as i said you just need clever compositions

[neon harbor]

To be clear, if an endofunction has both a left inverse and right inverse, then they are equal, but it may not have both

[neon harbor]

Consider x -> 2x on the integers for example

[radiant gale]

Right, which is why I excluded noninjective/nonsurjective case explicitly

Oh, wait

I'm not even sure we're talking about the same thing at this point

[neon harbor]

I mean it might have one but not both. It might be surjective but not injective and vice versa

[radiant gale]

So (• × 2) serves as the counterexample here

[neon harbor]

Yep

[rose musk]

I solved a and b, but I can't solve c

[drifting brook]

kinda getting stomped by my discrete 2 class anyone have resources for practicing algorithm problems

& determining the big O of a function

[shadow lion]

what have you tried?

[next ocean]

guys i got a question

prof has told me find another way to prove this statement.

any idea ??

[rose musk]

nvm, I solved that. thx

[shadow lion]

well done!

[rose musk]

I can only think of those two ways.
You can take contrapositives and use modus tollens or take contrapositive of the final implication you get. But that is just a longer way of doing the same thing.

[pearl thorn]

Hi, is it okay to ask about graph theory here? I can't find a more appropriate channel 😅

We defined a subgraph as this:

Graph G' = (V', E') is a subgraph of graph G = (V, E) if

1. V' ⊆ V
2. E' ⊆ E
3. E' = E intersection (V' x V')

This definition makes sense to me. However, we had a test and the professor says that "A subgraph can be formed by removing a single node" is a false statement. What's false about it? The only reason I think of is "you still need to remove the node's incident edges from E' " but if the node is removed, the edges can't possibly stay in E since they're not well-defined anymore, and plus the third point of the definition derives E' from a given V'. Is the prof just bikeshedding or am I missing something?

[brittle thorn]

Could someone please help me understand this underlined part. The u intersection!

[next ocean]

yup

[past rivet]

Ah, so if you have a set of sets, you can take the intersection over all of them

So if $S$ is a set of sets, then you can form the set $\bigcap S$

[vital dew]

Pseudonium

[past rivet]

Where $x \in \bigcap S \iff \forall s \in S, x \in s$

[vital dew]

Pseudonium

[past rivet]

But yeah this is a nice theorem, it shows that the naturals are the initial algebra of 1 + X

[rose musk]

anyone here completed or currently reading the book Discrete Mathematics and it's applications by Kenneth H. Rosen ?

[heady oak]

Let’s say I’m looking at the fibanocci sequence

How do I determine at which step this reaches the number 377 (say) ?

[raven forum]

log 377 / log phi + 2?

phi being the golden ratio ofc

That is a close approximation since at lower values, the ratio is obviously not exact

+2 is there coz we got the extra 0,1,1 at the start

[raven forum]

Consecutive terms of the Fibonacci sequence are observed to be in the golden ratio especially deep into the sequence. So you can approximate the whole sequence as a GP in a broad sense

[heady oak]

The orginal question I have is a bit different

I have this recurrence, F(n) = 3F(n-1) -2

I need to find for which n it reaches say 500.

[raven forum]

I'd still model it as a GP. But you still have to verify that the number does exist in the sequence

I'd say the model works coz the error in F(n+2) is gonna be 3(3F(n)-2)-2 - 9(F(n)) so, -8 which is tbf very small at large n

So if you have a guarantee that the given number is a part of the sequence, just make it as n = log F(n) / log(F(1))

[heady oak]

It won’t reach 500 i suppose

Generally won’t reach any even number ig

[raven forum]

depends on the initial values

[heady oak]

Oh sorry

F(1) = 3

[raven forum]

if you start with an odd, it would be odd always

[heady oak]

That’s the base case

I didn’t say that earlier mb

[raven forum]

or if you start with even, always even

[heady oak]

yes

[raven forum]

Ohh, okay, then yeah, no 500 here

[heady oak]

I can do this analysis if n odd?

Or is there a better way to determine the possibility of being in the sequence?

[raven forum]

If your formula reduces to some non iterative function, then you can verify it. But if it stays iterative, then you kinda need to calculate it all the way

(Or collatz wouldnt have been such a pain)

[heady oak]

I see

how cool

[raven forum]

Wait, Im dumb. Your formula does reduce to 3^(n-1) * (F(1) - 1) + 1

[raven forum]

I just realized coz this

so you can exactly find out n by solving for the roots of equation F(n) = 0

[lean rover]

How does one even make an isomorphism function for this? In the solution they say start with an arbitrary assignment and then work your way they. The arbitrary assignment they picked ended up "by accident" being a correct one so I have no clue how to even think and solve this? I tried starting with a=0 but then saw it doesn't work but it feels like too much work. Isn't there like an easier way?

[terse wyvern]

great news! the petersen graph is vertex transitive so any choice made and the corresponding deductions should work

you can set a = 0 and set b, e, f to be adjacent to a and adjust those guesses if there's an issue

[wary scarab]

For an infinite cluster to exist, the expected number of open edges per vertex must be greater than 1 in a branching process. can I use this and solve he problem?

[dim trout]

I need to find a onto and one-to-one function from [0,1] to [0,1) but it seems impossible...
I know they have the same cardinality

[weary tiger]

Hint: Can you find a subset of [0,1] of same cardinality as N?

[dim trout]

can we??

cardinality of N is Aleph0
cardinality of [0,1] is Aleph

[weary tiger]

You are the second person I've met who calls the cardinality of the continuum Aleph

[dim trout]

we didn't learn continuum

[weary tiger]

What does Aleph mean to you?

[dim trout]

|R| = Aleph

[weary tiger]

That is the cardinality of the continuum

[dim trout]

OH

[weary tiger]

We can

|N| < |R|

Do you know what it means for |N| < |R|?

[dim trout]

There is a one-to-one function from |N| to |R|

[weary tiger]

Are you aware that |N| < |R|?

[dim trout]

Yes

we know this

|N| is aleph_0
just like |N_even|

[weary tiger]

Let f : N->[0,1] be one-to-one then

Its image is a subset of [0,1] of same cardinality as N

Is that okay so far?

[dim trout]

okay

[weary tiger]

We can even be more explicit, it is easy to find an explicit example

Let f: N -> [0,1] given by f(n) = 1-n/(n+1)

[dim trout]

we gotta say that it's N+

we have 0 in N

but it's fine

|N+| is the same as |N|

[weary tiger]

Let's do this instead

[dim trout]

Okay

[weary tiger]

Do you know of any bijective function from N to N^+?

[dim trout]

f(x)=x+1

[weary tiger]

Yeah

Consider the following function from [0,1] to [0,1)

If x=f(n) for some n

Send x to f(n+1)

Otherwise keep x fixed

Can you see that this gives a well-defined bijection?

[dim trout]

wait... what

so you want to send f(x)=x+1 to f(n+1)=1-n/(n+1)

[weary tiger]

No

[weary tiger]

f(n) = 1-n/(n+1) as in here

All that really matters is that f is an injective function from N into [0,1] such that f(0)=1

[dim trout]

Yes

[weary tiger]

Does it make sense now?

[dim trout]

okay

so if we do 1-0/0+1 it's 1
okay

but we need to define the function from [0,1] to [0,1)

[weary tiger]

I did

Define g from [0,1] to [0,1) as follows

If x=f(n), let g(x)=f(n+1)

Otherwise, let g(x)=x

[dim trout]

Wait let me write this in lyx...

so f: N -> [0,1]
g: [0,1] -> [0,1)

we just need to prove that they are bijective?

which is easy to do for F since we know that
|N| < |R|

[weary tiger]

f cannot bijective, it just needs to be injective

g(x)=f(x+1) does not type check

[dim trout]

oh

This is g

[weary tiger]

f(n+1) not f(x+1)

[dim trout]

but n \in N?

So basically for all n that is in [0,1] we do f(n+1)
otherwise we do n?

[weary tiger]

No..

For every f(n) (which is in [0,1] by definition), you send it to f(n+1)

For every other x you keep it fixed

[dim trout]

are we allowed to do that?

[weary tiger]

The idea for this is you have a copy of N inside of [0,1] and shift it to the right, that way you get a bijection that sends nothing to the first element

[weary tiger]

Why wouldn't we?

[dim trout]

would it be surjective?

g not f

g needs to be bijective

I'm sorry, there is a language barrier for me... that's why I'm not understanding

[weary tiger]

It is surjective onto [0,1)

For every f(n) with n>0, f(n-1) gets mapped into it

f(0)=1 is the exception, and that is good

And for the x's that are not of the form f(n) for some n, they stay fixed

[dim trout]

wait wait
so if x \in f(n) (which means [0,1]) we keep it as x
if x is 0 we get 1 if we do f(0)
if x > 0 we do f(n+1)

[weary tiger]

f(n) is not a set

Do you mean if x = f(n) for some n?

And we don't keep those as x

We send f(n) to f(n+1)

[dim trout]

Yes

[weary tiger]

f(0), f(1), f(2),... are just certain points of [0,1] that we choose (and we choose f(0)=1)

All we are doing is sending f(0) to f(1), f(1) to f(2), and so on

And keeping the remaining points of [0,1] fixed

[dim trout]

Okay

so for example 0.pi is not in f(n) for any n

so we keep it as such and not do f(n+1)

[weary tiger]

Not sure what you mean by 0.pi, but if you mean an irrational number yeah (assuming we are using the same f we used before)

[dim trout]

I mean 1/pi

[weary tiger]

Yeah

[dim trout]

okay wait

g(x): [0,1] -> [0,1)
This is what it should look like

wait let me fix it

like this

[weary tiger]

Yeah

Note that this is only well-defined because f is injective

So if x=f(n) for some n, that n is unique

[dim trout]

Yes as you said, f is injective

unfortunetaly we need to prove it, so I'll do that

Okay

Thank you so much

[deep vector]

Show that if on a disk with 50 squares along its perimeter you place 25 tokens marked with a zero and 25 tokens marked with a one, it is always possible to find a token that has two adjacent tokens marked with a one.

help pls

[clever sail]

🐦🕳️

Pigeonhole principle

[deep vector]

Could you give me a suggestion for implementing this please?

I really appreciate any hints

[clever sail]

think about what such an arrangement that satisfies this condition would look like

0011001100...1 for example

this is around the circle so the last number is next to the first number

you need to prove that if you try to do this then somewhere you must have 101

or 111

not sure how much more i can give without completely giving the question away but that should be enough to get started

[deep vector]

I have come to the same reasoning, but it is not enough for me to write a formal proof.

[clever sail]

try a smaller case where its easy to look at each case by hand like 5 0's and 1's each and 10 total or something and then try to generalize the pattern of whats going on

this is something that's important to wrestle with, it'll help you build the skill of capturing your intuitive ideas about some situation into a mathematical framework you can work with

[clever sail]

also look into this and see some other examples of it

those will give you an idea of what that process of translating the problem looks like

[deep vector]

I was able to finish the proof, thank you so much for your words. they really helped me.

[clever sail]

No problem!

Good job

[clever kite]

Do you guys have any tips for getting better at proofs?

Or is it just doing a lot of practice

[shadow lion]

it's a whole lot of practice

you will trip, stumble, scratch your knee a lot along the way

and that's okay!

what matters is that you pick yourself back up, don't get discouraged, and keep working on it

[clever kite]

Thank you for the encouragement, I definitely need it haha

Got pretty discouraged after starting on this hw

[shadow lion]

hey, it happens!

just keep working on it, and you'll find yourself improving in no time

[clever kite]

Is this a valid proof?

[little prism]

no. you are basically assuming what you want to prove. irrational numbers arent automatically linearly independent over Q, for example sqrt2 and 2sqrt2 are clearly lin dependent

you havent used what sqrt2 and sqrt3 actually are (namely that they square to 2 and 3)

[clever kite]

Hmm ok

Yeah the linear indep thing was just something I thought I vaguely remembered

I'll try again tomorrow, I've stayed up till 3am now

[velvet lynx]

if $a \times -1 = -a$ in a field, is $-1a$ over $\mathbb{F}_p$ equal to $p - a$?

[vital dew]

somehybrid

[little prism]

yes. -a=0-a=p-a because 0=p

[velvet lynx]

right, thanks

just wanted to clarify that

was looking at the wikipedia page for fields :P

[velvet lynx]

does a finite field need to start from 0?

[weary tiger]

What do you mean by "start"?

Every field contains an additive identity which we usually denote by the symbol 0

[velvet lynx]

uh

[velvet lynx]

that, ig

[lean rover]

It says that this graph has 4 regions. Isn't it wrong tho? It has 3 regions if my understanding is correct.

[odd heart]

The outside also counts as a region

[mellow rose]

hello, for ii can I instead proof if x = 1, then 1^2 + 2 = 3(1)

so 3 = 3 and hence if x = 1 then x^2 + 2 = 3x?

Im assuming Im allowed to build of i which already proved the forward implication, so Im just focusing on the backward implication

[weary tiger]

For the backward implication you also need to show that if x=2 then x^2+2=3x

Not just for x=1

[mellow rose]

oh but I was thinking since it was an or condition I can just prove either one

[buoyant yoke]

can someone help me with this uestion

idk why its wrong

[mellow rose]

for a's answer set your smallest element is wrong

[buoyant yoke]

what do you mean?

[mellow rose]

mb I corrected it

[buoyant yoke]

why isnt it 2?

Ohhh

the smallest would be 4 right

[mellow rose]

ye

[buoyant yoke]

ok what about B

[mellow rose]

max element should be correct

for b your elements in the answer set are outside A

[buoyant yoke]

why did it have to be within A

it just said f inverse

also if it were in A wouldnt both be DNE

[mellow rose]

oh yea mb 🤡

[buoyant yoke]

so why is it wrong

[mellow rose]

not really sure 😓

[buoyant yoke]

😭 😭

can anyone help with this please

[sand pelican]

Sometimes people says "Every nonempty set of nonnegative integers has a least element.", sometimes "Every nonempty subset of the set of positive integers has a least element."
I need help on seeing how they relate to each other. Thanks a lot

[odd heart]

they're equivalent

[sand pelican]

Another document that I found says "Every nonempty subset of the natural numbers is well-ordered."
Do the natural numbers here include 0 or not? I want to know why sometimes 0 is included and sometimes not

[odd heart]

Well-ordered in the standard ordering, yes. And as for whether or not we include 0 in the natural numbers, it's basically a matter of convention and there isn't an universally agreed upon version. I prefer to include 0 because it's nice to have the neutral element in your set.

In any particular text it's best to check whether the author considers 0 to be a natural number.

If the author doesn't explicitly say it, it probably doesn't matter.

[sand pelican]

For these two statements, historically, which one follows the other?

[fossil mural]

i think you would probably need a time machine to check that

and even with a time machine you might find that the answer isn't really either, or that one of them followed the other after a span of 3 minutes

because like, the difference really doesn't matter that much, it's a single-line proof

so anyone writing down this principle might have picked either one formulation or the other if you look very literally at the actual words they wrote, ...or they might have said "natural number" without clarifying which was meant, or something else that doesn't really make the distinction obvious

it's like asking which of these two statements historically came first:

1. if a function is injective and surjective then it is bijective
2. if a function is surjective and injective then it is bijective

[lean rover]

Show that if for every pair of nodes (x) and (y) in a graph (G) with (n) nodes it holds that
[
\delta(x) + \delta(y) \geq n - 1,
]
then the graph is connected.

[vital dew]

DatON1

[lean rover]

I really don't even know how to begin with this.

[pearl thorn]

Graph G(V, E) consists only of nodes of degree 3 and 5, where Nd3 = 6 and Nd5 = 8. Find |V| and |E|, and describe the graph.

The first half of the question is a gimme: |V| = 6 + 8 = 14. |E| = (6*3 + 8*5) / 2 = 29. However, I don't see anything special about it. it's not a tree, It's not complete, it's not bipartite. It might be connected, idk? It's such a vague question that I don't even know what to look for 😦

[clever kite]

How does this look?

[pearl thorn]

Oh hey I think I know this one!

Assuming G is a simple graph, we prove that G is connected by proving there is a path between any two vertices in G.

for any pair of vertices x and y in G, either:

1. There is an (x,y) edge
2. There is no (x,y) edge

In case 1, the (x,y) edge is the path, easy peasy.

In case 2, three things are true:

• G has N vertices
• there is no (x,y) edge
• deg(x) + deg(y) >= n-1

The maximum degree of a vertex is N-1 (it has an edge to every other vertex). Since there is no (x,y) edge, neither x nor y have this degree. That means we have to distribute at least N-1 edges over the other N-2 nodes, which means there has to be at least one z such that (x,z) and (y,z). That means (x,z,y) is a path, and x and y are connected.

[rose musk]

Aren't options 1 and 3 also propositions?

[onyx pollen]

In math, is the “let” used in proofs a definition or assumption?

[past rivet]

It’s more a definition

For example if you say “let b = 2a + 1” and “a” was previously defined, then “b” is just a name for “2a + 1”

You could’ve just as easily said “let Derek = 2a + 1”, so you’re using “Derek” as a name for “2a + 1”

[remote sandal]

Can anyone help me with this problem.

how many ways are there to paint 5 colour onto 2xn grids with tile that next to each other are different colour

I wanna use inclusion-exclusion but I still dont know where to start yet

[clever sail]

Did it say 2 and 4 were the answers?

Wait this is kind of a weird question lmao

Yeah shouldn’t it be all of them

[true venture]

Looking at the series expansion of e^x,
1 + (x^1)/1! + (x^2)/2! + ...
Is there a cleaner way to write the power series that starts at some number k.
(x^k)/k! + (x^k+1)/(k+1)!
Other than for example k=2 being e^x - 1 -x?

[craggy iron]

hi!

im still kind of lost how to apply composition here @weary tiger

[weary tiger]

Do you know what composition is?

[craggy iron]

for example:
f(x) = x + 1
fof = (x+1) + 1

how do I apply that here?

[weary tiger]

fof(x) = f(f(x))

[craggy iron]

yes

ah

so

f(1) = 2, f(2) = 1

f(f(1)) = f(2) = 1
f(f(2)) = f(1) = 2

[weary tiger]

yeah

So does fof have fixed points?

[craggy iron]

no it does not

[weary tiger]

Why not?

[craggy iron]

well because there are only 2 elements in the set and they are different so all the combinations will be different

am i on the right track?

[weary tiger]

No

What does it mean for something to be a fixed point of fof?

[craggy iron]

the values swap?

[weary tiger]

No

A fixed point for a function g is a x such that g(x)=x

[craggy iron]

okay i see that

[weary tiger]

So a fixed point for fof is a x such that (fof)(x)=x

[craggy iron]

uh huh

[craggy iron]

what does that imply though?

[weary tiger]

What do you mean?

[craggy iron]

i see that definition but it isn't a function definition?

[weary tiger]

What do you mean by function definition?

[craggy iron]

like i get that (fof)(x) = x is a fixed point, am i supposed to expand this out?

i dont see how this is the next step in answering that hw question

[weary tiger]

The question asked you to find a function that has no fixed points, but whose composition with itself has a fixed point

If (fof)(x)=x for some x, since f didn't have fixed points, that is an answer to the question

[craggy iron]

so i need to find a function where (fof)(x) = x is true but f(x) dne x?

but dont i need to give an example like f(x) = x^2 + ... etc?

[weary tiger]

The question only asked you to find a function

Didn't say it had to be defined in any specific special way

[craggy iron]

so my answer could be:

let F be the set of all continuous differentiable functions:

f is an element of F

assume f has no fixed points

if (fof)(x) = x for x in the real numbers, this is an answer

[weary tiger]

No

[craggy iron]

why not?

[weary tiger]

Not every f that has no fixed points satisfies (fof)(x)=x

[craggy iron]

there exists an f?

[weary tiger]

you need to prove there is an f satisfying your conditions

[craggy iron]

how?

[craggy iron]

this just seems like a statement

and not a proof

[weary tiger]

Although this is true, you didn't prove an f satisfying those conditions exists

[craggy iron]

can you give me a hint on how to prove it?

[weary tiger]

Not sure how to give an hint without spoiling the solution, hmm

[craggy iron]

darn LOL

im really stuck on this question

[weary tiger]

what are the simplest kinds of continuously differentiable functions you know?

[craggy iron]

polynomial or linear

[weary tiger]

Let's look at linear functions

Who knows, maybe we'll get lucky with those ones

Tell me some linear function of your choice

[craggy iron]

y = x + 1

[weary tiger]

Lovely choice

f(x)=x+1

Does it have fixed points?

[craggy iron]

it does not

here's my question

fof = x + 2

so when you do a composition

it increases the value if that makes sense

so how can the output value revert back to the input value if it isn't decreasing?

[weary tiger]

it is a good observation

maybe functions of the form x+a won't work for this

Can you think of other kinds of linear functions?

[craggy iron]

uhhh y = 3x - 1

in the form of y = mx - b

[weary tiger]

Actually I'm sorry, no linear function will ever work

[craggy iron]

wait really

uhhh

so the thing is, polynomial functions get too messy with composition for me to see any observations or patterns

so if the answer was polynomial, it would have to take 0 as the input and return 0 as the output

but i dont see how to guarantee that

[weary tiger]

this might be a bit trickier than i thought

if you want it to be continuously differentiable

[craggy iron]

yeah, i thought it was trivial but for a continuously differentialble function i dont see any

ive messed around on desmos for hours LOL

i dont (??) think it's possible?

[weary tiger]

Suppose f:R->R is continuous and f(x) is never equal to x. Then either f(x)>x for all x or f(x)<x for all x. Wlog assume f(x)>x. Then f(f(x))>f(x)>x. So it should be impossible

[craggy iron]

yeah, i thought so, it keeps on increasing

it gets bigger and bigger

[weary tiger]

Or smaller and smaller

[craggy iron]

so my prof lied to me

he said multiple functions exist

[weary tiger]

What exactly did he say?

[craggy iron]

multiple functions exist that fit this criteria

[weary tiger]

Did he say continuously differentiable functions?

[craggy iron]

yeah

which im like ????

bc ive been breaking my head over this question for so long

i think be might be trolling?

[weary tiger]

Maybe tell him this proof and see what he answers

[craggy iron]

gotcha, thanks

[weary tiger]

I could have made a mistake too, I hope not

[real horizon]

Find the least positive integer n such that there are at least 1000 unordered pairs of diagonals in a regular polygon
with n vertices that intersect at a right angle in the interior of the polygon.

[snow field]

Part on right

[compact aspen]

Can anyone explain like 2 of these?

[rapid kernel]

Principle of Transfinite induction, if B is subset of a well - ordered set (A, ≤) such that for every a in A, {c in A | c < a } \subset B implies a in B, then B = A.

If A-B≠ \empty, then there is a least element a in A - B. By the definition of least element and A - B we must have { c in A | c < a } \subset B.

But this set { c in A | c < a } can be non-empty, right?

If yes then there is no problem because we assumed in the statement subset so it can be non-empty.

[radiant gale]

Continuous everywhere?

[lean rover]

How to calculate the chromatic polynomial for this:

[earnest steeple]

if a graph g has n vertices all of which but one have odd degree, how many vertices of odd degree are there in the complement of g

is it just one>

[odd heart]

I didn't answer earlier because I hoped someone would pop in with a less tedious idea, but there is a general algorithm for finding the chromatic polynomial: https://en.wikipedia.org/wiki/Chromatic_polynomial#Deletion–contraction

With a graph of this size it might be quite some work though, unless maybe you can choose the edges in a clever way

Actually if you pick the horizontal ones for deletion-contraction, it won't be that bad.

Once you end up with graphs without the horizontal edges, you can find their chromatic polynomials more directly, doing what jonathan_fisherman suggested

So I think that's what I'd do, deletion-contraction twice, and then find the chromatic polynomials of the simpler graphs "by hand"

[true venture]

My bad what said was not a complete way

[odd heart]

Well yeah, but that's basically what doing it "by hand" entails, just basic combinatorics.

I don't think it's easy to do on this graph as-is, because there'd be too many cases to consider.

But a few rounds of deletion-contraction give you graphs where you can find the chromatic polynomials using fairly simple combinatorics.

[true venture]

Thanks, but what was thinking of was completely wrong

[fervent swift]

anyone explain?

[weary tiger]

!status

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[fervent swift]

2

[weary tiger]

What did you do?

[fervent swift]

I finished questions a,b. I totally don't know about part c. can you give some notes or idea please?

[weary tiger]

You don't know the definition of kernel?

[fervent swift]

yeah

[weary tiger]

The kernel of a homomorphism is the inverse image of 0

[fervent swift]

Then how to create formula for kernel of homomorphism?

[weary tiger]

You need to find every element that gets mapped into 0

[jolly turret]

Can anyone help

[outer gust]

Can someone quickly explain why this can't be the answer: True

[neon cloud]

you’re asking why it’s false?

[outer gust]

yeah

[neon cloud]

pi is irrational

pi≠3.14

that would be a rational number

,w pi

[vital dew]

Results provided by WolframAlpha

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

Requested by c.knief

[neon cloud]

those are clearly not the same

[outer gust]

Thanks

[waxen linden]

I'm doing some graphs to figure out what are the best ways to give unique objects in a set to players so that they can find a match.

I guess this is more combinatrics than a graph... I just drew them that way.

Because of the pidgeon hole principle if you have a set of 5 objects, if you give each person 3 unique objects form the set they will definitely have an overlap, right?

Is there other topics related to this that I could look into?

[wheat mist]

how to you find discrete math (math for computer science) compared to calculus 2? which is easier?

i'm taking both this term and just not sure what to expect

p -> q truth table is confusing...

FF = T?

[agile magnet]

it's quite different so some people find it easier some find it harder

[agile magnet]

yea for implication, we define it to have F -> T is T and F -> F is T also. This is quite useful

For example, I would like to say that "the sum of two odd integers is even"

written as an implication

If a, b are integers, then "a odd and b odd -> a + b even"

We would like the definition of -> to say that the above statement is true (otherwise it wouldn't be a useful definition, right?)

But that means that no one can come up to us and say "hey if a is even and b is odd, then a + b is not even it's odd" and then claim that our statement is false

because it doesn't apply!

we made a statement about summing two odd integers

so it says nothing about the sum of an even and an odd integer

so if P is the statement "a odd and b odd" and Q is the statement "a + b is even"

then if a is odd and b is even, then we have P is false and Q is false

but we still want P -> Q to be true

[agile magnet]

because we want statements like this to be true

hopefully that helps motivate the definition

[wheat mist]

but what if we say
p is (1+1=3)
and
q is (1+1=5)

both are false

yet p->q is True

[agile magnet]

that's fine

[wheat mist]

it's like saying, "if we were born on mars, then we were born on neptune" so "therefor we were born on Earth"

[agile magnet]

notice that saying p->q is True is different than saying that q itself is True

"if 1 + 1 = 3 then 1 + 1 = 5"

this is a true statement

we aren't saying that "1 + 1 + 5" is a true statement

[wheat mist]

its kinda like saying "if pigs fly then people will live to 1000"?

[agile magnet]

that is also a true statement

[wheat mist]

but we can also say "if pigs fly then people can live to 100"

[agile magnet]

yes we can

[wheat mist]

FT=T

so if the first "hypothesis" is false, it doesn't matter what comes after it?

[agile magnet]

exactly

[wheat mist]

you are just talking giberish at that point, and people will think it's nonsense

no matter what you say

[agile magnet]

and nonsense is nonsense

[wheat mist]

hmmm

[agile magnet]

and we don't care about it

[wheat mist]

but why do two false make a positive

[agile magnet]

we care about the case that if P is true, then is Q true or not

because often we want to assume some prior statement (P) and use that assumption to prove that some other statement (Q) is true

[wheat mist]

if truth, then truth ... truth
if nonsense, then truth ... truth
if truth, then nonsense ... false
if nonsense, then nonsense ... truth

[agile magnet]

I mean consider "If it is raining outside, then I will use an umbrella"

If it's not raining outside and I don't use an umbrella

that statement is still true

[wheat mist]

you mean, "then"? instead of "and"?

[agile magnet]

no

[wheat mist]

FF:T
"if it's not raining outside, then I don't use an umbrella"

[agile magnet]

I'm saying that in the case of it not raining outside and me not using an umbrella

[agile magnet]

I still want to consider this statement to be true

i.e. I want F -> F to be T

[wheat mist]

that's equivilant to
p -> q
FF:T

p = raining outside
q = using umbrella

if p then q

do i understand that correctly or still off?

[agile magnet]

you understand it correctly

[wheat mist]

or is p and q already T

oh we say the opposite for false

if p = sunny outside
T for p is sunny
F for p is not sunny

[agile magnet]

yea

[wheat mist]

alright, so let's say
if it's raining outside I will not use an umbrella
this is false

TF:F

or

if it's not raining outside I will use an umbrella

FT:T

[agile magnet]

seems like you're understanding it more and more

[wheat mist]

i guess what confuses me, is that this kinda makes sense for simple statements that are connected

but who would go outside when it's sunny out, with an umbrella

doesn't need to make sense i guess

when it comes to math.. or disconnected statements, that's where i'm confused

like the 1+1 = 3 example

that's just wrong, yet two wrongs make a right apparently

[agile magnet]

I mean consider this example still