10182

Relations and Functions between Small Sets

A relation between two sets is a subset of their Cartesian product. The subset's pairs are plotted in the graph. Click the dots on the left to add or delete pairs from the relation.

DETAILS

A relation between two sets and is a subset of the Cartesian product ; is called the source set and is called the target set. If contains elements and contains elements, there are relations between and . If is a relation between and , the inverse of is the subset of consisting of all pairs where belongs to .
A function is a relation that contains no two pairs with the same first coordinate and distinct second coordinates. A function can be thought of as a rule that assigns to each element in a subset of the source (called the domain now) exactly one element in the target. The range is the subset of the target that consists of elements to which some element of the domain has been assigned. The function maps the domain to the range, and if a function called assigns an element to an element , it is written as . The relation that defines a function, that is, the collection of all pairs of the form for in the domain, is called the graph of the function.
There are different functions that map an -element domain into an -element target. (The sets in question must be finite for any formulas to do with and , but the definitions apply to infinite sets such as the real numbers.)
A function is one-to-one (also called an injection) if no two elements of the domain are assigned to the same element of the range. Visually, a function is one-to-one if no horizontal line intersects its graph more than once. The inverse of a function is itself a function if and only if the function is an injection. For any injections to exist, the target must be at least as large as the domain, that is, , in which case there are injections mapping an -element domain into an -element target.
A function is onto (also called a surjection) if the target and the range are the same set. For any surjections to exist, the domain must be at least as large as the target, that is, , in which case there are surjections mapping an -element domain onto an -element range.
A function that is both one-to-one and onto is called a bijection. For any bijections to exist, the domain and target must be the same size, that is, , in which case there are bijections mapping one -element set to another.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.