Tag Archives: function

Ways to prove a bijection

Posted on March 17, 2020 by Brent

You have a function and want to prove it is a bijection. What can you do? By the book A bijection is defined as a function which is both one-to-one and onto. So prove that is one-to-one, and prove that … Continue reading →

Posted in logic, proof | Tagged , , , , , , , , | 7 Comments

One-sided inverses, surjections, and injections

Posted on March 14, 2020 by Brent

Several commenters correctly answered the question from my previous post: if we have a function and such that for every , then is not necessarily invertible. Here are a few counterexamples: Commenter Buddha Buck came up with probably the simplest … Continue reading →

Posted in logic | Tagged , , , , , , | 1 Comment

Test your intuition: bijections

Posted on March 3, 2020 by Brent

Suppose we have sets and and a function (that is, ’s domain is and its codomain is ). Suppose there is another function such that for every . Is necessarily a bijection? That is, does necessarily match up each element … Continue reading →

Posted in logic | Tagged , , , | 12 Comments

A combinatorial proof: PIE a la mode!

Posted on October 25, 2019 by Brent

Continuing from my last post in this series, we’re trying to show that , where is defined as which is what we get when we start with a sequence of consecutive th powers and repeatedly take successive differences. Recall that … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | Comments Off on A combinatorial proof: PIE a la mode!

A combinatorial proof: counting bad functions

Posted on September 29, 2019 by Brent

In a previous post we derived the following expression: . We are trying to show that , in order to show that starting with a sequence of consecutive th powers and repeatedly taking successive differences will always result in . … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | 1 Comment

A combinatorial proof: functions and matchings

Posted on September 26, 2019 by Brent

We’re trying to prove the following equality (see my previous post for a recap of the story so far): In particular we’re trying to show that the two sides of this equation correspond to two different ways to count the … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | 5 Comments

Idempotent endofunctions

Posted on April 17, 2009 by Brent

Via Topological Musings comes another neat little counting problem. A function is idempotent if applying it twice gives the same result as applying it once: that is, for any input x. Endofunction is just a fancy way of talking about … Continue reading →

Posted in challenges, counting | Tagged , , | 8 Comments