discrete-math

[final cliff]

The proof is asking you to essentially show, given your formulas for k that $b_{k+1}=2^{k+2}-1$ is true.

[vital dew]

DootDooter

[wide vine]

well that is why I was saying how that every case of b_n = b_k when n = k

[final cliff]

I'm not sure I understand what you mean?

[willow fog]

n typically equals k in induction

k is the index of induction while n is the index of the sequence

it's like "the kth step is when n=k"

[sturdy walrus]

Hey, I don't mean to interrupt what's being explained above.. but whenever someone gets the chance, please take a look at this. I'm not really sure what to go about (A^x)^x here.

[final cliff]

It's sort of complicated. You're trying to leave k in general because the inductive step is to prove $\forall k\in\mathbb{N}(P(k)\implies P(k+1))$

[vital dew]

DootDooter

[final cliff]

n is just being used to define b as a function I suppose.

[wide vine]

I was taking it as these are 2 different "functions" 1 being recursive and not (not sure the correct word for the other) and show how all cases for using the non recursive one will equal to that of using the recursive one :v (assuming n = k). Yeah idk if it makes sense.

[final cliff]

Oh I see what you mean.

Yeah that's one way to look at it I guess.

You would show they have the same domains (which is obvious)

Then show on the same inputs each expression gives the same output (roughly speaking).

And this is totally doable by induction.

But you might want to rename one of the sequences, because calling them both b would be super confusing.

Might be more trouble thinking of it in those terms though?

Since really you just gotta show in your inductive step that 2^(k+2)-1 is b_(k+1) with a bit of algebra and some inductive assumptions.

[nova venture]

can anyone help me check if this proof is valid?

[final cliff]

Are you sure line 1 is the assumption you wanna make?

[nova venture]

using an universal instantiation is all i can think of when proving subsets, im really not sure tho kinda stuck on this question

[final cliff]

So if you wanna prove A is a subset of B you'd usually start by assuming x is an elt of A.

If you assume x is an elt of some other larger set than A it might not work.

[nova venture]

so instead of assuming an element is in divisors(b) i should assume the element is in b?

[final cliff]

Nah, I mean the subset proof you're trying to do involves a smaller set than divisors(b) as far as I can tell?

<@&268886789983436800>

[ember obsidian]

b&

[final cliff]

Thank you rocket ❤

[final cliff]

So to be specific the lhs of your subset relation you're trying to prove is divisors(b) intersected with divisors(a-b) rather than just divisors(b)

[nova venture]

wouldnt line 3 show that? bc i showed the relation of divisors(b) intersection divisors(a-b)

[final cliff]

I don't see how line 3 shows that.

Like 2|4 but 2|5-4 is false for ex (a=5,b=4,x=2)

Well ignore my crappy example it probably doesn't make much sense lol.

[nova venture]

sorry so what should i do to show this, im kinda confused with this topic

[final cliff]

I think the issue is that you started from the wrong assumption at line 1 and got led astray is what I'm saying.

Once you fix that you should be able to use the defn of divisors(n) to show x is an elt of divisors(a) and divisors(b) I'm thinking.

[nova venture]

ok i will try that, thank you!

[sturdy walrus]

I did a somewhat similar proof but I don't know how that'd apply to this one

[steady path]

This is fine, maybe some more sentences. What did you attempt with the other problem, showing that the complement of the complement is the original set?

[sturdy walrus]

This is my attempt on it

@steady path

[steady path]

I will use $A^c$ for "the complement of $A$ in $X$". You might start by taking an arbitrary $x \in (A^c)^c$, and showing that $x \in A$.

[vital dew]

matthew

[sweet steeple]

Can someone have a look at my proofs and tell me if tere are any holes in my logic?

thank you

[unreal stump]

How do you know you can find n1,n2 such that f(n1)=b1 and f(n2)=b2 in theorem 2
@sweet steeple

You can't prove theorem 2

Your proof gives you that h is injective restricted to range(f) . You can't say anything more

[ember obsidian]

also u can prove thm 1 directly instead of w/ contradiction

[unreal stump]

Theorem 3 proof is completely wrong

[sweet steeple]

Yeah I see ok I'll fix

[unreal stump]

You repeat what you wrote as proof for 2nd theorem and say since range(f) is the whole set the statement is true

For 2nd one pick a counterexample

Pick a non surjective f

[sweet steeple]

Counter example?

So like a contradiction?

[unreal stump]

Yea,A f and h which satisfies the premises but not the conclusion of the theorem

[ember obsidian]

ur wording is confusing

[unreal stump]

This?

[ember obsidian]

"proof." implies ur supplying a proof which validates the statement

but at the end u say its false

[unreal stump]

mb

[ember obsidian]

in which case u must give a counterexample to support ur claim

[sweet steeple]

Yeah idk what I was thinking

[ember obsidian]

but spoiler, thm 3 is actually true

[twilit sierra]

How do u concatenate n-1 . n

[stray reef]

@twilit sierra what do you mean

[twilit sierra]

If i have a^n-1 concatenation a

It becomes a^n how

[stray reef]

you have n-1 copies of a and you attach one more a to it, what do you get?

@twilit sierra

[sleek loom]

If ‘f’ is a surjective function f: A -> B, is the domain of f equal to the set A?

[obtuse lance]

try to come up with examples

[sleek loom]

I’m pretty sure it’s not but there’s this proof I need to do, which is easily disproven if the answer to my question is no

@obtuse lance

So I’m confused af

[obtuse lance]

sounds good, show what you've got so far then

[sleek loom]

$\phi$ is a surjective function $\phi: A \rightarrow B$. $A_1 \subseteq A$. I need to prove that $A_1 \subseteq (\phi\phi^-1)(A_1)$

[vital dew]

Orian

[obtuse lance]

looks like you're over thinking it, try to come up with some examples of specific surjective functions first

you're like getting lost in the sauce or somethin

[sleek loom]

but if $A = [1, 2, 3], B = [1,2], A_1 = [3]$ and $\phi=((1,1),(2,2))$ then $\phi$ is surjective and $\phi\phi^{-1}(A_1) = \emptyset $

sorry writing in latex takes me so long

here's the example

[vital dew]

Orian

[sleek loom]

and A_1 is not a subset of the empty set obviously

[stray reef]

first off you are misusing brackets

and parentheses

[sleek loom]

yes I know

I tried using {} but it didn't show up

but its readable

[stray reef]

it's \{ ... \}

second, what you wrote as phi is not a function from A to B at all

[sleek loom]

oh nice

what

[stray reef]

it's not a function from A to B. phi(3) is left undefined.

[sleek loom]

why does it have to be defined?

[stray reef]

it's part of the definition of a function

informally, a function must associate an output to every input

and every input means every input, not every input except the number 3 just because you happen to be triphobic.

[sleek loom]

informally?

yes fuck that number

the book I'm using specifically mentions the existence of "partial" functions in which their domain is a subset of the original set

[stray reef]

well phi is a partial function from A to B

but it is not total

and if you just say function without any context people will assume you are talking about total functions

[sleek loom]

so it's not really by definition then

[stray reef]

??

[sleek loom]

or if I'm saying $\phi$ is a function from A to B then $\phi$ is by definition a total function

[vital dew]

Orian

[stray reef]

yes that's right

by default when you say function you mean total function

if you want to talk about partial functions then you have to mention that explicitly

[sleek loom]

damn

thanks a lot

[tardy comet]

Is there a way to "see" which graphs are isomorphic to each other?

[austere cedar]

the short answer is no. You can check something like same number of vertices of each degree, but that doesn't help always (and it doesn't help in this case). There is no polynomial algorithm known...

for this special case ||it might help to look how the remaining graph looks like if you remove one vertex and all its neighbours||

[jolly rivet]

Hello! Would this be a valid way to show my solution

[tardy comet]

Thanks!

[native sable]

yes

[jolly rivet]

Thank you!

[weary tiger]

How can I prove a product of two integers is an integer? I could give examples but that wouldn't be considered correct way to prove it

[pale epoch]

you will have to refer back to the definition of integer and product

[jolly rivet]

Would this be a valid statement in my proof

I know that if x is an element of P(A) then it is an element of A

but is it true that A is a subset of P(A)

or like is that the right wording

[rain vessel]

I think it's wrong

Because if I understoord correctly, x can be a part of A but not necesarilly be a part of P(A)

[jolly rivet]

I think like A is a set inside the set P(A)

Oh P(A) contains all of A's subsets

[jolly rivet]

Would I need to clarify A is not the empty set

[coral parcel]

(Sorry, I wrote nonsense).

[jolly rivet]

I changed the line to this

[coral parcel]

The fact that x is an element of P(A) means that x is a subset of A, no more and no less.

The changed line looks right.

But "x must belong to B" looks wrong.

You can conclude that x is a subset of B, not that x is an element of B.

[jolly rivet]

Ok I will make that change

and would that still make the conclusion correct

[coral parcel]

Looks like you're still writing "B is a subset of P(B)" which is not true in general (just like it wasn't for A).

[jolly rivet]

Oh true

is there a way to describe the relationship between them

Like since B is ___ of P(B)

[ember obsidian]

theres no need. once u say x is a subset of B u can immediately say x is in P(B)

[jolly rivet]

Oh true

Also for my other proofs I wrote stuff like:

Also since x is an element of A and A is a subset of C, x belongs to C

I would need to change that to like

Also since x is an element of A and A is a subset of C, x is a subset of C

[ember obsidian]

no, the 2nd requires x to be a subset of A

and hopefully the change is due to u knowing the difference in subset vs element

[jolly rivet]

So could I keep the first statement the same

Oh so when I say x in an element of P(A) that means that x is a subset

[ember obsidian]

yes, the elements of P(A) are precisely the subsets of A

[jolly rivet]

And if in another example I say x is an element of A it means that x is a regular element

like it's not a set

[ember obsidian]

not necessarily

a set can be an element of another set

[jolly rivet]

oh true

[ember obsidian]

{{1},2}

[jolly rivet]

but like it doesnt need to be a set

where as a x in a power set it needs to be a set

[jolly rivet]

true

[ember obsidian]

yes, a subset of A is a certain kind of set

[jolly rivet]

Thank you!

And like if x belongs to A and A is a subset of B then x belongs to B

or is there a chance it doesn't

[ember obsidian]

this is true by the very definition of A being a subset of B

any element of A is an element of B

[jolly rivet]

Oh I see my mistake from before now

I just said that B was an element in P(B) but B was a subset of P(B)

[ember obsidian]

as said above B generally isnt a subset of P(B)

B is indeed an element of P(B)

but as i said, u dont need any of this to conclude x is in P(B)

u already said x is a subset of B

by definition of powerset, x is in P(B)

[jolly rivet]

Oh so like an element of P(B) is a subset of B

[ember obsidian]

yes, as said here

the elements of P(A) are precisely the subsets of A

[jolly rivet]

Ok thank you I should be able to fix my work!!!

😄

[ember obsidian]

ur welcome

[jolly rivet]

Here is the proof after some changes

[mint salmon]

I'm trying to figure out a regular expression that would build this language: L = {w | w consists of a and b, the number of bs should be even}
I'm not really sure where to start though. I have the definition of regular expressions but I can't seem to make the necessary connection for how it works. I don't want the answer, I want to understand how to come up with the answer

so far I have this:
(a)+ this matches one or more as in sequence.
(bb)+ this matches at least one case of two bs in sequence, but also matches bbbb and bbbbbb
(ab*ab*) seems like the direction I want to go to match multiple bs (possibly) separated by as

but how do I combine all this?

[coral parcel]

Hmm, would you find it easier to come up with a finite automaton?

[mint salmon]

I did make one actually, but I thought I would wait to ask about that

[coral parcel]

Okay.

[coral parcel]

I don't think that works completely -- it doesn't seem to match bb or abbbb.

[mint salmon]

I thought that there would need to be at least one a

[coral parcel]

Anyway, for the regular expression, can you devise a regex that matches strings with exactly two b but any number of as?

[coral parcel]

Oh, I see. By the usual conventions in this genre of exercises, I would firmly expect that "consists of a and b" means just "every symbol in the string is either an a or a b", but there's no requirement that both letters must appear.

[mint salmon]

that's a helpful tidbit

[coral parcel]

You're probably just missing a single intended transition in your drawing for recognizing abbbb.

[mint salmon]

not sure; I thought that it should be this, but it doesn't quite seem to work in the tool I'm using to check it: (a)*(bb)|(bb)(a)*

[coral parcel]

That seems to want to have the two b right next to each other and either at the beginning or the end of the string.

[mint salmon]

ah true, from q5 -> q2 when input is a b

[coral parcel]

You mean to q4, I hope.

[mint salmon]

yes

[coral parcel]

Perhaps think of it as "there must be exactly two b somewhere, but possibly with some a in front, and/or between and/or after them".

[mint salmon]

ahhhh ok now I get what I was doing wrong! (a*ba*ba*) the first a* is the a(s) which might come before, the second is in the middle, and the third comes afterwards. what I had before was backwards: (ab*ab*)

[coral parcel]

Right.

[mint salmon]

and (a*ba*ba*)* would be any number of such matches including words like abbbaab

[coral parcel]

Indeed.

Then you just need a special case for strings that do have a's but no b's to attach them to.

[mint salmon]

(a*ba*ba*)*|(a)+

so you asked me before about whether I would find it easier to draw a DFA (deterministic finite automaton); based on what I've learned so far it's possible to make a DFA for any regular expression and vice versa as they're both capable of "parsing" a regular language (wording?)

do I have that right?

[coral parcel]

Yes, that's true in principle. Systematic algorithms for converting a DFA to a regular expression tend to produce fairly horrible output, though. I was mostly asking about the automaton to gauge how far you had thought about the problem and where your hangups might be.

I would say (a*ba*ba*)*|a* so we also match the empty string (which is also a string over {a,b} with an even number of b's).

This can be said slightly shorter as (a*ba*b)*a* or a*(ba*ba*)*, by the way.

[mint salmon]

nice; it's cool to see how these things work for real after having seen them as mystical incantations for so long. step for step refinement and lots of thinking ftw

now I'm confused about my automaton though; I made the one for the case where there would need to be at least one a by first thinking about what states are possible:

q0 = (!a, !b)
q1 = (a, !b)
q2 = (!a, b)
q3 = (!a, b')
q4 = (a, b)
q5 = (a, b')

where !a, !b mean no a/b, b means uneven number of bs, and b' is an even number, q0 is the start state and q5 is the final state, and the set of functions were shown by a table of state transitions and inputs

but how can I represent the possibility of no as or no bs leading to a final state for instance? got it; guess I think better when thinking aloud

[nova venture]

Question --> Prove that F = {(x, y) | x − y ∈ Z} on the set R is an equivalence relation

what does the ordered pair (x,y) mean in this context?

that x or y divides x-y?

[pale epoch]

hm?

$(x, y)$ is an element of $R^2$

[vital dew]

Lochverstärker

[pale epoch]

recall that a relation F on a set R is a subset of R^2

[nova venture]

what does R^2 mean, my professor never explained lol

[pale epoch]

cartesian product of R with itself

its the set of tuples (x, y) with x, y both in R

so its just that: a ordered list of two numbers, both from R

[nova venture]

what would be the first step if i want to prove that this relation is reflexive?

[pale epoch]

you look up the definition of reflexive relation

[nova venture]

every x in Z (xRx)?

[pale epoch]

hm?

F is a relation on R

so you pick an x in R

and plug it in

i.e. show that (x, x) is in F

[nova venture]

F is reflexive: ∀x∈ℤ(xFx)

[pale epoch]

i think you need to review the definitions

[hushed fiber]

how to approach this question?
I was thinking that the group of permutation transformations would be
(12345)
(12345)^2
(12345)^3
(12345)^4
(12345)^5
Idk if I'm wrong

[coral parcel]

Vertices 1,2,3 are each incident to 4 faces, whereas 4 and 5 are incident to 3 faces each. So a symmetry cannot mix those up.

[hushed fiber]

can you elaborate more? I still don't quite understand

[coral parcel]

You can also count edges touching each vertex.

E.g. (12345) cannot be a symmetry because it takes vertex 5 (with three neighbors) to vertex 1 (with four neighbors).

[hushed fiber]

so (123)(45) would be a symmetry?

[coral parcel]

Yes.

[hushed fiber]

and then (123)(45) squared will be another?

[coral parcel]

Yes. That is just (132), of course.

[hushed fiber]

thank you !

[weary tiger]

I'm trying to prove that {33a + 14b } is subset of an integers

does this proof make sense?

[cerulean wind]

what are a and b?

[weary tiger]

oh right

they are integers

I forgot to add "assume a and b are integers" part in the screenshot

[cerulean wind]

why not just say that since the integers are closed under multiplication, then 33a and 14b are integers
and since the integers are closed under addition, then 33a + 14b are integers

[weary tiger]

what do you mean by "integers are closed under multiplication"?

integers * integers is an integer?

[cerulean wind]

yes

[weary tiger]

Ya, I was thinking about that but it felt simple. I guess I expected it to be little more complicated

[cerulean wind]

nope

[cerulean wind]

this proof is imo far too complicated and doesnt make much sense.

"an integer is a whole number or not a fraction" is not true. that would make any irrational number an integer

"for a number (presumably a real number) to be an integer, it must be reachable incrementally with just addition of ones" is also not true. what about -6 or pi + 1? i cant reach -6 by just adding ones but -6 is an integer. i can reach pi + 1 by just adding 1 to pi, but pi + 1 is not an integer.

"if a number is not reachable with addition of just 1's then it must be a decimal or a fraction" im not even sure how to interpret the last part of this sentence. it doesnt make much sense

[tough girder]

You can also say that, since a is an integer, 33a is just an integer added to itself 33 times, which yields an integer. Similarly, since b is an integer, 14b is b added to itself 14 times, which also yields an integer. Since both components are integers, then their sum must be an integer too.

[weary tiger]

Got it. Thanks for the help guys. I really appreciate it!

[sweet steeple]

Is the proof here valid?

The statement being proved is. If n is a bultiple of 10, then n+3 and n^2 + 1 are coprime

[spark eagle]

is this statement true? I know its prob too easy but im super confusedd

[pale epoch]

what do you think?

[spark eagle]

false?

[pale epoch]

do you have a counterexample?

[spark eagle]

nope 😦

[pale epoch]

what if P and Q are mutually exclusive?

[spark eagle]

so it is false?

[pale epoch]

well yes but you should convince yourself of that

what if P(x) is "x is even" and Q(x) is "x is odd"

(also side note, there is a parenthesis mismatch in your picture)

[spark eagle]

You’re right, but its only the second lecture so im tryna digest the concept

anyway thank u so much 🙂

[wheat grove]

Does the exponential time hypothesis hold if 3SAT reduces to a polynomial algorithm or an O(n^logn) algorithm in O(2^√n)?

maybe i should put them together lol

The “exponential time hypothesis” says that the problem $3SAT$ requires time $O(2^{δn})$, for some positive number $δ$ ($δ$ is allowed tobe less than 1).

Suppose that $3SAT$ reduces in time $O(2^{\sqrt n})$ to some problem $X$. Under the assumption
that the exponential time hypothesis holds, can $X$ be solved in polynomial time, or time
$O(n^{log n})$?

For the polynomial version my attempt's:

$\phi \in SAT \iff f(\phi) \in X$

and $n^c2^n$ for some constant c is less than $2^{\delta n}$ for all $n>=d$ where d is large enough, so X can't be solved in polynomial time.

I guess it's the same for $O(n^{log n})$ too since $2^{\sqrt[3]n} > n^{log n} $ (a guess) and then $2^{n^{5/6}} > 2 ^ {\delta n}$

but I'm not sure if this is correct?

[vital dew]

duk

[coral parcel]

Does your "exponential time hypothesis" say that 3SAT can be done in time O(2^dn), or that it requires time Omega(2^dn)?

"Requires" with O(...) don't really fit together.

Amyway, a reduction from 3SAT to X doesn't give us any kind of upper bound on the complexity of X.

We can reduce 3SAT to the halting problem in linear time...

[hoary cloak]

besides what troposphere said. a reduction in O(2^(n/2)) time is exponential so it's not conclusive to prove np-hardness. not even if you do what you're actually supposed to do to prove np hardness which is to reduce your problem to a known np hard one. and i'm not sure there did you get the n^(log n) from. so your intentions are unclear to me...

[wheat grove]

It's requires

[wheat grove]

Uhh, if there's an algorithm solving the problem of y in X in polytime, we can query f(x) where f is the reduction function, which is n^sqrtn and the query complexity is polynomial so overall it's <= stuff

[wheat grove]

I'm not proving NP hardness though?

[coral parcel]

That might give a lower bound on X.

[wheat grove]

Oh right

[hoary cloak]

i realized that much

[wheat grove]

Ok gimme a sec

[wheat grove]

Upper bound c*2^dn

[coral parcel]

So now it's not "requires" anymore?

[wheat grove]

About n^log n, I'm trying to figure that out separately (if X runs in O(n^logn) does if ETH is true

How does "requires O(..." Change the meaning?

[coral parcel]

"Requires" implies that you're stating a lower bound.

[wheat grove]

Hmm, it's an upper bound so not requires

Wait wtf

Hold on

It's a lower bound

[coral parcel]

Actually, "requires O(...)" is nonsense, because O(...) implies "or less". So "problem X requires time O(f(n))" translates to "it requires so-and-so-much time or less than that".

[wheat grove]

But an upper bounded lower bound if that makes sense?

Ok so probably just theta then

And not O

Sorry omega

[coral parcel]

So your hypothesis could be interpreted as either:
a) There exists an algorithm that always completes in time at most proportional to 2^dn
b) Every correct algorithm needs time at least proportional to 2^dn for some inputs
and these are radically different kinds of hypothesis.

And the somewhat flip-flopping answers here don't leave me very confident that I know which of them is the one you intend to be talking about.

[wheat grove]

(b)

[coral parcel]

Okay then.

So if we can reduce 3SAT to X in time O(2^sqrtn) and X has a polynomial-time algorithm (say, of degree m), then this reduction would allow us to solve 3SAT in time O(2^(m·sqrtn)), which is strictly faster than Omega(2^(delta·n)) for any delta. Therefore such a reduction would contradict your exponential time hypothesis.

[wheat grove]

Yep thanks!

And if X is solvable in O(n^{log n}) can we find any bounds?

Is n^logn < 2^n^c where c<1/2 ?

[coral parcel]

Hmm, the reduction doesn't have time to produce an X-instance longer than m=c·2^sqrtn bits. If we plug this into m^logm we get c·2^(sqrtn·log(2^sqrtn)) = c·2^dn, with a d is a constant that depends on which logarithm we mean in m^logm. In any case, this is now consistent with your hypothesis.

[wheat grove]

Ok wow this makes sense :o

Thank you so much!

[coral parcel]

Notice how this story would go quite differently if the reduction was in time 2 to the cube root of n ...

[weary tiger]

how tf do I prove this

I have to prove it or prove the negation is true

but Idk how to take the negation of an exclusive or

[obtuse lance]

I'd look at it as seeing if m^2-m=1 mod 3 has any solutions

since 1 is the only residue we care about having no solutions

[weary tiger]

how do you translate that problem into that

like the 1 mod 3

[obtuse lance]

well I'm saying that has no solutions is equivalent

because it means it must be 0 or 2 mod 3

which is what it means to write it as 3k or 3k+2

[weary tiger]

im so lost lol

i dont grasp the equivalence of any of that problem and mod

i don't get how it can be translated

[hasty yacht]

How can I find the minimum of f given ranges for the parameters and all variables are natural numbers? The ampersand in the second image is the bitwise and

[dense glade]

Can anyone help me with this

1number b

[drifting sail]

use the binomial theorem to write (a-b)^n as a sum, then find which numbers you should plug into a and b

[dense glade]

@drifting sail I tried doing that but I coulnd't get it at all

would u tell me where to start

I can't even find a video or something to read on it

I have the binomial theorem written and thats it

Idk how to find the x and y in the sum

[drifting sail]

maybe it's clearer if you write it as
[
3^n(-1)^0\binom n0 + 3^{n-1}(-1)^1\binom n1 +
3^{n-2}(-1)^2\binom n2 +
\hdots

• 3^0(-1)^n \binom nn
  ]

[vital dew]

derivada.schwarziana

[drifting sail]

it should be in any book on elementary number theory, I like Burton's

maybe in some discrete math textbooks but I don't know any

[dense glade]

ok

I see

but what do u observe here

so that u get the value of A and B

[drifting sail]

the binomial theorem tells you that any integer power of a binomial, $(a+b)^n$ can be written as a sum
[
(a+b)^n = a^n\binom n0 + a^{n-1}b\binom n1 + \hdots + b^n\binom nn
]

[vital dew]

derivada.schwarziana

[drifting sail]

so the idea is to rewrite the sums here as a sum that kinda looks like the one given by the binomial theorem

[dense glade]

ah i see

wait so u got the answer right?

[drifting sail]

yes, note that this sum is the same as

[drifting sail]

this sum

but with a=3 and b=-1

so your sum would be (a+b)^n=(3-1)^n=2^n

[dense glade]

I'm sorry how did u get the -1?

@drifting sail

[drifting sail]

the alternating between + and - here can be written as multiplying by (-1)^0, (-1)^1, (-1)^2, ..., (-1)^n

since (-1)^0=1, (-1)^1=-1, etc.

generally (-1)^k is 1 if k is even and -1 if k is odd

[drifting sail]

that's why the sum in your exercise equals this

and since the powers of 3 start at n and then decrease, and the powers of -1 start at 0 and increase, you get a binomial sum

[drifting sail]

in other words, just replace a=3 and b=-1 here and you should get the sum

[dense glade]

i see thank you

[past marsh]

Hello

Can I get some help

For iii) if one of the points are not connecting

Does that it mean it’s not a function

[drifting sail]

that's right

since a function would need to assign a value to each point in the domain

here no value is assigned to F(6), so F is not a function from A to B

[past marsh]

So would it be ii?

[drifting sail]

it also needs to assign an unique, i.e. only one value

so no

[past marsh]

So none of them basically

[drifting sail]

(i) is a function since there's a single arrow starting from each point in A

[past marsh]

False right

Bcuz it is not 1-1

[umbral tendon]

I'm doing some graph theory atm.. I understand the theory behind the question, I just need some help with articulating the proof.. I'm not sure where to start.

[wheat grove]

just a small clarification about this - is the reason why we compose the functions (ie set m = 2^(sqrt n) in m^c) because the (2^(sqrt n)) reduction might result in the output of the reduction function increasing by a factor of 2^(sqrt n)?

[coral parcel]

Yes -- unless we have more specific assumption we assume that a reduction that runs in time f(n) might also produce an output problem of size f(n).

Of course it is possible to speak of a reduction that runs within a certain time bound but produces an output that fits within a lower bound. It just needs to be stated explicitly if we make such an assumption.

might result in the output of the reduction function increasing by a factor of 2^(sqrt n)
This should be "might result in the output of the reduction function having a size of 2^(sqrt n)".

[wheat grove]

thanks!

[wheat grove]

yeah true

[coral parcel]

(The reasoning here is that it takes the reduction function some constant amount of time to print each output symbol, so the output cannot be larger than the time it takes to produce it).

[cerulean wind]

this isn’t true. if a graph has a hamiltonian cycle, then it’s not a spanning tree since trees don’t have cycles

[umbral tendon]

it says Hamiltonian path not cycle

but I think I managed to figure it out

[cerulean wind]

hamiltonian cycles are hamiltonian paths

[cerulean wind]

when you say permutation, do you mean all of the rectangles are just next to each other in a line, all oriented the same way?

in this picture i would just rotate each rectangle 90 degrees

to get a big stick

[ ][ ][ ][ ]…

[true venture]

I would think the permutations where the shortest one is next to the longest one ect. Would be the max perimeter?

Interesting!

What does the max area arrangement look like?

[cerulean wind]

this feels like a knapsack type of problem

[true venture]

Maybe look at the geometry of the end arrangement?

[cerulean wind]

i think the key is to look for repeated sub problems

and give a recursive dp type solution

why is that not a mathematical solution?

[true venture]

Is there a specific way to transform from the ordered arrangement , 1234... to the one with max perimeter?

[cerulean wind]

max perimeter arrangement is 2314 if i’m not mistaken

[true venture]

Maybe going into geometry, isn't the way to think of this, you want the permutation of n numbers so that the sum of the differences between each number is maximum

Would the heights always be sequential 1234 or like 2467?

That makes it more difficult

[cerulean wind]

eh

just order them

if the input ur receiving comes in unordered

just order it

if that makes it easier for now

[cerulean wind]

am i missing something here then?

[true venture]

I would find the max perimeter arrangement for several sets of numbers and look for patterns

Or thinking that ordering the numbers sequentially gives the minimal perimeter, find the furthest arrangement from that

You could think of the line connecting the tops of the rectangles, maybe the line with the flatest slope is the one with max perimeter

Or a less elegant solution would be rather than finding all permutations, just skip certain ones you know won't lead to the max arrangement

[livid minnow]

If u pair a large one next to a smaller then you gain more perimeter

could you order it like 9,0,8,1… ?

oh mb

[tidal tulip]

and is there a “better” way to define the range than the way they did

[dense glade]

for number A

what if it wall the string that contained the 3 same digits what would it be

I want the same digit to repeat 3 times

[sturdy ivy]

can some one verify if this is right

[true venture]

@night merlin did you find anything?

[gilded marsh]

I am meant to find the mistake but I can’t seem to find any

(Proofs)

[stiff lichen]

This says that m is 1 more than n

Which is not always true

[gilded marsh]

Is that not because one is odd and one is even?

[hard citrus]

The mistake is in the setup with the definition

So this actually proves that the sum of a number n and its successor is odd

Not for any two integers

[hushed fiber]

since each vertex has 3 edges
can I say that the group of all geometric transformations that leaves the prism invariant is
(123456)
(123456)^2
(123456)^3 ..................... and so fort until the identity transformation is achieved?

or will it be (123)(456) ?

[gilded marsh]

I was thinking this too, thank you

[iron hearth]

Can someone help me with b

[stiff lichen]

What is transitivity?

[sweet ingot]

For A union B, i get that this means that x is in the set A or x is in the set B. But it could also be that x is in A and B right? But we never worry about this for proofs?

[hard citrus]

Worry about it how? If x is in both A and B then of course x will be in their union

$x \in A\cup B \Leftrightarrow x \in A \lor x\in B$, the disjunction is true in the cases where:

1. x is in A and not in B;
2. x is in B and not in A;
3. x is in A and x is in B.

[vital dew]

.nai

[hard citrus]

So case 3) is covered by the very definition of union

[iron hearth]

does it mean if the first element is related to the second and the second is related to the third, then the first must be related to the third

[stiff lichen]

Yes.

So we want to set up some variables representing 3 elements and find a way to reach the final conclusion that the first and third are related

[iron hearth]

ok

[sweet ingot]

@hard citrus ah ok thank you.

[silent hinge]

I don’t understand what phi(p) is

How can I determine the general answer

If p is prime

If p is a prime then phi(p) = p-1?

[unreal stump]

Yea,come up with an argument for that

[silent hinge]

can you provide me an example beacause i am having a hard time understanding how

@unreal stump

[unreal stump]

So what's the special property of primes

If p is a prime ,p|a or gcd(a,p)=1

Does p divide any number less than it?

[silent hinge]

no?

actually idk i am guessing i am trying to translate what you saying in my head

i got lost on your github profile, nice projects

[coral parcel]

Your image seems to be saying gcd(7,7)=1 which doesn't look right.

On the other hand, your use of "..." in the phi(11) case looks like you essentially have the answer to the general question.

[silent hinge]

this is how i am doing it: gcd(7,7)=gcd( 7 mod 7, 7) = gcd( 0, 7) = 1

ohhh wait thats 7

[coral parcel]

Because 7 is a divisor of both 7 and 7, and they certainly don't have any divisor greater than that.

[silent hinge]

i get it now, thanks

[sweet ingot]

can anyone help me understand this

How can you say A X (BUC) based off that information

We must now prove that (A×B)∪(A×C)⊆A×(B∪C). So we let v∈(A×B)∪(A×C). Then v∈(A×B) or v∈(A×C)
In the case where v∈(A×B), we know that there exists s∈A and there exists t∈B such that v=(s,t). But because t∈C, we can conclude that t∈B∪C and, hence, v∈A×(B∪C).

[stray reef]

idk why that solution says $t \in C$ --- that need not be true in general

[vital dew]

Ann

[stray reef]

however we can say that $t \in B$ and thus $t \in B \cup C$

[vital dew]

Ann

[stray reef]

so you have $s \in A, t \in B \cup C \implies (s,t) \in A \times (B \cup C)$ by the definition of cartesian product

[vital dew]

Ann

[stray reef]

@sweet ingot

[sweet ingot]

oh wow that makes so much more sense

without that weird assumption that was throwing me with t element of C

thank you so much

$A \times (B - C) = (A \times B) - (A \times C)$ Could you help me with the start of the proof on this one

let $k \in A \times (B - C)$

$k = (x,y)$

$x \in A$

$y \in B $ and $y \notin C$

thus $k \in (A \times B)$

is anything wrong here so far?

[stray reef]

so far nothing is wrong, except for some

[sweet ingot]

haha im learning, my first go lol

[vital dew]

shaka

[sweet ingot]

seems better

Ok im am stuck on what my next move should be now

[stray reef]

you seem to be focusing first on proving $A \times (B-C) \subseteq A \times B - A \times C$, and to this end you took an arbitrary element of $A \times (B-C)$, whcih you called $k$, and you set out to show that $k \in A \times B - A \times C$.

[vital dew]

Ann

[sweet ingot]

yep

exactly

[stray reef]

you have shown that $k \in A \times B$

[vital dew]

Ann

[stray reef]

what else do you need to show?

[sweet ingot]

dont I need to show that $k \in (A \times B) - (A \times C)$

[vital dew]

shaka

[sweet ingot]

have I done that?

[stray reef]

no, you have not yet done that

you have so far only shown that $k \in A \times B$

[vital dew]

Ann

[stray reef]

$k \in A \times B - A \times C \iff (k \in A \times B) \land (???????)$

[vital dew]

Ann

[sweet ingot]

mm I dont know sorry

[stray reef]

i am certain that you do

you already applied the definition of set difference in your work

you can do it again

if you'd like i can prompt you more directly

[sweet ingot]

I honestly dont know. Id love a prompt here.

[stray reef]

$x \in S - T \iff x \in S \land (????)$

[vital dew]

Ann

[sweet ingot]

sorry im lost now. its ok ill study some more and come back to this. Thank you for your help

I havent used Iff in proofs yet

[stray reef]

...

[sweet ingot]

Its probably obvious but I only just started this last week, on my second class. Only did my first proof today so im still pretty bad.

[ember obsidian]

@sweet ingot whats the definition of setminus

[sweet ingot]

hmmm as in A - B

[ember obsidian]

yes

[sweet ingot]

$x \in A$ and $x \notin B ??

[vital dew]

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

[ember obsidian]

thats what x in A-B means

its important to read the form not the exact letters used

what does k in AxB-AxC mean?

[weary tiger]

could i get help understanding this question

[sweet steeple]

is the following proof valid?

[sweet ingot]

It means that k is in AxB and not in AxC

[ember obsidian]

ye, so far u only showed k is in AxB, u also must show k isnt in AxC

[sweet ingot]

whats the first step for that

am I on to the right hand side yet or still proving LHS subset of RHS

[sweet ingot]

for this ???? part $k \notin (A \times C)$

[vital dew]

shaka

[ember obsidian]

lhs subset of rhs

[sweet ingot]

yep im just stuck I dont know how to show that $k \notin (A \times C)$

[vital dew]

shaka

[sweet ingot]

I know that if it is then the proof fails. But how to show it

[ember obsidian]

unpack what AxC means

recall k=(x,y), etc

[stray reef]

refer back to this

this work contains all the info you need to conclude k ∉ A × C

[safe dawn]

Good day! Can u help me? 👉 👈

[tall gorge]

I'm reading the proof for the following identity:

$$\sum_{k}A_{k}(r,t)A_{n-k}(s,t) = A_{n}(r+s, t), \ integer \ n \geq 0 \ -----(1)$$

where $A_{n}(x,t)$ is the $n$th degree polynomial in $x$ that satisfies

$$A_{n}(x,t) = \binom{x-nt}{n}\frac{x}{x-nt}, \ for \ n \neq x.$$

The author starts off by assuming that $r \neq kt \neq s$ for $0 \leq k \leq n$, since both sides of (1) are polynomials in $r, s, t$. I'm not sure I understand this. I get that we need $r \neq k$ in order to prevent division by zero in $A_{k}(r,t) = \binom{r-kt}{k}\frac{r}{r-kt}$, but I'm not sure why we can additionally assume $kt \neq s$ and $r \neq s$ for $0 \leq k \leq n$? I'm a noob and especially useless at inequalities so any help would be greatly appreciated.

[vital dew]

mmerc

I'm reading the proof for the following identity:

$$\sum_{k}A_{k}(r,t)A_{n-k}(s,t) = A_{n}(r+s, t), \ integer \ n \geq 0 \ -----(1)$$

where $A_{n}(x,t)$ is the $n$th degree polynomial in $x$ that satisfies

$$A_{n}(x,t) = \binom{x-nt}{n}\frac{x}{x-nt}, \ for \ n \neq x.$$

The author starts off by assuming that $r \neq kt \neq s$ for $0 \leq k \leq n$, **since both sides of (1) are polynomials in $r, s, t$**. I'm not sure I understand this. I get that we need $r \neq k$ in order to prevent division by zero in $A_{k}(r,t) = \binom{r-kt}{k}\frac{r}{r-kt}$, but I'm not sure why we can additionally assume $kt \neq s$ and $r \neq s$ for $0 \leq k \leq n$? I'm a noob and especially useless at inequalities so any help would be greatly appreciated.

[gritty agate]

How would i solve part 1 in this?

I thought about using the inclusion exclusion principle

where A is the set of exactly 2 consecutive pairs, B is the set of exactly 3 consecutive pairs, and C is the set of exactly 4 consecutive pairs

i got as far as

$$\binom{19}{1}\binom{18}{2} + \binom{18}{1}\binom{17}{1} + \binom{17}{1}\ - .... $$

[vital dew]

Adamfk1

[gritty agate]

as per the inc exc principle

im supposed to remove the intersection of A and B, B and C, A and C then add back the intersection of A B and C, but im not sure if this is correct or how to do it

[unreal stump]

For first part,first pick 2 consective numbers,that can be done in (19C1) ways

Now,you have picked 2 numbers,so pick 2 out of remaining 18 numbers

And that's it

Exactly 2 is a lot tougher

[gritty agate]

How so?

is it not the opposite

[unreal stump]

Actually it's still easy

[gritty agate]

Shouldnt it be 19C1 * 18C2

for the exactly two numbers?

19 possible consecutive pairs

and 2 out of the 18 remaining numbers --> 18C2

[gritty agate]

https://math.stackexchange.com/questions/3525172/in-how-many-ways-can-we-choose-4-different-numbers-from-the-set-1-2-3-8-9 here is a reference that i followed

[unreal stump]

You have one consecutive pair

The other 2 could also end up being consective

[gritty agate]

In other words

the answer i have is for at least two consecutive

as for the exactly two consecutives

[gritty agate]

Is it not the same as this?

not the same answer, the same concept rather

we have at least two consecutive numbers and we subtract all possible three consecutive and 4 consecutive and then add back the intersection of all three sets

[dense glade]

How many ways to arrange the letters in the word ESTATE so that all vowels are adjacent?

My answer was (3!x4!)/(2!) but its wrong

[urban fiber]

Maybe you're missing a 2! in the denominator for two T's

[true venture]

I'm trying to work out the answer, the term on the right side is the maximum of the left side of all permutations for a given n. For n=3 it is half of all permutations then n=5 is less then less I think

[tidal tulip]

suppose f: X->Y is a function and let A subset X. show that if f is injective then f^-1(f(A))=A.

for this proof do i need to prove both directions and how should this proof go?

i know f[A] = { y in Y | y=f(a) for some a in A}

and want to show f^-1(f[A])={a in A | y=f(a) in f[A]}

[proven silo]

If you understand the question/definitions it should be straightforward

[proven silo]

Both ways? You didn’t write iff in your statement.

[tidal tulip]

there is no iff

in the original problem statement

[true venture]

A quick guess is n!/(n-1)

[proven silo]

Wdym both ways then?

[tidal tulip]

f^-1(f[A]) = A if f is injective

f is injective if f^-1(f[A]) = A

[proven silo]

“There is no iff” now you are saying yes there is an iff

Those are the same thing you wrote lol

[tidal tulip]

there isn’t an off

[proven silo]

If and only if

[tidal tulip]

there isn’t one

[proven silo]

If A implies B and B implies A

A iff B

[tidal tulip]

there isn’t an iff there unless it’s implicit

[proven silo]

.

[proven silo]

.

[tidal tulip]

suppose f: X->Y is a function and let A subset X. show that if f is injective then f^-1(f(A))=A.

that’s the statement as written

[proven silo]

What do you mean with both ways then?

I’ll try again

[tidal tulip]

okay moving on how do i go above proving this

i know f[A] = { y in Y | y=f(a) for some a in A}

and want to show f^-1(f[A])={a in A | y=f(a) in f[A]}

[tidal tulip]

i don’t think iff is relevant here from what you’re telling me it’s an if then proof

[proven silo]

Do you know A subseteq of f^(-1)(f(A)) already?

[proven silo]

“Both ways” implies there is an iff statement

[tidal tulip]

let’s clear this up, this is NOT an iff proof

correct?

[proven silo]

Otherwise no idea what you meant with both ways

Correct

[proven silo]

But again

[tidal tulip]

ok

so how do i begin the proof

[true venture]

I'm interested now, did you find the answer?

[proven silo]

.

[tidal tulip]

i don’t know anything other than the problem statement

suppose f: X->Y is a function and let A subset X. show that if f is injective then f^-1(f(A))=A.

[proven silo]

This always holds

Im asking do you know this is true

For example is that a theroem/excercise in your book?

[tidal tulip]

no

[proven silo]

Start proving that then

[tidal tulip]

unless it’s the preimage or something

[onyx fable]

So what is the pre-image under 1?

[proven silo]

Check what definition of pre-image is

And it should be clear

[tidal tulip]

f^-1(f[A])={a in A | y=f(a) in f[A]}

[onyx fable]

Where A is the function x^2

does the flooring making a difference?

[proven silo]

Is floor(0.5^2) equal to 0.5^2?

If no it matters

[dense glade]

thats where 2! is

[onyx fable]

So f^-1(f[A])={a in A | y=f(a) in f[A]} is the preimage under 1, should I change A to x^2?

[tidal tulip]

😂 copied pasted what i wrote

[proven silo]

Like I said at the beginning if you understand definitions its easy

That is not definition of preimage

So why not check your book for definition

[onyx fable]

Haven't learned pre-image

[proven silo]

Then you can’t do it

[tidal tulip]

what about my problem, how do i go about proving it

inverse is a function

preimage is a set

[proven silo]

Show this

This is true for all functions f

[tidal tulip]

how do you define f^-1(f[A])?

is it:
f^-1(f[A])={a in A | y=f(a) in f[A]}

[agile crown]

please guys help me i dont know what 1+1 is!

i need help

[proven silo]

b in f^(-1)(B) iff f(b) in B

[tidal tulip]

ok

[proven silo]

So a in f^(-1)(f(A)) iff f(a) in f(A)

[tidal tulip]

is that what i wrote

[tidal tulip]

here

[proven silo]

Not sure why you even have the y thing

But yes

[agile crown]

scrape

please help me

[urban fiber]

Then you missed the one for two E's? There must be 2 2! In the denominator

[tidal tulip]

ok

[proven silo]

But here we have this holds since a in A

[agile crown]

scrape i need help LOOK!!!!

[tidal tulip]

ok

i’ll think more

[agile crown]

NO WAIT SORRY!!!

THIS

[pale epoch]

take your memes to #chill @agile crown

or better yet, to a whole other server

[tidal tulip]

what does f(A) mean because A is a set so what does f applied to an entire set mean? is that the same thing as the image or f(A) = { y in Y | y=f(a) for some a in A} ?

[pale epoch]

yes

[tidal tulip]

k

[pale epoch]

more simply f(A) = {f(a) | a \in A}

[tidal tulip]

so why is the first step of this proof ‘prove A subset f^-1(f(A))’?

my thoughts were to evaluate f^-1(f(A)) and then somehow use f injective to show f ^-1(f(A))=A

how does proving that get me to my goal

[pale epoch]

"this proof"?

[tidal tulip]

i want to prove suppose f: X->Y is a function and let A subset X. show that if f is injective then f^-1(f(A))=A.

not sure how to go about it

[pale epoch]

you prove A subset f^-1(f(A)) and f^-1(f(A)) subset A

[tidal tulip]

ok

[pale epoch]

its just writing down definitions

one of the directions should be always true, the other will require injective

[tidal tulip]

f^-1(f(A))={a in A | y=f(a) in f(A)} by definition no?

let a in A, then a in f^-1(f(A)) since f^-1(f(A))={a in A | y=f(a) in f(A)} by definition therefore A subset f^-1(f(A))

is that a correct proof for that direction ?

@pale epoch

[pale epoch]

ye

[tidal tulip]

ok cool

then let a in f^-1(f(A))={a in A | y=f(a) in f(A)}, we want to show a in A

f^-1(f(A)) = f^-1(y) but here is where i get stuck

[safe dawn]

Good day! Can i delete this(blue)?

[tidal tulip]

i’m confused how to evaluate

f^-1(f(A))

because f(A) is a set and not a single element @pale epoch

[proven silo]

Let a in f^-1(f(A)), you want to show a is in A

[tidal tulip]

so i’m confused as to what it means when you say let a in f^-1(f(A)) too

[pale epoch]

just by definition of preimage it means that f(a) is in f(A)

so there is some a' in A such that ...

can you continue?

[tidal tulip]

f^-1(y=f(a))

f^-1(y)

[pale epoch]

look at the definition of f(A) you gave above

the very first thing you did

also probably use a different letter, this might be confusing here

[tidal tulip]

f(A) = { y in Y | y=f(a) for some a in A}

[pale epoch]

let x be in f^-1(f(A))

so f(x) is in f(A)

so f(x) = y = f(a) for some a in A just using your definition

[tidal tulip]

yeah

[pale epoch]

and now you are basically done

[tidal tulip]

f^-1(y) =

is what i have left

[pale epoch]

why are you doing f^-1

[tidal tulip]

because i am evuakaring f^-1(f(a))

[pale epoch]

why?

you want to show x in A

[tidal tulip]

because i want to show f^-1(f(A)) = A

[pale epoch]

you dont

[proven silo]

You show one is subset of the other

Then they must be equal

[pale epoch]

you take an arbitrary x in f^-1(f(A)) and show it is in A

[tidal tulip]

let a in f^-1(f(A) show a in A

[pale epoch]

yes, but as i said using a might mislead you

[tidal tulip]

what does it mean for a in f^-1(f(A))

[pale epoch]

because you dont know yet if a is in A

[proven silo]

a is arbitary

[tidal tulip]

f^-1(f(A))={a in A | y=f(a) in f(A)} by definition

so a is in that set

now how do i use injectivity to show a in A

[pale epoch]

that definiton is not correct

[tidal tulip]

what is the correct definition

[pale epoch]

{x in X | y=f(x) in f(A)} is better

[tidal tulip]

so is this proof wrong then

[pale epoch]

i think its better to write {x in X | y=f(x) in f(A)}

but the proof still works

[tidal tulip]

super confused i’ll be back have to go in a meeting

[pale epoch]

you start with a in A and then you have to show that f(a) is in f(A)

which, as you said, is just definition

[tidal tulip]

ok confused about the other direction

[pale epoch]

you start with a x in {x in X | y=f(x) in f(A)}

and have to show that x is in A

[tidal tulip]

i have questions but have to

go now

bbl

[pale epoch]

is this supposed to be round down?

[onyx fable]

yea, x^2 is getting floored

[pale epoch]

well

whats (11/10)^2

[onyx fable]

1.21

to 1

[pale epoch]

so surely 11/10 should be in the preimage of 1

but its not in [-1, 1]

[onyx fable]

right

but it also includes neg because we are squaring.

[pale epoch]

ye

you can just consider positive though

you seem to have correctly identified that your interval should be symmetric around 0

(if not, do that first)

so

when does a positive number get rounded down to 1?

[onyx fable]

So how should the pre-image under 1 be written, maybe I am not inputting correctly

[onyx fable]

depends

[pale epoch]

on what?

[onyx fable]

if its bigger than rounded down values to one

ex. 2

[pale epoch]

hm?

[onyx fable]

like (1.5)^2

rounded down will be 2

[pale epoch]

i didnt ask about squares though

i asked what positive numbers get rounded down to 1

[onyx fable]

1-1.99..

[pale epoch]

something like that

maybe write it as an inequality?

[onyx fable]

1<=x<2

[pale epoch]

ok yeah

they can be smaller than 1 but ok

[onyx fable]

if its less than 1 it gets rounded to 0

[pale epoch]

big brain move from me

so your answer is wrong for multiple reasons

anways

now if we can agree that x^2 is always positive (or at least non-negative)

you just have to solve 1 <= x^2 < 2 in this case

[tidal tulip]

let a in f^-1(f(A)) = { y in y | y=f(a) for some a in A} then… how can my argument continue? can i evaluate f^-1(f(A))

like:
f^-1(f(A))=
f^-1(y)=
a (since f is injective)

is that how it goes?

[onyx fable]

So this gets the preimage of 1 under f?

[tidal tulip]

im confused here

[safe dawn]

@pale epoch Are u free?

@tidal tulip or mb u 👉 👈

[pale epoch]

you should convince yourself of that

[pale epoch]

i dont know why you want to evaluate f^-1(f(A)) or what that even means

[tidal tulip]

i don’t know what do you after you say let a in f^-1(f(A)) or what that even means here

[pale epoch]

also this definition of f^-1(f(A)) is definitely wrong

you should check the defintion of f^-1

[tidal tulip]

if that definition is wrong then how is it correct in my other proof

[pale epoch]

you didnt use this one in your proof

the preimage is a subset of X and the definition should reflect that

[tidal tulip]

f^-1 = {(y,x) in Y x X | (x,y) in f}

[pale epoch]

where is this definition from

[tidal tulip]

idk that’s what my book states

[willow fog]

what kind of a definition is that

[tidal tulip]

then how should i define f^-1

[pale epoch]

this is the wrong definition

you need to look for the definition of preimage

[tidal tulip]

f^-1(f(A)) = { a in A | f(a) in Y} ?

[onyx fable]

So consider the related function g(x) = x^2. Then f(x) = (g(x)], and the function f will map x to 1 exactly when g maps x to an element in the half-open interval [1, 2],

[pale epoch]

you are reading this definition wrong

also wtf

is this the same source as the question?

[tidal tulip]

i’m so confused

no question is from homework

[pale epoch]

you need to write down the definition properly

including domains and codomain

[tidal tulip]

i thought i did

[pale epoch]

if $f\colon X\to Y$ is a function and $B \subseteq Y$, then we define
$$ f^{-1}(B) \coloneqq {x \in X | f(x) \in B}$$

[vital dew]

Lochverstärker

[pale epoch]

so in your case you have $f(A) \subseteq Y$ and just plugging this into the definition you get
$$f^{-1}(f(A)) = {x \in X | f(x) \in f(A)}$$

[vital dew]

Lochverstärker

[tidal tulip]

shouldn’t it be a in A

[pale epoch]

no

[tidal tulip]

since A subset X

[pale epoch]

this is the definition

[tidal tulip]

ok

[pale epoch]

the general definition doesnt care about any subsets of X

[tidal tulip]

ok

[pale epoch]

and now you have to take an element of this thing

so some x in X that satisfies f(x) \in f(A)

and show that x is in A

you will need to use the definiton of f(A), i.e. what does it mean for f(x) to be in f(A)

and then the definition of injectivity

which you havent even tried to use until now

[tidal tulip]

ok i will think about this

[pale epoch]

there is no reason to evaluate any set (in fact its unclear what this is supposed to mean)

[pale epoch]

other than using the definition as ^ here

[tidal tulip]

so f^-1 isn’t a function it’s a set (preimage) ?

and f is the image (another set)?

[safe dawn]

Can I do this?

[pale epoch]

you can think of f^-1 as a function if you want

it maps sets to sets

but f^-1(B) is a set

[tidal tulip]

f^-1(B) is the preimage of B yeah?

f(A) is the image of A?

[pale epoch]

yes

both of those things are sets

[tidal tulip]

ol

ok

i will give it thought a little busy atm

and then rearrange

[pale epoch]

you mostly have to be careful about where they live

[tidal tulip]

reattmept

[pale epoch]

i.e. whether they are subset of the domain or codomain

[true venture]

My guess was wrong, anyone know how to find the answer?

[shell lagoon]

so this makes intuitive sense to me since mod will always make sure the colors are spaced out

but I'm not comfortable enough with mod to know how to formally prove this?

[pale epoch]

suppose not

then some vertex i will have neighbours, say j and k and ij and ik must have the same color

translate this into modular arithmetic

[true venture]

Nobody?

[lone raft]

Definition in use: S is most countable if S is finite or countable. Suppose A is at most countable such that for every a in A we have B_a is at most countable. Let S be the collection of at most countable sets B_a, is S at most countable?

[shell lagoon]

alright I'll give it some thought, thanks!

[pale epoch]

i would start by looking at small examples

try to notice a pattern and then prove it via induction

there is probably a smart argument as well but 🤷

[pale epoch]

hm?

collection of?

i dont think this says what you want it to say

[true venture]

Ok, I looked at n being 3 and 5, after that too many lol

[lone raft]

I have for each a in A, the set B_a and S is the collection of those sets.

[dense glade]

if this si right?

[pale epoch]

what does collection mean mathematically

[lone raft]

set?

family of sets.

is there a more precise meaning?

[pale epoch]

ok but then you ask if ${B_a \mid a \in A}$ is countable

or what

[vital dew]

Lochverstärker

[lone raft]

yes, that.

[pale epoch]

this just has at most cardinality of A

[lone raft]

Hmm, yeah I see it.

It follows the map f : A -> S, where S is that set above is bijection.

[pale epoch]

it doesnt

if all the B_a are the same, the set above is a singleton

[lone raft]

Oh, so just onto then. That is perfect.

This was my lemma, thank you Loch.

[tidal tulip]

let a in A, then a in f^-1(f(A)) since f^-1(f(A))={x in X | f(x) in f(A)} — i don’t see the justification for this since x could be an element in X not in A @pale epoch so how do i fix this part of the proof?

[pale epoch]

a in f^-1(f(A)) means f(a) in f(A)

[true venture]

Ok so n! / 2*(n-2) works for n= 3 and 5. @pale epoch how do you prove by induction?

[pale epoch]

(also notice that any a in A is also in X)

[pale epoch]

no idea tbh, i would hope there is some way to build the functions for n+1 from the functions for n

but thinking more about it, that probably doesnt work

so no idea, sorry

[true venture]

What do you mean by functions?

[pale epoch]

the permutations

[tidal tulip]

let a in A, then a in f^-1(f(A)) since f^-1(f(A))={a in X | f(a) in f(A)} therefore a in f^-1(f(A)) and hence A subset f^-1(f(A)) — is that how the argument would go @pale epoch

[pale epoch]

also i should say n+2 from n

[true venture]

Ok ok, yea a that's what I was thinking, I way to elimate certain sets of permutations based on n

[tidal tulip]

let a in A, then a in f^-1(f(A)) since f^-1(f(A))={a in A | f(a) in f(A)} therefore a in f^-1(f(A)) and hence A subset f^-1(f(A)) — is that how the argument would go?

[pale epoch]

😵‍💫

it feels like you are just permuting symbols

its hard to tell, you are just writing down definitions, sometimes correctly, sometimes less correct

but this proof is just writing down definitions

and i cant look into your head to see if you understand it

so i dont think i can help you any further, sorry

[tidal tulip]

i’m not sure i understand your advice in my head it makes sense because it’s all the a in As where y= f(a) in f(A)

where A subset X

i don’t get your x in X because x in X could be an x not in A

you want to only consider a in As

not the general x in Xs

maybe if you better explained what you’re saying i would understand you.

i don’t write down anything willy nilly @pale epoch

[dense glade]

if this is right?
for number 1
the answer should be 31C20 * 30!/30!?
for number 2 the answer is the 50!/20!*30! - 31C20 * 30!/30!

[true venture]

Oh you mean build the permutations that satisfy the equation, gotcha. I was thinking of it as a way to eliminate the ones that don't out of the set of n!

[tidal tulip]

@pale epoch if you want me to explain why i am writing what i am i’d be happy to. i’m not just permuting symbols

but i think your advice isn’t so clear

[pale epoch]

yes this is precisely the point

the preimage of f(A) is all x in X that get mapped to f(A)

[tidal tulip]

ahh

[pale epoch]

in theory it could be elements outside of A

[tidal tulip]

i see, that clears up a major misconception

thinking f(A) had to all come from a in A

[pale epoch]

this is true

[wintry fable]

why does not p turn into all that?

[pale epoch]

but the preimage of f(A) is at first not defined like this

the preimage of f(A) is just all x in X that get mapped to f(A)

f(A) is the set of all images of element from A

like

if i set B = f(A), then i can still write down f^-1(B)

and there is no reason to mention A

[tidal tulip]

i see

[pale epoch]

because the elements of f^-1(B) do not necessarily have to come from A

[tidal tulip]

ok that was a misconception i had

[pale epoch]

f^-1(B) are elements x of X that additionally satisfy f(x) in B

[tidal tulip]

ah - ok

[pale epoch]

now if you take an a in A you have to check two things to show that it is in f^-1(B)

you have to confirm that it is in fact also in X, this follows from A being a subset of X

and you have to confirm that f(a) is in B

but as B is just f(A), you have to show that f(a) is in f(A)

but thats just the definition of f(A)

now in the backwards implication this is a lot more important

because if you take an element of f^-1(B) = f^-1(f(A)), it is not at first clear that it is in A

its just an element x of X that satisfies f(x) in B = f(A)

and then you have to use the definition of f(A) again and the injectivity of f to conclude that x is in fact also in A

[tidal tulip]

ok thank you — i will revisit the definitions and what you said and parse it carefully

you gave me a structure to follow ty

and cleared up a misconception i had

[pale epoch]

they used the distributive property, look closely at the parentheses

[wintry fable]

ohh i see it, thanks a lot !

[true venture]

Something like if an x existed that didn't satisfy the property then n wouldn't be an integer?

What does by cases mean?

[stray reef]

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

in this case there are two cases worth making a distinction for: one is for when x is an integer, and the other for when it isn't.

[true venture]

So by making those two cases you prove it?

[stray reef]

no, declaring those cases alone proves exactly nothing

[tidal tulip]

@pale epoch would the first direction go like this: let $x \in A$, then $x \in f^{-1}(f(A))$ since $f^{-1}(f(A))={x \in X | f(x) \in f(A)}$ by definition, therefore $A \subseteq f^{-1}(f(A))$.

[vital dew]

strings

[true venture]

So what then?

[stray reef]

the idea is that after you make the split into cases, you prove your goal statement for each case separately - and once you do that, you conclude that you have proved it in general

[true venture]

Thanks, sorry I've got to learn about proofs more

[wide vine]

can someone help explain how they arrived at this sequence?

I thought it would be like

sqrt(1), sqrt(2), sqrt(3), ....

idk where they are getting 1, 2, 2, 2, 3, 3, 3, 3, 3, 4

[pale epoch]

they are rounding up

(to the nearest integer)

[wide vine]

-_-

why

that completely changes the answer though

[pale epoch]

thats what the parentheses around sqrt(n) mean

$\left\lceil \sqrt{n} \right\rceil$

[vital dew]

Lochverstärker

[wide vine]

thats neat seeing they never introduced that

actually not only did they not introduce it

it is in the next unit

-_-

[pale epoch]

ok, thats just bad lmao

[wide vine]

thats really dumb that they didnt introduce it but also knowingly have it on the next unit of the book :/

okay well I guess I got it now

look at that part I see there is also a floor function that has similar notation

I really just thought they were some bugged looking brackets [ ]

[pale epoch]

if the "hooks" are on the lower end its floor

and the weird thing is that sometimes you use [] for flooring as well

[wide vine]

good thing it is located