ah okay
#discrete-math
glacial flame
and from x and y, we can plug it into ax = GCD(a,b) - by, but where do we get d from?
would it just be c/(ax + by)?
brave rock
More simply put, it is c/GCD(a,b).
brave rock
This is weridly overcomplicated
You will get x, you will get d
so it's just dx
Idk why you're writing it in this circuitious way
y is equally as difficult to calculate as x
glacial flame
thanks I'll need it 🥲
In hindsight, maybe I should have used l for left, r for right, and m for modulus so that the equations aren't so bungled
and u v for bezouts
odd compass
Can somebody help me understand something : If biconditionals are used to show that two statements can imply each other, why is it that we don't use equivalence instead? Is there something which I'm not getting?
brave rock
Please do not post your question in multiple channels at the same time.
worthy cargo
Can somebody help me understand something : If biconditionals are used to show t...
Try not to worry about it
odd compass
Please do not post your question in multiple channels at the same time.
Sorry did not know we could not do this
odd compass
Try not to worry about it
Why is that?
worthy cargo
Just doesn’t really matter. There’s nothing you’re missing
odd compass
Just doesn’t really matter. There’s nothing you’re missing
Can you give more details? If I someday write some notation, should I not know how it works?
worthy cargo
Just use it in a way that’s not going to be confusing
odd compass
Just use it in a way that’s not going to be confusing
are you talking from experience?
worthy cargo
Yeah
odd compass
thanks for the help though
viral hawk
I have a pie question if anyone can help?
You have a cup full of color pencils consisting of 10 different colors. How many ways can you write the numbers 1 through 12, if no color can be represented more than 3 times? State your answer as an integer.
sleek mirage
weary tiger
does anybody understand how to start this ? : m ∼ n ⇔ |m − 3| = |n − 3|
its asking if its an equivalence relation and for its relation classes
its on Z, integers
obtuse lance
try checking the 3 rules, uhh identity, commutative, transitivity
m∼m, m∼n <=> n∼m, and m∼n, n∼k => m∼k
weary tiger
thanks that helps
swift estuary
prove that the graph of every element of the symmetric group Sn is a subset of Zn^Zn is a spanning union of disjoint directed cycles
I have no idea what any of these terms mean so an explanation would be super helpful
Like what is a symmetric group, spanning union, or a disjoint directed cycle
night stream
hi! can someone explain how to solve this question like am i suppose to make up the numbers in R?
stray reef
this question is bullshit...
night stream
this question is bullshit...
Mine?
stray reef
yes, it's incredibly poorly phrased
"R is (property) if and only if x > y" simply does not make any sense
night stream
yea idk how to approach this problem;-/
like i dont understand what R is suppose to be
wicked bolt
like i dont understand what R is suppose to be
maybe it's supposed to be {(x,y) : x,y \in \bR and x>y} but the question is nonsense :c
night stream
maybe it's supposed to be {(x,y) : x,y \in \bR and x>y} but the question is nons...
hi! sorry but what does \in and \bR mean?
vital dewBOT
layla💜
wicked bolt
yep, just be careful because that might not be right haha
floral tangle
Is this relation reflexive? our senior in university said that this relation is reflexive
but isn't the condition for a relation to be reflexive is "for all elements a in the set A, there exists the ordered pair (a , a)"
floral tangle
Is this relation reflexive? our senior in university said that this relation is ...
in this relation, (0 , 0) is not an element of relation R since it does not satisfy the condition that xy >= 1
floral tangle
Is this relation reflexive? our senior in university said that this relation is ...
so R should not be reflexive right? but our senior said that it is reflexive and as long as there is one ordered pair of the form (a , a) then the relation is reflexive
grand totem
You're correct. For $R$ to be reflexive on $\mathbb{Z}$ we must have $\langle a,a\rangle\in R$ for every $a\in\mathbb{Z}$. But as you noticed, $\langle 0,0\rangle\notin R$, since $0\cdot 0=0\ngeq 1$.
vital dewBOT
Neverbloom
agile magnet
vital dewBOT
Spamakin🎷
unreal stump
Sounds like it
weary tiger
Is this hasse diagram correct ? answer is on the right page bottom left corner
Let S = {a}, {b}, {c}, {a, b}, {a, c}, {b, c}
Also i made a second answer top right corner of the right side page, the difference is i removed different transitive edges (can you do that and still be correct ?)
gentle bronze
why is B not subset of B here?
coral parcel
(Ingore this, was rubbish).
It must be a typo. The line would make much more sense if that part said "B not a subset of C".
gentle bronze
It must be a typo. The line would make much more sense if that part said "B not ...
so B IS a subset of B then?
cuz arent subsets always subsets of themselves?
coral parcel
Correct.
coral parcel
Yes, looks like you're right.
coral parcel
humble sluice
like i dont understand what R is suppose to be
R is the set for the relation. so the question is pretty much asking that can R be reflexive if x > y (no cause to be reflexive x = y) and then you do the same thing for symmetric and transitive.
gentle bronze
<:bleak:877093280905592842>
should it be worded ' this statement is false since, for example, letting x = -1, there is no real number ***y *** such that y^2 = -1?
or should it say
should it be worded ' this statement is false since, for example, letting x = -1, there is no real number **x **such that y^2 = -1?
coral parcel
The first.
gentle bronze
The first.
thanks
gentle bronze
The first.
does this state that all elements of A are elements of B?
brave rock
Looks like a typo to me
Oh right I misunderstood
Yes indeed this is what it's saying
gentle bronze
Yes indeed this is what it's saying
and does this say 'there exists an element in A that doesnt exist in B?
brave rock
Yes. Is this confusing to you?
gentle bronze
Yes. Is this confusing to you?
wdym
gentle bronze
Well I'm wondering why you're asking
just started degree maths
first year
and im going over my notes
so making sure i understand it
this is new to me
brave rock
OK
brave rock
No it's just like, you're not struggling so why ask
gentle bronze
No it's just like, you're not struggling so why ask
i wasnt sure if i was right
brave rock
OK
gentle bronze
but i know that i am now
ornate creek
Hello, I am trying to prove that any integer greater than or equal to 8 can be represented the sum of multiples of 3 and 5. I am just wondering if I have actually successfully proved that the set of counterexamples is empty.
wicked bolt
Hello, I am trying to prove that any integer greater than or equal to 8 can be r...
the idea looks ok
crystal oyster
Does anyone know proof by cases? I’m having a rough time with this problem.
rapid mural
Not sure what the question is but maybe:
Case 1: q is true
Case 2: r is true
Case 3: both q and r are true
stray reef
case 3 is unnecessary
rapid mural
Definitely. I do sometimes like to leave it in just as a sanity check.
brave rock
Yes
spring elk
so for something like this where the universe is involved, if i have to state whether the relation is reflective, symmetric, antisymmetirc or transitive as long as I find a case where its true then its fine?
brave rock
I don't know what you mean by that
You just have to prove the definitions as you do for any other relation
spring elk
for example if I take A {1, 3} and B {3,1} and C to be {3} then its symmetric
or it has to wor kfor all cases?
brave rock
Are you saying you can rely on one example to show that it is true for all cases?
If so, this is simply not true
spring elk
alright thanks. Only if its not true then i can disprove it with a simple example
spring elk
just to make sure i understood. In this case, R = {(1,1), (x,x)} would be reflexive right? even if (2,2) isnt in there, since number 2 does not appear anywhere in R
spring elk
would R {(1,2), (2,1)} be symmetric for the example above?
or does every element of A have to be in R? but if thats the case then this isnt symmetric
nvm. symmetric one has a p -> q property which is different
brave rock
just to make sure i understood. In this case, R = {(1,1), (x,x)} would be reflex...
In this case, R = {(1,1), (x,x)} would be reflexive right?
No, because since 2 is in A, we require (2,2) to be in R.
By definition
brave rock
or does every element of A have to be in R? but if thats the case then this isnt...
No, it is symmetric.
spring elk
yeah i realized from the'"p -> q property" that the symmetric one has.
I should pay very close attention to the definitions
crystal oyster
@rapid mural thank you.
rapid mural
No problem
minor gorge
What have you tried?
gentle bronze
Think I’ve got it
gentle bronze
What have you tried?
wat u think
minor gorge
This one's correct
I think you are also supposed to find out whether the union and intersection sets are finite or infinite
@gentle bronze
gentle bronze
<@849961886874730516>
here they would be right?
both infinite?
the union and intersection
?
minor gorge
Yup
minor gorge
Please use more gender neutral language
robust mango
@weary tiger Are you still here?
weary tiger
<@456226577798135808> Are you still here?
Isolved it
shut bolt
how do I go about solving this?
unreal stump
||Find a counter example||
shut bolt
but doesnt transitivity require 3 inputs?
spring elk
can someone help with question 4? I dont get their solution
if r1 and r2 is the usual les than or equal 2 how do we even have (2, 1)?
(2, 1) isnt in either R1 or R2
for r1 to be poset and total order then r1 is {(1,1), (2,2),} (1, 2) cant be in r1 cz then it wont be asymmetric.
r2 gets the same set above. why would R not be total order?
oh is it because R might have (1, 2) and (2, 1) ?
grand totem
Firstly, $\mathcal{R}_1=\mathcal{R}_2={\langle1,1\rangle,\langle1,2\rangle,\langle2,2\rangle}$.
We let $\langle a,b\rangle \mathcal{R}\langle a',b'\rangle \Longleftrightarrow a\leq a' \land b\leq b'$. Using the fact that $1\leq2$, but $2\nleq1$, what can you say about $\langle 1,2\rangle \mathcal{R}\langle 2,1\rangle$ as well as $\langle 2,1\rangle \mathcal{R}\langle 1,2\rangle$?
vital dewBOT
Neverbloom
weary tiger
Can somebody tell me what's going on here? I don't get how she's factoring out the 3.
And what the [] notation represents here.
weary tiger
`3k+3 = 3(k+1)`
right but if you look above she only seems to factor out the 3 from one clause(?)
elder berry
and?
weary tiger
is that allowed?
i see the 3 as a coefficient so i'd want to multiply all the clauses by that 3
elder berry
all terms are multiplied, so yes
(3k+1)(3k+2)(3k+3) = (3k+1)(3k+2)(3*(k+1)) = (3k+1)(3k+2)*3*(k+1) = 3*(3k+1)(3k+2)(k+1)
weary tiger
oh yeah that makes sense actually
elder berry
dropping brackets from second to third step because of associativity and switching the 3 from being third term to first term due to commutativity
weary tiger
what's the easiest way to find the n here?
obtuse lance
maybe see if you can find a pattern in the exponents on the prime factors of perfect squares
weary tiger
gloomy pelican
Hi ! Let's say I have a deck of cards from 1 to N in a random order. When I pick a card, let's say the card with number k, I switch the order of the first k cards. For example, let's take 3-1-4-2 --> 4-1-3-2 ---> 2-3-1-4 --> 3-2-1-4 --> 1-2-3-4. I want to prove that it always ends with a 1 in the first position. How would I do that ? Thanks 🙂
livid drum
Umm... just think about how you'd go about it mentally if you were given the input (1, 1, 1, 2, 2, 3, 4, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 11)
Test out for yourself different inputs.
Once you have your optimal algo, you can study its complexity.
molten fjord
does part a) literally just mean if I have two quantities b and r then I just literally put them into a set {b,r} and their transitions as {1,2,3,4}?
as an example
weary tiger
Umm... just think about how you'd go about it mentally if you were given the inp...
I have: procedure find location [array]
for i in range (0,len[array])
If i =i
Location =: array[i]
so far..
livid drum
I have: procedure find location [array]
for i in range (0,len[arra...
mate.... 😅
Maybe try having a counter for all-time "best" index with most repeats? And another for the current number of repeats.....
As i start at array[0], maybe I have a peek at the future (doesn't cost me complexity), maybe ill record some info.
And continue on...
livid drum
Hi ! Let's say I have a deck of cards from 1 to N in a random order. When I pick...
Hmm I really like this question!
Here is an argument which ought to be supported by induction, but whose intuition is as follows:
Take N in the problem as 100.
Either 100 shows up in the game (as the top card), or it doesn't.
If it does appear, then it can only appear once.
For once seen, it will go to the bottom of the deck and be inaccessible.
In either case, we can fast-forward to a state in the game in which 100 is no longer accessible.
Either 99 shows up in the game from that point on, or it doesn't. And we repeat these same arguments, crucially leveraging the fact 100 is inaccessible.
Eventually we collapse to 1.
A pro of this method is that it has nothing to do with how you put back the cards, so long as the kth card goes to slot k, you can shuffle the cards before it, and place it back.
A con is that isn't constructive; it doesn't compute an upper limit to the number of steps to play the game out before you're guaranteed to see 1's.
lusty garnet
for a problem, i have to prove by induction that 4^n -1 = 0, do i do this by strong induction or structural induction?
rapid mural
I feel like that's not true in the general case. Are you missing something?
(4^1) - 1 is certainly not 0
static ivy
Mod something mayb
brave rock
This function has no inverse
brave rock
Paying for homework help is not allowed on this server.
Please remove that offer, and you may actually get help.
gloomy pelican
Hmm I really like this question!
Here is an argument which ought to be supported...
That makes a lot of sense! Thanks man @livid drum
past sparrow
Does this channel handle Constraint Satisfaction Problems ?
coral parcel
Yes, but you have negated each of the inequalities incorrectly.
The negation of x <= -4 isn't x < -4.
chrome lily
The negation of x <= -4 isn't x < -4.
is it X > -4?
coral parcel
Yes.
chrome lily
👍
past sparrow
ive set 2=rock 3=paper 5=scissors. with the games held my hill and nor G1....G10. so that say the first constraint G1...G10= 2 * 3^6 * 5^3. How would i go about making the 3rd constraint?
HG1...HG10 =/= NG1...NG10 ? then singularly ?
dry raven
obtuse lance
I'd say no, cause every integer is a common divisor, so there is no greatest. But maybe out of laziness you could take gcd(0,n)=n for positive n and extend this to n=0 and just say gcd(0,0)=0. I'm sure there are more sophisticated answers for what is morally good here.
covert solstice
rapid mural
yeah looks fine to me
The organization is a bit weird though
you could do TTTTFFFF for p then TTFFTTFF for q etc
rapid mural
Start by writing down the definitions of injective and surjective
And bijective of course
mortal arrow
any good textbooks for discrete math with easy to understand explainations and lots of questions?
weary tiger
you could do TTTTFFFF for p then TTFFTTFF for q etc
Haha you can't realise how many times I was like "I am missing one of them..."
Thanks for the advise though
oak yacht
Determine how many arrangements can be made of the word
NASHVILLETENNESSEE so that the first N precedes the first S and
Let the first E precede the T.
Can anybody help me with this?
coral parcel
First scramble NANHVILLEEENNENNEE, and then consider how much choice you have in turning three of the Ns into Ss and one of the Es into a T, while sticking to the rules.
umbral blade
Why is the bottom question false when the universe of discourse is the set of all positive integers?
brave rock
So are you saying there is some y such that, for all x — chosen independently of y — we have xy = y?
And you say this positive integer y is 0?
Maybe this is an issue with language, but typically 0 is not called a positive integer.
umbral blade
So are you saying there is some y such that, for *all* x — chosen independently ...
Yeah but wouldn’t y= 1 make xy = 1 for all real numbers X?
umbral blade
Oh sorry. I meant to say wouldn’t
brave rock
It wouldn't, indeed.
umbral blade
X= 1 make xy = y
brave rock
y = 1?
So let's think about this, again
xy = y when y = 1 is saying x * 1 = 1.
Is that true for all x?
umbral blade
No
brave rock
So in fact y = 1 doesn't work.
umbral blade
Oh okay I see now
My teacher considers 0 as a positive integer
So x*y = y would only be true if y = 0 for all real numbers
But if the universe of discourse is positive integers then it would be false since 0 isn’t in that universe of discourse
lavish roost
is not normal to be confused with proofs and logic at the beginning?
brave rock
It is normal.
spring merlin
My teacher considers 0 as a positive integer
?????
brave rock
France™️
umbral blade
?????
I assume that’s what she meant unless there is any other one single value that makes x * y = y
Ah i see lmao
spring merlin
0 isnt a positive integer
umbral blade
Nvm she doesn’t
spring merlin
So if the domain of discourse is positive integers, it would be a contradiction
lavish roost
what is the difference between proposition, statement and predicate? Example syntaxes will help
azure willow
could someone help me with this? i feel like i'm not understanding this at all
i think i have a. but i'm not sure how to approach b
sweet thunder
In general how can we tell it a graph is connected?
weary tiger
I'm struggling to determine how this equality was found.
sweet thunder
Have you proved associativity in your class?
weary tiger
Have you proved associativity in your class?
mhm, probably not?
sweet thunder
Has addition been defined?
vital dewBOT
tropic mango
where i created mistake?
brave rock
This is unreadable
tropic mango
wait i will explain
(x,y)∈(A\B)×C ⇒ x∈(A\B) and y∈C ⇒ x∈A and x∉B and y∈C ⇒ (x∈A and y∈C) and (y∈C and x∉B)
main bane
I have a question concerning combinatorics and fuzzy sets.
We know that if we have a certain finite set whose elements are crisply in the set, we can state many combinatorial facts about them, such as the number of permutations and combinations of the elements in the set. However, I was wondering what this would look like if we were to extend combinatorics to fuzzy sets. We know that for finding the number of ways we can order n things in a set containing n elements, we have n! arrangements. But I’m wondering how exactly this can be done with fuzzy sets (if at all), and whether or not some version of the gamma function would be at play.
If it can be done, how exactly could it be done?
brave rock
is this readable?
Certainly readable now. This does almost show that (A\B) × C is a subset of (A × B) \ (B × C) – although in my opinion you need a tiny bit more justification, but more importantly you also need to show the reverse inclusion.
tropic mango
Certainly readable now. This does almost show that (A\B) × C is a *subset* of (A...
i got confused by the last part (x∈A and y∈C) and (y∈C and x∉B) , I know that first bracket meaning (A×C) but the second one confusing me and (y∈C and x∉B) i think i got there C\B
i think there need to be and (y∉C and x∉B)
idk if i'm right or not
near quartz
need help on this. Here's my work so far but I think I messed up because I cant factor 2 out of sqrt(2k)
anyone know where I'm going wrong?
grand totem
You prove this by double inclusion, so you should really have two (sub-)proofs, one showing M⊆Q and one showing Q⊆M. It seems like you're trying to do both at once here.
Let's focus on M⊆Q for now, that inclusion requires "structural" induction (and no induction on the naturals), can you see how to do that?
near quartz
Nope 🤣
Q is a subset of the reals so that's easy i guess but
How do u show M C Q
Also have this as well but I think it's wrong anyway
grand totem
It might be beneficial to recall what exactly makes up an inductive definition. A bit more precisely than stated in the image, inductively defined sets (like M) are those that meet some conditions (for M that would be 0 is in M and M is closed under the function x + 2sqrt(x) + 1). But they're also supposed to be the least set meeting those conditions (otherwise they wouldn't be uniquely defined and in fact the entire real numbers also meet our two conditions).
So one information that you also know about M is that for any other set M' for which (IA) and (IS) both also hold, we must have M⊆M'. This states precisely that M is the least set satisfying (IA) and (IS).
But now this gives us a perfect way to prove that M⊆Q: As M is the least set satisfying (IA) and (IS), it would be sufficient to show that Q also satisfies (IA) and (IS).
We could then let M' = Q in the minimality condition of M and immediately get M⊆Q.
grand totem
You mean the Q⊆M inclusion?
grand totem
You prove that n² is in M for every natural number n. This is a "for all natural numbers" statement, so induction (the regular old induction on the naturals) does the trick.
near quartz
Do you need a quadratic that when squared gives the form x+2√x +1?
grand totem
You mean the Q⊆M inclusion?
^The above was an answer to this question
grand totem
And how do you show Q satisfies IS
Take any x in Q, then x = n² for some natural number n.
You wish to prove that x + 2sqrt(x) + 1 is also in Q, that is you wish to exhibit another natural number m such that m² = x + 2sqrt(x) + 1.
If you plug x = n² into x + 2sqrt(x) + 1 and do some simplifications you'll probably see what our m might be
near quartz
It would become n^2 + 2n + 1
grand totem
Exactly, and when you factor that with the binomial theorem?
near quartz
(n+1)^2
grand totem
Perfect, so x + 2sqrt(x) + 1 = (n + 1)^2 and so it must be in Q [since there is a natural number m such that m² = x + 2sqrt(x) + 1, namely m = n + 1]
The part in the brackets is a bit pedantic and is probably not worth including in a written proof. It's just going through the details of what it means to be in Q
near quartz
I see, thank you
grand totem
Showing that Q satisfies (IA) is hopefully clear. And then you're already done with one inclusion
cursive echo
Why is this true? Confused on what it’s asking or what it would look like
I'm still learning this rn so someone may correct me:
p <-> q is the same as saying p and q are logically equivalent
p and q being logically equivalent means they have the same truth values for both true and false
a tautology is when all truth values are true - therefore surely that is false because they can still be equivalent without being a tautology as long as they are false at the same time as well as true at the same time
wait no i think im already wrong
no i think im right, https://www.cs.ox.ac.uk/people/michael.wooldridge/teaching/soft-eng/lect07.pdf
this might help
umbral blade
Well is p and q logically equivalent in the first place?
coral parcel
They may or may not be.
The claim is that whenever you find a p and a q that are logically equivelent, then p <-> q will be a tautology.
And if you find a p and a q that are not logically equivalent, then p <-> q is not a tautology.
Note that this claim is most interesting if "p" and "q" are our names for entire logical formulas, rather than two distinct propositional variables.
umbral blade
I believe that’s what I was thinking. If p and q are logical formulas then it would be true. But if there were two different single propositional variables it would be false?
coral parcel
It's still true in that case, just not very interesting.
If p and q are different propositional variables, then they are not equivalent, and correspondingly p <-> q is not a tautology (for example, in a valuation where p is true and q is false, p <-> q evaluates to false).
umbral blade
I see. Since it’s biconditional, False and False makes the proposition true?
coral parcel
Yes.
gray sun
I have the following theorem:
if n is an integer and n^2 is odd, then n is odd.
or
p : n^2 is odd
q : n is odd
(s ⋀ p) -> q```
I am doing a proof by contraposition. The contrapositive of this statement would be the following:
```if n is even, then n^2 is even or n is not an integer.```
or
```¬q -> (¬s ∨ ¬p)```
Is this correct?
Do you think I need to include the proposition about n being an integer? or can i simply assume it is one or what?(s ∧ p) → q is equivalent to s → (p → q). You'd want to use contrapositive on the inner implication
gray sun
`(s ∧ p) → q` is equivalent to `s → (p → q)`. You'd want to use contrapositive o...
Okay thanks, but is the text part correct?
if n is even, then n^2 is even or n is not an integer.
or should i write it like:
if n is an integer, then it is the case that if n is even, then n^2 is even.
grand totem
or should i write it like:
```if n is an integer, then it is the case that if n...
I mean they're all equivalent, but the latter one is in the "nicest" form if you go about proving it
gray sun
I mean they're all equivalent, but the latter one is in the "nicest" form if you...
ok thank yu
Is there a difference between ≡ and <->?
grand totem
<-> is part of the object language - it's just a connective used to build more complex well-formed formulas (in the same way that ¬, →, ∨, ∧ are).
Meanwhile ≡ isn't part of the formal language, but lives in our meta-language (which for all intents and purposes here is just plain English).
I'm assuming that ≡ is used in your course to assert logical equivalence between two formulas
If you scroll up a bit you can see a discussion on how the two are related: two formulas ϕ and ψ are logically equivalent, i.e. ϕ ≡ ψ, just in case the formula ϕ <-> ψ is a tautology
gray sun
<-> is part of the object language - it's just a connective used to build more c...
Okay I didn't realize there was so much nuance.
I have the two following statements:
[(p1 v p2 v p3) -> q] ≡ [(p1 -> q) ⋀ (p2 -> q) ⋀ (p3 -> q)]
[(p1 v p2 v p3) -> q]<-> [(p1 -> q) ⋀ (p2 -> q) ⋀ (p3 -> q)]
And i guess like your ϕ and ψ example, these two statements are equivalent right?
the text isnt formated here but numbers after p are subscript
grand totem
Yes, this is what I meant by how ≡ and <-> are related.
The first "statement" asserts that the two formulas are logically equivalent (they take on the same truth value for every possible assignment of the variables).
The second one technically doesn't really assert anything, it's just a well formed formula (similar to how p ∨ q by itself doesn't really assert anything, it's just an object of our formal language, a string of symbols).
What we may ask however is if that second formula is a tautology, i.e. is it true in every possible variable assignment?
And the connection here is that the first statement (the ≡ one) holds just in case the second formula is a tautology.
raw jetty
can someone help with this? Prove by induction that for any wff φ and PL-interpretations I and I′, if I(α) = I′(α) for each sentence letter α in φ, then VI(φ) = VI′(φ).
gray sun
Yes, this is what I meant by how ≡ and <-> are related.
The first "statement" as...
I understand now, and so im assuming "≡" is reserved for when it's already established, whereas a statement involving <-> has a truth value?
A better way to write is like this:
I have established that:
[(p1 v p2 v p3) -> q] ≡ [(p1 -> q) ⋀ (p2 -> q) ⋀ (p3 -> q)]
Therefore
[(p1 v p2 v p3) -> q] <-> [(p1 -> q) ⋀ (p2 -> q) ⋀ (p3 -> q)]
is always true
grand totem
Important to note that it goes both ways. You may also assert that two formulas p,q are logically equivalent after you've established that p <-> q is a tautology
gray sun
Important to note that it goes both ways. You may also assert that two formulas ...
ok cool
tysm
grand totem
👍
grand totem
can someone help with this? Prove by induction that for any wff φ and PL-interpr...
I can probably fill in most of the gaps but it would be easier to help if you also provided the necessary definitions: what does your language look like (this will determine the induction cases), how is truth defined, im assuming an interpretation is a mapping from propositional variables to truth values? Etc
raw jetty
we are doing axiomatic proofs with alpha, phi, psi, and chi
grand totem
That is not what I meant (and this question is related to semantics, not to proof systems anyway).
Your prof probably defined what a wff looks like, what an interpretation is and how one can recursively extend that to all wffs
raw jetty
oh yes
(i) Every sentence letter is a PL-wff.
(ii) If φ and ψ are PL-wff s, then ⌜¬φ⌝ and ⌜(φ → ψ)⌝ are also PL-wffs.
(iii) Nothing else is a PL-wff.
grand totem
ok, fix two interpretations I, I'. We prove that for any wff ϕ, if I and I' agree on all sentence symbols occuring in ϕ, then VI(ϕ) = VI'(ϕ).
Since the proof proceeds by induction we have to do 3 sub-proofs:
- We show that the claim holds for any sentence symbol
- We show that when the claim holds for a formula ϕ, then it also holds for ¬ϕ
- We show that when the claim holds for formulas ϕ, ψ; then it also holds for ϕ →ψ
Can you see how to prove the first case?
raw jetty
yes, that helps, thank you
raw jetty
@grand totem sorry for the ping, i am still struggling with this problem. i haven't been able to figure out how to do the first one yet. do you think you could help?
valid vigil
is this a good server for optimation problems?
grand totem
<@220941391054897153> sorry for the ping, i am still struggling with this proble...
Sorry, I just saw this. Do you still need help?
raw jetty
no worries, im all set
valid vigil
Hello?
leaden portal
brave rock
No.
"Only gods can kill other gods" should be interpreted as saying "If something can kill a god, then that something is a god." Try writing that out.
N.b. it does not mean that all gods can kill all other gods, or even a single other god!
vagrant iris
Hi guys
Can you help me
Prove that a^3 and b^3 result in the same remainder when divided by a-b
Thx
elder berry
N.b. it does not mean that all gods can kill all other gods, or even a single ot...
Interesting. Can it be the case that a god can't be killed by anything?
brave rock
The sentence "only gods can kill other gods" is compatible with that situation, yes
elder berry
ty!
vital flume
How should I approach this discrete math proof
Let f : A → B be a function. Prove that if f is not injective, then f −1 is not a function.
i get why it isnt a function if f isn't injective but how would i prove it
brave rock
I think if you "get it" but can't prove it, perhaps you don't really get it. Let's work on trying to turn your intuition into a proof.
First, explain in words why you think this is the case
vital flume
First, explain in words why you think this is the case
if f isnt injective then that means 2 or more integers in the domain share the same range. if you were to invert the function, then that would mean of the inverse function, one or more of the values in the inverse domain will have 2 or more range/image values
brave rock
if f isnt injective then that means 2 or more integers in the domain share the s...
Well good job, that's pretty much a proof
I'm not entirely sure why you're specifying that the domain consists of integers—perhaps this is part of the question that you left out.
But in any case, yes, you can simply find an example where f(a) = f(b) = c, but a =/= b.
That's pretty much it, as you point out.
vital flume
isnt there a proper structure
brave rock
You followed proper structure
vital flume
it doesnt specify proof by induction/cases etc but it doesnt feel structured to me
brave rock
OK well we're trying to prove:
for all functions f : A -> B,
IF f is not injective
THEN f^-1 is not a function
So to begin this proof, typically we say "Let f : A -> B be a function that is not injective," which is pretty much what you said in different words
Then you used the definition, and concluded something
It was a bit vague and making it totally precise is a good exercise
But you have the thrust of the proof down
vital flume
yea i just looked at the solution its the same thing but expressed with quantifiers
brave rock
Well there you go.
vital flume
i appreciate the help
barren bear
Does anyone happen to have access to practice problem sets for simplifying boolean expressions using the laws of boolean algebra? Or problems for showing that two boolean expressions are equivalent? The Zybooks textbook I use has almost none. Would love if anyone could share some with me. I'm trying to practice more.
gaunt kraken
How many elements are contained? I have no idea what the U and the lines mean, professor never taught it.
vital flume
the lines means not the set
like all elements in the universal set not in the set with the line above it
U is like or
well i think of it as or but the formal definition is union
and the upside down U is intersection
the upside down u is intersection because its the set containing elements from both of the sets
vital flume
How many elements are contained? I have no idea what the U and the lines mean, p...
If you were to do A \union B \union C it would be all of the numbers in the 3 circles
havent used latex in a while 😦
brave rock
\cup is union, \cap is intersection
vital flume
how would i prove X ∩ Y ⊆ X for all sets X and Y.
I can do direct proofs/proofs by contradiction but i dont have a clue on how to do set proofs
the intersection of x and y must be a subset of x because it only contains elements in x that are also in y(elements in x and y)
but that isnt well worded/strong proof
barren bear
How many elements are contained? I have no idea what the U and the lines mean, p...
Some other members already helped explain the operators but I drew a little visual aid incase you might find it helpful.
gaunt kraken
Some other members already helped explain the operators but I drew a little visu...
This is exactly what I needed. Thank you guys.
Thank you @vital flume as well for the other explanations!
barren bear
I wanna go back to sets
keen escarp
ez sets except when you forget the signs
barren bear
Rn I'm manipulating expressions using boolean laws lol
This logic has my brain having regular meltdowns
vital flume
i have no clue how to approach set proofs im fine with other proofs
whats that looking like
is it something like this?
we had to negate expressions using de morgen laws
lavish roost
De Morgan or de Morgen?
barren bear
Hard to say because my textbook has like 0 practice problems. (Thanks Zybooks lol)
But it's mostly expanding and simplifying using all the laws, yeah.
stuff like this
lavish roost
I like inductions, set proofs and universal if and only if proofs
Implication proofs can be tricky
vital flume
I like inductions, set proofs and universal if and only if proofs
help mee please 🙏
im doing set proofs problems before my midterm next week
lavish roost
I am a noob bro
vital flume
its an easy one
vital flume
well its not "easy" but i dont think its. along proof
cant say its easy cuz idk how to do it
its this : Prove that X∩Y⊆X for all sets X and Y
lavish roost
For some reason I don't like the proofs which have "odd/even/division/multiplication" stuff like that
Somehow my brain doesn't work when arithmetic stuff is in algebra
viral turret
Hi
barren bear
hi hi
viral turret
Can you help me why I got points of for these questions.
barren bear
Sorry, I didn't see your message. Looking now.
vital flume
maybe the in symbol? nah
elder berry
Can you help me why I got points of for these questions.
The negation of a > b would be a <= b
No where have you mentioned the equality case
and by the # of points deducted, I suppose it's just that
vital flume
i need to review negation rules 😭
elder berry
maybe the in symbol? nah
I mean this is also a valid point, I commonly see $\forall x \in \mathbb{N}$
barren bear
lol thats what I was doing. My brain fog is real today.
vital dewBOT
peaceGiant
gentle harness
Can you help me why I got points of for these questions.
I don’t think you should make a,b < 0 in the second one. It should remain unflipped
elder berry
I don’t think you should make a,b < 0 in the second one. It should remain unflip...
why'd u think so?
gentle harness
why'd u think so?
The negation happens to the predicate not the subject
I could be wrong tho
elder berry
oh yeah, an implication would work way better
gentle harness
But logically to negate a fact about positive natural numbers. The negation would still be about positive natural numbers with the fact about them negated. Idk if that expresses it well
elder berry
indeed
umbral blade
Why is the first one false and the second one true in terms of Big O?
viral turret
But logically to negate a fact about positive natural numbers. The negation woul...
So when negating the <> doesn’t change Rt. Because even for the first one I change it and idk if the point of on that was that to.
gentle harness
So when negating the <> doesn’t change Rt. Because even for the first one I cha...
No you change them if they are part of what’s being proposed by the statement. You don’t change if they are part of the subject in the statement.
elder berry
Why is the first one false and the second one true in terms of Big O?
Loosely speaking, Big O tells us that f(x) = O(g(x)) iff f(x) <= k g(x) for some constant k.
The second one is true because 2^(n+1) = 2 * 2^n = constant * 2^n so it is O(2^n)
The first one, you can't pull out such a constant, the best you can do is 2^(2n) = 2^n * 2^n which can't be bound with 2^n
gentle harness
So when negating the <> doesn’t change Rt. Because even for the first one I cha...
For example: “even numbers are divisible by 2”. When negated becomes: “even numbers are NOT divisible by 2”. Notice that when I negated the statement I made sure not to change it to “odd numbers are not divisible by 2” because I would’ve flipped the subject and that’s not what the proposition is talking about.
elder berry
to add to the above, this is very common when you are looking at the universal quantifier, paired up with an implicaton
"All even integers are divisible by 2" is the same as "For any integer, if it is even, then it is divisible by 2"
now you can happily apply all the symbols that you want to arrive at the negation
$\neg(\forall x : x \in 2 \mathbb{N} \implies 2 \mid x) \iff \exists x: x\in 2 \mathbb{N} \land 2 \nmid x$
vital dewBOT
peaceGiant
elder berry
the negation of your original statement becomes "There exists an even number not divisible by 2" which makes sense intuitively ("Not all even numbers are divisible by 2")
gentle harness
**peaceGiant**
I’ve always struggled to intuitively understand why implication was equivalent to “not p or q” but now when I saw it’s demorgan’s negation it made intuitive sense.
gentle harness
the negation of your original statement becomes "There exists an even number not...
Yup you’re right
stray reef
when you say "how is this proof", do you mean "can somebody evaluate this proof for aesthetic merit" or do you mean "i don't see how this proves anything, convince me otherwise"?
vital flume
when you say "how is this proof", do you mean "can somebody evaluate this proof ...
latter
stray reef
this is a proof by strong induction
vital flume
yea
its good enough for these type of problems?
like prove x-cent and y-cent can add up to n cents
i've done 3 and the approach has all been the same
but with a different type of proof by strong induciton
i cant solve it
like this
$\forall n \in \mathbb Z^+$, if $n \geq 2$, then $n$ is either prime or can be written as a product of primes. You may assume that an integer is either prime or not prime.
vital dewBOT
Praxis
pale epoch
this is a lot of text, why not pick one exercise, share your work and try to explain where you are stuck
serene mural
I need help understanding these type of questions. So basically i have to determine whether each statement is True/False.
For number (f), statement says "For all positive integer x and y, there exists at least one positive integer Z that satisfies z = x -y" (Did i get this right?)
So the question is
Is the statement above True because there is at least one Z that satisfies z = x - y?
or is the statement above false because Z doesn't exists when y > x?
coral parcel
Have you tried some combinations of x and y to see if you can construct a counterexample?
(Also, the exercise calls the number that may or may not exist "z", not "Z". You shouldn't call it alternately one or the other; letter case carries meaning in mathematics).
serene mural
Have you tried some combinations of x and y to see if you can construct a counte...
yes, statement is false when y > x
coral parcel
There's your answer then.
serene mural
There's your answer then.
so is z = x-y
∃z P(z) which is true
or is it
∀x ∀y P(x,y) which is false?
rapid mural
The question asks for the truth value of the entire statement
If the statement is false, then the negation of the statement is true
Can you see what the negation of the statement would be?
rapid mural
so is z = x-y
∃z P(z) which is true
or is it
∀x ∀y P(x,y) which is false?
Is the question asking for which part of the statement is incorrect? (which is unusual)
Or is it simply asking if the entire statement is true or false
serene mural
oh i think i misunderstood the question
yes, i think it asks the truth value of the entire statement
thanks for clearing my misunderstanding
opaque prawn
Hi all, how do I write if not P then Q in symbols?
is it
~P -> Q?
vital flume
if you are trying to write not p implies q then yea
weary tiger
dont get the inductive step
which line?
you assume the given statement is true for everything uptil k
mighty flame
So I had this set,
where Vi = [ -1/i , 1/i]
and the answer was [0,0]
but I was wondering why isnt this an empty set?
how can you have an interval between 0 and 0
brave rock
0 is the only element of [0, 0]
You may be confusing this with (0,0), which is empty.
mighty flame
oh true
proud gazelle
which line?
the inductive step is used in the 2nd line. i suppose he wasn't understanding that.
what's being used is that
$T_k<2^k ; T_{k-1}<2^{k-1} ; T_{k-2} < 2^{k-2}$
vital dewBOT
agilepotato
weary tiger
the inductive step is used in the 2nd line. i suppose he wasn't understanding th...
the inductive step is the entire third process. The second line is just using the strong induction hypothesis.
proud gazelle
the inductive step is the entire third process. The second line is just using th...
oh okay
vital flume
im crying
vital flume
i got a problem on a midterm that ive solved in the textbook and its the most valued problem
tropic mango
tropic mango
all of these are binary relations on A
grand totem
What is juxtaposition supposed to stand for here? Composition?
tropic mango
What is juxtaposition supposed to stand for here? Composition?
yes
grand totem
In any case, really no particular hints to give here. It's a standard double inclusion argument + some definition juggling (with composition and union)
So proving the ⊆ one might start with "Suppose (x,z) in ρ(σ∪τ)", then apply definition of composition (which will provide you with a y s.t. and so on and so forth)
weary tiger
So, I've been trying to rewrite f(a, b) in terms of a sum of products, divided by a product
I think it's possible
the sum would have (b - a) summands
and the inner product would have... (b - a - 1) factors?
but beyond that, idk
something of this form?
verbal crystal
Did I answer this right?
weary tiger
Did I answer this right?
no?
the outer loop is equivalent to multiplication by 5
...nvm, yes
lol
verbal crystal
What about this one?
the middle loop is based on 'i' which is based on 'n', so I'm assuming it is n * n
verbal crystal
so would it be 3 * n * i?
last flicker
well no, i is a dummy variable that changes as the program completes
So if you actually think about what the program does
initially i is 1
and so the inner loop never does anything, since j initialised at 1 is never less than i
then i is incremented to 2
and so the inner loop calls beep(); beep(); beep() once
Then, i is incremented to 3, and the inner loop calls beep(); beep(); beep() twice
and so on until i=n, after which the program terminates
i.e. whe i=x, beep() beep() beep() is called x-1 times
verbal crystal
3 * (n - 1)?
last flicker
no. you're going to have to represent it as a sum, and then you'll be able to change it into a closed form
3(n-1) is how many times beep() will be called at the final iteration of the outer loop, but there's also all the prior calls!
verbal crystal
like this?
last flicker
Almost, assuming the thing in the sum is 3, but the upper index on the inner sum is wrong
remember that j<i is strict, so beep() beep() beep() isnt called when j=i
verbal crystal
last flicker
:O well that counts even more than you had before... the upper index should be i-1
verbal crystal
Hmm I guess I should listen to my gut more often, I had that initially
So would I put a 3 next to these 2 sums?
like this:
last flicker
That's it yeah
verbal crystal
I'm not sure what to do at this point. I don't have much experience with summations
I know some of the closed formulas but I haven't done anything with 2 sums next to each other before
last flicker
Well, the inner sum is just the sum of i-1 copies of 3, so its just 3(i-1)
so now the sum is $$\sum_{i=1}^n 3(i-1)=3\sum_{i=1}^n i-1$$
verbal crystal
is that from this?
vital dewBOT
Sneaky
last flicker
is that from this?
yes
Then, you might have a formula for $\sum_{i=1}^n i$? If not, its very useful to remember that $\sum_{i=1}^n i=\frac{n(n+1)}{2}$
vital dewBOT
Sneaky
last flicker
can you see how you could apply that formula here
verbal crystal
**Sneaky**
Yeah I remember this one
and I think I remember the closed forms for i^2 and i^3 as well
last flicker
So what's your final answer
verbal crystal
$\frac{3n^2 - 3n}{2}$
vital dewBOT
HyperFirez
last flicker
Yup, and lets check thats consistent with the actual program:
gives this output
so with n=5 we would expect acc to be (3(25)-3(5))/2=30
which is exactly what we got
so thats it!
verbal crystal
awesome, thank you very much. I understand how to do these now
unreal stump
LEM moment
analog hound
If one asks to find solutions to a linear equation with coefficients > p in Z/pZ, what exactly does that mean? Find values of the unknowns for which the LHS and RHS are congruent mod p?
unreal stump
Well in Z/pZ coefficients>p "exist"
It's just they will be equal to a number <p
For example , 17=6 in Z/11Z
umbral blade
Would “for all students at a college x, it is not true that all students at a college x are registered to vote in Alaska” be an incorrect translation of the proposition? To me this doesn’t make sense because the negation would be “there exists a student at a college x such that student x is registered to vote in Alaska”. And I believe this negation doesn’t actually negate the translated sentence . Every student vs all students?
analog hound
Well in Z/pZ coefficients>p "exist"
Right, so just reduce the coefficients and then find solutions which have both sides congruent?
unreal stump
Yes
analog hound
I see, thanks
unreal stump
Well if you want a proper explanations, elements of Z/pZ are really sets and not numbers
You identify each set with some element( some number < p) and the operations on them feel like you are operating on numbers they are identified with
analog hound
So on this view, Z/pZ = {[1], ..., [p-1]} (or Z/pZ is the set of "equivalence classes mod p"), and a_1x_1 + ... + a_nx_n = d in Z/pZ iff the LHS and RHS are elements of the same equivalence class. Does that sound right?
atomic igloo
@unreal stump could you help me out with logic a little
unreal stump
So on this view, Z/pZ = {[1], ..., [p-1]} (or Z/pZ is the set of "equivalence cl...
yes
That's the same as saying lhs and rhs are equal congruent p here
@analog hound
Because a and b are in same equivalence classes iff a=b mod p
analog hound
Ok, I see now. People seem to usually define Z/pZ either as {1, ..., p} with the appropriate multiplication and addition operations, or as the integers with a special equivalence relation/a set of equivalence classes, and it's sort of confusing
unreal stump
So you have equivalence classes and if you represent each class by the remainder mod p you get the first one
It's literally instead of [1],you talk about 1
But everythin else remains the same
analog hound
Oh, I hadn't thought of that. Thanks!
old pilot
Let A be the set of all positive integers less than or equal to A's cardinality.
For |A| = 0, we have P(A) = P({}) = {{}} which has cardinality 2^0 = 1, obviously.
For |A| = k, then we say |P(A)| = 2^k, P(A U {k + 1}) = P(A) U {B in P(A) union {k+1}} which has cardinality |P(A)| * 2 = 2^(k+1)
Does this work for 'Prove by mathematical induction that |P(A)| = 2^(|A|)'
elder berry
Let A be the set of all positive integers less than or equal to A's cardinality....
Looks good, even though trivial you can emphasize P(A) and {B in P(A) union {k+1}} are disjoint, hence |P(A)|+|P(A)|
old pilot
Looks good, even though trivial you can emphasize `P(A) and {B in P(A) union {k+...
Yeah I could just say that every set in P(A) can only contain elements in A, and since k+1 is not in A, no set in P(A) contains k+ 1, but every set in the other set does by definition, hence the two sets have all different elements and are therefore disjoint, and the cardinality of the union of two disjoint sets is |A| + |B| or in our case |P(A)| + |P(A)| = 2 * |P(A)|
elder berry
mhm
{B in P(A) union {k+1}} is also kind of a weird notation, no?
{X U {k+1} : X \in P(A)} would work better ({X U {k+1} | X \in P(A)})
old pilot
`{B in P(A) union {k+1}}` is also kind of a weird notation, no?
It is but I suppose aslong as it gets the point across
It's not for homework anyway it's just me studying so aslong as I can understand it in my notes it should be fine
elder berry
right, just don't confuse it as B in (P(A) union {k+1})
old pilot
ill keep it in mind though for proper exams thanks
elder berry
np
wary scarab
Can someone help me find this limit?
limpid fossil
how are they getting this closed form formula??
near plume
weary tiger
can someone help me with addition of two's compliments in binary ? like this
cerulean vessel
can someone help me with this
night stream
can someone explain why we subtract 5 and not add?
stray reef
inclusion-exclusion principle
last flicker
can someone help me with this
could use ivt
This is more like a calculus solution then a discrete math solution so maybe there's a more discrete way to do it
but ivt would work fine
brave fjord
This year Apple has launched iPhone 14. There are 4 different colors (Silver, gold, space black, purple) of iPhone 14 Pro Max and iPhone 14 Pro. Also, there are 5 different colors (Midnight, blue, starlight, purple, red) available for iPhone 14 plus and iPhone 14. How many different types of phones are available this year?
coral parcel
... restricted to Apple phones with a "14" in their name?
stray reef
yes, obviously, because no other phones exist in the world. don't you remember that, tropo?
coral parcel
I must have forgotten for a moment.
somber heath
how do I express ${ \underbrace{H, H, \ldots, H}_{\text{n times}} }$ in a shorter form?
vital dewBOT
illuminator3 👻(#eric4honorable)
brave rock
{H}
A set does not count multiplicities of elements: an element is either in there once, or not at all.
somber heath
A set does not count multiplicities of elements: an element is either in there o...
ahhhh
thanks
sweet thunder
Can someone help me on this question. I have to verify that my conjecture is correct but I keep getting stuck on inductive step
sudden minnow
what is your actual sequence?
outer kayak
for a combinatorial proof how do I glue the LHS and RHS together? I have an assignment due very soon and im scrambling to figure it out
midnight mural
Guys can someone help me change this to predicate logic
Professor Walt is the advisor of all the students that work on the project Q
thats what i di
did
but am not sure about its correctness
for all x (work(x,q) -> Advisor(walt, x))
A(x, y) = x is the advisor of y
W(x, y) = x works on project y
jovial harbor
never seen arrow notation use a dash on the arrow, what does that mean here?
im guessing its because its partial
hybrid glen
Hello, I am really, but really struggling with discrete maths, I just can't seem to understand the logic behind everything or just what to write in general. I was wondering if anyone has any good youtuber, book (if possible free/in pdf) to advice me so that I can perform well. I am struggling with exercices and exams which may lead to me being kicked out 
unreal stump
never seen arrow notation use a dash on the arrow, what does that mean here?
Yea,It's partial function
solar patio
can someone help me with this question ?
i proved a with a acounter example but i dont know how to prove b ) with set proof
solar patio
I did this
unreal stump
That's the proof for (b)
solar patio
I know that this is in french but could you tell me if this is wrong for a?
And thank you for answering btw really kind of you
unreal stump
Well a) really means "{1,2,3,4} works but other values of C also work"
So that mean if C were phi, AUC has to BUC for the premise to be true
or if C were {1} also,they have to be the same
b) means "Ok,It's fine to have exactly one value of C work for the premise to be true"
unreal stump
yes
unreal stump
yes
solar patio
Thank you so much
if its not too much to ask could you check if what i did here for c is correct too ?
olive wren
This is not a proof
You only showed that for specific sets A and B which don’t equal each other, (e) doesn’t hold
You need to show this for all A and for all B
As a hint, think of a way of finding A if you know AUC and AnC
hybrid glen
Hello, I have fibonacci's sequence and lucas sequence and I must demonstrate that :
Ln+1 - Ln-1 = Fn+1 + Fn-1 for every 1 <= n
But I can't seem to understand how to demonstrate
stray reef
induction perhaps
weary tiger
Can somebody tell me what is meant by substitution here? If the left-side of the equality = a/b why is b/b being subtracted?
last flicker
what is meant by substitution here
all theyve done is use the fact that for any b not equal to 0, b/b=1. Thus, they can replace the 1 by a b/b
last flicker
weary tiger
hey guys
I'm struggling so hard on this problem - not looking for solutions but they'd be welcome
On the first day of school, a teacher writes the numbers 1 and 1 on the blackboard. Every day starting on day two, she asks two children to come to the blackboard. Each child stands in front of one of the numbers. One child is allowed to add or subtract 2 to her number. The other child is allowed to add or. subtract 1 to her number. For example, on day two, it is possible the numbers are updated to : 3, 2. Prove that it is impossible that the numbers on the board are 1, 1 after an even number of days.
weary tiger
I'm struggling so hard on this problem - not looking for solutions but they'd be...
A push in the right direction might be enough, I simply don't even know where to begin- my greatest difficulty is in dealing with two numbers
sudden minnow
A push in the right direction might be enough, I simply don't even know where to...
think of it this way, you have on day 1 two digits with odd parity
and every day after day 1, one of the digits will have same parity and the other will change parity
weary tiger
and every day after day 1, one of the digits will have same parity and the other...
Amazing, thank you so much.
spring elk
answer syas its not because its not transitive
but its not reflective either right?
actually
im a bit confued
what set will even be in R?
it says x y on A if x and y are in the same subset Does this mean:
nvm i think i get it.
sudden minnow
this is indeed ambiguous phrasing, could mean any of the A_i or all of them
spring elk
this is indeed ambiguous phrasing, could mean any of the A_i or all of them
ok this makes more sense
i initially thought it has to be in all A1 A2 and A3
but then it would just be empty
thanks
sudden minnow
not sure if it would be empty
sudden minnow
any diagonal
(1,1)
ok, so I don't know if this is about
xRy iff (x in A_i iff y in A_i )
but I think this is what it is trying to say
in this case it would be an equiv relation
spring elk
their answer does say its not so its just in either or all
sudden minnow
ok, now I get it, the author tried to show something that looks like a partition but isn't really, and wanted to define the equiv relation on A and ask you to find why it fails
the issue is the authors wording does actually read really badly since the sets aren't even a partition
so yeah it is supposed to be read "any A_i"
and that is how it fails
spring elk
so in the end R is all sets where (x, y) are elements of either A1xA1 or A2xA2 or A3xA3 right?
spring elk
yeah
sudden minnow
and I just reverse engineered to understand what author tried to say
spring elk
im confused, are they saying [1] is set of elements {1, 2, 4} x {1, 2, 4}? because if thats the case how is this true given that the definition of partition is
sudden minnow
no [1] would just be {1, 2, 4}
spring elk
is {[1], [3], [5]} supposed to equal R?
sudden minnow
no
R is a subset of A^2, {[1],[3],[5]} is a set of subsets of A
they dont even live in the same dimension
spring elk
i see. thanks
sudden minnow
don't get confused, partitions and equivalence relations are sort of the same thing because you can easily go from one to the other, but they aren't the same mathematical structure
every partition induces an equiv relation x~y iff they belong to the same part of the partition
every equiv relation induces a partition which is just set of equiv classes
spring elk
why is [1] nt {1, 2, 4, 7} ? I can have (1, 2) as an element so?
sudden minnow
you sure
spring elk
oh nvm..
sweet thunder
Where am I messing up? I’m given the equation on the upper left and I said it’s =2^(k-1) but when I try to verify with induction I get stuck
sudden minnow
your P(k) statements are weird
a_n = a_(n-1) + 2a_(n-2) should be a fact given a priori
and the thing you want to prove should presumably be a_n = 2^(n-1)
sweet thunder
Yes I want to prove 2^(n-1) by induction. I think the problem I’m having is how would I show the “next step”?
sudden minnow
so you are given a_k = 2^(k-1) for all k less than or equal to n
and want to show a_(n+1) = 2^n
so first, let's expand a_(n+1)
by definition, a_(n+1) = a_n + 2a_(n-1)
but we know by hypothesis, a_n = 2^(n-1)
and a_(n-1) = 2^(n-2)
and we are pretty much done
sweet thunder
Ohhh, so I would need to take a step back for a_(n-1).
Would I need to argue by strong induction then? I assumed I had to make the left hand side = the right hand side
sudden minnow
this is strong induction yes
but strong induction is just a better version of induction (actually theoretically the only version) so it is not really extra work
sweet thunder
Thank you so much!
sudden minnow
np
I think you confused yourself too much with all the terminology and abstract symbols
play around with the sequence first
coral parcel
"Show" + "without proofs". How does that even compute?
coral parcel
Depends completely on which knowledge about the tree you have to prove it from.
maiden python
was kind of thinking that
maiden python
Depends completely on which knowledge about the tree you have to prove it _from_...
my question is to general
coral parcel
Doesn't change the fact.
weary tiger
Still having tremendous difficulty with this question. Spent too many hours on it ugh
I'll upload my attempt in a moment its all messy rn
Inductive Step shows (3n)!/6^n = b_n, but then what? I genuinely don't know how to proceed
weary tiger
oops
elder berry
$b_{n+1} = \frac{(3n+3)(3n+2)(3n+1)}{6} \cdot b_n = \binom{3n+3}{3} \cdot b_n$
vital dewBOT
peaceGiant
elder berry
can you motivate a combinatoric reason why this would be true?
hint: ||First choose 3 candies for the very first bag, the rest of the candies you already know in how many ways you can put them via induction||
weary tiger
Thanks so much I appreciate it.
cold mesa
obtuse lance
try to work a problem, if you get stuck you can ask here about what you've tried, maybe someone will help
weary tiger
Stuck on this problem as well. Not sure how to move on from here...
weary tiger
Minor nitpick: what are you assuming to hold before moving on to the inductive step? You might want to write that down. Also you can use some more words instead of just single words.
weary tiger
Minor nitpick: what are you assuming to hold before moving on to the inductive s...
Yeah thats my difficulty
Say your statement that you are proving, is P(k). You have shown that from k = 8, P(8) is true. Now for inductive hypothesis you want to assume P(k) is true.
That shouldn't be difficult.
weary tiger
Minor nitpick: what are you assuming to hold before moving on to the inductive s...
Yeah I can't get there lmao
The goal is to express $2*(n^2log_2(n) as (n+1)^2log_2(n+1)$, right
vital dewBOT
OA
stray reef
jesus christ what is this notation
chrome sand
xD
stray reef
i thin there's an extraneous comma right before the intersection symbol and also an extraneous opening parentheses
anyway, assuming you meant {1, 3, 14, {1}} ∩ {1, {1}, {14}},
yes that's {1, {1}}
chrome sand
thank you
what the difference of 14 and {14}
{14} is a set itself
and 14 is jsut a number right?
stray reef
14 is a number, {14} is a set with one element
also i think you meant difference between and not difference of
chrome sand
jep sorry
can i ask you another question?
i thought the intersection would be {3,4,5} but why is it empty
woeful scroll
any good way to find all minimal edge cut sets of a graph?
stray reef
i thought the intersection would be {3,4,5} but why is it empty
neither 3 nor 4 nor 5 themselves are members of P({3,4,5})
covert bolt
I dont really understand the solution for 6b. I thought a column move means a single tile moving up/down
how does it affect 3 pairs of tiles?
elder berry
I dont really understand the solution for 6b. I thought a column move means a si...
I assume they mean this
whenever you make a column move, you'll have ...J K L M O... -> ...J L M O K
the relative order of the pairs K - L K - M and K - O will change
(K preceded all of the other letters before a column move, but after the move it is their relative* successor)
gentle bronze
dont understand how f1(0) = 2, f1(1) = 4 etc...
brave rock
That is a definition.
Note they write "... is a perfectly good function." at the end.
gentle bronze
That is a definition.
i dont get tho how it equals that
amd i supposed to just accept it?
gentle bronze
ight cool
gentle bronze
@unkempt elk aplogies to ping, just wanna carry on from ur msgs.
the thing i dont get is this 0 part here
and what it acc means
brave rock
It means that f(x) = 0 if x is not in Q.
gentle bronze
It means that f(x) = 0 if x is not in Q.
oh right
gentle bronze
It means that f(x) = 0 if x is not in Q.
could u explain this proof for me plz - what ive higlighted
i dont get why whats said is happening and whats acc going on
brave rock
What about the proof is confusing you?
gentle bronze
What about the proof is confusing you?
why have we picked nz = 2z. and nz = 1 - 2z
like im just lost
whats going on lol
brave rock
why have we picked nz = 2z. and nz = 1 - 2z
Because those give us the result that we were looking for
I'm afraid you're gonna have to be more specific than just saying you're lost
Maybe you should review what being onto means.
gentle bronze
Maybe you should review what being onto means.
ik what it means
brave rock
Then if you have any specific questions, feel free to ask.
gentle bronze
Then if you have any specific questions, feel free to ask.
how is (1-x) / 2 odd?
brave rock
Who said it was? It's typically not odd.
gentle bronze
Who said it was? It's typically not odd.
oh yh misread sry
sudden minnow
start with assuming q
deduce r
hence, you've deduced q implies r with no assumption
I am assuming this was a given rule in your class
spark silo
im confused and extremely rusty, this questions asks for a proof by contradiction, can i get some help please :c
consider graph g below, with the 3 edges x/y/z. Prove that any perfect matching in G must contain atleast one of the x/y/z edges
i need to use this theorem, but i dont understand it fully
Tutte's Theorem: a graph has a perfect matching if and only if every proper subset S of vertex set G, the number of odd components of G - S is at most |S|
do i find the negation of tutte's theorem or do i negate the original statement at the start to find a contradiction
spring elk
start with assuming q
ah ok. I can only do this for implication right (->). if it was q and r i couldnt do the assume q. is that true?
sudden minnow
yes
spring elk
alright thanks
rigid oriole
do i find the negation of tutte's theorem or do i negate the original statement ...
If you assumed tutte's theorem is false and somehow arrived at a contradiction, you will have proved this theorem, not your statement.
No, you need to assume what you're trying to prove is false and proceed. ie. there exists perfect matching in G which contains none of those edges
spark silo
If you assumed tutte's theorem is false and somehow arrived at a contradiction, ...
oh right ofc that makes sense. havent done proofs in like a year and a half mb
then i need to find a coutnerexample where the "false" statement is wrong, right? so i need to find a perfect matching in G which contains no xyz edges. i dont know how to go about doing that either tho lol.
if you get rid of xyz edges arent the the triangle/pentagon(?)/septagon(????)/triangle still a subset because they're connected by the outer vertices? soo i dont see how the xyz edges change anything.
Also i have no idea how to use tutte's theorem, this is my current understanding
G = 20 S = 3/5/7/3
G-S = 20-(3+5+7+3) = 2
|S| = ????
rigid oriole
(I don't know much graph thry or what perfect matching is)
rigid oriole
the same way you do in decimal (base 10) division
astral bone
the same way you do in decimal (base 10) division
Could you show an example?
rigid oriole
no, you can probably find one online
astral bone
I can do it it base 10 but not in base 2
astral bone
no, you can probably find one online
I can not
rigid oriole
you literally do exactly the same thing
where you would multiply by 10... multiply by 2
for moving decimal places
or divide
swift kettle
for c i did algebra and got root(x) * root(y) = 0
which implies either x = 0, y =0 or both = 0
but is the negation of positive nonpositive or is it negative
because if its nonpositive, then 0 is nonpositive which shows the contrapositive is true, but if negation of positive is negative, then im lost
wicked bolt
but is the negation of positive nonpositive or is it negative
it's nonpositive, so that's enough for the proof 🙂
sudden minnow
whats wrong with that
spring elk
any tips on how ot tackle these kind of problems?
lament canopy
whats wrong with that
I guess I’ve never seen that before. Do you just start summing with a number r indices before the indicated lower bounds?
lament canopy
I mean, it seems like you would have to for the two terms or be equal.
sudden minnow
you just sum from m+r to n+r, I don't see the issue
by issue I mean what you are confused about
,,\sum_{k=5}^{8}a_{k-4} = \sum_{k=1}^{4}a_{k} = \sum_{k=-99999}^{-99996}a_{k+100000}
vital dewBOT
lems
lament canopy
by issue I mean what you are confused about
Thanks - that’s what I thought it had to be, but I don’t recall seeing that notation before, where the first term being summed had an index lower than the lower bounds.
astral moss
"Determine all the numbers x and y for which the following statements are all true:
As a result, formulate a statement which exactly specifies all solutions."
Can anyone give me a headstart on how to begin to tackle this? Im not asking for end results, just tips how to do it
(Also original question was in German, I DeepL translated it to above it
oblique rock
How do I go about proving this? Can I use complete induction or something very simple?
brave rock
Hm, I'm not convinced induction is very helpful here
I think you can refer to the definition, and what you know about multiplication :)
oblique rock
I see two cases here a < n and a = n. Also that there exists b in Z s.t. n = b * a
swift kettle
for this question, im having trouble with proving the other direction of the double subset inclusion proof
im not sure where to go from here
also, can someone check to see if my working is valid for the first direction of the proof
elder berry
all of the laws that you use work both ways, so you can start with the end of your first proof and go backwards (though not necessary, you can just add <=> everywhere)
also a soft reminder to not mix up the symbols when dealing with sets as oppose to logical propositions
if $x \notin B \cup C$, then $x \in \overline{B \cup C}, \quad (x \in (B\cup C)^c)$
vital dewBOT
peaceGiant
elder berry
just mentioning this because not(B U C) doesn't make sense and if your professor is strict, they will take off points
swift kettle
**peaceGiant**
which step of my working is this referring to?
spring elk
I solved it by assuming ~t and then did all possibilities until i got the answer. Not so efficient. I will try what u said
spring elk
Question: I have to say "set A does not contain any prime number"
is the way i did it right?
this is their answer
are these logically equivalent?
could u expand more on what u did? what contradiction are u trying to get?
are u assuming ~t and q to be true?
zinc timber
Hi, I've modeled a mathematical function F(y) for which I would like to get the y so that F is minimized (I'm not searching for the absolute minimization, I'm more searching for an iterative algorithm like gradient descent that gives me a relative minimum)
my y are discrete, so F isn't obviously differentiable and I can't use gradient descent
what minimization (or optimization) techniques are used in a discrete problem?
lavish dagger
I am trying to help someone else solve question 1 (she's not on discord), but I don't know much about posets. My question is basically where to find examples to follow, or if anyone here would like to help me with sort of a "step-by-step"-guide?
sudden minnow
I am trying to help someone else solve question 1 (she's not on discord), but I ...
it is just checking the 3 axioms of a poset
e.g. say you have x < y and y < z in X
then you know f(x) < f(y) and f(y) < f(z) in A
but A is a poset, so you can use the transitivity of the order in A
and that is one axiom done
sudden minnow
my y are discrete, so F isn't obviously differentiable and I can't use gradient ...
what does F take as input
integer?
zinc timber
yes y is a natural number
sudden minnow
differentiating can still give insight, even if the function only takes natural numbers as input
or you can use the forward difference operator, the discrete analog of differentiation
lavish dagger
it is just checking the 3 axioms of a poset
thank you for helping!
sudden minnow
thank you for helping!
np, just have to be careful with antisymmetry, that is when you use injectivity of f
blazing rose
Because of transitivity I have to prove, that for all x,y,z, if (x,y) is element of Rho ° Sigma and (y,z) is element of that, then (x,z) must also be.I have proved that there is (x,a) and (y,b) in Rho and (a,y) and (b,z) in Sigma. Therefor there is (a,b) in Sigma°Rho and Rho°Sigma. If I continue my proof by doing this for (x,b) and (a,z) and in the end for (x,z), I get: (x,z) is element of Rho°(Rho°Sigma)°Sigma
Does anyone know where I had a misconception?
because what I wanna prove is (x,z) is element of Rho°Sigma
brave rock
Therefor there is (a,b) in Sigma°Rho and Rho°Sigma.
Why?
Oh, my bad. I see why.
Well for what it's worth, you've got no "misconception," you just haven't proved what was asked.
You can prove this without any reference to the elements of the set.
Hint: a relation R is transitive if R o R is a subset of R.
blazing rose
Hint: a relation R is transitive if R o R is a subset of R.
so u r saying its enough if I somehow prove (Rho°Sigma)°(Rho°Sigma) is a subset of Rho°Sigma?
weary tiger
is this circle sign "exclusive or" or "inclusive or"?
elder berry
is this circle sign "exclusive or" or "inclusive or"?
exclusive
vital dewBOT
peaceGiant
elder berry
is this circle sign "exclusive or" or "inclusive or"?
now that I look at that not p xor q (which is kinda reminiscent of an implication) it might be the case that the notation being used there is for an inclusive or. However I doubt it
brave rock
so u r saying its enough if I somehow prove (Rho°Sigma)°(Rho°Sigma) is a subset ...
I can see you're trying to DM me. I don't like being DM'd for questions about math. Please post your thoughts here; that way, even if I'm not around, someone else can come and help.
blazing rose
I can see you're trying to DM me. I don't like being DM'd for questions about ma...
sorry, I understood the proof of if R o R being a subset of R then R is transitive
but I just dont get how to apply it to this example where I already have a composition in the original R
brave rock
OK I'll just show you the proof I guess, why not.
$(\rho \circ \sigma) \circ (\rho \circ \sigma) = \rho \circ (\sigma \circ \rho) \circ \sigma \subseteq \rho \circ (\rho \circ \sigma) \circ \sigma = (\rho \circ \rho) \circ (\sigma \circ \sigma) \subseteq \rho \circ \sigma$.
vital dewBOT
Boytjie
blazing rose
$(\rho \circ \sigma) \circ (\rho \circ \sigma) = \rho \circ (\sigma \circ \rho) ...
ahhh
the last one is also due to the transitivity law u mentioned before right?
brave rock
Yes.
blazing rose
alright great I understood it all I think, thanks for help
brave rock
No worries
blazing rose
potentially, with the method I mentioned before
w
would it be possible to get to the conclusion of the proof in any way?
with referring to the elements etc.
brave rock
Yes, you just apply the definition of rho o rho o sigma o sigma and use transitivity of rho and sigma