22.2.2. Finding Onto Functions

Welcome everyone! Today, we're diving into the principle of inclusion-exclusion, which helps us find the cardinality of the union of sets. Can anyone tell me what cardinality means?

Isn't it the number of elements in a set?

Exactly! When dealing with two sets, say A and B, the inclusion-exclusion principle states that the cardinality of their union is the sum of their individual cardinalities minus the cardinality of their intersection, so |A ∪ B| = |A| + |B| - |A ∩ B|. Think of it like counting people in overlapping circles!

Why do we subtract the intersection, though?

Great question! If we simply added |A| and |B|, we would count the people in the intersection twice. This way, we accurately count each individual once.

What happens if we extend this to three sets?

Good point! The formula expands to include pairwise intersections and adds back the intersection of all three sets to correct for over-subtraction. We'll denote it like this: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.

Can you summarize what we’ve learned so far?

Sure! The principle of inclusion-exclusion helps us accurately count elements in unions by correcting for over-counting in intersections.

Now, let's generalize this principle to n sets. The formula becomes quite expansive. Can anyone guess what it looks like?

Is it just more additions and subtractions?

Exactly! The formula involves a summation where we alternately add and subtract the intersections of all possible combinations of the sets. This ensures that each element is counted exactly once.

How can we prove it works?

Good thought! A proof by induction works well here. Start with a base case of one set and then add in additional sets while making sure you've correctly accounted for each intersection.

What would be a practical application of this?

Let’s connect this to counting onto functions, where we're interested in functions where every element in the target set has at least one pre-image.

Let’s apply what we’ve learned to count onto functions. Suppose we have a set A with m elements and a set B with n elements. What is an onto function?

It means every element in B gets mapped by at least one element in A!

Exactly! To find the number of onto functions, we subtract the non-onto functions from the total functions. We count non-onto functions using the inclusion-exclusion principle!

Can you show us an example?

Sure! If |A| = 6 and |B| = 3, the total number of functions is |B|^|A|. For non-onto functions, we subtract the cases where one or more images aren’t used. Let’s use our earlier method to count these.

That sounds complicated, but I think I get it!

Awesome! Remember, breaking down the problem using inclusions and exclusions simplifies the counting process significantly.

Lastly, let’s relate this to real-world applications. Can anyone think of a scenario where counting onto functions would be essential?

Like assigning tasks to workers where each task must be assigned to someone?

Great example! Each task must have at least one worker for function mapping. This would be a practical application of counting onto functions.

This is really useful for anything that requires assigned tasks or roles!

Exactly! It’s used in many fields such as operations research, computer science, and economics, showcasing the breadth of combinatorial applications.

Can we summarize what we've learned about onto functions?

Sure! We defined onto functions, connected them to the principle of inclusion-exclusion, and explored their applications in real-world scenarios.