i know the answer is 1 since both are prime numbers
#discrete-math
abstract ravine
but im still tryin to implement the euclidian algorithm
shit nvm its supposed to be a 6 not a 1
haughty garden
I think that falls under #geometry-and-trigonometry
abstract ravine
So im supposed to find all the integer solutions
what am i supposed to do after that(the image) then
haughty garden
After performing the Euclidean algorithm, reverse that process to get the values for x and y
abstract ravine
wdym by "reverse the process"
haughty garden
Start with the gcd which is 1 and write it in terms of 6 and 7 (ie 1 = 7 - 6)
Then replace 6 with 13 - 7
abstract ravine
ok but where did you get 7-6?
haughty garden
So you end up getting 1 = 7 - (13 - 7) = 2 x 7 - 13 x 1
haughty garden
ok but where did you get 7-6?
From the line above your last line
I recommend writing your Euclidean algorithm as:
13 = 7 * 1 + 6
7 = 6 * 1 + 1
6 = 1 * 6 + 0.
gcd = 1
From here, start with the second last line and rewrite it so that you have the remainder on one side
abstract ravine
ye i know, but the problem is i got a question that asked me to perform the euclidian algorithm that way
haughty garden
I don’t like that method because it’s messy and hard to follow but if you’re asked then I guess disregard my msg
Anyways, the idea is that you want to apply the Extended Euclidean Algorithm which allows you to find the values for x and y
That’s basically the process in reverse
haughty garden
Now you can see that this is basically of the form that you want right
You can rewrite it to 1 = 7 * 2 + 13 * (-1)
drifting pewter
Does anyone know how to do this with using a truth table to justify the answer?
haughty garden
Draw out a truth table and only consider the result of (not p) if all three hypotheses are true
haughty garden
Yeah the last hypothesis is a bit weird
(p and q) implies p must be true and q must be true.
(q -> r) implies that r must be true.
The last hypothesis becomes a contradiction
drifting pewter
So to write that the last hypothesis/premise was a contradiction would be a correct answer
haughty garden
Well when you have false premises, that can lead to either true or false conclusions
So I’d say it’s still logically valid
Validity is defined to be logically valid if it’s not invalid (this only happens when true premises lead to false conclusions)
haughty garden
They used the extended Euclidean algorithm to find the base solutions
Then the general solution becomes x = 4 + 0 mod 9 (this comes from the fact that we can write the expression as 7x = 1 - 9y ==> 7x = 1 mod 9) and y = -3 - 0 mod 7 (again this comes from the fact that we can write the expression as 9y = 1 - 7x ==> 9y = 1 mod 7).
So your general solution is x = 4 + 9n and y = -3 - 7n for integers n
drifting pewter
Ok so my truth table is right for A and B
Oh i didn’t send A truth table hold on
abstract ravine
Then the general solution becomes x = 4 + 0 mod 9 (this comes from the fact that...
i see ok
surreal orbit
Can someone help me with a)? I'm pretty confused on how to write this
ebon valve
surreal orbit
I believe thats false
If a|b then gcd(a,b)=a
surreal orbit
that looks correct to mee
surreal orbit
Can someone help me with a)? I'm pretty confused on how to write this
I could still use the help on this if anyone is up for it 🙁
ocean coyote
They used the extended Euclidean algorithm to find the base solutions
in one of my books it shows this as radix representation. later in the book it has the euclidian algorithm in great detail but it depends on the theorem earlier in the book.
they are all related though
formal tulip
Does anyone here know recursive decent parser?
Would the string baab be accepted in this grammar?
brazen vessel
Anybody knows about rules of inference?
I've got a question 
echo rivet
Hey, do you guys know how to count possible connections on undirected grah with multiple edges?
brazen vessel
what do you mean by multiple edges?
echo rivet
two nodes can be connected using two or more edges
abstract ravine
Hey so im learning about logic
and i came across if-then and if-and-only-if
from my understanding
if-then works like this: If you study, then you will pass
if-and-only-if works like this: if you pass, then you must have studied
but this doesnt sound like a proposition
you can pass without studying
lol
idk if im making sense or im just confused
fluid summit
So I've come to a conclusion that a the number of Hamilton path between two vertices in a complete graph with 2n+2 vertices is given by 1/2(2n+1)!. However if I were to make separate sub graph with all the same vertices but remove the edges between {v2i, v2i+1} for i=1, ..., n then how many path Hamilton path are there? My main goal is to find the limit of the ratio of number of paths in sub graph and the initial graph as n goes to infinity.
CAn anybody help me solve this problem?
abstract ravine
is Absorbtion law the same as tautology law in logics?
abstract ravine
anyone knows what law was used for the last logical result?
<@&286206848099549185>
nimble ember
Because both statements are equal, they can be simplified into one expression I think. @abstract ravine
nimble ember
Probably Idempotent
If you look at the Idempotent law, both LHS/RHS are equivalent
If you want to see it more clearly, let (-p v q) = z
that means you have z v z
which can be simplified to z
nimble ember
np
mystic moss
@fluid summit what exactly did you mean by 1/2(2n+1)!, and how did you get this? is this the number of paths between two specific vertices or did you also get to choose which vertices you start/end at?
abstract ravine
So, im supposed to simplify this boolean expression
Im supposed to name every law i used
But how does this look, its wrong right?
abstract ravine
<@&286206848099549185>
surreal orbit
hiii Im pretty confused on how to do this
I believe I have to write the relation as a matrix but Im not sure how to do that??
foggy hatch
Does R^2 here mean something like "the relation S where xSz exactly when xRy and yRz for some y"?
Because my initial reading of part (a) made part (b) such a weird thing to ask I guess it's gotta be something like that. Edit: It seems that's pretty standard, yup.
fluid summit
<@!759277419298291713> what exactly did you mean by 1/2(2n+1)!, and how did you ...
sorry should have been more clearer. I used the formula (n-1)!/2 for 2n-1 vertices. Yes the starting and ending vertices are the first 1 and the last one. @mystic moss
(idk if I am right though)
surreal orbit
Because my initial reading of part (a) made part (b) such a weird thing to ask I...
Oofie I thought R^2 meant I had to write the relation as a matrix and do a matrix multiplication but like it sounds like im way off lmao
lost marsh
hello? can i ask a discrete math question here?
quaint star
Yes
minor dagger
no this channel is for discrete math not discrete math
quaint star
If I tell you "There is an apple that is red"
That statement is false if ALL APPLES are NOT RED
So the negation of a there exists is for all
And the reverse, the negation of for all is there exists
So you just flip all the quantifies and then negate the statement
$\forall x \in A \exists y \in B, P(x, y)$ negated is $exists x \in A \forall y \in B, \neg P(x, y) $
vital dewBOT
Lunasong
quaint star
@safe nest
safe nest
yeah this still really confuses me
quaint star
Okay, you're going to have to be more specific about what you didn't understand
safe nest
its just that these tasks are old and we haven't touched them in a while, completely lost i will just go back and watch my lectures to figure it out
but thanks anyways
as lost as i am rn, i dont think u can help me xD
quaint star
Uh okay
rocky mirage
Hi everyone. I need to convert this formula into the perfect conjunctive normal form. How can I do that?
~ is negation (~0=1, ~1=0), v is or, ^ is and
rocky mirage
I guess I kinda did it: (~X v ~Y) ^ (X v ~Y) ^ (X v Y)
neat grove
#discrete-math Here comes another question about relations. So, if M is a set m≥2, R is a relation on P(M) defined by (U,V)∈R if and only if U∩V=∅. What qualities does it have? refl., sym., trans.?
surreal orbit
is the E! is AxAzE!yP(x,y,z) the same as not exists?
mystic moss
sorry should have been more clearer. I used the formula (n-1)!/2 for 2n-1 vertic...
yeah i still don't get it
a) how did you get (n-1)!/2?
b) are you given specific first/last vertices?
fluid summit
yeah i still don't get it
a) how did you get (n-1)!/2?
b) are you given specific...
Ohh sorry I meant, I'm using the formula for no of hamitonian path in a n vertex graph which is given as (n-1)!/2.
And yes i"m specifically given first and last vertex.
Edit: Hold on, by using keeping the two vertex fixed we can say that using 2n remaining vertex we can create 2n! hamiltonian path. is this correct? If yes, how do i extend this to the subgraph with n {V2i, V2i+1} edges removed.
mystic moss
Ohh sorry I meant, I'm using the formula for no of hamitonian path in a n vertex...
yeah, i was thinking 2n! as well. and maybe something to think about is that when you remove the "even" edges, now each vertex (except for the ends) has exactly one less "neighbor" in the graph. but firstly why do you want to find the limit as n goes to infinity...? like is this a hw problem? (why would you take away half of a particular hp in the first place?)
orchid dust
Question:
You need to form a 6-character password, but you can only use letters A, B and C. Every password must contain at least 1x A, 1x B and 1x C. How many passwords are possible?
I counted 7200, but I know that it's not correct because I'm counting some passwords multiple times such as
A B C C C C
because in my approach reordering the C's are distinct permutations
fluid summit
yeah, i was thinking 2n! as well. and maybe something to think about is that whe...
yes, this was an assignment (but the prof never posted an answer so I wanted to actually know how to solve this for the finals) I don't suppose the no of HP path decreases by 1/2, can you give me a little more clarification for that? @mystic moss
fallow raft
Step 1: Chose a spot for the required A - $$\binom{6}{1}$$
Step 2: Chose a spot for the required B - $$\binom{5}{1}$$
Step 3: Chose a spot for the required C - $$\binom{4}{1}$$
Step 4: Chose the remaining elements for the remaining 3 spots - $$\binom{3+3-1}{3}$$
Per MR - $$\binom{6}{1}\binom{5}{1}\binom{4}{1}\binom{3+3-1}{3}$$
this might be a valid consruction, but Im not 100% @orchid dust
vital dewBOT
AH
orchid dust
I think with this you run into the same problem that I described above
@fallow raft With step 4 you consider passwords like A B C(1) C(2) C(3) C(4) and A B C(2) C(1) C(3) C(4) to be distinct passwords but they are the same in practice
mystic moss
yes, this was an assignment (but the prof never posted an answer so I wanted to ...
i didn't mean that the number of paths decreases by 1/2, i was questioning why you would choose a path and delete "even" edges in the first place. it's interesting that you'd need this for finals, have you been given any other problem like this?
haughty garden
Step 4 should be 3^3 as you have three options for the remaining spots
abstract ravine
@pale epoch sometimes im forced to ping you.......................................................................................................................................................................... do you know about Boolean algebra simplification ?
orchid dust
Question:
You need to form a 6-character password, but you can only use letters ...
Anyone got another clue? I calculated it using Python and got 540, but I still have no clue how to prove it
haughty garden
@orchid dust the question actually reduces down to finding the number of ways of arranging the A's, B's and C's in three positions (we fix an A, B, and a C in place)
So instead of looking at all six positions (with restriction), let's look at three positions (without restrictions). We take cases.
Case 1: All three positions are taken by a single letter. The number of ways of choosing such a combination is simply 3 (either all A, all B, or all C).
Case 2: The three positions are taken by a pair and an additional letter. The pair can be selected as follows: from 3 different letters, pick 1 to be the pair P(3, 1) and then the remaining letter can be chosen from either remaining letters. Hence, the pair and additional letter can be chosen in 3 * 2 ways.
Case 3: All three positions are taken by distinct letters. This is done in 1 way because we treat each combination as the same (BAC == ABC == CAB etc.) Remember that we're just taking combinations of letters and not arrangements.
Now, we start arranging these with the single A, B, and C letter we imposed earlier.
Case 1: We can arrange them in 3 * 6! ways (the number of combinations multiplied by arrangements in a line). But we double count certain cases. These occur because we treat A B C_1 C_2 C_3 C_4 as the same as if, say, C_2 and C_3 were swapped. We can reduce the number of cases by dividing by 4! and this occurs regardless of which letter we chose (so case 1 can be arranged in 3 * 6! / 4! ways.
Case 2: We can arrange them in (3 * 2 * 6!) ways (again, it's the #combinations multiplied by arrangements in a line). But this time, we double count 2 letters (hopefully you can see why). This gives us (3 * 2 * 6!) / (3! * 2!). Hopefully, you can see why we divide by 3! * 2! as well (lmk if it's not clear).
Case 3: We can arrange them in 6! ways (the #combinations in case 3 is actually 1). Hence, we have 6!/2^3 ways.
Adding these cases up gives us 540 different ways.
fluid summit
i didn't mean that the number of paths decreases by 1/2, i was questioning why y...
Not really. This is from my assignment. Any tips for bn?
orchid dust
Now, we start arranging these with the single A, B, and C letter we imposed earl...
that's a very good explanation. thank you so much
mystic moss
Not really. This is from my assignment. Any tips for bn?
hm i haven't got any rn, i'll think about it perhaps. what were the other problems on the assignment like?
warped magnet
Hi guys. I'm not sure how to solve this problem:
I have 2 Algorithms. Both depend on 2 variables, V and E, (Vertices and Edges) and each has a different time complexity. I have timed both algorithms on different Densities D(V, E) = 2E/V, and different V's. I wanted to achieve the relation between V and E that tells me at what point one algorithm becomes better than the other. Example: F(V, E) > 0 ----> Use Alg1, F(V, E) < 0 ----> Use Alg2. How would I achieve that?
Can I get some help here?
amber hill
Is there anything more given?
Like time complexity, or iterations, or any operations?
warped magnet
I have the times for each density and different Vs with the same densities
I could time it differently
amber hill
So, can you time two different algorithm with same density an compare their time?
iterate this for few values and then
warped magnet
The table should be like this
I can calculate the breaking point of alg1 and alg2 on each V. But would I use a linear graph?
And then what would I do with each breaking point?
warped magnet
what density are you talking about? d1?
amber hill
isn't density a function of E and V
warped magnet
Oh I see what you mean
warped magnet
but I wont know how long t1 and t1' will be, so I had to make a function that depended only on V and E.
amber hill
But , caution: I am not a computer science student, so I might be wrong.
amber hill
but I wont know how long `t1` and `t1'` will be, so I had to make a function tha...
Well, in that case we think we needmore information what the algorithm is about.
warped magnet
but you have the times, doesnt that tell you about the complexity?
But maybe that's where I'm wrong and my problem is just unsolvable
warped magnet
Let me explain myself better
I timed it now, in the present, for different densities and number of Vertices and for both algorithms. But when I run the program again, I wont know the time the program takes to run with the number of V and E they will give me, so I have to predict which algorithm will be better based only on the number of V and E
amber hill
if you have the initial values of densities and time, then there must be a peak point at which the one algorithm outperforms other.
warped magnet
Exactly, but there's a different breaking point for each Starting V
amber hill
is this dijkstra?
warped magnet
No, not really, it's a whole program, so it doesnt have just 1 algorithm
warped magnet
But it's not about the computer science, it's literally just about math
For 3 different starting V's I have the Density where one Alg becomes better than the other
amber hill
does this work? F(V1, E1) = (peak point - d1)
warped magnet
your peak point is the peak point of V1 right?
if yes it would be true but only for V1.
Oh yeah you wrote F(V1, E1), that is correct I believe
amber hill
I am not really sure, but if that makes sense to you. then ok
warped magnet
It's alright, I'll think about this some other day
fluid summit
hm i haven't got any rn, i'll think about it perhaps. what were the other proble...
There are 5 shirts and 5 pants. We want to arrange them into 5 pairs of 2 each.
What is the expectation and the variance of the number of pairs that have of one
shirt and one pant? (An example, I don't need a solution for this)
scarlet walrus
😄
foggy cloud
am I allowed to use an induction proof within cases within an induction proof?
I.E. Use induction to prove p(x) is true, show base case, then case 1, case2 within the induction step
then in case 2, use induction to show that a helper proof is true and use that helper proof to show case 2 is true
haughty garden
I don’t see why not
As long as you show the helper is true, you’re free to use any form of proof you like
You may like to structure it so that you prove the helper as a lemma before proceeding with the actual proof
green latch
does saying set A intersects U (universal set) count as using set identities? or would it have to be like set A ∧ U
shrewd oriole
does saying set A intersects U (universal set) count as using set identities? or...
Well you're more so using the fact that $A\subset U \implies A\cap U = A$.
vital dewBOT
Trichloromethane
gritty crescent
We have distributed 200 balls within 100 boxes in such a way that no box gets more than 100 balls and each box gets at least 1 ball. Prove that it is possible to find some boxes such that they together contain exactly 100 balls.
I don't know how to proceed with this problem. A hint would be appreciated.
stray reef
group the boxes by their ball count
group 1 will contain the boxes with 1 ball each, group 2 will contain the boxes with 2 balls each, etc.
there will be 99 such groups
pigeonhole
ah wait no hold on
i misread
gritty crescent
Sorry, but can you elaborate a bit more on how to use pigeonhole?
stray reef
disregard this
gritty crescent
Aah oki.
gritty crescent
Lmao
stray reef
im getting obviously BS results but i cant see why theyre BS
gritty crescent
Lemme check if the book has hints/solutions.
stray reef
im getting that the count of 1-ball boxes must be ≤ 0 and i'm about to figuratively rip my hair out
coral raven
isn't this trivial?
okay so you can start off from 100 boxes with 2 balls each
and you can easily make 100 from those
and then any other combination you can make by shuffling balls
stray reef
but who said it had to be 2 in each
coral raven
and if you go to like 1, 3
stray reef
what do you mean by shuffling
coral raven
you can just combine those
coral raven
you can make any other arrangement by taking balls out of some and putting them into others
gritty crescent
Ahhhh I feel like killing the Discord CEO
coral raven
right
gritty crescent
Welp, it happens to have a full blown solution. Should have bothered looking earlier.
stray reef
oh yeah
thats possible
kaisheng your idea looks way way way too vague to go in a proof
coral raven
probably
brave cedar
Is there special sign to indicate edge and level triggered in flipflop?
Like somewhere I see arrow head type as level triggered while same as edge triggered on another source
past iris
I don't know if this is formal or not but my professor taught us to use vertical arrows for edge Triggered and horizontal arrows for level triggered
potent oracle
if anyone can help me with some questions dm me
doing a test and need some answers
coral raven
sorry, we're all outta answers, but i have some very nice reaction memes for you
guaranteed at least secondhand
potent oracle
ah I'd like that if I had some time
you can save it for the next person who asks though or post them here regardless
that would be pretty good
frozen tapir
Do you guys know where I can find some discrete maths exercises (possibly with solutions) ?
green latch
so im trying to prove f(x) =⌈x⌉ is surjective, how can I get y=⌈x⌉ in terms of x? or is it basically in terms of x already?
obtuse lance
surjective? on what set?
green latch
for f:R->Z by f(x)=⌈x⌉
coral raven
so you can just explicitly list a set x such that f(x) is surjective over Z? i think that would do it?
green latch
dont i have to prove that every element in Z is in the range of f?
coral raven
sure?
green latch
im sorry im lost, my teacher only gave one example of proofing a function is onto, so im basing off that one example
lyric pumice
@gritty crescent
gritty crescent
Have I been pinged in hopes of getting help? You're in for a disappointment.
lyric pumice
Observe that the result is greater than 0 for some m>=0 when a=b=200 and n=x=100.
@gritty crescent
lyric pumice
The problem is partly solved. The computation must be carried out for 0<=m<=100. It is likely that the computation can be algebraically simplified. @green latch
green latch
ok yea so im lost on how to show that all elements of Z are in R through the function f(x) = ⌈x⌉ cause the example my teacher did was proofing f:(0,inf) -> R by f(x)=ln(x) and he showed tht by having x=e^y and showed e^y is in domain (0,inf). Then f(x)=ln(x)=ln(e^y)=y
uh i think you pinged wrong person?
lyric pumice
The formula counts the number of distributions that can be made by giving between a and b objects to n recipients so that each of m recipients receives x objects. @gritty crescent
gritty crescent
That's pretty awesome, although I'll need some time to process that haha.
Thanks for the insight, much appreciated. 😄
obtuse lance
@green latch surjective just means every element of Z gets mapped onto, so you just have to show you can pick x so that f(x) hits every integer
green latch
would i have to show ⌈x⌉ then plug in for what x= and get it to equal y? how would i get y= ⌈x⌉ into x= cause i've never dealt with ⌈ ⌉ before. would it just be x=⌈y⌉ or something
obtuse lance
all the ceiling function does is round up to the nearest integer
I'll just show you the answer since I feel like you've struggled enough
all you have to do is pick x to be an integer
f(x)=⌈x⌉=x
for instance, ⌈3⌉=3
⌈-12⌉=-12
etc
every integer rounded up is just itself, so that proves it's surjective
lyric pumice
@gritty crescent I'm sorry. I misrepresented the problem.
gritty crescent
Ohh, no worries. I appreciate you for devoting your time. 😄
lyric pumice
@gritty crescent A proper formulation would be very convoluted. I would like to attempt it.
gritty crescent
It's alright, no worries. Really, really appreciate you sacrificing your time for all this.
obtuse lance
@gritty crescent he wouldn't do it if he didn't enjoy it lol
gritty crescent
Fair enough lol, but I'm thankful for someone putting in their time into a problem which just went over my head.
safe scroll
coral raven
when is a binary number odd
surreal bay
I already proved that S is a subset of T, so I just need to prove the other part
coral raven
find something in T not in S?
surreal bay
how would I show that for example, 15 isn't in set S?
surreal bay
but that's not really a formal proof or can I just write that 15 =/= 12s (mod 42)?
coral raven
i've done it fairly formally imo lol
wait actually
hmmm
uh oh
wait what am i worried about it clearly doesn't have an inverse mod 42
because 12s is even and 15 is odd
surreal bay
so, how would you format the proof?
coral raven
find an element in T not in S
explaining why it isn't in S
so therefore S is a subset of T, but S =/= T so it is a proper subset
surreal bay
okay thanks
autumn star
Hey guys , I’m about to take discrete next semester any tips to prepare for it ? My schedule is overloaded so I’m worried that if I don’t get it right away I will be playing catch-up the whole semester
drifting sail
if your discrete is the "intro to proofs + discrete" kind I'd say prepare for the intro to proofs part, there's plenty of free, quality resources such as Hammack's Book of Proof
otherwise idk, I like to read the syllabus and skim over the rec. books or previously recorded lectures if such a thing exists — but that applies to any course
plucky flicker
https://i.stack.imgur.com/0vgUK.png
If someone could explain the steps to solve this and how the answer was derived, I was really appreciate it. Thanks!
wild merlin
@plucky flicker what do you think
put some values into f
1 |-> 5 and 3 |-> 5 so it's not one to one
so it's also not onto by the pigeonhole principle
plucky flicker
I think I'm misunderstanding the question, but I think I can solve it if I understand where to begin.
Would I graph the numbers in J6 in a chart plug in into the output of f(m) as the second chart, and see if those are one-to-one? I guess I'm confused on how J6 and f(m) relate @wild merlin
plucky flicker
so each J6 corresponds to m in f(m)? @wild merlin
What would be the best approach to this then?
wild merlin
so each J6 corresponds to m in f(m)? <@!443489055590711297>
hm?
wild merlin
6 isn't in J_6
J_6 = {0, 1, 2, 3, 4, 5}
also, that isn't the definition of onto
if it was then every function would be onto
onto means that every element in the codomain has a preimage, not that every element in the image has a preimage
your codomain is J_6 = {0, 1, 2, 3, 4, 5}
0 and 3 have no preimage
i.e: nothing maps to them
say domain, preimage, image, codomain instead of input and output
it's more precise terminology and helps you understand the meaning of onto and 1-1 better
plucky flicker
preimage is the input, and image is the output, correct?
wild merlin
for a total function domain = preimage
output can refer to image, codomain or range or etc
do you understand why it's not onto though
plucky flicker
hmm, so every element of 0-5 (the codomain) must map to an element in of the output, or the image?
is the definition ^ @wild merlin
What do you mean by 0 and 3 do not have a preimage?
wild merlin
every element in the codomain must be mapped to by an element in the domain
f: X → Y is onto if for every y in Y, there exists an x in X such that y = f(x)
take your function for example
is there an x in {0, 1, 2, 3, 4, 5} such that 0 = f(x)?
well no, because as you've shown, all of 0 to 5 map to either 2, 5, 4 or 1
nothing maps to 0, nothing maps to 3
plucky flicker
oh okay, so of J_6, those elements 0 and 3 are not present. Meaning it would need to also be a part of the image for it to be onto?
wild merlin
here is a total function f with domain X, codomain Y and image f(X)
if the yellow set (the image) coincides with the blue set (the codomain) entirely, then f is onto
plucky flicker
so all of the x values would need to be present in the codomain
wild merlin
in your question, 0 and 3 are elements in the blue set that are not in the yellow one
plucky flicker
So the correct justification would be: f is not onto because the resulting image does not contain all elements of the codomain
the preimage is considered the red area?
wild merlin
yes
this is a total function so the domain and preimage always coincide
in a partial function where the preimage doesn't coincide with the domain, we would have another set inside the red like how the yellow is inside the blue
and that would be the preimage inside the domain
also
when you do a diagram like this
make sure for the output you label every element of the codomain
plucky flicker
okay, that makes sense that the red and yellow would be the same
wild merlin
make sure for the output you label every element of the codomain
that way you can easily see if something doesn't 'get hit'
plucky flicker
so I would need to include 0 and 3
wild merlin
yeah
like
two columns of 0, 1, 2, 3, 4, 5
and then put 0 in and draw an arrow
then 1, then 2 and like that
a 1-1 will have no two arrows going to the same thing
an onto will hit everything
plucky flicker
for one-to-one functions, would you refer the the input and outputs as image/preimage/codomain as well?
wild merlin
in a one to one function we have for any x, y in the domain, and x≠y then f(x)≠f(y) in the image
so different elements will map to different elements
if you say image you can also say codomain since image is a subset of the codomain
you might've seen the contrapositive of this
f(x)=f(y) => x=y
wild merlin
in a one to one function we have for any x, y in the domain, and x≠y then f(x)≠f...
i think this one is easier to conceptualise though
plucky flicker
yes, for sure. I think that clarifies the concept a lot! Thank you so much!
near wind
can someone help me with this problem. I am confused. Thanksss
i got {15,21}, would that be correct?
naive saffron
yes
near wind
thank you!!!
naive saffron
now give me 10 dollars
near wind
lol
naive saffron
for legal reasons that was a joke
valid wave
Thoughts on needing an 80 to pass discrete math final
how fucked am I
😢
been spam studying
mortal crescent
@here Could someone help with this discrete question?
So far, I think a) false, counterexample would be if f(x) = x and g(x) = 1, then x+1 would be one-to-one.
b) false because if f(x) = 2x and g(x) = -2x, then f+g would not be onto because not all elements of the codomain would be mapped to.
However, for all the others, I'm a bit stumped.
unreal stump
C would be true and D would be false
Take f(x)=x and g(x)=x^2 ,(1,4) is in codomain of h(x) but not achieved for any value of x
robust light
can someone help explain equivalence classes to me?
i've been struggling to wrap my head around it for an hour
unreal stump
What exactly are you struggling with?
Like why do we care about equivalence classes?
robust light
just reviewing things on equivalence relations, lots of people online seem to discuss it regarding sets of points, but this question has an equation
but this review problem i'm looking at has a set defined by x^2−5x.
unreal stump
Take the relation R and check for what values of f, x^2-5x R f is satisfied
Those values will be the set you need
robust light
so I take the values in S and plug it into the equation to get the "y's", yea?
or at least the numbers we're looking at
unreal stump
Yes
The special thing about R being an equivalence,is if you take any other element in that obtained set and repeat this, you will get the same set again
robust light
okay, and from my understanding, equivalence classes is the amount of sets of y's equal the same thing
unreal stump
Equivalence class of a is the set of y's for aRy is true
robust light
so, can you give me an example of one class?
still having trouble wrapping my head around it
robust light
alright, sorry, still difficult to get, but can you walk me through getting one of those numbers?
sorry, been super sick lately so I've been trying to catch up on a lot
unreal stump
If 5 divides a-4,that implies a-4=5k for some integer k
Which means a=5k+4,for some integer k
Substituting k=...-2,-1,0,1,2... You get that set
robust light
If 5 divides a-4,that implies a-4=5k for some integer k
Where are you getting this part? Is it from solving the equation given? Or is it something else. Sorry for all the stupid questions
robust light
that makes sense, but where does the -4 and 5 come from?
unreal stump
Definition of that equivalence
mortal crescent
Take f(x)=x and g(x)=x^2 ,(1,4) is in codomain of h(x) but not achieved for any ...
I tried it out - this example would work for both c and d, right? unless i'm mistaken
regarding this question https://discordapp.com/channels/268882317391429632/496785905474994186/788307762848858122
robust light
definition of the equivalence as in, relating to f(x) = x^2 - 5x?
unreal stump
Take aRb if 5 divides (a-b)
This
robust light
would "5 divides (a-b)" be universal to all similar problems (different equations and whatnot)
valid trench
would someone mind helping me with these 3 questions? ive spent over an hour on it and cannot figure it out, thank you
unreal stump
I don't know what universal means here
robust light
sorry, i'm being vague
if i were to get a similar problem with an equation like, say, f(x) = x^2 +27x, would I still do "5 divides (a-b)"
robust light
i'm asking how 5 divides a-b relates the current problem
unreal stump
It's a different problem
Completely unrelated
You do something else in that case based on what your R is
robust light
ah, okay
It's just asking for the equivalence classes of this: Suppose S={0,1,2, . . . ,10} and f:S→Z is defined by f(x) =x^2−5x. If, for x, y∈S,xρy means f(x) =f(y), then ρ is an equivalence relation.
unreal stump
yea, Just use the properties
f(x)=f(x)(Reflexive xRx)
f(x)=f(y) implies f(y)=f(x) (symmetric)
f(x)=f(y) and f(y)=f(z) implies f(x)=f(z)
robust light
what would z be, in this case
unreal stump
Some number in S
robust light
ah, but so would x and y, right? which would all be plugged into the equation given
unreal stump
Yes
minor dagger
those are the properties of an equivalence relation
a relation that is reflexive, symmetric, and transitive
the equivalence relation partitions the set
into equivalence classes
vital dewBOT
xdres
brave lava
<@&286206848099549185>
twin rock
yeah sure
this works
okay yes there are 3 1s in an identity matrix
how many 1s are in each row
robust light
14
twin rock
no in an identity matrix
twin rock
so in particular
(3)1 + (3)1
=6
not 3
so do you see why you are counting the total number of 1s wrong?
robust light
well, there's 14 in rows and 12 in columns
twin rock
Well, every 1 is in some row, right?
twin rock
no sorry I think you're still a little confused
robust light
im very confused
robust light
got it
twin rock
that has nothing to do w this
i just used identity because you would know what it looks like
Here think about this: how many 1s are in the 3x3 identity
robust light
3
twin rock
how many rows
twin rock
how many per row
robust light
1
twin rock
So rows * 1s per row =?
robust light
3?
twin rock
Yep
robust light
got it
twin rock
Which is all the 1s
The point is that because every 1 is in some row
if you count all the rows and all the 1s in those rows
you count all the 1s
you could do the same thing with columns
(if you are having trouble believing this draw out some matricies with 0s and 1s and try it)
robust light
no i believe you i just feel like i'm either over or underthinking it
there's 12 1's in the columns
and if it's like 1's where there's a 1 in each row
then there would be 12 columns but that feels too obvious
twin rock
not quite
so like
all i am saying is that if you know how many rows you have
and how many 1s in each of them
that's all the 1s in the matrix
because every 1 is in some row
robust light
hmm, okay
but we dont know the columns
but we know the amount of 1's in the columns
i'm not quite sure where to go from there then
robust light
rows
twin rock
(You only have enough information to do one of them)
robust light
the rows
twin rock
and?
robust light
...columns also?
twin rock
Yes
rows * (1s per row)
and
columns * (1s per column)
both count the 1s
do you see why?
twin rock
Huh?
can you remind me of the original numbers
Okay so those two formulas above
they count the same thing
that means they are?
robust light
Each entry of the matrix M is 0 or 1. Each row of M contains exactly 14 1’s. Each column of M contains exactly 12 1’s. M has 60 rows. How many columns does M have?
twin rock
Did you see my questions above
twin rock
what would
robust light
the two formulas above being equal to one another
twin rock
so they have to be equal
so you know rows * (1s per row)=cols * (1s per cols)
and you know 3 of those inputs, right?
twin rock
yes
robust light
14^2 = 12 cols?
twin rock
yes
minor dagger
3|(m^2-n^2)
you need values for m,n that satisfy this
mRn only if this is true
pick values m,n from A such that m^2-n^2 is divisible by 3
shut jacinth
i see
minor dagger
for example, m = -4, n = 1 -> (-4)^2 - 1^2 = 15
3|15
so -4R1
does that make sense
minor dagger
do you have the problem?
whats confusing you
well an equivalence relation partitions the set into equivalence classes
that set has already been partitioned
so draw each part
weary tiger
draw each possible combination of edges?
weary tiger
sorry
minor dagger
i meant draw each part of whats given if that graph represents the equivalence relation then it should already be partitioned into equivalence classes
soar the easiest way is to write out what relates to what
start with the smallest element and work your way up
find what relates to it and make a set
if you do this for every element you would find some sets will be the same
the unique sets will be the equivalence classes
the sets either have to be completely disjoint or equal
take all the disjoint ones that will be all your equivalences classes
shut jacinth
so start with
-4?
@minor dagger i made a function in desmos f(m,n)
so can i just run thru all the values and put in whats divisible by 3?
$f(m,n)=\frac{(m^2-n^2)}{3}$
vital dewBOT
soar
minor dagger
if the output of this function is a natural number then you can say mRn sure
errant bear
m and n?
shut jacinth
ye
errant bear
im answering you
shut jacinth
in the form of a question lul
each class has to be distinct though
so should i go -4, -1, 2, 5?
and then -3, 0, 3, 6
upbeat trail
wild merlin
@upbeat trail you can use the extended euclidean algorithm on gcd(64, 149)
pale epoch
well, how did you define complexity
opaque fern
@pale epoch nott to sure
pale epoch
well, then look it up
opaque fern
Is that the Natural log of a number @pale epoch
pale epoch
what
opaque fern
I’m not sure rhen
pale epoch
then you have to study and look at your notes
how do you want to answer the question if you dont understand it?
minor dagger
are you looking for time conplexity?
should run log n on average
i think at least 😳
im a bad computer scientist
pale epoch
what
minor dagger
idk maybe im thinking of tree algorithms
pale epoch
what
not every algorithm runs in logarithmic time
the one given here certainly does not
pale epoch
set up a system of equations
opaque fern
@pale epoch i solved the question i sent earlier can u review it
pale epoch
what's your solution
pale epoch
oh that one
opaque fern
yea
pale epoch
,w sum from i=1 to n of sum from j=1 to 100 of sum from k=j to n of 1
vital dewBOT
pale epoch
i mean, your final result is still correct
opaque fern
just the working
pale epoch
how'd you arrive at that sum you are calculating
mystic moss
(@opaque fern incidentally, would you take into account the time to add a log-n digit number, or would you assume that's constant time?)
pale epoch
the two inner for loops run n + (n-1) + ... + (n-100) times
(module off by one)
and the outermost for loop runs n times
so you get n times that sum
and thats something of order n^2
with such things you can assume that addings numbers takes constant time
because they are 16 bit or wtv
and adding numbers of fixed size takes constant time
it certainly would not depend on n in this case
mystic moss
fair enough, so log-n is insignificantly large compared to n itself
pale epoch
well, two things
you are adding numbers that have nothing to do with n
and number on computer have fixed size, say 16 bit
and adding those then takes log(16) time or whatever
but that's a constant
but yeah, i guess to be 100% exact
mystic moss
we're adding ij, which does have to do with n right (i can be at most n). but yeah i get what you're saying, and i'm guessing the reason we don't say O(n) is also constant time is because 16 is insignificant compared to 2^16
pale epoch
you would have to not add 1 in my calculation above
but add some constant
also the multiplication has worse runtime
(probably n^2 in the input size)
but that only really becomes "a problem" if you add/multiply really large numbers
mystic moss
hm okay thanks
pale epoch
if your n becomes so big that ij (or S) doesnt fit in a normal int anymore
then the analysis becomes "wrong"
also to the original question, i have no idea what tractable or intractable means
pale epoch
ok, ehm
how did you come up with the n(1 + 100 + 2(...))
because your comments next to the code are correct, but
if you look at the 2 innermost for loops
they run n + (n-1) + (n-2) + ... + (n-100) times
because for j=1 the innermost run n times, then for j=2, it runs n-1 times and so on
and this whole thing runs n times inside the outermost loop
opaque fern
yea
pale epoch
so you should arrive at n*(n + (n-1) + ... + (n-100))
and + 2 for the stuff that runs once
and solving this you arrive at uh
,w n * sum of n-i from i=0 to 100
actually
,w n * sum of n-i from i=0 to 99
vital dewBOT
pale epoch
as i said your result is still correct
you are only off by a factor of 2 and some constants
O(n^2) is still the correct answer
opaque fern
O(n^2) is still the correct answer
okay
i need some help with this forgot it sort of
@pale epoch ^
pale epoch
what's Q and S
opaque fern
The predicates i guess
pale epoch
it seems like there is some information lacking
opaque fern
thats all of it
pale epoch
given those 5 statements, you want to prove Q(a) and S(a) for some a
opaque fern
yea;
opaque fern
How Would u go about it
pale epoch
(iv) will somehow give you Q(a)
you just have to prove not P(a) somehow
from the other stuff
opaque fern
Can u solve it so I can compare it I just got lost on an island doing jt
This is how far I got
pale epoch
(iii) and contraposition on (ii) gives you not P(a) for some a i guess
opaque fern
Okay
vital dewBOT
Lochverstärker
pale epoch
and then use (iv)
abstract ravine
could you just make n = 2k ?
sleek swallow
Suppose that $n$ is even. Then, there is a $k \in \bZ$ such that $n = 2k$. So:
$$n^2+3n-5 = 4k^2+6k-5 = 2(2k^2+3k-3)+1$$
since $2k^2+3k-3 \in \bZ$ and the above is of the form $2r+1$, it follows that it is odd and that's a contradiction.
vital dewBOT
Abhijeet Vats
sleek swallow
@opaque fern Does that make sense?
abstract ravine
So i have this Dophantine equation and im supposed to find an integer value
what do i do after the last step?
river mortar
lmao why is this channel under "early university"
By that logic even algebra can be classified as that
pale epoch
because "discrete math" is a class that is often taken in early university
sleek swallow
This won't do. Show some effort on your part first.
How would you check if both lists are identical?
@opaque fern
pine wave
Hello need quick help on some t/f questions
- 2 + -2 using a sign bit representation of -2 results in 0
- A + T =A
For the first one I'm leaning toward true but I dont get the second one
sleek swallow
You're first supposed to describe an algorithm for checking if the two lists are identical or not. So, just talk about how you'd tell if two lists are identical.
It's reasonable to first check if two lists have the same length or not, yes? If they don't have the same length, then they cannot be identical and checking anything else is pointless. Once you've checked that, then what do you do?
pine wave
can anyone help on my prev question ^^
wary terrace
Devise a recursive algorithm for computing bn mod m, where b, n, and m are integers with
m ≥ 2, n ≥ 0, and 1 ≤ b < m. How to solve this?
reef oasis
its when a function is one-to-one and onto
yea bijective also means that the function is invertible
thats what i am confused on how to do
wary terrace
Devise a recursive algorithm for computing bn mod m, where b, n, and m are integ...
<@&286206848099549185>
crude mural
Suppose we have a relation on the real numbers R. We say that two real numbers are related if their product is positive. (in other words xRy if xy > 0)Prove or disprove that this is an equivalence relation
oh ok so here are what i have so far. the properties of an equivalence relation are for it to be reflexive, transitive, and symmetric. when testing the reflexive property (xRx) i said it doesnt pass that property because a counter example would be 0, right? 0*0 = 0 and that doesnt satisfy the xy > 0 part. so since it's not reflexive then this cant be an equivalence relation.
not sure if my proof is correct tho or if i am approaching the problem correctly.
ocean coyote
I have a book that uses $\lor, &$ but I see latex has $\lor, \land$ what is more common?
vital dewBOT
galois
wary terrace
How to determine whether a tripartite graph is planar or not?
ocean coyote
wary terrace
<@!689888758744875009> https://math.stackexchange.com/questions/742659/planar-co...
thanks!
ocean coyote
ok
the book is from 1967 so I am trying to guess if this went out of fashion or if it is a thing
I once went crazy trying to find out if $\leqslant$ is the same as $\leq$
vital dewBOT
galois
ocean coyote
only the old books give me problems
unreal stump
What about those who do first order logic?
ocean coyote
I expect if it is in one book then it is in other books probably
this whole book has or and
so maybe that is how they do it in newer books
wary terrace
can someone suggest good tutorials and study materials for relations and graph theory
amber hill
rosen's book on discrete mathematics and it's application @wary terrace
ocean coyote
@abstract ravine
$$2^7=128, 2^4=16, |{0,1,2,3,4,5,6,7,8,9}|=10<16$$
vital dewBOT
galois
abstract ravine
Ah shit ok
drifting sail
What about those who do first order logic?
that's not "higher maths"; however a quick glance at recent arXiv papers on logic says that "wedge" and "vee" are more or less common in usage https://arxiv.org/list/math.LO/recent
but yes, if you're doing anything other than logic please save yourself and everyone else some trouble and write the actual words
ocean coyote
this book has $\forall x \exists v\lor ...$
vital dewBOT
galois
modest spoke
How would you even figure out that the symmetry property of this equivalence relation might be true before writing up the formal proof
vital dewBOT
derivada.schwarziana
drifting sail
that would be kind of cheating if you haven't seen integers modulo n yet, though. Without a firm grasp on that I don't think it'd be easy to guess that it should be an equiv. relation
modest spoke
I actually did figure that out with some chicken scratch work(not rigourously), but I still can't seem to make good sense of the symmetry proof here :/
viral zodiac
"if we roll a six-sided fair die three times and record results as an ordered list of length 3, how many outcomes contain exactly one 2 or exactly one 5?" Would 150 be correct?
modest spoke
@viral zodiac I believe so yes
haughty garden
Suppose that xRy. We want to show yRx for symmetry to hold. Beginning with xRy, this means that 4 | (x + 3y). Thus there is an integer a such that (x + 3y) = 4a.
We will digress a bit and consider the statement we want to prove: 4 | (y + 3x). This means there exists an integer b such that (y + 3x) = 4b. One key observation is that the coefficient of the x term is scaled by a factor of 3. Moreover multiplying the RHS by 3 does nothing to the overall expression. Finally, we can see that 9 = 1 (mod 4) since 9 = 4 * 2 + 1. Putting all of this together, we multiply the original expression by 3 to get the desired result.
(x + 3y) = 4a ==> 3(x + 3y) = 4(3b) ==> 3x + 9y = 4c where c = 3a.
Finally we can rewrite 9y as 4(2y) + y and move 4(2y) to the other side to get
3x + y = 4c - 4(2y) = 4(c - 2y).
But c - 2y is an integer for integers c and y. Thus we have 3x + y = 4d ==> 4 | (y + 3x) ==> symmetric
The only key insight is observing that multiplying both sides by 3 makes everything a lot simpler since nothing really changes to the overall expression but other algebraic manipulations come into play to extract that y out
weary tiger
John touches the screen to initiate the process. The pump requests to select a payment type. John selects, CASH. Following directions, he provides $30 in two bills. The pump takes the $30 and provides a credit to purchase gas. John lifts the pump hose and nozzle and proceeds to fill his car’s gas tank. At about the $20 point, the pump stops pumping gas and flashes an error on the screen—the pump’s storage tank is empty. The screen instructs John to go the cashier for a cash refund, which he does. List the states of the pump entered during this case study, in order. My order is Welcome, Payment Selection, Cash Transaction, Pump Gas, Maintenance, Accounting, Welcome. Does this seem correct?
valid wave
Hi question
if A then B. an instance where A is true and B is false is called like biconditonal?
modest spoke
thanks @haughty garden that was nice to see
wary terrace
Can we solve river crossing problem using vertex cover method?
dawn moon
Any recommendations for online discrete math calculators that would be useful for homework besides wolfram alpha?
daring crater
How do I arrive at the last line from the line above? How do I "iterate"?
c_1 and c_0 are 0 if it helps
unreal stump
You know how you can get n different equations?(The equations $\frac{C_r}{r+1}=\frac{C_{r-1}}{r} +\frac{2}{r+1}$ as you vary r from 2 to n)
vital dewBOT
DrunkenDrake
daring crater
Ok I see, thanks!
abstract ravine
What on earth is the first de morgans law
please i just cant afford wasting hours on this lmao
last timber
,w De Morgan laws
vital dewBOT
last timber
but which is first i guess book has to define
last timber
ok so they illustrate (A cap B)' = A' cup B'
abstract ravine
ok, why did they specifically do A cap B
last timber
first pic is just A cap B. then (A cap B)', then A' and B' on the two pics in second row and finally A' cup B'
last timber
because they want to show that (A cap B)' = (A') cup (B')
last timber
in first row the show you LHS of (A cap B)' = (A') cup (B')
i.e (A cap B)'
i mean they first show A cap B
so you see what you are complementing
then they show A', B' separately in the second row
and finally A' cup B'
abstract ravine
i mean they first show A cap B
why specifically this
last timber
so you see what you are complementing
this is kinda like when in solving (1+2)+4 in school you write each expression 1+2, then resulting 3+4 separately if you had such exercises
abstract ravine
ok why not (A cup b) first in the lower part
last timber
they just show all the steps
abstract ravine
and then (A cup B)`
last timber
because it won't be then illustration of de morgan law
(A cup B)' != (A cap B)'
but A' cup B' = (A cap B)'
ok gtg
bye
crystal dove
imo
If you translate this kind of basic logic homework to 0's and 1's
it gets a lot easier
or(a, b) := ab + a + b
not(a) := a + 1
De Morgan's laws become obvious in that context
modest spoke
Anybody familiar with this, what does it mean that each item in the set is it's own set?
Context
obtuse lance
P(A) is called the powerset of A, it's just the set of all subsets of A
abstract ravine
P(A) is called the powerset of A, it's just the set of all subsets of A
like all the possible subsets correct?
pliant lichen
does anyone know how to prove that 2^n * 3^m * 3^m+n
is an injection?
modest spoke
gotcha thanks @obtuse lance
minor dagger
yes its the set of all possible subsets of A @abstract ravine
abstract ravine
ok what if it's A = {1, {2}, 2, 6}
@minor dagger
what happens to the {2} and 2
minor dagger
well {2} is the set containing two so obviously its not the same as two
abstract ravine
will the set A have 2^4 possiblesubsets?
minor dagger
just treat it as an element
abstract ravine
oooooh
minor dagger
yes it will have 2^4 elements
minor dagger
all powersets have 2^n elements where n is the number of elements of the set
coral raven
oh, modular arithmetic
obtuse lance
@dreamy coral neat I made my own version just now with the same color scheme on accident lol
obtuse lance
it's modular arithmetic, idk past that
neat desmos lets you change line width now so you can get pretty good pictures
obtuse lance
I guess a mandala generator lol
you place the numbers 0 to N-1 on a circle in order, then write a line between a point n and the point m*n mod N
and these are the pictures you get
limber token
this is so cool
dreamy coral
N=1000 M=99 is very interesting on that generator
obtuse lance
@proven shard I worked out a formula for the outer shape
but they end up having different layers of inner shapes, interestingly
so like your example
I think I might be able to get an expression for the inner layers too
proven shard
hmmmm
obtuse lance
the way I got it was I wrote down an equation of the line between two points
$Y\left(t,x_{0}\right)=\frac{\sin(mt)-\sin(t)}{\cos(mt)-\cos(t)}(x_{0}-\cos(t))+\sin(t)$
vital dewBOT
Merosity
obtuse lance
then looked at the next line near it that intersects with it at t+dt
$Y(t+\Delta t,x_0) = Y(t, x_0)$
vital dewBOT
Merosity
obtuse lance
this gives us a condition to solve for x
then take the limit as Delta t->0
or, you can just take the derivative wrt t and set equal to 0
cobalt badge
How should I go about figuring out whether this graph is or is not planar?
Is looking for a k_3,3 subdivision from the start the best idea?
dreamy coral
the mandelbrot set is made up of a base cardiac curve and a perfect circle
ocean coyote
is there such a thing as an imperfect circle? asking for a friend
errant bear
no
forest maple
Is it right?
ocean coyote
@forest maple yes
forest maple
<@!644178886157926415> yes
Thank you
forest maple
<@!644178886157926415> yes
Is it ok if I send you my files and check them?
ocean coyote
why tho. I am not really the best person to ask about this stuff. I have limited knowledge.
also, why not post it here?
pale epoch
consider that a graph may be both
ocean coyote
perhaps it is implied in this context hamiltonian $\nsubseteq$ eulerian
vital dewBOT
galois
cursive lily
naive mural
What does that question even mean
frozen tapir
Could somebody help me with this exercise?
haughty garden
We can write i + 2013 as (i + 2012) + 1
Then observe that the two are almost identical so you suspect that it telescopes.
If you’re not sure, write out the first few terms and see what cancels
frozen tapir
Oh i see, thank you
zinc pecan
gangs
ocean coyote
that would be false if L1 and L2 are disjoint. the empty set is not $\in$ NP. the empty set is $\subset$ NP
vital dewBOT
galois
quaint star
a is, b is not
quaint star
Firstly, you can't say Let (a, a) be in S for all a.
You have to show that (a, a) is in S for all a
So just the way you wrote that is odd
And, it is symmetric
grave moon
Really ??
brave yarrow
Hey i have a question
how can i prove this
Prove the set of positive integer powers of 3, {3, 9, 27, 81, ...}, is countably infinite by defining a bijection from the positive integers to this set. Be sure to prove the function you define is a bijection.
pale epoch
by defining a bijection from the positive integers to this set
brave yarrow
can you give me an example
pale epoch
of what
amber hill
@grave moon it is antisymmetric too
quaint star
The even integers is countably infinite because you can define a bijection f(n) = 2n from the integers to the even integers. You can check that f is a bijection.
brave yarrow
so in that example would it be 3^n?
amber hill
well you can build a bijection.
eternal roost
but i believe instead of even integers would be integers where 3 is a factor or something